Re: qsort again (was Re: [PERFORM] Strange Create

At 09:48 AM 2/16/2006, Martijn van Oosterhout wrote:
>On Thu, Feb 16, 2006 at 08:22:55AM -0500, Ron wrote:
> > 3= Especially in modern systems where the gap between internal CPU
> > bandwidth and memory bandwidth is so great, the overhead of memory
> > accesses for comparisons and moves is the majority of the overhead
> > for both the pivot choosing and the partitioning algorithms within
> > quicksort.  Particularly random memory accesses.  The reason (#GPRs -
> > 1) is a magic constant is that it's the most you can compare and move
> > using only register-to-register operations.
>
>But how much of this applies to us? We're not sorting arrays of
>integers, we're sorting pointers to tuples. So while moves cost very
>little, a comparison costs hundreds, maybe thousands of cycles. A tuple
>can easily be two or three cachelines and you're probably going to
>access all of it, not to mention the Fmgr structures and the Datums
>themselves.
Pointers are simply fixed size 32b or 64b quantities.  They are 
essentially integers.  Comparing and moving pointers or fixed size 
keys to those pointers is exactly the same problem as comparing and 
moving integers.

Comparing =or= moving the actual data structures is a much more 
expensive and variable cost proposition.  I'm sure that pg's sort 
functionality is written intelligently enough that the only real data 
moves are done in a final pass after the exact desired order has been 
found using pointer compares and (re)assignments during the sorting 
process.  That's a standard technique for sorting data whose "key" or 
pointer is much smaller than a datum.

Your cost comment basically agrees with mine regarding the cost of 
random memory accesses.  The good news is that the number of datums 
to be examined during the pivot choosing process is small enough that 
the datums can fit into CPU cache while the pointers to them can be 
assigned to registers: making pivot choosing +very+ fast when done correctly.

As you've noted, actual partitioning is going to be more expensive 
since it involves accessing enough actual datums that they can't all 
fit into CPU cache.  The good news is that QuickSort has a very 
sequential access pattern within its inner loop.  So while we must go 
to memory for compares, we are at least keeping the cost for it down 
it a minimum.  In addition, said access is nice enough to be very 
prefetch and CPU cache hierarchy friendly.


>None of this is cache friendly. The actual tuples themselves could be
>spread all over memory (I don't think any particular effort is expended
>trying to minimize fragmentation).
It probably would be worth it to spend some effort on memory layout 
just as we do for HD layout.


>Do these algorithms discuss the case where a comparison is more than
>1000 times the cost of a move?
A move is always more expensive than a compare when the datum is 
larger than its pointer or key.  A move is always more expensive than 
a compare when it involves memory to memory movement rather than CPU 
location to CPU location movement.  A move is especially more 
expensive than a compare when it involves both factors.  Most moves 
do involve both.

What I suspect you meant is that a key comparison that involves 
accessing the data in memory is more expensive than reassigning the 
pointers associated with those keys.   That is certainly true.

Yes.  The problem has been extensively studied. ;-)


>Where this does become interesting is where we can convert a datum to
>an integer such that if f(A) > f(B) then A > B. Then we can sort on
>f(X) first with just integer comparisons and then do a full tuple
>comparison only if f(A) = f(B). This would be much more cache-coherent
>and make these algorithms much more applicable in my mind.
In fact we can do better.
Using hash codes or what-not to map datums to keys and then sorting 
just the keys and the pointers to those datums followed by an 
optional final pass where we do the actual data movement is also a 
standard technique for handling large data structures.


Regardless of what tweaks beyond the basic algorithms we use, the 
algorithms themselves have been well studied and their performance 
well established.  QuickSort is the best performing of the O(nlgn) 
comparison based sorts and it uses less resources than HeapSort or MergeSort.

Ron