VM: _CompactLinkedHashSet and _InternalLinkedHashMap are too big for small collections

[rakudrama]

_CompactLinkedHashSet (default Set implmentation) and _InternalLinkedHashMap (default Map) have good asymptotic storage efficiency as the size of the collection grows. They are always better than conveniently available alternatives above 10 elements and are designed for better locality.

For small collections they have poor storage efficiency. In dart2js there are many small sets and maps, so this is noticeable. dart2js uses two classes, Setlet and Maplet because the poor storage efficiency.

It would be nice if this use of specialized implementations was not necessary.

This table shows the size in bytes for various kinds of Set:

     length:  0    1    2    3    4    5    6    7    8    9    40
Set         240  240  240  240  240  240  240  240  240  496  1120
HashSet     144  176  208  240  272  306  400  432  464  496  1872
Setlet       32   32  128  128  128  128  128  128  128  528  1152

Maps show a similar pattern, just a bit bigger. The empty map {} is 304 bytes.
Can the VM-provided implementations be more efficient in the common case of a small collections?

---

I tried switching from Setlet to Set. One thing surprised me: more calls to get:hashCode. Setlet can add an element to an empty set without calling get:hashCode. Perhaps special handling for small numbers of elements could also have this efficiency.

[iposva-google]

We can definitely make them a bit more space-efficient (or even better less hashCode calling) for small sets. It is something we have discussed in the past, but have not felt the urgent need due to the Setlet and Maplet use in dart2js for example. The resulting implementation might not be as efficient as Setlet, but definitely better than currently.

@rakudrama I am assuming your quoted numbers are on a x64 build, correct?

[rakudrama]

Yes, these are x64 measurements.

[rakudrama]

Maybe change the initial capacity to 4 instead of 8.
Another thing to look at is the underlying _List has 3 'overhead' words (header, type, length), so an odd allocation length would reduce internal fragmentation (by 1 word).

[rakudrama]

This is still an issue.

My latest experience is debugging a 'huge heap' issue where I have 3.1M objects each with a Map. Most are singleton maps. Each empty or singleton Map is 320 bytes or 6x the size of the owning object. Sometimes it is possible to use a nullable field with the convention 'null-means-empty', but that doesn't work in the case where most Maps are singletons.

We could use the Maplet work-around, but the fact that we are often using a work-around is just a symptom that the default built-in Set/Map is not as good as it could be.

Can the default implementations be better?

• An empty Set/Map could be created with zero capacity using shared dummy 'constant' storage, similar to an empty _GrowableList. This would reduce the allocation for maps that are never filled.
• Then when the storage is actually allocated on first insertion, use a smaller starting the capacity not penalize very small Maps as much as the current scheme.

I tried making the default capacity be 2 elements and it seems to improve the dart2js compile MemoryUse benchmarks by about 4% (2%-10%). At this setting, the VM JSON parse benchmarks are slower, presumably because they grow a Map and do rehashing. There is a TODO to avoid rehashing by reusing the existing hash bits in the index, so perhaps the initial growing could be much faster.

I would expect that the large size of empty and small maps is something worth improving for mobile apps.

[rakudrama]

I have just been looking at the dart2js heap and rediscovered the above data.

In my large program compile scenario, the heap is reduced by 4% with an initial capacity of 2 elements.
The heap allocated to Uint32List dropped from 639MB to 487MB.
There is also a drop in _List storage which would be twice as much (this cross-checks as about 4% of the 10GB heap).

The mean length of a Uint32List (i.e. excluding header) dropped from 31 to 22, which shows there really are a lot of small Maps. (The initial capacity of 8 allocates an index Uint32List(16) and an initial capacity of 2 allocates Uint32List(4). We retain 9 of the 12 slots saved, so >75% of maps have four entries or fewer).

There are many singleton maps, so an initial non-empty capacity of 1 would save a little more storage (I tried this but the code does not work - it probably expects the mask for the data index to not be zero-width, which could probably be fixed with careful recoding).

There are also a few huge maps (> 1M entries) where the size is only a little over some 2^k.
These would benefit from growing to an intermediate size.
We can grow the index in powers of two but the data more often.
The growing step from 1.5×2^k to 2×2^k can use the same index if there have been no or few deletions.

[rakudrama]

Accessing 'all instances' programatically in Observatory, I can confirm 76% of Maps have two or fewer elements, 85% have four or fewer.

expr	result	x
this.where((dynamic x)=> x.length >= 0).length	2788029	✖ Remove
this.where((dynamic x)=> x.length == 0).length	1110611	✖ Remove
this.where((dynamic x)=> x.length == 1).length	574449	✖ Remove
this.where((dynamic x)=> x.length == 2).length	437808	✖ Remove
this.where((dynamic x)=> x.length == 3).length	162133	✖ Remove
this.where((dynamic x)=> x.length == 4).length	83673	✖ Remove
this.where((dynamic x)=> x.length == 5).length	81964	✖ Remove
this.where((dynamic x)=> x.length == 6).length	64605	✖ Remove
this.where((dynamic x)=> x.length == 7).length	35858	✖ Remove
this.where((dynamic x)=> x.length == 8).length	21775	✖ Remove
this.where((dynamic x)=> x.length == 9).length	23715	✖ Remove
this.where((dynamic x)=> x.length>=10 && x.length <20).length	109050	✖ Remove
this.where((dynamic x)=> x.length>=20 && x.length <50).length	61962	✖ Remove
this.where((dynamic x)=>x.length>50).length	19882	✖ Remove
this.where((dynamic x)=>x.length>100).length	7015	✖ Remove
this.where((dynamic x)=>x.length>1000).length	501	✖ Remove
this.where((dynamic x)=>x.length>10000).length	96	✖ Remove
this.where((dynamic x)=>x.length>100000).length	23	✖ Remove
this.where((dynamic x)=>x.length>1000000).length	0	✖ Remove

FYI @rmacnak-google