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.wallnoe...@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
