You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@groovy.apache.org by pa...@apache.org on 2026/09/02 20:50:35 UTC

(groovy) branch master updated: GROOVY-12327: JsonSlurper: bound the cost of parsing a wide JSON object

This is an automated email from the ASF dual-hosted git repository.

paulk-asert pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/groovy.git


The following commit(s) were added to refs/heads/master by this push:
     new 6e7b76ff2a GROOVY-12327: JsonSlurper: bound the cost of parsing a wide JSON object
6e7b76ff2a is described below

commit 6e7b76ff2acbda0f8ff200f0a1d3d9866ca92583
Author: Paul King <pa...@asert.com.au>
AuthorDate: Wed Sep 2 16:12:52 2026 +1000

    GROOVY-12327: JsonSlurper: bound the cost of parsing a wide JSON object
    
    LazyMap holds entries in parallel key/value arrays until something asks
    for a key, so the small objects that dominate JSON documents never build
    a backing map. Duplicate-key detection scanned those arrays linearly on
    every put, which costs O(n^2) comparisons for an object of n keys — on
    the default JsonSlurper path, and with the per-comparison cost tunable
    from the document by giving the keys a long common prefix. Past 32
    entries put now builds the backing map and delegates, keeping insertion
    amortized constant-time while leaving narrow objects on the compact
    representation. Parsing 64k keys drops from 3048ms to 18ms, and scales
    linearly rather than quadratically.
    
    Hydration sized its LinkedHashMap with a 0.01 load factor to blunt hash
    collisions, forcing a bucket table ~100x the entry count. Every runtime
    this builds for treeifies a heavily-collided String-keyed bucket by
    itself, so the table now uses the default load factor with capacity to
    match. This matters more once put hydrates during the parse rather than
    on first access: without it, a 0.7MB document of 3000 40-key objects
    retains 104MB read or not, against 10MB now.
---
 .../org/apache/groovy/json/internal/LazyMap.java   | 27 ++++++++--
 .../apache/groovy/json/internal/LazyMapTest.groovy | 61 ++++++++++++++++++++++
 2 files changed, 84 insertions(+), 4 deletions(-)

diff --git a/subprojects/groovy-json/src/main/java/org/apache/groovy/json/internal/LazyMap.java b/subprojects/groovy-json/src/main/java/org/apache/groovy/json/internal/LazyMap.java
index 6099b56a88..219859a26d 100644
--- a/subprojects/groovy-json/src/main/java/org/apache/groovy/json/internal/LazyMap.java
+++ b/subprojects/groovy-json/src/main/java/org/apache/groovy/json/internal/LazyMap.java
@@ -27,8 +27,9 @@ import java.util.Set;
 import java.util.TreeMap;
 
 /**
- * This maps only builds once you ask for a key for the first time.
- * It is designed to not incur the overhead of creating a map unless needed.
+ * A map that defers creating its backing map, so the small objects that dominate JSON documents
+ * do not incur that overhead. Entries are held in parallel key/value arrays until the first
+ * lookup, or until the entry count passes the linear-scan threshold, whichever comes first.
  */
 public class LazyMap extends AbstractMap<String, Object> {
 
@@ -37,6 +38,15 @@ public class LazyMap extends AbstractMap<String, Object> {
      */
     static final String JDK_MAP_ALTHASHING_SYSPROP = System.getProperty("jdk.map.althashing.threshold");
 
+    /*
+     * Entry count past which put(String, Object) stops detecting duplicate keys with a linear scan
+     * of the key array and delegates to the backing map instead. The scan costs O(size) comparisons
+     * per insertion, so an object with many keys would otherwise cost O(size^2) to populate; a
+     * crafted document whose keys share a long common prefix makes each of those comparisons
+     * expensive too. Small objects stay on the compact representation the class exists for.
+     */
+    private static final int LINEAR_SCAN_THRESHOLD = 32;
+
     /* Holds the actual map that will be lazily created. */
     private Map<String, Object> map;
     /* The size of the map. */
@@ -66,6 +76,8 @@ public class LazyMap extends AbstractMap<String, Object> {
 
     /**
      * Stores a mapping while keeping the compact array-backed representation until hydration is needed.
+     * Once the entry count passes the linear-scan threshold, the backing map is built and delegated
+     * to, keeping insertion amortized constant-time for wide objects.
      *
      * @param key entry key
      * @param value entry value
@@ -74,6 +86,10 @@ public class LazyMap extends AbstractMap<String, Object> {
     @Override
     public Object put(String key, Object value) {
         if (map == null) {
+            if (size >= LINEAR_SCAN_THRESHOLD) {
+                buildIfNeeded();
+                return map.put(key, value);
+            }
             for (int i = 0; i < size; i++) {
                 String curKey = keys[i];
                 if ((key == null && curKey == null)
@@ -174,9 +190,12 @@ public class LazyMap extends AbstractMap<String, Object> {
 
     private void buildIfNeeded() {
         if (map == null) {
-            // added to avoid hash collision attack
+            // A TreeMap keeps lookups logarithmic where the runtime's String-keyed hash buckets are
+            // not collision-hardened; later runtimes treeify a heavily-collided bucket themselves, so
+            // a LinkedHashMap sized for its entries is enough. Capacity leaves room for the default
+            // load factor, so hydration fills the table without rehashing it.
             if (Sys.is1_8OrLater() || (Sys.is1_7() && JDK_MAP_ALTHASHING_SYSPROP != null)) {
-                map = new LinkedHashMap<String, Object>(size, 0.01f);
+                map = new LinkedHashMap<String, Object>((int) (size / 0.75f) + 1);
             } else {
                 map = new TreeMap<String, Object>();
             }
diff --git a/subprojects/groovy-json/src/test/groovy/org/apache/groovy/json/internal/LazyMapTest.groovy b/subprojects/groovy-json/src/test/groovy/org/apache/groovy/json/internal/LazyMapTest.groovy
index cdfb96b3e5..3efaf5b707 100644
--- a/subprojects/groovy-json/src/test/groovy/org/apache/groovy/json/internal/LazyMapTest.groovy
+++ b/subprojects/groovy-json/src/test/groovy/org/apache/groovy/json/internal/LazyMapTest.groovy
@@ -18,6 +18,7 @@
  */
 package org.apache.groovy.json.internal
 
+import groovy.json.JsonSlurper
 import org.junit.jupiter.api.BeforeEach
 import org.junit.jupiter.api.Test
 
@@ -383,4 +384,64 @@ class LazyMapTest {
         assertEquals(1, map.size())
         assertEquals("value3", map.get("key"))
     }
+
+    // GROOVY-12327
+    @Test
+    void testBackingMapBuiltOnceEntriesPassLinearScanThreshold() {
+        32.times { i -> map.put("key$i".toString(), i) }
+        assert map.@map == null
+
+        map.put("key32", 32)
+        assert map.@map != null
+        assertEquals(33, map.size())
+    }
+
+    // GROOVY-12327
+    @Test
+    void testWideMapKeepsInsertionOrderAndValues() {
+        200.times { i -> assertNull(map.put("key$i".toString(), i)) }
+
+        assertEquals(200, map.size())
+        assertEquals((0..<200).collect { "key$it".toString() }, map.keySet() as List)
+        assertEquals(0, map.get("key0"))
+        assertEquals(199, map.get("key199"))
+    }
+
+    // GROOVY-12327
+    @Test
+    void testReplaceSemanticsSpanTheLinearScanThreshold() {
+        200.times { i -> map.put("key$i".toString(), i) }
+
+        // a key stored while the compact representation was still active...
+        assertEquals(5, map.put("key5", -5))
+        // ...and one stored after the switch to the backing map
+        assertEquals(150, map.put("key150", -150))
+
+        assertEquals(200, map.size())
+        assertEquals(-5, map.get("key5"))
+        assertEquals(-150, map.get("key150"))
+        assertEquals((0..<200).collect { "key$it".toString() }, map.keySet() as List)
+    }
+
+    // GROOVY-12327
+    @Test
+    void testDuplicateKeyHandlingAfterBuild() {
+        40.times { i -> map.put("key$i".toString(), i) }
+        map.put("key1", "replaced")
+
+        assertEquals(40, map.size())
+        assertEquals("replaced", map.get("key1"))
+        assertEquals((0..<40).collect { "key$it".toString() }, map.keySet() as List)
+    }
+
+    // GROOVY-12327
+    @Test
+    void testWideObjectParsesWithDuplicateKeySpanningThreshold() {
+        def json = '{' + (0..<40).collect { "\"key$it\":$it" }.join(',') + ',"key1":99}'
+        def parsed = new JsonSlurper().parseText(json)
+
+        assertEquals(40, parsed.size())
+        assertEquals(99, parsed.key1)
+        assertEquals((0..<40).collect { "key$it".toString() }, parsed.keySet() as List)
+    }
 }