From: | Thomas Munro <thomas(dot)munro(at)gmail(dot)com> |
---|---|
To: | Andres Freund <andres(at)anarazel(dot)de> |
Cc: | Daniel Gustafsson <daniel(at)yesql(dot)se>, pgsql-hackers <pgsql-hackers(at)postgresql(dot)org> |
Subject: | Re: A qsort template |
Date: | 2021-03-14 02:35:23 |
Message-ID: | CA+hUKGKztHEWm676csTFjYzortziWmOcf8HDss2Zr0muZ2xfEg@mail.gmail.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers |
On Sat, Mar 13, 2021 at 3:49 PM Thomas Munro <thomas(dot)munro(at)gmail(dot)com> wrote:
> On Fri, Mar 12, 2021 at 7:58 AM Andres Freund <andres(at)anarazel(dot)de> wrote:
> > I wish we had the same for bsearch... :)
>
> Glibc already has the definition of the traditional void-based
> function in /usr/include/bits/stdlib-bsearch.h, so the generated code
> when the compiler can see the comparator definition is already good in
> eg lazy_tid_reaped() and eg some nbtree search routines. We could
> probably expose more trivial comparators in headers to get more of
> that, and we could perhaps put our own bsearch definition in a header
> for other platforms that didn't think of that...
>
> It might be worth doing type-safe macro templates as well, though (as
> I already did in an earlier proposal[1]), just to have nice type safe
> code though, not sure, I'm thinking about that...
I remembered a very good reason to do this: the ability to do
branch-free comparators in more places by introducing optional wider
results. That's good for TIDs (needs 49 bits), and places that want
to "reverse" a traditional comparator (just doing -result on an int
comparator that might theoretically return INT_MIN requires at least
33 bits). So I rebased the relevant parts of my earlier version, and
went through and wrote a bunch of examples to demonstrate all this
stuff actually working.
There are two categories of change in these patches:
0002-0005: Places that sort/unique/search OIDs, BlockNumbers and TIDs,
which can reuse a small set of typed functions (a few more could be
added, if useful). See sortitemptr.h and sortscalar.h. Mostly this
is just a notational improvement, and an excuse to drop a bunch of
duplicated code. In a few places this might really speed something
important up! Like VACUUM's lazy_tid_reaped().
0006-0009. Places where a specialised function is generated for one
special purpose, such as ANALYZE's HeapTuple sort, tidbitmap.c's
pagetable sort, some places in nbtree code etc. These may require
some case-by-case research on whether the extra executable size is
worth the speedup, and there are surely more opportunities like that;
I just picked on these arbitrarily.
Attachment | Content-Type | Size |
---|---|---|
0001-Add-bsearch-and-unique-templates-to-sort_template.h.patch | text/x-patch | 6.6 KB |
0002-Supply-sort-search-specializations-for-common-scalar.patch | text/x-patch | 2.4 KB |
0003-Use-qsort_oid-and-friends-in-obvious-places.patch | text/x-patch | 9.1 KB |
0004-Supply-specialized-sort-search-routines-for-ItemPtrD.patch | text/x-patch | 2.2 KB |
0005-Use-qsort_itemptr-and-friends-in-various-places.patch | text/x-patch | 4.3 KB |
0006-Specialize-the-HeapTuple-sort-routine-for-ANALYZE.patch | text/x-patch | 2.6 KB |
0007-Specialize-pagetable-sort-routines-in-tidbitmap.c.patch | text/x-patch | 4.1 KB |
0008-Specialize-some-sort-search-routines-in-nbtree-code.patch | text/x-patch | 5.6 KB |
0009-Specialize-sort-routine-used-by-multixact.c.patch | text/x-patch | 2.9 KB |
From | Date | Subject | |
---|---|---|---|
Next Message | wangsh.fnst@fujitsu.com | 2021-03-14 02:52:05 | RE: [HACKERS] logical decoding of two-phase transactions |
Previous Message | Tatsuo Ishii | 2021-03-14 00:28:34 | Re: Using COPY FREEZE in pgbench |