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

Alex Miller made changes -
Field Original Value New Value
Approval Triaged [ 10120 ]
Jozef Wagner made changes -
Attachment clj-1387.diff [ 12884 ]
Jozef Wagner made changes -
Patch Code and Test [ 10002 ]
Assignee Jozef Wagner [ wagjo ]
Rich Hickey made changes -
Approval Triaged [ 10120 ] Vetted [ 10003 ]
Fix Version/s Release 1.6 [ 10157 ]
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.
Alex Miller made changes -
Description Larger hash maps have nested INodes. As kvreduce implementations in INodes dereference reduced objects, parent INodes continue to reduce.
{code}
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
{code}
Dereferencing reduced objects should happen only PersistentHashMap/kvreduce
Larger hash maps have nested INodes. As kvreduce implementations in INodes dereference reduced objects, parent INodes continue to reduce.
{code}
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
{code}

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

*Patch:* clj-1387-v2.diff
*Screened-by:*

Attachment clj-1387-v2.diff [ 12885 ]
Summary reduce-kv on hash map ignores reduced objects reduce-kv on hash map ignores reduced objects in large maps
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.
Alex Miller made changes -
Attachment clj-1387-v3.diff [ 12891 ]
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.
Alex Miller made changes -
Description Larger hash maps have nested INodes. As kvreduce implementations in INodes dereference reduced objects, parent INodes continue to reduce.
{code}
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
{code}

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

*Patch:* clj-1387-v2.diff
*Screened-by:*

Larger hash maps have nested INodes. As kvreduce implementations in INodes dereference reduced objects, parent INodes continue to reduce.
{code}
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
{code}

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

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

Rich Hickey made changes -
Approval Vetted [ 10003 ] Ok [ 10007 ]
Jozef Wagner made changes -
Comment [ There's a 'return init;' right after the closing brace. Is it a problem for JIT or do you just consider it a bad style? ]
Stuart Halloway made changes -
Resolution Completed [ 1 ]
Status Open [ 1 ] Closed [ 6 ]

People

Vote (0)
Watch (3)

Dates

  • Created:
    Updated:
    Resolved: