# A faster (and safe?) reverse **URL:** \ **Category:** Nice to know\ **Created:** [December 10, 2022, 9:05pm UTC](https://swi-prolog.discourse.group/t/a-faster-and-safe-reverse/6012 "2022-12-10T21:05:57Z")\ **Posts on this page:** 7\ **Page:** 1
**Author:** ![brebs](https://avatars.discourse-cdn.com/v4/letter/b/e9c0ed/32.png) [@brebs](https://swi-prolog.discourse.group/u/brebs)\ **Post date:** [December 10, 2022, 9:05pm UTC](https://swi-prolog.discourse.group/t/a-faster-and-safe-reverse/6012/1 "2022-12-10T21:05:57Z")
reverse/2 uses a variable named `Bound`, to prevent [going off to infinity](https://swi-prolog.discourse.group/t/reverse-2-why-related-to-a-reverse-4-in-spite-of-a-reverse-3/4085) - as a performance penalty on each iteration. However, since the arguments in reverse/2 can be swapped, we can instead use the more usual version, and check whether to swap the arguments to remain safe: ```prolog reverse_faster(Lst, Rev) :- nonvar_first_preferably(Lst, Rev, L, R), reverse_faster_(L, [], R). reverse_faster_([], Ys, Ys). reverse_faster_([X|Xs], Rs, Ys) :- reverse_faster_(Xs, [X|Rs], Ys). nonvar_first_preferably(L1, L2, F1, F2) :- ( nonvar(L1) -> (F1, F2) = (L1, L2) ; nonvar(L2) -> (F1, F2) = (L2, L1) % Preferring not to change the order, if no benefit ; (F1, F2) = (L1, L2) ). ``` This is still safe, and has a surprisingly significant performance improvement: ```prolog ?- numlist(1, 12_000_000, L), garbage_collect, time(reverse(L, R)). % 12,000,002 inferences, 1.227 CPU in 1.229 seconds (100% CPU, 9775973 Lips) % Slightly longer, with arguments swapped ?- numlist(1, 12_000_000, L), garbage_collect, time(reverse(R, L)). % 12,000,002 inferences, 1.400 CPU in 1.401 seconds (100% CPU, 8572785 Lips) vs ?- numlist(1, 12_000_000, L), garbage_collect, time(reverse_faster(L, R)). % 12,000,004 inferences, 0.703 CPU in 0.703 seconds (100% CPU, 17078104 Lips) % Arguments get swapped back, so no performance penalty ?- numlist(1, 12_000_000, L), garbage_collect, time(reverse_faster(R, L)). % 12,000,004 inferences, 0.704 CPU in 0.704 seconds (100% CPU, 17055462 Lips) ``` Presumably this is a candidate to replace the built-in reverse/2? ---
**Author:** ![Boris](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/boris/32/7486_2.png) [@Boris](https://swi-prolog.discourse.group/u/Boris)\ **Post date:** [December 10, 2022, 10:13pm UTC](https://swi-prolog.discourse.group/t/a-faster-and-safe-reverse/6012/2 "2022-12-10T22:13:12Z")
Did you try measuring reversing a short list many times, instead of a very long list once? On my computer, if we reverse in the normal way, it is still faster. Probably the lack of conditional does it? Something like this: ```prolog ?- forall(between(1, 1 000 000, _), reverse([a, b], _). ``` You’d need to have a program that reverses very long lists, or reversing in the opposite direction; then your version would be indeed an improvement. ---
**Author:** ![brebs](https://avatars.discourse-cdn.com/v4/letter/b/e9c0ed/32.png) [@brebs](https://swi-prolog.discourse.group/u/brebs)\ **Post date:** [December 10, 2022, 10:48pm UTC](https://swi-prolog.discourse.group/t/a-faster-and-safe-reverse/6012/3 "2022-12-10T22:48:18Z")
`reverse_faster` is slower with length 2, around the same with length 4, then starts being faster with length 5: ```prolog ?- garbage_collect, time(forall(between(1, 4 000 000, _), reverse([a, b], _))). % 20,000,001 inferences, 0.841 CPU in 0.842 seconds (100% CPU, 23780499 Lips) ?- garbage_collect, time(forall(between(1, 4 000 000, _), reverse_faster([a, b], _))). % 28,000,001 inferences, 0.987 CPU in 0.988 seconds (100% CPU, 28376784 Lips) ?- garbage_collect, time(forall(between(1, 4 000 000, _), reverse([a, b, c, d], _))). % 28,000,001 inferences, 2.384 CPU in 2.386 seconds (100% CPU, 11742584 Lips) ?- garbage_collect, time(forall(between(1, 4 000 000, _), reverse_faster([a, b, c, d], _))). % 36,000,001 inferences, 2.350 CPU in 2.351 seconds (100% CPU, 15320793 Lips) ?- garbage_collect, time(forall(between(1, 4 000 000, _), reverse([a, b, c, d, e], _))). % 32,000,001 inferences, 2.768 CPU in 2.770 seconds (100% CPU, 11562202 Lips) ?- garbage_collect, time(forall(between(1, 4 000 000, _), reverse_faster([a, b, c, d, e], _))). % 40,000,001 inferences, 2.567 CPU in 2.569 seconds (100% CPU, 15581728 Lips) ``` ---
**Author:** ![brebs](https://avatars.discourse-cdn.com/v4/letter/b/e9c0ed/32.png) [@brebs](https://swi-prolog.discourse.group/u/brebs)\ **Post date:** [December 11, 2022, 12:42pm UTC](https://swi-prolog.discourse.group/t/a-faster-and-safe-reverse/6012/4 "2022-12-11T12:42:18Z")
Can be simplified to: ```prolog reverse_fast(Lst, Rev) :- nonvar(Lst), !, reverse_fast_(Lst, [], Rev). reverse_fast(Lst, Rev) :- reverse_fast_(Rev, [], Lst). reverse_fast_([], Ys, Ys). reverse_fast_([X|Xs], Rs, Ys) :- reverse_fast_(Xs, [X|Rs], Ys). ``` … which starts being faster at length 2: ```prolog ?- garbage_collect, time(forall(between(1, 4 000 000, _), reverse([a, b], _))). % 20,000,001 inferences, 0.836 CPU in 0.837 seconds (100% CPU, 23910204 Lips) ?- garbage_collect, time(forall(between(1, 4 000 000, _), reverse_fast([a, b], _))). % 20,000,001 inferences, 0.709 CPU in 0.709 seconds (100% CPU, 28213667 Lips) ``` ---
**Author:** ![brebs](https://avatars.discourse-cdn.com/v4/letter/b/e9c0ed/32.png) [@brebs](https://swi-prolog.discourse.group/u/brebs)\ **Post date:** [December 26, 2022, 6:09pm UTC](https://swi-prolog.discourse.group/t/a-faster-and-safe-reverse/6012/5 "2022-12-26T18:09:35Z")
To also prevent: ```prolog ?- reverse_fast([a,b|T], [c,b,a]). T = [c] ; ERROR: Stack limit (1.0Gb) exceeded ``` … have to check using is\_list/1 and then nonvar/1, resulting in: ```prolog reverse_fast(L, R) :- % For reverse_fast([a,b|T], [c,b,a]). ( ( is_list(L) % For reverse_fast(L, [a,b]). ; \+ is_list(R), nonvar(L) ) -> reverse_fast_(L, [], R) ; reverse_fast_(R, [], L) ). reverse_fast_([], Ys, Ys). reverse_fast_([X|Xs], Rs, Ys) :- reverse_fast_(Xs, [X|Rs], Ys). ``` … which is faster than the current reverse/2 in all of: ```prolog ?- garbage_collect, time(forall(between(1, 4 000 000, _), reverse(L, [a]))). % 16,000,001 inferences, 0.866 CPU in 0.867 seconds (100% CPU, 18465102 Lips) ?- garbage_collect, time(forall(between(1, 4 000 000, _), reverse_fast(L, [a]))). % 28,000,001 inferences, 0.743 CPU in 0.743 seconds (100% CPU, 37702855 Lips) ?- garbage_collect, time(forall(between(1, 4 000 000, _), reverse([a], _))). % 16,000,001 inferences, 0.761 CPU in 0.762 seconds (100% CPU, 21014563 Lips) ?- garbage_collect, time(forall(between(1, 4 000 000, _), reverse_fast([a], _))). % 20,000,001 inferences, 0.625 CPU in 0.625 seconds (100% CPU, 32004282 Lips) ?- garbage_collect, time(forall(between(1, 4 000 000, _), reverse(L, [a|T]))). % 16,000,001 inferences, 0.957 CPU in 0.958 seconds (100% CPU, 16721772 Lips) ?- garbage_collect, time(forall(between(1, 4 000 000, _), reverse_fast(L, [a|T]))). % 32,000,001 inferences, 0.910 CPU in 0.911 seconds (100% CPU, 35153104 Lips) ``` ---
**Author:** ![brebs](https://avatars.discourse-cdn.com/v4/letter/b/e9c0ed/32.png) [@brebs](https://swi-prolog.discourse.group/u/brebs)\ **Post date:** [December 27, 2022, 4:40pm UTC](https://swi-prolog.discourse.group/t/a-faster-and-safe-reverse/6012/6 "2022-12-27T16:40:08Z")
As helpfully [pointed out](https://stackoverflow.com/questions/74922561/recursion-in-prolog-reversing-a-list) by @false: ```prolog ?- freeze(L,false), reverse(L,R). false. ?- freeze(L,false), reverse_fast(L,R). ERROR: Stack limit (1.0Gb) exceeded ``` … so it’s not general enough to replace reverse/2. ---
**Author:** ![brebs](https://avatars.discourse-cdn.com/v4/letter/b/e9c0ed/32.png) [@brebs](https://swi-prolog.discourse.group/u/brebs)\ **Post date:** [February 5, 2023, 3:52pm UTC](https://swi-prolog.discourse.group/t/a-faster-and-safe-reverse/6012/7 "2023-02-05T15:52:14Z")
I thought of a different method - starting at the empty tail of the reversed list, then repeatedly adding a head: ```prolog reverse_better([], []). reverse_better([H|T], [RH|RT]) :- % Prevent infinity after 1st solution: reverse_better(L, [a]) ( is_list(T) -> reverse_better_(T, H, RH, [], RT) ; reverse_better_(RT, RH, H, [], T) ). reverse_better_([], P, P, RT, RT). reverse_better_([H|T], P, RH, RT, RTF) :- reverse_better_(T, H, RH, [P|RT], RTF). ``` This fails as intended with the freeze/2 test above, and is **faster** than the built-in reverse/2: ```prolog ?- garbage_collect, time(forall(between(1, 4 000 000, _), reverse([a, b], _))). % 20,000,001 inferences, 0.907 CPU in 0.908 seconds (100% CPU, 22055617 Lips) ?- garbage_collect, time(forall(between(1, 4 000 000, _), reverse_better([a, b], _))). % 20,000,001 inferences, 0.794 CPU in 0.795 seconds (100% CPU, 25182747 Lips) ``` ```prolog ?- garbage_collect, numlist(1, 100, L), time(forall(between(1, 1_000_000, _), reverse(L, _))). % 103,000,001 inferences, 4.653 CPU in 4.656 seconds (100% CPU, 22137726 Lips) ?- garbage_collect, numlist(1, 100, L), time(forall(between(1, 1_000_000, _), reverse_better(L, _))). % 103,000,001 inferences, 3.362 CPU in 3.369 seconds (100% CPU, 30637854 Lips) ``` ```prolog ?- garbage_collect, numlist(1, 12_000_000, L), time(reverse(L, R)). % 12,000,002 inferences, 0.628 CPU in 0.629 seconds (100% CPU, 19115214 Lips) ?- garbage_collect, numlist(1, 12_000_000, L), time(reverse_better(L, R)). % 12,000,002 inferences, 0.366 CPU in 0.367 seconds (100% CPU, 32757865 Lips) ``` Edit: With swi-prolog 9.0.4, the performance benefit has gone 🙃