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

Stuart Halloway made changes -
Field Original Value New Value
Assignee Alex Miller [ alexmiller ]
Approval Vetted [ 10003 ]
Fix Version/s Release 1.7 [ 10250 ]
Alex Miller made changes -
Approval Vetted [ 10003 ] Incomplete [ 10006 ]
Alex Miller made changes -
Summary cycle and iterate return vals should IReduceInit cycle, iterate, repeate return vals should IReduceInit
Attachment clj-1603.patch [ 13582 ]
Description * with generative tests
* with perf examples
* with generative tests
* with perf examples


*Performance:*

|| Expression || 1.6.0 || 1.7.0-alpha4 || + patch ||
| (into [] (repeat 1000 1)) | 107 | 97 | 5 |
| (reduce + 0 (repeat 1000 1)) | 112 | 112 | 17 |
| (into [] (take 1000) (repeat 1)) | n/a | 75 | 33 |
| (doall (take 1000 (cycle [1 2 3]))) | 110 | 115 | 81 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 66 | 33 |
| (doall (take 1000 (iterate inc 0))) | 98 | 96 | 75 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 79 | 28 |
Patch Code [ 10001 ]
Alex Miller made changes -
Description * with generative tests
* with perf examples


*Performance:*

|| Expression || 1.6.0 || 1.7.0-alpha4 || + patch ||
| (into [] (repeat 1000 1)) | 107 | 97 | 5 |
| (reduce + 0 (repeat 1000 1)) | 112 | 112 | 17 |
| (into [] (take 1000) (repeat 1)) | n/a | 75 | 33 |
| (doall (take 1000 (cycle [1 2 3]))) | 110 | 115 | 81 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 66 | 33 |
| (doall (take 1000 (iterate inc 0))) | 98 | 96 | 75 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 79 | 28 |
* with generative tests
* with perf examples


*Performance:*

All times in µs:

|| Expression || 1.6.0 || 1.7.0-alpha4 || + patch ||
| (into [] (repeat 1000 1)) | 107 | 97 | 5 |
| (reduce + 0 (repeat 1000 1)) | 112 | 112 | 17 |
| (into [] (take 1000) (repeat 1)) | n/a | 75 | 33 |
| (doall (take 1000 (cycle [1 2 3]))) | 110 | 115 | 81 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 66 | 33 |
| (doall (take 1000 (iterate inc 0))) | 98 | 96 | 75 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 79 | 28 |
Alex Miller made changes -
Attachment clj-1603-2.patch [ 13583 ]
Description * with generative tests
* with perf examples


*Performance:*

All times in µs:

|| Expression || 1.6.0 || 1.7.0-alpha4 || + patch ||
| (into [] (repeat 1000 1)) | 107 | 97 | 5 |
| (reduce + 0 (repeat 1000 1)) | 112 | 112 | 17 |
| (into [] (take 1000) (repeat 1)) | n/a | 75 | 33 |
| (doall (take 1000 (cycle [1 2 3]))) | 110 | 115 | 81 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 66 | 33 |
| (doall (take 1000 (iterate inc 0))) | 98 | 96 | 75 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 79 | 28 |
* with generative tests
* with perf examples

*Approach:*

A few things to note:
- Added repeat to title and implementation (seemed natural along with cycle)
- Added some example tests for iterate (cycle and repeat were covered). 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.
- Because the former repeat, cycle, and iterate produced lazyseqs that participated in the IReduce form of reduce (via the seq paths in CollReduce), I extended these classes all to IReduce instead of IReduceInit. An alternative would have been to re-route the no-init form of reduce for these classes to seq-reduce.
- Because Repeat, Cycle, and Iterate are IReduce but also extend ASeq, I provided explicit extensions for them in CollReduce to ensure they got called via reduce path rather than seq path.

*Performance:*

Some example timing, all in µs:

|| Expression || 1.6.0 || 1.7.0-alpha4 || 1.7.0-alpha4 + patch ||
| (into [] (repeat 1000 1)) | 107 | 97 | 5 |
| (reduce + 0 (repeat 1000 1)) | 112 | 112 | 17 |
| (into [] (take 1000) (repeat 1)) | n/a | 75 | 33 |
| (doall (take 1000 (cycle [1 2 3]))) | 110 | 115 | 81 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 66 | 33 |
| (doall (take 1000 (iterate inc 0))) | 98 | 96 | 75 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 79 | 28 |

*Patch:* clj-1603-2.patch

*Screened by:*
Approval Incomplete [ 10006 ] Vetted [ 10003 ]
Patch Code [ 10001 ] Code and Test [ 10002 ]
Alex Miller made changes -
Description * with generative tests
* with perf examples

*Approach:*

A few things to note:
- Added repeat to title and implementation (seemed natural along with cycle)
- Added some example tests for iterate (cycle and repeat were covered). 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.
- Because the former repeat, cycle, and iterate produced lazyseqs that participated in the IReduce form of reduce (via the seq paths in CollReduce), I extended these classes all to IReduce instead of IReduceInit. An alternative would have been to re-route the no-init form of reduce for these classes to seq-reduce.
- Because Repeat, Cycle, and Iterate are IReduce but also extend ASeq, I provided explicit extensions for them in CollReduce to ensure they got called via reduce path rather than seq path.

*Performance:*

Some example timing, all in µs:

|| Expression || 1.6.0 || 1.7.0-alpha4 || 1.7.0-alpha4 + patch ||
| (into [] (repeat 1000 1)) | 107 | 97 | 5 |
| (reduce + 0 (repeat 1000 1)) | 112 | 112 | 17 |
| (into [] (take 1000) (repeat 1)) | n/a | 75 | 33 |
| (doall (take 1000 (cycle [1 2 3]))) | 110 | 115 | 81 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 66 | 33 |
| (doall (take 1000 (iterate inc 0))) | 98 | 96 | 75 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 79 | 28 |

*Patch:* clj-1603-2.patch

*Screened by:*
* with generative tests
* with perf examples

*Alternatives:*

There were a number of possible approaches for these enhancements:
1) Straight Java impl (chosen, see below)
2) Clojure deftype - there are several issues with this - complexity of implementing all necessary interfaces, entanglements with deftype load order, inability to create transient hash codes, etc - see Ghadi's comment.
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. I also considered optionally allowing this but then it is tricky when in a reduce to determine which path to go down.

In the end, #1 seemed to be the most straightforward implementation by extending ASeq and providing custom seq and reduce logic. The perf #s below demonstrate the benefits of using a customized seq impl vs the generic lazy seq versions.

*Approach:*

A few things to note:
- Added repeat to title and implementation (seemed natural along with cycle)
- Added some example tests for iterate (cycle and repeat were covered). 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.
- Because the former repeat, cycle, and iterate produced lazyseqs that participated in the IReduce form of reduce (via the seq paths in CollReduce), I extended these classes all to IReduce instead of IReduceInit. An alternative would have been to re-route the no-init form of reduce for these classes to seq-reduce.
- Because Repeat, Cycle, and Iterate are IReduce but also extend ASeq, I provided explicit extensions for them in CollReduce to ensure they got called via reduce path rather than seq path.

*Performance:*

Some example timing, all in µs:

|| Expression || 1.6.0 || 1.7.0-alpha4 || 1.7.0-alpha4 + patch ||
| (into [] (repeat 1000 1)) | 107 | 97 | 5 |
| (reduce + 0 (repeat 1000 1)) | 112 | 112 | 17 |
| (into [] (take 1000) (repeat 1)) | n/a | 75 | 33 |
| (doall (take 1000 (cycle [1 2 3]))) | 110 | 115 | 81 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 66 | 33 |
| (doall (take 1000 (iterate inc 0))) | 98 | 96 | 75 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 79 | 28 |

*Patch:* clj-1603-2.patch

*Screened by:*
Alex Miller made changes -
Summary cycle, iterate, repeate return vals should IReduceInit cycle, iterate, repeat return vals should IReduceInit
Alex Miller made changes -
Description * with generative tests
* with perf examples

*Alternatives:*

There were a number of possible approaches for these enhancements:
1) Straight Java impl (chosen, see below)
2) Clojure deftype - there are several issues with this - complexity of implementing all necessary interfaces, entanglements with deftype load order, inability to create transient hash codes, etc - see Ghadi's comment.
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. I also considered optionally allowing this but then it is tricky when in a reduce to determine which path to go down.

In the end, #1 seemed to be the most straightforward implementation by extending ASeq and providing custom seq and reduce logic. The perf #s below demonstrate the benefits of using a customized seq impl vs the generic lazy seq versions.

*Approach:*

A few things to note:
- Added repeat to title and implementation (seemed natural along with cycle)
- Added some example tests for iterate (cycle and repeat were covered). 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.
- Because the former repeat, cycle, and iterate produced lazyseqs that participated in the IReduce form of reduce (via the seq paths in CollReduce), I extended these classes all to IReduce instead of IReduceInit. An alternative would have been to re-route the no-init form of reduce for these classes to seq-reduce.
- Because Repeat, Cycle, and Iterate are IReduce but also extend ASeq, I provided explicit extensions for them in CollReduce to ensure they got called via reduce path rather than seq path.

*Performance:*

Some example timing, all in µs:

|| Expression || 1.6.0 || 1.7.0-alpha4 || 1.7.0-alpha4 + patch ||
| (into [] (repeat 1000 1)) | 107 | 97 | 5 |
| (reduce + 0 (repeat 1000 1)) | 112 | 112 | 17 |
| (into [] (take 1000) (repeat 1)) | n/a | 75 | 33 |
| (doall (take 1000 (cycle [1 2 3]))) | 110 | 115 | 81 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 66 | 33 |
| (doall (take 1000 (iterate inc 0))) | 98 | 96 | 75 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 79 | 28 |

*Patch:* clj-1603-2.patch

*Screened by:*
* with generative tests
* with perf examples

*Alternatives:*

There were a number of possible approaches for these enhancements:
1) Straight Java impl (chosen, see below)
2) Clojure deftype - there are several issues with this - complexity of implementing all necessary interfaces, entanglements with deftype load order, inability to create transient hash codes, etc - see Ghadi's comment.
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. I also considered optionally allowing this but then it is tricky when in a reduce to determine which path to go down.

In the end, #1 seemed to be the most straightforward implementation by extending ASeq and providing custom seq and reduce logic. The perf #s below demonstrate the benefits of using a customized seq impl vs the generic lazy seq versions.

*Approach:*

A few things to note:
- Added repeat to title and implementation (seemed natural along with cycle)
- Added some example tests for iterate (cycle and repeat were covered). 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.
- Because the former repeat, cycle, and iterate produced lazyseqs that participated in the IReduce form of reduce (via the seq paths in CollReduce), I extended these classes all to IReduce instead of IReduceInit. An alternative would have been to re-route the no-init form of reduce for these classes to seq-reduce.
- Because Repeat, Cycle, and Iterate are IReduce but also extend ASeq, I provided explicit extensions for them in CollReduce to ensure they got called via reduce path rather than seq path.

*Performance:*

Some example timing, all in µs:

|| Expression || 1.6.0 || 1.7.0-alpha4 || 1.7.0-alpha4 + patch ||
| (into [] (repeat 1000 1)) | 107 | 97 | 5 |
| (reduce + 0 (repeat 1000 1)) | 112 | 112 | 17 |
| (into [] (take 1000) (repeat 1)) | n/a | 75 | 33 |
| (doall (take 1000 (cycle [1 2 3]))) | 110 | 115 | 81 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 66 | 33 |
| (doall (take 1000 (iterate inc 0))) | 98 | 96 | 75 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 79 | 28 |

*Patch:* clj-1603-2.patch

*Notes for screener:*

- Should Repeat be split into finite/infinite classes? If so, should the finite one be Counted?

*Screened by:*
Alex Miller made changes -
Attachment clj-1603-3.patch [ 13709 ]
Description * with generative tests
* with perf examples

*Alternatives:*

There were a number of possible approaches for these enhancements:
1) Straight Java impl (chosen, see below)
2) Clojure deftype - there are several issues with this - complexity of implementing all necessary interfaces, entanglements with deftype load order, inability to create transient hash codes, etc - see Ghadi's comment.
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. I also considered optionally allowing this but then it is tricky when in a reduce to determine which path to go down.

In the end, #1 seemed to be the most straightforward implementation by extending ASeq and providing custom seq and reduce logic. The perf #s below demonstrate the benefits of using a customized seq impl vs the generic lazy seq versions.

*Approach:*

A few things to note:
- Added repeat to title and implementation (seemed natural along with cycle)
- Added some example tests for iterate (cycle and repeat were covered). 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.
- Because the former repeat, cycle, and iterate produced lazyseqs that participated in the IReduce form of reduce (via the seq paths in CollReduce), I extended these classes all to IReduce instead of IReduceInit. An alternative would have been to re-route the no-init form of reduce for these classes to seq-reduce.
- Because Repeat, Cycle, and Iterate are IReduce but also extend ASeq, I provided explicit extensions for them in CollReduce to ensure they got called via reduce path rather than seq path.

*Performance:*

Some example timing, all in µs:

|| Expression || 1.6.0 || 1.7.0-alpha4 || 1.7.0-alpha4 + patch ||
| (into [] (repeat 1000 1)) | 107 | 97 | 5 |
| (reduce + 0 (repeat 1000 1)) | 112 | 112 | 17 |
| (into [] (take 1000) (repeat 1)) | n/a | 75 | 33 |
| (doall (take 1000 (cycle [1 2 3]))) | 110 | 115 | 81 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 66 | 33 |
| (doall (take 1000 (iterate inc 0))) | 98 | 96 | 75 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 79 | 28 |

*Patch:* clj-1603-2.patch

*Notes for screener:*

- Should Repeat be split into finite/infinite classes? If so, should the finite one be Counted?

*Screened by:*
* with generative tests
* with perf examples

*Alternatives:*

There were a number of possible approaches for these enhancements:
1) Straight Java impl (chosen, see below)
2) Clojure deftype - there are several issues with this - complexity of implementing all necessary interfaces, entanglements with deftype load order, inability to create transient hash codes, etc - see Ghadi's comment.
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. I also considered optionally allowing this but then it is tricky when in a reduce to determine which path to go down.

In the end, #1 seemed to be the most straightforward implementation by extending ASeq and providing custom seq and reduce logic. The perf #s below demonstrate the benefits of using a customized seq impl vs the generic lazy seq versions.

*Approach:*

A few things to note:
- Added repeat to title and implementation (seemed natural along with cycle)
- Added some example tests for iterate (cycle and repeat were covered). 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.
- Because the former repeat, cycle, and iterate produced lazyseqs that participated in the IReduce form of reduce (via the seq paths in CollReduce), I extended these classes all to IReduce instead of IReduceInit. An alternative would have been to re-route the no-init form of reduce for these classes to seq-reduce.
- Because Repeat, Cycle, and Iterate are IReduce but also extend ASeq, I provided explicit extensions for them in CollReduce to ensure they got called via reduce path rather than seq path.

*Performance:*

Some example timing, all in µs:

|| Expression || 1.6.0 || 1.7.0-alpha4 || 1.7.0-alpha4 + patch ||
| (into [] (repeat 1000 1)) | 107 | 97 | 7 |
| (reduce + 0 (repeat 1000 1)) | 112 | 112 | 17 |
| (into [] (take 1000) (repeat 1)) | n/a | 75 | 29 |
| (doall (take 1000 (cycle [1 2 3]))) | 110 | 115 | 80 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 66 | 36 |
| (doall (take 1000 (iterate inc 0))) | 98 | 96 | 75 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 79 | 35 |

*Patch:* clj-1603-3.patch

*Notes for screener:*

- Should Repeat be split into finite/infinite classes? If so, should the finite one be Counted?

*Screened by:*
Alex Miller made changes -
Description * with generative tests
* with perf examples

*Alternatives:*

There were a number of possible approaches for these enhancements:
1) Straight Java impl (chosen, see below)
2) Clojure deftype - there are several issues with this - complexity of implementing all necessary interfaces, entanglements with deftype load order, inability to create transient hash codes, etc - see Ghadi's comment.
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. I also considered optionally allowing this but then it is tricky when in a reduce to determine which path to go down.

In the end, #1 seemed to be the most straightforward implementation by extending ASeq and providing custom seq and reduce logic. The perf #s below demonstrate the benefits of using a customized seq impl vs the generic lazy seq versions.

*Approach:*

A few things to note:
- Added repeat to title and implementation (seemed natural along with cycle)
- Added some example tests for iterate (cycle and repeat were covered). 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.
- Because the former repeat, cycle, and iterate produced lazyseqs that participated in the IReduce form of reduce (via the seq paths in CollReduce), I extended these classes all to IReduce instead of IReduceInit. An alternative would have been to re-route the no-init form of reduce for these classes to seq-reduce.
- Because Repeat, Cycle, and Iterate are IReduce but also extend ASeq, I provided explicit extensions for them in CollReduce to ensure they got called via reduce path rather than seq path.

*Performance:*

Some example timing, all in µs:

|| Expression || 1.6.0 || 1.7.0-alpha4 || 1.7.0-alpha4 + patch ||
| (into [] (repeat 1000 1)) | 107 | 97 | 7 |
| (reduce + 0 (repeat 1000 1)) | 112 | 112 | 17 |
| (into [] (take 1000) (repeat 1)) | n/a | 75 | 29 |
| (doall (take 1000 (cycle [1 2 3]))) | 110 | 115 | 80 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 66 | 36 |
| (doall (take 1000 (iterate inc 0))) | 98 | 96 | 75 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 79 | 35 |

*Patch:* clj-1603-3.patch

*Notes for screener:*

- Should Repeat be split into finite/infinite classes? If so, should the finite one be Counted?

*Screened by:*
* with generative tests
* with perf examples

*Alternatives:*

There were a number of possible approaches for these enhancements:
1) Straight Java impl (chosen, see below)
2) Clojure deftype - there are several issues with this - complexity of implementing all necessary interfaces, entanglements with deftype load order, inability to create transient hash codes, etc - see Ghadi's comment.
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. I also considered optionally allowing this but then it is tricky when in a reduce to determine which path to go down.

In the end, #1 seemed to be the most straightforward implementation by extending ASeq and providing custom seq and reduce logic. The perf #s below demonstrate the benefits of using a customized seq impl vs the generic lazy seq versions.

*Approach:*

A few things to note:
- Added repeat to title and implementation (seemed natural along with cycle)
- Added some example tests for iterate (cycle and repeat were covered). 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.
- Because the former repeat, cycle, and iterate produced lazyseqs that participated in the IReduce form of reduce (via the seq paths in CollReduce), I extended these classes all to IReduce instead of IReduceInit. An alternative would have been to re-route the no-init form of reduce for these classes to seq-reduce.
- Because Repeat, Cycle, and Iterate are IReduce but also extend ASeq, I provided explicit extensions for them in CollReduce to ensure they got called via reduce path rather than seq path. See also CLJ-1572, which may make this unnecessary.

*Performance:*

Some example timing, all in µs:

|| Expression || 1.6.0 || 1.7.0-alpha4 || 1.7.0-alpha4 + patch ||
| (into [] (repeat 1000 1)) | 107 | 97 | 7 |
| (reduce + 0 (repeat 1000 1)) | 112 | 112 | 17 |
| (into [] (take 1000) (repeat 1)) | n/a | 75 | 29 |
| (doall (take 1000 (cycle [1 2 3]))) | 110 | 115 | 80 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 66 | 36 |
| (doall (take 1000 (iterate inc 0))) | 98 | 96 | 75 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 79 | 35 |

*Patch:* clj-1603-3.patch

*Notes for screener:*

- Should Repeat be split into finite/infinite classes? If so, should the finite one be Counted?

*Screened by:*
Alex Miller made changes -
Approval Vetted [ 10003 ] Incomplete [ 10006 ]
Alex Miller made changes -
Attachment clj-1603-4.patch [ 13766 ]
Description * with generative tests
* with perf examples

*Alternatives:*

There were a number of possible approaches for these enhancements:
1) Straight Java impl (chosen, see below)
2) Clojure deftype - there are several issues with this - complexity of implementing all necessary interfaces, entanglements with deftype load order, inability to create transient hash codes, etc - see Ghadi's comment.
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. I also considered optionally allowing this but then it is tricky when in a reduce to determine which path to go down.

In the end, #1 seemed to be the most straightforward implementation by extending ASeq and providing custom seq and reduce logic. The perf #s below demonstrate the benefits of using a customized seq impl vs the generic lazy seq versions.

*Approach:*

A few things to note:
- Added repeat to title and implementation (seemed natural along with cycle)
- Added some example tests for iterate (cycle and repeat were covered). 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.
- Because the former repeat, cycle, and iterate produced lazyseqs that participated in the IReduce form of reduce (via the seq paths in CollReduce), I extended these classes all to IReduce instead of IReduceInit. An alternative would have been to re-route the no-init form of reduce for these classes to seq-reduce.
- Because Repeat, Cycle, and Iterate are IReduce but also extend ASeq, I provided explicit extensions for them in CollReduce to ensure they got called via reduce path rather than seq path. See also CLJ-1572, which may make this unnecessary.

*Performance:*

Some example timing, all in µs:

|| Expression || 1.6.0 || 1.7.0-alpha4 || 1.7.0-alpha4 + patch ||
| (into [] (repeat 1000 1)) | 107 | 97 | 7 |
| (reduce + 0 (repeat 1000 1)) | 112 | 112 | 17 |
| (into [] (take 1000) (repeat 1)) | n/a | 75 | 29 |
| (doall (take 1000 (cycle [1 2 3]))) | 110 | 115 | 80 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 66 | 36 |
| (doall (take 1000 (iterate inc 0))) | 98 | 96 | 75 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 79 | 35 |

*Patch:* clj-1603-3.patch

*Notes for screener:*

- Should Repeat be split into finite/infinite classes? If so, should the finite one be Counted?

*Screened by:*
* with generative tests
* with perf examples

*Alternatives:*

There were a number of possible approaches for these enhancements:
1) Straight Java impl - see clj-1603-3.patch
2) Clojure deftype - see clj-1603-4.patch (current choice)
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. I also considered optionally allowing this but then it is tricky when in a reduce to determine which path to go down.

*Approach:* The first few versions of this patch (through clj-1603-3) used Java-based implementations. These have the benefit of improving the performance of both the seq and reduce paths at the expense of writing a bunch of Java. The clj-1603-4 patch uses a deftype based approach - 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 and a much smaller patch. This seems better, so I am proposing clj-1603-4 for screening.

A few things to note:
- Added repeat to title and implementation (seemed natural along with cycle)
- 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.
- Because the former repeat, cycle, and iterate produced lazyseqs that participated in the IReduce form of reduce (via the seq paths in CollReduce), I extended all impls to IReduce instead of IReduceInit as otherwise there would be a regression in the non-init path (I did see one test that encountered this for repeat).

*Performance:*

Some example timing, all in µs:

|| Expression || 1.6.0 || 1.7.0-alpha5 || alpha5 + clj-1603-3 || alpha5 + clj-1603-4 ||
| (doall (repeat 1000 1)) | 87 | 94 | 8 | 90 |
| (into [] (repeat 1000 1)) | 99 | 110 | 12 | 12 |
| (reduce + 0 (repeat 1000 1)) | 99 | 126 | 17 | 18 |
| (into [] (take 1000) (repeat 1)) | n/a | 67 | 35 | 28 |
| (doall (take 1000 (cycle [1 2 3]))) | 101 | 106 | 78 | 106 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 73 | 39 | 42 |
| (doall (take 1000 (iterate inc 0))) | 93 | 98 | 71 | 102 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 85 | 39 | 38 |

- clj-1603-3 is a Java class implementation - generally it's faster for both seqs and reduce (at the cost of more Java)
- clj-1603-4 is a deftype implementation - generally it's about the same on seqs but faster on reduce

*Patch:* clj-1603-4.patch

*Screened by:*
Approval Incomplete [ 10006 ] Vetted [ 10003 ]
Alex Miller made changes -
Description * with generative tests
* with perf examples

*Alternatives:*

There were a number of possible approaches for these enhancements:
1) Straight Java impl - see clj-1603-3.patch
2) Clojure deftype - see clj-1603-4.patch (current choice)
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. I also considered optionally allowing this but then it is tricky when in a reduce to determine which path to go down.

*Approach:* The first few versions of this patch (through clj-1603-3) used Java-based implementations. These have the benefit of improving the performance of both the seq and reduce paths at the expense of writing a bunch of Java. The clj-1603-4 patch uses a deftype based approach - 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 and a much smaller patch. This seems better, so I am proposing clj-1603-4 for screening.

A few things to note:
- Added repeat to title and implementation (seemed natural along with cycle)
- 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.
- Because the former repeat, cycle, and iterate produced lazyseqs that participated in the IReduce form of reduce (via the seq paths in CollReduce), I extended all impls to IReduce instead of IReduceInit as otherwise there would be a regression in the non-init path (I did see one test that encountered this for repeat).

*Performance:*

Some example timing, all in µs:

|| Expression || 1.6.0 || 1.7.0-alpha5 || alpha5 + clj-1603-3 || alpha5 + clj-1603-4 ||
| (doall (repeat 1000 1)) | 87 | 94 | 8 | 90 |
| (into [] (repeat 1000 1)) | 99 | 110 | 12 | 12 |
| (reduce + 0 (repeat 1000 1)) | 99 | 126 | 17 | 18 |
| (into [] (take 1000) (repeat 1)) | n/a | 67 | 35 | 28 |
| (doall (take 1000 (cycle [1 2 3]))) | 101 | 106 | 78 | 106 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 73 | 39 | 42 |
| (doall (take 1000 (iterate inc 0))) | 93 | 98 | 71 | 102 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 85 | 39 | 38 |

- clj-1603-3 is a Java class implementation - generally it's faster for both seqs and reduce (at the cost of more Java)
- clj-1603-4 is a deftype implementation - generally it's about the same on seqs but faster on reduce

*Patch:* clj-1603-4.patch

*Screened by:*
* with generative tests
* with perf examples

*Alternatives:*

There were a number of possible approaches for these enhancements:
1) Straight Java impl - see clj-1603-3.patch
2) Clojure deftype - see clj-1603-4.patch (current choice)
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. I also considered optionally allowing this but then it is tricky when in a reduce to determine which path to go down.

*Approach:* The first few versions of this patch (through clj-1603-3) used Java-based implementations. These have the benefit of improving the performance of both the seq and reduce paths at the expense of writing a bunch of Java. The clj-1603-4 patch uses a deftype based approach - 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 and a much smaller patch. This seems better, so I am proposing clj-1603-4 for screening.

A few things to note:
- Added repeat to title and implementation (seemed natural along with cycle)
- 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.
- Because the former repeat, cycle, and iterate produced lazyseqs that participated in the IReduce form of reduce (via the seq paths in CollReduce), I extended all impls to IReduce instead of IReduceInit as otherwise there would be a regression in the non-init path (I did see one test that encountered this for repeat).

*Performance:*

Some example timing, all in µs:

|| Expression || 1.6.0 || 1.7.0-alpha5 || alpha5 + clj-1603-3 (Java) || alpha5 + clj-1603-4 (deftype) ||
| (doall (repeat 1000 1)) | 87 | 94 | 8 | 90 |
| (into [] (repeat 1000 1)) | 99 | 110 | 12 | 12 |
| (reduce + 0 (repeat 1000 1)) | 99 | 126 | 17 | 18 |
| (into [] (take 1000) (repeat 1)) | n/a | 67 | 35 | 28 |
| (doall (take 1000 (cycle [1 2 3]))) | 101 | 106 | 78 | 106 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 73 | 39 | 42 |
| (doall (take 1000 (iterate inc 0))) | 93 | 98 | 71 | 102 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 85 | 39 | 38 |

- clj-1603-3 is a Java class implementation - generally it's faster for both seqs and reduce (at the cost of more Java)
- clj-1603-4 is a deftype implementation - generally it's about the same on seqs but faster on reduce

*Patch:* clj-1603-4.patch

*Screened by:*
Stuart Halloway made changes -
Approval Vetted [ 10003 ] Incomplete [ 10006 ]
Alex Miller made changes -
Attachment clj-1603-5.patch [ 13774 ]
Description * with generative tests
* with perf examples

*Alternatives:*

There were a number of possible approaches for these enhancements:
1) Straight Java impl - see clj-1603-3.patch
2) Clojure deftype - see clj-1603-4.patch (current choice)
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. I also considered optionally allowing this but then it is tricky when in a reduce to determine which path to go down.

*Approach:* The first few versions of this patch (through clj-1603-3) used Java-based implementations. These have the benefit of improving the performance of both the seq and reduce paths at the expense of writing a bunch of Java. The clj-1603-4 patch uses a deftype based approach - 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 and a much smaller patch. This seems better, so I am proposing clj-1603-4 for screening.

A few things to note:
- Added repeat to title and implementation (seemed natural along with cycle)
- 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.
- Because the former repeat, cycle, and iterate produced lazyseqs that participated in the IReduce form of reduce (via the seq paths in CollReduce), I extended all impls to IReduce instead of IReduceInit as otherwise there would be a regression in the non-init path (I did see one test that encountered this for repeat).

*Performance:*

Some example timing, all in µs:

|| Expression || 1.6.0 || 1.7.0-alpha5 || alpha5 + clj-1603-3 (Java) || alpha5 + clj-1603-4 (deftype) ||
| (doall (repeat 1000 1)) | 87 | 94 | 8 | 90 |
| (into [] (repeat 1000 1)) | 99 | 110 | 12 | 12 |
| (reduce + 0 (repeat 1000 1)) | 99 | 126 | 17 | 18 |
| (into [] (take 1000) (repeat 1)) | n/a | 67 | 35 | 28 |
| (doall (take 1000 (cycle [1 2 3]))) | 101 | 106 | 78 | 106 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 73 | 39 | 42 |
| (doall (take 1000 (iterate inc 0))) | 93 | 98 | 71 | 102 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 85 | 39 | 38 |

- clj-1603-3 is a Java class implementation - generally it's faster for both seqs and reduce (at the cost of more Java)
- clj-1603-4 is a deftype implementation - generally it's about the same on seqs but faster on reduce

*Patch:* clj-1603-4.patch

*Screened by:*
* with generative tests
* with perf examples

*Alternatives:*

There were a number of possible approaches for these enhancements:
1) Straight Java impl - see clj-1603-3.patch
2) Clojure deftype - see clj-1603-4.patch (current choice)
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. I also considered optionally allowing this but then it is tricky when in a reduce to determine which path to go down.

*Approach:* The first few versions of this patch (through clj-1603-3) used Java-based implementations. These have the benefit of improving the performance of both the seq and reduce paths at the expense of writing a bunch of Java. The clj-1603-4 patch uses a deftype based approach - 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 and a much smaller patch. This seems better, so I am proposing clj-1603-4 for screening.

A few things to note:
- Added repeat to title and implementation (seemed natural along with cycle)
- 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.
- I extended finite repeat to IReduce instead of IReduceInit as otherwise there would be a regression in the non-init path (we had one existing test where this failed).

*Performance:*

Some example timing, all in µs:

|| Expression || 1.6.0 || 1.7.0-alpha5 || alpha5 + clj-1603-3 (Java) || alpha5 + clj-1603-4 (deftype) ||
| (doall (repeat 1000 1)) | 87 | 94 | 8 | 90 |
| (into [] (repeat 1000 1)) | 99 | 110 | 12 | 12 |
| (reduce + 0 (repeat 1000 1)) | 99 | 126 | 17 | 18 |
| (into [] (take 1000) (repeat 1)) | n/a | 67 | 35 | 28 |
| (doall (take 1000 (cycle [1 2 3]))) | 101 | 106 | 78 | 106 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 73 | 39 | 42 |
| (doall (take 1000 (iterate inc 0))) | 93 | 98 | 71 | 102 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 85 | 39 | 38 |

- clj-1603-3 is a Java class implementation - generally it's faster for both seqs and reduce (at the cost of more Java)
- clj-1603-4 is a deftype implementation - generally it's about the same on seqs but faster on reduce

*Patch:* clj-1603-5.patch

*Screened by:*
Approval Incomplete [ 10006 ] Vetted [ 10003 ]
Stuart Halloway made changes -
Approval Vetted [ 10003 ] Screened [ 10004 ]
Alex Miller made changes -
Description * with generative tests
* with perf examples

*Alternatives:*

There were a number of possible approaches for these enhancements:
1) Straight Java impl - see clj-1603-3.patch
2) Clojure deftype - see clj-1603-4.patch (current choice)
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. I also considered optionally allowing this but then it is tricky when in a reduce to determine which path to go down.

*Approach:* The first few versions of this patch (through clj-1603-3) used Java-based implementations. These have the benefit of improving the performance of both the seq and reduce paths at the expense of writing a bunch of Java. The clj-1603-4 patch uses a deftype based approach - 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 and a much smaller patch. This seems better, so I am proposing clj-1603-4 for screening.

A few things to note:
- Added repeat to title and implementation (seemed natural along with cycle)
- 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.
- I extended finite repeat to IReduce instead of IReduceInit as otherwise there would be a regression in the non-init path (we had one existing test where this failed).

*Performance:*

Some example timing, all in µs:

|| Expression || 1.6.0 || 1.7.0-alpha5 || alpha5 + clj-1603-3 (Java) || alpha5 + clj-1603-4 (deftype) ||
| (doall (repeat 1000 1)) | 87 | 94 | 8 | 90 |
| (into [] (repeat 1000 1)) | 99 | 110 | 12 | 12 |
| (reduce + 0 (repeat 1000 1)) | 99 | 126 | 17 | 18 |
| (into [] (take 1000) (repeat 1)) | n/a | 67 | 35 | 28 |
| (doall (take 1000 (cycle [1 2 3]))) | 101 | 106 | 78 | 106 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 73 | 39 | 42 |
| (doall (take 1000 (iterate inc 0))) | 93 | 98 | 71 | 102 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 85 | 39 | 38 |

- clj-1603-3 is a Java class implementation - generally it's faster for both seqs and reduce (at the cost of more Java)
- clj-1603-4 is a deftype implementation - generally it's about the same on seqs but faster on reduce

*Patch:* clj-1603-5.patch

*Screened by:*
* with generative tests
* with perf examples

*Alternatives:*

There were a number of possible approaches for these enhancements:
1) Straight Java impl - see clj-1603-3.patch
2) Clojure deftype - see clj-1603-5.patch (current choice)
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. I also considered optionally allowing this but then it is tricky when in a reduce to determine which path to go down.

*Approach:* The first few versions of this patch (through clj-1603-3) used Java-based implementations. These have the benefit of improving the performance of both the seq and reduce paths at the expense of writing a bunch of Java. The clj-1603-5 patch uses a deftype based approach - 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 and a much smaller patch. This seems better, so I am proposing clj-1603-5 for screening.

A few things to note:
- Added repeat to title and implementation (seemed natural along with cycle)
- 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.
- I extended finite repeat to IReduce instead of IReduceInit as otherwise there would be a regression in the non-init path (we had one existing test where this failed).

*Performance:*

Some example timing, all in µs:

|| Expression || 1.6.0 || 1.7.0-alpha5 || alpha5 + clj-1603-3 (Java) || alpha5 + clj-1603-5 (deftype) ||
| (doall (repeat 1000 1)) | 87 | 94 | 8 | 90 |
| (into [] (repeat 1000 1)) | 99 | 110 | 12 | 12 |
| (reduce + 0 (repeat 1000 1)) | 99 | 126 | 17 | 18 |
| (into [] (take 1000) (repeat 1)) | n/a | 67 | 35 | 28 |
| (doall (take 1000 (cycle [1 2 3]))) | 101 | 106 | 78 | 106 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 73 | 39 | 42 |
| (doall (take 1000 (iterate inc 0))) | 93 | 98 | 71 | 102 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 85 | 39 | 38 |

- clj-1603-3 is a Java class implementation - generally it's faster for both seqs and reduce (at the cost of more Java)
- clj-1603-5 is a deftype implementation - generally it's about the same on seqs but faster on reduce

*Patch:* clj-1603-5.patch

*Screened by:* Stu Halloway
Michael Blume made changes -
Attachment clj-1603-6.patch [ 13780 ]
Alex Miller made changes -
Attachment clj-1603-7.patch [ 13786 ]
Description * with generative tests
* with perf examples

*Alternatives:*

There were a number of possible approaches for these enhancements:
1) Straight Java impl - see clj-1603-3.patch
2) Clojure deftype - see clj-1603-5.patch (current choice)
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. I also considered optionally allowing this but then it is tricky when in a reduce to determine which path to go down.

*Approach:* The first few versions of this patch (through clj-1603-3) used Java-based implementations. These have the benefit of improving the performance of both the seq and reduce paths at the expense of writing a bunch of Java. The clj-1603-5 patch uses a deftype based approach - 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 and a much smaller patch. This seems better, so I am proposing clj-1603-5 for screening.

A few things to note:
- Added repeat to title and implementation (seemed natural along with cycle)
- 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.
- I extended finite repeat to IReduce instead of IReduceInit as otherwise there would be a regression in the non-init path (we had one existing test where this failed).

*Performance:*

Some example timing, all in µs:

|| Expression || 1.6.0 || 1.7.0-alpha5 || alpha5 + clj-1603-3 (Java) || alpha5 + clj-1603-5 (deftype) ||
| (doall (repeat 1000 1)) | 87 | 94 | 8 | 90 |
| (into [] (repeat 1000 1)) | 99 | 110 | 12 | 12 |
| (reduce + 0 (repeat 1000 1)) | 99 | 126 | 17 | 18 |
| (into [] (take 1000) (repeat 1)) | n/a | 67 | 35 | 28 |
| (doall (take 1000 (cycle [1 2 3]))) | 101 | 106 | 78 | 106 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 73 | 39 | 42 |
| (doall (take 1000 (iterate inc 0))) | 93 | 98 | 71 | 102 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 85 | 39 | 38 |

- clj-1603-3 is a Java class implementation - generally it's faster for both seqs and reduce (at the cost of more Java)
- clj-1603-5 is a deftype implementation - generally it's about the same on seqs but faster on reduce

*Patch:* clj-1603-5.patch

*Screened by:* Stu Halloway
* with generative tests
* with perf examples

*Alternatives:*

There were a number of possible approaches for these enhancements:
1) Straight Java impl - see clj-1603-3.patch
2) Clojure deftype - see latest patch (current choice)
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. I also considered optionally allowing this but then it is tricky when in a reduce to determine which path to go down.

*Approach:* The first few versions of this patch (through clj-1603-3) used Java-based implementations. These have the benefit of improving the performance of both the seq and reduce paths at the expense of writing a bunch of Java. The latest patch uses a deftype based approach - 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 and a much smaller patch. This seems better.

A few things to note:
- Added repeat to title and implementation (seemed natural along with cycle)
- 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.
- I extended finite repeat to IReduce instead of IReduceInit as otherwise there would be a regression in the non-init path (we had one existing test where this failed).
- print-method is implemented for all of the new deftypes and print-dup is implemented for FiniteRepeat. print-dup doesn't seem to make sense on the other infinite length sequences.
- I added calls to ns-unmap the deftype constructor functions so they're not publicly visible

*Performance:*

Some example timing, all in µs:

|| Expression || 1.6.0 || 1.7.0-alpha5 || alpha5 + clj-1603-3 (Java) || alpha5 + clj-1603-7 (deftype) ||
| (doall (repeat 1000 1)) | 87 | 94 | 8 | 90 |
| (into [] (repeat 1000 1)) | 99 | 110 | 12 | 12 |
| (reduce + 0 (repeat 1000 1)) | 99 | 126 | 17 | 18 |
| (into [] (take 1000) (repeat 1)) | n/a | 67 | 35 | 28 |
| (doall (take 1000 (cycle [1 2 3]))) | 101 | 106 | 78 | 106 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 73 | 39 | 42 |
| (doall (take 1000 (iterate inc 0))) | 93 | 98 | 71 | 102 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 85 | 39 | 38 |

- clj-1603-3 is a Java class implementation - generally it's faster for both seqs and reduce (at the cost of more Java)
- clj-1603-7 is a deftype implementation - generally it's about the same on seqs but faster on reduce

*Patch:* clj-1603-7.patch

*Screened by:*
Approval Screened [ 10004 ] Vetted [ 10003 ]
Alex Miller made changes -
Attachment clj-1603-8.patch [ 13797 ]
Description * with generative tests
* with perf examples

*Alternatives:*

There were a number of possible approaches for these enhancements:
1) Straight Java impl - see clj-1603-3.patch
2) Clojure deftype - see latest patch (current choice)
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. I also considered optionally allowing this but then it is tricky when in a reduce to determine which path to go down.

*Approach:* The first few versions of this patch (through clj-1603-3) used Java-based implementations. These have the benefit of improving the performance of both the seq and reduce paths at the expense of writing a bunch of Java. The latest patch uses a deftype based approach - 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 and a much smaller patch. This seems better.

A few things to note:
- Added repeat to title and implementation (seemed natural along with cycle)
- 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.
- I extended finite repeat to IReduce instead of IReduceInit as otherwise there would be a regression in the non-init path (we had one existing test where this failed).
- print-method is implemented for all of the new deftypes and print-dup is implemented for FiniteRepeat. print-dup doesn't seem to make sense on the other infinite length sequences.
- I added calls to ns-unmap the deftype constructor functions so they're not publicly visible

*Performance:*

Some example timing, all in µs:

|| Expression || 1.6.0 || 1.7.0-alpha5 || alpha5 + clj-1603-3 (Java) || alpha5 + clj-1603-7 (deftype) ||
| (doall (repeat 1000 1)) | 87 | 94 | 8 | 90 |
| (into [] (repeat 1000 1)) | 99 | 110 | 12 | 12 |
| (reduce + 0 (repeat 1000 1)) | 99 | 126 | 17 | 18 |
| (into [] (take 1000) (repeat 1)) | n/a | 67 | 35 | 28 |
| (doall (take 1000 (cycle [1 2 3]))) | 101 | 106 | 78 | 106 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 73 | 39 | 42 |
| (doall (take 1000 (iterate inc 0))) | 93 | 98 | 71 | 102 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 85 | 39 | 38 |

- clj-1603-3 is a Java class implementation - generally it's faster for both seqs and reduce (at the cost of more Java)
- clj-1603-7 is a deftype implementation - generally it's about the same on seqs but faster on reduce

*Patch:* clj-1603-7.patch

*Screened by:*
* with generative tests
* with perf examples

*Alternatives:*

There were a number of possible approaches for these enhancements:
1) Straight Java impl - see clj-1603-3.patch
2) Clojure deftype - see latest patch (most recent patch)
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. I also considered optionally allowing this but then it is tricky when in a reduce to determine which path to go down.

*Approach:* The first few versions of this patch (through clj-1603-3) used Java-based implementations. These have the benefit of improving the performance of both the seq and reduce paths at the expense of writing a bunch of Java. The latest patch uses a deftype based approach - 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 and a much smaller patch. This seems better.

A few things to note:
- Added repeat to title and implementation (seemed natural along with cycle)
- 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.
- I extended finite repeat to IReduce instead of IReduceInit as otherwise there would be a regression in the non-init path (we had one existing test where this failed).
- print-method is implemented for all of the new deftypes and print-dup is implemented for FiniteRepeat. print-dup doesn't seem to make sense on the other infinite length sequences.
- I added calls to ns-unmap the deftype constructor functions so they're not publicly visible

*Performance:*

Some example timing, all in µs:

|| Expression || 1.6.0 || 1.7.0-alpha5 || alpha5 + clj-1603-3 (Java) || alpha5 + clj-1603-8 (deftype) ||
| (doall (repeat 1000 1)) | 87 | 94 | 8 | 92 |
| (into [] (repeat 1000 1)) | 99 | 110 | 12 | 12 |
| (reduce + 0 (repeat 1000 1)) | 99 | 126 | 17 | 19 |
| (into [] (take 1000) (repeat 1)) | n/a | 67 | 35 | 29 |
| (doall (take 1000 (cycle [1 2 3]))) | 101 | 106 | 78 | 106 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 73 | 39 | 45 |
| (doall (take 1000 (iterate inc 0))) | 93 | 98 | 71 | 102 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 85 | 39 | 39 |

- clj-1603-3 is a Java class implementation - generally it's faster for both seqs and reduce (at the cost of more Java)
- clj-1603-8 is a deftype implementation - generally it's about the same on seqs but faster on reduce

*Patch:* clj-1603-8.patch

*Screened by:*
Fogus made changes -
Assignee Alex Miller [ alexmiller ] Fogus [ fogus ]
Alex Miller made changes -
Approval Vetted [ 10003 ] Incomplete [ 10006 ]
Fogus made changes -
Assignee Fogus [ fogus ]
Alex Miller made changes -
Attachment clj-1603-9.patch [ 13801 ]
Description * with generative tests
* with perf examples

*Alternatives:*

There were a number of possible approaches for these enhancements:
1) Straight Java impl - see clj-1603-3.patch
2) Clojure deftype - see latest patch (most recent patch)
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. I also considered optionally allowing this but then it is tricky when in a reduce to determine which path to go down.

*Approach:* The first few versions of this patch (through clj-1603-3) used Java-based implementations. These have the benefit of improving the performance of both the seq and reduce paths at the expense of writing a bunch of Java. The latest patch uses a deftype based approach - 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 and a much smaller patch. This seems better.

A few things to note:
- Added repeat to title and implementation (seemed natural along with cycle)
- 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.
- I extended finite repeat to IReduce instead of IReduceInit as otherwise there would be a regression in the non-init path (we had one existing test where this failed).
- print-method is implemented for all of the new deftypes and print-dup is implemented for FiniteRepeat. print-dup doesn't seem to make sense on the other infinite length sequences.
- I added calls to ns-unmap the deftype constructor functions so they're not publicly visible

*Performance:*

Some example timing, all in µs:

|| Expression || 1.6.0 || 1.7.0-alpha5 || alpha5 + clj-1603-3 (Java) || alpha5 + clj-1603-8 (deftype) ||
| (doall (repeat 1000 1)) | 87 | 94 | 8 | 92 |
| (into [] (repeat 1000 1)) | 99 | 110 | 12 | 12 |
| (reduce + 0 (repeat 1000 1)) | 99 | 126 | 17 | 19 |
| (into [] (take 1000) (repeat 1)) | n/a | 67 | 35 | 29 |
| (doall (take 1000 (cycle [1 2 3]))) | 101 | 106 | 78 | 106 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 73 | 39 | 45 |
| (doall (take 1000 (iterate inc 0))) | 93 | 98 | 71 | 102 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 85 | 39 | 39 |

- clj-1603-3 is a Java class implementation - generally it's faster for both seqs and reduce (at the cost of more Java)
- clj-1603-8 is a deftype implementation - generally it's about the same on seqs but faster on reduce

*Patch:* clj-1603-8.patch

*Screened by:*
* with generative tests
* with perf examples

*Alternatives:*

There were a number of possible approaches for these enhancements:
1) Straight Java impl - see clj-1603-3.patch
2) Clojure deftype - see latest patch (most recent patch)
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. I also considered optionally allowing this but then it is tricky when in a reduce to determine which path to go down.

*Approach:* The first few versions of this patch (through clj-1603-3) used Java-based implementations. These have the benefit of improving the performance of both the seq and reduce paths at the expense of writing a bunch of Java. The latest patch uses a deftype based approach - 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 and a much smaller patch. This seems better.

A few things to note:
- Added repeat to title and implementation (seemed natural along with cycle)
- 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.
- I extended finite repeat to IReduce instead of IReduceInit as otherwise there would be a regression in the non-init path (we had one existing test where this failed).
- print-method is implemented for all of the new deftypes and print-dup is implemented for FiniteRepeat. print-dup doesn't seem to make sense on the other infinite length sequences.
- I added calls to ns-unmap the deftype constructor functions so they're not publicly visible
- the finite repeat has implementations for hashing and equality that just defer to seq semantics. the infinite seqs will do nothing useful (as there is nothing useful to do). considered deferring to seq semantics (infinite loop) or throwing an exception.

*Performance:*

Some example timing, all in µs:

|| Expression || 1.6.0 || 1.7.0-alpha5 || alpha5 + clj-1603-3 (Java) || alpha5 + clj-1603-9 (deftype) ||
| (doall (repeat 1000 1)) | 87 | 94 | 8 | 92 |
| (into [] (repeat 1000 1)) | 99 | 110 | 12 | 12 |
| (reduce + 0 (repeat 1000 1)) | 99 | 126 | 17 | 19 |
| (into [] (take 1000) (repeat 1)) | n/a | 67 | 35 | 29 |
| (doall (take 1000 (cycle [1 2 3]))) | 101 | 106 | 78 | 106 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 73 | 39 | 45 |
| (doall (take 1000 (iterate inc 0))) | 93 | 98 | 71 | 102 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 85 | 39 | 39 |

- clj-1603-3 is a Java class implementation - generally it's faster for both seqs and reduce (at the cost of more Java)
- clj-1603-8 is a deftype implementation - generally it's about the same on seqs but faster on reduce

*Patch:* clj-1603-9.patch

*Screened by:*
Approval Incomplete [ 10006 ] Vetted [ 10003 ]
Alex Miller made changes -
Description * with generative tests
* with perf examples

*Alternatives:*

There were a number of possible approaches for these enhancements:
1) Straight Java impl - see clj-1603-3.patch
2) Clojure deftype - see latest patch (most recent patch)
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. I also considered optionally allowing this but then it is tricky when in a reduce to determine which path to go down.

*Approach:* The first few versions of this patch (through clj-1603-3) used Java-based implementations. These have the benefit of improving the performance of both the seq and reduce paths at the expense of writing a bunch of Java. The latest patch uses a deftype based approach - 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 and a much smaller patch. This seems better.

A few things to note:
- Added repeat to title and implementation (seemed natural along with cycle)
- 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.
- I extended finite repeat to IReduce instead of IReduceInit as otherwise there would be a regression in the non-init path (we had one existing test where this failed).
- print-method is implemented for all of the new deftypes and print-dup is implemented for FiniteRepeat. print-dup doesn't seem to make sense on the other infinite length sequences.
- I added calls to ns-unmap the deftype constructor functions so they're not publicly visible
- the finite repeat has implementations for hashing and equality that just defer to seq semantics. the infinite seqs will do nothing useful (as there is nothing useful to do). considered deferring to seq semantics (infinite loop) or throwing an exception.

*Performance:*

Some example timing, all in µs:

|| Expression || 1.6.0 || 1.7.0-alpha5 || alpha5 + clj-1603-3 (Java) || alpha5 + clj-1603-9 (deftype) ||
| (doall (repeat 1000 1)) | 87 | 94 | 8 | 92 |
| (into [] (repeat 1000 1)) | 99 | 110 | 12 | 12 |
| (reduce + 0 (repeat 1000 1)) | 99 | 126 | 17 | 19 |
| (into [] (take 1000) (repeat 1)) | n/a | 67 | 35 | 29 |
| (doall (take 1000 (cycle [1 2 3]))) | 101 | 106 | 78 | 106 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 73 | 39 | 45 |
| (doall (take 1000 (iterate inc 0))) | 93 | 98 | 71 | 102 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 85 | 39 | 39 |

- clj-1603-3 is a Java class implementation - generally it's faster for both seqs and reduce (at the cost of more Java)
- clj-1603-8 is a deftype implementation - generally it's about the same on seqs but faster on reduce

*Patch:* clj-1603-9.patch

*Screened by:*
* with generative tests
* with perf examples

*Alternatives:*

There were a number of possible approaches for these enhancements:
1) Straight Java impl - see clj-1603-3.patch
2) Clojure deftype - see latest patch (most recent patch)
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. I also considered optionally allowing this but then it is tricky when in a reduce to determine which path to go down.

*Approach:* The first few versions of this patch (through clj-1603-3) used Java-based implementations. These have the benefit of improving the performance of both the seq and reduce paths at the expense of writing a bunch of Java. The latest patch uses a deftype based approach - 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 and a much smaller patch. This seems better.

A few things to note:
- Added repeat to title and implementation (seemed natural along with cycle)
- 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.
- I extended finite repeat to IReduce instead of IReduceInit as otherwise there would be a regression in the non-init path (we had one existing test where this failed).
- print-method is implemented for all of the new deftypes and print-dup is implemented for FiniteRepeat. print-dup doesn't seem to make sense on the other infinite length sequences.
- I added calls to ns-unmap the deftype constructor functions so they're not publicly visible
- the finite repeat has implementations for hashing and equality that just defer to seq semantics. the infinite seqs will do nothing useful (as there is nothing useful to do). considered deferring to seq semantics (infinite loop) or throwing an exception.

*Performance:*

Some example timing, all in µs:

|| Expression || 1.6.0 || 1.7.0-alpha5 || alpha5 + clj-1603-3 (Java) || alpha5 + clj-1603-9 (deftype) ||
| (doall (repeat 1000 1)) | 87 | 94 | 8 | 92 |
| (into [] (repeat 1000 1)) | 99 | 110 | 12 | 12 |
| (reduce + 0 (repeat 1000 1)) | 99 | 126 | 17 | 19 |
| (into [] (take 1000) (repeat 1)) | n/a | 67 | 35 | 29 |
| (doall (take 1000 (cycle [1 2 3]))) | 101 | 106 | 78 | 106 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 73 | 39 | 45 |
| (doall (take 1000 (iterate inc 0))) | 93 | 98 | 71 | 102 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 85 | 39 | 39 |

- clj-1603-3 is a Java class implementation - generally it's faster for both seqs and reduce (at the cost of more Java)
- clj-1603-9 is a deftype implementation - generally it's about the same on seqs but faster on reduce

*Patch:* clj-1603-9.patch

*Screened by:*
Alex Miller made changes -
Description * with generative tests
* with perf examples

*Alternatives:*

There were a number of possible approaches for these enhancements:
1) Straight Java impl - see clj-1603-3.patch
2) Clojure deftype - see latest patch (most recent patch)
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. I also considered optionally allowing this but then it is tricky when in a reduce to determine which path to go down.

*Approach:* The first few versions of this patch (through clj-1603-3) used Java-based implementations. These have the benefit of improving the performance of both the seq and reduce paths at the expense of writing a bunch of Java. The latest patch uses a deftype based approach - 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 and a much smaller patch. This seems better.

A few things to note:
- Added repeat to title and implementation (seemed natural along with cycle)
- 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.
- I extended finite repeat to IReduce instead of IReduceInit as otherwise there would be a regression in the non-init path (we had one existing test where this failed).
- print-method is implemented for all of the new deftypes and print-dup is implemented for FiniteRepeat. print-dup doesn't seem to make sense on the other infinite length sequences.
- I added calls to ns-unmap the deftype constructor functions so they're not publicly visible
- the finite repeat has implementations for hashing and equality that just defer to seq semantics. the infinite seqs will do nothing useful (as there is nothing useful to do). considered deferring to seq semantics (infinite loop) or throwing an exception.

*Performance:*

Some example timing, all in µs:

|| Expression || 1.6.0 || 1.7.0-alpha5 || alpha5 + clj-1603-3 (Java) || alpha5 + clj-1603-9 (deftype) ||
| (doall (repeat 1000 1)) | 87 | 94 | 8 | 92 |
| (into [] (repeat 1000 1)) | 99 | 110 | 12 | 12 |
| (reduce + 0 (repeat 1000 1)) | 99 | 126 | 17 | 19 |
| (into [] (take 1000) (repeat 1)) | n/a | 67 | 35 | 29 |
| (doall (take 1000 (cycle [1 2 3]))) | 101 | 106 | 78 | 106 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 73 | 39 | 45 |
| (doall (take 1000 (iterate inc 0))) | 93 | 98 | 71 | 102 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 85 | 39 | 39 |

- clj-1603-3 is a Java class implementation - generally it's faster for both seqs and reduce (at the cost of more Java)
- clj-1603-9 is a deftype implementation - generally it's about the same on seqs but faster on reduce

*Patch:* clj-1603-9.patch

*Screened by:*
* with generative tests
* with perf examples

*Alternatives:*

There were a number of possible approaches for these enhancements:
1) Straight Java impl - see clj-1603-3.patch
2) Clojure deftype - see latest patch (most recent patch)
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. I also considered optionally allowing this but then it is tricky when in a reduce to determine which path to go down.

*Approach:* The first few versions of this patch (through clj-1603-3) used Java-based implementations. These have the benefit of improving the performance of both the seq and reduce paths at the expense of writing a bunch of Java. The latest patch uses a deftype based approach - 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 and a much smaller patch. This seems better.

A few things to note:
- Added repeat to title and implementation (seemed natural along with cycle)
- 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.
- I extended finite repeat to IReduce instead of IReduceInit as otherwise there would be a regression in the non-init path (we had one existing test where this failed).
- print-method is implemented for all of the new deftypes and print-dup is implemented for FiniteRepeat. print-dup doesn't seem to make sense on the other infinite length sequences.
- I added calls to ns-unmap the deftype constructor functions so they're not publicly visible
- the finite repeat has implementations for hashing and equality that just defer to seq semantics. the infinite seqs will do nothing useful (as there is nothing useful to do). considered deferring to seq semantics (infinite loop) or throwing an exception.

*Performance:*

Some example timing, all in µs:

|| Expression || 1.6.0 || 1.7.0-alpha5 || alpha5 + clj-1603-3 (Java) || alpha5 + clj-1603-10 (deftype) ||
| (doall (repeat 1000 1)) | 87 | 94 | 8 | 92 |
| (into [] (repeat 1000 1)) | 99 | 110 | 12 | 12 |
| (reduce + 0 (repeat 1000 1)) | 99 | 126 | 17 | 19 |
| (into [] (take 1000) (repeat 1)) | n/a | 67 | 35 | 29 |
| (doall (take 1000 (cycle [1 2 3]))) | 101 | 106 | 78 | 106 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 73 | 39 | 45 |
| (doall (take 1000 (iterate inc 0))) | 93 | 98 | 71 | 102 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 85 | 39 | 39 |

- clj-1603-3 is a Java class implementation - generally it's faster for both seqs and reduce (at the cost of more Java)
- clj-1603-10 is a deftype implementation - generally it's about the same on seqs but faster on reduce

*Patch:* clj-1603-10.patch

*Screened by:*
Attachment clj-1603-10.patch [ 13807 ]
Stuart Halloway made changes -
Approval Vetted [ 10003 ] Incomplete [ 10006 ]
Alex Miller made changes -
Attachment clj-1603-11.patch [ 13898 ]
Description * with generative tests
* with perf examples

*Alternatives:*

There were a number of possible approaches for these enhancements:
1) Straight Java impl - see clj-1603-3.patch
2) Clojure deftype - see latest patch (most recent patch)
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. I also considered optionally allowing this but then it is tricky when in a reduce to determine which path to go down.

*Approach:* The first few versions of this patch (through clj-1603-3) used Java-based implementations. These have the benefit of improving the performance of both the seq and reduce paths at the expense of writing a bunch of Java. The latest patch uses a deftype based approach - 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 and a much smaller patch. This seems better.

A few things to note:
- Added repeat to title and implementation (seemed natural along with cycle)
- 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.
- I extended finite repeat to IReduce instead of IReduceInit as otherwise there would be a regression in the non-init path (we had one existing test where this failed).
- print-method is implemented for all of the new deftypes and print-dup is implemented for FiniteRepeat. print-dup doesn't seem to make sense on the other infinite length sequences.
- I added calls to ns-unmap the deftype constructor functions so they're not publicly visible
- the finite repeat has implementations for hashing and equality that just defer to seq semantics. the infinite seqs will do nothing useful (as there is nothing useful to do). considered deferring to seq semantics (infinite loop) or throwing an exception.

*Performance:*

Some example timing, all in µs:

|| Expression || 1.6.0 || 1.7.0-alpha5 || alpha5 + clj-1603-3 (Java) || alpha5 + clj-1603-10 (deftype) ||
| (doall (repeat 1000 1)) | 87 | 94 | 8 | 92 |
| (into [] (repeat 1000 1)) | 99 | 110 | 12 | 12 |
| (reduce + 0 (repeat 1000 1)) | 99 | 126 | 17 | 19 |
| (into [] (take 1000) (repeat 1)) | n/a | 67 | 35 | 29 |
| (doall (take 1000 (cycle [1 2 3]))) | 101 | 106 | 78 | 106 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 73 | 39 | 45 |
| (doall (take 1000 (iterate inc 0))) | 93 | 98 | 71 | 102 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 85 | 39 | 39 |

- clj-1603-3 is a Java class implementation - generally it's faster for both seqs and reduce (at the cost of more Java)
- clj-1603-10 is a deftype implementation - generally it's about the same on seqs but faster on reduce

*Patch:* clj-1603-10.patch

*Screened by:*
* with generative tests
* with perf examples

*Alternatives:*

There were a number of possible approaches for these enhancements:
1) Straight Java impl - see clj-1603-3.patch
2) Clojure deftype - see latest patch (most recent patch)
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. I also considered optionally allowing this but then it is tricky when in a reduce to determine which path to go down.

*Approach:* The first few versions of this patch (through clj-1603-3) used Java-based implementations. These have the benefit of improving the performance of both the seq and reduce paths at the expense of writing a bunch of Java. The latest patch uses a deftype based approach - 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 and a much smaller patch. This seems better.

A few things to note:
- Added repeat to title and implementation (seemed natural along with cycle)
- 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.
- I extended finite repeat to IReduce instead of IReduceInit as otherwise there would be a regression in the non-init path (we had one existing test where this failed).
- print-method is implemented for all of the new deftypes and print-dup is implemented for FiniteRepeat. print-dup doesn't seem to make sense on the other infinite length sequences.
- I added calls to ns-unmap the deftype constructor functions so they're not publicly visible
- the finite repeat has implementations for hashing and equality that just defer to seq semantics. the infinite seqs will do nothing useful (as there is nothing useful to do). considered deferring to seq semantics (infinite loop) or throwing an exception.

*Performance:*

Some example timing, all in µs:

|| Expression || 1.6.0 || 1.7.0-alpha5 || alpha5 + clj-1603-3 (Java) || alpha5 + clj-1603-11 (deftype) ||
| (doall (repeat 1000 1)) | 87 | 94 | 8 | 92 |
| (into [] (repeat 1000 1)) | 99 | 110 | 12 | 12 |
| (reduce + 0 (repeat 1000 1)) | 99 | 126 | 17 | 19 |
| (into [] (take 1000) (repeat 1)) | n/a | 67 | 35 | 29 |
| (doall (take 1000 (cycle [1 2 3]))) | 101 | 106 | 78 | 106 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 73 | 39 | 45 |
| (doall (take 1000 (iterate inc 0))) | 93 | 98 | 71 | 102 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 85 | 39 | 39 |

- clj-1603-3 is a Java class implementation - generally it's faster for both seqs and reduce (at the cost of more Java)
- clj-1603-11 is a deftype implementation - generally it's about the same on seqs but faster on reduce

*Patch:* clj-1603-11.patch

*Screened by:*
Alex Miller made changes -
Attachment clj-1603-12.patch [ 13903 ]
Description * with generative tests
* with perf examples

*Alternatives:*

There were a number of possible approaches for these enhancements:
1) Straight Java impl - see clj-1603-3.patch
2) Clojure deftype - see latest patch (most recent patch)
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. I also considered optionally allowing this but then it is tricky when in a reduce to determine which path to go down.

*Approach:* The first few versions of this patch (through clj-1603-3) used Java-based implementations. These have the benefit of improving the performance of both the seq and reduce paths at the expense of writing a bunch of Java. The latest patch uses a deftype based approach - 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 and a much smaller patch. This seems better.

A few things to note:
- Added repeat to title and implementation (seemed natural along with cycle)
- 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.
- I extended finite repeat to IReduce instead of IReduceInit as otherwise there would be a regression in the non-init path (we had one existing test where this failed).
- print-method is implemented for all of the new deftypes and print-dup is implemented for FiniteRepeat. print-dup doesn't seem to make sense on the other infinite length sequences.
- I added calls to ns-unmap the deftype constructor functions so they're not publicly visible
- the finite repeat has implementations for hashing and equality that just defer to seq semantics. the infinite seqs will do nothing useful (as there is nothing useful to do). considered deferring to seq semantics (infinite loop) or throwing an exception.

*Performance:*

Some example timing, all in µs:

|| Expression || 1.6.0 || 1.7.0-alpha5 || alpha5 + clj-1603-3 (Java) || alpha5 + clj-1603-11 (deftype) ||
| (doall (repeat 1000 1)) | 87 | 94 | 8 | 92 |
| (into [] (repeat 1000 1)) | 99 | 110 | 12 | 12 |
| (reduce + 0 (repeat 1000 1)) | 99 | 126 | 17 | 19 |
| (into [] (take 1000) (repeat 1)) | n/a | 67 | 35 | 29 |
| (doall (take 1000 (cycle [1 2 3]))) | 101 | 106 | 78 | 106 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 73 | 39 | 45 |
| (doall (take 1000 (iterate inc 0))) | 93 | 98 | 71 | 102 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 85 | 39 | 39 |

- clj-1603-3 is a Java class implementation - generally it's faster for both seqs and reduce (at the cost of more Java)
- clj-1603-11 is a deftype implementation - generally it's about the same on seqs but faster on reduce

*Patch:* clj-1603-11.patch

*Screened by:*
* with generative tests
* with perf examples

*Alternatives:*

There were a number of possible approaches for these enhancements:
1) Straight Java impl - see clj-1603-3.patch
2) Clojure deftype - see latest patch (most recent patch)
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. I also considered optionally allowing this but then it is tricky when in a reduce to determine which path to go down.

*Approach:* The first few versions of this patch (through clj-1603-3) used Java-based implementations. These have the benefit of improving the performance of both the seq and reduce paths at the expense of writing a bunch of Java. The latest patch uses a deftype based approach - 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 and a much smaller patch. This seems better.

A few things to note:
- Added repeat to title and implementation (seemed natural along with cycle)
- 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.
- I extended finite repeat to IReduce instead of IReduceInit as otherwise there would be a regression in the non-init path (we had one existing test where this failed).
- print-method is implemented for all of the new deftypes and print-dup is implemented for FiniteRepeat. print-dup doesn't seem to make sense on the other infinite length sequences.
- I added calls to ns-unmap the deftype constructor functions so they're not publicly visible

*Performance:*

Some example timing, all in µs:

|| Expression || 1.6.0 || 1.7.0-alpha5 || alpha5 + clj-1603-3 (Java) || alpha5 + clj-1603-12 (deftype) ||
| (doall (repeat 1000 1)) | 87 | 94 | 8 | 92 |
| (into [] (repeat 1000 1)) | 99 | 110 | 12 | 12 |
| (reduce + 0 (repeat 1000 1)) | 99 | 126 | 17 | 19 |
| (into [] (take 1000) (repeat 1)) | n/a | 67 | 35 | 29 |
| (doall (take 1000 (cycle [1 2 3]))) | 101 | 106 | 78 | 106 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 73 | 39 | 45 |
| (doall (take 1000 (iterate inc 0))) | 93 | 98 | 71 | 102 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 85 | 39 | 39 |

- clj-1603-3 is a Java class implementation - generally it's faster for both seqs and reduce (at the cost of more Java)
- clj-1603-12 is a deftype implementation - generally it's about the same on seqs but faster on reduce

*Patch:* clj-1603-12.patch

*Screened by:*
Approval Incomplete [ 10006 ] Vetted [ 10003 ]
Alex Miller made changes -
Approval Vetted [ 10003 ] Incomplete [ 10006 ]
Alex Miller made changes -
Attachment clj-1603-13.patch [ 13908 ]
Description * with generative tests
* with perf examples

*Alternatives:*

There were a number of possible approaches for these enhancements:
1) Straight Java impl - see clj-1603-3.patch
2) Clojure deftype - see latest patch (most recent patch)
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. I also considered optionally allowing this but then it is tricky when in a reduce to determine which path to go down.

*Approach:* The first few versions of this patch (through clj-1603-3) used Java-based implementations. These have the benefit of improving the performance of both the seq and reduce paths at the expense of writing a bunch of Java. The latest patch uses a deftype based approach - 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 and a much smaller patch. This seems better.

A few things to note:
- Added repeat to title and implementation (seemed natural along with cycle)
- 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.
- I extended finite repeat to IReduce instead of IReduceInit as otherwise there would be a regression in the non-init path (we had one existing test where this failed).
- print-method is implemented for all of the new deftypes and print-dup is implemented for FiniteRepeat. print-dup doesn't seem to make sense on the other infinite length sequences.
- I added calls to ns-unmap the deftype constructor functions so they're not publicly visible

*Performance:*

Some example timing, all in µs:

|| Expression || 1.6.0 || 1.7.0-alpha5 || alpha5 + clj-1603-3 (Java) || alpha5 + clj-1603-12 (deftype) ||
| (doall (repeat 1000 1)) | 87 | 94 | 8 | 92 |
| (into [] (repeat 1000 1)) | 99 | 110 | 12 | 12 |
| (reduce + 0 (repeat 1000 1)) | 99 | 126 | 17 | 19 |
| (into [] (take 1000) (repeat 1)) | n/a | 67 | 35 | 29 |
| (doall (take 1000 (cycle [1 2 3]))) | 101 | 106 | 78 | 106 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 73 | 39 | 45 |
| (doall (take 1000 (iterate inc 0))) | 93 | 98 | 71 | 102 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 85 | 39 | 39 |

- clj-1603-3 is a Java class implementation - generally it's faster for both seqs and reduce (at the cost of more Java)
- clj-1603-12 is a deftype implementation - generally it's about the same on seqs but faster on reduce

*Patch:* clj-1603-12.patch

*Screened by:*
* with generative tests
* with perf examples

*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-3.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.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.
- I extended finite repeat to IReduce instead of just IReduceInit as otherwise there would be a regression in the non-init path (we had one existing test where this failed).

*Performance:*

Some example timing, all in µs:

|| Expression || 1.6.0 || 1.7.0-alpha5 || alpha5 + clj-1603-3 (Java) || alpha5 + clj-1603-12 (deftype) || alpha5 + clj-1603-13 (reducible-lazy-seq) ||
| (doall (repeat 1000 1)) | 87 | 94 | 8 | 92 | 89 |
| (into [] (repeat 1000 1)) | 99 | 110 | 12 | 12 | 14 |
| (reduce + 0 (repeat 1000 1)) | 99 | 126 | 17 | 19 | 22 |
| (into [] (take 1000) (repeat 1)) | n/a | 67 | 35 | 29 | 27 |
| (doall (take 1000 (cycle [1 2 3]))) | 101 | 106 | 78 | 106 | 111 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 73 | 39 | 45 | 43 |
| (doall (take 1000 (iterate inc 0))) | 93 | 98 | 71 | 102 | 112 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 85 | 39 | 39 | 40 |

- clj-1603-3 is a Java class implementation - generally it's faster for both seqs and reduce (at the cost of more Java)
- clj-1603-12 is a deftype implementation - generally it's about the same on seqs but faster on reduce
- clj-1603-13 is the LazySeq extension to IReduce - generally it's good but the iterate seq path introduces an extra lazy seq to force so it's slightly slower on that path.

*Patch:* clj-1603-13.patch

*Screened by:*
Approval Incomplete [ 10006 ] Vetted [ 10003 ]
Alex Miller made changes -
Attachment clj-1603-14.patch [ 13909 ]
Description * with generative tests
* with perf examples

*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-3.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.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.
- I extended finite repeat to IReduce instead of just IReduceInit as otherwise there would be a regression in the non-init path (we had one existing test where this failed).

*Performance:*

Some example timing, all in µs:

|| Expression || 1.6.0 || 1.7.0-alpha5 || alpha5 + clj-1603-3 (Java) || alpha5 + clj-1603-12 (deftype) || alpha5 + clj-1603-13 (reducible-lazy-seq) ||
| (doall (repeat 1000 1)) | 87 | 94 | 8 | 92 | 89 |
| (into [] (repeat 1000 1)) | 99 | 110 | 12 | 12 | 14 |
| (reduce + 0 (repeat 1000 1)) | 99 | 126 | 17 | 19 | 22 |
| (into [] (take 1000) (repeat 1)) | n/a | 67 | 35 | 29 | 27 |
| (doall (take 1000 (cycle [1 2 3]))) | 101 | 106 | 78 | 106 | 111 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 73 | 39 | 45 | 43 |
| (doall (take 1000 (iterate inc 0))) | 93 | 98 | 71 | 102 | 112 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 85 | 39 | 39 | 40 |

- clj-1603-3 is a Java class implementation - generally it's faster for both seqs and reduce (at the cost of more Java)
- clj-1603-12 is a deftype implementation - generally it's about the same on seqs but faster on reduce
- clj-1603-13 is the LazySeq extension to IReduce - generally it's good but the iterate seq path introduces an extra lazy seq to force so it's slightly slower on that path.

*Patch:* clj-1603-13.patch

*Screened by:*
*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-3.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.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 || alpha5 + clj-1603-3 (Java) || alpha5 + clj-1603-12 (deftype) || alpha5 + clj-1603-14 (split impl) ||
| (doall (repeat 1000 1)) | 87 | 94 | 8 | 92 | 91 |
| (into [] (repeat 1000 1)) | 99 | 110 | 12 | 12 | 14 |
| (reduce + 0 (repeat 1000 1)) | 99 | 126 | 17 | 19 | 22 |
| (into [] (take 1000) (repeat 1)) | n/a | 67 | 35 | 29 | 27 |
| (doall (take 1000 (cycle [1 2 3]))) | 101 | 106 | 78 | 106 | 111 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 73 | 39 | 45 | 43 |
| (doall (take 1000 (iterate inc 0))) | 93 | 98 | 71 | 102 | 112 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 85 | 39 | 39 | 38 |

- clj-1603-3 is a Java class implementation - generally it's faster for both seqs and reduce (at the cost of more Java)
- clj-1603-12 is a deftype implementation - generally it's about the same on seqs but faster on reduce
- clj-1603-14 is the LazySeq extension to IReduceInit - generally it's good but the iterate seq path introduces an extra lazy seq to force so it's slightly slower on that path.

*Patch:* clj-1603-14.patch

*Screened by:*
Alex Miller made changes -
Approval Vetted [ 10003 ] Incomplete [ 10006 ]
Alex Miller made changes -
Attachment clj-1603-12-2.patch [ 13959 ]
Attachment clj-1603-3-2.patch [ 13960 ]
Description *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-3.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.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 || alpha5 + clj-1603-3 (Java) || alpha5 + clj-1603-12 (deftype) || alpha5 + clj-1603-14 (split impl) ||
| (doall (repeat 1000 1)) | 87 | 94 | 8 | 92 | 91 |
| (into [] (repeat 1000 1)) | 99 | 110 | 12 | 12 | 14 |
| (reduce + 0 (repeat 1000 1)) | 99 | 126 | 17 | 19 | 22 |
| (into [] (take 1000) (repeat 1)) | n/a | 67 | 35 | 29 | 27 |
| (doall (take 1000 (cycle [1 2 3]))) | 101 | 106 | 78 | 106 | 111 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 73 | 39 | 45 | 43 |
| (doall (take 1000 (iterate inc 0))) | 93 | 98 | 71 | 102 | 112 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 85 | 39 | 39 | 38 |

- clj-1603-3 is a Java class implementation - generally it's faster for both seqs and reduce (at the cost of more Java)
- clj-1603-12 is a deftype implementation - generally it's about the same on seqs but faster on reduce
- clj-1603-14 is the LazySeq extension to IReduceInit - generally it's good but the iterate seq path introduces an extra lazy seq to force so it's slightly slower on that path.

*Patch:* clj-1603-14.patch

*Screened by:*
*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-3.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.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 || alpha5 + clj-1603-3-2 (Java) || alpha5 + clj-1603-12-2 (deftype) || alpha5 + clj-1603-14 (split impl) ||
| (doall (repeat 1000 1)) | 87 | 94 | 8 | 94 | 89 |
| (into [] (repeat 1000 1)) | 99 | 110 | 12 | 12 | 12 |
| (reduce + 0 (repeat 1000 1)) | 99 | 126 | 17 | 22 | 25 |
| (into [] (take 1000) (repeat 1)) | n/a | 67 | 35 | 33 | 27 |
| (doall (take 1000 (cycle [1 2 3]))) | 101 | 106 | 73 | 108 | 103 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 73 | 39 | 45 | 44 |
| (doall (take 1000 (iterate inc 0))) | 93 | 98 | 68 | 123 | 116 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 85 | 39 | 40 | 39 |

- clj-1603-3-2 is a Java class implementation - generally it's faster for both seqs and reduce (at the cost of more Java)
- clj-1603-12-2 is a deftype implementation - generally it's about the same on seqs but faster on reduce
- clj-1603-14 is the LazySeq extension to IReduceInit - generally it's good but the iterate seq path introduces an extra lazy seq to force so it's slightly slower on that path.

*Patch:* clj-1603-14.patch

*Screened by:*
Alex Miller made changes -
Description *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-3.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.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 || alpha5 + clj-1603-3-2 (Java) || alpha5 + clj-1603-12-2 (deftype) || alpha5 + clj-1603-14 (split impl) ||
| (doall (repeat 1000 1)) | 87 | 94 | 8 | 94 | 89 |
| (into [] (repeat 1000 1)) | 99 | 110 | 12 | 12 | 12 |
| (reduce + 0 (repeat 1000 1)) | 99 | 126 | 17 | 22 | 25 |
| (into [] (take 1000) (repeat 1)) | n/a | 67 | 35 | 33 | 27 |
| (doall (take 1000 (cycle [1 2 3]))) | 101 | 106 | 73 | 108 | 103 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 73 | 39 | 45 | 44 |
| (doall (take 1000 (iterate inc 0))) | 93 | 98 | 68 | 123 | 116 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 85 | 39 | 40 | 39 |

- clj-1603-3-2 is a Java class implementation - generally it's faster for both seqs and reduce (at the cost of more Java)
- clj-1603-12-2 is a deftype implementation - generally it's about the same on seqs but faster on reduce
- clj-1603-14 is the LazySeq extension to IReduceInit - generally it's good but the iterate seq path introduces an extra lazy seq to force so it's slightly slower on that path.

*Patch:* clj-1603-14.patch

*Screened by:*
*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-3-2.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 || alpha5 + clj-1603-3-2 (Java) || alpha5 + clj-1603-12-2 (deftype) || alpha5 + clj-1603-14 (split impl) ||
| (doall (repeat 1000 1)) | 87 | 94 | 8 | 94 | 89 |
| (into [] (repeat 1000 1)) | 99 | 110 | 12 | 12 | 12 |
| (reduce + 0 (repeat 1000 1)) | 99 | 126 | 17 | 22 | 25 |
| (into [] (take 1000) (repeat 1)) | n/a | 67 | 35 | 33 | 27 |
| (doall (take 1000 (cycle [1 2 3]))) | 101 | 106 | 73 | 108 | 103 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 73 | 39 | 45 | 44 |
| (doall (take 1000 (iterate inc 0))) | 93 | 98 | 68 | 123 | 116 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 85 | 39 | 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.
- 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:* clj-1603-14.patch

*Screened by:*
Alex Miller made changes -
Approval Incomplete [ 10006 ] Vetted [ 10003 ]
Alex Miller made changes -
Description *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-3-2.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 || alpha5 + clj-1603-3-2 (Java) || alpha5 + clj-1603-12-2 (deftype) || alpha5 + clj-1603-14 (split impl) ||
| (doall (repeat 1000 1)) | 87 | 94 | 8 | 94 | 89 |
| (into [] (repeat 1000 1)) | 99 | 110 | 12 | 12 | 12 |
| (reduce + 0 (repeat 1000 1)) | 99 | 126 | 17 | 22 | 25 |
| (into [] (take 1000) (repeat 1)) | n/a | 67 | 35 | 33 | 27 |
| (doall (take 1000 (cycle [1 2 3]))) | 101 | 106 | 73 | 108 | 103 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 73 | 39 | 45 | 44 |
| (doall (take 1000 (iterate inc 0))) | 93 | 98 | 68 | 123 | 116 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 85 | 39 | 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.
- 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:* clj-1603-14.patch

*Screened by:*
*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-3-2.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-3-2 (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 | 27 | 27 | 33 |
| (doall (repeat 1000 1)) | 87 | 94 | 8 | 94 | 89 |
| (into [] (repeat 1000 1)) | 99 | 110 | 12 | 12 | 12 |
| (reduce + 0 (repeat 1000 1)) | 99 | 126 | 17 | 22 | 25 |
| (into [] (take 1000) (repeat 1)) | n/a | 67 | 35 | 33 | 27 |
| (doall (take 1000 (cycle [1 2 3]))) | 101 | 106 | 73 | 108 | 103 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 73 | 39 | 45 | 44 |
| (doall (take 1000 (iterate inc 0))) | 93 | 98 | 68 | 123 | 116 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 85 | 39 | 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:* clj-1603-14.patch

*Screened by:*
Alex Miller made changes -
Attachment clj-1603-3-3.patch [ 13965 ]
Description *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-3-2.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-3-2 (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 | 27 | 27 | 33 |
| (doall (repeat 1000 1)) | 87 | 94 | 8 | 94 | 89 |
| (into [] (repeat 1000 1)) | 99 | 110 | 12 | 12 | 12 |
| (reduce + 0 (repeat 1000 1)) | 99 | 126 | 17 | 22 | 25 |
| (into [] (take 1000) (repeat 1)) | n/a | 67 | 35 | 33 | 27 |
| (doall (take 1000 (cycle [1 2 3]))) | 101 | 106 | 73 | 108 | 103 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 73 | 39 | 45 | 44 |
| (doall (take 1000 (iterate inc 0))) | 93 | 98 | 68 | 123 | 116 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 85 | 39 | 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:* clj-1603-14.patch

*Screened by:*
*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-3-3.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-3-3 (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 | 27 | 27 | 33 |
| (doall (repeat 1000 1)) | 87 | 94 | 8 | 94 | 89 |
| (into [] (repeat 1000 1)) | 99 | 110 | 12 | 12 | 12 |
| (reduce + 0 (repeat 1000 1)) | 99 | 126 | 17 | 22 | 25 |
| (into [] (take 1000) (repeat 1)) | n/a | 67 | 35 | 33 | 27 |
| (doall (take 1000 (cycle [1 2 3]))) | 101 | 106 | 73 | 108 | 103 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 73 | 39 | 45 | 44 |
| (doall (take 1000 (iterate inc 0))) | 93 | 98 | 68 | 123 | 116 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 85 | 39 | 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-3-3.patch - for the Java version (NOTE: -3-3, *not* -3)
- 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-3-3.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.

*Screened by:*
Alex Miller made changes -
Assignee Stuart Halloway [ stu ]
Stuart Halloway made changes -
Description *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-3-3.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-3-3 (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 | 27 | 27 | 33 |
| (doall (repeat 1000 1)) | 87 | 94 | 8 | 94 | 89 |
| (into [] (repeat 1000 1)) | 99 | 110 | 12 | 12 | 12 |
| (reduce + 0 (repeat 1000 1)) | 99 | 126 | 17 | 22 | 25 |
| (into [] (take 1000) (repeat 1)) | n/a | 67 | 35 | 33 | 27 |
| (doall (take 1000 (cycle [1 2 3]))) | 101 | 106 | 73 | 108 | 103 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 73 | 39 | 45 | 44 |
| (doall (take 1000 (iterate inc 0))) | 93 | 98 | 68 | 123 | 116 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 85 | 39 | 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-3-3.patch - for the Java version (NOTE: -3-3, *not* -3)
- 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-3-3.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.

*Screened by:*
*Screened*

clj-1603-3-3.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-3-3.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-3-3 (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 | 27 | 27 | 33 |
| (doall (repeat 1000 1)) | 87 | 94 | 8 | 94 | 89 |
| (into [] (repeat 1000 1)) | 99 | 110 | 12 | 12 | 12 |
| (reduce + 0 (repeat 1000 1)) | 99 | 126 | 17 | 22 | 25 |
| (into [] (take 1000) (repeat 1)) | n/a | 67 | 35 | 33 | 27 |
| (doall (take 1000 (cycle [1 2 3]))) | 101 | 106 | 73 | 108 | 103 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 73 | 39 | 45 | 44 |
| (doall (take 1000 (iterate inc 0))) | 93 | 98 | 68 | 123 | 116 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 85 | 39 | 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-3-3.patch - for the Java version (NOTE: -3-3, *not* -3)
- 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-3-3.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.

*Screened by:*
Approval Vetted [ 10003 ] Screened [ 10004 ]
Nicola Mometto made changes -
Attachment clj-1603-3-4.patch [ 13985 ]
Alex Miller made changes -
Attachment clj-1603-15.patch [ 13986 ]
Description *Screened*

clj-1603-3-3.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-3-3.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-3-3 (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 | 27 | 27 | 33 |
| (doall (repeat 1000 1)) | 87 | 94 | 8 | 94 | 89 |
| (into [] (repeat 1000 1)) | 99 | 110 | 12 | 12 | 12 |
| (reduce + 0 (repeat 1000 1)) | 99 | 126 | 17 | 22 | 25 |
| (into [] (take 1000) (repeat 1)) | n/a | 67 | 35 | 33 | 27 |
| (doall (take 1000 (cycle [1 2 3]))) | 101 | 106 | 73 | 108 | 103 |
| (into [] (take 1000) (cycle [1 2 3])) | n/a | 73 | 39 | 45 | 44 |
| (doall (take 1000 (iterate inc 0))) | 93 | 98 | 68 | 123 | 116 |
| (into [] (take 1000) (iterate inc 0)) | n/a | 85 | 39 | 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-3-3.patch - for the Java version (NOTE: -3-3, *not* -3)
- 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-3-3.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.

*Screened by:*
*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-3-3.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.

Approval Screened [ 10004 ] Vetted [ 10003 ]
Alex Miller made changes -
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-3-3.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.

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

Alex Miller made changes -
Attachment clj-1603-15.patch [ 13986 ]
Alex Miller made changes -
Attachment clj-1603-15.patch [ 13996 ]
Stuart Halloway made changes -
Approval Vetted [ 10003 ] Screened [ 10004 ]
Rich Hickey made changes -
Approval Screened [ 10004 ] Ok [ 10007 ]
Stuart Halloway made changes -
Status Open [ 1 ] Closed [ 6 ]
Resolution Completed [ 1 ]

People

Vote (0)
Watch (3)

Dates

  • Created:
    Updated:
    Resolved: