Clojure

Widen vec to take Iterable/IReduce

Details

  • Type: Enhancement Enhancement
  • Status: Closed Closed
  • Priority: Critical Critical
  • Resolution: Completed
  • Affects Version/s: Release 1.7
  • Fix Version/s: Release 1.7
  • Component/s: None
  • Labels:
    None
  • Patch:
    Code and Test
  • Approval:
    Ok

Description

These examples should work but do not:

Something Iterable but not IReduce:

user> (def i (eduction (map inc) (range 100)))
#'user/i
user> (instance? java.util.Collection i)
false
user> (instance? Iterable i)
true
user> (vec i)
RuntimeException Unable to convert: class clojure.core.Iteration to Object[]

Something IReduceInit but not Iterable:

user=> (vec
  (reify clojure.lang.IReduceInit
    (reduce [_ f start]
      (reduce f start (range 10)))))
RuntimeException Unable to convert: class user$reify__15 to Object[]

Proposal: Add PersistentVector.create(Iterable) and PersistentVector.create(IReduceInit) to efficiently create PVs from those. See also the blog post http://insideclojure.org/2015/01/07/vec-perf/.

For performance, vec has several cases:
1) (vec) if vector?: return new vector w/o meta - this matches prior behavior but has a constant cost of a few ns, rather than linear cost. If not a vector, spill to LazilyPersistentVector.create(Object).

2) (LPV) instanceof IReduceInit: Anything reducible can reduce itself fastest. Right now this has a big benefit for PersistentList. on 1.7.0-alpha4 with list of size 1024, into=28 seconds, vec=18 seconds. After patch, vec=7 seconds. As more things become IReduce, they'll take this path as well. This is also the branch that handles the new Eduction and IReduceInit cases.

3) (LPV) instanceof ISeq: If the coll is a sequence already, best to just walk it rather than build an iterator or array from it. This calls into PersistentVector.create(ISeq). That implementation now contains an optimization to build into an array and construct the PersistentVector directly from the array for sequences <= 32 elements (which is common). Once that threshold is reached, it switches to building with transients. The benchmark shows that the patch makes vec substantially faster for all seqs and even faster than into in some cases.

4) (LPV) instanceof Iterable: For all non-Clojure collections (ArrayList) and current non-IReduce Clojure collections (PHM, PHS), this is fastest path. Iterators are preferred to seqs as they do not cache or hold onto the values as they go by. The PV.create() for Iterable uses transients. Due to slightly more overhead, small maps and sets are slightly slower but this is largely fixed by CLJ-1499 which adds direct iterators. ArrayLists with <= 32 are special-cased - we can toArray() and construct the PV with a seeded node in this case. This type and size is particularly common in real code. Even so, very small ArrayLists are a bit slower than they were due to increased number of conditional checks I think.

5) (LPV) otherwise RT.toArray(): catches Map, String, Object[], primitive array, etc. The important ones here are the arrays - they are slightly slower on small arrays due to overhead of checking more cases above, but big arrays are significantly faster than they were.

In addition, there was one hard-coded path in the Compiler into PersistentVector.create() and I re-routed that through LazilyPersistentVector instead as that code is now the place to choose the fastest path logic.

Patch: clj-1546-6.patch, see numbers.png for perf comparison

Screened by: Stu

  1. clj-1546.patch
    02/Oct/14 9:36 AM
    2 kB
    Alex Miller
  2. clj-1546-2.patch
    14/Oct/14 9:56 AM
    3 kB
    Alex Miller
  3. clj-1546-3.patch
    24/Oct/14 9:52 AM
    4 kB
    Alex Miller
  4. clj-1546-4.patch
    13/Nov/14 4:14 PM
    5 kB
    Alex Miller
  5. clj-1546-5.patch
    25/Nov/14 10:07 AM
    6 kB
    Alex Miller
  6. clj-1546-6.patch
    07/Jan/15 12:24 AM
    7 kB
    Alex Miller
  1. numbers.png
    189 kB
    07/Jan/15 12:24 AM

Activity

Alex Miller made changes -
Field Original Value New Value
Fix Version/s Release 1.7 [ 10250 ]
Attachment clj-1546.patch [ 13382 ]
Approval Vetted [ 10003 ]
Patch Code [ 10001 ]
Alex Miller made changes -
Description This should work but does not:

{code}
user> (def i (iteration (map inc) (range 100)))
#'user/i
user> (instance? java.util.Collection i)
false
user> (instance? Iterable i)
true
user> (vec i)
RuntimeException Unable to convert: class clojure.core.Iteration to Object[]
{code}

