On 27.06.21 19:34, Robby Findler wrote: > On Sun, Jun 27, 2021 at 11:58 AM Alessandro Motta <[email protected] > <mailto:[email protected]>> wrote: > > I also like Jens' code for its pure functional elegance. I'm surprised > that building up a long list of short strings before joining them is so > much faster. After all, isn't the final `string-join` essentially doing > what the original code snipped did? (Clearly not! I will have a look at > the implementation.) > > This is a classic O(n^2) gotcha. Cons is constant work (in terms of the > size of its inputs) and string-append is linear in the size of all of > its arguments. So if you repeatedly string-append in a loop, you'll get > the 1+2+3+4+5+6+7+8+....+n which is O(n^2), but if you collect all the > arguments in a list and then call string-append once at the end, it will > be linear (which implies than string-append isn't naive when it gets a > lot of arguments; it looks at them twice. Once to know how much to > allocate before a second pass to filling in the string).
Thank you for these explanations, Robby and Jens! The parenthetical remarks about the two-pass approach of `string-append` were particularly helpful. That makes sense now. One thing that is still puzzling / worrying me: I completely failed to identify the actual bottleneck when profiling the code. Did I simply misinterpret the profiling output / flame graph? Or is the problem rather that memory allocations and garbage collection are not tracked by the profiler? Thinking about it: Does garbage collection also pause the profiler's sampler thread? That would explain the lack of samples from these code paths, of course. All the best, Alessandro -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/cec30f7f-3166-ce1f-9660-9f305f8cdbd5%40gmail.com.
