Re: master 4b79c80c999 1/2: New function 'sort-on'

[Dmitry Gutov <dmitry@gutov.dev>]

On 28/02/2024 09:40, Michael Heerdegen wrote:
> Dmitry Gutov <dmitry@gutov.dev> writes:
> 
>> The other alternative (suggested by Daniel) is to add a yet another
>> optional argument - whether to do the schwartz transform - so it would
>> be on the caller to determine whether the accessor is costly enough.
> 
> This would be my preferred solution, too
> 
>> This is not my first choice, but I'd still prefer it over having two
>> different but very similar functions. sort-on is slower than it has to
>> be, too.
> 
> It could be improved?  How?

Well, 'mapcar' in it allocates a new sequence of length N. The Schwartz 
transform creates about as many new cons cells too. If the function is 
made destructive, 'mapcar' becomes unnecessary as the original sequence 
could be reused - and that is measurably faster, too (when the cost 
function is simple enough).

And if it's made destructive, it becomes even closer to the current 
'sort'. That would mean less justification to keep them as separate 
functions.

> BTW, I wonder how this addition fits into my original suggestion about
> sort predicate construction.

Sorry, I either can't find your respective message in this thread, or 
don't understand the suggestion.

> I guess we would want to allow to choose
> between using schwartz or not (at each level) in the specification -

I don't know if we really want to (every such knob is a step toward more 
complex api, and higher odds of user choosing the parameters poorly), 
but we could indeed try something like that.

> which would mean that my approach would build a sort function, not a
> sort predicate.  Which also might allow to build more efficient code.

If you mean that your proposed constructed sort function would 
incorporate the lookup logic (currently supplied with ACCESSOR), then it 
would incur the same cost that the Schwartz transform is amortizing, 
wouldn't it? Perhaps some code would help.

Also, if the sort function will be in Lisp (even byte-compiled one), 
then it will likely have higher overhead than the simple '< or 'string<, 
for example. And while the cost of the transform is O(N), the comparison 
function is called O(N*logN) on average.