[racket] Hash array mapped tries

From: Jon Zeppieri (zeppieri at gmail.com)
Date: Tue Oct 8 17:33:40 EDT 2013

On Tue, Oct 8, 2013 at 2:28 PM, Asumu Takikawa <asumu at ccs.neu.edu> wrote:
> On 2013-10-04 14:03:00 -0400, Jon Zeppieri wrote:
>> The HAMT library I began working on at the RacketCon Hackathon is now
>> available at [https://github.com/97jaz/hamt]. Suggestions are welcome.
>
> Very nice! Have you tried using the version of `popcount` in the `data`
> library's private interface to see if that's any faster?
>
> https://github.com/plt/racket/blob/master/racket/collects/data/private/count-bits-in-fixnum.rkt
>

I have not (since I didn't know it existed), but I would be surprised
if it were faster. My version trades off space for time by building,
in advance, a vector of popcounts for all 16-bit integers, and it's is
specialized to work on numbers up to 32 bits rather than on all
fixnums. I think it's worthwhile, though, to find out if there is any
measurable performance difference, since it would be nice not to need
a 65536-length vector hanging around.

-Jon

Posted on the users mailing list.