On Wed, Mar 3, 2021 at 10:25 AM Daniel Gustafsson <dan...@yesql.se> wrote: > > On 18 Feb 2021, at 04:09, Thomas Munro <thomas.mu...@gmail.com> wrote: > > In another thread[1], I proposed $SUBJECT, but then we found a better > > solution to that thread's specific problem. The general idea is still > > good though: it's possible to (1) replace several existing copies of > > our qsort algorithm with one, and (2) make new specialised versions a > > bit more easily than the existing Perl generator allows. So, I'm back > > with a rebased stack of patches. I'll leave specific cases for new > > worthwhile specialisations for separate proposals; I've heard about > > several. > > Just to play around with this while reviewing I made a qsort_strcmp, like in > the attached, and tested it using a ~9M word [0] randomly shuffled wordlist. > While being too small input to make any meaningful difference in runtime (it > shaved a hair off but it might well be within the error margin) there was no > regression either. More importantly, it was really simple and quick to make a > tailored qsort which is the intention with the patch. While still being a bit > of magic, moving from the Perl generator makes this slightly less magic IMO so > +1 on this approach.
Thanks for testing and reviewing! > A tiny nitpick on the patch itself: > > + * - ST_COMPARE(a, b) - a simple comparison expression > + * - ST_COMPARE(a, b, arg) - variant that takes an extra argument > Indentation. Fixed. Also ran pgindent. > All tests pass and the documentation in the the sort_template.h is enough to > go > on, but I would prefer to see a comment in port/qsort.c referring back to > sort_template.h for documentation. I tried adding a comment along the lines "see lib/sort_template.h for details", but it felt pretty redundant, when the file contains very little other than #include "lib/sort_template.h" which should already tell you to go and look there to find out what this is about... I went ahead and pushed these. I am sure there are plenty of opportunities to experiment with this code. Here are some I recall Peter Geoghegan mentioning: 1. If you know that elements are unique, you could remove some branches that deal with equal elements (see "r == 0"). 2. Perhaps you might want to be able to disable the "presorted" check in some cases? 3. The parameters 7, 7 and 40 were probably tuned for an ancient Vax or similar[1]. We see higher insertion sort thesholds such as 27 in more recent sort algorithms[2] used in eg the JVM. You could perhaps speculate that the right answer depends in part on the element size; I dunno, but if so, here we have that at compile time while traditional qsort() does not. As for which cases are actually worth specialising, I've attached the example that Andres mentioned earlier; it seems like a reasonable candidate to go ahead and commit too, but I realised that I'd forgotten to attach it earlier. It's possible that the existing support sorting tuples could be further specialised for common sort key data types; I haven't tried that. [1] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.14.8162&rep=rep1&type=pdf [2] https://codeblab.com/wp-content/uploads/2009/09/DualPivotQuicksort.pdf
From 4cec5cb9a2e0c50726b7337fb8221281e155c4cd Mon Sep 17 00:00:00 2001 From: Thomas Munro <thomas.mu...@gmail.com> Date: Thu, 18 Feb 2021 14:47:28 +1300 Subject: [PATCH] Specialize checkpointer sort functions. When sorting a potentially large number of dirty buffers, the checkpointer can benefit from a faster sort routine. One reported improvement on a large buffer pool system was 1.4s -> 0.6s. Discussion: https://postgr.es/m/CA%2BhUKGJ2-eaDqAum5bxhpMNhvuJmRDZxB_Tow0n-gse%2BHG0Yig%40mail.gmail.com --- src/backend/storage/buffer/bufmgr.c | 37 +++++++++++++++++------------ 1 file changed, 22 insertions(+), 15 deletions(-) diff --git a/src/backend/storage/buffer/bufmgr.c b/src/backend/storage/buffer/bufmgr.c index 561c212092..7adec2ddc3 100644 --- a/src/backend/storage/buffer/bufmgr.c +++ b/src/backend/storage/buffer/bufmgr.c @@ -488,8 +488,8 @@ static void FindAndDropRelFileNodeBuffers(RelFileNode rnode, static void AtProcExit_Buffers(int code, Datum arg); static void CheckForBufferLeaks(void); static int rnode_comparator(const void *p1, const void *p2); -static int buffertag_comparator(const void *p1, const void *p2); -static int ckpt_buforder_comparator(const void *pa, const void *pb); +static inline int buffertag_comparator(const BufferTag *a, const BufferTag *b); +static inline int ckpt_buforder_comparator(const CkptSortItem *a, const CkptSortItem *b); static int ts_ckpt_progress_comparator(Datum a, Datum b, void *arg); @@ -1831,6 +1831,13 @@ UnpinBuffer(BufferDesc *buf, bool fixOwner) } } +#define ST_SORT sort_checkpoint_bufferids +#define ST_ELEMENT_TYPE CkptSortItem +#define ST_COMPARE(a, b) ckpt_buforder_comparator(a, b) +#define ST_SCOPE static +#define ST_DEFINE +#include <lib/sort_template.h> + /* * BufferSync -- Write out all dirty buffers in the pool. * @@ -1931,8 +1938,7 @@ BufferSync(int flags) * end up writing to the tablespaces one-by-one; possibly overloading the * underlying system. */ - qsort(CkptBufferIds, num_to_scan, sizeof(CkptSortItem), - ckpt_buforder_comparator); + sort_checkpoint_bufferids(CkptBufferIds, num_to_scan); num_spaces = 0; @@ -4595,11 +4601,9 @@ WaitBufHdrUnlocked(BufferDesc *buf) /* * BufferTag comparator. */ -static int -buffertag_comparator(const void *a, const void *b) +static inline int +buffertag_comparator(const BufferTag *ba, const BufferTag *bb) { - const BufferTag *ba = (const BufferTag *) a; - const BufferTag *bb = (const BufferTag *) b; int ret; ret = rnode_comparator(&ba->rnode, &bb->rnode); @@ -4626,12 +4630,9 @@ buffertag_comparator(const void *a, const void *b) * It is important that tablespaces are compared first, the logic balancing * writes between tablespaces relies on it. */ -static int -ckpt_buforder_comparator(const void *pa, const void *pb) +static inline int +ckpt_buforder_comparator(const CkptSortItem *a, const CkptSortItem *b) { - const CkptSortItem *a = (const CkptSortItem *) pa; - const CkptSortItem *b = (const CkptSortItem *) pb; - /* compare tablespace */ if (a->tsId < b->tsId) return -1; @@ -4722,6 +4723,13 @@ ScheduleBufferTagForWriteback(WritebackContext *context, BufferTag *tag) IssuePendingWritebacks(context); } +#define ST_SORT sort_pending_writebacks +#define ST_ELEMENT_TYPE PendingWriteback +#define ST_COMPARE(a, b) buffertag_comparator(&a->tag, &b->tag) +#define ST_SCOPE static +#define ST_DEFINE +#include <lib/sort_template.h> + /* * Issue all pending writeback requests, previously scheduled with * ScheduleBufferTagForWriteback, to the OS. @@ -4741,8 +4749,7 @@ IssuePendingWritebacks(WritebackContext *context) * Executing the writes in-order can make them a lot faster, and allows to * merge writeback requests to consecutive blocks into larger writebacks. */ - qsort(&context->pending_writebacks, context->nr_pending, - sizeof(PendingWriteback), buffertag_comparator); + sort_pending_writebacks(context->pending_writebacks, context->nr_pending); /* * Coalesce neighbouring writes, but nothing else. For that we iterate -- 2.30.0
