|
From: | Dmitry Gutov |
Subject: | bug#69709: `sort` interface improvement and universal ordering predicate |
Date: | Sun, 24 Mar 2024 01:19:09 +0200 |
User-agent: | Mozilla Thunderbird |
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-L3118IIUC 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.
[Prev in Thread] | Current Thread | [Next in Thread] |