Clojure

cycle, iterate, repeat return vals should IReduceInit

Details

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

Description

Screened

clj-1603-15.patch (Java approach)

Alternatives:

There were a number of possible approaches for these enhancements:
1) Straight Java impl. The benefit of this approach is improving the performance of both the seq and reduce paths at the expense of writing a bunch of Java. See clj-1603-15.patch for the best of these impls.

2) Clojure deftype. This required moving cycle and iterate and providing a repeat1 implementation until deftype is defined (similar to the approach with reduce1). The deftype version returns a Seqable, IReduce object and has effectively the same former implementation for seq with a new fast implementation for IReduce. This makes reduce paths fast, but leaves seq paths about the same, with the benefit of no new Java code. The downside was that the new seqs did not implement the full range of interfaces from prior impls, which could potentially break code. See clj-1603-12-2.patch for a patch that covers this.

3) Add Iterable or IReduceInit directly to LazySeq. Conceptually, this does not make sense for general lazy seqs. Seqs materialize and cache each value once and doing this along with the ability to iterate/reduce introduces issues with caching (might as well use seqs for that) and synchronization. However, doing this for just these specific lazy seqs is possible - see latest patch.

Approach: Latest patch makes LazySeq implement IReduce and internal macro reducible-lazy-seq lets callers supply a function to implement the reduce path.

A few things to note:

  • Added some example-based tests for iterate, cycle, and repeat where I thought they were needed. Did not add generative tests - not clear to me what these would be that would actually be valuable. All of these functions are pretty simple and the examples cover the special cases.

Performance:

Some example timing, all in ┬Ás:

Expression 1.6.0 1.7.0-alpha5 master + clj-1603-15 (Java) master + clj-1603-12-2 (deftype) master + clj-1603-14 (split)
(doall (take 1000 (repeat 1))) 87 93 63 89 92
(into [] (take 1000) (repeat 1)) n/a 67 25 27 33
(doall (repeat 1000 1)) 87 94 16 94 89
(into [] (repeat 1000 1)) 99 110 13 12 12
(reduce + 0 (repeat 1000 1)) 99 126 20 22 25
(into [] (take 1000) (repeat 1)) n/a 67 28 33 27
(doall (take 1000 (cycle [1 2 3]))) 101 106 85 108 103
(into [] (take 1000) (cycle [1 2 3])) n/a 73 38 45 44
(doall (take 1000 (iterate inc 0))) 93 98 75 123 116
(into [] (take 1000) (iterate inc 0)) n/a 85 38 40 39

Notes on timings above:

  • All reduce timings (with into) comparable across the impls and significantly better than the current behavior over seqs.
  • The Java impl is faster across the board with doall. doall repeatedly calls seq() and next() to walk the sequence. The Java class versions of Repeat, Cycle, and Iterate extend ASeq and seq() just return this. next() constructs and returns a new instance of the class, which is immutable. In the lazy seq versions, LazySeq is mutable and requires synchronization and handling the caching safely. So, simple immutable instance ftw here.
  • The Java finite repeat has an extra benefit from using a primitive long for the counter.
  • One performance difference that's not visible in the timings is that the Java implementations have the benefit of being both seqs and reducibles as they are traversed, so you can always get a fast reduce. The deftype and split impls are only reducible at the initial instance, walking off that initial head reverts to lazy seqs that are not quickly reducible.

Patch: The two patches in leading contention are:

  • clj-1603-15.patch - for the Java version
  • clj-1603-14.patch - for the split impl

Alex opinion: I have swung back and forth on this but my current recommendation is for the Java implementation (clj-1603-15.patch). It's faster for both seqs and reduce, both in the timings above and importantly in maintaining reducibility as they are traversed. There is more Java, but I've made my peace with that - the code maximally leverages existing ASeq infrastructure and the implementation is easy to understand.

  1. clj-1603.patch
    05/Dec/14 11:17 PM
    9 kB
    Alex Miller
  2. clj-1603-10.patch
    26/Jan/15 3:27 PM
    10 kB
    Alex Miller
  3. clj-1603-11.patch
    20/Feb/15 11:03 AM
    10 kB
    Alex Miller
  4. clj-1603-12.patch
    24/Feb/15 11:23 AM
    12 kB
    Alex Miller
  5. clj-1603-12-2.patch
    17/Mar/15 4:23 PM
    12 kB
    Alex Miller
  6. clj-1603-13.patch
    02/Mar/15 10:21 AM
    12 kB
    Alex Miller
  7. clj-1603-14.patch
    02/Mar/15 4:04 PM
    11 kB
    Alex Miller
  8. clj-1603-15.patch
    25/Mar/15 4:14 PM
    12 kB
    Alex Miller
  9. clj-1603-2.patch
    06/Dec/14 12:15 AM
    10 kB
    Alex Miller
  10. clj-1603-3.patch
    02/Jan/15 4:21 PM
    10 kB
    Alex Miller
  11. clj-1603-3-2.patch
    17/Mar/15 4:23 PM
    10 kB
    Alex Miller
  12. clj-1603-3-3.patch
    18/Mar/15 10:13 AM
    12 kB
    Alex Miller
  13. clj-1603-3-4.patch
    23/Mar/15 2:26 PM
    12 kB
    Nicola Mometto
  14. clj-1603-4.patch
    15/Jan/15 12:01 PM
    9 kB
    Alex Miller
  15. clj-1603-5.patch
    16/Jan/15 1:34 PM
    9 kB
    Alex Miller
  16. clj-1603-6.patch
    18/Jan/15 1:52 PM
    9 kB
    Michael Blume
  17. clj-1603-7.patch
    19/Jan/15 10:12 AM
    10 kB
    Alex Miller
  18. clj-1603-8.patch
    22/Jan/15 10:33 PM
    9 kB
    Alex Miller
  19. clj-1603-9.patch
    23/Jan/15 3:04 PM
    10 kB
    Alex Miller

Activity

People

Vote (0)
Watch (3)

Dates

  • Created:
    Updated:
    Resolved: