# HG changeset patch
# User hannesw
# Date 1508171227 -7200
# Node ID fff3970bd14fc3d1b79750128aa62250c212c530
# Parent  d65c3b21081c589228377b3a9a17202805e53890
8068513: Adding elements to a javascript 'object' (a map) is slow
Reviewed-by: jlaskey, sundar

diff -r d65c3b21081c -r fff3970bd14f src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/PropertyHashMap.java
--- a/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/PropertyHashMap.java	Fri Sep 01 14:04:20 2017 +0200
+++ b/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/PropertyHashMap.java	Mon Oct 16 18:27:07 2017 +0200
@@ -31,23 +31,34 @@
 import java.util.HashSet;
 import java.util.Map;
 import java.util.Set;
+import jdk.nashorn.internal.runtime.options.Options;
 
 /**
- * Immutable hash map implementation for properties.  Properties are keyed on strings.
- * Copying and cloning is avoided by relying on immutability.
+ * Immutable hash map implementation for properties. Properties are keyed on strings
+ * or symbols (ES6). Copying and cloning is avoided by relying on immutability.
  * <p>
  * When adding an element to a hash table, only the head of a bin list is updated, thus
  * an add only requires the cloning of the bins array and adding an element to the head
  * of the bin list.  Similarly for removal, only a portion of a bin list is updated.
  * <p>
+ * For large tables with hundreds or thousands of elements, even just cloning the bins
+ * array when adding properties is an expensive operation. For this case, we put new
+ * elements in a separate list called {@link ElementQueue}.
+ * The list component is merged into the hash table at regular intervals during element
+ * insertion to keep it from growing too long. Also, when a map with a queue component
+ * is queried repeatedly, the map will replace itself with a pure hash table version
+ * of itself to optimize lookup performance.
+ * <p>
  * A separate chronological list is kept for quick generation of keys and values, and,
- * for rehashing.
+ * for rehashing. For very small maps where the overhead of the hash table would
+ * outweigh its benefits we deliberately avoid creating a hash structure and use the
+ * chronological list alone for element storage.
  * <p>
  * Details:
  * <p>
  * The main goal is to be able to retrieve properties from a map quickly, keying on
- * the property name (String.)  A secondary, but important goal, is to keep maps
- * immutable, so that a map can be shared by multiple objects in a context.
+ * the property name (String or Symbol). A secondary, but important goal, is to keep
+ * maps immutable, so that a map can be shared by multiple objects in a context.
  * Sharing maps allows objects to be categorized as having similar properties, a
  * fact that call site guards rely on.  In this discussion, immutability allows us
  * to significantly reduce the amount of duplication we have in our maps.
@@ -109,6 +120,9 @@
     /** Threshold before using bins. */
     private static final int LIST_THRESHOLD = 8;
 
+    /** Threshold before adding new elements to queue instead of directly adding to hash bins. */
+    private static final int QUEUE_THRESHOLD = Options.getIntProperty("nashorn.propmap.queue.threshold", 500);
+
     /** Initial map. */
     public static final PropertyHashMap EMPTY_HASHMAP = new PropertyHashMap();
 
@@ -122,7 +136,10 @@
     private final Element list;
 
     /** Hash map bins. */
-    private final Element[] bins;
+    private Element[] bins;
+
+    /** Queue for adding elements to large maps with delayed hashing. */
+    private ElementQueue queue;
 
     /** All properties as an array (lazy). */
     private Property[] properties;
@@ -134,33 +151,26 @@
         this.size      = 0;
         this.threshold = 0;
         this.bins      = null;
+        this.queue     = null;
         this.list      = null;
     }
 
     /**
-     * Clone Constructor
+     * Constructor used internally to create new maps
      *
-     * @param map Original {@link PropertyHashMap}.
+     * @param map the new map
      */
