Clojure

range should return something that implements IReduce

Details

  • Type: Enhancement Enhancement
  • Status: Closed Closed
  • Priority: Major Major
  • Resolution: Completed
  • Affects Version/s: Release 1.7
  • Fix Version/s: Release 1.7
  • Component/s: None
  • Labels:
    None
  • Patch:
    Code and Test
  • Approval:
    Ok

Description

range should implement IReduce for fast reduction.

Patch: clj-1515-14.patch - Java range with long optimizations

Approach: The clj-1515-14 patch revives the unused clojure.lang.Range class. This class is similar in implementation to ChunkedCons. It differs by lazily constructing the first chunk (this is done in the existing impl by using a LazySeq wrapper) and by caching the next reference like other seq impls. The latter is done because range is frequently used in both chunked and unchunked traversal.

Additionally, 1515-14 contains an optimized version of range (LongRange) for the extremely common case where start, end, and step are all longs. This version uses primitive longs and primitive math and a customized version of ArrayChunk for greater performance.

The special case of (range) is just handled with (iterate inc' 0) (which was further optimized for reduce in CLJ-1603).

Alternatives:

  • CLJ-1515-deftype3.patch took the approach of using deftype to create a seqable, reducible entity that was not actually a seq. Based on work for CLJ-1603, it was established that due to historical requirements, this is not viable and the entity returned for range should implement the ISeq and Collection interfaces directly.
  • clj-1515-11.patch uses the approach of a "split" implementation - a LazySeq that has a fast reduce path. This is a minimal patch that provides no perf difference for sequence usage but a moderate improvement for reduce paths. One important difference vs clj-1515-12 is that the fast reduce path is only obtained on the initial range. Once you walk off the head, the performance will be the same as prior (seq perf).

Performance

criterium quick-bench with java 1.8.0-b132

code 1.7.0-master Java clj-1515-14 split clj-1515-11
(count (range (* 1024 1024))) 63 ms 0 ms 58 ms
(reduce + (map inc (range (* 1024 1024)))) 50 ms 33 ms 50 ms
(reduce + (map inc (map inc (range (* 1024 1024))))) 68 ms 52 ms 67 ms
(count (keep odd? (range (* 1024 1024)))) 73 ms 52 ms 67 ms
(transduce (comp (map inc) (map inc)) + (range (* 1024 1024))) 46 ms 26 ms 34 ms
(reduce + 0 (range (* 2048 1024))) 67 ms 19 ms 40 ms
(reduce + 0 (rest (range (* 2048 1024)))) 67 ms 19 ms 57 ms
(doall (range 0 31)) 1.04 µs 0.75 µs 1.15 µs
(doall (range 0 32)) 1.08 µs 0.76 µs 1.18 µs
(doall (range 0 4096)) 135 µs 96 µs 145 µs
(into [] (map inc (range 31))) 1.81 µs 1.30 µs 1.88 µs
(into [] (map inc) (range 31)) 1.71 µs 0.75 µs 1.02 µs
(into [] (range 128)) 4.82 µs 2.20 µs 3.27 µs
(doall (range 1/2 1000 1/3)) 1.24 ms 1.24 ms 1.28 µs
(doall (range 0.5 1000 0.33)) 126 µs 147 µs 151 µs
(into [] (range 1/2 1000 1/3)) 1.26 ms 1.20 ms 1.26 ms
(into [] (range 0.5 1000 0.33)) 148 µs 91 µs 130 µs
(count (filter odd? (take (* 1024 1024) (range)))) 185 ms 167 ms 176 ms
(transduce (take (* 1024 1024)) + (range)) 67 ms 35 ms 68 ms

Performance notes:

  • 1515-14 (Java) - significant improvements in virtually all use cases, both seq and reduce. The final two cases with (range) leverage optimizations from CLJ-1603.
  • 1515-11 (split) - a much smaller patch that gives no seq benefits and smaller reduction benefits. Only the head of the range will receive the perf benefits (see (reduce + 0 (rest (range (* 2048 1024))))).

Questions
(range) and supports auto-promotion towards infinity in this patch, which seems to be implied by the doc string but was not actually implemented or tested correctly afaict.

  1. clj-1515.patch
    09/Dec/14 2:40 AM
    23 kB
    Alex Miller
  2. clj-1515-10.patch
    02/Jan/15 11:24 AM
    21 kB
    Alex Miller
  3. clj-1515-11.patch
    25/Mar/15 12:44 PM
    6 kB
    Alex Miller
  4. clj-1515-12.patch
    25/Mar/15 12:44 PM
    18 kB
    Alex Miller
  5. clj-1515-13.patch
    27/Mar/15 3:44 PM
    18 kB
    Alex Miller
  6. clj-1515-14.patch
    03/Apr/15 10:28 AM
    18 kB
    Alex Miller
  7. clj-1515-2.patch
    10/Dec/14 5:12 PM
    23 kB
    Alex Miller
  8. clj-1515-3.patch
    10/Dec/14 11:34 PM
    22 kB
    Alex Miller
  9. clj-1515-4.patch
    11/Dec/14 12:11 AM
    22 kB
    Alex Miller
  10. clj-1515-5.patch
    11/Dec/14 10:20 AM
    22 kB
    Alex Miller
  11. clj-1515-6.patch
    11/Dec/14 11:31 AM
    22 kB
    Alex Miller
  12. clj-1515-7.patch
    11/Dec/14 11:49 AM
    22 kB
    Alex Miller
  13. clj-1515-8.patch
    11/Dec/14 3:49 PM
    23 kB
    Alex Miller
  14. clj-1515-9.patch
    12/Dec/14 2:11 PM
    22 kB
    Alex Miller
  15. CLJ-1515-deftype.patch
    18/Jan/15 8:27 PM
    13 kB
    Ghadi Shayban
  16. CLJ-1515-deftype2.patch
    22/Jan/15 9:35 AM
    12 kB
    Ghadi Shayban
  17. CLJ-1515-deftype3.patch
    23/Jan/15 3:20 PM
    12 kB
    Ghadi Shayban
  18. CLJ-1515-deftype-nostructural-dup.patch
    18/Jan/15 11:05 PM
    12 kB
    Ghadi Shayban
  19. patch.diff
    29/Aug/14 3:34 PM
    9 kB
    Timothy Baldridge
  20. range-patch3.diff
    19/Sep/14 10:02 AM
    11 kB
    Timothy Baldridge
  21. reified-range4.diff
    31/Oct/14 11:30 AM
    16 kB
    Timothy Baldridge

Activity

People

Vote (2)
Watch (5)

Dates

  • Created:
    Updated:
    Resolved: