Clojure

vals and keys return values should implement IReduceInit or Iterable

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

Background: clojure.core/keys calls RT.keys(Object) calls APersistentMap.KeySeq.create(ISeq). RT.keys() creates a sequence (of Map.Entry objects) and KeySeq just wraps it, calling .keyValue(). There is an equivalent vals -> RT.vals() -> ValSeq path. Both of these seq impls extend ASeq and provide Iterable implementations via SeqIterator (iterator wrapped over the seq).

Approach: The important thing here is to avoid creating the sequence and instead directly iterate/reduce over the map. Noting that CLJ-1499 provides support for making PHM directly Iterable and that KeySeq/ValSeq already implement Iterable, I chose to focus on making the instances returned from keys and vals support Iterable directly on the underlying map instead of via the seq.

RT.keys()/vals() created the seq and passed it to KeySeq/ValSeq which made it too late to directly cover the original map iterator. There are a few places that rely on passing a seq of Map.Entry to keys/vals (not just a map instance), so I check for IPersistentMap and in that case pass it directly to a new KeySeq factory method that remembers both the Iterable and the ISeq. There is also support in here for using a direct key/value iterator via IMapIterable as introduced in CLJ-1499.

Questions/notes:

  • Could potentially check for Map or Iterable instead of IPersistentMap in RT.keys()/vals(). Not sure how common it is to pass normal Java maps to keys/vals.
  • The direct Iterable support vanishes once you move off the head of the keys or vals seq. So (rest (keys map)) does not have Iterable support. This is not really possible unless you hold an Iterator and advance it along with the seq, but that seemed to introduce all sorts of possibilities for badness. Since maps are unordered, it seems weird to rely on any ordering or processing only parts of any map, so I suspect doing this would be quite rare.
  • This patch depends on CLJ-1499 for IMapIterable.

Performance: I tested perf using criterium to benchmark as follows:

(use 'criterium.core)
(def m (zipmap (range 1000) (range 1000)))
(bench (reduce + (keys m)))
(bench (reduce + (vals m)))
(bench expr) 1.6.0 1.7.0-alpha5 alpha5 + clj-1499 + patch
(reduce + (keys m)) 69 µs 73 µs 44 µs
(reduce + (vals m)) 75 µs 77 µs 50 µs

Tests:

  • I added some basic tests for subseq and rsubseq as those both rely on the somewhat special behavior of keys accepting a seqable of Map.Entry objects (not just a map itself). There were no other tests for subseq or rsubseq already present.
  • Some coverage from CLJ-1499 tests d760db
  • Show that metadata works on keys/vals
  • Show that iterator works correctly after you step off the head of the seq, invalidating the iterable
  • Show that the fallthrough branch of iterator works (from PersistentTreeMap)

Patch: clj-1602-6.diff

Screened by:

  • the changes in CollReduce are unlikely to stand but are currently essential
  1. clj-1602.diff
    03/Dec/14 5:19 PM
    6 kB
    Alex Miller
  2. clj-1602-2.diff
    03/Dec/14 11:24 PM
    9 kB
    Alex Miller
  3. clj-1602-3.diff
    04/Dec/14 1:36 PM
    10 kB
    Alex Miller
  4. clj-1602-4.diff
    14/Jan/15 5:40 PM
    8 kB
    Alex Miller
  5. clj-1602-5.diff
    22/Mar/15 8:16 AM
    8 kB
    Stuart Halloway
  6. clj-1602-6.diff
    23/Mar/15 1:51 PM
    9 kB
    Alex Miller

Activity

Hide
Alex Miller added a comment -

Could leverage CLJ-1499 for the bulk of this, may pull that back from 1.8 into 1.7. Waiting on further work till that's answered.

Show
Alex Miller added a comment - Could leverage CLJ-1499 for the bulk of this, may pull that back from 1.8 into 1.7. Waiting on further work till that's answered.
Hide
Alex Miller added a comment -

I also have a patch that extends the CLJ-1499 iterators to support providing both key and val iterators that do not require creating and unpacking a Map.Entry. Unfortunately I only saw times that were ~48 µs on the perf benchmark in the description, so it's not a huge benefit (short-lived object allocation is cheap).

Show
Alex Miller added a comment - I also have a patch that extends the CLJ-1499 iterators to support providing both key and val iterators that do not require creating and unpacking a Map.Entry. Unfortunately I only saw times that were ~48 µs on the perf benchmark in the description, so it's not a huge benefit (short-lived object allocation is cheap).
Hide
Alex Miller added a comment -

waiting on 1499 mods

Show
Alex Miller added a comment - waiting on 1499 mods
Hide
Alex Miller added a comment -

Updated patch based on latest CLJ-1499-v10 patch.

Show
Alex Miller added a comment - Updated patch based on latest CLJ-1499-v10 patch.
Hide
Michael Blume added a comment -

I find it concerning that the v9 patch passed generative tests, shouldn't we have seen that?

Show
Michael Blume added a comment - I find it concerning that the v9 patch passed generative tests, shouldn't we have seen that?
Hide
Alex Miller added a comment -

Actually I did see it in the generative tests for this ticket so I moved those tests into the CLJ-1499 patch.

Show
Alex Miller added a comment - Actually I did see it in the generative tests for this ticket so I moved those tests into the CLJ-1499 patch.
Hide
Michael Blume added a comment -

Ah, cool =)

Show
Michael Blume added a comment - Ah, cool =)
Hide
Stuart Halloway added a comment -

clj-1602-5.diff merely updates -4 to apply on current master

Show
Stuart Halloway added a comment - clj-1602-5.diff merely updates -4 to apply on current master
Hide
Stuart Halloway added a comment -

requested some tests in the description

Show
Stuart Halloway added a comment - requested some tests in the description
Hide
Alex Miller added a comment -

Updated to -6 patch that adds the requested tests.

Show
Alex Miller added a comment - Updated to -6 patch that adds the requested tests.

People

Vote (0)
Watch (1)

Dates

  • Created:
    Updated:
    Resolved: