Clojure

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

Details

  • Type: Enhancement Enhancement
  • Status: Open Open
  • Priority: Critical Critical
  • Resolution: Unresolved
  • Affects Version/s: Release 1.7
  • Fix Version/s: Release 1.7
  • Component/s: None
  • Labels:
    None
  • Patch:
    Code and Test
  • Approval:
    Vetted

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

  1. clj-1499-all.diff
    01/Oct/14 11:54 AM
    15 kB
    Alex Miller
  2. clj-1499-v2.diff
    29/Sep/14 10:26 PM
    10 kB
    Alex Miller
  3. clj-1499-v3.diff
    30/Sep/14 4:18 PM
    12 kB
    Alex Miller
  4. clj-1499-v6.diff
    02/Dec/14 3:03 PM
    16 kB
    Alex Miller
  5. defrecord-iterator.patch
    27/Sep/14 2:16 PM
    4 kB
    Ghadi Shayban
  6. defrecord-iterator-v2.diff
    30/Sep/14 7:30 PM
    3 kB
    Ghadi Shayban

Activity

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.
Hide
Alex Miller added a comment -

PHM patch

Show
Alex Miller added a comment - PHM patch
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.
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.
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.
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?
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.
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.

People

Vote (0)
Watch (2)

Dates

  • Created:
    Updated: