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

[Jim Meyering]

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.