Thread: Vectors instead of lists, specialised qsort(), binary_search(), unique()

Hello hackers,

David Rowley posted some interesting stuff about an ArrayList[1] that
would replace List in many places.  (I probably would have replied to
that thread if I hadn't changed email account, sorry.)  I had similar
thoughts when I needed to maintain a sorted vector for my refactoring
proposal for the fsync queue, as part of my undo log work, except I
came at the problem with some ideas from C++ in mind.  However, now
this stuff seems to be redundant for now, given some decisions we've
arrived at in the thread about how to track the fsync queue, and I'm
more focused on getting the undo work done.

I wanted to share what I had anyway, since it seems to be related to
David's proposal but make some different trade-offs.  Perhaps it will
be useful for ideas, code, or examples of what not to do :-)  Or
perhaps I'll come back to it later.

Specialising the comparator and element size of functions like
qsort(), binary_search(), unique() is a well known technique for going
faster, and the resulting programming environment has better type
safety.  It's easy to measure a speedup for specialised qsort of small
objects (compared to pg_qsort() with function pointer and object size
as arguments).  Doing that in a way that works well with automatically
managed vectors (and also any array, including in shmem etc) seemed
like a good plan to me, hence this prototyping work.

The basic idea is to use simplehash-style generic programming, like a
kind of poor man's C++ standard library.  The vector type is
instantiated for a given type like Oid etc, and then you can
instantiate specialised qsort() etc.  The vector has a 'small vector
optimisation' where you can hold very small lists without allocating
any extra memory until you get past (say) 3 members.  I was planning
to extend the qsort implementation a bit further to that it could
replace both pg_qsort() and the Perl-based tuple qsort generator, and
then we'd have only one copy of the algorithm in the tree (the dream
of generic programmers).  I wanted to do the same with unique(), since
I'd already noticed that we have many open coded examples of that
algorithm scattered throughout the tree.

Some of the gratuitous C++isms should be removed including some
nonsense about const qualifiers, use of begin and end rather than data
and size (more common in C code), some some other details, and I was
planning to fix some of that before I reposted the patch set as part
of the larger undo patch set, but now that I'm not going to do that...
here is a snapshot of the patch set as-is, with toy examples showing
several examples of List-of-Oid relationOids being replaced with a
specialised vector (with a missed opportunity for it to be sorted and
use binary_search() instead of find()), and the List-of-Node
p_joinexprs being replaced with a specialised vector.  I think those
last things are the sort of thing that David was targeting.

[1] https://www.postgresql.org/message-id/flat/CAKJS1f_2SnXhPVa6eWjzy2O9A%3Docwgd0Cj-LQeWpGtrWqbUSDA%40mail.gmail.com

-- 
Thomas Munro
https://enterprisedb.com

On Thu, 21 Feb 2019 at 18:02, Thomas Munro <thomas.munro@gmail.com> wrote:
> David Rowley posted some interesting stuff about an ArrayList[1] that
> would replace List in many places.  (I probably would have replied to
> that thread if I hadn't changed email account, sorry.)  I had similar
> thoughts when I needed to maintain a sorted vector for my refactoring
> proposal for the fsync queue, as part of my undo log work, except I
> came at the problem with some ideas from C++ in mind.  However, now
> this stuff seems to be redundant for now, given some decisions we've
> arrived at in the thread about how to track the fsync queue, and I'm
> more focused on getting the undo work done.

Hi Thomas,

Glad to see further work being done in this area. I do agree that our
linked list implementation is very limited and of course, does perform
very poorly for Nth lookups and checking if the list contains
something. Seems what you have here solves (at least) these two
issues.  I also think it's tragic in the many places where we take the
List and turn it into an array because we know list_nth() performs
terribly. (e.g ExecInitRangeTable(), setup_simple_rel_arrays() and
setup_append_rel_array(), it would be great to one day see those
fixed)

As for the ArrayList patch that I'd been working on, I was a bit
blocked on it due to Tom's comment in [1], after having quickly looked
over your patch I see there's no solution for that complaint.

(I'd been trying to think of a solution to this as a sort of idle
background task and so far I'd only come up with a sort of List
indexing system, where we could build additional data structures atop
of the list and have functions like list_nth() check for such an index
and use it if available.   I don't particularly like the idea, but it
was the only way I could think of to work around Tom's complaint.  I
felt there was just too much list API code that relies on the list
being a linked list.  e.g checking for empty lists with list == NIL.
lnext() etc.)

So in short, I'm in favour of not just having braindead linked lists
all over the place to store things. I will rejoice the day we move
away from that, but also Tom's comment kinda stuck with me.  He's
often right too.   Likely backpatching pain that Tom talks about would
be much less if we used C++, but... we don't.

I'm happy to support the cause here, just not quite sure yet how I can
best do that.

[1] https://www.postgresql.org/message-id/21592.1509632225%40sss.pgh.pa.us

-- 
 David Rowley                   http://www.2ndQuadrant.com/
 PostgreSQL Development, 24x7 Support, Training & Services

On Thu, Feb 21, 2019 at 7:27 PM David Rowley
<david.rowley@2ndquadrant.com> wrote:
> As for the ArrayList patch that I'd been working on, I was a bit
> blocked on it due to Tom's comment in [1], after having quickly looked
> over your patch I see there's no solution for that complaint.
>
> (I'd been trying to think of a solution to this as a sort of idle
> background task and so far I'd only come up with a sort of List
> indexing system, where we could build additional data structures atop
> of the list and have functions like list_nth() check for such an index
> and use it if available.   I don't particularly like the idea, but it
> was the only way I could think of to work around Tom's complaint.  I
> felt there was just too much list API code that relies on the list
> being a linked list.  e.g checking for empty lists with list == NIL.
> lnext() etc.)
>
> So in short, I'm in favour of not just having braindead linked lists
> all over the place to store things. I will rejoice the day we move
> away from that, but also Tom's comment kinda stuck with me.  He's
> often right too.   Likely backpatching pain that Tom talks about would
> be much less if we used C++, but... we don't.

Right, in this patch-set I wasn't really focused on how to replace the
existing lists in a back-patch friendly style (a very legitimate
concern), I was focused on how to get the best possible machine code
for basic data structures and algorithms that are used all over the
place, by inlining as many known-at-compile-time parameters as
possible.  And using the right data-structures in the first place by
making them easily available; I guess that's the bit where your ideas
and mine overlapped.  I'm also interested in skipping gratuitous
allocation and pointer chasing, even in cases where eg linked lists
might not be "wrong" according to the access pattern, just because
it's cache-destructive and a waste of cycles.  As Alexander Stepanov
said: "Use vectors whenever you can. If you cannot use vectors,
redesign your solution so that you can use vectors", and I think there
is also something interesting about keeping objects inside in their
containing object, instead of immediately using pointers to somewhere
else (obviously tricky with variable sized data, but that's what the
small vector optimisation idea is about; whether it's worth it after
the overhead of detecting the case, I don't know; std::string
implementors seem to think so).  I was primarily interested in new
code, though I'm pretty sure there are places all over the tree where
microoptimisations are possible through specialisation (think
partitioning, sorting, searching, uniquifying in cases where the types
are fixed, or vary at runtime but there are some common cases you
might want to specialise for).

For the cases you're interested in, maybe piecemeal replication of the
planner lists that are measurably very hot is the only practical way
to do it, along with evidence that it's really worth the future
backpatching pain in each case.  Or maybe there is some way to create
a set of macros that map to List operations in back branches, as you
were hinting at, to keep client code identical...  I dunno.

-- 
Thomas Munro
https://enterprisedb.com