<< Back to previous view

[CLJS-2464] Directly reducible tree-seq Created: 10/Jan/18  Updated: 10/Jan/18  Resolved: 10/Jan/18

Status: Closed
Project: ClojureScript
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Enhancement Priority: Major
Reporter: Mike Fikes Assignee: Mike Fikes
Resolution: Declined Votes: 0
Labels: None

Attachments: Text File CLJS-2464-1.patch    

 Description   

Introduce a directly reducible tree-seq implementation.

In a sense, tree-seq is akin to iterate in that both are sequence generator functions which accept higher order functions that are used to generate the sequence: While iterate takes a single function that operates on the previous value to produce the subsequent value, tree-seq takes two functions, and has some interesting recursive nature that makes it differ from iterate. Additionally, tree-seq can produce infinite as well as finite sequences, while iterate can only produce infinite sequences. Regardless, tree-seq is amenable to similar optimizations that were done in CLJS-2445 for iterate.

This high-level sketch shows how a directly-reducible tree-seq can be built upon the existing directly-reducible iterate. While this code has great perf characteristics, it lacks IPending support, but that can be addressed via a production patch that adds a new TreeSeq deftype.

(defn tree-seq
  [branch? children root]
    (eduction (take-while some?) (map first)
      (iterate (fn [[node pair]]
                 (when-some [[[node' & r] cont] (if (branch? node)
                                                  (if-some [cs (not-empty (children node))]
                                                    [cs pair]
                                                    pair)
                                                  pair)]
                   (if (some? r)
                     [node' [r cont]]
                     [node' cont])))
        [root nil])))


 Comments   
Comment by Mike Fikes [ 10/Jan/18 11:18 AM ]

Attaching CLJS-2464-1.patch for feedback. I'd still like to flesh out the functional tests, and perhaps add more perf tests, especially perf tests that don't exercise the "directly reducible" aspect, in order to ensure no perf regressions.

Here are the results for the two benchmarks that are included:

Speedup summaries:

            V8: 4.4, 9.9
  SpiderMonkey: 2.3, 9.5
JavaScriptCore: 2.8, 6.0

Before:

Benchmarking with V8
[], (into [] (tree-seq seq? identity (quote ((1 2 (3)) (4))))), 1000000 runs, 14381 msecs
[], (nth' (tree-seq seq? identity (repeat 10 (repeat 100 [1 2 (repeat 100 3)]))) 1000), 10000 runs, 17217 msecs
Benchmarking with SpiderMonkey
[], (into [] (tree-seq seq? identity (quote ((1 2 (3)) (4))))), 1000000 runs, 16855 msecs
[], (nth' (tree-seq seq? identity (repeat 10 (repeat 100 [1 2 (repeat 100 3)]))) 1000), 10000 runs, 13921 msecs
Benchmarking with JavaScriptCore
[], (into [] (tree-seq seq? identity (quote ((1 2 (3)) (4))))), 1000000 runs, 11075 msecs
[], (nth' (tree-seq seq? identity (repeat 10 (repeat 100 [1 2 (repeat 100 3)]))) 1000), 10000 runs, 9598 msecs

tree-seq branch

Benchmarking with V8
[], (into [] (tree-seq seq? identity (quote ((1 2 (3)) (4))))), 1000000 runs, 3293 msecs
[], (nth' (tree-seq seq? identity (repeat 10 (repeat 100 [1 2 (repeat 100 3)]))) 1000), 10000 runs, 1742 msecs
Benchmarking with SpiderMonkey
[], (into [] (tree-seq seq? identity (quote ((1 2 (3)) (4))))), 1000000 runs, 7308 msecs
[], (nth' (tree-seq seq? identity (repeat 10 (repeat 100 [1 2 (repeat 100 3)]))) 1000), 10000 runs, 1469 msecs
Benchmarking with JavaScriptCore
[], (into [] (tree-seq seq? identity (quote ((1 2 (3)) (4))))), 1000000 runs, 3928 msecs
[], (nth' (tree-seq seq? identity (repeat 10 (repeat 100 [1 2 (repeat 100 3)]))) 1000), 10000 runs, 1610 msecs
Comment by Mike Fikes [ 10/Jan/18 11:48 AM ]

We can't pursue this because the functions passed to tree-seq are not constrained to be side-effect free. In other words, tree-seq is akin to repeatedly and not akin to iterate. The fundamental problem is that you could reduce across a tree-seq and have it change things (via side effects) followed by simply mapping across the tree-seq (realizing it) and get different results. In other words, the fact that branch? and children could have side effects would mean that the suggested patch would cause tree-seq to fail to produce an immutable sequence.





Generated at Tue Jan 16 08:03:48 CST 2018 using JIRA 4.4#649-r158309.