[00/10] typed sort of linked lists

Message

René Scharfe July 16, 2022, 4:50 p.m. UTC

llist_mergesort() is a function for sorting linked lists of any type
without any dynamic memory allocation.  It just requires the programmer
to define two accessor functions and doesn't need an embedded struct
or magic next pointer placement, which makes it relatively easy to use.

These accessor functions impose function call overhead and a barrier to
type checking.  This series aims to avoid that by giving the compiler
full type information and allow it to inline them.  Programmers don't
need to write the accessor functions anymore and get to use typed
comparison functions -- no more casts from void *.  Sorting gets a bit
quicker.  The cost: Increased binary size.

It starts by making llist_mergesort() leaner without reducing its
performance:

  mergesort: unify ranks loops
  mergesort: tighten merge loop

This matters for the next step, which creates the macro version of
that function:

  mergesort: add macros for typed sort of linked lists

The next two patches show the impact of using the macro on performance
and object text size of the test helper:

  test-mergesort: use DEFINE_LIST_SORT_DEBUG
  test-mergesort: use DEFINE_LIST_SORT

Then all llist_mergesort() callers get converted:

  blame: use DEFINE_LIST_SORT
  commit: use DEFINE_LIST_SORT
  fetch-pack: use DEFINE_LIST_SORT
  packfile: use DEFINE_LIST_SORT

... and the final patch removes the function which has become unused:

  mergesort: remove llist_mergesort()

 Makefile                  |   1 -
 blame.c                   |  30 ++++-------
 commit.c                  |  20 +++----
 fetch-pack.c              |   8 +++
 mergesort.c               |  84 -----------------------------
 mergesort.h               | 108 ++++++++++++++++++++++++++++++++++----
 packfile.c                |  18 ++-----
 remote.c                  |  22 --------
 remote.h                  |   2 -
 t/helper/test-mergesort.c |  34 +++---------
 t/perf/p0071-sort.sh      |   4 +-
 t/t0071-sort.sh           |   2 +-
 12 files changed, 134 insertions(+), 199 deletions(-)
 delete mode 100644 mergesort.c

--
2.37.1

Comments

Junio C Hamano July 17, 2022, 10:31 p.m. UTC | #1

René Scharfe <[e-mail]> writes:

> It starts by making llist_mergesort() leaner without reducing its
> performance:
>
>   mergesort: unify ranks loops
>   mergesort: tighten merge loop
>
> This matters for the next step, which creates the macro version of
> that function:
>
>   mergesort: add macros for typed sort of linked lists
>
> The next two patches show the impact of using the macro on performance
> and object text size of the test helper:
>
>   test-mergesort: use DEFINE_LIST_SORT_DEBUG
>   test-mergesort: use DEFINE_LIST_SORT
>
> Then all llist_mergesort() callers get converted:
>
>   blame: use DEFINE_LIST_SORT
>   commit: use DEFINE_LIST_SORT
>   fetch-pack: use DEFINE_LIST_SORT
>   packfile: use DEFINE_LIST_SORT
>
> ... and the final patch removes the function which has become unused:
>
>   mergesort: remove llist_mergesort()

A nicely presented coherent story that results in an overall code
reduction.  Thanks for a pleasant read.

Will queue.


>  Makefile                  |   1 -
>  blame.c                   |  30 ++++-------
>  commit.c                  |  20 +++----
>  fetch-pack.c              |   8 +++
>  mergesort.c               |  84 -----------------------------
>  mergesort.h               | 108 ++++++++++++++++++++++++++++++++++----
>  packfile.c                |  18 ++-----
>  remote.c                  |  22 --------
>  remote.h                  |   2 -
>  t/helper/test-mergesort.c |  34 +++---------
>  t/perf/p0071-sort.sh      |   4 +-
>  t/t0071-sort.sh           |   2 +-
>  12 files changed, 134 insertions(+), 199 deletions(-)
>  delete mode 100644 mergesort.c
>
> --
> 2.37.1

Junio C Hamano July 25, 2022, 6:52 p.m. UTC | #2

Junio C Hamano <[e-mail]> writes:

> René Scharfe <[e-mail]> writes:
>
>> It starts by making llist_mergesort() leaner without reducing its
>> performance:
>>
>>   mergesort: unify ranks loops
>>   mergesort: tighten merge loop
>>
>> This matters for the next step, which creates the macro version of
>> that function:
>>
>>   mergesort: add macros for typed sort of linked lists
>>
>> The next two patches show the impact of using the macro on performance
>> and object text size of the test helper:
>>
>>   test-mergesort: use DEFINE_LIST_SORT_DEBUG
>>   test-mergesort: use DEFINE_LIST_SORT
>>
>> Then all llist_mergesort() callers get converted:
>>
>>   blame: use DEFINE_LIST_SORT
>>   commit: use DEFINE_LIST_SORT
>>   fetch-pack: use DEFINE_LIST_SORT
>>   packfile: use DEFINE_LIST_SORT
>>
>> ... and the final patch removes the function which has become unused:
>>
>>   mergesort: remove llist_mergesort()
>
> A nicely presented coherent story that results in an overall code
> reduction.  Thanks for a pleasant read.
>
> Will queue.

No comments or objections from anybody?  I am planning to merge the
topic to 'next' and to 'master' soonish.

Thanks.

Derrick Stolee July 25, 2022, 8:35 p.m. UTC | #3

On 7/25/2022 2:52 PM, Junio C Hamano wrote:
> Junio C Hamano <[e-mail]> writes:
> 
>> René Scharfe <[e-mail]> writes:
>> A nicely presented coherent story that results in an overall code
>> reduction.  Thanks for a pleasant read.
>>
>> Will queue.
> 
> No comments or objections from anybody?  I am planning to merge the
> topic to 'next' and to 'master' soonish.

Sorry. I had started reading it and also found it to be a
pleasant read, but did not get around to finishing it and
saying so publicly. Consider that done now.

Thanks, René!
-Stolee

Junio C Hamano July 25, 2022, 8:49 p.m. UTC | #4

Derrick Stolee <[e-mail]> writes:

> On 7/25/2022 2:52 PM, Junio C Hamano wrote:
>> Junio C Hamano <[e-mail]> writes:
>> 
>>> René Scharfe <[e-mail]> writes:
>>> A nicely presented coherent story that results in an overall code
>>> reduction.  Thanks for a pleasant read.
>>>
>>> Will queue.
>> 
>> No comments or objections from anybody?  I am planning to merge the
>> topic to 'next' and to 'master' soonish.
>
> Sorry. I had started reading it and also found it to be a
> pleasant read, but did not get around to finishing it and
> saying so publicly. Consider that done now.
>
> Thanks, René!
> -Stolee

Thanks.