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

Previous Next

Full log

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

From: Jim Meyering <jim <at> meyering.net>
To: Pádraig Brady <P <at> draigBrady.com>
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 17:16:20 +0200

Pádraig Brady wrote:
> 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.

Thanks for the perf. testing.

> Do you want me to roll that into my patch?

Sure, thanks.

Previous Next

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