[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
bug#6600: [PATCH] sort: add --threads option to parallelize internal sor
From: |
Pádraig Brady |
Subject: |
bug#6600: [PATCH] sort: add --threads option to parallelize internal sort. |
Date: |
Tue, 13 Jul 2010 16:09:08 +0100 |
User-agent: |
Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.1.8) Gecko/20100227 Thunderbird/3.0.3 |
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.
- bug#6600: [PATCH] sort: add --threads option to parallelize internal sort., Pádraig Brady, 2010/07/09
- bug#6600: [PATCH] sort: add --threads option to parallelize internal sort., Paul Eggert, 2010/07/09
- bug#6600: [PATCH] sort: add --threads option to parallelize internal sort., Chen Guo, 2010/07/10
- bug#6600: [PATCH] sort: add --threads option to parallelize internal sort., Pádraig Brady, 2010/07/10
- bug#6600: [PATCH] sort: add --threads option to parallelize internal sort., Pádraig Brady, 2010/07/12
- bug#6600: [PATCH] sort: add --threads option to parallelize internal sort., Pádraig Brady, 2010/07/13
- bug#6600: [PATCH] sort: add --threads option to parallelize internal sort., Jim Meyering, 2010/07/13
- bug#6600: [PATCH] sort: add --threads option to parallelize internal sort.,
Pádraig Brady <=
- bug#6600: [PATCH] sort: add --threads option to parallelize internal sort., Jim Meyering, 2010/07/13
- bug#6600: [PATCH] sort: add --threads option to parallelize internal sort., Chen Guo, 2010/07/13
- bug#6600: [PATCH] sort: add --threads option to parallelize internal sort., Pádraig Brady, 2010/07/14
- bug#6600: [PATCH] sort: add --threads option to parallelize internal sort., Pádraig Brady, 2010/07/15
- bug#6600: [PATCH] sort: add --threads option to parallelize internal sort., Jim Meyering, 2010/07/15
- bug#6600: [PATCH] sort: add --threads option to parallelize internal sort., Chen Guo, 2010/07/21
- bug#6600: [PATCH] sort: add --threads option to parallelize internal sort., Pádraig Brady, 2010/07/21