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)
+ }
}