Affects Version/s: Release 1.7
Fix Version/s: Release 1.7
Patch:Code and Test
Currently range returns a lazy chunked seq. If the return value of range were reified into a type we could optimize common cases and add IReduce support.
Approach: this patch revives the unused (but previously existing) clojure.lang.Range class. This class acts as a lazy seq and implements several other appropriate interfaces such as Counted and Indexed. This type is implemented in Java since range is needed fairly on in core.clj before deftype is defined. The attached patch provides two Range impls sharing some common code in AbstractRange. Range uses Numbers.* methods for all math due to the input types to range being unknown. LongRange handles the specific (but very common) case of a long start/end/step for higher performance. The special case of (range) is just handled with (iterate inc' 0) (which is further optimized for reduce in CLJ-1603).
Note: The patch also includes a tiny tweak in filter that has nothing to do with this patch other than being found while testing. It is a perf boost for all filter operations by avoiding calling .nth twice for every element in every chunk. Notice the filter seq example below gets an extra improvement in perf. If desired, this change could be split out.
timings done via criterium quick-bench
|(count (filter odd? (take (* 1024 1024) (range))))||183 ms||173 ms||170 ms|
|(transduce (take (* 1024 1024)) + (range))||n/a||67 ms||81 ms (w/CLJ-1603: 41 ms)|
|(count (range (* 1024 1024)))||75 ms||69 ms||0 ms|
|(reduce + (map inc (range (* 1024 1024))))||71 ms||68 ms||46 ms|
|(reduce + (map inc (map inc (range (* 1024 1024)))))||89 ms||91 ms||69 ms|
|(count (filter odd? (range (* 1024 1024))))||69 ms||65 ms||43 ms|
|(transduce (comp (map inc) (map inc)) + (range (* 1024 1024)))||n/a||67 ms||36 ms|
|(doall (range 0 31))||1.41 µs||1.51 µs||3.02 µs|
|(into  (map inc (range 31)))||1.76 µs||1.77 µs||1.43 µs|
|(into  (map inc) (range 31))||n/a||1.60 µs||0.63 µs|
|(doall (range 1/2 1000 1/3))||1.58 ms||1.53 ms||1.66 ms|
|(into  (range 1/2 1000 1/3))||1.52 ms||1.51 ms||1.38 ms|
|(doall (range 0.5 1000 0.33))||0.15 ms||0.14 ms||0.35 ms|
|(into  (range 0.5 1000 0.33))||0.13 ms||0.12 ms||0.08 ms|
These results are a bit mixed but in general I think they make the most common and important things faster while some less important things are slightly slower. In general the "doall" examples are slower as this is kind of the worst case wrt overhead and values are retrieved via seq/next looping (the slowest option). Stacked sequence ops happen via the the chunked seq impl (which is a little faster), and the transduce/into will use the reduce impl (which is much faster).
Screener question: (range) and range on non-longs both support 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.