Reducing the cost of garbage collecting small arrays

[Johan Tibell]

On Thu, Jun 23, 2011 at 12:31 AM, Jan-Willem Maessen
<jmaessen at alum.mit.edu> wrote:
> On Wed, Jun 22, 2011 at 12:33 PM, Johan Tibell <johan.tibell at gmail.com> wrote:
>> Hi,
>>
>> Now when we can efficiently copy small arrays I've gone back to
>> benchmarking/optimizing my hash array mapped trie data structure. The
>> data structure's performance depends on how efficiently we can
>> allocate/collect/copy Array#s and MutableArrays#s of size <=32.
>> Speeding up copying helped quite a bit, but the HAMT is still slower
>> than a Patricia tree for inserts.
>
> Is 5 the optimal number of bits to slice off at a time (ie the best
> fanout)?  It sounds like node copy cost on insert argues for a
> slightly narrower fanout.  You'll be evacuating / scanning more words
> total, but new nodes may equate to less scanning overall (especially
> if this is running long enough to have some nodes get tenure).

I'm experimenting with this. 6 is far too much, making inserts 4-5x
slower. 4 doesn't seem to improve things much (which is a bit
counter-intuitive given that 6 made things so much work), but I need
to experiment some more.

Cheers,
Johan