On Fri, Feb 7, 2014 at 4:28 PM, Jeremy Harris <j...@wizmail.org> 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: level compares, 70% time. > Reverse-sorted ints: 10% compares, 15% time (!) > Constant ints: 200% compares, 360% time (ouch, and not O(n)) > Pipe-organ ints: 80% compares, 107% time > Random text: 83% compares, 106% time
This is kind of what I expected to happen. The problem is that it's hard to make some cases better without making other cases worse. I suspect (hope?) there's some simple fix for the constant-int case. But the last two cases are trickier. It seems intuitively that reducing comparisons ought to reduce runtime, but if I'm reading the results, the runtime actually went up even though the number of comparisons went down. This is hard to account for, but we probably need to at least understand why that's happening. I feel like this algorithm ought to be a win, but these data don't provide a compelling case for change. I wonder if it would be worth trying this test with text data as well. Text comparisons are much more expensive than integer comparisons, so the effect of saving comparisons ought to be more visible there. -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