*Proposal:* Add PersistentVector.create(Iterable) to efficiently create PV from Iterable. Add a case to vec to support "Iterable but not Collection" to call it.

*Patch:*

*Screened by:*
This should work but does not:

{code}
user> (def i (iteration (map inc) (range 100)))
#'user/i
user> (instance? java.util.Collection i)
false
user> (instance? Iterable i)
true
user> (vec i)
RuntimeException Unable to convert: class clojure.core.Iteration to Object[]
{code}

*Proposal:* Add PersistentVector.create(Iterable) to efficiently create PV from Iterable. Add a case to vec to support "Iterable but not Collection" to call it.

*Patch:* clj-1546.patch

*Screened by:*
Alex Miller made changes -
Approval Vetted [ 10003 ] Incomplete [ 10006 ]
Rich Hickey made changes -
Summary Widen vec to take Iterable Widen vec to take Iterable/IReduce
Alex Miller made changes -
Description This should work but does not:

{code}
user> (def i (iteration (map inc) (range 100)))
#'user/i
user> (instance? java.util.Collection i)
false
user> (instance? Iterable i)
true
user> (vec i)
RuntimeException Unable to convert: class clojure.core.Iteration to Object[]
{code}

*Proposal:* Add PersistentVector.create(Iterable) to efficiently create PV from Iterable. Add a case to vec to support "Iterable but not Collection" to call it.

*Patch:* clj-1546.patch

*Screened by:*
This should work but does not:

{code}
user> (def i (eduction (map inc) (range 100)))
#'user/i
user> (instance? java.util.Collection i)
false
user> (instance? Iterable i)
true
user> (vec i)
RuntimeException Unable to convert: class clojure.core.Iteration to Object[]
{code}

*Proposal:* Add PersistentVector.create(Iterable) to efficiently create PV from Iterable. Add a case to vec to support "Iterable but not Collection" to call it.

*Patch:* clj-1546.patch

*Screened by:*
Alex Miller made changes -
Description This should work but does not:

{code}
user> (def i (eduction (map inc) (range 100)))
#'user/i
user> (instance? java.util.Collection i)
false
user> (instance? Iterable i)
true
user> (vec i)
RuntimeException Unable to convert: class clojure.core.Iteration to Object[]
{code}

*Proposal:* Add PersistentVector.create(Iterable) to efficiently create PV from Iterable. Add a case to vec to support "Iterable but not Collection" to call it.

*Patch:* clj-1546.patch

*Screened by:*
These examples should work but does not:

Something Iterable but not IReduce:

{code}
user> (def i (eduction (map inc) (range 100)))
#'user/i
user> (instance? java.util.Collection i)
false
user> (instance? Iterable i)
true
user> (vec i)
RuntimeException Unable to convert: class clojure.core.Iteration to Object[]
{code}

Something IReduceInit but not Iterable:
{code}
user=> (vec
  (reify clojure.lang.IReduceInit
    (reduce [_ f start]
      (reduce f start (range 10)))))
RuntimeException Unable to convert: class user$reify__15 to Object[]
{code}

*Proposal:* Add PersistentVector.create(Iterable) to efficiently create PV from Iterable. Add a case to vec to support "Iterable but not Collection" to call it.

*Patch:* clj-1546.patch

*Screened by:*
Alex Miller made changes -
Attachment clj-1546-2.patch [ 13415 ]
Description These examples should work but does not:

Something Iterable but not IReduce:

{code}
user> (def i (eduction (map inc) (range 100)))
#'user/i
user> (instance? java.util.Collection i)
false
user> (instance? Iterable i)
true
user> (vec i)
RuntimeException Unable to convert: class clojure.core.Iteration to Object[]
{code}

Something IReduceInit but not Iterable:
{code}
user=> (vec
  (reify clojure.lang.IReduceInit
    (reduce [_ f start]
      (reduce f start (range 10)))))
RuntimeException Unable to convert: class user$reify__15 to Object[]
{code}

*Proposal:* Add PersistentVector.create(Iterable) to efficiently create PV from Iterable. Add a case to vec to support "Iterable but not Collection" to call it.

*Patch:* clj-1546.patch

*Screened by:*
These examples should work but does not:

Something Iterable but not IReduce:

{code}
user> (def i (eduction (map inc) (range 100)))
#'user/i
user> (instance? java.util.Collection i)
false
user> (instance? Iterable i)
true
user> (vec i)
RuntimeException Unable to convert: class clojure.core.Iteration to Object[]
{code}

Something IReduceInit but not Iterable:
{code}
user=> (vec
  (reify clojure.lang.IReduceInit
    (reduce [_ f start]
      (reduce f start (range 10)))))
RuntimeException Unable to convert: class user$reify__15 to Object[]
{code}

*Proposal:* Add PersistentVector.create(Iterable) to efficiently create PV from Iterable. Add a case to vec to support "Iterable but not Collection" to call it.

*Patch:* clj-1546-2.patch

*Screened by:*
Alex Miller made changes -
Approval Incomplete [ 10006 ] Vetted [ 10003 ]
Alex Miller made changes -
Attachment clj-1546-3.patch [ 13438 ]
Description These examples should work but does not:

Something Iterable but not IReduce:

{code}
user> (def i (eduction (map inc) (range 100)))
#'user/i
user> (instance? java.util.Collection i)
false
user> (instance? Iterable i)
true
user> (vec i)
RuntimeException Unable to convert: class clojure.core.Iteration to Object[]
{code}

Something IReduceInit but not Iterable:
{code}
user=> (vec
  (reify clojure.lang.IReduceInit
    (reduce [_ f start]
      (reduce f start (range 10)))))
RuntimeException Unable to convert: class user$reify__15 to Object[]
{code}

*Proposal:* Add PersistentVector.create(Iterable) to efficiently create PV from Iterable. Add a case to vec to support "Iterable but not Collection" to call it.

*Patch:* clj-1546-2.patch

*Screened by:*
These examples should work but does not:

Something Iterable but not IReduce:

{code}
user> (def i (eduction (map inc) (range 100)))
#'user/i
user> (instance? java.util.Collection i)
false
user> (instance? Iterable i)
true
user> (vec i)
RuntimeException Unable to convert: class clojure.core.Iteration to Object[]
{code}

Something IReduceInit but not Iterable:
{code}
user=> (vec
  (reify clojure.lang.IReduceInit
    (reduce [_ f start]
      (reduce f start (range 10)))))
RuntimeException Unable to convert: class user$reify__15 to Object[]
{code}

*Proposal:* Add PersistentVector.create(Iterable) and PersistentVector.create(IReduceInit) to efficiently create PVs from those. Add a number of cases to vec to support different cases.

*Patch:* clj-1546-3.patch

*Screened by:*
Patch Code [ 10001 ] Code and Test [ 10002 ]
Stuart Halloway made changes -
Description These examples should work but does not:

Something Iterable but not IReduce:

{code}
user> (def i (eduction (map inc) (range 100)))
#'user/i
user> (instance? java.util.Collection i)
false
user> (instance? Iterable i)
true
user> (vec i)
RuntimeException Unable to convert: class clojure.core.Iteration to Object[]
{code}

Something IReduceInit but not Iterable:
{code}
user=> (vec
  (reify clojure.lang.IReduceInit
    (reduce [_ f start]
      (reduce f start (range 10)))))
RuntimeException Unable to convert: class user$reify__15 to Object[]
{code}

*Proposal:* Add PersistentVector.create(Iterable) and PersistentVector.create(IReduceInit) to efficiently create PVs from those. Add a number of cases to vec to support different cases.

*Patch:* clj-1546-3.patch

*Screened by:*
These examples should work but does not:

Something Iterable but not IReduce:

{code}
user> (def i (eduction (map inc) (range 100)))
#'user/i
user> (instance? java.util.Collection i)
false
user> (instance? Iterable i)
true
user> (vec i)
RuntimeException Unable to convert: class clojure.core.Iteration to Object[]
{code}

Something IReduceInit but not Iterable:
{code}
user=> (vec
  (reify clojure.lang.IReduceInit
    (reduce [_ f start]
      (reduce f start (range 10)))))
RuntimeException Unable to convert: class user$reify__15 to Object[]
{code}

*Proposal:* Add PersistentVector.create(Iterable) and PersistentVector.create(IReduceInit) to efficiently create PVs from those. Add a number of cases to vec to support different cases.

*Patch:* clj-1546-3.patch

*Open Question:* Which branch should come first, {{Collection}} or {{IReduceInit}}? {{Collection}} reaches the fast path for small collections through {{LazilyPersistentVector}}, but {{IReduceInit}} should be faster for larger things. Related: Shouldn't the item count in {{LazilyPersistentVector}} be a bounded count?

*Screened by:*
Approval Vetted [ 10003 ] Incomplete [ 10006 ]
Alex Miller made changes -
Attachment clj-1546-4.patch [ 13507 ]
Description These examples should work but does not:

Something Iterable but not IReduce:

{code}
user> (def i (eduction (map inc) (range 100)))
#'user/i
user> (instance? java.util.Collection i)
false
user> (instance? Iterable i)
true
user> (vec i)
RuntimeException Unable to convert: class clojure.core.Iteration to Object[]
{code}

Something IReduceInit but not Iterable:
{code}
user=> (vec
  (reify clojure.lang.IReduceInit
    (reduce [_ f start]
      (reduce f start (range 10)))))
RuntimeException Unable to convert: class user$reify__15 to Object[]
{code}

*Proposal:* Add PersistentVector.create(Iterable) and PersistentVector.create(IReduceInit) to efficiently create PVs from those. Add a number of cases to vec to support different cases.

*Patch:* clj-1546-3.patch

*Open Question:* Which branch should come first, {{Collection}} or {{IReduceInit}}? {{Collection}} reaches the fast path for small collections through {{LazilyPersistentVector}}, but {{IReduceInit}} should be faster for larger things. Related: Shouldn't the item count in {{LazilyPersistentVector}} be a bounded count?

*Screened by:*
These examples should work but does not:

Something Iterable but not IReduce:

{code}
user> (def i (eduction (map inc) (range 100)))
#'user/i
user> (instance? java.util.Collection i)
false
user> (instance? Iterable i)
true
user> (vec i)
RuntimeException Unable to convert: class clojure.core.Iteration to Object[]
{code}

Something IReduceInit but not Iterable:
{code}
user=> (vec
  (reify clojure.lang.IReduceInit
    (reduce [_ f start]
      (reduce f start (range 10)))))
RuntimeException Unable to convert: class user$reify__15 to Object[]
{code}

*Proposal:* Add PersistentVector.create(Iterable) and PersistentVector.create(IReduceInit) to efficiently create PVs from those. Add a number of cases to vec to support different cases.

*Patch:* clj-1546-4.patch

*Screened by:*
Approval Incomplete [ 10006 ] Vetted [ 10003 ]
Alex Miller made changes -
Approval Vetted [ 10003 ] Incomplete [ 10006 ]
Alex Miller made changes -
Attachment benchmark.png [ 13541 ]
Attachment clj-1546-5.patch [ 13542 ]
Description These examples should work but does not:

Something Iterable but not IReduce:

{code}
user> (def i (eduction (map inc) (range 100)))
#'user/i
user> (instance? java.util.Collection i)
false
user> (instance? Iterable i)
true
user> (vec i)
RuntimeException Unable to convert: class clojure.core.Iteration to Object[]
{code}

Something IReduceInit but not Iterable:
{code}
user=> (vec
  (reify clojure.lang.IReduceInit
    (reduce [_ f start]
      (reduce f start (range 10)))))
RuntimeException Unable to convert: class user$reify__15 to Object[]
{code}

*Proposal:* Add PersistentVector.create(Iterable) and PersistentVector.create(IReduceInit) to efficiently create PVs from those. Add a number of cases to vec to support different cases.

*Patch:* clj-1546-4.patch

*Screened by:*
These examples should work but does not:

Something Iterable but not IReduce:

{code}
user> (def i (eduction (map inc) (range 100)))
#'user/i
user> (instance? java.util.Collection i)
false
user> (instance? Iterable i)
true
user> (vec i)
RuntimeException Unable to convert: class clojure.core.Iteration to Object[]
{code}

Something IReduceInit but not Iterable:
{code}
user=> (vec
  (reify clojure.lang.IReduceInit
    (reduce [_ f start]
      (reduce f start (range 10)))))
RuntimeException Unable to convert: class user$reify__15 to Object[]
{code}

*Proposal:* Add PersistentVector.create(Iterable) and PersistentVector.create(IReduceInit) to efficiently create PVs from those.

For performance, vec has several cases:
1) (vec) if vector?: return new vector w/o meta - this matches prior behavior but has a constant cost of a few ns, rather than linear cost. If not a vector, spill to LazilyPersistentVector.create(Object).

2) (LPV) instanceof IReduceInit: Anything reducible can reduce itself fastest. Right now this has a big benefit for PersistentList. on 1.7.0-alpha4 with list of size 1024, into=28 seconds, vec=18 seconds. After patch, vec=7 seconds. If maps, sets, and range were IReduce later they would also use this path and see noticeable boosts. This is also the branch that will handle the Eduction and IReduceInit cases added in the patch.

3) (LPV) instanceof ISeq: If the coll is a sequence already, best to walk it rather than build an iterator or array from it. This calls into PersistentVector.create(ISeq). That implementation now contains an optimization to build into an array and construct the PersistentVector directly from the array for sequences <= 32 elements (which is most common). Once that threshold is reached, it switches to building with transients. The benchmark shows that the patch makes vec substantially faster for all seqs and even faster than into in some cases.

4) (LPV) instanceof Iterable: For all non-Clojure collections (ArrayList) and current non-IReduce Clojure collections (PHM, PHS), this is fastest path. Iterators are preferred to seqs as they do not cache or hold onto the values as they go by. The PV.create() for Iterable uses transients. Due to slightly more overhead, small maps and sets are slightly slower but this would be fixed by CLJ-1499 and/or making PHM/PHS IReduceInit.

5) (LPV) otherwise RT.toArray(): catches Map, String, Object[], primitive array, etc. The important ones here are the arrays - they are slightly slower on small arrays due to overhead of checking more cases above, but big arrays are significantly faster than they were.

In addition, there was one hard-coded path in the Compiler into PersistentVector.create() and I re-routed that through LazilyPersistentVector instead as that code is now the place to choose the fastest path logic.

*Patch:* clj-1546-5.patch

*Screened by:*
Approval Incomplete [ 10006 ] Vetted [ 10003 ]
Alex Miller made changes -
Attachment clj-1546-5.patch [ 13542 ]
Alex Miller made changes -
Attachment clj-1546-5.patch [ 13543 ]
Alex Miller made changes -
Description These examples should work but does not:

Something Iterable but not IReduce:

{code}
user> (def i (eduction (map inc) (range 100)))
#'user/i
user> (instance? java.util.Collection i)
false
user> (instance? Iterable i)
true
user> (vec i)
RuntimeException Unable to convert: class clojure.core.Iteration to Object[]
{code}

Something IReduceInit but not Iterable:
{code}
user=> (vec
  (reify clojure.lang.IReduceInit
    (reduce [_ f start]
      (reduce f start (range 10)))))
RuntimeException Unable to convert: class user$reify__15 to Object[]
{code}

*Proposal:* Add PersistentVector.create(Iterable) and PersistentVector.create(IReduceInit) to efficiently create PVs from those.

For performance, vec has several cases:
1) (vec) if vector?: return new vector w/o meta - this matches prior behavior but has a constant cost of a few ns, rather than linear cost. If not a vector, spill to LazilyPersistentVector.create(Object).

2) (LPV) instanceof IReduceInit: Anything reducible can reduce itself fastest. Right now this has a big benefit for PersistentList. on 1.7.0-alpha4 with list of size 1024, into=28 seconds, vec=18 seconds. After patch, vec=7 seconds. If maps, sets, and range were IReduce later they would also use this path and see noticeable boosts. This is also the branch that will handle the Eduction and IReduceInit cases added in the patch.

3) (LPV) instanceof ISeq: If the coll is a sequence already, best to walk it rather than build an iterator or array from it. This calls into PersistentVector.create(ISeq). That implementation now contains an optimization to build into an array and construct the PersistentVector directly from the array for sequences <= 32 elements (which is most common). Once that threshold is reached, it switches to building with transients. The benchmark shows that the patch makes vec substantially faster for all seqs and even faster than into in some cases.

4) (LPV) instanceof Iterable: For all non-Clojure collections (ArrayList) and current non-IReduce Clojure collections (PHM, PHS), this is fastest path. Iterators are preferred to seqs as they do not cache or hold onto the values as they go by. The PV.create() for Iterable uses transients. Due to slightly more overhead, small maps and sets are slightly slower but this would be fixed by CLJ-1499 and/or making PHM/PHS IReduceInit.

5) (LPV) otherwise RT.toArray(): catches Map, String, Object[], primitive array, etc. The important ones here are the arrays - they are slightly slower on small arrays due to overhead of checking more cases above, but big arrays are significantly faster than they were.

In addition, there was one hard-coded path in the Compiler into PersistentVector.create() and I re-routed that through LazilyPersistentVector instead as that code is now the place to choose the fastest path logic.

*Patch:* clj-1546-5.patch

*Screened by:*
These examples should work but do not:

Something Iterable but not IReduce:

{code}
user> (def i (eduction (map inc) (range 100)))
#'user/i
user> (instance? java.util.Collection i)
false
user> (instance? Iterable i)
true
user> (vec i)
RuntimeException Unable to convert: class clojure.core.Iteration to Object[]
{code}

Something IReduceInit but not Iterable:
{code}
user=> (vec
  (reify clojure.lang.IReduceInit
    (reduce [_ f start]
      (reduce f start (range 10)))))
RuntimeException Unable to convert: class user$reify__15 to Object[]
{code}

*Proposal:* Add PersistentVector.create(Iterable) and PersistentVector.create(IReduceInit) to efficiently create PVs from those.

For performance, vec has several cases:
1) (vec) if vector?: return new vector w/o meta - this matches prior behavior but has a constant cost of a few ns, rather than linear cost. If not a vector, spill to LazilyPersistentVector.create(Object).

2) (LPV) instanceof IReduceInit: Anything reducible can reduce itself fastest. Right now this has a big benefit for PersistentList. on 1.7.0-alpha4 with list of size 1024, into=28 seconds, vec=18 seconds. After patch, vec=7 seconds. If maps, sets, and range were IReduce later they would also use this path and see noticeable boosts. This is also the branch that will handle the Eduction and IReduceInit cases added in the patch.

3) (LPV) instanceof ISeq: If the coll is a sequence already, best to walk it rather than build an iterator or array from it. This calls into PersistentVector.create(ISeq). That implementation now contains an optimization to build into an array and construct the PersistentVector directly from the array for sequences <= 32 elements (which is most common). Once that threshold is reached, it switches to building with transients. The benchmark shows that the patch makes vec substantially faster for all seqs and even faster than into in some cases.

4) (LPV) instanceof Iterable: For all non-Clojure collections (ArrayList) and current non-IReduce Clojure collections (PHM, PHS), this is fastest path. Iterators are preferred to seqs as they do not cache or hold onto the values as they go by. The PV.create() for Iterable uses transients. Due to slightly more overhead, small maps and sets are slightly slower but this would be fixed by CLJ-1499 and/or making PHM/PHS IReduceInit.

5) (LPV) otherwise RT.toArray(): catches Map, String, Object[], primitive array, etc. The important ones here are the arrays - they are slightly slower on small arrays due to overhead of checking more cases above, but big arrays are significantly faster than they were.

In addition, there was one hard-coded path in the Compiler into PersistentVector.create() and I re-routed that through LazilyPersistentVector instead as that code is now the place to choose the fastest path logic.

*Patch:* clj-1546-5.patch

*Screened by:*
Alex Miller made changes -
Attachment clj-1546-6.patch [ 13721 ]
Attachment numbers.png [ 13722 ]
Description These examples should work but do not:

Something Iterable but not IReduce:

{code}
user> (def i (eduction (map inc) (range 100)))
#'user/i
user> (instance? java.util.Collection i)
false
user> (instance? Iterable i)
true
user> (vec i)
RuntimeException Unable to convert: class clojure.core.Iteration to Object[]
{code}

Something IReduceInit but not Iterable:
{code}
user=> (vec
  (reify clojure.lang.IReduceInit
    (reduce [_ f start]
      (reduce f start (range 10)))))
RuntimeException Unable to convert: class user$reify__15 to Object[]
{code}

*Proposal:* Add PersistentVector.create(Iterable) and PersistentVector.create(IReduceInit) to efficiently create PVs from those.

For performance, vec has several cases:
1) (vec) if vector?: return new vector w/o meta - this matches prior behavior but has a constant cost of a few ns, rather than linear cost. If not a vector, spill to LazilyPersistentVector.create(Object).

2) (LPV) instanceof IReduceInit: Anything reducible can reduce itself fastest. Right now this has a big benefit for PersistentList. on 1.7.0-alpha4 with list of size 1024, into=28 seconds, vec=18 seconds. After patch, vec=7 seconds. If maps, sets, and range were IReduce later they would also use this path and see noticeable boosts. This is also the branch that will handle the Eduction and IReduceInit cases added in the patch.

3) (LPV) instanceof ISeq: If the coll is a sequence already, best to walk it rather than build an iterator or array from it. This calls into PersistentVector.create(ISeq). That implementation now contains an optimization to build into an array and construct the PersistentVector directly from the array for sequences <= 32 elements (which is most common). Once that threshold is reached, it switches to building with transients. The benchmark shows that the patch makes vec substantially faster for all seqs and even faster than into in some cases.

4) (LPV) instanceof Iterable: For all non-Clojure collections (ArrayList) and current non-IReduce Clojure collections (PHM, PHS), this is fastest path. Iterators are preferred to seqs as they do not cache or hold onto the values as they go by. The PV.create() for Iterable uses transients. Due to slightly more overhead, small maps and sets are slightly slower but this would be fixed by CLJ-1499 and/or making PHM/PHS IReduceInit.

5) (LPV) otherwise RT.toArray(): catches Map, String, Object[], primitive array, etc. The important ones here are the arrays - they are slightly slower on small arrays due to overhead of checking more cases above, but big arrays are significantly faster than they were.

In addition, there was one hard-coded path in the Compiler into PersistentVector.create() and I re-routed that through LazilyPersistentVector instead as that code is now the place to choose the fastest path logic.

*Patch:* clj-1546-5.patch

*Screened by:*
These examples should work but do not:

Something Iterable but not IReduce:

{code}
user> (def i (eduction (map inc) (range 100)))
#'user/i
user> (instance? java.util.Collection i)
false
user> (instance? Iterable i)
true
user> (vec i)
RuntimeException Unable to convert: class clojure.core.Iteration to Object[]
{code}

Something IReduceInit but not Iterable:
{code}
user=> (vec
  (reify clojure.lang.IReduceInit
    (reduce [_ f start]
      (reduce f start (range 10)))))
RuntimeException Unable to convert: class user$reify__15 to Object[]
{code}

*Proposal:* Add PersistentVector.create(Iterable) and PersistentVector.create(IReduceInit) to efficiently create PVs from those.

For performance, vec has several cases:
1) (vec) if vector?: return new vector w/o meta - this matches prior behavior but has a constant cost of a few ns, rather than linear cost. If not a vector, spill to LazilyPersistentVector.create(Object).

2) (LPV) instanceof IReduceInit: Anything reducible can reduce itself fastest. Right now this has a big benefit for PersistentList. on 1.7.0-alpha4 with list of size 1024, into=28 seconds, vec=18 seconds. After patch, vec=7 seconds. As more things become IReduce, they'll take this path as well. This is also the branch that handles the new Eduction and IReduceInit cases.

3) (LPV) instanceof ISeq: If the coll is a sequence already, best to just walk it rather than build an iterator or array from it. This calls into PersistentVector.create(ISeq). That implementation now contains an optimization to build into an array and construct the PersistentVector directly from the array for sequences <= 32 elements (which is common). Once that threshold is reached, it switches to building with transients. The benchmark shows that the patch makes vec substantially faster for all seqs and even faster than into in some cases.

4) (LPV) instanceof Iterable: For all non-Clojure collections (ArrayList) and current non-IReduce Clojure collections (PHM, PHS), this is fastest path. Iterators are preferred to seqs as they do not cache or hold onto the values as they go by. The PV.create() for Iterable uses transients. Due to slightly more overhead, small maps and sets are slightly slower but this is largely fixed by CLJ-1499 which adds direct iterators. ArrayLists with <= 32 are special-cased - we can toArray() and construct the PV with a seeded node in this case. This type and size is particularly common in real code. Even so, very small ArrayLists are a bit slower than they were due to increased number of conditional checks I think.

5) (LPV) otherwise RT.toArray(): catches Map, String, Object[], primitive array, etc. The important ones here are the arrays - they are slightly slower on small arrays due to overhead of checking more cases above, but big arrays are significantly faster than they were.

In addition, there was one hard-coded path in the Compiler into PersistentVector.create() and I re-routed that through LazilyPersistentVector instead as that code is now the place to choose the fastest path logic.

*Patch:* clj-1546-6.patch, see numbers.png for perf comparison

*Screened by:*
Alex Miller made changes -
Attachment benchmark.png [ 13541 ]
Stuart Halloway made changes -
Description These examples should work but do not:

Something Iterable but not IReduce:

{code}
user> (def i (eduction (map inc) (range 100)))
#'user/i
user> (instance? java.util.Collection i)
false
user> (instance? Iterable i)
true
user> (vec i)
RuntimeException Unable to convert: class clojure.core.Iteration to Object[]
{code}

Something IReduceInit but not Iterable:
{code}
user=> (vec
  (reify clojure.lang.IReduceInit
    (reduce [_ f start]
      (reduce f start (range 10)))))
RuntimeException Unable to convert: class user$reify__15 to Object[]
{code}

*Proposal:* Add PersistentVector.create(Iterable) and PersistentVector.create(IReduceInit) to efficiently create PVs from those.

For performance, vec has several cases:
1) (vec) if vector?: return new vector w/o meta - this matches prior behavior but has a constant cost of a few ns, rather than linear cost. If not a vector, spill to LazilyPersistentVector.create(Object).

2) (LPV) instanceof IReduceInit: Anything reducible can reduce itself fastest. Right now this has a big benefit for PersistentList. on 1.7.0-alpha4 with list of size 1024, into=28 seconds, vec=18 seconds. After patch, vec=7 seconds. As more things become IReduce, they'll take this path as well. This is also the branch that handles the new Eduction and IReduceInit cases.

3) (LPV) instanceof ISeq: If the coll is a sequence already, best to just walk it rather than build an iterator or array from it. This calls into PersistentVector.create(ISeq). That implementation now contains an optimization to build into an array and construct the PersistentVector directly from the array for sequences <= 32 elements (which is common). Once that threshold is reached, it switches to building with transients. The benchmark shows that the patch makes vec substantially faster for all seqs and even faster than into in some cases.

4) (LPV) instanceof Iterable: For all non-Clojure collections (ArrayList) and current non-IReduce Clojure collections (PHM, PHS), this is fastest path. Iterators are preferred to seqs as they do not cache or hold onto the values as they go by. The PV.create() for Iterable uses transients. Due to slightly more overhead, small maps and sets are slightly slower but this is largely fixed by CLJ-1499 which adds direct iterators. ArrayLists with <= 32 are special-cased - we can toArray() and construct the PV with a seeded node in this case. This type and size is particularly common in real code. Even so, very small ArrayLists are a bit slower than they were due to increased number of conditional checks I think.

5) (LPV) otherwise RT.toArray(): catches Map, String, Object[], primitive array, etc. The important ones here are the arrays - they are slightly slower on small arrays due to overhead of checking more cases above, but big arrays are significantly faster than they were.

In addition, there was one hard-coded path in the Compiler into PersistentVector.create() and I re-routed that through LazilyPersistentVector instead as that code is now the place to choose the fastest path logic.

*Patch:* clj-1546-6.patch, see numbers.png for perf comparison

*Screened by:*
These examples should work but do not:

Something Iterable but not IReduce:

{code}
user> (def i (eduction (map inc) (range 100)))
#'user/i
user> (instance? java.util.Collection i)
false
user> (instance? Iterable i)
true
user> (vec i)
RuntimeException Unable to convert: class clojure.core.Iteration to Object[]
{code}

Something IReduceInit but not Iterable:
{code}
user=> (vec
  (reify clojure.lang.IReduceInit
    (reduce [_ f start]
      (reduce f start (range 10)))))
RuntimeException Unable to convert: class user$reify__15 to Object[]
{code}

*Proposal:* Add PersistentVector.create(Iterable) and PersistentVector.create(IReduceInit) to efficiently create PVs from those. See also the blog post http://insideclojure.org/2015/01/07/vec-perf/.

For performance, vec has several cases:
1) (vec) if vector?: return new vector w/o meta - this matches prior behavior but has a constant cost of a few ns, rather than linear cost. If not a vector, spill to LazilyPersistentVector.create(Object).

2) (LPV) instanceof IReduceInit: Anything reducible can reduce itself fastest. Right now this has a big benefit for PersistentList. on 1.7.0-alpha4 with list of size 1024, into=28 seconds, vec=18 seconds. After patch, vec=7 seconds. As more things become IReduce, they'll take this path as well. This is also the branch that handles the new Eduction and IReduceInit cases.

3) (LPV) instanceof ISeq: If the coll is a sequence already, best to just walk it rather than build an iterator or array from it. This calls into PersistentVector.create(ISeq). That implementation now contains an optimization to build into an array and construct the PersistentVector directly from the array for sequences <= 32 elements (which is common). Once that threshold is reached, it switches to building with transients. The benchmark shows that the patch makes vec substantially faster for all seqs and even faster than into in some cases.

4) (LPV) instanceof Iterable: For all non-Clojure collections (ArrayList) and current non-IReduce Clojure collections (PHM, PHS), this is fastest path. Iterators are preferred to seqs as they do not cache or hold onto the values as they go by. The PV.create() for Iterable uses transients. Due to slightly more overhead, small maps and sets are slightly slower but this is largely fixed by CLJ-1499 which adds direct iterators. ArrayLists with <= 32 are special-cased - we can toArray() and construct the PV with a seeded node in this case. This type and size is particularly common in real code. Even so, very small ArrayLists are a bit slower than they were due to increased number of conditional checks I think.

5) (LPV) otherwise RT.toArray(): catches Map, String, Object[], primitive array, etc. The important ones here are the arrays - they are slightly slower on small arrays due to overhead of checking more cases above, but big arrays are significantly faster than they were.

In addition, there was one hard-coded path in the Compiler into PersistentVector.create() and I re-routed that through LazilyPersistentVector instead as that code is now the place to choose the fastest path logic.

*Patch:* clj-1546-6.patch, see numbers.png for perf comparison

*Screened by:* Stu
Approval Vetted [ 10003 ] Screened [ 10004 ]
Rich Hickey made changes -
Approval Screened [ 10004 ] Ok [ 10007 ]
Stuart Halloway made changes -
Status Open [ 1 ] Closed [ 6 ]
Resolution Completed [ 1 ]

People

Vote (0)
Watch (2)

Dates

  • Created:
    Updated:
    Resolved: