sort-by calls keyfn more times than is necessary

Question

clojure.core/sort-by evaluates keyfn for every pairwise comparison. This is wasteful when keyfn is expensive to compute.

`
user=> (def keyfn-calls (atom 0))

'user/keyfn-calls

user=> (defn keyfn [x] (do (swap! keyfn-calls inc) x))

'user/keyfn

user=> @keyfn-calls
0
user=> (sort-by keyfn (repeatedly 10 rand))
(0.1647483850582695 0.2836687590331822 0.3222305842748623 0.3850390922996001 0.41965440953966326 0.4777580378736771 0.6051704988802923 0.659376178201709 0.8459820304223701 0.938863131161208)
user=> @keyfn-calls
44
`

Answer 1

Comment made by: stevemkim

(link: CLJ-99) is a similar issue

Answer 2

Comment made by: michaelblume

Avoid using for before it's defined

Answer 3

Comment made by: jafingerhut

Michael, does your patch CLJ-1402-v2.patch intentionally modify the doc string of sort-by, because the sentence you are removing is now obsolete? If so, that would be good to mention explicitly in the comments here.

Answer 4

Comment made by: michaelblume

Yep, the patch changes sort-by so that it maps over the collection and then performs a sort on the resulting seq. This means arrays will be unmodified and a new seq created instead.

Answer 5

Comment made by: alexmiller

This patch seems like it could be slower, rather than faster, due to the extra allocation. Really needs perf tests before it can be seriously considered.

Answer 6

Reference: https://clojure.atlassian.net/browse/CLJ-1402 (reported by alex+import)