From: Paul Eggert <eggert@cs.ucla.edu>
To: Dmitry Antipov <dmantipov@yandex.ru>
Cc: emacs-devel@gnu.org
Subject: Change Emacs 'sort' API to use three-way comparison
Date: Fri, 29 Aug 2014 14:19:44 -0700 [thread overview]
Message-ID: <5400EE70.8050207@cs.ucla.edu> (raw)
In-Reply-To: <83fvgfinea.fsf@gnu.org>
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.
next prev parent reply other threads:[~2014-08-29 21:19 UTC|newest]
Thread overview: 15+ messages / expand[flat|nested] mbox.gz Atom feed top
2014-08-29 10:46 [Emacs-diffs] trunk r117765: Add vectors support to Fsort Eli Zaretskii
2014-08-29 14:21 ` Jordon Biondo
2014-08-29 15:41 ` Dmitry Antipov
2014-08-29 15:50 ` Jordon Biondo
2014-08-29 16:34 ` Dmitry Antipov
2014-08-29 16:43 ` Jordon Biondo
2014-08-29 18:31 ` Stefan Monnier
2014-08-29 22:53 ` Dmitry Antipov
2014-08-31 0:18 ` Richard Stallman
2014-08-29 21:19 ` Paul Eggert [this message]
2014-08-29 21:51 ` Change Emacs 'sort' API to use three-way comparison David Kastrup
2014-08-30 14:23 ` Lars Ingebrigtsen
2014-08-30 16:45 ` Paul Eggert
2014-08-30 18:07 ` Lars Ingebrigtsen
2014-08-30 18:14 ` Paul Eggert
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=5400EE70.8050207@cs.ucla.edu \
--to=eggert@cs.ucla.edu \
--cc=dmantipov@yandex.ru \
--cc=emacs-devel@gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this external index
https://git.savannah.gnu.org/cgit/emacs.git
https://git.savannah.gnu.org/cgit/emacs/org-mode.git
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.