From: Sokolov Yura <funny.falcon@postgrespro.ru>
To: Heikki Linnakangas <hlinnaka@iki.fi>
Cc: pgsql-hackers@postgresql.org, Heikki Linnakangas <hlinnaka@gmail.com>
Subject: Re: Small improvement to compactify_tuples
Date: Mon, 15 May 2017 15:08:40 +0300
Message-ID: <0dcb7a5afa3fae6001bd1712253cf81d@postgrespro.ru> (raw)
In-Reply-To: <6d8cd37e-3d78-451e-a9a1-418650397639@iki.fi>
References: <3c6ff1d3a2ff429ee80d0031e6c69cb7@postgrespro.ru>
<6d8cd37e-3d78-451e-a9a1-418650397639@iki.fi>
List-Unsubscribe: <mailto:majordomo@postgresql.org?body=unsub%20pgsql-hackers>
Heikki Linnakangas писал 2017-05-15 12:06:
> On 05/14/2017 09:47 PM, Sokolov Yura wrote:
>> Good day, everyone.
>>
>> I've been playing a bit with unlogged tables - just random updates on
>> simple
>> key-value table. I've noticed amount of cpu spent in a
>> compactify_tuples
>> (called by PageRepareFragmentaion). Most of time were spent in qsort
>> of
>> itemidbase items.
>
> Ah, I played with this too a couple of years ago, see
> https://www.postgresql.org/message-id/546B89DE.7030906%40vmware.com,
> but got distracted by other things and never got around to commit
> that.
>
>> itemidbase array is bounded by number of tuples in a page, and
>> itemIdSortData
>> structure is simple, so specialized version could be a better choice.
>>
>> Attached patch adds combination of one pass of prefix sort with
>> insertion
>> sort for larger array and shell sort for smaller array.
>> Insertion sort and shell sort are implemented as macros and could be
>> reused.
>
> Cool! Could you compare that against the bucket sort I posted in the
> above thread, please?
>
> At a quick glance, your "prefix sort" seems to be the the same
> algorithm as the bucket sort that I implemented. You chose 256
> buckets, where I picked 32. And you're adding a shell sort
> implementation, for small arrays, while I used a straight insertion
> sort. Not sure what these differences mean in practice.
>
> - Heikki
Thank you for attention.
My first version of big page sort was almost exactly same to yours.
I had a bug in my insertion sort, so I had to refactor it.
(bug were fixed)
I found that items in itemidbase are almost sorted, so it is important
to try keep its order in prefix sort. So I've changed --count[i] to
count[i+1]++.
And it looks like it is better to have more buckets:
- with 256 buckets, size of single bucket is almost always less than 2,
so array is almost always sorted after prefix sort pass.
But it looks like it is better to sort each bucket separately, as you
did, and as it was in my early version.
Also I used your names for functions and some comments.
I attached new version of the patch.
I left memcpy intact cause it looks like it doesn't take noticable
cpu time.
--
Sokolov Yura aka funny.falcon
Postgres Professional: https://postgrespro.ru
The Russian PostgreSQL Company
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackersAttachments:
[text/x-diff] 0001-storage-page-bufpage.c-improve-compactify_tuples-v02.patch (6.1K, ../0dcb7a5afa3fae6001bd1712253cf81d@postgrespro.ru/2-0001-storage-page-bufpage.c-improve-compactify_tuples-v02.patch)
download | inline diff:
From 8f75fcaba0590d5150dd956a60feee5c28f4caab Mon Sep 17 00:00:00 2001
From: Sokolov Yura <funny.falcon@postgrespro.ru>
Date: Mon, 15 May 2017 14:23:39 +0300
Subject: [PATCH] storage/page/bufpage.c: improve compactify_tuples
Items passed to compactify_tuples are almost sorted. So call to general
qsort makes unnecessary overhead on function calls (swapfunc, med,
itemoffcompare).
This patch implements bucket sort:
- one pass of stable prefix sort on high 8 bits of offset- and insertion sort for buckets larger than 1 element
Also for smaller arrays shell sort is used.
Insertion and Shell sort are implemented using macroses.
This approach allows to save 3% of cpu in degenerate case
(highly intensive HOT random updates on unlogged table with
synchronized_commit=off), and speeds up WAL replaying (as were
found by Heikki Linnakangas).
Same approach were implemented by Heikki Linnakangas some time ago with
several distinctions.
---
src/backend/storage/page/bufpage.c | 78 ++++++++++++++++++++++++++++++++++++--
src/include/c.h | 59 ++++++++++++++++++++++++++++
2 files changed, 134 insertions(+), 3 deletions(-)
diff --git a/src/backend/storage/page/bufpage.c b/src/backend/storage/page/bufpage.cindex fdf045a45b..c5630e808b 100644--- a/src/backend/storage/page/bufpage.c+++ b/src/backend/storage/page/bufpage.c@@ -434,6 +434,77 @@ itemoffcompare(const void *itemidp1, const void *itemidp2)
}
/*
+ * Sort an array of itemIdSort's on itemoff, descending.+ *+ * It uses Shell sort. Given array is small and itemoffcompare is inlined,+ * it is much faster than call to qsort.+ */+static void+sort_itemIds_small(itemIdSort itemidbase, int nitems)+{+ pg_shell_sort(itemIdSortData, itemidbase, nitems, itemoffcompare);+}++/*+ * Sort an array of itemIdSort's on itemoff, descending.+ *+ * It uses bucket sort:+ * - single pass of stable prefix sort on high 8 bits+ * - and insertion sort on buckets larger than 1 element+ */+static void+sort_itemIds(itemIdSort itemidbase, int nitems)+{+ itemIdSortData copy[Max(MaxIndexTuplesPerPage, MaxHeapTuplesPerPage)];+#define NSPLIT 256+#define PREFDIV (BLCKSZ / NSPLIT)+ /* two extra elements to emulate offset on previous step */+ uint16 count[NSPLIT + 2] = {0};+ int i,+ pos,+ highbits;++ Assert(nitems <= MaxIndexTuplesPerPage);+ for (i = 0; i < nitems; i++)+ {+ highbits = itemidbase[i].itemoff / PREFDIV;+ count[highbits]++;+ }+ /* sort in decreasing order */+ for (i = NSPLIT - 1; i != 0; i--)+ count[i - 1] += count[i];++ /*+ * count[k+1] is start of bucket k, count[k] is end of bucket k, and+ * count[k] - count[k+1] is length of bucket k.+ */+ Assert(count[0] == nitems);+ for (i = 0; i < nitems; i++)+ {+ highbits = itemidbase[i].itemoff / PREFDIV;+ pos = count[highbits + 1];+ count[highbits + 1]++;+ copy[pos] = itemidbase[i];+ }+ Assert(count[1] == nitems);++ /*+ * count[k+2] is start of bucket k, count[k+1] is end of bucket k, and+ * count[k+1]-count[k+2] is length of bucket k.+ */+ for (i = NSPLIT; i > 0; i--)+ {+ if (likely(count[i] - count[i + 1] <= 1))+ continue;+ pg_insertion_sort(itemIdSortData,+ copy + count[i + 1],+ count[i] - count[i + 1],+ itemoffcompare);+ }+ memcpy(itemidbase, copy, sizeof(itemIdSortData) * nitems);+}++/*
* After removing or marking some line pointers unused, move the tuples to
* remove the gaps caused by the removed items.
*/
@@ -444,9 +515,10 @@ compactify_tuples(itemIdSort itemidbase, int nitems, Page page)
Offset upper;
int i;
- /* sort itemIdSortData array into decreasing itemoff order */- qsort((char *) itemidbase, nitems, sizeof(itemIdSortData),- itemoffcompare);+ if (nitems > 48)+ sort_itemIds(itemidbase, nitems);+ else+ sort_itemIds_small(itemidbase, nitems);
upper = phdr->pd_special;
for (i = 0; i < nitems; i++)
diff --git a/src/include/c.h b/src/include/c.hindex fba07c651f..837940d5cf 100644--- a/src/include/c.h+++ b/src/include/c.h@@ -962,6 +962,65 @@ typedef NameData *Name;
#define unlikely(x) ((x) != 0)
#endif
+/*+ * pg_shell_sort - sort for small arrays with inlinable comparator.+ * Since it is implemented as a macros it could be optimized together with+ * comparison function.+ * Gaps are "gap(i) = smallest prime number below e^i". They are close to+ * Incerpi & Sedwick gaps, but looks to be better in average.+ * It is best used with array smaller than 200 elements, and could be safely+ * used upto 1000 elements. But it degrades fast after that, and it is+ * better to use qsort.+ *+ * Arguments:+ * elem_t - type of array element (for declaring temporary variables)+ * array - pointer to elements to be sorted+ * nitems - amount of elements to be sorted+ * cmp - comparison function that accepts address of elements+ * (it is compatible with qsort comparison function).+ * Note: `cmp` argument evaluates many times.+ * Other arguments evaluates once+ */+#define pg_shell_sort_pass(elem_t, cmp, off) \+ do { \+ int _i, _j; \+ elem_t _temp; \+ for (_i = off; _i < _n; _i += off) \+ { \+ if ((cmp)(_arr+_i, _arr+_i-off) >= 0) \+ continue; \+ _temp = _arr[_i]; \+ _j = _i; \+ do { \+ _arr[_j] = _arr[_j - off]; \+ _j -= off; \+ } while (_j >= off && (cmp)(_arr+_j-off, &_temp) > 0); \+ _arr[_j] = _temp; \+ } \+ } while (0)+#define pg_shell_sort(elem_t, array, nitems, cmp) \+ do { \+ int _n = (nitems); \+ elem_t* _arr = (array); \+ static const int _offsets[] = {401, 139, 53, 19, 7, 3}; \+ int _noff, _off; \+ for (_noff = 0; _noff < lengthof(_offsets); _noff++) { \+ _off = _offsets[_noff]; \+ pg_shell_sort_pass(elem_t, (cmp), _off); \+ } \+ pg_shell_sort_pass(elem_t, (cmp), 1); \+ } while(0)+/*+ * pg_insertion_sort - just insertion sort for smallest array, or if+ * array was almost sorted already. Uses same arguments as pg_shell_sort.+ */+#define pg_insertion_sort(elem_t, array, nitems, cmp) \+ do { \+ int _n = (nitems); \+ elem_t* _arr = (array); \+ pg_shell_sort_pass(elem_t, (cmp), 1); \+ } while (0)+
/* ----------------------------------------------------------------
* Section 8: random stuff
--
2.11.0
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: funny.falcon@postgrespro.ru, hlinnaka@iki.fi, hlinnaka@gmail.com
Subject: Re: Small improvement to compactify_tuples
In-Reply-To: <0dcb7a5afa3fae6001bd1712253cf81d@postgrespro.ru>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox