Skip to:

  1. Skip to Jira Navigation
  2. Skip to Side Navigation
  3. Skip to Main Content

Have Range implement IChunkedSeq

Description

When Clojure's range was converted from a lazy seq to a LongRange in CLJ-1515, LongRange was made to implement IChunkedSeq. It seems that this could also be applicable in ClojureScript, with superficial evidence being that by taking this form

(apply + (filter even? (map inc (range 1e6))))

and simply adding a call to vec

(apply + (filter even? (map inc (vec (range 1e6)))))

dramatically speeds it up. Benchmarks are included below.

Note that Alex Miller recalls that the change in Clojure was rather challenging, with difficulty:
"balancing the perf concerns of reducible, sequence, and chunked sequence traversal (all of which are possible and may even interleave) while also avoiding potential overflow/underflow cases was a surprisingly narrow path"

Benchmarking with V8 [x (range 100000)], (apply + (filter even? (map inc x))), 10 runs, 1014 msecs Benchmarking with SpiderMonkey [x (range 100000)], (apply + (filter even? (map inc x))), 10 runs, 849 msecs Benchmarking with JavaScriptCore [x (range 100000)], (apply + (filter even? (map inc x))), 10 runs, 423 msecs Benchmarking with Nashorn [x (range 100000)], (apply + (filter even? (map inc x))), 10 runs, 2386 msecs Benchmarking with ChakraCore [x (range 100000)], (apply + (filter even? (map inc x))), 10 runs, 1798 msecs
Benchmarking with V8 [x (vec (range 100000))], (apply + (filter even? (map inc x))), 10 runs, 280 msecs Benchmarking with SpiderMonkey [x (vec (range 100000))], (apply + (filter even? (map inc x))), 10 runs, 201 msecs Benchmarking with JavaScriptCore [x (vec (range 100000))], (apply + (filter even? (map inc x))), 10 runs, 230 msecs Benchmarking with Nashorn [x (vec (range 100000))], (apply + (filter even? (map inc x))), 10 runs, 2954 msecs Benchmarking with ChakraCore [x (vec (range 100000))], (apply + (filter even? (map inc x))), 10 runs, 427 msecs

Environment

None

Attachments

2
  • 01 Jul 2018, 07:51 PM
  • 23 Mar 2018, 01:19 AM

Activity

Mike Fikes 
November 28, 2018 at 1:32 PM

Mike Fikes 
November 28, 2018 at 5:11 AM

CLJS-2693.patch passes CI and Canary

Mike Fikes 
July 1, 2018 at 7:51 PM

The attached
CLJS-2693.patch patch depends on the patches in CLJS-2798 and CLJS-2799 having been applied.

Here are the performance speedups across the 3 major engines, covering the same metrics given in https://clojure.atlassian.net/browse/CLJ-1515#icft=CLJ-1515 (minus the ones depending on ratio support):

Code

V8 Speedup

SpiderMonkey

JavaScriptCore

(count (range (* 1024 1024)))

5.28

8.58

7.43

(reduce + (map inc (range (* 1024 1024))))

4.04

6.41

2.02

(reduce + (map inc (map inc (range (* 1024 1024)))))

5.80

7.53

2.57

(count (keep odd? (range (* 1024 1024))))

4.77

4.39

1.43

(transduce (comp (map inc) (map inc)) + (range (* 1024 1024)))

1.01

1.00

1.00

(reduce + 0 (range (* 2048 1024)))

1.01

1.00

1.00

(reduce + 0 (rest (range (* 2048 1024))))

1.01

1.00

0.99

(doall (range 0 31))

0.60

0.98

0.81

(doall (range 0 32))

0.60

0.94

0.87

(doall (range 0 4096))

0.59

0.88

0.82

(into [] (map inc (range 31)))

1.91

1.58

1.30

(into [] (map inc) (range 31))

0.86

1.00

1.12

(into [] (range 128))

0.93

1.04

1.02

(doall (range 0.5 1000 0.33))

1.27

0.97

0.80

(into [] (range 0.5 1000 0.33))

1.13

1.02

0.98

(count (filter odd? (take (* 1024 1024) (range))))

1.00

1.15

0.52

(transduce (take (* 1024 1024)) + (range))

1.05

1.06

0.95

Mike Fikes 
June 15, 2018 at 10:42 PM

Yes, work towards taking the spike idea and creating a production-quality change has been in progress over here https://github.com/mfikes/clojurescript/commits/CLJS-2693

David Nolen 
June 15, 2018 at 10:32 PM

Nice! Seems like it just needs a bit more work?

Completed

Details

Assignee

Reporter

Approval

Patch

Priority

Created March 22, 2018 at 10:05 PM
Updated November 28, 2018 at 1:32 PM
Resolved November 28, 2018 at 1:32 PM