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
From 8f75fcaba0590d5150dd956a60feee5c28f4caab Mon Sep 17 00:00:00 2001
From: Sokolov Yura <funny.fal...@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.c
index 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.h
index 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
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
