Clojure

Replace seq-based iterators with direct iterators for all non-seq collections that use SeqIterator

Details

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

Description

Motivation:

Currently, the process of reducing over a map or set involves converting them to seqs. This action thus causes more intermediate objects than we'd like. Therefore, we'd like for reduce to be more efficient about the way that it reduces over these types. One way is for reduction to use the types' core collections while another way is to instead use a smart iterator type that abstracts the direct operation.

Solution

Add support for direct iterators instead of seq-based iterators for non-seq collections that use SeqIterator.

Patch adds support for direct iterators on the following (removing use of SeqIterator):

  • PersistentHashMap - new internal iterator (~20% faster)
  • APersistentSet - use internal map impl iterator (~5% faster)
  • PersistentQueue
  • PersistentStructMap
  • records (in core_deftype.clj)

Patch does not change use of SeqIterator in:

  • LazyTransformer$MultiStepper (not sure if this could be changed)
  • ASeq
  • LazySeq

In preparation for use in CLJ-1602, there is also a new IMapIterable interface that allows a map to publish direct Iterators of keys and values (without creating and pulling apart MapEntry objs). PersistentHashMap and PersistentArrayMap implement it right now and PersistentHashSet will check for and use the direct key iterator if possible.

Performance:

I re-ran the set of tests from CLJ-1546 for vec improvements which use these new iterators for PersistentArrayMap, PersistentHashMap, and PersistentHashSet. These test the time to run vec on a PHS or PHM of the given size. All timings in nanoseconds.

coll size 1.7.0-alpha4 1.7.0-alpha5 alpha5 + patch alpha5 + patch / alpha5
PHS 4 236 406 204 0.86
PHS 16 857 896 382 0.45
PHS 64 3637 3832 1723 0.47
PHS 256 14235 14672 6525 0.46
PHS 1024 67743 68857 44654 0.66
PHM 4 112 232 232 2.07
PHM 16 550 832 442 0.80
PHM 64 3014 3155 2014 0.67
PHM 256 11661 12082 7522 0.65
PHM 1024 57388 59787 44240 0.77

I also ran a set of tests just on reduce with reduce-kv for comparison (reduce-kv uses a different unaffected reduction path so it's a good baseline for comparison).

expr a-set / a-map size 1.6.0 1.7.0-alpha5 (ns) 1.7.0-alpha5 + patch (ns) patch / alpha5 patch / 1.6
(reduce + 0 a-set) 4 171 241 114 0.47 0.67
(reduce + 0 a-set) 16 663 826 395 0.48 0.60
(reduce + 0 a-set) 64 3637 4456 2361 0.53 0.65
(reduce + 0 a-set) 256 14772 16158 8872 0.55 0.60
(reduce + 0 a-set) 1024 72548 79010 49626 0.63 0.68
(reduce + 0 a-set) 16384 1197962 1234286 729335 0.59 0.61
(reduce #(+ %1 (val %2)) 0 a-map) 4 69 103 104 1.01 1.51
(reduce #(+ %1 (val %2)) 0 a-map) 16 640 752 506 0.67 0.79
(reduce #(+ %1 (val %2)) 0 a-map) 64 2861 3238 2388 0.74 0.83
(reduce #(+ %1 (val %2)) 0 a-map) 256 11998 12848 9526 0.74 0.79
(reduce #(+ %1 (val %2)) 0 a-map) 1024 59650 61913 54717 0.88 0.92
(reduce #(+ %1 (val %2)) 0 a-map) 16384 982317 969168 837842 0.86 0.85
(reducekv #(%1 %3) 0 a-map) 4 58 62 60 0.97 1.03
(reducekv #(%1 %3) 0 a-map) 16 233 250 248 0.99 1.06
(reducekv #(%1 %3) 0 a-map) 64 1477 1525 1442 0.95 0.98
(reducekv #(%1 %3) 0 a-map) 256 5470 5258 5201 0.99 0.95
(reducekv #(%1 %3) 0 a-map) 1024 27344 27442 27410 1.00 1.00
(reducekv #(%1 %3) 0 a-map) 16384 399591 397090 396267 1.00 0.99

Patch: clj-1499-v12.patch

Screened by:

  1. clj-1499-all.diff
    01/Oct/14 11:54 AM
    15 kB
    Alex Miller
  2. clj-1499-v10.patch
    14/Jan/15 5:35 PM
    22 kB
    Alex Miller
  3. clj-1499-v11.patch
    16/Jan/15 1:40 PM
    21 kB
    Stuart Halloway
  4. clj-1499-v12.patch
    20/Feb/15 9:46 AM
    22 kB
    Alex Miller
  5. clj-1499-v2.diff
    29/Sep/14 10:26 PM
    10 kB
    Alex Miller
  6. clj-1499-v3.diff
    30/Sep/14 4:18 PM
    12 kB
    Alex Miller
  7. clj-1499-v6.diff
    02/Dec/14 3:03 PM
    16 kB
    Alex Miller
  8. clj-1499-v7.diff
    09/Jan/15 11:11 AM
    16 kB
    Alex Miller
  9. clj-1499-v8.diff
    09/Jan/15 3:09 PM
    21 kB
    Alex Miller
  10. clj-1499-v9.patch
    14/Jan/15 1:15 PM
    21 kB
    Alex Miller
  11. defrecord-iterator.patch
    27/Sep/14 2:16 PM
    4 kB
    Ghadi Shayban
  12. defrecord-iterator-v2.diff
    30/Sep/14 7:30 PM
    3 kB
    Ghadi Shayban

Activity

Alex Miller made changes -
Field Original Value New Value
Assignee Alex Miller [ alexmiller ]
Fix Version/s Release 1.7 [ 10250 ]
Approval Vetted [ 10003 ]
Alex Miller made changes -
Reporter Alex Miller [ alexmiller ] Rich Hickey [ richhickey ]
Hide
Alex Miller added a comment -

The list of non-seqs that uses SeqIterator are:

  • records (in core_deftype.clj)
  • APersistentSet - fallback, maybe is ok?
  • PersistentHashMap
  • PersistentQueue
  • PersistentStructMap

Seqs (that do not need to be changed) are:

  • ASeq
  • LazySeq.java

LazyTransformer$MultiStepper - not sure

Show
Alex Miller added a comment - The list of non-seqs that uses SeqIterator are:
  • records (in core_deftype.clj)
  • APersistentSet - fallback, maybe is ok?
  • PersistentHashMap
  • PersistentQueue
  • PersistentStructMap
Seqs (that do not need to be changed) are:
  • ASeq
  • LazySeq.java
LazyTransformer$MultiStepper - not sure
Hide
Ghadi Shayban added a comment -

attached iterator impl for defrecords. ready to leverage iteration for extmap when PHM iteration lands.

Show
Ghadi Shayban added a comment - attached iterator impl for defrecords. ready to leverage iteration for extmap when PHM iteration lands.
Ghadi Shayban made changes -
Attachment defrecord-iterator.patch [ 13369 ]
Hide
Alex Miller added a comment -

PHM patch

Show
Alex Miller added a comment - PHM patch
Alex Miller made changes -
Attachment clj-1499-phm.diff [ 13370 ]
Alex Miller made changes -
Attachment clj-1499-phm.diff [ 13370 ]
Hide
Alex Miller added a comment -

New patch that fixes bugs with PHMs with null keys (and added tests to expose those issues), added support for PHS.

Show
Alex Miller added a comment - New patch that fixes bugs with PHMs with null keys (and added tests to expose those issues), added support for PHS.
Alex Miller made changes -
Attachment clj-1499-v2.diff [ 13371 ]
Alex Miller made changes -
Description What the title says Add support for direct iterators instead of seq-based iterators for non-seq collections that use SeqIterator.

defrecord-iterator.patch addresses:
* records (in core_deftype.clj) - still need to update to use extmap iterator and throw exception

clj-1499-v2.diff addresses:
* PersistentHashMap - new internal iterator (~20% faster)
* APersistentSet - use internal map impl iterator (~5% faster)
* PersistentQueue
* PersistentStructMap

DO NOT address:
* ASeq
* LazySeq

not sure yet:
* LazyTransformer$MultiStepper
Alex Miller made changes -
Description Add support for direct iterators instead of seq-based iterators for non-seq collections that use SeqIterator.

defrecord-iterator.patch addresses:
* records (in core_deftype.clj) - still need to update to use extmap iterator and throw exception

clj-1499-v2.diff addresses:
* PersistentHashMap - new internal iterator (~20% faster)
* APersistentSet - use internal map impl iterator (~5% faster)
* PersistentQueue
* PersistentStructMap

DO NOT address:
* ASeq
* LazySeq

not sure yet:
* LazyTransformer$MultiStepper
Add support for direct iterators instead of seq-based iterators for non-seq collections that use SeqIterator.

defrecord-iterator.patch addresses:
* records (in core_deftype.clj) - still need to update to use extmap iterator and throw exception

clj-1499-v2.diff addresses:
* PersistentHashMap - new internal iterator (~20% faster)
* APersistentSet - use internal map impl iterator (~5% faster)

not sure yet:
* PersistentQueue
* PersistentStructMap
* LazyTransformer$MultiStepper

Will NOT address:
* ASeq
* LazySeq
Hide
Ghadi Shayban added a comment -

Alex, the defrecord patch already uses the iterator for extmap. It's just made better by the PHM patch.

Show
Ghadi Shayban added a comment - Alex, the defrecord patch already uses the iterator for extmap. It's just made better by the PHM patch.
Alex Miller made changes -
Description Add support for direct iterators instead of seq-based iterators for non-seq collections that use SeqIterator.

defrecord-iterator.patch addresses:
* records (in core_deftype.clj) - still need to update to use extmap iterator and throw exception

clj-1499-v2.diff addresses:
* PersistentHashMap - new internal iterator (~20% faster)
* APersistentSet - use internal map impl iterator (~5% faster)

not sure yet:
* PersistentQueue
* PersistentStructMap
* LazyTransformer$MultiStepper

Will NOT address:
* ASeq
* LazySeq
Add support for direct iterators instead of seq-based iterators for non-seq collections that use SeqIterator.

defrecord-iterator.patch addresses:
* records (in core_deftype.clj) - still need to update to throw exception appropriately

clj-1499-v2.diff addresses:
* PersistentHashMap - new internal iterator (~20% faster)
* APersistentSet - use internal map impl iterator (~5% faster)

not sure yet:
* PersistentQueue
* PersistentStructMap
* LazyTransformer$MultiStepper

Will NOT address:
* ASeq
* LazySeq
Hide
Alex Miller added a comment -

Show
Alex Miller added a comment -
Hide
Ghadi Shayban added a comment -

Heh. Skate to where the puck is going to be – Gretzky

Re: defrecord iterator: As is, it propagates exceptions from reaching the end of the ExtMap's iterator. As noted in CLJ-1453, PersistentArrayMap's iterator improperly returns an ArrayIndexOutOfBoundsException, rather than NoSuchElementException.

Show
Ghadi Shayban added a comment - Heh. Skate to where the puck is going to be – Gretzky Re: defrecord iterator: As is, it propagates exceptions from reaching the end of the ExtMap's iterator. As noted in CLJ-1453, PersistentArrayMap's iterator improperly returns an ArrayIndexOutOfBoundsException, rather than NoSuchElementException.
Alex Miller made changes -
Attachment clj-1499-v3.diff [ 13372 ]
Description Add support for direct iterators instead of seq-based iterators for non-seq collections that use SeqIterator.

defrecord-iterator.patch addresses:
* records (in core_deftype.clj) - still need to update to throw exception appropriately

clj-1499-v2.diff addresses:
* PersistentHashMap - new internal iterator (~20% faster)
* APersistentSet - use internal map impl iterator (~5% faster)

not sure yet:
* PersistentQueue
* PersistentStructMap
* LazyTransformer$MultiStepper

Will NOT address:
* ASeq
* LazySeq
Add support for direct iterators instead of seq-based iterators for non-seq collections that use SeqIterator.

defrecord-iterator.patch addresses:
* records (in core_deftype.clj) - still need to update to throw exception appropriately

clj-1499-v3.diff addresses:
* PersistentHashMap - new internal iterator (~20% faster)
* APersistentSet - use internal map impl iterator (~5% faster)
* PersistentQueue
* PersistentStructMap

not sure:
* LazyTransformer$MultiStepper

Will NOT address:
* ASeq
* LazySeq
Patch Code and Test [ 10002 ]
Alex Miller made changes -
Description Add support for direct iterators instead of seq-based iterators for non-seq collections that use SeqIterator.

defrecord-iterator.patch addresses:
* records (in core_deftype.clj) - still need to update to throw exception appropriately

clj-1499-v3.diff addresses:
* PersistentHashMap - new internal iterator (~20% faster)
* APersistentSet - use internal map impl iterator (~5% faster)
* PersistentQueue
* PersistentStructMap

not sure:
* LazyTransformer$MultiStepper

Will NOT address:
* ASeq
* LazySeq
Add support for direct iterators instead of seq-based iterators for non-seq collections that use SeqIterator.

defrecord-iterator.patch addresses:
* records (in core_deftype.clj)

clj-1499-v3.diff addresses:
* PersistentHashMap - new internal iterator (~20% faster)
* APersistentSet - use internal map impl iterator (~5% faster)
* PersistentQueue
* PersistentStructMap

not sure:
* LazyTransformer$MultiStepper

Will NOT address:
* ASeq
* LazySeq
Alex Miller made changes -
Assignee Alex Miller [ alexmiller ]
Hide
Alex Miller added a comment -

Hey Ghadi, rather than rebuilding the case map to pass to the RecordIterator, why don't you just pass the fields in iteration order to it and leverage the case map via .valAt like everything else?

Show
Alex Miller added a comment - Hey Ghadi, rather than rebuilding the case map to pass to the RecordIterator, why don't you just pass the fields in iteration order to it and leverage the case map via .valAt like everything else?
Alex Miller made changes -
Approval Vetted [ 10003 ] Incomplete [ 10006 ]
Hide
Ghadi Shayban added a comment -

defrecord-iterator-v2.diff reuses valAt and minimizes macrology.

Show
Ghadi Shayban added a comment - defrecord-iterator-v2.diff reuses valAt and minimizes macrology.
Ghadi Shayban made changes -
Attachment defrecord-iterator-v2.diff [ 13378 ]
Alex Miller made changes -
Description Add support for direct iterators instead of seq-based iterators for non-seq collections that use SeqIterator.

defrecord-iterator.patch addresses:
* records (in core_deftype.clj)

clj-1499-v3.diff addresses:
* PersistentHashMap - new internal iterator (~20% faster)
* APersistentSet - use internal map impl iterator (~5% faster)
* PersistentQueue
* PersistentStructMap

not sure:
* LazyTransformer$MultiStepper

Will NOT address:
* ASeq
* LazySeq
Add support for direct iterators instead of seq-based iterators for non-seq collections that use SeqIterator.

defrecord-iterator-v2.diff addresses:
* records (in core_deftype.clj)

clj-1499-v3.diff addresses:
* PersistentHashMap - new internal iterator (~20% faster)
* APersistentSet - use internal map impl iterator (~5% faster)
* PersistentQueue
* PersistentStructMap

not sure:
* LazyTransformer$MultiStepper

Will NOT address:
* ASeq
* LazySeq
Alex Miller made changes -
Attachment clj-1499-all.diff [ 13379 ]
Description Add support for direct iterators instead of seq-based iterators for non-seq collections that use SeqIterator.

defrecord-iterator-v2.diff addresses:
* records (in core_deftype.clj)

clj-1499-v3.diff addresses:
* PersistentHashMap - new internal iterator (~20% faster)
* APersistentSet - use internal map impl iterator (~5% faster)
* PersistentQueue
* PersistentStructMap

not sure:
* LazyTransformer$MultiStepper

Will NOT address:
* ASeq
* LazySeq
Add support for direct iterators instead of seq-based iterators for non-seq collections that use SeqIterator.

Patch adds support for direct iterators on the following (removing use of SeqIterator):
* PersistentHashMap - new internal iterator (~20% faster)
* APersistentSet - use internal map impl iterator (~5% faster)
* PersistentQueue
* PersistentStructMap
* records (in core_deftype.clj)

Patch does not change use of SeqIterator in:
* LazyTransformer$MultiStepper (not sure if this could be changed)
* ASeq
* LazySeq

*Patch:* clj-1499-all.diff
Approval Incomplete [ 10006 ] Vetted [ 10003 ]
Alex Miller made changes -
Priority Major [ 3 ] Critical [ 2 ]
Rich Hickey made changes -
Fix Version/s Release 1.8 [ 10254 ]
Fix Version/s Release 1.7 [ 10250 ]
Hide
Alex Miller added a comment -

Comments from Stu (found under the couch):

"1. some of the impls (e.g. queue manually concatenate two iters. Would implementing iter-cat and calling that be simpler and more robust?
2. I found this tweak to the generative testing more useful in reporting failure, non-dependent on clojure.test, and capable of expecting failures. Waddya think?

(defn seq-iter-match
  [seqable iterable]
  (let [i (.iterator iterable)]
    (loop [s (seq seqable)
           n 0]
      (if (seq s)
        (do
          (when-not (.hasNext i)
            (throw (ex-info "Iterator exhausted before seq"
                            {:pos n :seqable seqable :iterable iterable})))
          (when-not (= (.next i) (first s))
            (throw (ex-info "Iterator and seq did not match"
                            {:pos n :seqable seqable :iterable iterable})))
          (recur (rest s) (inc n)))
        (when (.hasNext i)
          (throw (ex-info "Seq exhausted before iterator"
                          {:pos n :seqable seqable :iterable iterable})))))))

		(defspec seq-and-iter-match-for-maps
  identity
  [^{:tag clojure.test-clojure.data-structures/gen-map} m]
  (seq-iter-match m m))

3. similar generative approach would be good for the other types (looks like we just do maps)"

Show
Alex Miller added a comment - Comments from Stu (found under the couch): "1. some of the impls (e.g. queue manually concatenate two iters. Would implementing iter-cat and calling that be simpler and more robust? 2. I found this tweak to the generative testing more useful in reporting failure, non-dependent on clojure.test, and capable of expecting failures. Waddya think?
(defn seq-iter-match
  [seqable iterable]
  (let [i (.iterator iterable)]
    (loop [s (seq seqable)
           n 0]
      (if (seq s)
        (do
          (when-not (.hasNext i)
            (throw (ex-info "Iterator exhausted before seq"
                            {:pos n :seqable seqable :iterable iterable})))
          (when-not (= (.next i) (first s))
            (throw (ex-info "Iterator and seq did not match"
                            {:pos n :seqable seqable :iterable iterable})))
          (recur (rest s) (inc n)))
        (when (.hasNext i)
          (throw (ex-info "Seq exhausted before iterator"
                          {:pos n :seqable seqable :iterable iterable})))))))

		(defspec seq-and-iter-match-for-maps
  identity
  [^{:tag clojure.test-clojure.data-structures/gen-map} m]
  (seq-iter-match m m))
3. similar generative approach would be good for the other types (looks like we just do maps)"
Hide
Alex Miller added a comment -

Latest patch (clj-1499-v6.diff) makes Stu's suggested change #2 above and adds tests recommended in #3. I looked at #1 but decided in the end that it wasn't going to make anything easier.

Show
Alex Miller added a comment - Latest patch (clj-1499-v6.diff) makes Stu's suggested change #2 above and adds tests recommended in #3. I looked at #1 but decided in the end that it wasn't going to make anything easier.
Alex Miller made changes -
Fix Version/s Release 1.7 [ 10250 ]
Fix Version/s Release 1.8 [ 10254 ]
Attachment clj-1499-v6.diff [ 13561 ]
Description Add support for direct iterators instead of seq-based iterators for non-seq collections that use SeqIterator.

Patch adds support for direct iterators on the following (removing use of SeqIterator):
* PersistentHashMap - new internal iterator (~20% faster)
* APersistentSet - use internal map impl iterator (~5% faster)
* PersistentQueue
* PersistentStructMap
* records (in core_deftype.clj)

Patch does not change use of SeqIterator in:
* LazyTransformer$MultiStepper (not sure if this could be changed)
* ASeq
* LazySeq

*Patch:* clj-1499-all.diff
Add support for direct iterators instead of seq-based iterators for non-seq collections that use SeqIterator.

Patch adds support for direct iterators on the following (removing use of SeqIterator):
* PersistentHashMap - new internal iterator (~20% faster)
* APersistentSet - use internal map impl iterator (~5% faster)
* PersistentQueue
* PersistentStructMap
* records (in core_deftype.clj)

Patch does not change use of SeqIterator in:
* LazyTransformer$MultiStepper (not sure if this could be changed)
* ASeq
* LazySeq

*Patch:* clj-1499-v6.diff
Alex Miller made changes -
Description Add support for direct iterators instead of seq-based iterators for non-seq collections that use SeqIterator.

Patch adds support for direct iterators on the following (removing use of SeqIterator):
* PersistentHashMap - new internal iterator (~20% faster)
* APersistentSet - use internal map impl iterator (~5% faster)
* PersistentQueue
* PersistentStructMap
* records (in core_deftype.clj)

Patch does not change use of SeqIterator in:
* LazyTransformer$MultiStepper (not sure if this could be changed)
* ASeq
* LazySeq

*Patch:* clj-1499-v6.diff
Add support for direct iterators instead of seq-based iterators for non-seq collections that use SeqIterator.

Patch adds support for direct iterators on the following (removing use of SeqIterator):
* PersistentHashMap - new internal iterator (~20% faster)
* APersistentSet - use internal map impl iterator (~5% faster)
* PersistentQueue
* PersistentStructMap
* records (in core_deftype.clj)

Patch does not change use of SeqIterator in:
* LazyTransformer$MultiStepper (not sure if this could be changed)
* ASeq
* LazySeq

*Patch:* clj-1499-v6.diff

*Screening note:* I have played with an extension to this patch that adds a new MapIterable interface for obtaining direct key and val iterators (without having to build and tear apart map entries), which can pretty easily be used by keys/vals in CLJ-1602. I was not sure if that was taking this too far for small perf improvement in those cases). If that seems like a good idea, I could re-work this patch to include it.

*Screened by:*
Alex Miller made changes -
Assignee Alex Miller [ alexmiller ]
Approval Vetted [ 10003 ] Incomplete [ 10006 ]
Hide
Alex Miller added a comment -

v7 patch just updates to current master

Show
Alex Miller added a comment - v7 patch just updates to current master
Alex Miller made changes -
Attachment clj-1499-v7.diff [ 13741 ]
Description Add support for direct iterators instead of seq-based iterators for non-seq collections that use SeqIterator.

Patch adds support for direct iterators on the following (removing use of SeqIterator):
* PersistentHashMap - new internal iterator (~20% faster)
* APersistentSet - use internal map impl iterator (~5% faster)
* PersistentQueue
* PersistentStructMap
* records (in core_deftype.clj)

Patch does not change use of SeqIterator in:
* LazyTransformer$MultiStepper (not sure if this could be changed)
* ASeq
* LazySeq

*Patch:* clj-1499-v6.diff

*Screening note:* I have played with an extension to this patch that adds a new MapIterable interface for obtaining direct key and val iterators (without having to build and tear apart map entries), which can pretty easily be used by keys/vals in CLJ-1602. I was not sure if that was taking this too far for small perf improvement in those cases). If that seems like a good idea, I could re-work this patch to include it.

*Screened by:*
Add support for direct iterators instead of seq-based iterators for non-seq collections that use SeqIterator.

Patch adds support for direct iterators on the following (removing use of SeqIterator):
* PersistentHashMap - new internal iterator (~20% faster)
* APersistentSet - use internal map impl iterator (~5% faster)
* PersistentQueue
* PersistentStructMap
* records (in core_deftype.clj)

Patch does not change use of SeqIterator in:
* LazyTransformer$MultiStepper (not sure if this could be changed)
* ASeq
* LazySeq

*Patch:* clj-1499-v7.diff

*Screening note:* I have played with an extension to this patch that adds a new MapIterable interface for obtaining direct key and val iterators (without having to build and tear apart map entries), which can pretty easily be used by keys/vals in CLJ-1602. I was not sure if that was taking this too far for small perf improvement in those cases). If that seems like a good idea, I could re-work this patch to include it.

*Screened by:*
Alex Miller made changes -
Attachment clj-1499-v8.diff [ 13743 ]
Description Add support for direct iterators instead of seq-based iterators for non-seq collections that use SeqIterator.

Patch adds support for direct iterators on the following (removing use of SeqIterator):
* PersistentHashMap - new internal iterator (~20% faster)
* APersistentSet - use internal map impl iterator (~5% faster)
* PersistentQueue
* PersistentStructMap
* records (in core_deftype.clj)

Patch does not change use of SeqIterator in:
* LazyTransformer$MultiStepper (not sure if this could be changed)
* ASeq
* LazySeq

*Patch:* clj-1499-v7.diff

*Screening note:* I have played with an extension to this patch that adds a new MapIterable interface for obtaining direct key and val iterators (without having to build and tear apart map entries), which can pretty easily be used by keys/vals in CLJ-1602. I was not sure if that was taking this too far for small perf improvement in those cases). If that seems like a good idea, I could re-work this patch to include it.

*Screened by:*
Add support for direct iterators instead of seq-based iterators for non-seq collections that use SeqIterator.

Patch adds support for direct iterators on the following (removing use of SeqIterator):
* PersistentHashMap - new internal iterator (~20% faster)
* APersistentSet - use internal map impl iterator (~5% faster)
* PersistentQueue
* PersistentStructMap
* records (in core_deftype.clj)

Patch does not change use of SeqIterator in:
* LazyTransformer$MultiStepper (not sure if this could be changed)
* ASeq
* LazySeq

In preparation for use in CLJ-1602, there is a new IMapIterable interface that allows a map to publish direct Iterators of keys and values (without creating and pulling apart MapEntry objs). PersistentHashMap and PersistentArrayMap implement it right now.

*Patch:* clj-1499-v8.diff

*Screening note:* I have played with an extension to this patch that adds a new MapIterable interface for obtaining direct key and val iterators (without having to build and tear apart map entries), which can pretty easily be used by keys/vals in CLJ-1602. I was not sure if that was taking this too far for small perf improvement in those cases). If that seems like a good idea, I could re-work this patch to include it.

*Screened by:*
Alex Miller made changes -
Attachment clj-1499-v9.patch [ 13762 ]
Description Add support for direct iterators instead of seq-based iterators for non-seq collections that use SeqIterator.

Patch adds support for direct iterators on the following (removing use of SeqIterator):
* PersistentHashMap - new internal iterator (~20% faster)
* APersistentSet - use internal map impl iterator (~5% faster)
* PersistentQueue
* PersistentStructMap
* records (in core_deftype.clj)

Patch does not change use of SeqIterator in:
* LazyTransformer$MultiStepper (not sure if this could be changed)
* ASeq
* LazySeq

In preparation for use in CLJ-1602, there is a new IMapIterable interface that allows a map to publish direct Iterators of keys and values (without creating and pulling apart MapEntry objs). PersistentHashMap and PersistentArrayMap implement it right now.

*Patch:* clj-1499-v8.diff

*Screening note:* I have played with an extension to this patch that adds a new MapIterable interface for obtaining direct key and val iterators (without having to build and tear apart map entries), which can pretty easily be used by keys/vals in CLJ-1602. I was not sure if that was taking this too far for small perf improvement in those cases). If that seems like a good idea, I could re-work this patch to include it.

*Screened by:*
Add support for direct iterators instead of seq-based iterators for non-seq collections that use SeqIterator.

Patch adds support for direct iterators on the following (removing use of SeqIterator):
* PersistentHashMap - new internal iterator (~20% faster)
* APersistentSet - use internal map impl iterator (~5% faster)
* PersistentQueue
* PersistentStructMap
* records (in core_deftype.clj)

Patch does not change use of SeqIterator in:
* LazyTransformer$MultiStepper (not sure if this could be changed)
* ASeq
* LazySeq

In preparation for use in CLJ-1602, there is also a new IMapIterable interface that allows a map to publish direct Iterators of keys and values (without creating and pulling apart MapEntry objs). PersistentHashMap and PersistentArrayMap implement it right now and PersistentHashSet will check for and use the direct key iterator if possible.

*Performance:*

I re-ran the set of tests from CLJ-1546 for vec improvements which use these new iterators for PersistentArrayMap, PersistentHashMap, and PersistentHashSet. These test the time to run vec on a PHS or PHM of the given size. All timings in nanoseconds.

|| coll || size || 1.7.0-alpha4 || 1.7.0-alpha5 || alpha5 + patch || alpha5 + patch / alpha5 ||
| PHS | 4 | 236 | 406 | 204 | 0.86 |
| PHS | 16 | 857 | 896 | 382 | 0.45 |
| PHS | 64 | 3637 | 3832 | 1723 | 0.47 |
| PHS | 256 | 14235 | 14672 | 6525 | 0.46 |
| PHS | 1024 | 67743 | 68857 | 44654 | 0.66 |
| PHM | 4 | 112 | 232 | 232 | 2.07 |
| PHM | 16 | 550 | 832 | 442 | 0.80 |
| PHM | 64 | 3014 | 3155 | 2014 | 0.67 |
| PHM | 256 | 11661 | 12082 | 7522 | 0.65 |
| PHM | 1024 | 57388 | 59787 | 44240 | 0.77 |

I also ran a set of tests just on reduce with reduce-kv for comparison (reduce-kv uses a different unaffected reduction path so it's a good baseline for comparison).

|| expr || a-set / a-map size || 1.6.0 || 1.7.0-alpha5 (ns) || 1.7.0-alpha5 + patch (ns) || patch / alpha5 || patch / 1.6 ||
| (reduce + 0 a-set) | 4 | 171 | 241 | 114 | 0.47 | 0.67 |
| (reduce + 0 a-set) | 16 | 663 | 826 | 395 | 0.48 | 0.60 |
| (reduce + 0 a-set) | 64 | 3637 | 4456 | 2361 | 0.53 | 0.65 |
| (reduce + 0 a-set) | 256 | 14772 | 16158 | 8872 | 0.55 | 0.60 |
| (reduce + 0 a-set) | 1024 | 72548 | 79010 | 49626 | 0.63 | 0.68 |
| (reduce + 0 a-set) | 16384 | 1197962 | 1234286 | 729335 | 0.59 | 0.61 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 4 | 69 | 103 | 104 | 1.01 | 1.51 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 16 | 640 | 752 | 506 | 0.67 | 0.79 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 64 | 2861 | 3238 | 2388 | 0.74 | 0.83 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 256 | 11998 | 12848 | 9526 | 0.74 | 0.79 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 1024 | 59650 | 61913 | 54717 | 0.88 | 0.92 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 16384 | 982317 | 969168 | 837842 | 0.86 | 0.85 |
| (reducekv #(%1 %3) 0 a-map) | 4 | 58 | 62 | 60 | 0.97 | 1.03 |
| (reducekv #(%1 %3) 0 a-map) | 16 | 233 | 250 | 248 | 0.99 | 1.06 |
| (reducekv #(%1 %3) 0 a-map) | 64 | 1477 | 1525 | 1442 | 0.95 | 0.98 |
| (reducekv #(%1 %3) 0 a-map) | 256 | 5470 | 5258 | 5201 | 0.99 | 0.95 |
| (reducekv #(%1 %3) 0 a-map) | 1024 | 27344 | 27442 | 27410 | 1.00 | 1.00 |
| (reducekv #(%1 %3) 0 a-map) | 16384 | 399591 | 397090 | 396267 | 1.00 | 0.99 |

*Patch:* clj-1499-v9.diff

*Screened by:*
Approval Incomplete [ 10006 ] Vetted [ 10003 ]
Alex Miller made changes -
Description Add support for direct iterators instead of seq-based iterators for non-seq collections that use SeqIterator.

Patch adds support for direct iterators on the following (removing use of SeqIterator):
* PersistentHashMap - new internal iterator (~20% faster)
* APersistentSet - use internal map impl iterator (~5% faster)
* PersistentQueue
* PersistentStructMap
* records (in core_deftype.clj)

Patch does not change use of SeqIterator in:
* LazyTransformer$MultiStepper (not sure if this could be changed)
* ASeq
* LazySeq

In preparation for use in CLJ-1602, there is also a new IMapIterable interface that allows a map to publish direct Iterators of keys and values (without creating and pulling apart MapEntry objs). PersistentHashMap and PersistentArrayMap implement it right now and PersistentHashSet will check for and use the direct key iterator if possible.

*Performance:*

I re-ran the set of tests from CLJ-1546 for vec improvements which use these new iterators for PersistentArrayMap, PersistentHashMap, and PersistentHashSet. These test the time to run vec on a PHS or PHM of the given size. All timings in nanoseconds.

|| coll || size || 1.7.0-alpha4 || 1.7.0-alpha5 || alpha5 + patch || alpha5 + patch / alpha5 ||
| PHS | 4 | 236 | 406 | 204 | 0.86 |
| PHS | 16 | 857 | 896 | 382 | 0.45 |
| PHS | 64 | 3637 | 3832 | 1723 | 0.47 |
| PHS | 256 | 14235 | 14672 | 6525 | 0.46 |
| PHS | 1024 | 67743 | 68857 | 44654 | 0.66 |
| PHM | 4 | 112 | 232 | 232 | 2.07 |
| PHM | 16 | 550 | 832 | 442 | 0.80 |
| PHM | 64 | 3014 | 3155 | 2014 | 0.67 |
| PHM | 256 | 11661 | 12082 | 7522 | 0.65 |
| PHM | 1024 | 57388 | 59787 | 44240 | 0.77 |

I also ran a set of tests just on reduce with reduce-kv for comparison (reduce-kv uses a different unaffected reduction path so it's a good baseline for comparison).

|| expr || a-set / a-map size || 1.6.0 || 1.7.0-alpha5 (ns) || 1.7.0-alpha5 + patch (ns) || patch / alpha5 || patch / 1.6 ||
| (reduce + 0 a-set) | 4 | 171 | 241 | 114 | 0.47 | 0.67 |
| (reduce + 0 a-set) | 16 | 663 | 826 | 395 | 0.48 | 0.60 |
| (reduce + 0 a-set) | 64 | 3637 | 4456 | 2361 | 0.53 | 0.65 |
| (reduce + 0 a-set) | 256 | 14772 | 16158 | 8872 | 0.55 | 0.60 |
| (reduce + 0 a-set) | 1024 | 72548 | 79010 | 49626 | 0.63 | 0.68 |
| (reduce + 0 a-set) | 16384 | 1197962 | 1234286 | 729335 | 0.59 | 0.61 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 4 | 69 | 103 | 104 | 1.01 | 1.51 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 16 | 640 | 752 | 506 | 0.67 | 0.79 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 64 | 2861 | 3238 | 2388 | 0.74 | 0.83 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 256 | 11998 | 12848 | 9526 | 0.74 | 0.79 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 1024 | 59650 | 61913 | 54717 | 0.88 | 0.92 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 16384 | 982317 | 969168 | 837842 | 0.86 | 0.85 |
| (reducekv #(%1 %3) 0 a-map) | 4 | 58 | 62 | 60 | 0.97 | 1.03 |
| (reducekv #(%1 %3) 0 a-map) | 16 | 233 | 250 | 248 | 0.99 | 1.06 |
| (reducekv #(%1 %3) 0 a-map) | 64 | 1477 | 1525 | 1442 | 0.95 | 0.98 |
| (reducekv #(%1 %3) 0 a-map) | 256 | 5470 | 5258 | 5201 | 0.99 | 0.95 |
| (reducekv #(%1 %3) 0 a-map) | 1024 | 27344 | 27442 | 27410 | 1.00 | 1.00 |
| (reducekv #(%1 %3) 0 a-map) | 16384 | 399591 | 397090 | 396267 | 1.00 | 0.99 |

*Patch:* clj-1499-v9.diff

*Screened by:*
Add support for direct iterators instead of seq-based iterators for non-seq collections that use SeqIterator.

Patch adds support for direct iterators on the following (removing use of SeqIterator):
* PersistentHashMap - new internal iterator (~20% faster)
* APersistentSet - use internal map impl iterator (~5% faster)
* PersistentQueue
* PersistentStructMap
* records (in core_deftype.clj)

Patch does not change use of SeqIterator in:
* LazyTransformer$MultiStepper (not sure if this could be changed)
* ASeq
* LazySeq

In preparation for use in CLJ-1602, there is also a new IMapIterable interface that allows a map to publish direct Iterators of keys and values (without creating and pulling apart MapEntry objs). PersistentHashMap and PersistentArrayMap implement it right now and PersistentHashSet will check for and use the direct key iterator if possible.

*Performance:*

I re-ran the set of tests from CLJ-1546 for vec improvements which use these new iterators for PersistentArrayMap, PersistentHashMap, and PersistentHashSet. These test the time to run vec on a PHS or PHM of the given size. All timings in nanoseconds.

|| coll || size || 1.7.0-alpha4 || 1.7.0-alpha5 || alpha5 + patch || alpha5 + patch / alpha5 ||
| PHS | 4 | 236 | 406 | 204 | 0.86 |
| PHS | 16 | 857 | 896 | 382 | 0.45 |
| PHS | 64 | 3637 | 3832 | 1723 | 0.47 |
| PHS | 256 | 14235 | 14672 | 6525 | 0.46 |
| PHS | 1024 | 67743 | 68857 | 44654 | 0.66 |
| PHM | 4 | 112 | 232 | 232 | 2.07 |
| PHM | 16 | 550 | 832 | 442 | 0.80 |
| PHM | 64 | 3014 | 3155 | 2014 | 0.67 |
| PHM | 256 | 11661 | 12082 | 7522 | 0.65 |
| PHM | 1024 | 57388 | 59787 | 44240 | 0.77 |

I also ran a set of tests just on reduce with reduce-kv for comparison (reduce-kv uses a different unaffected reduction path so it's a good baseline for comparison).

|| expr || a-set / a-map size || 1.6.0 || 1.7.0-alpha5 (ns) || 1.7.0-alpha5 + patch (ns) || patch / alpha5 || patch / 1.6 ||
| (reduce + 0 a-set) | 4 | 171 | 241 | 114 | 0.47 | 0.67 |
| (reduce + 0 a-set) | 16 | 663 | 826 | 395 | 0.48 | 0.60 |
| (reduce + 0 a-set) | 64 | 3637 | 4456 | 2361 | 0.53 | 0.65 |
| (reduce + 0 a-set) | 256 | 14772 | 16158 | 8872 | 0.55 | 0.60 |
| (reduce + 0 a-set) | 1024 | 72548 | 79010 | 49626 | 0.63 | 0.68 |
| (reduce + 0 a-set) | 16384 | 1197962 | 1234286 | 729335 | 0.59 | 0.61 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 4 | 69 | 103 | 104 | 1.01 | 1.51 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 16 | 640 | 752 | 506 | 0.67 | 0.79 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 64 | 2861 | 3238 | 2388 | 0.74 | 0.83 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 256 | 11998 | 12848 | 9526 | 0.74 | 0.79 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 1024 | 59650 | 61913 | 54717 | 0.88 | 0.92 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 16384 | 982317 | 969168 | 837842 | 0.86 | 0.85 |
| (reducekv #(%1 %3) 0 a-map) | 4 | 58 | 62 | 60 | 0.97 | 1.03 |
| (reducekv #(%1 %3) 0 a-map) | 16 | 233 | 250 | 248 | 0.99 | 1.06 |
| (reducekv #(%1 %3) 0 a-map) | 64 | 1477 | 1525 | 1442 | 0.95 | 0.98 |
| (reducekv #(%1 %3) 0 a-map) | 256 | 5470 | 5258 | 5201 | 0.99 | 0.95 |
| (reducekv #(%1 %3) 0 a-map) | 1024 | 27344 | 27442 | 27410 | 1.00 | 1.00 |
| (reducekv #(%1 %3) 0 a-map) | 16384 | 399591 | 397090 | 396267 | 1.00 | 0.99 |

*Patch:* clj-1499-v9.patch

*Screened by:*
Hide
Alex Miller added a comment -

found a bug in last impl in maps with null values...fixing

Show
Alex Miller added a comment - found a bug in last impl in maps with null values...fixing
Alex Miller made changes -
Approval Vetted [ 10003 ] Incomplete [ 10006 ]
Alex Miller made changes -
Attachment clj-1499-v10.patch [ 13763 ]
Description Add support for direct iterators instead of seq-based iterators for non-seq collections that use SeqIterator.

Patch adds support for direct iterators on the following (removing use of SeqIterator):
* PersistentHashMap - new internal iterator (~20% faster)
* APersistentSet - use internal map impl iterator (~5% faster)
* PersistentQueue
* PersistentStructMap
* records (in core_deftype.clj)

Patch does not change use of SeqIterator in:
* LazyTransformer$MultiStepper (not sure if this could be changed)
* ASeq
* LazySeq

In preparation for use in CLJ-1602, there is also a new IMapIterable interface that allows a map to publish direct Iterators of keys and values (without creating and pulling apart MapEntry objs). PersistentHashMap and PersistentArrayMap implement it right now and PersistentHashSet will check for and use the direct key iterator if possible.

*Performance:*

I re-ran the set of tests from CLJ-1546 for vec improvements which use these new iterators for PersistentArrayMap, PersistentHashMap, and PersistentHashSet. These test the time to run vec on a PHS or PHM of the given size. All timings in nanoseconds.

|| coll || size || 1.7.0-alpha4 || 1.7.0-alpha5 || alpha5 + patch || alpha5 + patch / alpha5 ||
| PHS | 4 | 236 | 406 | 204 | 0.86 |
| PHS | 16 | 857 | 896 | 382 | 0.45 |
| PHS | 64 | 3637 | 3832 | 1723 | 0.47 |
| PHS | 256 | 14235 | 14672 | 6525 | 0.46 |
| PHS | 1024 | 67743 | 68857 | 44654 | 0.66 |
| PHM | 4 | 112 | 232 | 232 | 2.07 |
| PHM | 16 | 550 | 832 | 442 | 0.80 |
| PHM | 64 | 3014 | 3155 | 2014 | 0.67 |
| PHM | 256 | 11661 | 12082 | 7522 | 0.65 |
| PHM | 1024 | 57388 | 59787 | 44240 | 0.77 |

I also ran a set of tests just on reduce with reduce-kv for comparison (reduce-kv uses a different unaffected reduction path so it's a good baseline for comparison).

|| expr || a-set / a-map size || 1.6.0 || 1.7.0-alpha5 (ns) || 1.7.0-alpha5 + patch (ns) || patch / alpha5 || patch / 1.6 ||
| (reduce + 0 a-set) | 4 | 171 | 241 | 114 | 0.47 | 0.67 |
| (reduce + 0 a-set) | 16 | 663 | 826 | 395 | 0.48 | 0.60 |
| (reduce + 0 a-set) | 64 | 3637 | 4456 | 2361 | 0.53 | 0.65 |
| (reduce + 0 a-set) | 256 | 14772 | 16158 | 8872 | 0.55 | 0.60 |
| (reduce + 0 a-set) | 1024 | 72548 | 79010 | 49626 | 0.63 | 0.68 |
| (reduce + 0 a-set) | 16384 | 1197962 | 1234286 | 729335 | 0.59 | 0.61 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 4 | 69 | 103 | 104 | 1.01 | 1.51 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 16 | 640 | 752 | 506 | 0.67 | 0.79 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 64 | 2861 | 3238 | 2388 | 0.74 | 0.83 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 256 | 11998 | 12848 | 9526 | 0.74 | 0.79 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 1024 | 59650 | 61913 | 54717 | 0.88 | 0.92 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 16384 | 982317 | 969168 | 837842 | 0.86 | 0.85 |
| (reducekv #(%1 %3) 0 a-map) | 4 | 58 | 62 | 60 | 0.97 | 1.03 |
| (reducekv #(%1 %3) 0 a-map) | 16 | 233 | 250 | 248 | 0.99 | 1.06 |
| (reducekv #(%1 %3) 0 a-map) | 64 | 1477 | 1525 | 1442 | 0.95 | 0.98 |
| (reducekv #(%1 %3) 0 a-map) | 256 | 5470 | 5258 | 5201 | 0.99 | 0.95 |
| (reducekv #(%1 %3) 0 a-map) | 1024 | 27344 | 27442 | 27410 | 1.00 | 1.00 |
| (reducekv #(%1 %3) 0 a-map) | 16384 | 399591 | 397090 | 396267 | 1.00 | 0.99 |

*Patch:* clj-1499-v9.patch

*Screened by:*
Add support for direct iterators instead of seq-based iterators for non-seq collections that use SeqIterator.

Patch adds support for direct iterators on the following (removing use of SeqIterator):
* PersistentHashMap - new internal iterator (~20% faster)
* APersistentSet - use internal map impl iterator (~5% faster)
* PersistentQueue
* PersistentStructMap
* records (in core_deftype.clj)

Patch does not change use of SeqIterator in:
* LazyTransformer$MultiStepper (not sure if this could be changed)
* ASeq
* LazySeq

In preparation for use in CLJ-1602, there is also a new IMapIterable interface that allows a map to publish direct Iterators of keys and values (without creating and pulling apart MapEntry objs). PersistentHashMap and PersistentArrayMap implement it right now and PersistentHashSet will check for and use the direct key iterator if possible.

*Performance:*

I re-ran the set of tests from CLJ-1546 for vec improvements which use these new iterators for PersistentArrayMap, PersistentHashMap, and PersistentHashSet. These test the time to run vec on a PHS or PHM of the given size. All timings in nanoseconds.

|| coll || size || 1.7.0-alpha4 || 1.7.0-alpha5 || alpha5 + patch || alpha5 + patch / alpha5 ||
| PHS | 4 | 236 | 406 | 204 | 0.86 |
| PHS | 16 | 857 | 896 | 382 | 0.45 |
| PHS | 64 | 3637 | 3832 | 1723 | 0.47 |
| PHS | 256 | 14235 | 14672 | 6525 | 0.46 |
| PHS | 1024 | 67743 | 68857 | 44654 | 0.66 |
| PHM | 4 | 112 | 232 | 232 | 2.07 |
| PHM | 16 | 550 | 832 | 442 | 0.80 |
| PHM | 64 | 3014 | 3155 | 2014 | 0.67 |
| PHM | 256 | 11661 | 12082 | 7522 | 0.65 |
| PHM | 1024 | 57388 | 59787 | 44240 | 0.77 |

I also ran a set of tests just on reduce with reduce-kv for comparison (reduce-kv uses a different unaffected reduction path so it's a good baseline for comparison).

|| expr || a-set / a-map size || 1.6.0 || 1.7.0-alpha5 (ns) || 1.7.0-alpha5 + patch (ns) || patch / alpha5 || patch / 1.6 ||
| (reduce + 0 a-set) | 4 | 171 | 241 | 114 | 0.47 | 0.67 |
| (reduce + 0 a-set) | 16 | 663 | 826 | 395 | 0.48 | 0.60 |
| (reduce + 0 a-set) | 64 | 3637 | 4456 | 2361 | 0.53 | 0.65 |
| (reduce + 0 a-set) | 256 | 14772 | 16158 | 8872 | 0.55 | 0.60 |
| (reduce + 0 a-set) | 1024 | 72548 | 79010 | 49626 | 0.63 | 0.68 |
| (reduce + 0 a-set) | 16384 | 1197962 | 1234286 | 729335 | 0.59 | 0.61 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 4 | 69 | 103 | 104 | 1.01 | 1.51 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 16 | 640 | 752 | 506 | 0.67 | 0.79 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 64 | 2861 | 3238 | 2388 | 0.74 | 0.83 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 256 | 11998 | 12848 | 9526 | 0.74 | 0.79 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 1024 | 59650 | 61913 | 54717 | 0.88 | 0.92 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 16384 | 982317 | 969168 | 837842 | 0.86 | 0.85 |
| (reducekv #(%1 %3) 0 a-map) | 4 | 58 | 62 | 60 | 0.97 | 1.03 |
| (reducekv #(%1 %3) 0 a-map) | 16 | 233 | 250 | 248 | 0.99 | 1.06 |
| (reducekv #(%1 %3) 0 a-map) | 64 | 1477 | 1525 | 1442 | 0.95 | 0.98 |
| (reducekv #(%1 %3) 0 a-map) | 256 | 5470 | 5258 | 5201 | 0.99 | 0.95 |
| (reducekv #(%1 %3) 0 a-map) | 1024 | 27344 | 27442 | 27410 | 1.00 | 1.00 |
| (reducekv #(%1 %3) 0 a-map) | 16384 | 399591 | 397090 | 396267 | 1.00 | 0.99 |

*Patch:* clj-1499-v10.patch

*Screened by:*
Approval Incomplete [ 10006 ] Vetted [ 10003 ]
Alex Miller made changes -
Priority Critical [ 2 ] Major [ 3 ]
Hide
Stuart Halloway added a comment -

v11 updates v10 to apply cleanly on master

Show
Stuart Halloway added a comment - v11 updates v10 to apply cleanly on master
Stuart Halloway made changes -
Attachment clj-1499-v11.patch [ 13775 ]
Description Add support for direct iterators instead of seq-based iterators for non-seq collections that use SeqIterator.

Patch adds support for direct iterators on the following (removing use of SeqIterator):
* PersistentHashMap - new internal iterator (~20% faster)
* APersistentSet - use internal map impl iterator (~5% faster)
* PersistentQueue
* PersistentStructMap
* records (in core_deftype.clj)

Patch does not change use of SeqIterator in:
* LazyTransformer$MultiStepper (not sure if this could be changed)
* ASeq
* LazySeq

In preparation for use in CLJ-1602, there is also a new IMapIterable interface that allows a map to publish direct Iterators of keys and values (without creating and pulling apart MapEntry objs). PersistentHashMap and PersistentArrayMap implement it right now and PersistentHashSet will check for and use the direct key iterator if possible.

*Performance:*

I re-ran the set of tests from CLJ-1546 for vec improvements which use these new iterators for PersistentArrayMap, PersistentHashMap, and PersistentHashSet. These test the time to run vec on a PHS or PHM of the given size. All timings in nanoseconds.

|| coll || size || 1.7.0-alpha4 || 1.7.0-alpha5 || alpha5 + patch || alpha5 + patch / alpha5 ||
| PHS | 4 | 236 | 406 | 204 | 0.86 |
| PHS | 16 | 857 | 896 | 382 | 0.45 |
| PHS | 64 | 3637 | 3832 | 1723 | 0.47 |
| PHS | 256 | 14235 | 14672 | 6525 | 0.46 |
| PHS | 1024 | 67743 | 68857 | 44654 | 0.66 |
| PHM | 4 | 112 | 232 | 232 | 2.07 |
| PHM | 16 | 550 | 832 | 442 | 0.80 |
| PHM | 64 | 3014 | 3155 | 2014 | 0.67 |
| PHM | 256 | 11661 | 12082 | 7522 | 0.65 |
| PHM | 1024 | 57388 | 59787 | 44240 | 0.77 |

I also ran a set of tests just on reduce with reduce-kv for comparison (reduce-kv uses a different unaffected reduction path so it's a good baseline for comparison).

|| expr || a-set / a-map size || 1.6.0 || 1.7.0-alpha5 (ns) || 1.7.0-alpha5 + patch (ns) || patch / alpha5 || patch / 1.6 ||
| (reduce + 0 a-set) | 4 | 171 | 241 | 114 | 0.47 | 0.67 |
| (reduce + 0 a-set) | 16 | 663 | 826 | 395 | 0.48 | 0.60 |
| (reduce + 0 a-set) | 64 | 3637 | 4456 | 2361 | 0.53 | 0.65 |
| (reduce + 0 a-set) | 256 | 14772 | 16158 | 8872 | 0.55 | 0.60 |
| (reduce + 0 a-set) | 1024 | 72548 | 79010 | 49626 | 0.63 | 0.68 |
| (reduce + 0 a-set) | 16384 | 1197962 | 1234286 | 729335 | 0.59 | 0.61 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 4 | 69 | 103 | 104 | 1.01 | 1.51 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 16 | 640 | 752 | 506 | 0.67 | 0.79 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 64 | 2861 | 3238 | 2388 | 0.74 | 0.83 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 256 | 11998 | 12848 | 9526 | 0.74 | 0.79 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 1024 | 59650 | 61913 | 54717 | 0.88 | 0.92 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 16384 | 982317 | 969168 | 837842 | 0.86 | 0.85 |
| (reducekv #(%1 %3) 0 a-map) | 4 | 58 | 62 | 60 | 0.97 | 1.03 |
| (reducekv #(%1 %3) 0 a-map) | 16 | 233 | 250 | 248 | 0.99 | 1.06 |
| (reducekv #(%1 %3) 0 a-map) | 64 | 1477 | 1525 | 1442 | 0.95 | 0.98 |
| (reducekv #(%1 %3) 0 a-map) | 256 | 5470 | 5258 | 5201 | 0.99 | 0.95 |
| (reducekv #(%1 %3) 0 a-map) | 1024 | 27344 | 27442 | 27410 | 1.00 | 1.00 |
| (reducekv #(%1 %3) 0 a-map) | 16384 | 399591 | 397090 | 396267 | 1.00 | 0.99 |

*Patch:* clj-1499-v10.patch

*Screened by:*
Add support for direct iterators instead of seq-based iterators for non-seq collections that use SeqIterator.

Patch adds support for direct iterators on the following (removing use of SeqIterator):
* PersistentHashMap - new internal iterator (~20% faster)
* APersistentSet - use internal map impl iterator (~5% faster)
* PersistentQueue
* PersistentStructMap
* records (in core_deftype.clj)

Patch does not change use of SeqIterator in:
* LazyTransformer$MultiStepper (not sure if this could be changed)
* ASeq
* LazySeq

In preparation for use in CLJ-1602, there is also a new IMapIterable interface that allows a map to publish direct Iterators of keys and values (without creating and pulling apart MapEntry objs). PersistentHashMap and PersistentArrayMap implement it right now and PersistentHashSet will check for and use the direct key iterator if possible.

*Performance:*

I re-ran the set of tests from CLJ-1546 for vec improvements which use these new iterators for PersistentArrayMap, PersistentHashMap, and PersistentHashSet. These test the time to run vec on a PHS or PHM of the given size. All timings in nanoseconds.

|| coll || size || 1.7.0-alpha4 || 1.7.0-alpha5 || alpha5 + patch || alpha5 + patch / alpha5 ||
| PHS | 4 | 236 | 406 | 204 | 0.86 |
| PHS | 16 | 857 | 896 | 382 | 0.45 |
| PHS | 64 | 3637 | 3832 | 1723 | 0.47 |
| PHS | 256 | 14235 | 14672 | 6525 | 0.46 |
| PHS | 1024 | 67743 | 68857 | 44654 | 0.66 |
| PHM | 4 | 112 | 232 | 232 | 2.07 |
| PHM | 16 | 550 | 832 | 442 | 0.80 |
| PHM | 64 | 3014 | 3155 | 2014 | 0.67 |
| PHM | 256 | 11661 | 12082 | 7522 | 0.65 |
| PHM | 1024 | 57388 | 59787 | 44240 | 0.77 |

I also ran a set of tests just on reduce with reduce-kv for comparison (reduce-kv uses a different unaffected reduction path so it's a good baseline for comparison).

|| expr || a-set / a-map size || 1.6.0 || 1.7.0-alpha5 (ns) || 1.7.0-alpha5 + patch (ns) || patch / alpha5 || patch / 1.6 ||
| (reduce + 0 a-set) | 4 | 171 | 241 | 114 | 0.47 | 0.67 |
| (reduce + 0 a-set) | 16 | 663 | 826 | 395 | 0.48 | 0.60 |
| (reduce + 0 a-set) | 64 | 3637 | 4456 | 2361 | 0.53 | 0.65 |
| (reduce + 0 a-set) | 256 | 14772 | 16158 | 8872 | 0.55 | 0.60 |
| (reduce + 0 a-set) | 1024 | 72548 | 79010 | 49626 | 0.63 | 0.68 |
| (reduce + 0 a-set) | 16384 | 1197962 | 1234286 | 729335 | 0.59 | 0.61 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 4 | 69 | 103 | 104 | 1.01 | 1.51 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 16 | 640 | 752 | 506 | 0.67 | 0.79 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 64 | 2861 | 3238 | 2388 | 0.74 | 0.83 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 256 | 11998 | 12848 | 9526 | 0.74 | 0.79 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 1024 | 59650 | 61913 | 54717 | 0.88 | 0.92 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 16384 | 982317 | 969168 | 837842 | 0.86 | 0.85 |
| (reducekv #(%1 %3) 0 a-map) | 4 | 58 | 62 | 60 | 0.97 | 1.03 |
| (reducekv #(%1 %3) 0 a-map) | 16 | 233 | 250 | 248 | 0.99 | 1.06 |
| (reducekv #(%1 %3) 0 a-map) | 64 | 1477 | 1525 | 1442 | 0.95 | 0.98 |
| (reducekv #(%1 %3) 0 a-map) | 256 | 5470 | 5258 | 5201 | 0.99 | 0.95 |
| (reducekv #(%1 %3) 0 a-map) | 1024 | 27344 | 27442 | 27410 | 1.00 | 1.00 |
| (reducekv #(%1 %3) 0 a-map) | 16384 | 399591 | 397090 | 396267 | 1.00 | 0.99 |

*Patch:* clj-1499-v11.patch

*Screened by:*
Fogus made changes -
Assignee Alex Miller [ alexmiller ] Fogus [ fogus ]
Hide
Fogus added a comment -

Added a motivation section to the ticket.

Show
Fogus added a comment - Added a motivation section to the ticket.
Fogus made changes -
Description Add support for direct iterators instead of seq-based iterators for non-seq collections that use SeqIterator.

Patch adds support for direct iterators on the following (removing use of SeqIterator):
* PersistentHashMap - new internal iterator (~20% faster)
* APersistentSet - use internal map impl iterator (~5% faster)
* PersistentQueue
* PersistentStructMap
* records (in core_deftype.clj)

Patch does not change use of SeqIterator in:
* LazyTransformer$MultiStepper (not sure if this could be changed)
* ASeq
* LazySeq

In preparation for use in CLJ-1602, there is also a new IMapIterable interface that allows a map to publish direct Iterators of keys and values (without creating and pulling apart MapEntry objs). PersistentHashMap and PersistentArrayMap implement it right now and PersistentHashSet will check for and use the direct key iterator if possible.

*Performance:*

I re-ran the set of tests from CLJ-1546 for vec improvements which use these new iterators for PersistentArrayMap, PersistentHashMap, and PersistentHashSet. These test the time to run vec on a PHS or PHM of the given size. All timings in nanoseconds.

|| coll || size || 1.7.0-alpha4 || 1.7.0-alpha5 || alpha5 + patch || alpha5 + patch / alpha5 ||
| PHS | 4 | 236 | 406 | 204 | 0.86 |
| PHS | 16 | 857 | 896 | 382 | 0.45 |
| PHS | 64 | 3637 | 3832 | 1723 | 0.47 |
| PHS | 256 | 14235 | 14672 | 6525 | 0.46 |
| PHS | 1024 | 67743 | 68857 | 44654 | 0.66 |
| PHM | 4 | 112 | 232 | 232 | 2.07 |
| PHM | 16 | 550 | 832 | 442 | 0.80 |
| PHM | 64 | 3014 | 3155 | 2014 | 0.67 |
| PHM | 256 | 11661 | 12082 | 7522 | 0.65 |
| PHM | 1024 | 57388 | 59787 | 44240 | 0.77 |

I also ran a set of tests just on reduce with reduce-kv for comparison (reduce-kv uses a different unaffected reduction path so it's a good baseline for comparison).

|| expr || a-set / a-map size || 1.6.0 || 1.7.0-alpha5 (ns) || 1.7.0-alpha5 + patch (ns) || patch / alpha5 || patch / 1.6 ||
| (reduce + 0 a-set) | 4 | 171 | 241 | 114 | 0.47 | 0.67 |
| (reduce + 0 a-set) | 16 | 663 | 826 | 395 | 0.48 | 0.60 |
| (reduce + 0 a-set) | 64 | 3637 | 4456 | 2361 | 0.53 | 0.65 |
| (reduce + 0 a-set) | 256 | 14772 | 16158 | 8872 | 0.55 | 0.60 |
| (reduce + 0 a-set) | 1024 | 72548 | 79010 | 49626 | 0.63 | 0.68 |
| (reduce + 0 a-set) | 16384 | 1197962 | 1234286 | 729335 | 0.59 | 0.61 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 4 | 69 | 103 | 104 | 1.01 | 1.51 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 16 | 640 | 752 | 506 | 0.67 | 0.79 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 64 | 2861 | 3238 | 2388 | 0.74 | 0.83 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 256 | 11998 | 12848 | 9526 | 0.74 | 0.79 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 1024 | 59650 | 61913 | 54717 | 0.88 | 0.92 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 16384 | 982317 | 969168 | 837842 | 0.86 | 0.85 |
| (reducekv #(%1 %3) 0 a-map) | 4 | 58 | 62 | 60 | 0.97 | 1.03 |
| (reducekv #(%1 %3) 0 a-map) | 16 | 233 | 250 | 248 | 0.99 | 1.06 |
| (reducekv #(%1 %3) 0 a-map) | 64 | 1477 | 1525 | 1442 | 0.95 | 0.98 |
| (reducekv #(%1 %3) 0 a-map) | 256 | 5470 | 5258 | 5201 | 0.99 | 0.95 |
| (reducekv #(%1 %3) 0 a-map) | 1024 | 27344 | 27442 | 27410 | 1.00 | 1.00 |
| (reducekv #(%1 %3) 0 a-map) | 16384 | 399591 | 397090 | 396267 | 1.00 | 0.99 |

*Patch:* clj-1499-v11.patch

*Screened by:*
*Motivation:*

Currently, the process of reducing over a map or set involves converting them to seqs. This action thus causes more intermediate
objects than we'd like. Therefore, we'd like for reduce to be more efficient about the way that it reduces over these types. One
way is for reduction to use the types' core collections while another way is to instead use a smart iterator
type that abstracts the direct operation.

*Solution*

Add support for direct iterators instead of seq-based iterators for non-seq collections that use SeqIterator.

Patch adds support for direct iterators on the following (removing use of SeqIterator):
* PersistentHashMap - new internal iterator (~20% faster)
* APersistentSet - use internal map impl iterator (~5% faster)
* PersistentQueue
* PersistentStructMap
* records (in core_deftype.clj)

Patch does not change use of SeqIterator in:
* LazyTransformer$MultiStepper (not sure if this could be changed)
* ASeq
* LazySeq

In preparation for use in CLJ-1602, there is also a new IMapIterable interface that allows a map to publish direct Iterators of keys and values (without creating and pulling apart MapEntry objs). PersistentHashMap and PersistentArrayMap implement it right now and PersistentHashSet will check for and use the direct key iterator if possible.

*Performance:*

I re-ran the set of tests from CLJ-1546 for vec improvements which use these new iterators for PersistentArrayMap, PersistentHashMap, and PersistentHashSet. These test the time to run vec on a PHS or PHM of the given size. All timings in nanoseconds.

|| coll || size || 1.7.0-alpha4 || 1.7.0-alpha5 || alpha5 + patch || alpha5 + patch / alpha5 ||
| PHS | 4 | 236 | 406 | 204 | 0.86 |
| PHS | 16 | 857 | 896 | 382 | 0.45 |
| PHS | 64 | 3637 | 3832 | 1723 | 0.47 |
| PHS | 256 | 14235 | 14672 | 6525 | 0.46 |
| PHS | 1024 | 67743 | 68857 | 44654 | 0.66 |
| PHM | 4 | 112 | 232 | 232 | 2.07 |
| PHM | 16 | 550 | 832 | 442 | 0.80 |
| PHM | 64 | 3014 | 3155 | 2014 | 0.67 |
| PHM | 256 | 11661 | 12082 | 7522 | 0.65 |
| PHM | 1024 | 57388 | 59787 | 44240 | 0.77 |

I also ran a set of tests just on reduce with reduce-kv for comparison (reduce-kv uses a different unaffected reduction path so it's a good baseline for comparison).

|| expr || a-set / a-map size || 1.6.0 || 1.7.0-alpha5 (ns) || 1.7.0-alpha5 + patch (ns) || patch / alpha5 || patch / 1.6 ||
| (reduce + 0 a-set) | 4 | 171 | 241 | 114 | 0.47 | 0.67 |
| (reduce + 0 a-set) | 16 | 663 | 826 | 395 | 0.48 | 0.60 |
| (reduce + 0 a-set) | 64 | 3637 | 4456 | 2361 | 0.53 | 0.65 |
| (reduce + 0 a-set) | 256 | 14772 | 16158 | 8872 | 0.55 | 0.60 |
| (reduce + 0 a-set) | 1024 | 72548 | 79010 | 49626 | 0.63 | 0.68 |
| (reduce + 0 a-set) | 16384 | 1197962 | 1234286 | 729335 | 0.59 | 0.61 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 4 | 69 | 103 | 104 | 1.01 | 1.51 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 16 | 640 | 752 | 506 | 0.67 | 0.79 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 64 | 2861 | 3238 | 2388 | 0.74 | 0.83 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 256 | 11998 | 12848 | 9526 | 0.74 | 0.79 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 1024 | 59650 | 61913 | 54717 | 0.88 | 0.92 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 16384 | 982317 | 969168 | 837842 | 0.86 | 0.85 |
| (reducekv #(%1 %3) 0 a-map) | 4 | 58 | 62 | 60 | 0.97 | 1.03 |
| (reducekv #(%1 %3) 0 a-map) | 16 | 233 | 250 | 248 | 0.99 | 1.06 |
| (reducekv #(%1 %3) 0 a-map) | 64 | 1477 | 1525 | 1442 | 0.95 | 0.98 |
| (reducekv #(%1 %3) 0 a-map) | 256 | 5470 | 5258 | 5201 | 0.99 | 0.95 |
| (reducekv #(%1 %3) 0 a-map) | 1024 | 27344 | 27442 | 27410 | 1.00 | 1.00 |
| (reducekv #(%1 %3) 0 a-map) | 16384 | 399591 | 397090 | 396267 | 1.00 | 0.99 |

*Patch:* clj-1499-v11.patch

*Screened by:*
Fogus made changes -
Approval Vetted [ 10003 ] Screened [ 10004 ]
Hide
Rich Hickey added a comment -

Any reason why MAKE_ENTRY/KEY/VAL are not final?

Show
Rich Hickey added a comment - Any reason why MAKE_ENTRY/KEY/VAL are not final?
Rich Hickey made changes -
Approval Screened [ 10004 ] Incomplete [ 10006 ]
Hide
Alex Miller added a comment -

Nope, just an oversight. Will fix.

Show
Alex Miller added a comment - Nope, just an oversight. Will fix.
Hide
Alex Miller added a comment -

New -v12 patch is identical except makes MAKE_ENTRY, MAKE_KEY, MAKE_VAL final.

Show
Alex Miller added a comment - New -v12 patch is identical except makes MAKE_ENTRY, MAKE_KEY, MAKE_VAL final.
Alex Miller made changes -
Attachment clj-1499-v12.patch [ 13896 ]
Description *Motivation:*

Currently, the process of reducing over a map or set involves converting them to seqs. This action thus causes more intermediate
objects than we'd like. Therefore, we'd like for reduce to be more efficient about the way that it reduces over these types. One
way is for reduction to use the types' core collections while another way is to instead use a smart iterator
type that abstracts the direct operation.

*Solution*

Add support for direct iterators instead of seq-based iterators for non-seq collections that use SeqIterator.

Patch adds support for direct iterators on the following (removing use of SeqIterator):
* PersistentHashMap - new internal iterator (~20% faster)
* APersistentSet - use internal map impl iterator (~5% faster)
* PersistentQueue
* PersistentStructMap
* records (in core_deftype.clj)

Patch does not change use of SeqIterator in:
* LazyTransformer$MultiStepper (not sure if this could be changed)
* ASeq
* LazySeq

In preparation for use in CLJ-1602, there is also a new IMapIterable interface that allows a map to publish direct Iterators of keys and values (without creating and pulling apart MapEntry objs). PersistentHashMap and PersistentArrayMap implement it right now and PersistentHashSet will check for and use the direct key iterator if possible.

*Performance:*

I re-ran the set of tests from CLJ-1546 for vec improvements which use these new iterators for PersistentArrayMap, PersistentHashMap, and PersistentHashSet. These test the time to run vec on a PHS or PHM of the given size. All timings in nanoseconds.

|| coll || size || 1.7.0-alpha4 || 1.7.0-alpha5 || alpha5 + patch || alpha5 + patch / alpha5 ||
| PHS | 4 | 236 | 406 | 204 | 0.86 |
| PHS | 16 | 857 | 896 | 382 | 0.45 |
| PHS | 64 | 3637 | 3832 | 1723 | 0.47 |
| PHS | 256 | 14235 | 14672 | 6525 | 0.46 |
| PHS | 1024 | 67743 | 68857 | 44654 | 0.66 |
| PHM | 4 | 112 | 232 | 232 | 2.07 |
| PHM | 16 | 550 | 832 | 442 | 0.80 |
| PHM | 64 | 3014 | 3155 | 2014 | 0.67 |
| PHM | 256 | 11661 | 12082 | 7522 | 0.65 |
| PHM | 1024 | 57388 | 59787 | 44240 | 0.77 |

I also ran a set of tests just on reduce with reduce-kv for comparison (reduce-kv uses a different unaffected reduction path so it's a good baseline for comparison).

|| expr || a-set / a-map size || 1.6.0 || 1.7.0-alpha5 (ns) || 1.7.0-alpha5 + patch (ns) || patch / alpha5 || patch / 1.6 ||
| (reduce + 0 a-set) | 4 | 171 | 241 | 114 | 0.47 | 0.67 |
| (reduce + 0 a-set) | 16 | 663 | 826 | 395 | 0.48 | 0.60 |
| (reduce + 0 a-set) | 64 | 3637 | 4456 | 2361 | 0.53 | 0.65 |
| (reduce + 0 a-set) | 256 | 14772 | 16158 | 8872 | 0.55 | 0.60 |
| (reduce + 0 a-set) | 1024 | 72548 | 79010 | 49626 | 0.63 | 0.68 |
| (reduce + 0 a-set) | 16384 | 1197962 | 1234286 | 729335 | 0.59 | 0.61 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 4 | 69 | 103 | 104 | 1.01 | 1.51 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 16 | 640 | 752 | 506 | 0.67 | 0.79 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 64 | 2861 | 3238 | 2388 | 0.74 | 0.83 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 256 | 11998 | 12848 | 9526 | 0.74 | 0.79 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 1024 | 59650 | 61913 | 54717 | 0.88 | 0.92 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 16384 | 982317 | 969168 | 837842 | 0.86 | 0.85 |
| (reducekv #(%1 %3) 0 a-map) | 4 | 58 | 62 | 60 | 0.97 | 1.03 |
| (reducekv #(%1 %3) 0 a-map) | 16 | 233 | 250 | 248 | 0.99 | 1.06 |
| (reducekv #(%1 %3) 0 a-map) | 64 | 1477 | 1525 | 1442 | 0.95 | 0.98 |
| (reducekv #(%1 %3) 0 a-map) | 256 | 5470 | 5258 | 5201 | 0.99 | 0.95 |
| (reducekv #(%1 %3) 0 a-map) | 1024 | 27344 | 27442 | 27410 | 1.00 | 1.00 |
| (reducekv #(%1 %3) 0 a-map) | 16384 | 399591 | 397090 | 396267 | 1.00 | 0.99 |

*Patch:* clj-1499-v11.patch

*Screened by:*
*Motivation:*

Currently, the process of reducing over a map or set involves converting them to seqs. This action thus causes more intermediate objects than we'd like. Therefore, we'd like for reduce to be more efficient about the way that it reduces over these types. One way is for reduction to use the types' core collections while another way is to instead use a smart iterator type that abstracts the direct operation.

*Solution*

Add support for direct iterators instead of seq-based iterators for non-seq collections that use SeqIterator.

Patch adds support for direct iterators on the following (removing use of SeqIterator):
* PersistentHashMap - new internal iterator (~20% faster)
* APersistentSet - use internal map impl iterator (~5% faster)
* PersistentQueue
* PersistentStructMap
* records (in core_deftype.clj)

Patch does not change use of SeqIterator in:
* LazyTransformer$MultiStepper (not sure if this could be changed)
* ASeq
* LazySeq

In preparation for use in CLJ-1602, there is also a new IMapIterable interface that allows a map to publish direct Iterators of keys and values (without creating and pulling apart MapEntry objs). PersistentHashMap and PersistentArrayMap implement it right now and PersistentHashSet will check for and use the direct key iterator if possible.

*Performance:*

I re-ran the set of tests from CLJ-1546 for vec improvements which use these new iterators for PersistentArrayMap, PersistentHashMap, and PersistentHashSet. These test the time to run vec on a PHS or PHM of the given size. All timings in nanoseconds.

|| coll || size || 1.7.0-alpha4 || 1.7.0-alpha5 || alpha5 + patch || alpha5 + patch / alpha5 ||
| PHS | 4 | 236 | 406 | 204 | 0.86 |
| PHS | 16 | 857 | 896 | 382 | 0.45 |
| PHS | 64 | 3637 | 3832 | 1723 | 0.47 |
| PHS | 256 | 14235 | 14672 | 6525 | 0.46 |
| PHS | 1024 | 67743 | 68857 | 44654 | 0.66 |
| PHM | 4 | 112 | 232 | 232 | 2.07 |
| PHM | 16 | 550 | 832 | 442 | 0.80 |
| PHM | 64 | 3014 | 3155 | 2014 | 0.67 |
| PHM | 256 | 11661 | 12082 | 7522 | 0.65 |
| PHM | 1024 | 57388 | 59787 | 44240 | 0.77 |

I also ran a set of tests just on reduce with reduce-kv for comparison (reduce-kv uses a different unaffected reduction path so it's a good baseline for comparison).

|| expr || a-set / a-map size || 1.6.0 || 1.7.0-alpha5 (ns) || 1.7.0-alpha5 + patch (ns) || patch / alpha5 || patch / 1.6 ||
| (reduce + 0 a-set) | 4 | 171 | 241 | 114 | 0.47 | 0.67 |
| (reduce + 0 a-set) | 16 | 663 | 826 | 395 | 0.48 | 0.60 |
| (reduce + 0 a-set) | 64 | 3637 | 4456 | 2361 | 0.53 | 0.65 |
| (reduce + 0 a-set) | 256 | 14772 | 16158 | 8872 | 0.55 | 0.60 |
| (reduce + 0 a-set) | 1024 | 72548 | 79010 | 49626 | 0.63 | 0.68 |
| (reduce + 0 a-set) | 16384 | 1197962 | 1234286 | 729335 | 0.59 | 0.61 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 4 | 69 | 103 | 104 | 1.01 | 1.51 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 16 | 640 | 752 | 506 | 0.67 | 0.79 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 64 | 2861 | 3238 | 2388 | 0.74 | 0.83 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 256 | 11998 | 12848 | 9526 | 0.74 | 0.79 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 1024 | 59650 | 61913 | 54717 | 0.88 | 0.92 |
| (reduce #(+ %1 (val %2)) 0 a-map) | 16384 | 982317 | 969168 | 837842 | 0.86 | 0.85 |
| (reducekv #(%1 %3) 0 a-map) | 4 | 58 | 62 | 60 | 0.97 | 1.03 |
| (reducekv #(%1 %3) 0 a-map) | 16 | 233 | 250 | 248 | 0.99 | 1.06 |
| (reducekv #(%1 %3) 0 a-map) | 64 | 1477 | 1525 | 1442 | 0.95 | 0.98 |
| (reducekv #(%1 %3) 0 a-map) | 256 | 5470 | 5258 | 5201 | 0.99 | 0.95 |
| (reducekv #(%1 %3) 0 a-map) | 1024 | 27344 | 27442 | 27410 | 1.00 | 1.00 |
| (reducekv #(%1 %3) 0 a-map) | 16384 | 399591 | 397090 | 396267 | 1.00 | 0.99 |

*Patch:* clj-1499-v12.patch

*Screened by:*
Approval Incomplete [ 10006 ] Vetted [ 10003 ]
Hide
Fogus added a comment -

Screened latest v12 (with added finals) and would be happy to work in this code if the need arose. Additionally, with the added "motivation" the ticket and its solution makes more sense.

Show
Fogus added a comment - Screened latest v12 (with added finals) and would be happy to work in this code if the need arose. Additionally, with the added "motivation" the ticket and its solution makes more sense.
Fogus made changes -
Assignee Fogus [ fogus ]
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 (2)

Dates

  • Created:
    Updated:
    Resolved: