[PATCH] Speed up srfi-69 by caching current min and max length based on load and *actually resizing*

[Peter Bex]

Hi all,

I'm sure you've all read Ben Hoyt's blog post from earlier this week,
https://benhoyt.com/writings/count-words/

Of course (duh) I tried to implement a version in CHICKEN.  So did
Vasilij and Mario, and we all came to the conclusion that our performance
on that simple task is abysmal, we can't even outperform Python.

So I had a look and came up with one somewhat simple improvement to
srfi-69; every time you insert something into a hash table, it checks
if it needs to be resized.  This check involves a computation which is
needlessly heavy; it multiplies the min and max load factor with the
current length, calls "floor" and inexact->exact on the result, just to
compare it with the new size.

The attached patch moves these calculations to when the hash table is
created or resized, so that it can just read it out when checking for
resize.  It is a bit ugly because now we have 13 slots in the hash table
object, and keeping track of all the indexes becomes a bit cumbersome.
This could be changed in a refactor if necessary.

Then, I noticed that the resize check doesn't actually even resize it
when needed!  The argument passed to hash-table-resize! is "len", while
I think it should be "newsiz".  I've also fixed that in the patch.

This improves performance on my machine by getting the benchmark down
from 12 seconds to 4 seconds using Vasilij's code at http://ix.io/2Ths.
This puts us at least in the same ball park as Python, using the "simple"
version at least (which is comparable in code to Vasilij's).

Cheers,
Peter

srfi-69.patch
Description: Text Data

signature.asc
Description: PGP signature