Re: sorting in C

[Eli Zaretskii]

> From: Andrew Cohen <acohen@ust.hk>
> Date: Wed, 23 Feb 2022 20:53:28 +0800
> 
> >>>>> "EZ" == Eli Zaretskii <eliz@gnu.org> writes:
> 
> [...]
> 
>     EZ> The 5-fold slowdown is a pain, IMO.  Can we do better in the
>     EZ> worst case?
> 
> Maybe, but probably not too much. That is the point of these
> hybrids---they improve on some cases and do worse on others. Its a win
> only if the real-world data favors the improved case.
> 
> I played around a bit more and lowering the length threshold to 40
> might be a better compromise. I am working on a more thorough set of
> tests first.

OK, thanks.  Let's see the improved numbers, and can you also show
absolute times?  If they are short enough, the slowdown might not be
significant, since if the data structure is larger, the slow method
will not be used, right?  Or did I misunderstand?

>      >> And implementing TIMSORT will be even better---similar or better
>     >> speedup for the best cases, and only marginal degradation of the
>     >> worst.  But I think even this small change here is a win.
> 
>     EZ> Can we see the numbers?  This sounds like a net win to me.
> 
> Err, no? I have it all working but I'm using a C version of TIMSORT from
> the web. I don't think the license is acceptable so it probably needs to
> be written from scratch.

But for showing the performance, the license is not important, is it?

> Shouldn't be that difficult (the algorithm itself is
> well-documented) but I'm not sure how much time I have to finish it.

>From my POV, take all the time you need.  Emacs 29 is far from a
release.