I was poking around in the Macro Stepper for the first time and noticed that a for/list expanded into code involving something called alt-reverse. Does for/list cons each item onto the front of an empty list and then reverse it? That seems very inefficient.
I wrote a little test:
(define (test n)
(time
(for/list ([x (in-range n)])
(list x x)))
(time
(for/fold ([result '()])
([x (in-range n)])
(cons (list x x) result)))
(void))
Indeed the for/list version runs in about 150% of the time of for/fold without reverse, the difference apparently due entirely to additional garbage collection:
> (test 500000)
cpu time: 1059 real time: 2079 gc time: 940
cpu time: 614 real time: 1231 gc time: 550
> (test 500000)
cpu time: 1060 real time: 3889 gc time: 907
cpu time: 770 real time: 1363 gc time: 699
> (test 500000)
cpu time: 1035 real time: 2479 gc time: 917
cpu time: 736 real time: 2535 gc time: 651
It sounds like I shouldn't get in the habit of calling for/list. Is there a more efficient way to make a list in "forward" order (i.e. where the last item evaluated is the last item in the list)?
Looking through the Git history, I see that a change to make for/list avoid reverse was committed, but it didn't work because of a subtle interaction with continuations that could tigger quadtradic-time behavior. (I do wonder if the upcoming move to a Chez Scheme backend might mean that "when Racket one day gets a better implementation of continuations" could actually be coming soon.)
You can build a list in "forward" order by, as the first commit message put it, "consing onto a recursive call." The Racket Guide sections on Tail Recursion and Recursion versus Iteration actually discuss the trade-offs between the map-style and for/fold-style approaches in some detail.
Also, for future reference, the Racket community tends to live more on the very active and friendly racket-users mailing list and to some extent the Slack channel than here on Stack Overflow.