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
