Performance issue of generators with spec.alpha/merge

[pithyless]

I've been trying to debug some performance issues with my tests and have identified spell-spec as an unexpected culprit. The issue is definitely noticeable when generating examples with spec.alpha/merge, but I have not investigated the root cause.

Test case:

(tufte/add-basic-println-handler! {})

(s/def ::foo pos-int?)
(s/def ::bar neg-int?)
(s/def ::baz string?)
(s/def ::qux keyword?)

(deftest speed-difference-test
  (let [spec1 (s/merge (s/keys :req [::foo])
                       (s/keys :req [::bar])
                       (s/keys :req [::baz])
                       (s/keys :req [::qux]))
        spec2 (s/merge (spell-spec/keys :req [::foo])
                       (spell-spec/keys :req [::bar])
                       (spell-spec/keys :req [::baz])
                       (spell-spec/keys :req [::qux]))]
    (tufte/profile
     {}
     (tufte/p :spec (doall (take 100 (gen/sample-seq (s/gen (s/spec spec1))))))
     (tufte/p :spell (doall (take 100 (gen/sample-seq (s/gen (s/spec spec2)))))))))

Result:

      pId     nCalls        Min      50% ≤      90% ≤      95% ≤      99% ≤        Max       Mean   MAD       Total   Clock

   :spell          1   909.46ms   909.46ms   909.46ms   909.46ms   909.46ms   909.46ms   909.46ms   ±0%    909.46ms     97%
    :spec          1    27.39ms    27.39ms    27.39ms    27.39ms    27.39ms    27.39ms    27.39ms   ±0%     27.39ms      3%

Tested with:

[com.bhauman/spell-spec        "0.1.1"]
[org.clojure/spec.alpha        "0.1.143"]
[org.clojure/clojure           "1.9.0"]