Rose Tree Children Appear to be Eagerly Evaluated (Clojure 1.12+)

Question

To make a long story shorter, I've been aggressively profiling the generative tests I rely on on a daily basis. In CI, they run on memory-constrained machines which have occasionally ended up in OOM states that cause our test executor to kill the nodes running some generative tests. In many cases, we've been able to adjust sizing to get under the line and resume normally. I've been running into that case more frequently, and have been looking for potential causes/levers to adjust in the source code.

The below findings are from my relatively powerful Macbook:

Operating System: MacOS (Tahoe - AArch64)
Clojure version: Verified on 1.12.1, Compared against 1.11.4
JDK vendor and version: OpenJDK 21.0.11

---

Using clj-async-profiler and an allocation/timing macro from Clojure Goes Fast, I benchmarked clojure.test.check.generators against some pretty common generators (Assume I'm using gen as an alias for that namespace):

• gen/string
• gen/large-integer
• (gen/map gen/keyword gen/string)

While benchmarking, ReentrantLock (and ReentrantLock$NonfairSync), accounted for ~1/3rd of all allocations. Since Clojure 1.12, each LazySeq also allocates a ReentrantLock, so I reran the benchmarking after downgrading to Clojure 1.11.4 Obviously, all of those object references were no longer in the profiler results, but the amount of bytes allocated did consistently shrink (~10-15%, depending on the generator).

Most of the allocation appears to be happening while constructing the children segments of nodes in the rose tree. To my knowledge, we only ever lean on the full tree when shrinking results, and wouldn't read them on a generate-only pass. To test that, I wrapped the children arguments to a few of the make-rose calls in the call tree for string generation, and re-instrumented on v.12.1

This approximated the same reduction in memory use as downgrading to 1.11.4, and wiped out almost all of the ReentrantLock allocation events. I've been able to verify the fix does not break any tests, and that shrinking is functional as well.

For posterity / reproduction, the specific call sites I wrapped the children in were:

• clojure.test.check.rose-tree
  • join
  • fmap
  • shrink
  • shrink-vector*
• clojure.test.check.generators
  • int-rose-tree

---

Happy to share the profiler output / git patch if anyone is interested!

Answer 1

diff --git a/src/main/clojure/clojure/test/check/generators.cljc b/src/main/clojure/clojure/test/check/generators.cljc
index 9ec69d2..b503f88 100644
--- a/src/main/clojure/clojure/test/check/generators.cljc
+++ b/src/main/clojure/clojure/test/check/generators.cljc
@@ -238,7 +238,7 @@
 
 (defn- int-rose-tree
   [value]
-  (rose/make-rose value (core/map int-rose-tree (shrink-int value))))
+  (rose/make-rose value (lazy-seq (core/map int-rose-tree (shrink-int value)))))
 
 ;; calc-long is factored out to support testing the surprisingly tricky double math.  Note:
 ;; An extreme long value does not have a precision-preserving representation as a double.
diff --git a/src/main/clojure/clojure/test/check/rose_tree.cljc b/src/main/clojure/clojure/test/check/rose_tree.cljc
index 66ad336..03b0a93 100644
--- a/src/main/clojure/clojure/test/check/rose_tree.cljc
+++ b/src/main/clojure/clojure/test/check/rose_tree.cljc
@@ -61,8 +61,8 @@
         outer-children (children rose)
         inner-root (root outer-root)
         inner-children (children outer-root)]
-    (make-rose inner-root (concat (map join outer-children)
-                                  inner-children))))
+    (make-rose inner-root (lazy-seq (concat (map join outer-children)
+                                            inner-children)))))
 
 (defn pure
   "Puts a value `x` into a Rose tree, with no children."
@@ -74,7 +74,7 @@
   "Applies functions `f` to all values in the tree."
   {:no-doc true}
   [f rose]
-  (make-rose (f (root rose)) (map #(fmap f %) (children rose))))
+  (make-rose (f (root rose)) (lazy-seq (map #(fmap f %) (children rose)))))
 
 (defn bind
   "Takes a Rose tree (m) and a function (k) from
@@ -130,7 +130,7 @@
   [f roses]
   (if (core/seq roses)
     (make-rose (apply f (map root roses))
-               (map #(shrink f %) (remove (unchunk roses))))
+               (lazy-seq (map #(shrink f %) (remove (unchunk roses)))))
     (make-rose (f) [])))
 
 (declare shrink-vector*)
@@ -151,7 +151,7 @@
   [f roses]
   (let [thing (shrink f roses)]
     (make-rose (root thing)
-               (concat (bifurcate f roses) (children thing)))))
+               (lazy-seq (concat (bifurcate f roses) (children thing))))))
 
 (defn shrink-vector
   [f roses]

Answer 2

What's forcing the child seqs?

Comments

`clojure.test.check.rose-tree/remove` is calling `vec` against `roses` to build permutations. I was able to get most of the benefits from above by wrapping the body of `remove` in a `lazy-seq` call.

 `clojure.test.check.rose-tree/shrink-vector` is the main function calling through to `remove`, and that is (in)directly called in the implementation of most of the generators I'm using (`string`, `keyword`, `map`).