Re: Timsort performance, quicksort (was: Re: Memory usage during sorting)

On Tue, Apr 24, 2012 at 7:16 PM, Peter Geoghegan <peter(at)2ndquadrant(dot)com> wrote:
>>> That makes sense to me, but obviously more data is needed here.
>>
>> What more data do you think is needed?  I've been suspicious of that
>> code since the first time I looked at it, and I'm now fairly well
>> convinced that it's full of suckitude.  Honestly, I'm not sure I could
>> manage to contrive a case where that code wins if I set out to do so.
>
> Yeah, I thought that the rationale for introducing the pre-sorted
> check, as it appeared in a commit message, was a little weak. I don't
> know that I'd go as far as to say that it was full of suckitude. The
> worst thing about that code to my mind is that despite being highly
> performance critical, it has exactly no comments beyond a brief
> description, and the names of variables are arcanely curt.

Well, what I don't like about it is that it doesn't work. Having a
special case for pre-sorted input makes sense to me, but doing that
check recursively at every level is pointless unless it helps with
almost-sorted input, and doubling the runtime doesn't meet my
definition of helping.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company