Re: PageRepairFragmentation performance

On 11/18/2014 07:03 PM, Heikki Linnakangas wrote:
> When profiling replay the WAL generated by pgbench, I noticed the
> PageRepairFragmentation consumes a large fraction of the CPU time:
> [snip]
>
> 1. Replace the qsort with something cheaper. The itemid arrays being
> sorted are small, a few hundred item at most, usually even smaller. In
> this pgbench test case I used, the typical size is about 60. With a
> small array a plain insertion sort is cheaper than the generic
> qsort(), because it can avoid the function overhead etc. involved with
> generic qsort. Or we could use something smarter, like a radix sort,
> knowing that we're sorting small integers. Or we could implement an
> inlineable version of qsort and use that.
IIRC, we would have a theoretical complexity of quicksort and radix sort
should be approximately the same for 256-1024 items... O(n*log(n)) vs
O(d*n), where d is ~log2(n) or just 16 in this case. However,
lexicographical ("bitstring-wise" ordering) might not be what we are
aiming for here

AFAIK, an inlined quicksort should be about the best performing sort
available (most of the enhancement coming from staying within the I-cache)

> 2. Instead of sorting the array and using memmove in-place, we could
> copy all the tuples to a temporary buffer in arbitrary order, and
> finally copy the temporary copy back to the buffer. That requires two
> memory copies per tuple, instead of one memmove, but memcpy() is
> pretty darn fast. It would be a loss when there are only a few large
> tuples on the page, so that avoiding the sort doesn't help, or when
> the tuples are mostly already in the correct places, so that most of
> the memmove()s are no-ops. But with a lot of small tuples, it would be
> a win, and it would be simple.

Memmove *should* be no slower than memcpy.... if both are actually
translated by the compiler to use intrinsics as opposed to calling the
functions --- as it seems to be done here (cfr. __memmove_ssse3_back )
A simple "if" in order to eliminate the no-op memmoves might as well do
it, too.

Just my two (euro) cents, though

> The second option would change behaviour slightly, as the tuples would
> be placed on the page in different physical order than before. It
> wouldn't be visible to to users, though.
>
> I spent some time hacking approach 1, and replaced the qsort() call
> with a bucket sort. I'm not sure if a bucket sort is optimal, or
> better than a specialized quicksort implementation, but it seemed simple.
>
> With the testcase I've been using - replaying about 2GB of WAL
> generated by pgbench - this reduces the replay time from about 55 s to
> 45 s.

Not bad at all... though I suspect most of it might come from staying
within the I-cache as opposed to regular qsort.
The smaller itemIdSortData structure surely helps a bit, too :)

> Thoughts? Attached is the patch I put together. It's actually two
> patches: the first is just refactoring, putting the common code
> between PageRepairFragmentation, PageIndexMultiDelete, and
> PageIndexDeleteNoCompact to function. The second replaces the qsort().

Definitively worth-while, even if just for the refactor. The speed-up
sounds very good, too.

Thanks,

/ J.L.