-    private PropertyHashMap(final PropertyHashMap map) {
+    private PropertyHashMap(final MapBuilder map) {
         this.size      = map.size;
-        this.threshold = map.threshold;
-        this.bins      = map.bins;
+        if (map.qhead == null) {
+            this.bins = map.bins;
+            this.queue = null;
+        } else {
+            this.bins = null;
+            this.queue = new ElementQueue(map.qhead, map.bins);
+        }
         this.list      = map.list;
-    }
-
-    /**
-     * Constructor used internally to extend a map
-     *
-     * @param size Size of the new {@link PropertyHashMap}.
-     * @param bins The hash bins.
-     * @param list The {@link Property} list.
-     */
-    private PropertyHashMap(final int size, final Element[] bins, final Element list) {
-        this.size      = size;
-        this.threshold = bins != null ? threeQuarters(bins.length) : 0;
-        this.bins      = bins;
-        this.list      = list;
+        this.threshold = map.bins != null ? threeQuarters(map.bins.length) : 0;
     }
 
     /**
@@ -173,7 +183,9 @@
     public PropertyHashMap immutableReplace(final Property property, final Property newProperty) {
         assert property.getKey().equals(newProperty.getKey()) : "replacing properties with different keys: '" + property.getKey() + "' != '" + newProperty.getKey() + "'";
         assert findElement(property.getKey()) != null         : "replacing property that doesn't exist in map: '" + property.getKey() + "'";
-        return cloneMap().replaceNoClone(property.getKey(), newProperty);
+        final MapBuilder builder = newMapBuilder(size);
+        builder.replaceProperty(property.getKey(), newProperty);
+        return new PropertyHashMap(builder);
     }
 
     /**
@@ -185,9 +197,9 @@
      */
     public PropertyHashMap immutableAdd(final Property property) {
         final int newSize = size + 1;
-        PropertyHashMap newMap = cloneMap(newSize);
-        newMap = newMap.addNoClone(property);
-        return newMap;
+        MapBuilder builder = newMapBuilder(newSize);
+        builder.addProperty(property);
+        return new PropertyHashMap(builder);
     }
 
     /**
@@ -199,11 +211,11 @@
      */
     public PropertyHashMap immutableAdd(final Property... newProperties) {
         final int newSize = size + newProperties.length;
-        PropertyHashMap newMap = cloneMap(newSize);
+        MapBuilder builder = newMapBuilder(newSize);
         for (final Property property : newProperties) {
-            newMap = newMap.addNoClone(property);
+            builder.addProperty(property);
         }
-        return newMap;
+        return new PropertyHashMap(builder);
     }
 
     /**
@@ -216,27 +228,16 @@
     public PropertyHashMap immutableAdd(final Collection<Property> newProperties) {
         if (newProperties != null) {
             final int newSize = size + newProperties.size();
-            PropertyHashMap newMap = cloneMap(newSize);
+            MapBuilder builder = newMapBuilder(newSize);
             for (final Property property : newProperties) {
-                newMap = newMap.addNoClone(property);
+                builder.addProperty(property);
             }
-            return newMap;
+            return new PropertyHashMap(builder);
         }
         return this;
     }
 
     /**
-     * Clone a {@link PropertyHashMap} and remove a {@link Property}.
-     *
-     * @param property {@link Property} to remove.
-     *
-     * @return New {@link PropertyHashMap}.
-     */
-    public PropertyHashMap immutableRemove(final Property property) {
-        return immutableRemove(property.getKey());
-    }
-
-    /**
      * Clone a {@link PropertyHashMap} and remove a {@link Property} based on its key.
      *
      * @param key Key of {@link Property} to remove.
@@ -244,22 +245,10 @@
      * @return New {@link PropertyHashMap}.
      */
     public PropertyHashMap immutableRemove(final Object key) {
-        if (bins != null) {
-            final int binIndex = binIndex(bins, key);
-            final Element bin = bins[binIndex];
-            if (findElement(bin, key) != null) {
-                final int newSize = size - 1;
-                Element[] newBins = null;
-                if (newSize >= LIST_THRESHOLD) {
-                    newBins = bins.clone();
-                    newBins[binIndex] = removeFromList(bin, key);
-                }
-                final Element newList = removeFromList(list, key);
-                return new PropertyHashMap(newSize, newBins, newList);
-            }
-        } else if (findElement(list, key) != null) {
-            final int newSize = size - 1;
-            return newSize != 0 ? new PropertyHashMap(newSize, null, removeFromList(list, key)) : EMPTY_HASHMAP;
+        MapBuilder builder = newMapBuilder(size);
+        builder.removeProperty(key);
+        if (builder.size < size) {
+            return builder.size != 0 ? new PropertyHashMap(builder) : EMPTY_HASHMAP;
         }
         return this;
     }
@@ -356,7 +345,9 @@
      * @return {@link Element} matching key or {@code null} if not found.
      */
     private Element findElement(final Object key) {
-        if (bins != null) {
+        if (queue != null) {
+            return queue.find(key);
+        } else if (bins != null) {
             final int binIndex = binIndex(bins, key);
             return findElement(bins[binIndex], key);
         }
@@ -380,73 +371,52 @@
         return null;
     }
 
-
-    private PropertyHashMap cloneMap() {
-        return new PropertyHashMap(size, bins == null ? null : bins.clone(), list);
-    }
-
     /**
-     * Clone {@link PropertyHashMap} to accommodate new size.
+     * Create a {@code MapBuilder} to add new elements to.
      *
      * @param newSize New size of {@link PropertyHashMap}.
      *
-     * @return Cloned {@link PropertyHashMap} with new size.
+     * @return {@link MapBuilder} for the new size.
      */
-    private PropertyHashMap cloneMap(final int newSize) {
-        Element[] newBins;
-        if (bins == null && newSize <= LIST_THRESHOLD) {
-            newBins = null;
+    private MapBuilder newMapBuilder(final int newSize) {
+        if (bins == null && newSize < LIST_THRESHOLD) {
+            return new MapBuilder(bins, list, size, false);
         } else if (newSize > threshold) {
-            newBins = rehash(list, binsNeeded(newSize));
+            return new MapBuilder(rehash(list, binsNeeded(newSize)), list, size, true);
+        } else if (shouldCloneBins(size, newSize)) {
+            return new MapBuilder(cloneBins(), list, size, true);
+        } else if (queue == null) {
+            return new MapBuilder(bins, list, size, false);
         } else {
-            newBins = bins.clone();
+            return new MapBuilder(queue, list, size, false);
         }
-        return new PropertyHashMap(newSize, newBins, list);
     }
 
-
-
     /**
-     * Add a {@link Property} to a temporary {@link PropertyHashMap}, that has
-     * been already cloned.  Removes duplicates if necessary.
+     * Create a cloned or new bins array and merge the elements in the queue into it if there are any.
      *
-     * @param property {@link Property} to add.
-     *
-     * @return New {@link PropertyHashMap}.
+     * @return the cloned bins array
      */
-    private PropertyHashMap addNoClone(final Property property) {
-        int newSize = size;
-        final Object key = property.getKey();
-        Element newList = list;
-        if (bins != null) {
-            final int binIndex = binIndex(bins, key);
-            Element bin = bins[binIndex];
-            if (findElement(bin, key) != null) {
-                newSize--;
-                bin = removeFromList(bin, key);
-                newList = removeFromList(list, key);
-            }
-            bins[binIndex] = new Element(bin, property);
-        } else {
-            if (findElement(list, key) != null) {
-                newSize--;
-                newList = removeFromList(list, key);
-            }
+    private Element[] cloneBins() {
+        if (queue != null) {
+            return queue.cloneAndMergeBins();
         }
-        newList = new Element(newList, property);
-        return new PropertyHashMap(newSize, bins, newList);
+
+        return bins.clone();
     }
 
-    private PropertyHashMap replaceNoClone(final Object key, final Property property) {
-        if (bins != null) {
-            final int binIndex = binIndex(bins, key);
-            Element bin = bins[binIndex];
-            bin = replaceInList(bin, key, property);
-            bins[binIndex] = bin;
-        }
-        Element newList = list;
-        newList = replaceInList(newList, key, property);
-        return new PropertyHashMap(size, bins, newList);
+    /**
+     * Used on insertion to determine whether the bins array should be cloned, or we should keep
+     * using the ancestor's bins array and put new elements into the queue.
+     *
+     * @param oldSize the old map size
+     * @param newSize the new map size
+     * @return whether to clone the bins array
+     */
+    private boolean shouldCloneBins(final int oldSize, final int newSize) {
+        // For maps with less than QUEUE_THRESHOLD elements we clone the bins array on every insertion.
+        // Above that threshold we put new elements into the queue and only merge every 512  elements.
+        return newSize < QUEUE_THRESHOLD || (newSize >>> 9) > (oldSize >>> 9);
     }
 
     /**
@@ -681,4 +651,210 @@
         }
     }
 
+    /**
+     * A hybrid map/list structure to add elements to the map without the need to clone and rehash the main table.
+     * This is used for large maps to reduce the overhead of adding elements. Instances of this class can replace
+     * themselves with a pure hash map version of themselves to optimize query performance.
+     */
+    private class ElementQueue {
+
+        /** List of elements not merged into bins */
+        private final Element qhead;
+
+        /** Our own bins array. Differs from original PropertyHashMap bins when queue is merged. */
+        private final Element[] qbins;
+
+        /** Count searches to trigger merging of queue into bins. */
+        int searchCount = 0;
+
+        ElementQueue(final Element qhead, final Element[] qbins) {
+            this.qhead = qhead;
+            this.qbins = qbins;
+        }
+
+        Element find(final Object key) {
+            final int binIndex = binIndex(qbins, key);
+            final Element element = findElement(qbins[binIndex], key);
+            if (element != null) {
+                return element;
+            }
+            if (qhead != null) {
+                if (++searchCount > 2) {
+                    // Merge the queue into the hash bins if this map is queried more than a few times
+                    final Element[] newBins = cloneAndMergeBins();
+                    assert newBins != qbins;
+                    PropertyHashMap.this.queue = new ElementQueue(null, newBins);
+                    return PropertyHashMap.this.queue.find(key);
+                }
+                return findElement(qhead, key);
+            }
+            return null;
+        }
+
+        /**
+         * Create a cloned or new bins array and merge the elements in the queue into it if there are any.
+         *
+         * @return the cloned bins array
+         */
+        private Element[] cloneAndMergeBins() {
+            if (qhead == null) {
+                return qbins;
+            }
+
+            final Element[] newBins = qbins.clone();
+
+            for (Element element = qhead; element != null; element = element.getLink()) {
+                final Property property = element.getProperty();
+                final Object key = property.getKey();
+                final int binIndex = binIndex(newBins, key);
+
+                newBins[binIndex] = new Element(newBins[binIndex], property);
+            }
+
+            return newBins;
+        }
+
+    }
+
+    /**
+     * A builder class used for adding, replacing, or removing elements.
+     */
+    private static class MapBuilder {
+
+        /** Bins array - may be shared with map that created us. */
+        private Element[] bins;
+        /** Whether our bins are shared */
+        private boolean hasOwnBins;
+
+        /** Queue of unmerged elements */
+        private Element qhead;
+
+        /** Full property list. */
+        private Element list;
+
+        /** Number of properties. */
+        private int size;
+
+        MapBuilder(final Element[] bins, final Element list, final int size, final boolean hasOwnBins) {
+            this.bins  = bins;
+            this.hasOwnBins = hasOwnBins;
+            this.list  = list;
+            this.qhead = null;
+            this.size  = size;
+        }
+
+        MapBuilder(final ElementQueue queue, final Element list, final int size, final boolean hasOwnBins) {
+            this.bins  = queue.qbins;
+            this.hasOwnBins = hasOwnBins;
+            this.list  = list;
+            this.qhead = queue.qhead;
+            this.size  = size;
+        }
+
+        /**
+         * Add a {@link Property}. Removes duplicates if necessary.
+         *
+         * @param property {@link Property} to add.
+         */
+        private void addProperty(final Property property) {
+            final Object key = property.getKey();
+
+            if (bins != null) {
+                final int binIndex = binIndex(bins, key);
+                if (findElement(bins[binIndex], key) != null) {
+                    ensureOwnBins();
+                    bins[binIndex] = removeExistingElement(bins[binIndex], key);
+                } else if (findElement(qhead, key) != null) {
+                    qhead = removeExistingElement(qhead, key);
+                }
+                if (hasOwnBins) {
+                    bins[binIndex] = new Element(bins[binIndex], property);
+                } else {
+                    qhead = new Element(qhead, property);
+                }
+            } else {
+                if (findElement(list, key) != null) {
+                    list = removeFromList(list, key);
+                    size--;
+                }
+            }
+
+            list = new Element(list, property);
+            size++;
+        }
+
+        /**
+         * Replace an existing {@link Property} with a new one with the same key.
+         *
+         * @param key the property key
+         * @param property the property to replace the old one with
+         */
+        private void replaceProperty(final Object key, final Property property) {
+
+            if (bins != null) {
+                final int binIndex = binIndex(bins, key);
+                Element bin = bins[binIndex];
+                if (findElement(bin, key) != null) {
+                    ensureOwnBins();
+                    bins[binIndex] = replaceInList(bin, key, property);
+                } else if (qhead != null) {
+                    qhead = replaceInList(qhead, key, property);
+                }
+            }
+
+            list = replaceInList(list, key, property);
+        }
+
+        /**
+         * Remove a {@link Property} based on its key.
+         *
+         * @param key Key of {@link Property} to remove.
+         */
+        void removeProperty(final Object key) {
+
+            if (bins != null) {
+                final int binIndex = binIndex(bins, key);
+                final Element bin = bins[binIndex];
+                if (findElement(bin, key) != null) { ;
+                    if (size >= LIST_THRESHOLD) {
+                        ensureOwnBins();
+                        bins[binIndex] = removeFromList(bin, key);
+                    } else {
+                        // Go back to list-only representation for small maps
+                        bins = null;
+                        qhead = null;
+                    }
+                } else if (findElement(qhead, key) != null) {
+                    qhead = removeFromList(qhead, key);
+                }
+            }
+
+            list = removeFromList(list, key);
+            size--;
+        }
+
+        /**
+         * Removes an element known to exist from an element list and the main {@code list} and decreases {@code size}.
+         *
+         * @param element the element list
+         * @param key the key to remove
+         * @return the new element list
+         */
+        private Element removeExistingElement(Element element, Object key) {
+            size--;
+            list = removeFromList(list, key);
+            return removeFromList(element, key);
+        }
+
+        /**
+         * Make sure we own the bins we have, cloning them if necessary.
+         */
+        private void ensureOwnBins() {
+            if (!hasOwnBins) {
+                bins = bins.clone();
+            }
+            hasOwnBins = true;
+        }
+    }
+
 }
diff -r d65c3b21081c -r fff3970bd14f test/nashorn/script/basic/JDK-8068513.js
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/nashorn/script/basic/JDK-8068513.js	Mon Oct 16 18:27:07 2017 +0200
@@ -0,0 +1,95 @@
+/*
+ * Copyright (c) 2017, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ * 
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ * 
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ * 
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ * 
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/**
+ * JDK-8068513: Adding elements to a javascript 'object' (a map) is slow
+ *
+ * @test
+ * @run
+ */
+
+var map = {};
+var keys = [];
+var values = [];
+
+for (i = 0; i < 5000; i++) {
+    var key = 'key' + i;
+    var value = i;
+    keys.push(key);
+    values.push(value);
+    map[key] = value;
+}
+
+function testAssertions() {
+    Assert.assertTrue(Object.keys(map).length === values.length);
+
+    var c = 0;
+    for (var k in map) {
+        Assert.assertTrue(k === keys[c]);
+        Assert.assertTrue(map[k] === values[c]);
+        c++;
+    }
+
+    Assert.assertTrue(c === values.length);
+}
+
+// redefine existing property
+Object.defineProperty(map, "key2000", { enumerable: true, get: function() { return 'new value 2000' } });
+values[2000] = 'new value 2000';
+
+testAssertions();
+
+// define new property
+Object.defineProperty(map, "defined property", { enumerable: true, configurable: true, get: function() { return 13 } });
+keys.push('defined property');
+values.push(13);
+
+testAssertions();
+
+// delete and redefine
+delete map.key3000;
+map.key3000 = 'new value';
+keys.splice(3000, 1);
+values.splice(3000, 1);
+keys.push('key3000');
+values.push('new value');
+
+testAssertions();
+
+// delete all properties
+while (values.length > 0) {
+    values.pop();
+    delete map[keys.pop()];
+}
+
+testAssertions();
+
+// add a few new ones
+for (var i = 0; i < 1000; i++) {
+    keys.push('k' + i);
+    values.push('v' + i);
+    map['k' + i] = 'v' + i;
+}
+
+testAssertions();
+