Clojure

vec function is substantially slower than into function

Details

  • Type: Enhancement Enhancement
  • Status: Open Open
  • Priority: Major Major
  • Resolution: Unresolved
  • Affects Version/s: Release 1.5
  • Fix Version/s: Release 1.7
  • Component/s: None
  • Labels:
  • Approval:
    Vetted

Description

(vec coll) and (into [] coll) do exactly the same thing. However, due to into using transients, it is substantially faster. On my machine:

(time (dotimes [_ 100] (vec (range 100000))))
"Elapsed time: 732.56 msecs"

(time (dotimes [_ 100] (into [] (range 100000))))
"Elapsed time: 491.411 msecs"

This is consistently repeatable.

Since vec's sole purpose is to transform collections into vectors, it should do so at the maximum speed available.

Activity

Hide
Andy Fingerhut added a comment -

I am pretty sure that Clojure 1.5.1 also uses transient vectors for (vec (range n)) (probably also some earlier versions of Clojure, too).

Look at vec in core.clj. It checks whether its arg is a java.util.Collection, which lazy seqs are, so calls (clojure.lang.LazilyPersistentVector/create coll).

LazilyPersistentVector's create method checks whether its argument is an ISeq, which lazy seqs are, so it calls PersistentVector.create(RT.seq(coll)).

All 3 of PersistentVector's create() methods use transient vectors to build up the result.

I suspect the difference in run times are not because of transients or not, but because of the way into uses reduce, and perhaps may also have something to do with the perhaps-unnecessary call to RT.seq in LazilyPersistentVector's create method (in this case, at least – it is likely needed for other types of arguments).

Show
Andy Fingerhut added a comment - I am pretty sure that Clojure 1.5.1 also uses transient vectors for (vec (range n)) (probably also some earlier versions of Clojure, too). Look at vec in core.clj. It checks whether its arg is a java.util.Collection, which lazy seqs are, so calls (clojure.lang.LazilyPersistentVector/create coll). LazilyPersistentVector's create method checks whether its argument is an ISeq, which lazy seqs are, so it calls PersistentVector.create(RT.seq(coll)). All 3 of PersistentVector's create() methods use transient vectors to build up the result. I suspect the difference in run times are not because of transients or not, but because of the way into uses reduce, and perhaps may also have something to do with the perhaps-unnecessary call to RT.seq in LazilyPersistentVector's create method (in this case, at least – it is likely needed for other types of arguments).
Hide
Alan Malloy added a comment -

I'm pretty sure the difference is that into uses reduce: since reducers were added in 1.5, chunked sequences know how to reduce themselves without creating unnecessary cons cells. PersistentVector/create doesn't use reduce, so it has to allocate a cons cell for each item in the sequence.

Show
Alan Malloy added a comment - I'm pretty sure the difference is that into uses reduce: since reducers were added in 1.5, chunked sequences know how to reduce themselves without creating unnecessary cons cells. PersistentVector/create doesn't use reduce, so it has to allocate a cons cell for each item in the sequence.
Hide
Gary Fredericks added a comment -

Is there any downside to (defn vec [coll] (into [] coll)) (or the inlined equivalent)?

Show
Gary Fredericks added a comment - Is there any downside to (defn vec [coll] (into [] coll)) (or the inlined equivalent)?
Hide
Ghadi Shayban added a comment -

While I agree that there are improvements and possibly low-hanging fruit, FWIW https://github.com/clojure/tools.analyzer/commit/cf7dda81a22f4c9c1fe64c699ca17e7deed61db4#commitcomment-5989545

showed a 5% slowdown from a few callsites in tools.analyzer.

This ticket's benchmark is incomplete in that it covers a single type of argument (chunked range), and flawed as it timing the expense of realizing the range. (That could be a legit benchmark case, but it shouldn't be the only one).

Sorry to rain on a parade. I promise like speed too!

Show
Ghadi Shayban added a comment - While I agree that there are improvements and possibly low-hanging fruit, FWIW https://github.com/clojure/tools.analyzer/commit/cf7dda81a22f4c9c1fe64c699ca17e7deed61db4#commitcomment-5989545 showed a 5% slowdown from a few callsites in tools.analyzer. This ticket's benchmark is incomplete in that it covers a single type of argument (chunked range), and flawed as it timing the expense of realizing the range. (That could be a legit benchmark case, but it shouldn't be the only one). Sorry to rain on a parade. I promise like speed too!
Hide
Greg Chapman added a comment -

One thing to note is that vec has a subtle difference from into when the collection is an Object array of length <= 32. In that case, vec aliases the supplied array, rather than copying it (this is noted in the warning here: http://clojuredocs.org/clojure_core/clojure.core/vec). I believe I read some place that this behavior is intentional, but I can't find the citation.

Show
Greg Chapman added a comment - One thing to note is that vec has a subtle difference from into when the collection is an Object array of length <= 32. In that case, vec aliases the supplied array, rather than copying it (this is noted in the warning here: http://clojuredocs.org/clojure_core/clojure.core/vec). I believe I read some place that this behavior is intentional, but I can't find the citation.
Hide
Andy Fingerhut added a comment -

Greg, CLJ-893 might be what you remember. That is the ticket that was closed by a patch updating the documentation of vec.

Show
Andy Fingerhut added a comment - Greg, CLJ-893 might be what you remember. That is the ticket that was closed by a patch updating the documentation of vec.
Hide
Mike Anderson added a comment -

I think there are quite a few performance improvements that can be made to vec in general. For example, if given a List it should use PersistentVector.create(List) rather than producing an unnecessary seq, which appears to be the case at the moment. Also it should probably return the same object if passed an existing IPersistentVector.

Basically there are a number of cases that we could be handling more efficiently....

I'm taking a look at this now.... will propose a quick patch if it seems there is a good solution.

Show
Mike Anderson added a comment - I think there are quite a few performance improvements that can be made to vec in general. For example, if given a List it should use PersistentVector.create(List) rather than producing an unnecessary seq, which appears to be the case at the moment. Also it should probably return the same object if passed an existing IPersistentVector. Basically there are a number of cases that we could be handling more efficiently.... I'm taking a look at this now.... will propose a quick patch if it seems there is a good solution.
Hide
Mike Anderson added a comment -

I've looked at this issue and it is quite complex. There are multiple types that need to potentially be converted into vectors, and doing so efficiently will often require making use of reduce-style operations on the source collections.

Doing this efficiently will probably in turn require making use of the IReduce interface, which doesn't yet seem to be fully utilised across the Clojure code based. If we do this, lots of operations (not just vec!) can be made faster but it will be quite a major change.

I have a branch that implements some of this but would appreciate feedback if this is the right direction before I take it any further:
https://github.com/mikera/clojure/tree/clj-1192-vec-performance

Show
Mike Anderson added a comment - I've looked at this issue and it is quite complex. There are multiple types that need to potentially be converted into vectors, and doing so efficiently will often require making use of reduce-style operations on the source collections. Doing this efficiently will probably in turn require making use of the IReduce interface, which doesn't yet seem to be fully utilised across the Clojure code based. If we do this, lots of operations (not just vec!) can be made faster but it will be quite a major change. I have a branch that implements some of this but would appreciate feedback if this is the right direction before I take it any further: https://github.com/mikera/clojure/tree/clj-1192-vec-performance
Hide
Alex Miller added a comment -

Thanks Mike! It may take a few days before I can get back to you about this.

Show
Alex Miller added a comment - Thanks Mike! It may take a few days before I can get back to you about this.
Hide
Mike Anderson added a comment -

Basically the approach I am proposing is:

  • Make various collections implement IReduce efficiently (if they don't already). Especially applied to chunked seqs etc.
  • Have RT.reduce(...) methods that implement reduce on the Java side
  • Make the Clojure side use IReduce where relevant (should be as simple as extending the existing protocols)
  • Implement vec (and other similar operations) in terms of IReduce - which will solve this specific issue

If we really care about pushing vector performance even further, we can also consider:

  • Create specialised small vector types where appropriate - e.g. a specialised SmallPersistentVector class for <32 elements. This should outperform the more generic PersistentVector which is better suited for large vectors.
  • Some dedicated construction functions that know how to efficiently exploit knowledge about the data source (e.g. creating a vec from a segment of a big Object array can be done with a bunch of arraycopys into 32-element chunks and then constructing a PersistentVector around these)

This should give us a decent speedup overall (of course it would need benchmarking... but I'd hope to see some sort of measurable improvement on a macro benchmark like building and testing Clojure).

Show
Mike Anderson added a comment - Basically the approach I am proposing is:
  • Make various collections implement IReduce efficiently (if they don't already). Especially applied to chunked seqs etc.
  • Have RT.reduce(...) methods that implement reduce on the Java side
  • Make the Clojure side use IReduce where relevant (should be as simple as extending the existing protocols)
  • Implement vec (and other similar operations) in terms of IReduce - which will solve this specific issue
If we really care about pushing vector performance even further, we can also consider:
  • Create specialised small vector types where appropriate - e.g. a specialised SmallPersistentVector class for <32 elements. This should outperform the more generic PersistentVector which is better suited for large vectors.
  • Some dedicated construction functions that know how to efficiently exploit knowledge about the data source (e.g. creating a vec from a segment of a big Object array can be done with a bunch of arraycopys into 32-element chunks and then constructing a PersistentVector around these)
This should give us a decent speedup overall (of course it would need benchmarking... but I'd hope to see some sort of measurable improvement on a macro benchmark like building and testing Clojure).

People

Vote (0)
Watch (2)

Dates

  • Created:
    Updated: