Details
-
Type:
Enhancement
-
Status:
Closed
-
Priority:
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.
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.