Re: [PATCH 04/16] Add embedded list interface (header only)

On 20 June 2012 14:38, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
> It incurs a rather high performance overhead due to added memory allocations
> and added pointer indirections. Thats fine for most of the current users of
> the List interface, but certainly not for all. In other places you cannot even
> have memory allocations because the list lives in shared memory.

Yes, in general lists interact horribly with the memory hierarchy. I
think I pointed out to you once a rant of mine on -hackers a while
back in which I made various points about just how badly they do these
days.

On modern architectures, with many layers of cache, the cost of the
linear search to get an insertion point is very large. So this:

/*
* removes a node from a list
* Attention: O(n)
*/
static inline void ilist_s_remove(ilist_s_head *head,
ilist_s_node *node)

is actually even worse than you might suspect.

> E.g. in the ApplyCache, where I use the submitted ilist.h stuff, when
> reconstructing transactions you add to a potentially really long linked list
> of individual changes for every interesting wal record. Before I prevented
> memory allocations in that path it took about 12-14% of the time when applying
> changes in the same backend. Afterwards it wasn't visible in the profile
> anymore.

I find that very easy to believe.

> Several of the pieces of code I pointed out in a previous email use open-coded
> list implementation exactly to prevent those problems.

Interesting.

So, it seems like this list implementation could be described as a
minimal embeddable list implementation that requires the user to do
all the memory allocation, and offers a doubly-linked list too. Not an
unreasonable idea. I do think that the constraints you have are not
well served by any existing implementation, including List and Dllist.
Are you planning on just overhauling the Dllist interface in your next
iteration?

As to the question of inling, the C99 standard (where inlining is
standardised by ANSI, but inspired by earlier extensions to C), unlike
the C89 standard, seems to be well respected by vendors as far as it
goes, with some compilers going to pains to implement it correctly,
like ICC and Clang. We can't really switch to C99, because MSVC
doesn't support it, and it is patently obvious that Microsoft have
zero interest in it.

Funnily enough, if anyone takes C89 as a standard seriously still,
it's Microsoft, if only due to indifference to later standards. This
hack exists purely for the benefit of their strict interpretation of
C89, I think:

/* Define to `__inline__' or `__inline' if that's what the C compiler
calls it, or to nothing if 'inline' is not supported under any name. */
#ifndef __cplusplus
/* #undef inline */
#endif

If anyone today is using PostgreSQL binaries in production that were
built with a compiler that does not USE_INLINE, I would be very
surprised indeed. The idea that anyone intends to build 9.3 with a
compiler that doesn't support inline functions is very difficult to
believe. Other C open source projects like Linux freely use inline
functions. Now, granted, it was only possible to build the kernel for
a long time using gcc, but inline had nothing to do with the problem
of building the kernel.

My point is that broadly it makes more practical sense to talk about
GNU C as a standard than C89, and GNU C supports inline functions (C99
is a different matter, but that isn't going to happen in the
foreseeable future). Don't believe me? This is from our configure
script:

# Check if it's Intel's compiler, which (usually) pretends to be gcc,
# but has idiosyncrasies of its own. We assume icc will define
# __INTEL_COMPILER regardless of CFLAGS.

All of the less popular compilers we support we support precisely
because they pretend to be GCC, with the sole exception, as always, of
the Microsoft product, in this case MSVC. So my position is that I'm
in broad agreement that we should freely allow the use of inline
without macro hacks, since we generally resists using macro hacks if
that makes code ugly, which USE_INLINE certainly does, and for a
benefit that is indistinguishable from zero, at least to me.

Why are you using the stdlib's <assert.h>? Why have you used the
NDEBUG macro rather than USE_ASSERT_CHECKING? This might make sense if
the header was intended to live in port, but it isn't, right?

Why have you done this:

#ifdef __GNUC__
#define unused_attr __attribute__((unused))
#else
#define unused_attr
#endif

and then gone on to use this unused_attr macro all over the place?
Firstly, that isn't going to suppress the warnings on many platforms
that we support, and we do make an effort to build warning free on at
least 3 compilers these days - GCC, Clang and MSVC. Secondly,
compilers give these warnings because it doesn't make any sense to
have an unused parameter - so why have you used one? At the very
least, if you require this exact interface, use compatibility macros.
I can't imagine why that would be important though. And even if you
did want a standard unused_attr facility, you'd do that in c.h, where
a lot of that stuff lives.

You haven't put a copyright notice or description in this new file,
which is required.

So, I infer that by embeddable you mean that the intended interface of
this is that someone writes a struct that has as its first field a
ilist_d_head or a ilist_s_head, and through the magic of C's
guarantees about how those structures will be laid-out, type punning
can be used to traverse the unknown structure, as opposed to doing
that weird ListCell thing - IIRC, Berkeley sockets uses this kind of
inheritance. This isn't really obvious from the code, and if you
engaged me in conversation and asked what an embeddable list was, I
wouldn't have been able to tell you off the top of my head before
today. The lack of comments generally should be worked on.

I am not sure that I like this inconsistency:

ilist_d_foreach(t, head)
ilist_d_remove(head, t);

In the first call, head is specified and then node. In the second,
node and then head. This could probably stand to be made consistent.

That's all for now...

--
Peter Geoghegan       http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training and Services