<< Back to previous view

[CLJS-2472] ES6 Iterators should use IIterable if possible Created: 15/Jan/18  Updated: 15/Jan/18

Status: Open
Project: ClojureScript
Component/s: None
Affects Version/s: 1.9.908
Fix Version/s: None

Type: Enhancement Priority: Minor
Reporter: A. R Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: performance


 Description   

Motivation:

ES6 Iterables: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols

Use in React: https://github.com/facebook/react/blob/30dac4e78de02fb427ee82013160ae875128d7a2/packages/react/src/ReactElementValidator.js#L195-L204

(defn es6-iterator**
  [coll]
  (if (implements? IIterable coll)
    (let [it (-iterator ^not-native coll)]
      #js{:next (fn []
                  (if ^boolean (.hasNext it)
                    #js{:value (.next it), :done false}
                    #js{:value nil, :done true}))})
    ;; Fallback to naive first/next iterator:
    (ES6Iterator. (seq coll))))

;; Tests can use round trip:
(es6-iterator-seq (es6-iterator (hash-map 0 1 2 3)))

(defn es6-iter-consume
  [it]
  (while (not (.-done (.next it)))))

(dotimes [_ 3]
  (let [xs (vec (range 3000))
        runs 1000]
    (simple-benchmark []
      (es6-iter-consume (es6-iterator xs)) runs)
    (simple-benchmark []
      (es6-iter-consume (es6-iterator** xs)) runs)))

About a 4x speedup in Chrome. Also note that much less garbage is produced.






[CLJS-2471] ChunkedSeq should implemented ICounted Created: 15/Jan/18  Updated: 15/Jan/18

Status: Open
Project: ClojureScript
Component/s: None
Affects Version/s: 1.9.908
Fix Version/s: None

Type: Enhancement Priority: Minor
Reporter: A. R Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: None


 Description   

ChunkedSeq in clojure implements Counted, should do the same in CLJS. Implementation is straight forward.






[CLJS-2470] ArrayChunk.reduce doesn't honor end param Created: 15/Jan/18  Updated: 15/Jan/18

Status: Open
Project: ClojureScript
Component/s: None
Affects Version/s: 1.9.908
Fix Version/s: None

Type: Defect Priority: Minor
Reporter: A. R Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: None


 Description   

Ex:

(reduce max (array-chunk #js[0 1 2 3] 0 1))
;; => 3

Currently not an issue since end is always arr.length for our usage of ArrayChunk, but since it's a public API users might pass a different end param.

This can easily be fixed after CLJS-2466 which properly implements the reduce for ArrayChunk.






[CLJS-2469] ChunkedCons chunk-next returns empty seq instead of nil Created: 13/Jan/18  Updated: 13/Jan/18

Status: Open
Project: ClojureScript
Component/s: None
Affects Version/s: 1.9.908
Fix Version/s: None

Type: Defect Priority: Minor
Reporter: A. R Assignee: David Nolen
Resolution: Unresolved Votes: 0
Labels: None

Attachments: Text File CLJS-2469.patch    

 Description   

There is a bug in ChunkedCons. In Clojure ChunkedCons (correctly) always calls seq in chunked-next. In CLJS it's not done. But since ChunkedCons has to be lazy it pretty much always gets an (empty) lazy seq as the "more" part.

Bug:

(-> (map inc (vec (range 64)))
    seq
    chunk-next
    seq
    chunk-next)

Returns and empty sequence instead of nil. This hasn't surfaced yet since nothing calls chunk-next on a ChunkedCons (yet).



 Comments   
Comment by A. R [ 13/Jan/18 7:26 AM ]

Found another bug that surfaced: Current implementation calls -seq on more which could be nil and this would blow up. So the patch also make a tiny change to -next also just calling seq on more. Pretty straight forward.





[CLJS-2468] Implement reduce for ChunkedCons Created: 12/Jan/18  Updated: 12/Jan/18

Status: Open
Project: ClojureScript
Component/s: None
Affects Version/s: 1.9.908
Fix Version/s: None

Type: Enhancement Priority: Minor
Reporter: A. R Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: None


 Description   

Forked from CLJS-2466

Title says it all.






[CLJS-2467] Small PVs are never chunked Created: 12/Jan/18  Updated: 13/Jan/18

Status: Open
Project: ClojureScript
Component/s: None
Affects Version/s: 1.9.908
Fix Version/s: None

Type: Enhancement Priority: Minor
Reporter: A. R Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: performance

Attachments: Text File CLJS-2467.patch    

 Description   

A PersistenVector that has <=32 elements and is seq'ed will return an IndexedSeq. Though IndexedSeq always fails the chunked-seq? check.

This means a:

(def xv (vec (range 32)))
(reduce + (map inc xv))

is about 4x slower than a map over a vector with 33 elements.

Options:
1. Return a ChunkedCons with the "rest" set to nil in PersistentVector.seq()
2. Implement IChunkedSeq for IndexedSeq:

(extend-type IndexedSeq
    IChunkedSeq
    (-chunked-first [x] x)
    (-chunked-rest [x] ())
    IChunkedNext
    (-chunked-next [x] nil)
    IChunk
    (-drop-first [coll]
      (if-some [n (-next coll)]
        n
        (throw (js/Error. "-drop-first of empty chunk")))))

I think option #2 is better since IndexedSeq is used quite a bunch throughout the code base, so the chunking will also kick in for many other code paths.



 Comments   
Comment by A. R [ 12/Jan/18 10:20 AM ]

Note:

This is different from Clojure (which does not consider an IndexedSeq a ChunkedSeq) since we use IndexedSeq a lot more where Clojure often uses a ChunkedSeq. For instance:

(apply (fn [& a] (type a)) [1 2 3 4 8])

will return IndexedSeq in CLJS but ChunkedCons in CLJ.

Since these IndexedSeq's will be passed around wildly in a normal CLJS app it makes sense to extend them as a IChunkedSeq since otherwise all these will never be chunked and get a slow first/next treatment.





[CLJS-2466] Faster reduce for lazy-seqs Created: 12/Jan/18  Updated: 13/Jan/18

Status: Open
Project: ClojureScript
Component/s: None
Affects Version/s: 1.9.908
Fix Version/s: None

Type: Enhancement Priority: Minor
Reporter: A. R Assignee: David Nolen
Resolution: Unresolved Votes: 1
Labels: None

Attachments: Text File CLJS-2466.patch    

 Description   

Lazy seqs that are built from vectors/chunked-seqs can sometimes take a slow first/next reduce.

Observation:

(def xs (vec (range 3000000)))

(time (reduce max xs)) ;; #1: 130ms, (reference)
(time (reduce max (lazy-cat xs))) ;; #2: 130ms, just as fast
(time (reduce max 0 (lazy-cat xs))) ;; #3: 500ms, 4x slower!!

;; Double them with concat and they're not 2x slower but 10x slower:
(time (reduce max (lazy-cat xs xs))) ;; #4: 1200ms
(time (reduce max 0 (lazy-cat xs xs))) ;; #5: 1200ms

Explanation for #3: The problem is that seq-reduce when called without init will properly call reduce again and take a fast path. With init given it won't ever escape to a faster reduce but will stick to first/next.

Note: In Clojure they scale "properly" (first 3 are ~45ms, last 2 are ~110ms).

The reason is that Clojure properly escapes to a fast path:

https://github.com/clojure/clojure/blob/2b242f943b9a74e753b7ee1b951a8699966ea560/src/clj/clojure/core/protocols.clj#L131-L143

An improved seq-reduce could look like this:

(defn seq-reduce
  ([f coll]
   (if-let [s (seq coll)]
     (reduce f (first s) (next s))
     (f)))
  ([f val coll]
   (loop [val val, coll (seq coll)]
     (if coll
       (if (chunked-seq? coll)
         (if (implements? IReduce coll)
           (reduce f val coll)
           (let [nval (reduce f val (chunk-first coll))]
             (if (reduced? nval)
               @nval
               (recur nval (chunk-next coll)))))
         (let [nval (f val (first coll))]
           (if (reduced? nval)
             @nval
             (recur nval (next coll)))))
       val))))

This reduces the times for #3: 160ms, #4: 380ms, #5: 380ms.

This is an RFC, since I'm not 100% certain about the implemenation. Need to be careful to not blow the stack here...

Questions:
1. Should ChunkedCons implement IReduce? I think so.



 Comments   
Comment by A. R [ 12/Jan/18 1:59 AM ]

Timings with advanced compilation:

CHROME:
"OLD"
#1: "Elapsed time: 21.870000 msecs"
#2: "Elapsed time: 25.485000 msecs"
#3: "Elapsed time: 134.900000 msecs"
#4: "Elapsed time: 317.155000 msecs"
#5: "Elapsed time: 313.225000 msecs"
"NEW"
#1: "Elapsed time: 23.290000 msecs"
#2: "Elapsed time: 19.445000 msecs"
#3: "Elapsed time: 20.075000 msecs"
#4: "Elapsed time: 102.895000 msecs"
#5: "Elapsed time: 100.430000 msecs"
"OLD"
#1: "Elapsed time: 19.585000 msecs"
#2: "Elapsed time: 19.475000 msecs"
#3: "Elapsed time: 87.805000 msecs"
#4: "Elapsed time: 303.340000 msecs"
#5: "Elapsed time: 291.680000 msecs"
"NEW"
#1: "Elapsed time: 20.760000 msecs"
#2: "Elapsed time: 19.690000 msecs"
#3: "Elapsed time: 18.960000 msecs"
#4: "Elapsed time: 101.385000 msecs"
#5: "Elapsed time: 101.290000 msecs"

FIREFOX:

"OLD"
#1: "Elapsed time: 7.880000 msecs"
#2: "Elapsed time: 7.820000 msecs"
#3: "Elapsed time: 69.460000 msecs"
#4: "Elapsed time: 197.800000 msecs"
#5: "Elapsed time: 209.300000 msecs"
"NEW"
#1: "Elapsed time: 7.380000 msecs"
#2: "Elapsed time: 7.360000 msecs"
#3: "Elapsed time: 8.100000 msecs"
#4: "Elapsed time: 110.640000 msecs"
#5: "Elapsed time: 89.960000 msecs"
"OLD"
#1: "Elapsed time: 6.520000 msecs"
#2: "Elapsed time: 7.360000 msecs"
#3: "Elapsed time: 106.920000 msecs"
#4: "Elapsed time: 252.300000 msecs"
#5: "Elapsed time: 249.800000 msecs"
"NEW"
#1: "Elapsed time: 7.360000 msecs"
#2: "Elapsed time: 6.940000 msecs"
#3: "Elapsed time: 6.880000 msecs"
#4: "Elapsed time: 99.380000 msecs"
#5: "Elapsed time: 53.220000 msecs"
Comment by A. R [ 12/Jan/18 2:14 AM ]

Impact on truly (unchunked) lazy-seqs is neglibile (hard to measure due to garbage collection causing a lot of variance).

Comment by A. R [ 12/Jan/18 10:22 AM ]

New ticket for reduce for ChunkedCons: CLJS-2468

Comment by A. R [ 13/Jan/18 7:00 AM ]

Depends on CLJS-2469 for tests to pass. Patch is attached.





[CLJS-2465] Using var-args as arguments name in variadic function overrides first argument Created: 11/Jan/18  Updated: 11/Jan/18

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

Type: Defect Priority: Minor
Reporter: A. R Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: None


 Description   

The following returns (nil "b"):

((fn [& var-args]
   var-args) "a" "b")

var-args should to be shadowed by default.






[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.





[CLJS-2463] js calls are mistakenly treated as higher order invokes Created: 10/Jan/18  Updated: 10/Jan/18

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

Type: Defect Priority: Minor
Reporter: A. R Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: None


 Description   

Code that invokes js/ a lot (like Sablono) will currently treat the JS invokes as higher order invokes and bind all arguments in a let beforehand. This generates a ton of IIFEs which are all unnecessary.

Fix:

HO-invoke? (and (boolean *cljs-static-fns*)
                        (not fn-var?)
                        (not (js-tag? f))
                        (not kw?)
                        (not (analyzed? f)))


 Comments   
Comment by A. R [ 10/Jan/18 2:11 PM ]

Actually this has a much larger scope. Currently also Math,goog (and more?) are treated like HO invokes. This also affects compile time when using these a lot since it generates a lot of new {{let}}s. Will probably also be affected by JS modules? So we should do a more careful check here to avoid this.

Comment by A. R [ 10/Jan/18 2:45 PM ]

Another one: all-values predicate should also include keyword? check, no reason to bind the argument when passing keywords.

To illustrate what the current code gen looks like:

(defn foooooooo
  [x y]
  (x :fooo :bar)
  (goog/mixin (js/fooo x) (js/bar y))
  (Math/floor (js/fooo x) (js/fooo x))
  (goog.mixin (js/fooo x) (js/fooo x)))

Generated:

foooooooo = (function (x,y){

var G__21625_21633 = cljs.core.cst$kw$fooo;
var G__21626_21634 = cljs.core.cst$kw$bar;
(x.cljs$core$IFn$_invoke$arity$2 ? x.cljs$core$IFn$_invoke$arity$2(G__21625_21633,G__21626_21634) : x(G__21625_21633,G__21626_21634));

var G__21627_21635 = fooo(x);
var G__21628_21636 = bar(y);
goog.mixin(G__21627_21635,G__21628_21636);

var G__21629_21637 = fooo(x);
var G__21630_21638 = fooo(x);
Math.floor(G__21629_21637,G__21630_21638);

var G__21631 = fooo(x);
var G__21632 = fooo(x);
return goog.mixin(G__21631,G__21632);

});

All of them don't need to bind the passed arguments.

Obviously in this simple case GCC will just inline everything and the cost is 0. But if any of these calls happen inside a function, like {{let [x (the-call...] ...}} then an IIFE is created that isn't broken up by GCC.





Generated at Tue Jan 16 19:43:36 CST 2018 using JIRA 4.4#649-r158309.