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.
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
