Re: [HACKERS] Small improvement to compactify_tuples
On Wed, Nov 8, 2017 at 12:59 PM, Andres Freundwrote: > I complained about multiple related things, I'm not exactly sure what > exactly you're referring to here: > - The fact that HeapTupleHeaderData's are commonly iterated over in > reverse order is bad for performance. For shared buffers resident > workloads involving seqscans that yields 15-25% slowdowns for me. It's > trivial to fix that by just changing iteration order, but that > obviously changes results. But we could reorder the page during heap > pruning. FWIW, the classic page layout (the one that appears in Gray's Transaction Processing Systems, at any rate) has the ItemId array at the end of the page and the tuples at the start (immediately after a generic page header) -- it's the other way around. I think that that has its pros and cons. > - The layout of items in index pages is suboptimal. We regularly do > binary searches over the the linearly ordered items, which is cache > inefficient. So instead we should sort items as [1/2, 1/4, 3/4, ...] > elements, which will access items in a close-ish to linear manner. I still think that we can repurpose each ItemId's lp_len as an abbreviated key in internal index pages [1], and always get IndexTuple size through the index tuple header. I actual got as far as writing a very rough prototype of that. That's obviously a significant project, but it seems doable. [1] https://www.postgresql.org/message-id/CAH2-Wz=mv4dmoapficrsyntv2kinxeotbwuy5r7fxxoc-oe...@mail.gmail.com -- Peter Geoghegan -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Small improvement to compactify_tuples
On 2017-11-08 12:02:40 -0500, Tom Lane wrote: > BTW, it strikes me that in considering the rebuild-the-page approach, > we should not have blinders on and just measure the speed of > PageRepairFragmentation. Rather, we should take a look at what happens > subsequently given a physically-ordered set of tuples. I can recall > Andres or someone moaning awhile ago about lack of locality of access in > index page searches --- maybe applying that approach while vacuuming > indexes will help? I complained about multiple related things, I'm not exactly sure what exactly you're referring to here: - The fact that HeapTupleHeaderData's are commonly iterated over in reverse order is bad for performance. For shared buffers resident workloads involving seqscans that yields 15-25% slowdowns for me. It's trivial to fix that by just changing iteration order, but that obviously changes results. But we could reorder the page during heap pruning. But that's fairly independent of indexes, so I'm not sure whether that's what you're referring. - The layout of items in index pages is suboptimal. We regularly do binary searches over the the linearly ordered items, which is cache inefficient. So instead we should sort items as [1/2, 1/4, 3/4, ...] elements, which will access items in a close-ish to linear manner. But that's fairly independent of pruning, so I'm not sure whether that's what you're referring to, either. Greetings, Andres Freund -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Small improvement to compactify_tuples
2017-11-08 20:02 GMT+03:00 Tom Lane: > > Claudio Freire writes: > > What's perhaps not clear is whether there are better ideas. Like > > rebuilding the page as Tom proposes, which doesn't seem like a bad > > idea. Bucket sort already is O(bytes), just as memcopy, only it has a > > lower constant factor (it's bytes/256 in the original patch), which > > might make copying the whole page an extra time lose against bucket > > sort in a few cases. > > > Deciding that last point does need more benchmarking. That doesn't > > mean the other improvements can't be pursued in the meanwhile, right? > > Well, I doubt we're going to end up committing more than one of these > ideas. The question is which way is best. If people are willing to > put in the work to test all of them, let's do it. > > BTW, it strikes me that in considering the rebuild-the-page approach, > we should not have blinders on and just measure the speed of > PageRepairFragmentation. Rather, we should take a look at what happens > subsequently given a physically-ordered set of tuples. I can recall > Andres or someone moaning awhile ago about lack of locality of access in > index page searches --- maybe applying that approach while vacuuming > indexes will help? > > regards, tom lane I'd like to add qsort_template.h as Claudio suggested, ie in a way close to simplehash.h. With such template header, there will be no need in qsort_tuple_gen.pl . With regards, Sokolov Yura
Re: [HACKERS] Small improvement to compactify_tuples
Claudio Freirewrites: > What's perhaps not clear is whether there are better ideas. Like > rebuilding the page as Tom proposes, which doesn't seem like a bad > idea. Bucket sort already is O(bytes), just as memcopy, only it has a > lower constant factor (it's bytes/256 in the original patch), which > might make copying the whole page an extra time lose against bucket > sort in a few cases. > Deciding that last point does need more benchmarking. That doesn't > mean the other improvements can't be pursued in the meanwhile, right? Well, I doubt we're going to end up committing more than one of these ideas. The question is which way is best. If people are willing to put in the work to test all of them, let's do it. BTW, it strikes me that in considering the rebuild-the-page approach, we should not have blinders on and just measure the speed of PageRepairFragmentation. Rather, we should take a look at what happens subsequently given a physically-ordered set of tuples. I can recall Andres or someone moaning awhile ago about lack of locality of access in index page searches --- maybe applying that approach while vacuuming indexes will help? regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Small improvement to compactify_tuples
On Wed, Nov 8, 2017 at 12:33 PM, Tom Lanewrote: > Robert Haas writes: >> On Tue, Nov 7, 2017 at 4:39 PM, Tom Lane wrote: >>> What I'm getting from the standard pgbench measurements, on both machines, >>> is that this patch might be a couple percent slower than HEAD, but that is >>> barely above the noise floor so I'm not too sure about it. > >> Hmm. It seems like slowing down single client performance by a couple >> of percent is something that we really don't want to do. > > I do not think there is any change here that can be proven to always be a > win. Certainly the original patch, which proposes to replace an O(n log n) > sort algorithm with an O(n^2) one, should not be thought to be that. > The question to focus on is what's the average case, and I'm not sure how > to decide what the average case is. But more than two test scenarios > would be a good start. > > regards, tom lane Doing no change to the overall algorithm and replacing qsort with an inlineable type-specific one should be a net win in all cases. Doing bucket sort with a qsort of large buckets (or small tuple arrays) should also be a net win in all cases. Using shell sort might not seem clear, but lets not forget the original patch only uses it in very small arrays and very infrequently at that. What's perhaps not clear is whether there are better ideas. Like rebuilding the page as Tom proposes, which doesn't seem like a bad idea. Bucket sort already is O(bytes), just as memcopy, only it has a lower constant factor (it's bytes/256 in the original patch), which might make copying the whole page an extra time lose against bucket sort in a few cases. Deciding that last point does need more benchmarking. That doesn't mean the other improvements can't be pursued in the meanwhile, right? -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Small improvement to compactify_tuples
On Wed, Nov 8, 2017 at 8:19 AM, Robert Haaswrote: > I don't remember any more just how much faster qsort_tuple() and > qsort_ssup() are than plain qsort(), but it was significant enough to > convince me to commit 337b6f5ecf05b21b5e997986884d097d60e4e3d0... IIRC, qsort_ssup() was about 20% faster at the time, while qsort_tuple() was 5% - 10% faster. -- Peter Geoghegan -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Small improvement to compactify_tuples
Robert Haaswrites: > Just to throw a random idea out here, we currently have > gen_qsort_tuple.pl producing qsort_tuple() and qsort_ssup(). Maybe it > could be modified to also produce a specialized qsort_itemids(). That > might be noticeably faster that our general-purpose qsort() for the > reasons mentioned in the comments in gen_qsort_tuple.pl, viz: +1 for somebody trying that (I'm not volunteering, though). regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Small improvement to compactify_tuples
On Wed, Nov 8, 2017 at 10:33 AM, Tom Lanewrote: > I do not think there is any change here that can be proven to always be a > win. Certainly the original patch, which proposes to replace an O(n log n) > sort algorithm with an O(n^2) one, should not be thought to be that. > The question to focus on is what's the average case, and I'm not sure how > to decide what the average case is. But more than two test scenarios > would be a good start. I appreciate the difficulties here; I'm just urging caution. Let's not change things just to clear this patch off our plate. Just to throw a random idea out here, we currently have gen_qsort_tuple.pl producing qsort_tuple() and qsort_ssup(). Maybe it could be modified to also produce a specialized qsort_itemids(). That might be noticeably faster that our general-purpose qsort() for the reasons mentioned in the comments in gen_qsort_tuple.pl, viz: # The major effects are (1) inlining simple tuple comparators is much faster # than jumping through a function pointer and (2) swap and vecswap operations # specialized to the particular data type of interest (in this case, SortTuple) # are faster than the generic routines. I don't remember any more just how much faster qsort_tuple() and qsort_ssup() are than plain qsort(), but it was significant enough to convince me to commit 337b6f5ecf05b21b5e997986884d097d60e4e3d0... -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Small improvement to compactify_tuples
Robert Haaswrites: > On Tue, Nov 7, 2017 at 4:39 PM, Tom Lane wrote: >> What I'm getting from the standard pgbench measurements, on both machines, >> is that this patch might be a couple percent slower than HEAD, but that is >> barely above the noise floor so I'm not too sure about it. > Hmm. It seems like slowing down single client performance by a couple > of percent is something that we really don't want to do. I do not think there is any change here that can be proven to always be a win. Certainly the original patch, which proposes to replace an O(n log n) sort algorithm with an O(n^2) one, should not be thought to be that. The question to focus on is what's the average case, and I'm not sure how to decide what the average case is. But more than two test scenarios would be a good start. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Small improvement to compactify_tuples
On Tue, Nov 7, 2017 at 4:39 PM, Tom Lanewrote: > What I'm getting from the standard pgbench measurements, on both machines, > is that this patch might be a couple percent slower than HEAD, but that is > barely above the noise floor so I'm not too sure about it. Hmm. It seems like slowing down single client performance by a couple of percent is something that we really don't want to do. -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Small improvement to compactify_tuples
On Tue, Nov 7, 2017 at 2:40 PM, Юрий Соколовwrote: >> The same is true of unique indexes vs. non-unique. > > offtopic: recently I'd a look at setting LP_DEAD in indexes. > I didn't found huge difference between unique and non-unique indices. > There is codepath that works only for unique, but it is called less > frequently than common codepath that also sets LP_DEAD. I meant to say that this is only important with UPDATEs + contention. The extra LP_DEAD setting within _bt_check_unique() makes quite a noticeable difference, at least in terms of index bloat (though less so in terms of raw TPS). -- Peter Geoghegan -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Small improvement to compactify_tuples
On Tue, Nov 7, 2017 at 2:36 PM, Tom Lanewrote: > Peter Geoghegan writes: >> My point is only that it's worth considering that this factor affects >> how representative your sympathetic case is. It's not clear how many >> PageIndexMultiDelete() calls are from opportunistic calls to >> _bt_vacuum_one_page(), how important that subset of calls is, and so >> on. Maybe it doesn't matter at all. > > According to the perf measurements I took earlier, essentially all the > compactify_tuple calls in this test case are from PageRepairFragmentation > (from heap_page_prune), not PageIndexMultiDelete. For a workload with high contention (e.g., lots of updates that follow a Zipfian distribution) lots of important cleanup has to occur within _bt_vacuum_one_page(), and with an exclusive buffer lock held. It may be that making PageIndexMultiDelete() faster pays off disproportionately well there, but I'd only expect to see that at higher client count workloads with lots of contention -- workloads that we still do quite badly on (note that we always have not done well here, even prior to commit 2ed5b87f9 -- Yura showed this at one point). It's possible that this work influenced Yura in some way. When Postgres Pro did some benchmarking of this at my request, we saw that the bloat got really bad past a certain client count. IIRC there was a clear point at around 32 or 64 clients where TPS nosedived, presumably because cleanup could not keep up. This was a 128 core box, or something like that, so you'll probably have difficulty recreating it with what's at hand. -- Peter Geoghegan -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Small improvement to compactify_tuples
2017-11-08 1:11 GMT+03:00 Peter Geoghegan: > > The same is true of unique indexes vs. non-unique. offtopic: recently I'd a look at setting LP_DEAD in indexes. I didn't found huge difference between unique and non-unique indices. There is codepath that works only for unique, but it is called less frequently than common codepath that also sets LP_DEAD.
Re: [HACKERS] Small improvement to compactify_tuples
Peter Geogheganwrites: > My point is only that it's worth considering that this factor affects > how representative your sympathetic case is. It's not clear how many > PageIndexMultiDelete() calls are from opportunistic calls to > _bt_vacuum_one_page(), how important that subset of calls is, and so > on. Maybe it doesn't matter at all. According to the perf measurements I took earlier, essentially all the compactify_tuple calls in this test case are from PageRepairFragmentation (from heap_page_prune), not PageIndexMultiDelete. I'd be the first to agree that I doubt that test case is really representative. I'd been whacking around Yura's original case to try to get PageRepairFragmentation's runtime up to some measurable fraction of the total, and while I eventually succeeded, I'm not sure that too many real workloads will look like that. However, if we can make it smaller as well as faster, that seems like a win even if it's not a measurable fraction of most workloads. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Small improvement to compactify_tuples
) On Tue, Nov 7, 2017 at 1:39 PM, Tom Lanewrote: > So I think we should seriously consider the attached, but it'd be a > good idea to benchmark it on a wider variety of platforms and test > cases. > create unlogged table test3 ( > id integer PRIMARY KEY with (fillfactor=85), > val text > ) WITH (fillfactor=85); Passing observation: Unlogged table B-Tree indexes have a much greater tendency for LP_DEAD setting/kill_prior_tuple() working out following commit 2ed5b87f9 [1], because unlogged tables were unaffected by that commit. (I've been meaning to follow up with my analysis of that regression, actually.) The same is true of unique indexes vs. non-unique. There are workloads where the opportunistic LP_DEAD setting performed by _bt_check_unique() is really important (it calls ItemIdMarkDead()). Think high contention workloads, like when Postgres is used to implement a queue table. My point is only that it's worth considering that this factor affects how representative your sympathetic case is. It's not clear how many PageIndexMultiDelete() calls are from opportunistic calls to _bt_vacuum_one_page(), how important that subset of calls is, and so on. Maybe it doesn't matter at all. [1] https://postgr.es/m/cah2-wzmyry7mnjf0gw5wtk3cszh3gqfhhoxvsyuno5pk8cu...@mail.gmail.com -- Peter Geoghegan -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Small improvement to compactify_tuples
I've been getting less and less excited about this patch, because I still couldn't measure any above-the-noise performance improvement without artificial exaggerations, and some cases seemed actually slower. However, this morning I had an epiphany: why are we sorting at all? There is no requirement that these functions preserve the physical ordering of the tuples' data areas, only that the line-pointer ordering be preserved. Indeed, reorganizing the data areas into an ordering matching the line pointers is probably a good thing, because it should improve locality of access in future scans of the page. This is trivial to implement if we copy the data into a workspace area and back again, as I was already proposing to do to avoid memmove. Moreover, at that point there's little value in a separate compactify function at all: we can integrate the data-copying logic into the line pointer scan loops in PageRepairFragmentation and PageIndexMultiDelete, and get rid of the costs of constructing the intermediate itemIdSortData arrays. That led me to the attached patch, which is the first version of any of this work that produces an above-the-noise performance win for me. I'm seeing 10-20% gains on this modified version of Yura's original example: psql -f test3setup.sql pgbench -M prepared -c 3 -s 1000 -T 300 -P 3 -n -f test3.sql (sql scripts also attached below; I'm using 1GB shared_buffers and fsync off, other parameters stock.) However, there are a couple of objections that could be raised to this patch: 1. It's trading off per-byte work, in the form of an extra memcpy, to save sorting work that has per-tuple costs. Therefore, the relatively narrow tuples used in Yura's example offer a best-case scenario; with wider tuples the performance might be worse. 2. On a platform with memmove not so much worse than memcpy as I'm seeing on my RHEL6 server, trading memmove for memcpy might not be such a win. To address point 1, I tried some measurements on the standard pgbench scenario, which uses significantly wider tuples. In hopes of addressing point 2, I also ran the measurements on a laptop running Fedora 25 (gcc 6.4.1, glibc 2.24); I haven't actually checked memmove vs memcpy on that machine, but at least it's a reasonably late-model glibc. What I'm getting from the standard pgbench measurements, on both machines, is that this patch might be a couple percent slower than HEAD, but that is barely above the noise floor so I'm not too sure about it. So I think we should seriously consider the attached, but it'd be a good idea to benchmark it on a wider variety of platforms and test cases. regards, tom lane drop table if exists test3; create unlogged table test3 ( id integer PRIMARY KEY with (fillfactor=85), val text ) WITH (fillfactor=85); insert into test3 select i, '!'||i from generate_series(1, 1000) as i; vacuum analyze; checkpoint; create or replace function dotest3(n int, scale float8) returns void language plpgsql as $$ begin for i in 1..n loop declare id1 int := random() * scale; id2 int := random() * scale; begin perform * from test3 where id = id1; update test3 set val = '!'|| id2 where id = id1; end; end loop; end $$; select dotest3(100, :scale); diff --git a/src/backend/storage/page/bufpage.c b/src/backend/storage/page/bufpage.c index b6aa2af..73b73de 100644 *** a/src/backend/storage/page/bufpage.c --- b/src/backend/storage/page/bufpage.c *** PageRestoreTempPage(Page tempPage, Page *** 415,471 } /* - * sorting support for PageRepairFragmentation and PageIndexMultiDelete - */ - typedef struct itemIdSortData - { - uint16 offsetindex; /* linp array index */ - int16 itemoff; /* page offset of item data */ - uint16 alignedlen; /* MAXALIGN(item data len) */ - } itemIdSortData; - typedef itemIdSortData *itemIdSort; - - static int - itemoffcompare(const void *itemidp1, const void *itemidp2) - { - /* Sort in decreasing itemoff order */ - return ((itemIdSort) itemidp2)->itemoff - - ((itemIdSort) itemidp1)->itemoff; - } - - /* - * After removing or marking some line pointers unused, move the tuples to - * remove the gaps caused by the removed items. - */ - static void - compactify_tuples(itemIdSort itemidbase, int nitems, Page page) - { - PageHeader phdr = (PageHeader) page; - Offset upper; - int i; - - /* sort itemIdSortData array into decreasing itemoff order */ - qsort((char *) itemidbase, nitems, sizeof(itemIdSortData), - itemoffcompare); - - upper = phdr->pd_special; - for (i = 0; i < nitems; i++) - { - itemIdSort itemidptr = [i]; - ItemId lp; - - lp = PageGetItemId(page, itemidptr->offsetindex + 1); - upper -= itemidptr->alignedlen; - memmove((char *) page + upper, - (char *) page + itemidptr->itemoff, - itemidptr->alignedlen); - lp->lp_off = upper; - } - - phdr->pd_upper = upper; - } - - /* * PageRepairFragmentation * *
Re: [HACKERS] Small improvement to compactify_tuples
On 2017-11-07 12:12:02 -0300, Claudio Freire wrote: > If you need it. I'm not particularly fond of writing code before it's needed. +1 > Otherwise, if it's a rarely-encountered corner case, I'd recommend > simply calling the stdlib's qsort. FWIW, we always map qsort onto our own implementation: #define qsort(a,b,c,d) pg_qsort(a,b,c,d) Greetings, Andres Freund -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Small improvement to compactify_tuples
On Tue, Nov 7, 2017 at 11:42 AM, Юрий Соколовwrote: > > > 2017-11-07 17:15 GMT+03:00 Claudio Freire : >> Aside from requiring all that include magic, if you place specialized >> sort functions in a reusable header, using it is as simple as >> including the type-specific header (or declaring the type macros and >> including the template), and using them as regular functions. There's >> no runtime overhead involved, especially if you declare the comparison >> function as a macro or a static inline function. The sort itself can >> be declared static inline as well, and the compiler will decide >> whether it's worth inlining. > > Ok, if no one will complain against another one qsort implementation, > I will add template header for qsort. Since qsort needs insertion sort, > it will be in a same file. > Do you approve of this? > > With regards, > Sokolov Yura If you need it. I'm not particularly fond of writing code before it's needed. If you can measure the impact for that particular case where qsort might be needed, and it's a real-world case, then by all means. Otherwise, if it's a rarely-encountered corner case, I'd recommend simply calling the stdlib's qsort. -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Small improvement to compactify_tuples
2017-11-07 17:15 GMT+03:00 Claudio Freire: > > On Mon, Nov 6, 2017 at 9:08 PM, Юрий Соколов wrote: > > 2017-11-07 1:14 GMT+03:00 Claudio Freire : > >> > >> I haven't seen this trick used in postgres, nor do I know whether it > >> would be well received, so this is more like throwing an idea to see > >> if it sticks... > >> > >> But a way to do this without macros is to have an includable > >> "template" algorithm that simply doesn't define the comparison > >> function/type, it rather assumes it: > >> > >> qsort_template.h > >> > >> #define QSORT_NAME qsort_ ## QSORT_SUFFIX > >> > >> static void QSORT_NAME(ELEM_TYPE arr, size_t num_elems) > >> { > >> ... if (ELEM_LESS(arr[a], arr[b])) > >> ... > >> } > >> > >> #undef QSORT_NAME > >> > >> Then, in "offset_qsort.h": > >> > >> #define QSORT_SUFFIX offset > >> #define ELEM_TYPE offset > >> #define ELEM_LESS(a,b) ((a) < (b)) > >> > >> #include "qsort_template.h" > >> > >> #undef QSORT_SUFFIX > >> #undef ELEM_TYPE > >> #undef ELEM_LESS > >> > >> Now, I realize this may have its cons, but it does simplify > >> maintainance of type-specific or parameterized variants of > >> performance-critical functions. > >> > >> > I can do specialized qsort for this case. But it will be larger bunch of > >> > code, than > >> > shell sort. > >> > > >> >> And I'd recommend doing that when there is a need, and I don't think > >> >> this patch really needs it, since bucket sort handles most cases > >> >> anyway. > >> > > >> > And it still needs insertion sort for buckets. > >> > I can agree to get rid of shell sort. But insertion sort is necessary. > >> > >> I didn't suggest getting rid of insertion sort. But the trick above is > >> equally applicable to insertion sort. > > > > This trick is used in simplehash.h . I agree, it could be useful for qsort. > > This will not make qsort inlineable, but will reduce overhead much. > > > > This trick is too heavy-weight for insertion sort alone, though. Without > > shellsort, insertion sort could be expressed in 14 line macros ( 8 lines > > without curly braces). But if insertion sort will be defined together with > > qsort (because qsort still needs it), then it is justifiable. > > What do you mean by heavy-weight? I mean, I've already made reusable sort implementation with macros that is called like a function (with type parameter). If we are talking only about insertion sort, then such macros looks much prettier than including file. But qsort is better implemented with included template-header. BTW, there is example of defining many functions with call to template macro instead of including template header: https://github.com/attractivechaos/klib/blob/master/khash.h But it looks ugly. > > Aside from requiring all that include magic, if you place specialized > sort functions in a reusable header, using it is as simple as > including the type-specific header (or declaring the type macros and > including the template), and using them as regular functions. There's > no runtime overhead involved, especially if you declare the comparison > function as a macro or a static inline function. The sort itself can > be declared static inline as well, and the compiler will decide > whether it's worth inlining. Ok, if no one will complain against another one qsort implementation, I will add template header for qsort. Since qsort needs insertion sort, it will be in a same file. Do you approve of this? With regards, Sokolov Yura
Re: [HACKERS] Small improvement to compactify_tuples
On Mon, Nov 6, 2017 at 9:08 PM, Юрий Соколовwrote: > 2017-11-07 1:14 GMT+03:00 Claudio Freire : >> >> I haven't seen this trick used in postgres, nor do I know whether it >> would be well received, so this is more like throwing an idea to see >> if it sticks... >> >> But a way to do this without macros is to have an includable >> "template" algorithm that simply doesn't define the comparison >> function/type, it rather assumes it: >> >> qsort_template.h >> >> #define QSORT_NAME qsort_ ## QSORT_SUFFIX >> >> static void QSORT_NAME(ELEM_TYPE arr, size_t num_elems) >> { >> ... if (ELEM_LESS(arr[a], arr[b])) >> ... >> } >> >> #undef QSORT_NAME >> >> Then, in "offset_qsort.h": >> >> #define QSORT_SUFFIX offset >> #define ELEM_TYPE offset >> #define ELEM_LESS(a,b) ((a) < (b)) >> >> #include "qsort_template.h" >> >> #undef QSORT_SUFFIX >> #undef ELEM_TYPE >> #undef ELEM_LESS >> >> Now, I realize this may have its cons, but it does simplify >> maintainance of type-specific or parameterized variants of >> performance-critical functions. >> >> > I can do specialized qsort for this case. But it will be larger bunch of >> > code, than >> > shell sort. >> > >> >> And I'd recommend doing that when there is a need, and I don't think >> >> this patch really needs it, since bucket sort handles most cases >> >> anyway. >> > >> > And it still needs insertion sort for buckets. >> > I can agree to get rid of shell sort. But insertion sort is necessary. >> >> I didn't suggest getting rid of insertion sort. But the trick above is >> equally applicable to insertion sort. > > This trick is used in simplehash.h . I agree, it could be useful for qsort. > This will not make qsort inlineable, but will reduce overhead much. > > This trick is too heavy-weight for insertion sort alone, though. Without > shellsort, insertion sort could be expressed in 14 line macros ( 8 lines > without curly braces). But if insertion sort will be defined together with > qsort (because qsort still needs it), then it is justifiable. What do you mean by heavy-weight? Aside from requiring all that include magic, if you place specialized sort functions in a reusable header, using it is as simple as including the type-specific header (or declaring the type macros and including the template), and using them as regular functions. There's no runtime overhead involved, especially if you declare the comparison function as a macro or a static inline function. The sort itself can be declared static inline as well, and the compiler will decide whether it's worth inlining. -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Small improvement to compactify_tuples
2017-11-07 1:14 GMT+03:00 Claudio Freire: > > On Mon, Nov 6, 2017 at 6:58 PM, Юрий Соколов wrote: > > > > 2017-11-06 17:55 GMT+03:00 Claudio Freire : > >> > >> On Mon, Nov 6, 2017 at 11:50 AM, Юрий Соколов > >> wrote: > >> >> Maybe leave a fallback to qsort if some corner case produces big > >> >> buckets? > >> > > >> > For 8kb pages, each bucket is per 32 bytes. So, for heap pages it is at > >> > most 1 heap-tuple per bucket, and for index pages it is at most 2 index > >> > tuples per bucket. For 32kb pages it is 4 heap-tuples and 8 index-tuples > >> > per bucket. > >> > It will be unnecessary overhead to call non-inlineable qsort in this > >> > cases > >> > > >> > So, I think, shell sort could be removed, but insertion sort have to > >> > remain. > >> > > >> > I'd prefer shell sort to remain also. It could be useful in other places > >> > also, > >> > because it is easily inlinable, and provides comparable to qsort > >> > performance > >> > up to several hundreds of elements. > >> > >> I'd rather have an inlineable qsort. > > > > But qsort is recursive. It is quite hard to make it inlineable. And still it > > will be > > much heavier than insertion sort (btw, all qsort implementations uses > > insertion > > sort for small arrays). And it will be heavier than shell sort for small > > arrays. > > I haven't seen this trick used in postgres, nor do I know whether it > would be well received, so this is more like throwing an idea to see > if it sticks... > > But a way to do this without macros is to have an includable > "template" algorithm that simply doesn't define the comparison > function/type, it rather assumes it: > > qsort_template.h > > #define QSORT_NAME qsort_ ## QSORT_SUFFIX > > static void QSORT_NAME(ELEM_TYPE arr, size_t num_elems) > { > ... if (ELEM_LESS(arr[a], arr[b])) > ... > } > > #undef QSORT_NAME > > Then, in "offset_qsort.h": > > #define QSORT_SUFFIX offset > #define ELEM_TYPE offset > #define ELEM_LESS(a,b) ((a) < (b)) > > #include "qsort_template.h" > > #undef QSORT_SUFFIX > #undef ELEM_TYPE > #undef ELEM_LESS > > Now, I realize this may have its cons, but it does simplify > maintainance of type-specific or parameterized variants of > performance-critical functions. > > > I can do specialized qsort for this case. But it will be larger bunch of > > code, than > > shell sort. > > > >> And I'd recommend doing that when there is a need, and I don't think > >> this patch really needs it, since bucket sort handles most cases > >> anyway. > > > > And it still needs insertion sort for buckets. > > I can agree to get rid of shell sort. But insertion sort is necessary. > > I didn't suggest getting rid of insertion sort. But the trick above is > equally applicable to insertion sort. This trick is used in simplehash.h . I agree, it could be useful for qsort. This will not make qsort inlineable, but will reduce overhead much. This trick is too heavy-weight for insertion sort alone, though. Without shellsort, insertion sort could be expressed in 14 line macros ( 8 lines without curly braces). But if insertion sort will be defined together with qsort (because qsort still needs it), then it is justifiable.
Re: [HACKERS] Small improvement to compactify_tuples
On Mon, Nov 6, 2017 at 6:58 PM, Юрий Соколовwrote: > > 2017-11-06 17:55 GMT+03:00 Claudio Freire : >> >> On Mon, Nov 6, 2017 at 11:50 AM, Юрий Соколов >> wrote: >> >> Maybe leave a fallback to qsort if some corner case produces big >> >> buckets? >> > >> > For 8kb pages, each bucket is per 32 bytes. So, for heap pages it is at >> > most 1 heap-tuple per bucket, and for index pages it is at most 2 index >> > tuples per bucket. For 32kb pages it is 4 heap-tuples and 8 index-tuples >> > per bucket. >> > It will be unnecessary overhead to call non-inlineable qsort in this >> > cases >> > >> > So, I think, shell sort could be removed, but insertion sort have to >> > remain. >> > >> > I'd prefer shell sort to remain also. It could be useful in other places >> > also, >> > because it is easily inlinable, and provides comparable to qsort >> > performance >> > up to several hundreds of elements. >> >> I'd rather have an inlineable qsort. > > But qsort is recursive. It is quite hard to make it inlineable. And still it > will be > much heavier than insertion sort (btw, all qsort implementations uses > insertion > sort for small arrays). And it will be heavier than shell sort for small > arrays. I haven't seen this trick used in postgres, nor do I know whether it would be well received, so this is more like throwing an idea to see if it sticks... But a way to do this without macros is to have an includable "template" algorithm that simply doesn't define the comparison function/type, it rather assumes it: qsort_template.h #define QSORT_NAME qsort_ ## QSORT_SUFFIX static void QSORT_NAME(ELEM_TYPE arr, size_t num_elems) { ... if (ELEM_LESS(arr[a], arr[b])) ... } #undef QSORT_NAME Then, in "offset_qsort.h": #define QSORT_SUFFIX offset #define ELEM_TYPE offset #define ELEM_LESS(a,b) ((a) < (b)) #include "qsort_template.h" #undef QSORT_SUFFIX #undef ELEM_TYPE #undef ELEM_LESS Now, I realize this may have its cons, but it does simplify maintainance of type-specific or parameterized variants of performance-critical functions. > I can do specialized qsort for this case. But it will be larger bunch of > code, than > shell sort. > >> And I'd recommend doing that when there is a need, and I don't think >> this patch really needs it, since bucket sort handles most cases >> anyway. > > And it still needs insertion sort for buckets. > I can agree to get rid of shell sort. But insertion sort is necessary. I didn't suggest getting rid of insertion sort. But the trick above is equally applicable to insertion sort. -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Small improvement to compactify_tuples
2017-11-06 17:55 GMT+03:00 Claudio Freire: > > On Mon, Nov 6, 2017 at 11:50 AM, Юрий Соколов wrote: > >> Maybe leave a fallback to qsort if some corner case produces big buckets? > > > > For 8kb pages, each bucket is per 32 bytes. So, for heap pages it is at > > most 1 heap-tuple per bucket, and for index pages it is at most 2 index > > tuples per bucket. For 32kb pages it is 4 heap-tuples and 8 index-tuples > > per bucket. > > It will be unnecessary overhead to call non-inlineable qsort in this cases > > > > So, I think, shell sort could be removed, but insertion sort have to remain. > > > > I'd prefer shell sort to remain also. It could be useful in other places > > also, > > because it is easily inlinable, and provides comparable to qsort performance > > up to several hundreds of elements. > > I'd rather have an inlineable qsort. But qsort is recursive. It is quite hard to make it inlineable. And still it will be much heavier than insertion sort (btw, all qsort implementations uses insertion sort for small arrays). And it will be heavier than shell sort for small arrays. I can do specialized qsort for this case. But it will be larger bunch of code, than shell sort. > And I'd recommend doing that when there is a need, and I don't think > this patch really needs it, since bucket sort handles most cases > anyway. And it still needs insertion sort for buckets. I can agree to get rid of shell sort. But insertion sort is necessary.
Re: [HACKERS] Small improvement to compactify_tuples
On Mon, Nov 6, 2017 at 11:50 AM, Юрий Соколовwrote: >> Maybe leave a fallback to qsort if some corner case produces big buckets? > > For 8kb pages, each bucket is per 32 bytes. So, for heap pages it is at > most 1 heap-tuple per bucket, and for index pages it is at most 2 index > tuples per bucket. For 32kb pages it is 4 heap-tuples and 8 index-tuples > per bucket. > It will be unnecessary overhead to call non-inlineable qsort in this cases > > So, I think, shell sort could be removed, but insertion sort have to remain. > > I'd prefer shell sort to remain also. It could be useful in other places > also, > because it is easily inlinable, and provides comparable to qsort performance > up to several hundreds of elements. I'd rather have an inlineable qsort. And I'd recommend doing that when there is a need, and I don't think this patch really needs it, since bucket sort handles most cases anyway. -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Small improvement to compactify_tuples
2017-11-05 20:44 GMT+03:00 Claudio Freire: > > On Sat, Nov 4, 2017 at 8:07 PM, Юрий Соколов wrote: > > 2017-11-03 5:46 GMT+03:00 Tom Lane : > >> > >> Sokolov Yura writes: > >> > [ 0001-Improve-compactify_tuples.patch, v5 or thereabouts ] > >> > >> I went to check the shellsort algorithm against Wikipedia's entry, > >> and found that this appears to be an incorrect implementation of > >> shellsort: where pg_shell_sort_pass has > >> > >> for (_i = off; _i < _n; _i += off) \ > >> > >> it seems to me that we need to have > >> > >> for (_i = off; _i < _n; _i += 1) \ > >> > >> or maybe just _i++. > > > > > > Shame on me :-( > > I've wrote shell sort several times, so I forgot to recheck myself once > > again. > > And looks like best gap sequence from wikipedia is really best > > ( {301, 132, 57, 23, 10 , 4} in my notation), > > > > > > 2017-11-03 17:37 GMT+03:00 Claudio Freire : > >> On Thu, Nov 2, 2017 at 11:46 PM, Tom Lane wrote: > >>> BTW, the originally given test case shows no measurable improvement > >>> on my box. > >> > >> I did manage to reproduce the original test and got a consistent > >> improvement. > > > > I've rechecked my self using my benchmark. > > Without memmove, compactify_tuples comsumes: > > - with qsort 11.66% cpu (pg_qsort + med3 + swapfunc + itemoffcompare + > > compactify_tuples = 5.97 + 0.51 + 2.87 + 1.88 + 0.44) > > - with just insertion sort 6.65% cpu (sort is inlined, itemoffcompare also > > inlined, so whole is compactify_tuples) > > - with just shell sort 5,98% cpu (sort is inlined again) > > - with bucket sort 1,76% cpu (sort_itemIds + compactify_tuples = 1.30 + > > 0.46) > > Is that just insertion sort without bucket sort? Yes. Just to show that inlined insertion sort is better than non-inlined qsort in this particular use-case. > Because I think shell sort has little impact in your original patch > because it's rarely exercised. With bucket sort, most buckets are very > small, too small for shell sort to do any useful work. Yes. In the patch, buckets are sorted with insertion sort. Shell sort is used only on full array if its size less than 48. Bucket sort has constant overhead of traversing all buckets, even if they are empty. That is why I think, shell sort for small arrays is better. Though, I didn't measure that carefully. And probably insertion sort for small arrays will be just enough. > Maybe leave a fallback to qsort if some corner case produces big buckets? For 8kb pages, each bucket is per 32 bytes. So, for heap pages it is at most 1 heap-tuple per bucket, and for index pages it is at most 2 index tuples per bucket. For 32kb pages it is 4 heap-tuples and 8 index-tuples per bucket. It will be unnecessary overhead to call non-inlineable qsort in this cases So, I think, shell sort could be removed, but insertion sort have to remain. I'd prefer shell sort to remain also. It could be useful in other places also, because it is easily inlinable, and provides comparable to qsort performance up to several hundreds of elements. With regards, Sokolov Yura aka funny_falcon.
Re: [HACKERS] Small improvement to compactify_tuples
On Sat, Nov 4, 2017 at 8:07 PM, Юрий Соколовwrote: > 2017-11-03 5:46 GMT+03:00 Tom Lane : >> >> Sokolov Yura writes: >> > [ 0001-Improve-compactify_tuples.patch, v5 or thereabouts ] >> >> I went to check the shellsort algorithm against Wikipedia's entry, >> and found that this appears to be an incorrect implementation of >> shellsort: where pg_shell_sort_pass has >> >> for (_i = off; _i < _n; _i += off) \ >> >> it seems to me that we need to have >> >> for (_i = off; _i < _n; _i += 1) \ >> >> or maybe just _i++. > > > Shame on me :-( > I've wrote shell sort several times, so I forgot to recheck myself once > again. > And looks like best gap sequence from wikipedia is really best > ( {301, 132, 57, 23, 10 , 4} in my notation), > > > 2017-11-03 17:37 GMT+03:00 Claudio Freire : >> On Thu, Nov 2, 2017 at 11:46 PM, Tom Lane wrote: >>> BTW, the originally given test case shows no measurable improvement >>> on my box. >> >> I did manage to reproduce the original test and got a consistent >> improvement. > > I've rechecked my self using my benchmark. > Without memmove, compactify_tuples comsumes: > - with qsort 11.66% cpu (pg_qsort + med3 + swapfunc + itemoffcompare + > compactify_tuples = 5.97 + 0.51 + 2.87 + 1.88 + 0.44) > - with just insertion sort 6.65% cpu (sort is inlined, itemoffcompare also > inlined, so whole is compactify_tuples) > - with just shell sort 5,98% cpu (sort is inlined again) > - with bucket sort 1,76% cpu (sort_itemIds + compactify_tuples = 1.30 + > 0.46) Is that just insertion sort without bucket sort? Because I think shell sort has little impact in your original patch because it's rarely exercised. With bucket sort, most buckets are very small, too small for shell sort to do any useful work. That's why I'm inclined to agree with Tom in that we could safely simplify it out, remove it, without much impact. Maybe leave a fallback to qsort if some corner case produces big buckets? -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Small improvement to compactify_tuples
Юрий Соколовwrote: tps is also reflects changes: ~17ktps with qsort ~19ktps with bucket sort Also vacuum of benchmark's table is also improved: ~3s with qsort, ~2.4s with bucket sort One thing that you have to be careful with when it comes to our qsort with partially presored inputs is what I like to call "banana skin effects": https://postgr.es/m/cah2-wzku2xk2dpz7n8-a1mvuuttuvhqkfna+eutwnwctgyc...@mail.gmail.com This may have nothing at all to do with your results; I'm just pointing it out as a possibility. -- Peter Geoghegan -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Small improvement to compactify_tuples
2017-11-03 5:46 GMT+03:00 Tom Lane: > > Sokolov Yura writes: > > [ 0001-Improve-compactify_tuples.patch, v5 or thereabouts ] > > I went to check the shellsort algorithm against Wikipedia's entry, > and found that this appears to be an incorrect implementation of > shellsort: where pg_shell_sort_pass has > > for (_i = off; _i < _n; _i += off) \ > > it seems to me that we need to have > > for (_i = off; _i < _n; _i += 1) \ > > or maybe just _i++. Shame on me :-( I've wrote shell sort several times, so I forgot to recheck myself once again. And looks like best gap sequence from wikipedia is really best ( {301, 132, 57, 23, 10 , 4} in my notation), 2017-11-03 17:37 GMT+03:00 Claudio Freire : > On Thu, Nov 2, 2017 at 11:46 PM, Tom Lane wrote: >> BTW, the originally given test case shows no measurable improvement >> on my box. > > I did manage to reproduce the original test and got a consistent improvement. I've rechecked my self using my benchmark. Without memmove, compactify_tuples comsumes: - with qsort 11.66% cpu (pg_qsort + med3 + swapfunc + itemoffcompare + compactify_tuples = 5.97 + 0.51 + 2.87 + 1.88 + 0.44) - with just insertion sort 6.65% cpu (sort is inlined, itemoffcompare also inlined, so whole is compactify_tuples) - with just shell sort 5,98% cpu (sort is inlined again) - with bucket sort 1,76% cpu (sort_itemIds + compactify_tuples = 1.30 + 0.46) (memmove consumes 1.29% cpu) tps is also reflects changes: ~17ktps with qsort ~19ktps with bucket sort Also vacuum of benchmark's table is also improved: ~3s with qsort, ~2.4s with bucket sort Of course, this benchmark is quite synthetic: table is unlogged, and tuple is small, and synchronous commit is off. Though, such table is still useful in some situations (think of not-too-important, but useful counters, like "photo watch count"). And patch affects not only this synthetic benchmark. It affects restore performance, as Heikki mentioned, and cpu consumption of Vacuum (though vacuum is more io bound). > I think we should remove pg_shell_sort and just use pg_insertion_sort. Using shell sort is just a bit safer. Doubtfully worst pattern (for insertion sort) will appear, but what if? Shellsort is a bit better on whole array (5.98% vs 6.65%). Though on small array difference will be much smaller. With regards, Sokolov Yura aka funny_falcon
Re: [HACKERS] Small improvement to compactify_tuples
On Fri, Nov 3, 2017 at 4:30 PM, Tom Lanewrote: > Claudio Freire writes: >> On Thu, Nov 2, 2017 at 11:46 PM, Tom Lane wrote: >>> BTW, the originally given test case shows no measurable improvement >>> on my box. > >> I did manage to reproduce the original test and got a consistent improvement. > > This gave me the idea to memcpy the page into some workspace and then use > memcpy, not memmove, to put the tuples back into the caller's copy of the > page. That gave me about a 50% improvement in observed TPS, and a perf > profile like this: > > + 38.50%38.40%299520 postmaster postgres > [.] compactify_tuples > + 31.11%31.02%241975 postmaster libc-2.12.so > [.] memcpy > +8.74% 8.72% 68022 postmaster postgres > [.] itemoffcompare > +6.51% 6.49% 50625 postmaster postgres > [.] compactify_tuples_loop > +4.21% 4.19% 32719 postmaster postgres > [.] pg_qsort > +1.70% 1.69% 13213 postmaster postgres > [.] memcpy@plt > > There still doesn't seem to be any point in replacing the qsort, > but it does seem like something like the second attached patch > might be worth doing. > > So I'm now wondering why my results seem to be so much different > from those of other people who have tried this, both as to whether > compactify_tuples is worth working on at all and as to what needs > to be done to it if so. Thoughts? > > regards, tom lane > I'm going to venture a guess that the version of gcc and libc, and build options used both in the libc (ie: the distro) and postgres may play a part here. I'm running with glibc 2.22, for instance, and building with gcc 4.8.5. I will try and benchmark memcpy vs memmove and see what the performance difference is there with my versions, too. This may heavily depend on compiler optimizations that may vary between versions, since memcpy/memmove tend to be inlined a lot. -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Small improvement to compactify_tuples
I wrote: > Have not looked at the 0002 patch yet. I looked at that one, and it seems to be a potential win with no downside, so pushed. (I tweaked it slightly to avoid an unnecessary conflict with the test patch I posted earlier.) regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Small improvement to compactify_tuples
Claudio Freirewrites: > On Thu, Nov 2, 2017 at 11:46 PM, Tom Lane wrote: >> BTW, the originally given test case shows no measurable improvement >> on my box. > I did manage to reproduce the original test and got a consistent improvement. It occurred to me that I could force the issue by hacking bufpage.c to execute compactify_tuples multiple times each time it was called, as in the first patch attached below. This has nothing directly to do with real performance of course, but it's making use of the PG system to provide realistic test data for microbenchmarking compactify_tuples. I was a bit surprised to find that I had to set the repeat count to 1000 to make compactify_tuples really dominate the runtime (while using the originally posted test case ... maybe there's a better one?). But once I did get it to dominate the runtime, perf gave me this for the CPU hotspots: + 27.97%27.88%229040 postmaster libc-2.12.so [.] memmove + 14.61%14.57%119704 postmaster postgres [.] compactify_tuples + 12.40%12.37%101566 postmaster libc-2.12.so [.] _wordcopy_bwd_aligned + 11.68%11.65% 95685 postmaster libc-2.12.so [.] _wordcopy_fwd_aligned +7.67% 7.64% 62801 postmaster postgres [.] itemoffcompare +7.00% 6.98% 57303 postmaster postgres [.] compactify_tuples_loop +4.53% 4.52% 37111 postmaster postgres [.] pg_qsort +1.71% 1.70% 13992 postmaster libc-2.12.so [.] memcpy which says that micro-optimizing the sort step is a complete, utter waste of time, and what we need to be worried about is the data copying part. The memcpy part of the above is presumably from the scaffolding memcpy's in compactify_tuples_loop, which is interesting because that's moving as much data as the memmove's are. So at least with RHEL6's version of glibc, memmove is apparently a lot slower than memcpy. This gave me the idea to memcpy the page into some workspace and then use memcpy, not memmove, to put the tuples back into the caller's copy of the page. That gave me about a 50% improvement in observed TPS, and a perf profile like this: + 38.50%38.40%299520 postmaster postgres [.] compactify_tuples + 31.11%31.02%241975 postmaster libc-2.12.so [.] memcpy +8.74% 8.72% 68022 postmaster postgres [.] itemoffcompare +6.51% 6.49% 50625 postmaster postgres [.] compactify_tuples_loop +4.21% 4.19% 32719 postmaster postgres [.] pg_qsort +1.70% 1.69% 13213 postmaster postgres [.] memcpy@plt There still doesn't seem to be any point in replacing the qsort, but it does seem like something like the second attached patch might be worth doing. So I'm now wondering why my results seem to be so much different from those of other people who have tried this, both as to whether compactify_tuples is worth working on at all and as to what needs to be done to it if so. Thoughts? regards, tom lane diff --git a/src/backend/storage/page/bufpage.c b/src/backend/storage/page/bufpage.c index 41642eb..bf6d308 100644 *** a/src/backend/storage/page/bufpage.c --- b/src/backend/storage/page/bufpage.c *** compactify_tuples(itemIdSort itemidbase, *** 465,470 --- 465,489 phdr->pd_upper = upper; } + static void + compactify_tuples_loop(itemIdSort itemidbase, int nitems, Page page) + { + itemIdSortData copy[Max(MaxIndexTuplesPerPage, MaxHeapTuplesPerPage)]; + union { + char page[BLCKSZ]; + double align; + } pagecopy; + int i; + + for (i = 1; i < 1000; i++) + { + memcpy(copy, itemidbase, sizeof(itemIdSortData) * nitems); + memcpy(pagecopy.page, page, BLCKSZ); + compactify_tuples(copy, nitems, pagecopy.page); + } + compactify_tuples(itemidbase, nitems, page); + } + /* * PageRepairFragmentation * *** PageRepairFragmentation(Page page) *** 560,566 errmsg("corrupted item lengths: total %u, available space %u", (unsigned int) totallen, pd_special - pd_lower))); ! compactify_tuples(itemidbase, nstorage, page); } /* Set hint bit for PageAddItem */ --- 579,585 errmsg("corrupted item lengths: total %u, available space %u", (unsigned int) totallen, pd_special - pd_lower))); ! compactify_tuples_loop(itemidbase, nstorage, page); } /* Set hint bit for PageAddItem */ *** PageIndexMultiDelete(Page page, OffsetNu *** 940,946 phdr->pd_lower = SizeOfPageHeaderData + nused *
Re: [HACKERS] Small improvement to compactify_tuples
On Thu, Nov 2, 2017 at 11:46 PM, Tom Lanewrote: > Sokolov Yura writes: >> [ 0001-Improve-compactify_tuples.patch, v5 or thereabouts ] > > I started to review this patch. I spent a fair amount of time on > beautifying the code, because I found it rather ugly and drastically > undercommented. Once I had it to the point where it seemed readable, > I went to check the shellsort algorithm against Wikipedia's entry, > and found that this appears to be an incorrect implementation of > shellsort: where pg_shell_sort_pass has > > for (_i = off; _i < _n; _i += off) \ > > it seems to me that we need to have > > for (_i = off; _i < _n; _i += 1) \ > > or maybe just _i++. As-is, this isn't h-sorting the whole file, > but just the subset of entries that have multiple-of-h indexes > (ie, the first of the h distinct subfiles that should get sorted). > The bug is masked by the final pass of plain insertion sort, but > we are not getting the benefit we should get from the earlier passes. > > However, I'm a bit dubious that it's worth fixing that; instead > my inclination would be to rip out the shellsort implementation > entirely. The code is only using it for the nitems <= 48 case > (which makes the first three offset steps certainly no-ops) and > I am really unconvinced that it's worth expending the code space > for a shellsort rather than plain insertion sort in that case, > especially when we have good reason to think that the input data > is nearly sorted. I actually noticed that and benchmarked some variants. Neither made any noticeable difference in performance, so I decided not to complain about them. I guess the same case can be made for removing the shell sort. So I'm inclined to agree. > BTW, the originally given test case shows no measurable improvement > on my box. I did manage to reproduce the original test and got a consistent improvement. > I was eventually able to convince myself by profiling > that the patch makes us spend less time in compactify_tuples, but > this test case isn't a very convincing one. > > So, quite aside from the bug, I'm not excited about committing the > attached as-is. I think we should remove pg_shell_sort and just > use pg_insertion_sort. If somebody can show a test case that > provides a measurable speed improvement from the extra code, > I could be persuaded to reconsider. My tests modifying the shell sort didn't produce any measurable difference, but I didn't test removing it altogether. -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Small improvement to compactify_tuples
Sokolov Yurawrites: > [ 0001-Improve-compactify_tuples.patch, v5 or thereabouts ] I started to review this patch. I spent a fair amount of time on beautifying the code, because I found it rather ugly and drastically undercommented. Once I had it to the point where it seemed readable, I went to check the shellsort algorithm against Wikipedia's entry, and found that this appears to be an incorrect implementation of shellsort: where pg_shell_sort_pass has for (_i = off; _i < _n; _i += off) \ it seems to me that we need to have for (_i = off; _i < _n; _i += 1) \ or maybe just _i++. As-is, this isn't h-sorting the whole file, but just the subset of entries that have multiple-of-h indexes (ie, the first of the h distinct subfiles that should get sorted). The bug is masked by the final pass of plain insertion sort, but we are not getting the benefit we should get from the earlier passes. However, I'm a bit dubious that it's worth fixing that; instead my inclination would be to rip out the shellsort implementation entirely. The code is only using it for the nitems <= 48 case (which makes the first three offset steps certainly no-ops) and I am really unconvinced that it's worth expending the code space for a shellsort rather than plain insertion sort in that case, especially when we have good reason to think that the input data is nearly sorted. BTW, the originally given test case shows no measurable improvement on my box. I was eventually able to convince myself by profiling that the patch makes us spend less time in compactify_tuples, but this test case isn't a very convincing one. So, quite aside from the bug, I'm not excited about committing the attached as-is. I think we should remove pg_shell_sort and just use pg_insertion_sort. If somebody can show a test case that provides a measurable speed improvement from the extra code, I could be persuaded to reconsider. I also wonder if the nitems <= 48 cutoff needs to be reconsidered in light of this. But since I can hardly measure any benefit from the patch at all, I'm not in the best position to test different values for that cutoff. Have not looked at the 0002 patch yet. regards, tom lane diff --git a/src/backend/storage/page/bufpage.c b/src/backend/storage/page/bufpage.c index 41642eb..1af1b85 100644 *** a/src/backend/storage/page/bufpage.c --- b/src/backend/storage/page/bufpage.c *** *** 18,23 --- 18,24 #include "access/itup.h" #include "access/xlog.h" #include "storage/checksum.h" + #include "utils/inline_sort.h" #include "utils/memdebug.h" #include "utils/memutils.h" *** typedef struct itemIdSortData *** 425,439 } itemIdSortData; typedef itemIdSortData *itemIdSort; ! static int itemoffcompare(const void *itemidp1, const void *itemidp2) { - /* Sort in decreasing itemoff order */ return ((itemIdSort) itemidp2)->itemoff - ((itemIdSort) itemidp1)->itemoff; } /* * After removing or marking some line pointers unused, move the tuples to * remove the gaps caused by the removed items. */ --- 426,542 } itemIdSortData; typedef itemIdSortData *itemIdSort; ! /* Comparator for sorting in decreasing itemoff order */ ! static inline int itemoffcompare(const void *itemidp1, const void *itemidp2) { return ((itemIdSort) itemidp2)->itemoff - ((itemIdSort) itemidp1)->itemoff; } /* + * Sort an array of itemIdSort's on itemoff, descending. + * + * This uses Shell sort. Given that array is small and itemoffcompare + * can be inlined, it is much faster than general-purpose 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. + * + * This uses bucket sort: + * - single pass of stable prefix sort on high 8 bits of itemoffs + * - then insertion sort on buckets larger than 1 element + */ + static void + sort_itemIds(itemIdSort itemidbase, int nitems) + { + /* number of buckets to use: */ + #define NSPLIT 256 + /* divisor to scale input values into 0..NSPLIT-1: */ + #define PREFDIV (BLCKSZ / NSPLIT) + /* per-bucket counts; we need two extra elements, see below */ + uint16 count[NSPLIT + 2]; + itemIdSortData copy[Max(MaxIndexTuplesPerPage, MaxHeapTuplesPerPage)]; + int i, + max, + total, + pos, + highbits; + + Assert(nitems <= lengthof(copy)); + + /* + * Count how many items in each bucket. We assume all itemoff values are + * less than BLCKSZ, therefore dividing by PREFDIV gives a value less than + * NSPLIT. + */ + memset(count, 0, sizeof(count)); + for (i = 0; i < nitems; i++) + { + highbits = itemidbase[i].itemoff / PREFDIV; + count[highbits]++; + } + + /* + * Now convert counts to bucket position info, placing the buckets in + *
Re: [HACKERS] Small improvement to compactify_tuples
On Sat, Sep 23, 2017 at 5:56 AM, Sokolov Yurawrote: > Hello, Claudio. > > Thank you for review and confirm of improvement. > > > On 2017-09-23 01:12, Claudio Freire wrote: >> >> >> Patch 1 applies cleanly, builds, and make check runs fine. >> >> The code looks similar in style to surrounding code too, so I'm not >> going to complain about the abundance of underscores in the macros :-p >> >> I can reproduce the results in the OP's benchmark, with slightly >> different numbers, but an overall improvement of ~6%, which matches >> the OP's relative improvement. >> >> Algorithmically, everything looks sound. >> >> >> A few minor comments about patch 1: >> >> +if (max == 1) >> +goto end; >> >> That goto is unnecessary, you could just as simply say >> >> if (max > 1) >> { >>... >> } > > > Done. > (I don't like indentation, though :-( ) > >> >> >> +#define pg_shell_sort_pass(elem_t, cmp, off) \ >> +do { \ >> +int _i, _j; \ >> +elem_t _temp; \ >> +for (_i = off; _i < _n; _i += off) \ >> +{ \ >> >> _n right there isn't declared in the macro, and it isn't an argument >> either. It should be an argument, having stuff inherited from the >> enclosing context like that is confusing. >> >> Same with _arr, btw. > > > pg_shell_sort_pass is not intended to be used outside pg_shell_sort > and ph_insertion_sort, so I think, stealing from their context is ok. > Nonetheless, done. Looks good. Marking this patch as ready for committer -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Small improvement to compactify_tuples
Hello, Claudio. Thank you for review and confirm of improvement. On 2017-09-23 01:12, Claudio Freire wrote: On Tue, Sep 12, 2017 at 12:49 PM, Sokolov Yurawrote: On 2017-07-21 13:49, Sokolov Yura wrote: On 2017-05-17 17:46, Sokolov Yura wrote: Alvaro Herrera писал 2017-05-15 20:13: As I understand, these patches are logically separate, so putting them together in a single file isn't such a great idea. If you don't edit the patches further, then you're all set because we already have the previously archived patches. Next commitfest starts in a few months yet, and if you feel the need to submit corrected versions in the meantime, please do submit in separate files. (Some would even argue that each should be its own thread, but I don't think that's necessary.) Thank you for explanation. I'm adding new version of first patch with minor improvement: - I added detection of a case when all buckets are trivial (ie 0 or 1 element). In this case no need to sort buckets at all. I'm putting rebased version of second patch. Again rebased version of both patches. Now second patch applies cleanly independent of first patch. Patch 1 applies cleanly, builds, and make check runs fine. The code looks similar in style to surrounding code too, so I'm not going to complain about the abundance of underscores in the macros :-p I can reproduce the results in the OP's benchmark, with slightly different numbers, but an overall improvement of ~6%, which matches the OP's relative improvement. Algorithmically, everything looks sound. A few minor comments about patch 1: +if (max == 1) +goto end; That goto is unnecessary, you could just as simply say if (max > 1) { ... } Done. (I don't like indentation, though :-( ) +#define pg_shell_sort_pass(elem_t, cmp, off) \ +do { \ +int _i, _j; \ +elem_t _temp; \ +for (_i = off; _i < _n; _i += off) \ +{ \ _n right there isn't declared in the macro, and it isn't an argument either. It should be an argument, having stuff inherited from the enclosing context like that is confusing. Same with _arr, btw. pg_shell_sort_pass is not intended to be used outside pg_shell_sort and ph_insertion_sort, so I think, stealing from their context is ok. Nonetheless, done. Patch 2 LGTM. -- Sokolov Yura aka funny_falcon Postgres Professional: https://postgrespro.ru The Russian Postgres CompanyFrom e486014c0a7545f7bb2264d0d7ac96f0544eacdb Mon Sep 17 00:00:00 2001 From: Sokolov Yura Date: Mon, 15 May 2017 14:23:39 +0300 Subject: [PATCH] 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 | 87 -- src/include/c.h| 63 +++ 2 files changed, 147 insertions(+), 3 deletions(-) diff --git a/src/backend/storage/page/bufpage.c b/src/backend/storage/page/bufpage.c index 41642eb59c..0f9f7d5dfc 100644 --- a/src/backend/storage/page/bufpage.c +++ b/src/backend/storage/page/bufpage.c @@ -434,6 +434,86 @@ 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, +max, +total, +pos, +highbits; + + Assert(nitems <= MaxIndexTuplesPerPage); + for (i = 0; i < nitems; i++) + { + highbits = itemidbase[i].itemoff / PREFDIV; + count[highbits]++; + } + /* sort in decreasing order */ + max = total = count[NSPLIT - 1]; + for (i =
Re: [HACKERS] Small improvement to compactify_tuples
On Tue, Sep 12, 2017 at 12:49 PM, Sokolov Yurawrote: > On 2017-07-21 13:49, Sokolov Yura wrote: >> >> On 2017-05-17 17:46, Sokolov Yura wrote: >>> >>> Alvaro Herrera писал 2017-05-15 20:13: As I understand, these patches are logically separate, so putting them together in a single file isn't such a great idea. If you don't edit the patches further, then you're all set because we already have the previously archived patches. Next commitfest starts in a few months yet, and if you feel the need to submit corrected versions in the meantime, please do submit in separate files. (Some would even argue that each should be its own thread, but I don't think that's necessary.) >>> >>> >>> Thank you for explanation. >>> >>> I'm adding new version of first patch with minor improvement: >>> - I added detection of a case when all buckets are trivial >>> (ie 0 or 1 element). In this case no need to sort buckets at all. >> >> >> I'm putting rebased version of second patch. > > > Again rebased version of both patches. > Now second patch applies cleanly independent of first patch. Patch 1 applies cleanly, builds, and make check runs fine. The code looks similar in style to surrounding code too, so I'm not going to complain about the abundance of underscores in the macros :-p I can reproduce the results in the OP's benchmark, with slightly different numbers, but an overall improvement of ~6%, which matches the OP's relative improvement. Algorithmically, everything looks sound. A few minor comments about patch 1: +if (max == 1) +goto end; That goto is unnecessary, you could just as simply say if (max > 1) { ... } +#define pg_shell_sort_pass(elem_t, cmp, off) \ +do { \ +int _i, _j; \ +elem_t _temp; \ +for (_i = off; _i < _n; _i += off) \ +{ \ _n right there isn't declared in the macro, and it isn't an argument either. It should be an argument, having stuff inherited from the enclosing context like that is confusing. Same with _arr, btw. Patch 2 LGTM. -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Small improvement to compactify_tuples
On 2017-07-21 13:49, Sokolov Yura wrote: On 2017-05-17 17:46, Sokolov Yura wrote: Alvaro Herrera писал 2017-05-15 20:13: As I understand, these patches are logically separate, so putting them together in a single file isn't such a great idea. If you don't edit the patches further, then you're all set because we already have the previously archived patches. Next commitfest starts in a few months yet, and if you feel the need to submit corrected versions in the meantime, please do submit in separate files. (Some would even argue that each should be its own thread, but I don't think that's necessary.) Thank you for explanation. I'm adding new version of first patch with minor improvement: - I added detection of a case when all buckets are trivial (ie 0 or 1 element). In this case no need to sort buckets at all. I'm putting rebased version of second patch. Again rebased version of both patches. Now second patch applies cleanly independent of first patch. -- Sokolov Yura aka funny_falcon Postgres Professional: https://postgrespro.ru The Russian Postgres CompanyFrom a60ac9f79cc97bd6b8cf6932b56844d136893ff9 Mon Sep 17 00:00:00 2001 From: Sokolov YuraDate: Mon, 15 May 2017 14:23:39 +0300 Subject: [PATCH 1/2] 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 | 87 -- src/include/c.h| 59 ++ 2 files changed, 143 insertions(+), 3 deletions(-) diff --git a/src/backend/storage/page/bufpage.c b/src/backend/storage/page/bufpage.c index 41642eb59c..ba99d062b6 100644 --- a/src/backend/storage/page/bufpage.c +++ b/src/backend/storage/page/bufpage.c @@ -434,6 +434,86 @@ 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, +max, +total, +pos, +highbits; + + Assert(nitems <= MaxIndexTuplesPerPage); + for (i = 0; i < nitems; i++) + { + highbits = itemidbase[i].itemoff / PREFDIV; + count[highbits]++; + } + /* sort in decreasing order */ + max = total = count[NSPLIT - 1]; + for (i = NSPLIT - 2; i >= 0; i--) + { + max |= count[i]; + total += count[i]; + count[i] = total; + } + + /* + * 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); + + if (max == 1) + goto end; + + /* + * 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--) + { + pg_insertion_sort(itemIdSortData, + copy + count[i + 1], + count[i] - count[i + 1], + itemoffcompare); + } +end: + 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 +524,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);
Re: [HACKERS] Small improvement to compactify_tuples
On 2017-05-17 17:46, Sokolov Yura wrote: Alvaro Herrera писал 2017-05-15 20:13: As I understand, these patches are logically separate, so putting them together in a single file isn't such a great idea. If you don't edit the patches further, then you're all set because we already have the previously archived patches. Next commitfest starts in a few months yet, and if you feel the need to submit corrected versions in the meantime, please do submit in separate files. (Some would even argue that each should be its own thread, but I don't think that's necessary.) Thank you for explanation. I'm adding new version of first patch with minor improvement: - I added detection of a case when all buckets are trivial (ie 0 or 1 element). In this case no need to sort buckets at all. I'm putting rebased version of second patch. -- Sokolov Yura aka funny_falcon Postgres Professional: https://postgrespro.ru The Russian Postgres CompanyFrom 3ae5aa0401fc5028cc916d55c4b18e53bf6aa9fb Mon Sep 17 00:00:00 2001 From: Sokolov YuraDate: Mon, 15 May 2017 16:04:14 +0300 Subject: [PATCH 2/2] Simplify PageRepairFragmentation In assumption that page usually doesn't become empty, merge second loop body (collecting items with storage) into first (counting kinds of items). --- src/backend/storage/page/bufpage.c | 47 +++--- 1 file changed, 19 insertions(+), 28 deletions(-) diff --git a/src/backend/storage/page/bufpage.c b/src/backend/storage/page/bufpage.c index f28f18cff3..77cef51d02 100644 --- a/src/backend/storage/page/bufpage.c +++ b/src/backend/storage/page/bufpage.c @@ -497,6 +497,7 @@ sort_itemIds(itemIdSort itemidbase, int nitems) if (max == 1) goto end; + /* * 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. @@ -563,10 +564,11 @@ PageRepairFragmentation(Page page) Offset pd_special = ((PageHeader) page)->pd_special; ItemId lp; int nline, -nstorage, nunused; int i; Size totallen; + itemIdSortData itemidbase[MaxHeapTuplesPerPage]; + itemIdSort itemidptr = itemidbase; /* * It's worth the trouble to be more paranoid here than in most places, @@ -586,14 +588,26 @@ PageRepairFragmentation(Page page) pd_lower, pd_upper, pd_special))); nline = PageGetMaxOffsetNumber(page); - nunused = nstorage = 0; + nunused = totallen = 0; for (i = FirstOffsetNumber; i <= nline; i++) { lp = PageGetItemId(page, i); if (ItemIdIsUsed(lp)) { if (ItemIdHasStorage(lp)) -nstorage++; + { +itemidptr->offsetindex = i - 1; +itemidptr->itemoff = ItemIdGetOffset(lp); +if (unlikely(itemidptr->itemoff < (int) pd_upper || + itemidptr->itemoff >= (int) pd_special)) + ereport(ERROR, + (errcode(ERRCODE_DATA_CORRUPTED), + errmsg("corrupted item pointer: %u", + itemidptr->itemoff))); +itemidptr->alignedlen = MAXALIGN(ItemIdGetLength(lp)); +totallen += itemidptr->alignedlen; +itemidptr++; + } } else { @@ -603,7 +617,7 @@ PageRepairFragmentation(Page page) } } - if (nstorage == 0) + if (itemidptr == itemidbase) { /* Page is completely empty, so just reset it quickly */ ((PageHeader) page)->pd_upper = pd_special; @@ -611,36 +625,13 @@ PageRepairFragmentation(Page page) else { /* Need to compact the page the hard way */ - itemIdSortData itemidbase[MaxHeapTuplesPerPage]; - itemIdSort itemidptr = itemidbase; - - totallen = 0; - for (i = 0; i < nline; i++) - { - lp = PageGetItemId(page, i + 1); - if (ItemIdHasStorage(lp)) - { -itemidptr->offsetindex = i; -itemidptr->itemoff = ItemIdGetOffset(lp); -if (itemidptr->itemoff < (int) pd_upper || - itemidptr->itemoff >= (int) pd_special) - ereport(ERROR, - (errcode(ERRCODE_DATA_CORRUPTED), - errmsg("corrupted item pointer: %u", - itemidptr->itemoff))); -itemidptr->alignedlen = MAXALIGN(ItemIdGetLength(lp)); -totallen += itemidptr->alignedlen; -itemidptr++; - } - } - if (totallen > (Size) (pd_special - pd_lower)) ereport(ERROR, (errcode(ERRCODE_DATA_CORRUPTED), errmsg("corrupted item lengths: total %u, available space %u", (unsigned int) totallen, pd_special - pd_lower))); - compactify_tuples(itemidbase, nstorage, page); + compactify_tuples(itemidbase, (int) (itemidptr - itemidbase), page); } /* Set hint bit for PageAddItem */ -- 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
Re: [HACKERS] Small improvement to compactify_tuples
Alvaro Herrera писал 2017-05-15 20:13: As I understand, these patches are logically separate, so putting them together in a single file isn't such a great idea. If you don't edit the patches further, then you're all set because we already have the previously archived patches. Next commitfest starts in a few months yet, and if you feel the need to submit corrected versions in the meantime, please do submit in separate files. (Some would even argue that each should be its own thread, but I don't think that's necessary.) Thank you for explanation. I'm adding new version of first patch with minor improvement: - I added detection of a case when all buckets are trivial (ie 0 or 1 element). In this case no need to sort buckets at all. -- Sokolov Yura aka funny.falcon Postgres Professional: https://postgrespro.ru The Russian Postgres CompanyFrom 4fafc870690b7de5aeab7e583780546e8170f6d0 Mon Sep 17 00:00:00 2001 From: Sokolov YuraDate: Mon, 15 May 2017 14:23:39 +0300 Subject: [PATCH 1/2] 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 | 86 -- src/include/c.h| 59 ++ 2 files changed, 142 insertions(+), 3 deletions(-) diff --git a/src/backend/storage/page/bufpage.c b/src/backend/storage/page/bufpage.c index fdf045a45b..c1bb11c354 100644 --- a/src/backend/storage/page/bufpage.c +++ b/src/backend/storage/page/bufpage.c @@ -434,6 +434,85 @@ 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, +max, +total, +pos, +highbits; + + Assert(nitems <= MaxIndexTuplesPerPage); + for (i = 0; i < nitems; i++) + { + highbits = itemidbase[i].itemoff / PREFDIV; + count[highbits]++; + } + /* sort in decreasing order */ + max = total = count[NSPLIT - 1]; + for (i = NSPLIT - 2; i >= 0; i--) + { + max |= count[i]; + total += count[i]; + count[i] = total; + } + + /* + * 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); + + if (max == 1) + goto end; + /* + * 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--) + { + pg_insertion_sort(itemIdSortData, + copy + count[i + 1], + count[i] - count[i + 1], + itemoffcompare); + } +end: + 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 +523,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;
Re: [HACKERS] Small improvement to compactify_tuples
Sokolov Yura wrote: > Sokolov Yura писал 2017-05-15 18:23: > > Alvaro Herrera писал 2017-05-15 18:04: > > > Please add these two patches to the upcoming commitfest, > > > https://commitfest.postgresql.org/ > > > > Thank you for suggestion. > > > > I've created https://commitfest.postgresql.org/14/1138/ > > As I could understand, I should attach both patches to single email > > to be show correctly in commitfest topic. So I do it with this email. > Looks like it should be single file. As I understand, these patches are logically separate, so putting them together in a single file isn't such a great idea. If you don't edit the patches further, then you're all set because we already have the previously archived patches. Next commitfest starts in a few months yet, and if you feel the need to submit corrected versions in the meantime, please do submit in separate files. (Some would even argue that each should be its own thread, but I don't think that's necessary.) -- Álvaro Herrerahttps://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Small improvement to compactify_tuples
Sokolov Yura писал 2017-05-15 18:23: Alvaro Herrera писал 2017-05-15 18:04: Please add these two patches to the upcoming commitfest, https://commitfest.postgresql.org/ Thank you for suggestion. I've created https://commitfest.postgresql.org/14/1138/ As I could understand, I should attach both patches to single email to be show correctly in commitfest topic. So I do it with this email. Please, correct me, if I do something wrong. With regards. Looks like it should be single file. -- Sokolov Yura aka funny.falcon Postgres Professional: https://postgrespro.ru The Russian Postgres CompanyFrom 231023298aad3024e31b487c8f5d2a6e68ad1da9 Mon Sep 17 00:00:00 2001 From: Sokolov YuraDate: Mon, 15 May 2017 14:23:39 +0300 Subject: [PATCH 1/2] 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
Re: [HACKERS] Small improvement to compactify_tuples
Alvaro Herrera писал 2017-05-15 18:04: Please add these two patches to the upcoming commitfest, https://commitfest.postgresql.org/ Thank you for suggestion. I've created https://commitfest.postgresql.org/14/1138/ As I could understand, I should attach both patches to single email to be show correctly in commitfest topic. So I do it with this email. Please, correct me, if I do something wrong. With regards. -- Sokolov Yura aka funny.falcon Postgres Professional: https://postgrespro.ru The Russian Postgres CompanyFrom 2cde4cb6b0c4c5868d99e13789b0ac33364d7315 Mon Sep 17 00:00:00 2001 From: Sokolov YuraDate: Mon, 15 May 2017 16:04:14 +0300 Subject: [PATCH 2/2] bufpage.c: simplify PageRepairFragmentation In assumption that page usually doesn't become empty, merge second loop body (collecting items with storage) into first (counting kinds of items). --- src/backend/storage/page/bufpage.c | 46 +++--- 1 file changed, 18 insertions(+), 28 deletions(-) diff --git a/src/backend/storage/page/bufpage.c b/src/backend/storage/page/bufpage.c index c5630e808b..61738f241f 100644 --- a/src/backend/storage/page/bufpage.c +++ b/src/backend/storage/page/bufpage.c @@ -555,10 +555,11 @@ PageRepairFragmentation(Page page) Offset pd_special = ((PageHeader) page)->pd_special; ItemId lp; int nline, -nstorage, nunused; int i; Size totallen; + itemIdSortData itemidbase[MaxHeapTuplesPerPage]; + itemIdSort itemidptr = itemidbase; /* * It's worth the trouble to be more paranoid here than in most places, @@ -578,14 +579,26 @@ PageRepairFragmentation(Page page) pd_lower, pd_upper, pd_special))); nline = PageGetMaxOffsetNumber(page); - nunused = nstorage = 0; + nunused = totallen = 0; for (i = FirstOffsetNumber; i <= nline; i++) { lp = PageGetItemId(page, i); if (ItemIdIsUsed(lp)) { if (ItemIdHasStorage(lp)) -nstorage++; + { +itemidptr->offsetindex = i - 1; +itemidptr->itemoff = ItemIdGetOffset(lp); +if (unlikely(itemidptr->itemoff < (int) pd_upper || + itemidptr->itemoff >= (int) pd_special)) + ereport(ERROR, + (errcode(ERRCODE_DATA_CORRUPTED), + errmsg("corrupted item pointer: %u", + itemidptr->itemoff))); +itemidptr->alignedlen = MAXALIGN(ItemIdGetLength(lp)); +totallen += itemidptr->alignedlen; +itemidptr++; + } } else { @@ -595,7 +608,7 @@ PageRepairFragmentation(Page page) } } - if (nstorage == 0) + if (itemidptr == itemidbase) { /* Page is completely empty, so just reset it quickly */ ((PageHeader) page)->pd_upper = pd_special; @@ -603,36 +616,13 @@ PageRepairFragmentation(Page page) else { /* Need to compact the page the hard way */ - itemIdSortData itemidbase[MaxHeapTuplesPerPage]; - itemIdSort itemidptr = itemidbase; - - totallen = 0; - for (i = 0; i < nline; i++) - { - lp = PageGetItemId(page, i + 1); - if (ItemIdHasStorage(lp)) - { -itemidptr->offsetindex = i; -itemidptr->itemoff = ItemIdGetOffset(lp); -if (itemidptr->itemoff < (int) pd_upper || - itemidptr->itemoff >= (int) pd_special) - ereport(ERROR, - (errcode(ERRCODE_DATA_CORRUPTED), - errmsg("corrupted item pointer: %u", - itemidptr->itemoff))); -itemidptr->alignedlen = MAXALIGN(ItemIdGetLength(lp)); -totallen += itemidptr->alignedlen; -itemidptr++; - } - } - if (totallen > (Size) (pd_special - pd_lower)) ereport(ERROR, (errcode(ERRCODE_DATA_CORRUPTED), errmsg("corrupted item lengths: total %u, available space %u", (unsigned int) totallen, pd_special - pd_lower))); - compactify_tuples(itemidbase, nstorage, page); + compactify_tuples(itemidbase, (int) (itemidptr - itemidbase), page); } /* Set hint bit for PageAddItem */ -- 2.11.0 From 8f75fcaba0590d5150dd956a60feee5c28f4caab Mon Sep 17 00:00:00 2001 From: Sokolov Yura 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
Re: [HACKERS] Small improvement to compactify_tuples
Please add these two patches to the upcoming commitfest, https://commitfest.postgresql.org/ -- Álvaro Herrerahttps://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Small improvement to compactify_tuples
Sokolov Yura писал 2017-05-15 15:08: 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. In a sequel, I propose to simplify PageRepairFragmentation in attached patch. -- Sokolov Yura aka funny.falcon Postgres Professional: https://postgrespro.ru The Russian Postgres CompanyFrom 2cde4cb6b0c4c5868d99e13789b0ac33364d7315 Mon Sep 17 00:00:00 2001 From: Sokolov YuraDate: Mon, 15 May 2017 16:04:14 +0300 Subject: [PATCH 2/2] bufpage.c: simplify PageRepairFragmentation In assumption that page usually doesn't become empty, merge second loop body (collecting items with storage) into first (counting kinds of items). --- src/backend/storage/page/bufpage.c | 46 +++--- 1 file changed, 18 insertions(+), 28 deletions(-) diff --git a/src/backend/storage/page/bufpage.c b/src/backend/storage/page/bufpage.c index c5630e808b..61738f241f 100644 --- a/src/backend/storage/page/bufpage.c +++ b/src/backend/storage/page/bufpage.c @@ -555,10 +555,11 @@ PageRepairFragmentation(Page page) Offset pd_special = ((PageHeader) page)->pd_special; ItemId lp; int nline, -nstorage, nunused; int i; Size totallen; + itemIdSortData itemidbase[MaxHeapTuplesPerPage]; + itemIdSort itemidptr = itemidbase; /* * It's worth the trouble to be more paranoid here than in most places, @@ -578,14 +579,26 @@ PageRepairFragmentation(Page page) pd_lower, pd_upper, pd_special))); nline = PageGetMaxOffsetNumber(page); - nunused = nstorage = 0; + nunused = totallen = 0; for (i = FirstOffsetNumber; i <= nline; i++) { lp = PageGetItemId(page, i); if (ItemIdIsUsed(lp)) { if (ItemIdHasStorage(lp)) -nstorage++; + { +itemidptr->offsetindex = i - 1; +itemidptr->itemoff = ItemIdGetOffset(lp); +if (unlikely(itemidptr->itemoff < (int) pd_upper || + itemidptr->itemoff >= (int) pd_special)) + ereport(ERROR, + (errcode(ERRCODE_DATA_CORRUPTED), + errmsg("corrupted item pointer: %u", + itemidptr->itemoff))); +itemidptr->alignedlen = MAXALIGN(ItemIdGetLength(lp)); +totallen += itemidptr->alignedlen; +itemidptr++; + } } else { @@ -595,7 +608,7 @@ PageRepairFragmentation(Page page) } } - if (nstorage == 0) + if (itemidptr == itemidbase) { /* Page is completely empty, so just reset it quickly */ ((PageHeader) page)->pd_upper = pd_special; @@ -603,36 +616,13 @@ PageRepairFragmentation(Page page) else { /* Need to compact the page the hard way */ - itemIdSortData itemidbase[MaxHeapTuplesPerPage]; - itemIdSort itemidptr = itemidbase; - - totallen = 0; - for (i = 0; i < nline; i++) - { - lp = PageGetItemId(page, i + 1); - if (ItemIdHasStorage(lp)) - { -itemidptr->offsetindex = i; -itemidptr->itemoff = ItemIdGetOffset(lp); -if (itemidptr->itemoff < (int) pd_upper || - itemidptr->itemoff >= (int) pd_special) -
Re: [HACKERS] Small improvement to compactify_tuples
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 CompanyFrom 8f75fcaba0590d5150dd956a60feee5c28f4caab Mon Sep 17 00:00:00 2001 From: Sokolov YuraDate: 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 =
Re: [HACKERS] Small improvement to compactify_tuples
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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers