Clojure

sort-by calls keyfn more times than is necessary

Details

  • Type: Enhancement Enhancement
  • Status: Open Open
  • Priority: Minor Minor
  • Resolution: Unresolved
  • Affects Version/s: None
  • Fix Version/s: None
  • Component/s: None
  • Labels:
  • Patch:
    Code
  • Approval:
    Triaged

Description

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
  1. CLJ-1402-v1.patch
    09/Feb/15 3:00 PM
    1 kB
    Michael Blume
  2. CLJ-1402-v2.patch
    09/Feb/15 3:03 PM
    1 kB
    Michael Blume

Activity

Hide
Steve Kim added a comment -

CLJ-99 is a similar issue

Show
Steve Kim added a comment - CLJ-99 is a similar issue
Hide
Michael Blume added a comment -

Avoid using for before it's defined

Show
Michael Blume added a comment - Avoid using for before it's defined
Hide
Andy Fingerhut added a comment -

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.

Show
Andy Fingerhut added a comment - 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.
Hide
Michael Blume added a comment -

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.

Show
Michael Blume added a comment - 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.
Hide
Alex Miller added a comment -

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.

Show
Alex Miller added a comment - 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.

People

Vote (2)
Watch (3)

Dates

  • Created:
    Updated: