GNU bug report logs -
#69709
`sort` interface improvement and universal ordering predicate
Previous Next
Full log
Message #59 received at 69709 <at> debbugs.gnu.org (full text, mbox):
On 23/03/2024 22:09, Stefan Monnier wrote:
>> So others will have to go around each such project, ensure the original list
>> is "owned" and add the :in-place argument, to reach the optimum
>> performance. That's why, I think, 'sort' is mutating in most languages.
> I think it's mutating in "most languages" because "most languages" are
> imperative and because those primitives usually operate on arrays (a
> "naturally imperative" data structure) rather than on singly-linked
> lists (a "naturally more immutable" data structure).
There aren't many general purpose languages around which use cons cells
and have 'sort' in stdlib for them, to compare.
To get back to the example of Clojure, which touts immutability most of
the time, the 'sort' routine first copies a sequence into an array
(apparently for performance - fewer indirections and better locality
when subsequently swapping values around), and then returns that array
with a thin wrapper called ArraySeq (which it 1 extra object, not N).
https://github.com/clojure/clojure/blob/ce55092f2b2f5481d25cff6205470c1335760ef6/src/clj/clojure/core.clj#L3103-L3118
IIUC we allocate an array internally as well during the sorting phrase,
but then we can't return it as-is or with a thin wrapper (if only
because the user expects back a list, not a vector), so we'll need to
allocate a whole new list to avoid mutating the original. And our GC is
worse than JVM's.
This bug report was last modified 1 year and 90 days ago.
Previous Next
GNU bug tracking system
Copyright (C) 1999 Darren O. Benham,
1997,2003 nCipher Corporation Ltd,
1994-97 Ian Jackson.