On 27.06.21 19:34, Robby Findler wrote: > On Sun, Jun 27, 2021 at 11:58 AM Alessandro Motta <amott...@gmail.com > <mailto:amott...@gmail.com>> 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 racket-users+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/cec30f7f-3166-ce1f-9660-9f305f8cdbd5%40gmail.com.
