On Wed, Apr 16, 2014 at 7:38 PM, Bruce Momjian wrote:
> On Thu, Apr 10, 2014 at 06:03:15PM +0100, Simon Riggs wrote:
>> On 6 February 2014 18:21, Jeff Janes wrote:
>> > On Tue, Feb 4, 2014 at 2:22 PM, Jeremy Harris wrote:
>> >>
>> >> The attached patch replaces the existing siftup method for hea
On Thu, Apr 10, 2014 at 06:03:15PM +0100, Simon Riggs wrote:
> On 6 February 2014 18:21, Jeff Janes wrote:
> > On Tue, Feb 4, 2014 at 2:22 PM, Jeremy Harris wrote:
> >>
> >> The attached patch replaces the existing siftup method for heapify with
> >> a siftdown method. Tested with random integers
On 6 February 2014 18:21, Jeff Janes wrote:
> On Tue, Feb 4, 2014 at 2:22 PM, Jeremy Harris wrote:
>>
>> The attached patch replaces the existing siftup method for heapify with
>> a siftdown method. Tested with random integers it does 18% fewer
>> compares and takes 10% less time for the heapify,
On 26/02/14 03:08, Robert Haas wrote:
On Tue, Feb 25, 2014 at 2:55 PM, Jeremy Harris wrote:
On 24/02/14 17:38, Robert Haas wrote:
On Thu, Feb 20, 2014 at 7:27 PM, Jeremy Harris wrote:
Run under cachegrind, it takes about N/10 last-level cache misses,
all for the new item being introduced t
On Tue, Feb 25, 2014 at 2:55 PM, Jeremy Harris wrote:
> On 24/02/14 17:38, Robert Haas wrote:
>>
>> On Thu, Feb 20, 2014 at 7:27 PM, Jeremy Harris wrote:
>>>
>>> Run under cachegrind, it takes about N/10 last-level cache misses,
>>> all for the new item being introduced to the heap. The existing
On 24/02/14 17:38, Robert Haas wrote:
On Thu, Feb 20, 2014 at 7:27 PM, Jeremy Harris wrote:
Run under cachegrind, it takes about N/10 last-level cache misses,
all for the new item being introduced to the heap. The existing
code takes none at all.
Can you explain this further? This seems lik
On Thu, Feb 20, 2014 at 7:27 PM, Jeremy Harris wrote:
> On 09/02/14 17:11, Jeremy Harris wrote:
>> On 06/02/14 18:21, Jeff Janes wrote:
>>> Did you try sorting already-sorted, reverse
>>> sorted, or pipe-organ shaped data sets? We will also need to test it on
>>> strings. I usually use md5(ran
On 09/02/14 17:11, Jeremy Harris wrote:
On 06/02/14 18:21, Jeff Janes wrote:
Did you try sorting already-sorted, reverse
sorted, or pipe-organ shaped data sets? We will also need to test it on
strings. I usually use md5(random()::text) to generate strings for such
purposes, at least for a fi
On Fri, Feb 7, 2014 at 4:28 PM, Jeremy Harris wrote:
> On 06/02/14 22:12, Jeremy Harris wrote:
>>> Did you try sorting already-sorted, reverse
>>> sorted, or pipe-organ shaped data sets?
>
> Summary (low numbers better):
>
> Random ints: 83% compares, level on time.
> Sorted ints:
On 06/02/14 22:12, Jeremy Harris wrote:
Did you try sorting already-sorted, reverse
sorted, or pipe-organ shaped data sets?
Summary (low numbers better):
Random ints: 83% compares, level on time.
Sorted ints: level compares, 70% time.
Reverse-sorted ints: 10% compares, 15% tim
On 06/02/14 14:22, Robert Haas wrote:
On Thu, Feb 6, 2014 at 4:22 AM, Jeremy Harris wrote:
On 05/02/14 21:56, Robert Haas wrote:
On Tue, Feb 4, 2014 at 5:22 PM, Jeremy Harris wrote:
The attached patch replaces the existing siftup method for heapify with
a siftdown method. Tested with random
On 06/02/14 18:21, Jeff Janes wrote:
How big of
sets were you sorting in each case?
Big enough to go external. The timings and compare-counts given are
purely for the heapify stage not the total for the sort, so are
constrained by the work_mem not by the sort size per se.
I'm limited to wor
On Tue, Feb 4, 2014 at 2:22 PM, Jeremy Harris wrote:
> The attached patch replaces the existing siftup method for heapify with
> a siftdown method. Tested with random integers it does 18% fewer
> compares and takes 10% less time for the heapify, over the work_mem
> range 1024 to 1048576.
>
Thank
On Thu, Feb 6, 2014 at 4:22 AM, Jeremy Harris wrote:
> On 05/02/14 21:56, Robert Haas wrote:
>> On Tue, Feb 4, 2014 at 5:22 PM, Jeremy Harris wrote:
>>> The attached patch replaces the existing siftup method for heapify with
>>> a siftdown method. Tested with random integers it does 18% fewer
>>>
On 05/02/14 21:56, Robert Haas wrote:
On Tue, Feb 4, 2014 at 5:22 PM, Jeremy Harris wrote:
The attached patch replaces the existing siftup method for heapify with
a siftdown method. Tested with random integers it does 18% fewer
compares and takes 10% less time for the heapify, over the work_mem
On Tue, Feb 4, 2014 at 5:22 PM, Jeremy Harris wrote:
> The attached patch replaces the existing siftup method for heapify with
> a siftdown method. Tested with random integers it does 18% fewer
> compares and takes 10% less time for the heapify, over the work_mem
> range 1024 to 1048576.
>
> Both
On Wed, Feb 5, 2014 at 7:22 AM, Jeremy Harris wrote:
> The attached patch replaces the existing siftup method for heapify with
> a siftdown method. Tested with random integers it does 18% fewer
> compares and takes 10% less time for the heapify, over the work_mem
> range 1024 to 1048576.
>
> Both
The attached patch replaces the existing siftup method for heapify with
a siftdown method. Tested with random integers it does 18% fewer
compares and takes 10% less time for the heapify, over the work_mem
range 1024 to 1048576.
Both algorithms appear to be O(n) (contradicting Wikipedia's claim
th
18 matches
Mail list logo
