Clojure

reduce-kv on hash map ignores reduced objects in large maps

Details

  • Type: Defect Defect
  • Status: Closed Closed
  • Priority: Major Major
  • Resolution: Completed
  • Affects Version/s: Release 1.6
  • Fix Version/s: Release 1.6
  • Component/s: None
  • Labels:
    None
  • Environment:
    JRE 7
  • Patch:
    Code and Test
  • Approval:
    Ok

Description

Larger hash maps have nested INodes. As kvreduce implementations in INodes dereference reduced objects, parent INodes continue to reduce.

user=> (defn test-reduce-kv [m] (reduce-kv (fn [_ k v] (when (== 1 k) (reduced :foo))) nil m))
#'user/test-reduce-kv
user=> (test-reduce-kv (zipmap (range 3) (range 3)))
:foo
user=> (test-reduce-kv (zipmap (range 300) (range 300)))
nil

Dereferencing reduced objects should happen only PersistentHashMap/kvreduce - intermediate nodes should pass the Reduced object along.

Patch: clj-1387-v3.diff
Screened-by:

  1. clj-1387.diff
    18/Mar/14 8:46 AM
    2 kB
    Jozef Wagner
  2. clj-1387-v2.diff
    18/Mar/14 5:11 PM
    3 kB
    Alex Miller
  3. clj-1387-v3.diff
    21/Mar/14 9:03 AM
    3 kB
    Alex Miller

Activity

Hide
Alex Miller added a comment -

Added new version of patch that retains the return flow and doesn't fall through.

Show
Alex Miller added a comment - Added new version of patch that retains the return flow and doesn't fall through.
Hide
Rich Hickey added a comment -

if(root != null){ - return root.kvreduce(f,init); + init = root.kvreduce(f,init); + if(RT.isReduced(init)) + return ((IDeref)init).deref(); }

Turns code that always had a return into code that sometimes does.

Show
Rich Hickey added a comment - if(root != null){ - return root.kvreduce(f,init); + init = root.kvreduce(f,init); + if(RT.isReduced(init)) + return ((IDeref)init).deref(); } Turns code that always had a return into code that sometimes does.
Hide
Alex Miller added a comment -

I updated the patch to use a generative test that will try many combinations of map size and the reduced index to bail out on. This test failed before applying the source patch and passes with it.

Show
Alex Miller added a comment - I updated the patch to use a generative test that will try many combinations of map size and the reduced index to bail out on. This test failed before applying the source patch and passes with it.

People

Vote (0)
Watch (3)

Dates

  • Created:
    Updated:
    Resolved: