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

Activity

Hide
Ghadi Shayban added a comment -

Stu, do you intend these to be in Java or Clojure? It could be trickier to implement in Clojure directly, as loading would have to be deferred until core_deftype loads. It's certainly tractable without breaking any backwards compatibility, and I've explored this while experimenting with Range as a deftype https://github.com/ghadishayban/clojure/commit/906cd6ed4d7c624dc4e553373dabfd57550eeff2

A macro to help with Seq&List participation could be certainly useful, as efficiently being both a Seq/List and IReduceInit isn't a party.

May be useful to list requirements for protocol/iface participation.

It seems like 'repeatedly' is another missing link in the IReduceInit story.

Rich mentioned the future integration of reduce-kv at the conj, it would also be useful to know how that could fit in.

---- Other concerns and ops that may belong better on the mailing list ----

In experimenting with more reducible sources, I put out a tiny repo (github.com/ghadishayban/reducers) a couple weeks ago that includes some sources and operations. The sources were CollReduce and not ISeq.

Relatedly, caching the hashcode as a Java `transient` field is not supported when implementing a collection using deftype (patch w/ test in CLJ-1573).

Sources:
Iterate was one of them https://github.com/ghadishayban/reducers/blob/master/src/ghadi/reducers.clj#L43-L51
Repeatedly https://github.com/ghadishayban/reducers/blob/master/src/ghadi/reducers.clj#L43-L51

Reduce/transduce-based Operations that accept transducers:
some, any, yield-first https://github.com/ghadishayban/reducers/blob/master/src/ghadi/reducers.clj#L52-L80
(any could use a better name, equiv to (first (filter...)))
some and any have a symmetry like filter/remove.

Novelty maybe for 1.8:
A transducible context for Iterables similar to LazyTransformer:
https://github.com/ghadishayban/reducers/blob/master/src/ghadi/reducers.clj#L157-L161

The unless-reduced macro was very useful in implementing the collections:
https://github.com/ghadishayban/reducers/blob/master/src/ghadi/reducers.clj#L7-L15
It is different than the ensure-reduced and unreduced functions in core.

Show
Ghadi Shayban added a comment - Stu, do you intend these to be in Java or Clojure? It could be trickier to implement in Clojure directly, as loading would have to be deferred until core_deftype loads. It's certainly tractable without breaking any backwards compatibility, and I've explored this while experimenting with Range as a deftype https://github.com/ghadishayban/clojure/commit/906cd6ed4d7c624dc4e553373dabfd57550eeff2 A macro to help with Seq&List participation could be certainly useful, as efficiently being both a Seq/List and IReduceInit isn't a party. May be useful to list requirements for protocol/iface participation. It seems like 'repeatedly' is another missing link in the IReduceInit story. Rich mentioned the future integration of reduce-kv at the conj, it would also be useful to know how that could fit in. ---- Other concerns and ops that may belong better on the mailing list ---- In experimenting with more reducible sources, I put out a tiny repo (github.com/ghadishayban/reducers) a couple weeks ago that includes some sources and operations. The sources were CollReduce and not ISeq. Relatedly, caching the hashcode as a Java `transient` field is not supported when implementing a collection using deftype (patch w/ test in CLJ-1573). Sources: Iterate was one of them https://github.com/ghadishayban/reducers/blob/master/src/ghadi/reducers.clj#L43-L51 Repeatedly https://github.com/ghadishayban/reducers/blob/master/src/ghadi/reducers.clj#L43-L51 Reduce/transduce-based Operations that accept transducers: some, any, yield-first https://github.com/ghadishayban/reducers/blob/master/src/ghadi/reducers.clj#L52-L80 (any could use a better name, equiv to (first (filter...))) some and any have a symmetry like filter/remove. Novelty maybe for 1.8: A transducible context for Iterables similar to LazyTransformer: https://github.com/ghadishayban/reducers/blob/master/src/ghadi/reducers.clj#L157-L161 The unless-reduced macro was very useful in implementing the collections: https://github.com/ghadishayban/reducers/blob/master/src/ghadi/reducers.clj#L7-L15 It is different than the ensure-reduced and unreduced functions in core.
Hide
Alex Miller added a comment -

