Bogdan Popa writes:
> Ah! You're right. When I make the change you suggest, the program
> takes 5s to run. Filed under "Accidentally Not Quadratic" 😅.
The program actually takes 2.5s to run. I missed the fact that I had
made two separate calls to `string-append!` in that version of the
program because the `string-append!` where the source and the
destination were the same ended up being so cheap. The fixed version:
https://gist.github.com/Bogdanp/f36201cd852ac2e363fdaebba1d02709#file-quadratic-no-alloc-rkt
I also wrote a version of that same code with a custom `string-append`
function:
https://gist.github.com/Bogdanp/f36201cd852ac2e363fdaebba1d02709#file-quadratic-with-alloc-rkt
That version takes about 6.7s to run. When I did that, I finally
realized that what I had misinterpreted as allocation overhead was
actually mostly the overhead of zero-filling the newly-allocated string,
which I'd forgotten about.
Here's that same code, but using bytes instead of strings:
https://gist.github.com/Bogdanp/f36201cd852ac2e363fdaebba1d02709#file-quadratic-with-alloc-bytes-rkt
It runs in 2.2s. Finally, a version of that code that uses a custom
byte string implementation that doesn't perform an initialization step:
https://gist.github.com/Bogdanp/f36201cd852ac2e363fdaebba1d02709#file-quadratic-with-alloc-no-fill-rkt
That runs in 870ms, which is a little under half the time of the
previous version, which makes sense to me since the number of iterations
is halved and the GC is being side-stepped.
All that to say I was completely wrong yesterday about allocation being
a big factor here!
Assuming I haven't made any other mistakes and the same 2x improvement
could apply to a version of `string-append` that doesn't try to fill the
newly-allocated string before copying, I wonder if that would be a
worthwhile improvement to make to it.
--
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/m2k0mecvqc.fsf%40defn.io.
