Re: sorting in C

[Eli Zaretskii]

> From: Andrew Cohen <acohen@ust.hk>
> Date: Tue, 22 Feb 2022 10:52:06 +0800
> 
> I have been trying to speed up some things in gnus, with some
> success. But it inspired me to take a look at the sorting algorithm
> in C.  I have done some simple tests and have made some (simple)
> improvements which I hope to push. But I am a novice at the C parts of
> emacs (and C in general) so am sharing here.
> 
> Currently, lists and vectors have different code paths, but both use a
> recursive merge sort (I haven't actually looked at the vector code, I'm
> just guessing from the function names). There are some minor
> inefficiencies in the list code (it computes the length of the list on
> each recursion, for example, rather than passing it as an
> argument---changing this alone gives a 10% speedup) which I played
> with. I also tried an iterative rather than recursive merge (no real
> improvement). But in the end I found that the simplest large improvement
> was to:
> 
> 1. Use an iterative insertion sort for small lists (length < 64). I
>    wrote one that is in-place and does minimal work when the list is
>    sorted or reverse sorted, which is the case for much of the sorting
>    in gnus.
> 2. Convert longer lists to a vector, hand it off to the vector code, and
>    convert back to a list. This gives a 35% improvement in all cases I
>    was able to test.
> 
> These are the parts I propose pushing (patch attached). But then I:
> 
> 3. Replaced the current vector sorting algorithm with TIMSORT. This did
>    exactly what TIMSORT is supposed to do: on random data it is
>    marginally slower than the current mergesort. But on partially
>    ordered data it is 5 times faster.
> 
> I plan to continue playing with changes to the vector algorithm to see
> what other changes might be worthwhile.

Thank you for working on this.

Could you please work on benchmarks for this functionality, and post
those benchmarks (and their code if relevant) together with the code
changes?  AFAICT, our test suite only includes tests for very small
lists and vectors, which is not enough for considering these changes.

> -  if (length < 2)
> +  if (length < 2) {
>      return list;
> +  } else if (length < 64) {
> +    /* use an iterative insertion sort for short lists */
> +    Lisp_Object old = Qnil, new = list, before, after;
> +    while (CONSP (new)) {
> +      Lisp_Object next = Fcdr (new);
> +      if (NILP (old) || inorder (predicate, Fcar (old), Fcar (new))) {
> +        old = new;
> +        new = next;
> +        continue;
> +      }

Stylistic comment: the above is not our style of using braces.  Please
look around in the existing code to see what style we use, and if you
have questions, ask them here.

> +      before = Qnil, after = list;

Another stylistic nit: please don't use "foo, bar" where not
necessary.  (It basically is only necessary inside parenthesized
expressions.)

> +          XSETCDR(new, list); list = new; break;}
                   ^^
Please leave one space between the name of a function/macro and the
following open parenthesis.

> +        XSETCDR(before, new);
> +        XSETCDR(new, after);

Likewise.

> +    Lisp_Object result = make_nil_vector (length), tail = list;

Why not make_uninit_vector?  It's marginally faster, and I don't think
you really need to initialize the members to nil, do you?

> +    int i;
> +    /* convert list to vector */
> +    for (i=0; i < length; i++) {

"i = 0", with spaces.

> +    /* convert vector to list */

Text in comments should be complete sentences, and end in 2 spaces:

   /* Convert vector back to list.  */

> +    i = 0;
> +    tail = list;
> +    while (CONSP (tail)) {
> +      XSETCAR (tail, AREF (result, i));
> +      tail = XCDR (tail);
> +      i++;
> +    }
> +    return list;
> +  }

Btw, did you also compare the number of GC cycles in the two
implementations?  If not, I suggest to include that, since excess GC
also slows down real-life Lisp programs.

Last, but not least: it seems like your copyright assignment was only
about changes to Gnus?  If so, would you like to start your assignment
paperwork at this time, so that by the time you have the code ready,
we could accept it without limitations?  If you agree, I will send you
the form to fill and the instructions to go with it.

Thanks.