Subject: bug#6600: [PATCH] sort: add --threads option to parallelize internal sort.

From: Pádraig Brady <[email-masked]>
Date: Tue, 13 Jul 2010 16:09:08 +0100

On 13/07/10 15:35, Jim Meyering wrote:
> I noticed that heap_insert's reallocation was awkward and inefficient.
> Using x2nrealloc rather than xrealloc makes the code
> cleaner as well as more efficient in the face of a growing
> heap, and also handles integer overflow.
> 
> diff --git a/gl/lib/heap.c b/gl/lib/heap.c
> index a37224f..12a7767 100644
> --- a/gl/lib/heap.c
> +++ b/gl/lib/heap.c
> @@ -82,15 +82,8 @@ int
>  heap_insert (struct heap *heap, void *item)
>  {
>    if (heap->capacity - 1 <= heap->count)
> -    {
> -      size_t new_size = (2 + heap->count) * sizeof *(heap->array);
> -      void *realloc_ret = xrealloc (heap->array, new_size);
> -      heap->array = (void **) realloc_ret;
> -      heap->capacity = (2 + heap->count);
> -
> -      if (!heap->array)
> -        return -1;
> -    }
> +    heap->array = x2nrealloc (heap->array, &heap->capacity,
> +                              sizeof *(heap->array));
> 
>    heap->array[++heap->count] = item;
>    heapify_up (heap->array, heap->count, heap->compare);

Much cleaner and increases with n *= 1.5 rather than n += 2
Testing here shows no change in performance.

Do you want me to roll that into my patch?

cheers,
Pádraig.