RFR: 8068513: Adding elements to a javascript 'object' (a map) is slow

[Hannes Wallnöfer]

I uploaded a new webrev, please review:

http://cr.openjdk.java.net/~hannesw/8068513/webrev.02/

Changes to previous webrev:

 - updated to consolidated repository layout
 - fixed typos and improved/added some comments
 - improved test

Thanks,
Hannes


> Am 11.09.2017 um 16:18 schrieb Hannes Wallnöfer <hannes.wallnoefer at oracle.com>:
> 
> Unfortunately I rushed the first webrev a bit, and a couple of bugs slipped in.
> 
>  - PropertyHashMap(MapBuilder) constructor checks its own bins field instead of MapBuilder’s for calculating threshold
>  - ElementQueue.cloneAndMerge() updates the queue field in PropertyHashMap instead of just returning cloned and merged bins
> 
> I uploaded a new webrev that fixes these problems, everything I wrote in my original RFR still applies.
> 
> http://cr.openjdk.java.net/~hannesw/8068513/webrev.01/
> 
> Thanks,
> Hannes
> 
> 
>> Am 05.09.2017 um 19:57 schrieb Hannes Wallnöfer <hannes.wallnoefer at oracle.com>:
>> 
>> Please review 8068513: Adding elements to a javascript 'object' (a map) is slow:
>> 
>> Bug: https://bugs.openjdk.java.net/browse/JDK-8068513
>> Webrev: http://cr.openjdk.java.net/~hannesw/8068513/webrev.00/
>> 
>> This adds a new singly linked list called ‚ElementQueue‘ to PropertyHashMap that is used above a certain map size to store newly inserted elements without having to hash them (and therefore clone the bins array) immediately. Instead, The queue is merged into the hash bins at certain intervals, either every 512th insertions, or when a map's queue is searched for properties more than a few times.
>> 
>> Merging the queue every 512 insertions proved to be the best balance between keeping the list searchable (we still need to check it for duplicates when adding elements) and avoiding too frequent cloning.
>> 
>> In order to merge the queue to optimise query performance, the queue field needs to be non-final. To preserve thread safety, ElementQueue bundles both the bins and queue components, so it can replace both with the update of a single reference in PropertyHashMap. The old and new ElementQueue instances logically contain the same elements, so it is safe for other threads to keep using the old instance. I was thinking of maybe making the queue field volatile, but I don’t think this should be an issue.
>> 
>> As part of this change I also added a new MapBuilder class that helps derive new maps from the existing ones by adding, replacing, or removing elements. The code is a bit more complex now with three possible storage data structures (list, bins, queue), but it’s still not too bad.
>> 
>> I made sure that the code used for maps beneath the queue threshold is largely the same as before. Performance of the new combined behaveior is very close to before. The queued implementation itself performs pretty close to the normal implementation (apart from insertion on large maps of course) - I tested much lower thresholds during development, and it was still very good. 
>> 
>> Of course, all tests pass and performance is comparable or maybe slightly faster for some code.
>> 
>> Thanks,
>> Hannes
>