<< Back to previous view

[CLJ-99] max-key and min-key evaluate k multiple times for arguments Created: 17/Jun/09  Updated: 06/Sep/17  Resolved: 06/Sep/17

Status: Closed
Project: Clojure
Component/s: None
Affects Version/s: None
Fix Version/s: Release 1.9

Type: Enhancement Priority: Major
Reporter: Andy Fingerhut Assignee: Unassigned
Resolution: Completed Votes: 4
Labels: performance

Attachments: File clj-99-v1.diff     Text File clj-99-v2.patch     Text File clj-99-v3.patch    
Patch: Code and Test
Approval: Ok


max-key or min-key will evaluate (k value) multiple times for arguments if more than 2 arguments are passed. This is undesirable if k is expensive to calculate.

Good perf test:

(apply max-key #(Math/tan %) (range 1000))

Approach: Avoid repeated evaluation of k for any element.

A criterium test of the example above shows:

  • Before: 206.017411 µs
  • After: 126.532306 µs

Patch: clj-99-v3.patch

Comment by Assembla Importer [ 24/Aug/10 5:45 AM ]

Converted from http://www.assembla.com/spaces/clojure/tickets/99

Comment by Assembla Importer [ 24/Aug/10 5:45 AM ]

richhickey said: Updating tickets (#8, #19, #30, #31, #126, #17, #42, #47, #50, #61, #64, #69, #71, #77, #79, #84, #87, #89, #96, #99, #103, #107, #112, #113, #114, #115, #118, #119, #121, #122, #124)

Comment by Andy Fingerhut [ 15/Nov/12 9:36 PM ]

clj-99-min-key-max-key-performance-v1.txt dated Nov 15 2012 changes min-key and max-key to evaluate the function k on each of its other arguments at most once.

Comment by Andy Fingerhut [ 22/Oct/13 7:54 PM ]

Patch clj-99-v1.diff is same as previously attached patch, but with .diff suffix for easier diff-style viewing in some editors.

Comment by Steve Kim [ 11/Apr/14 10:48 AM ]

sort-by is similarly inefficient. It calls keyfn for every comparison in sort, not once for every element to be sorted.

I'm not familiar with this project's preferred workflow, so I have to ask: Do you want me to open a separate ticket for sort-by, or do you prefer to consolidate that issue into this ticket?

Comment by Alex Miller [ 11/Apr/14 10:50 AM ]


Comment by Steve Kim [ 11/Apr/14 11:47 AM ]

I created CLJ-1402 for sort-by

Comment by Michael Blume [ 09/Feb/15 2:50 PM ]

clj-99-v2 applies cleanly to master

Comment by Michael Blume [ 03/Nov/15 7:52 PM ]

clj-99-v3.patch behaves correctly for collection elements that are nil or false.

Generated at Tue Oct 17 04:51:20 CDT 2017 using JIRA 4.4#649-r158309.