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

Previous Next

Full log

Message #28 received at 6600 <at> debbugs.gnu.org (full text, mbox):

From: Pádraig Brady <P <at> draigBrady.com>
To: Jim Meyering <jim <at> meyering.net>
Cc: Gene Auyeung <quaker4lyf <at> gmail.com>, 6600 <at> debbugs.gnu.org,
	Paul Eggert <eggert <at> CS.UCLA.EDU>, Chen Guo <chenguo4 <at> yahoo.com>
Subject: Re: bug#6600: [PATCH] sort: add --threads option
	to	parallelize	internal sort.
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.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.