I think you found a slowdown that's just a severe as the one we've been talking about and, once that one'd been cleared up, you might have seen the other one, perhaps in the calls to string-append. But you are right that some costs (like gc) are smeared out across the whole computation and thus hard to identify with profiling (hence Bogdan's helpful hint about gc logging).
Robby On Mon, Jun 28, 2021 at 2:18 PM Alessandro Motta <amott...@gmail.com> wrote: > 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/CAL3TdOMpMpfY4CW8y%2BUZHJFm3Wyv0yYdDhFSvXEfSg6zaDFKNA%40mail.gmail.com.