When we discussed this in the past, it was in the vein of reusing some of the range work (in Java) to implement cycle and iterate (per CLJ-1515).

Show
Alex Miller added a comment - When we discussed this in the past, it was in the vein of reusing some of the range work (in Java) to implement cycle and iterate (per CLJ-1515).
Hide
Ghadi Shayban added a comment -

Never mind about 'repeatedly'. Being both ISeq and IReduceInit for repeatedly doesn't make sense for something that relies on side-effects. Current users of repeatedly can reduce over it many times and only realize the elements once.

Show
Ghadi Shayban added a comment - Never mind about 'repeatedly'. Being both ISeq and IReduceInit for repeatedly doesn't make sense for something that relies on side-effects. Current users of repeatedly can reduce over it many times and only realize the elements once.
Hide
Alex Miller added a comment -

attached wip Java impl and posted some example timings

Show
Alex Miller added a comment - attached wip Java impl and posted some example timings
Hide
Ghadi Shayban added a comment -

NB iterate in this patch does not cache the realized ISeq, but recalcs it at every call to realize the tail. This is not a change in the promised behavior (docstring says "f must be side-effect free") but an implementation change, as worth noting in the changelog.

Show
Ghadi Shayban added a comment - NB iterate in this patch does not cache the realized ISeq, but recalcs it at every call to realize the tail. This is not a change in the promised behavior (docstring says "f must be side-effect free") but an implementation change, as worth noting in the changelog.
Hide
Stuart Halloway added a comment - - edited

It looks like all the reduce with no inital value paths are still seq-y, and slower, as shown by e.g.

(dotimes [_ 10]
  (time
   (reduce
    +
    (repeat 10000000 1))))

(dotimes [_ 20]
  (time
   (reduce
    +
    0
    (repeat 10000000 1))))
Show
Stuart Halloway added a comment - - edited It looks like all the reduce with no inital value paths are still seq-y, and slower, as shown by e.g.
(dotimes [_ 10]
  (time
   (reduce
    +
    (repeat 10000000 1))))

(dotimes [_ 20]
  (time
   (reduce
    +
    0
    (repeat 10000000 1))))
Hide
Alex Miller added a comment -

On that example in master before / after patch I see:

before:

  • no init = 844 ms
  • with init = 920 ms

after:

  • no init = 124 ms
  • with init = 90 ms

Is that similar to what you see or not?

Show
Alex Miller added a comment - On that example in master before / after patch I see: before:
  • no init = 844 ms
  • with init = 920 ms
after:
  • no init = 124 ms
  • with init = 90 ms
Is that similar to what you see or not?
Hide
Alex Miller added a comment -

The clj-1603-3.patch has been updated to use effectively the same algorithm for both versions of reduce. With the -3 patch, I got ~96 ms on both examples in the prior comment. I re-ran the tests in the description and updated those as well (about the same as expected).

Show
Alex Miller added a comment - The clj-1603-3.patch has been updated to use effectively the same algorithm for both versions of reduce. With the -3 patch, I got ~96 ms on both examples in the prior comment. I re-ran the tests in the description and updated those as well (about the same as expected).
Hide
Stuart Halloway added a comment -

The tests do not seem to hit the unseeded reduce branches – do we even want these branches? The original ticket was for IReduceInit.

Show
Stuart Halloway added a comment - The tests do not seem to hit the unseeded reduce branches – do we even want these branches? The original ticket was for IReduceInit.
Hide
Michael Blume added a comment -

Probably worth noting – Git will happily apply the latest patch for CLJ-1603 on top of the latest patch for CLJ-1515, but the result does not compile because 1515 uses iterate and 1603 moves the definition of iterate lower in clojure.core. Not sure if this is worth fixing now or just noting for when they're actually applied.

Show
Michael Blume added a comment - Probably worth noting – Git will happily apply the latest patch for CLJ-1603 on top of the latest patch for CLJ-1515, but the result does not compile because 1515 uses iterate and 1603 moves the definition of iterate lower in clojure.core. Not sure if this is worth fixing now or just noting for when they're actually applied.
Hide
Michael Blume added a comment -

Actually, here, this just moves the declare statement further up the file.

Show
Michael Blume added a comment - Actually, here, this just moves the declare statement further up the file.
Hide
Michael Blume added a comment -

OK, no, the two patches are still incompatible even with the declaration order fixed:

[java] ERROR in (test-range) (LongRange.java:95)
     [java] expected: (= (take 3 (range 3 9 0)) (quote (3 3 3)))
     [java]   actual: java.lang.ClassCastException: clojure.core.InfiniteRepeat cannot be cast to clojure.lang.ISeq
     [java]  at clojure.lang.LongRange.create (LongRange.java:95)
Show
Michael Blume added a comment - OK, no, the two patches are still incompatible even with the declaration order fixed:
[java] ERROR in (test-range) (LongRange.java:95)
     [java] expected: (= (take 3 (range 3 9 0)) (quote (3 3 3)))
     [java]   actual: java.lang.ClassCastException: clojure.core.InfiniteRepeat cannot be cast to clojure.lang.ISeq
     [java]  at clojure.lang.LongRange.create (LongRange.java:95)
Hide
Alex Miller added a comment -

The 1515 patch is actually being reworked right now - we will patch things up at application time if needed.

Show
Alex Miller added a comment - The 1515 patch is actually being reworked right now - we will patch things up at application time if needed.
Hide
Alex Miller added a comment -

Removing screened marking so can be re-screened. Added new -7 patch that handles print-method, print-dup, and unmapping the deftype constructors so they're not visible. Thanks to Ghadi in CLJ-1515 for the idea on those.

Show
Alex Miller added a comment - Removing screened marking so can be re-screened. Added new -7 patch that handles print-method, print-dup, and unmapping the deftype constructors so they're not visible. Thanks to Ghadi in CLJ-1515 for the idea on those.
Hide
Ghadi Shayban added a comment -

Review of -7 patch:

Seqable/seq implementations that return a separate ISeq like these do should forward a call to seq on the result, like eduction does. [1] (This is not necessary in these particular impls, as the LazySeqs returned are themselves ISeqs. Also because Cycle's deftype is only constructed for non-empty cycles, the fact that there is a guaranteed seq is implicit. Probably a best practice to add an innocuous seq call if users look to these impls as a recipe.)

The performance regression in (doall (repeat 1000 1)) should go away completely with the dorun tweak in CLJ-1515. This is because dorun is effectively calling seq twice (it calls seq, throws away the result, then calls next.)

minor nits
1) repeat1 seems to be identical to repeat-seq and has both arities necessary for the deftypes
2) inside FiniteRepeat s/(> i 0)/(pos? i) also inside the repeat constructor
3) some things are defn- , some are ^:private
4) Cycle/reduce the recur binding can be (recur rr (or (next s) coll)) rather than nil? check

[1] https://github.com/clojure/clojure/blob/master/src/clj/clojure/core.clj#L7324

Show
Ghadi Shayban added a comment - Review of -7 patch: Seqable/seq implementations that return a separate ISeq like these do should forward a call to seq on the result, like eduction does. [1] (This is not necessary in these particular impls, as the LazySeqs returned are themselves ISeqs. Also because Cycle's deftype is only constructed for non-empty cycles, the fact that there is a guaranteed seq is implicit. Probably a best practice to add an innocuous seq call if users look to these impls as a recipe.) The performance regression in (doall (repeat 1000 1)) should go away completely with the dorun tweak in CLJ-1515. This is because dorun is effectively calling seq twice (it calls seq, throws away the result, then calls next.) minor nits 1) repeat1 seems to be identical to repeat-seq and has both arities necessary for the deftypes 2) inside FiniteRepeat s/(> i 0)/(pos? i) also inside the repeat constructor 3) some things are defn- , some are ^:private 4) Cycle/reduce the recur binding can be (recur rr (or (next s) coll)) rather than nil? check [1] https://github.com/clojure/clojure/blob/master/src/clj/clojure/core.clj#L7324
Hide
Alex Miller added a comment -

Ghadi - good comments! Fixed 1,2,4. #3 - ^:private is because defn- is not yet defined. New -8 patch.

Show
Alex Miller added a comment - Ghadi - good comments! Fixed 1,2,4. #3 - ^:private is because defn- is not yet defined. New -8 patch.
Hide
Alex Miller added a comment -

Bah.

user=> (= (repeat 5 :a) (repeat 5 :a))
false
Show
Alex Miller added a comment - Bah.
user=> (= (repeat 5 :a) (repeat 5 :a))
false
Hide
Alex Miller added a comment -

Updated to -9 patch that handles hash and equality for finite repeat case.

Show
Alex Miller added a comment - Updated to -9 patch that handles hash and equality for finite repeat case.
Hide
Ghadi Shayban added a comment -

metadata in the wrong place on #'repeat1

Show
Ghadi Shayban added a comment - metadata in the wrong place on #'repeat1
Hide
Alex Miller added a comment -

Thanks, fixed in -10.

Show
Alex Miller added a comment - Thanks, fixed in -10.
Hide
Stuart Halloway added a comment -

The collections returned by these APIs promise several things the new deftypes do not deliver. For example, 1.6's repeat currently has the following ancestors that are lost in the propopsed deftype:

  • clojure.lang.ISeq
  • java.io.Serializable
  • clojure.lang.IPending
  • java.util.Collection
  • java.util.List
  • java.lang.Iterable
  • clojure.lang.Obj
  • clojure.lang.IPersistentCollection
  • clojure.lang.IMeta
  • clojure.lang.IObj

Losing metadata and serializability are certainly regressions, other stuff maybe as well. I suspect similar problems in all the other API returns.

We could improve testing by taking advantage of the property-checking fns already in test-clojure/data-structures, e.g. is-same-collection

Show
Stuart Halloway added a comment - The collections returned by these APIs promise several things the new deftypes do not deliver. For example, 1.6's repeat currently has the following ancestors that are lost in the propopsed deftype:
  • clojure.lang.ISeq
  • java.io.Serializable
  • clojure.lang.IPending
  • java.util.Collection
  • java.util.List
  • java.lang.Iterable
  • clojure.lang.Obj
  • clojure.lang.IPersistentCollection
  • clojure.lang.IMeta
  • clojure.lang.IObj
Losing metadata and serializability are certainly regressions, other stuff maybe as well. I suspect similar problems in all the other API returns. We could improve testing by taking advantage of the property-checking fns already in test-clojure/data-structures, e.g. is-same-collection
Hide
Alex Miller added a comment -

I think we should consider carefully what is contractually required by the return of repeat. My opinion is that repeat must return something seqable, not literally a seq (or lazy seq). With that perspective, ISeq, IPending (there re lazy seq laziness), Collection, List, Iterable, and IPersistentCollection are non-essential. Obj is a concrete class and we shouldn't commit to that.

  • IObj is a gap, this should work but doesn't: (with-meta (repeat 1 :a) {:a 1})
  • IMeta doesn't need to be added, will never have meta right now and meta handles this correctly
  • Serializable - doesn't make sense for the infinite seqs but should probably fix for finite range
Show
Alex Miller added a comment - I think we should consider carefully what is contractually required by the return of repeat. My opinion is that repeat must return something seqable, not literally a seq (or lazy seq). With that perspective, ISeq, IPending (there re lazy seq laziness), Collection, List, Iterable, and IPersistentCollection are non-essential. Obj is a concrete class and we shouldn't commit to that.
  • IObj is a gap, this should work but doesn't: (with-meta (repeat 1 :a) {:a 1})
  • IMeta doesn't need to be added, will never have meta right now and meta handles this correctly
  • Serializable - doesn't make sense for the infinite seqs but should probably fix for finite range
Hide
Alex Miller added a comment -

Added -11 patch that adds IObj for all the new deftypes and Serializable for FiniteRepeat. Still need to add more tests.

Show
Alex Miller added a comment - Added -11 patch that adds IObj for all the new deftypes and Serializable for FiniteRepeat. Still need to add more tests.
Hide
Stuart Halloway added a comment - - edited

I think all the java. interfaces are mandatory for interop. Leaving out any one of the clojure. interfaces creates observable change in behavior composing with other core fns (admittedly the IPending case would be bizarre, who uses that?), so those seem mandatory too.

Agreed Obj should be irrelevant, and if it isn't the bug is elsewhere.

Show
Stuart Halloway added a comment - - edited I think all the java. interfaces are mandatory for interop. Leaving out any one of the clojure. interfaces creates observable change in behavior composing with other core fns (admittedly the IPending case would be bizarre, who uses that?), so those seem mandatory too. Agreed Obj should be irrelevant, and if it isn't the bug is elsewhere.
Hide
Alex Miller added a comment -

pending further discussion w/ stu

Show
Alex Miller added a comment - pending further discussion w/ stu
Hide
Alex Miller added a comment -

for a clean run and more explanation of the perf numbers

Show
Alex Miller added a comment - for a clean run and more explanation of the perf numbers
Hide
Alex Miller added a comment -

refreshed numbers in table

Show
Alex Miller added a comment - refreshed numbers in table
Hide
Alex Miller added a comment -

Refreshed perf numbers and older patch variants, added some more explanation of the perf numbers for comparison.

Show
Alex Miller added a comment - Refreshed perf numbers and older patch variants, added some more explanation of the perf numbers for comparison.
Hide
Stuart Halloway added a comment -

Screened clj-1603-3-3.patch

Show
Stuart Halloway added a comment - Screened clj-1603-3-3.patch
Hide
Nicola Mometto added a comment -

Shouldn't iterate cache its next slot? the current implementation recalculates it every time:

user=> (def coll (iterate #(do (println %) (inc %)) 0))
#'user/coll
user=> (nth coll 3)
0
1
2
3
user=> (nth coll 3)
0
1
2
3

I realize the docstring for iterate explicitely warns that f must be side-effect free but this is just for demonstration purposes, imagine that f is a computationally-heavy function and you'll understand why I don't think the new proposed behaviour is desiderable.

Show
Nicola Mometto added a comment - Shouldn't iterate cache its next slot? the current implementation recalculates it every time:
user=> (def coll (iterate #(do (println %) (inc %)) 0))
#'user/coll
user=> (nth coll 3)
0
1
2
3
user=> (nth coll 3)
0
1
2
3
I realize the docstring for iterate explicitely warns that f must be side-effect free but this is just for demonstration purposes, imagine that f is a computationally-heavy function and you'll understand why I don't think the new proposed behaviour is desiderable.
Hide
Nicola Mometto added a comment -

I attached clj-1603-3-4.patch which is the same as clj-1603-3-3.patch except it caches the next slot of iterate.

Here is the diff between -3-3 and -3-4 for ease of review:

diff --git a/src/jvm/clojure/lang/Iterate.java b/src/jvm/clojure/lang/Iterate.java
index f23ddca..aeef998 100644
--- a/src/jvm/clojure/lang/Iterate.java
+++ b/src/jvm/clojure/lang/Iterate.java
@@ -16,6 +16,7 @@ public class Iterate extends ASeq implements IReduce {
 
 private final IFn f;      // never null
 private final Object seed;
+private volatile ISeq _next;
 
 private Iterate(IFn f, Object seed){
     this.f = f;
@@ -37,7 +38,14 @@ public Object first(){
 }
 
 public ISeq next(){
-    return new Iterate(f, f.invoke(seed));
+    ISeq ret = _next;
+    if (ret == null)
+        synchronized(this) {
+            ret = _next;
+            if (ret == null)
+                _next = ret = new Iterate(f, f.invoke(seed));
+        }
+    return ret;
 }
 
 public Iterate withMeta(IPersistentMap meta){
Show
Nicola Mometto added a comment - I attached clj-1603-3-4.patch which is the same as clj-1603-3-3.patch except it caches the next slot of iterate. Here is the diff between -3-3 and -3-4 for ease of review:
diff --git a/src/jvm/clojure/lang/Iterate.java b/src/jvm/clojure/lang/Iterate.java
index f23ddca..aeef998 100644
--- a/src/jvm/clojure/lang/Iterate.java
+++ b/src/jvm/clojure/lang/Iterate.java
@@ -16,6 +16,7 @@ public class Iterate extends ASeq implements IReduce {
 
 private final IFn f;      // never null
 private final Object seed;
+private volatile ISeq _next;
 
 private Iterate(IFn f, Object seed){
     this.f = f;
@@ -37,7 +38,14 @@ public Object first(){
 }
 
 public ISeq next(){
-    return new Iterate(f, f.invoke(seed));
+    ISeq ret = _next;
+    if (ret == null)
+        synchronized(this) {
+            ret = _next;
+            if (ret == null)
+                _next = ret = new Iterate(f, f.invoke(seed));
+        }
+    return ret;
 }
 
 public Iterate withMeta(IPersistentMap meta){
Hide
Alex Miller added a comment -

It's a good question. That impl kills all of the performance improvement for iterate on the seq use case (prob the current common case). I'll take a look at it though.

Show
Alex Miller added a comment - It's a good question. That impl kills all of the performance improvement for iterate on the seq use case (prob the current common case). I'll take a look at it though.
Hide
Nicola Mometto added a comment -

My opinion is that the performance improvement for iterate that the benchmark shows won't reflect a real performance improvement in "real" usage cases of iterate where `f` actually does some computation

Show
Nicola Mometto added a comment - My opinion is that the performance improvement for iterate that the benchmark shows won't reflect a real performance improvement in "real" usage cases of iterate where `f` actually does some computation
Hide
Nicola Mometto added a comment -

This is also true for its reduce impl btw.
I'm sorry if I'm pointing this out late in the life of this ticket but it never occurred to me that, contrary to cycle, repeat or range (CLJ-1515), this change for iterate will possibly make accessing large sequences slower since we lose the caching aspect of lazy-seqs.

Show
Nicola Mometto added a comment - This is also true for its reduce impl btw. I'm sorry if I'm pointing this out late in the life of this ticket but it never occurred to me that, contrary to cycle, repeat or range (CLJ-1515), this change for iterate will possibly make accessing large sequences slower since we lose the caching aspect of lazy-seqs.
Hide
Alex Miller added a comment -

Added new -15 patch, which is the same as -3-3 but caches _next for all three types. This has no impact on the reduce performance and was 2-8 us slower in the timings for the seqs above. That seems like a small hit for the reduction in perf and memory on all cases where the seq is traversed multiple times. That seems like a reasonably common thing to do, particularly for finite repeat.

Show
Alex Miller added a comment - Added new -15 patch, which is the same as -3-3 but caches _next for all three types. This has no impact on the reduce performance and was 2-8 us slower in the timings for the seqs above. That seems like a small hit for the reduction in perf and memory on all cases where the seq is traversed multiple times. That seems like a reasonably common thing to do, particularly for finite repeat.
Hide
Alex Miller added a comment -

Stu - the only change in -15 vs -3-3 is in the next() methods of each new type. Each has a new "private volatile ISeq _next;"

Cycle:

public ISeq next(){
    if(_next == null) {
        ISeq next = current.next();
        if (next != null)
            _next = new Cycle(all, next);
        else
            _next = new Cycle(all, all);
    }
    return _next;
}

Iterate:

public ISeq next(){
    if(_next == null) {
        _next = new Iterate(f, f.invoke(seed));
    }
    return _next;
}

Repeat:

public ISeq next() {
    if(_next == null) {
        if(count > 1)
            _next = new Repeat(count - 1, val);
        else if(count == INFINITE)
            _next = this;
    }
    return _next;
}
Show
Alex Miller added a comment - Stu - the only change in -15 vs -3-3 is in the next() methods of each new type. Each has a new "private volatile ISeq _next;" Cycle:
public ISeq next(){
    if(_next == null) {
        ISeq next = current.next();
        if (next != null)
            _next = new Cycle(all, next);
        else
            _next = new Cycle(all, all);
    }
    return _next;
}
Iterate:
public ISeq next(){
    if(_next == null) {
        _next = new Iterate(f, f.invoke(seed));
    }
    return _next;
}
Repeat:
public ISeq next() {
    if(_next == null) {
        if(count > 1)
            _next = new Repeat(count - 1, val);
        else if(count == INFINITE)
            _next = this;
    }
    return _next;
}
Hide
Michael Blume added a comment - - edited

For Cycle, would it be worth holding the head and linking back to it when we loop, so that the underlying sequence only has to be traversed once? Something like this

https://github.com/MichaelBlume/clojure/commit/cache-cycle-head

On my machine this saves about 10 microseconds on

(doall (take 1000 (cycle [1 2 3])))

Show
Michael Blume added a comment - - edited For Cycle, would it be worth holding the head and linking back to it when we loop, so that the underlying sequence only has to be traversed once? Something like this https://github.com/MichaelBlume/clojure/commit/cache-cycle-head On my machine this saves about 10 microseconds on
(doall (take 1000 (cycle [1 2 3])))
Hide
Michael Blume added a comment -

Also, for the Cycle reduce implementations, it might make sense to assume the underlying sequence is going to be traversed many times, copy it into an array, and loop over it with an index.

Show
Michael Blume added a comment - Also, for the Cycle reduce implementations, it might make sense to assume the underlying sequence is going to be traversed many times, copy it into an array, and loop over it with an index.
Hide
Alex Miller added a comment -

The problem with holding a pointer back to the head is that the intervening cycle can be arbitrarily large. You are then literally holding the head on an arbitrary size seq. A silly example that fails with the patch but works without it (depending on your jvm size):

(dorun (take 10000000 (cycle (range 10000000))))

I played with the cycle reduce too but it has the same effective potential issue of creating and holding an arbitrarily sized array. Actually this one is worse in that it realizes an arbitrarily large array before knowing how many inputs it will need - it could be a take 1. Also, things that formerly worked could blow up with an oome. What if someone relies on passing an infinite sequence to cycle in a fallthrough case? For example, this works with the current version but would blow up with the array.

(into [] (take 1000) (cycle (iterate inc 0)))

Neither of these seem worth the risk to me.

Show
Alex Miller added a comment - The problem with holding a pointer back to the head is that the intervening cycle can be arbitrarily large. You are then literally holding the head on an arbitrary size seq. A silly example that fails with the patch but works without it (depending on your jvm size):
(dorun (take 10000000 (cycle (range 10000000))))
I played with the cycle reduce too but it has the same effective potential issue of creating and holding an arbitrarily sized array. Actually this one is worse in that it realizes an arbitrarily large array before knowing how many inputs it will need - it could be a take 1. Also, things that formerly worked could blow up with an oome. What if someone relies on passing an infinite sequence to cycle in a fallthrough case? For example, this works with the current version but would blow up with the array.
(into [] (take 1000) (cycle (iterate inc 0)))
Neither of these seem worth the risk to me.
Hide
Michael Blume added a comment -

Yeah, fair enough.

Show
Michael Blume added a comment - Yeah, fair enough.
Hide
Alex Miller added a comment -

updated version of the -15 patch that gives proper credit to Ghadi for part.

Show
Alex Miller added a comment - updated version of the -15 patch that gives proper credit to Ghadi for part.

People

Vote (0)
Watch (3)

Dates

  • Created:
    Updated:
    Resolved: