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 [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/racket-users/m2k0mecvqc.fsf%40defn.io.
