Clojure

reduce-kv fails on subvec

Details

  • Type: Defect Defect
  • Status: Open Open
  • Priority: Minor Minor
  • Resolution: Unresolved
  • Affects Version/s: Release 1.9
  • Fix Version/s: None
  • Component/s: None
  • Labels:
  • Patch:
    Code and Test
  • Approval:
    Triaged

Description

reduce-kv works as expected on vectors with the element index passed as the "key" argument. However, it fails with a subvec because clojure.lang.APersistentVector$SubVector does not implement IKVReduce.

(reduce-kv + 0 [1 2 3])
9

(reduce-kv + 0 (subvec [1 2 3] 1))
IllegalArgumentException No implementation of method: :kv-reduce of protocol: #'clojure.core.protocols/IKVReduce found for class: clojure.lang.APersistentVector$SubVector clojure.core/-cache-protocol-fn (core_deftype.clj:583)

One work around is to copy the subvec into a vector:

(reduce-kv + 0 (into [] (subvec [1 2 3] 1)))
6

Note however, the `vec` would not work here. Since Clojure 1.7, vec will return a subvec rather than copying.

(reduce-kv + 0 (vec (subvec [1 2 3] 1)))
IllegalArgumentException No implementation of method: :kv-reduce of protocol: #'clojure.core.protocols/IKVReduce found for class: clojure.lang.APersistentVector$SubVector clojure.core/-cache-protocol-fn (core_deftype.clj:583)

The Clojure user expects that a subvector supports all of the normal vector operations and this exception is confusing. The cause of the problem is that subvec returns a clojure.lang.APersistentVector$SubVector which does not implement clojure.lang.IKVReduce. PersistentVector inherits from APersistentVector and implements IKVReduce but SubVector doesn't get any IKVReduce support. This was probably just an oversight.

There are two patches attached. The first fixed the problem by extending the IKVReduce protocol in core.clj. The second, as suggested by Alex Miller, just adds the Java implementation of the IKVReduce interface directly to APersistentVector$SubVector. The same test is included in both patches.

Activity

Hide
Steve Miner added a comment - - edited

Here is my current work-around:

(extend-type clojure.lang.APersistentVector$SubVector
  clojure.core.protocols/IKVReduce
  (kv-reduce [subv f init]
    (transduce (map-indexed vector)
               (fn ([ret] ret) ([ret [k v]] (f ret k v)))
               init
               subv)))

In my tests it was usually faster to copy the subvec into a regular vector but I like the look of the transduce fix. It would probably be faster to add a native Java implementation in APersistentVector.java. I'm willing to do the work if the Clojure/core team wants a patch.

Show
Steve Miner added a comment - - edited Here is my current work-around:
(extend-type clojure.lang.APersistentVector$SubVector
  clojure.core.protocols/IKVReduce
  (kv-reduce [subv f init]
    (transduce (map-indexed vector)
               (fn ([ret] ret) ([ret [k v]] (f ret k v)))
               init
               subv)))
In my tests it was usually faster to copy the subvec into a regular vector but I like the look of the transduce fix. It would probably be faster to add a native Java implementation in APersistentVector.java. I'm willing to do the work if the Clojure/core team wants a patch.
Hide
Steve Miner added a comment -

Revised work-around using more interop for better performance. Comparable to the speed of normal vector reduce-kv.

(when-not (satisfies?   clojure.core.protocols/IKVReduce (subvec [1] 0))
  (extend-type clojure.lang.APersistentVector$SubVector
    clojure.core.protocols/IKVReduce
    (kv-reduce
      [subv f init]
      (let [cnt (.count subv)]
        (loop [k 0 ret init]
          (if (< k cnt)
            (let [val (.nth subv k)
                  ret (f ret k val)]
              (if (reduced? ret)
                @ret
                (recur (inc k) ret)))
            ret))))))
Show
Steve Miner added a comment - Revised work-around using more interop for better performance. Comparable to the speed of normal vector reduce-kv.
(when-not (satisfies?   clojure.core.protocols/IKVReduce (subvec [1] 0))
  (extend-type clojure.lang.APersistentVector$SubVector
    clojure.core.protocols/IKVReduce
    (kv-reduce
      [subv f init]
      (let [cnt (.count subv)]
        (loop [k 0 ret init]
          (if (< k cnt)
            (let [val (.nth subv k)
                  ret (f ret k val)]
              (if (reduced? ret)
                @ret
                (recur (inc k) ret)))
            ret))))))
Hide
Steve Miner added a comment -

support IKVReduce for SubVector

Show
Steve Miner added a comment - support IKVReduce for SubVector
Hide
Steve Miner added a comment -

Patch also adds test for reduce-kv on regular vector and subvector.

Show
Steve Miner added a comment - Patch also adds test for reduce-kv on regular vector and subvector.
Hide
Alex Miller added a comment -

Why not implement IKVReduce directly in APersistentVector$SubVector?

Show
Alex Miller added a comment - Why not implement IKVReduce directly in APersistentVector$SubVector?
Hide
Steve Miner added a comment -

Java implementation of IKVReduce on SubVector

Show
Steve Miner added a comment - Java implementation of IKVReduce on SubVector
Hide
Steve Miner added a comment -

Yes, that makes sense. I hesitated because I didn't want to rework the hierarchy to make SubVector a subclass of PersistentVector but that wasn't necessary to fix the bug. CLJ-2065-Support-IKVReduce-on-SubVector.patch is just the Java side, plus the same test.

Show
Steve Miner added a comment - Yes, that makes sense. I hesitated because I didn't want to rework the hierarchy to make SubVector a subclass of PersistentVector but that wasn't necessary to fix the bug. CLJ-2065-Support-IKVReduce-on-SubVector.patch is just the Java side, plus the same test.
Hide
Steve Miner added a comment -

Updated patch to inline nth() call, avoiding unnecessary bounds checking.

Show
Steve Miner added a comment - Updated patch to inline nth() call, avoiding unnecessary bounds checking.

People

Vote (0)
Watch (0)

Dates

  • Created:
    Updated: