[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Change Emacs 'sort' API to use three-way comparison

From: Paul Eggert
Subject: Change Emacs 'sort' API to use three-way comparison
Date: Fri, 29 Aug 2014 14:19:44 -0700
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.7.0

One infelicity I noticed in the recent change to 'sort' in the trunk is that the new implementation calls its predicate twice for each comparison. This is because the Lisp API says the comparison function returns a boolean (nil or non-nil), whereas qsort_r wants the comparison function to return a ternary value (-1, 0, or 1). If the predicate is expensive, the new Fsort can be twice as slow as the old. We could tune it but I don't see how to get it any faster than 1.5x slower than before, assuming random input and an expensive comparison function.

To fix this I propose changing the API for 'sort' so that its function argument is no longer a predicate, but instead returns a negative integer, 0, or a positive integer. For compatibility with old code, it would treat nil as if it were nonpositive (thus requiring a reverse comparison) and noninteger nonnil values as if they were positive. This wouldn't be 100% upward-compatible, because if an existing predicate returns a nonpositive integer to stand for 'true' there will be a silent change to behavior, but I expect such usage is so rare that we don't need to worry about it.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]