On 05/02/14 21:56, Robert Haas wrote:
On Tue, Feb 4, 2014 at 5:22 PM, Jeremy Harris <j...@wizmail.org> 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 algorithms appear to be O(n) (contradicting Wikipedia's claim
that a siftup heapify is O(n log n)).
I think Wikipedia is right. Inserting an a tuple into a heap is O(lg
n); doing that n times is therefore O(n lg n). Your patch likewise
implements an outer loop which runs O(n) times and an inner loop which
runs at most O(lg n) times, so a naive analysis of that algorithm also
comes out to O(n lg n).
The patch implements a siftdown. Measurements attached.
--
Cheers,
Jeremy
work_mem baseline Sift-down baseline K siftdown K K ratio baseline K siftdown K K ratio
cmps time cmps time cmps cmps cmps time time time
1024 27271 0.001 22426 0.001 26.6 21.9 82% 6.76E-07 4.93E-07 73%
2048 52153 0.001 44557 0.001 25.5 21.8 85% 6.28E-07 4.47E-07 71%
4096 108660 0.003 89591 0.002 26.5 21.9 82% 6.47E-07 4.63E-07 72%
8192 217341 0.005 179191 0.004 26.5 21.9 82% 6.57E-07 4.88E-07 74%
16384 434101 0.011 358680 0.009 26.5 21.9 83% 6.55E-07 5.42E-07 83%
32768 871110 0.022 717542 0.019 26.6 21.9 82% 6.60E-07 5.74E-07 87%
65536 1740355 0.043 1434967 0.039 26.6 21.9 82% 6.59E-07 5.96E-07 90%
131072 3478497 0.087 2869190 0.078 26.5 21.9 82% 6.62E-07 5.98E-07 90%
262144 6962693 0.173 5740518 0.154 26.6 21.9 82% 6.58E-07 5.89E-07 89%
524288 13912236 0.345 11476660 0.311 26.5 21.9 82% 6.59E-07 5.93E-07 90%
1048576 27839260 0.690 22957368 0.622 26.5 21.9 82% 6.58E-07 5.93E-07 90%
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
