public inbox for [email protected]
help / color / mirror / Atom feedFrom: Zhihong Yu <[email protected]>
To: Thomas Munro <[email protected]>
Cc: Andres Freund <[email protected]>
Cc: Daniel Gustafsson <[email protected]>
Cc: pgsql-hackers <[email protected]>
Subject: Re: A qsort template
Date: Sat, 13 Mar 2021 20:06:26 -0800
Message-ID: <CALNJ-vRSvudAbdY-DChFv8C0-dJYD3FamX4FpW9A2xivKuB83A@mail.gmail.com> (raw)
In-Reply-To: <CA+hUKGKztHEWm676csTFjYzortziWmOcf8HDss2Zr0muZ2xfEg@mail.gmail.com>
References: <CA+hUKGJ2-eaDqAum5bxhpMNhvuJmRDZxB_Tow0n-gse+HG0Yig@mail.gmail.com>
<[email protected]>
<CA+hUKGJhOtjQH+wjCodtJzHAFCAPYyt6Qm9E1mUoJph42qo1hg@mail.gmail.com>
<[email protected]>
<CA+hUKGLqmksGRKQRF6qkih6jV_d9qVrrk4wh5F_EgTXyRGeCyw@mail.gmail.com>
<CA+hUKGKztHEWm676csTFjYzortziWmOcf8HDss2Zr0muZ2xfEg@mail.gmail.com>
Hi,
For 0001-Add-bsearch-and-unique-templates-to-sort_template.h.patch :
+ * Remove duplicates from an array. Return the new size.
+ */
+ST_SCOPE size_t
+ST_UNIQUE(ST_ELEMENT_TYPE *array,
The array is supposed to be sorted, right ?
The comment should mention this.
Cheers
On Sat, Mar 13, 2021 at 6:36 PM Thomas Munro <[email protected]> wrote:
> On Sat, Mar 13, 2021 at 3:49 PM Thomas Munro <[email protected]>
> wrote:
> > On Fri, Mar 12, 2021 at 7:58 AM Andres Freund <[email protected]>
> 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.
>
view thread (52+ messages) latest in thread
reply
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: [email protected]
Cc: [email protected], [email protected], [email protected], [email protected]
Subject: Re: A qsort template
In-Reply-To: <CALNJ-vRSvudAbdY-DChFv8C0-dJYD3FamX4FpW9A2xivKuB83A@mail.gmail.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox