Re: [HACKERS] embedded list
Alvaro Herrera writes: > Oops. I mentioned this explicitely somewhere in the discussion. I > assumed you had seen that, and that you would have complained had you > found it objectionable. Sorry, I've been too busy to pay very much attention to this patch. >> I think we should remove the head argument at least from dlist_delete, >> and probably also dlist_insert_after and dlist_insert_before. > There are more functions that get the list head just to run the check. > Can I assume that you don't propose removing the argument from those? > (dlist_next_node, dlist_prev_node I think are the only ones). Yeah, I wondered whether to do the same for those. But it's less of an issue there, because in practice the caller is almost certainly going to also need to do dlist_has_next or dlist_has_prev respectively, and those require the list header. On the other hand, applying the same principle to slists, you could argue that slist_has_next and slist_next_node should not require the head pointer (since that's throwing away an advantage of slists). If we wanted to remove the head pointer from those, there would be some value in not having the head argument in dlist_next_node/dlist_prev_node for symmetry with slist_next_node. I'm not as excited about these since it seems relatively less likely to matter. What do you think? 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] embedded list
Tom Lane escribió: > Alvaro Herrera writes: > > Here's the final version. I think this is ready to go in. > > I got around to reviewing this today. I'm pretty seriously annoyed at > the definition of dlist_delete: it should *not* require the list header. > The present coding simply throws away one of the primary advantages of > a doubly-linked list over a singly-linked list, namely that you don't > have to have your hands on the list header in order to unlink a node. > This isn't merely academic either, as I see that the patch to catcache > code actually added a field to struct catctup to support making the > list header available. That's a complete waste of 8 bytes (on a 64-bit > machine) per catalog cache entry. The only thing it buys for us is > the ability to run dlist_check, which is something that isn't even > compiled (not even in an Assert build), and which doesn't actually do > that much useful even if it is compiled --- for instance, there's no way > to verify that the nodes were actually in the list claimed. Oops. I mentioned this explicitely somewhere in the discussion. I assumed you had seen that, and that you would have complained had you found it objectionable. (It's hard enough to figure out if people don't respond because they don't have a problem with something, or just because they didn't see it.) On the other hand, it's convenient to remove them, because in predicate.c there are plenty of SHM_QUEUE node removals which is clearly easier to port over to dlist if we don't have to figure out exactly which list each node is in. (Maybe in other SHM_QUEUE users as well, but that's the most complex of the bunch.) > I think we should remove the head argument at least from dlist_delete, > and probably also dlist_insert_after and dlist_insert_before. There are more functions that get the list head just to run the check. Can I assume that you don't propose removing the argument from those? (dlist_next_node, dlist_prev_node I think are the only ones). -- Álvaro Herrerahttp://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, 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] embedded list
Alvaro Herrera writes: > Here's the final version. I think this is ready to go in. I got around to reviewing this today. I'm pretty seriously annoyed at the definition of dlist_delete: it should *not* require the list header. The present coding simply throws away one of the primary advantages of a doubly-linked list over a singly-linked list, namely that you don't have to have your hands on the list header in order to unlink a node. This isn't merely academic either, as I see that the patch to catcache code actually added a field to struct catctup to support making the list header available. That's a complete waste of 8 bytes (on a 64-bit machine) per catalog cache entry. The only thing it buys for us is the ability to run dlist_check, which is something that isn't even compiled (not even in an Assert build), and which doesn't actually do that much useful even if it is compiled --- for instance, there's no way to verify that the nodes were actually in the list claimed. I think we should remove the head argument at least from dlist_delete, and probably also dlist_insert_after and dlist_insert_before. 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] embedded list
Alvaro Herrera escribió: > Here's the final version. I think this is ready to go in. Committed. There are several uses of SHM_QUEUE in the backend code which AFAICS can be replaced with dlist. If someone's looking for an easy project, here's one. -- Álvaro Herrerahttp://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, 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] embedded list
On Thursday, October 11, 2012 06:37:59 PM Andres Freund wrote: > On Thursday, October 11, 2012 03:27:17 PM Andres Freund wrote: > > On Thursday, October 11, 2012 03:23:12 PM Alvaro Herrera wrote: > > > Alvaro Herrera escribió: > > > > I also included two new functions in that patch, dlisti_push_head and > > > > dlisti_push_tail. These functions are identical to dlist_push_head > > > > and dlist_push_tail, except that they do not accept non-circular > > > > lists. What this means is that callers that find the non-circularity > > > > acceptable can use the regular version, and will run dlist_init() on > > > > demand; callers that want the super-tight code can use the other > > > > version. I didn't bother with a new dlist_is_empty. > > > > > > Is there any more input on this? At this point I would recommend > > > committing this patch _without_ these dlisti functions, i.e. we will > > > only have the functions that check for NULL-initialized dlists. We can > > > later discuss whether to include them or not (it would be a much > > > smaller patch and would not affect the existing functionality in any > > > way.) > > > > I can live with that. I didn't have a chance to look at the newest > > revision yet, will do that after I finish my first pass through foreign > > key locks. > > I looked at and I am happy enough ;) > > One thing: > I think you forgot to adjust dlist_reverse_foreach to the NULL list header. Tom, whats your thought about Alvaro's latest version (except the "bug" mentioned above)? It looks like a somewhat fair compromise between our positions and I don't think the external interface needs to change if we decide to resolve any of our differences differently. Greetings, Andres -- Andres Freund http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, 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] embedded list
On Thursday, October 11, 2012 03:27:17 PM Andres Freund wrote: > On Thursday, October 11, 2012 03:23:12 PM Alvaro Herrera wrote: > > Alvaro Herrera escribió: > > > I also included two new functions in that patch, dlisti_push_head and > > > dlisti_push_tail. These functions are identical to dlist_push_head and > > > dlist_push_tail, except that they do not accept non-circular lists. > > > What this means is that callers that find the non-circularity > > > acceptable can use the regular version, and will run dlist_init() on > > > demand; callers that want the super-tight code can use the other > > > version. I didn't bother with a new dlist_is_empty. > > > > Is there any more input on this? At this point I would recommend > > committing this patch _without_ these dlisti functions, i.e. we will > > only have the functions that check for NULL-initialized dlists. We can > > later discuss whether to include them or not (it would be a much smaller > > patch and would not affect the existing functionality in any way.) > > I can live with that. I didn't have a chance to look at the newest revision > yet, will do that after I finish my first pass through foreign key locks. I looked at and I am happy enough ;) One thing: I think you forgot to adjust dlist_reverse_foreach to the NULL list header. Thanks! Andres -- Andres Freund http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, 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] embedded list
On Thursday, October 11, 2012 03:23:12 PM Alvaro Herrera wrote: > Alvaro Herrera escribió: > > I also included two new functions in that patch, dlisti_push_head and > > dlisti_push_tail. These functions are identical to dlist_push_head and > > dlist_push_tail, except that they do not accept non-circular lists. > > What this means is that callers that find the non-circularity acceptable > > can use the regular version, and will run dlist_init() on demand; > > callers that want the super-tight code can use the other version. > > I didn't bother with a new dlist_is_empty. > > Is there any more input on this? At this point I would recommend > committing this patch _without_ these dlisti functions, i.e. we will > only have the functions that check for NULL-initialized dlists. We can > later discuss whether to include them or not (it would be a much smaller > patch and would not affect the existing functionality in any way.) I can live with that. I didn't have a chance to look at the newest revision yet, will do that after I finish my first pass through foreign key locks. Andres -- Andres Freund http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, 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] embedded list
Alvaro Herrera escribió: > I also included two new functions in that patch, dlisti_push_head and > dlisti_push_tail. These functions are identical to dlist_push_head and > dlist_push_tail, except that they do not accept non-circular lists. > What this means is that callers that find the non-circularity acceptable > can use the regular version, and will run dlist_init() on demand; > callers that want the super-tight code can use the other version. > I didn't bother with a new dlist_is_empty. Is there any more input on this? At this point I would recommend committing this patch _without_ these dlisti functions, i.e. we will only have the functions that check for NULL-initialized dlists. We can later discuss whether to include them or not (it would be a much smaller patch and would not affect the existing functionality in any way.) -- Álvaro Herrerahttp://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, 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] embedded list v3
Hi Peter,
On Monday, October 08, 2012 09:43:51 PM Peter Geoghegan wrote:
> Pendantry: This should be in alphabetical order:
>
> ! OBJS = stringinfo.o ilist.o
Argh. Youve said that before. Somehow I reintroduced it...
> I notice that the patch (my revision) produces a whole bunch of
> warnings like this with Clang, though not GCC:
>
>
>
> [peter@peterlaptop cache]$ clang -O2 -g -Wall -Wmissing-prototypes
> -Wpointer-arith -Wdeclaration-after-statement -Wendif-labels
> -Wmissing-format-attribute -Wformat-security -fno-strict-aliasing
> -fwrapv -fexcess-precision=standard -g -I../../../../src/include
> -D_GNU_SOURCE -D_FORTIFY_SOURCE=2 -I/usr/include/libxml2 -c -o
> catcache.o catcache.c -MMD -MP -MF .deps/catcache.Po
> clang: warning: argument unused during compilation:
> '-fexcess-precision=standard'
> catcache.c:457:21: warning: expression result unused [-Wunused-value]
> CatCache *ccp = slist_container(CatCache, cc_next,
> cache_iter.cur);
>
> ^~
> ../../../../src/include/lib/ilist.h:721:3: note: expanded from macro
> 'slist_container'
> (AssertVariableIsOfTypeMacro(ptr, slist_node *),...
> ^
> ../../../../src/include/c.h:735:2: note: expanded from macro
> 'AssertVariableIsOfTypeMacro'
> StaticAssertExpr(__builtin_types_compatible_p(__typeof__(varname),
> typename), \
> ^
> ../../../../src/include/c.h:710:46: note: expanded from macro
> 'StaticAssertExpr' ({ StaticAssertStmt(condition, errmessage); true; })
> ^
> ../../../../src/include/c.h:185:15: note: expanded from macro 'true'
> #define true((bool) 1)
> ^ ~
>
> *** SNIP SNIP SNIP ***
>
> catcache.c:1818:21: warning: expression result unused [-Wunused-value]
> CatCache *ccp = slist_container(CatCache, cc_next,
> iter.cur); ^~~~
> ../../../../src/include/lib/ilist.h:722:3: note: expanded from macro
> 'slist_container'
> AssertVariableIsOfTypeMacro(((type*)NULL)->membername,
> slist_node), \
> ^
> ../../../../src/include/c.h:735:2: note: expanded from macro
> 'AssertVariableIsOfTypeMacro'
> StaticAssertExpr(__builtin_types_compatible_p(__typeof__(varname),
> typename), \
> ^
> ../../../../src/include/c.h:710:46: note: expanded from macro
> 'StaticAssertExpr' ({ StaticAssertStmt(condition, errmessage); true; })
> ^
> ../../../../src/include/c.h:185:15: note: expanded from macro 'true'
> #define true((bool) 1)
> ^ ~
> 28 warnings generated.
>
>
>
> I suppose that this is something that's going to have to be addressed
> sooner or later.
That looks like an annoying warning. Split of StaticAssertExpr into
StaticAssertExpr and StaticAssertExprBool?
> This seems kind of arbitrary:
>
> /* The socket number we are listening for connections on */
> int PostPortNumber;
> +
> /* The directory names for Unix socket(s) */
> char *Unix_socket_directories;
> +
> /* The TCP listen address(es) */
> char *ListenAddresses;
Yep, no idea why I added the spaces.
> This looks funny:
>
> + #endif /* defined(USE_INLINE) ||
> + *
> defined(ILIST_DEFINE_FUNCTIONS) */
>
> I tend to consider the 80-column thing a recommendation more than a
> requirement.
Thats pgindent's doing. I couldn't convince it not to do that short of making
it a multiline comment with 's.
> A further stylistic gripe is that this:
>
> + #define dlist_container(type, membername, ptr)
>
\
> + (AssertVariableIsOfTypeMacro(ptr, dlist_node *),
> \
> + AssertVariableIsOfTypeMacro(((type *) NULL)->membername, dlist_node),
> \ +((type *)((char *)(ptr) - offsetof(type, membername)))
>
\
> + )
>
> Should probably look like this:
>
> + #define dlist_container(type, membername, ptr)
>
\
> + (AssertVariableIsOfTypeMacro(ptr, dlist_node *),
> \
> + AssertVariableIsOfTypeMacro(((type *) NULL)->membername, dlist_node),
> \ +((type *)((char *)(ptr) - offsetof(type, membername
Why? I find the former better readable.
> This is a little unclear:
>
> + * dlist_foreach (iter, &db->tables)
> + * {
> + * // inside an *_foreach the iterator's .cur field can be used to
> access + * // the current element
> This comment:
>
> + * Singly linked lists are *not* circularly linked (how could they be?)
> in + * contrast to the doubly linked lists. As no pointer to the last
> list element
>
> Isn't quite accurate, if I've understood
Re: [HACKERS] embedded list v3
On Monday, October 01, 2012 05:33:01 PM Tom Lane wrote: > Andres Freund writes: > > On Sunday, September 30, 2012 10:33:28 PM Tom Lane wrote: > >> I'm still pretty desperately unhappy with your insistence on circularly > >> linked dlists. Not only does that make initialization problematic, > >> but now it's not even consistent with slists. > > > > We literally have tens of thousands list manipulation a second if the > > server is busy. > > Tens of thousands, with maybe 1ns extra per call, adds up to what? Well, a pipeline stall is a bit more than a ns. > > I am really sorry for being stubborn here, but I changed to circular > > lists after profiling and finding that pipeline stalls & misprediced > > branches where the major thing I could change. Not sure how we can > > resolv this :( > > I'm going to be stubborn too. I think you're allowing very small > micro-optimization arguments to contort the design of a fundamental data > structure, in a way that makes it harder to use. That's not a tradeoff > I like. Your usability problem is the initialization? Iteration? dlist_initialiaized_(push_head|push_tail|is_empty)() + your hybrid approach of checking for NULL at the plain functions? > Especially when the micro-optimization isn't even uniformly a > win. I remain of the opinion that the extra cycles spent on iteration > (which are real despite your denials) will outweigh any savings in list > alteration in many use-cases. I am not denying that one more register used which possibly leading to one more register spill can be an efficiency difference. Just that it is not as big as the differences are for modification. Greetings, Andres -- Andres Freund http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, 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] embedded list v3
Andres Freund writes: > On Sunday, September 30, 2012 10:33:28 PM Tom Lane wrote: >> I'm still pretty desperately unhappy with your insistence on circularly >> linked dlists. Not only does that make initialization problematic, >> but now it's not even consistent with slists. > We literally have tens of thousands list manipulation a second if the server > is > busy. Tens of thousands, with maybe 1ns extra per call, adds up to what? > I am really sorry for being stubborn here, but I changed to circular lists > after profiling and finding that pipeline stalls & misprediced branches where > the major thing I could change. Not sure how we can resolv this :( I'm going to be stubborn too. I think you're allowing very small micro-optimization arguments to contort the design of a fundamental data structure, in a way that makes it harder to use. That's not a tradeoff I like. Especially when the micro-optimization isn't even uniformly a win. I remain of the opinion that the extra cycles spent on iteration (which are real despite your denials) will outweigh any savings in list alteration in many use-cases. 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] embedded list v3
On 9/30/12 5:42 PM, Andres Freund wrote: > I thought msvc supported _Static_assert as well, but after a short search it > seems I misremembered and it only supports static_assert from C++11 (which is > plausible, because I've worked on a C++11 project which was ported to windows > ). I don't know how C and C++ compilation modes are different in msvc. The issue is rather that the MSVC guys have decided not to bother supporting C99. -- 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] embedded list v3
On Sunday, September 30, 2012 10:48:01 PM Tom Lane wrote: > Andres Freund writes: > > Perhaps we need to decouple _Static_assert support from compound > > statement support at some point, but we will see. > > Yeah, possibly, but until we have an example of a non-gcc-compatible > compiler that can do something equivalent, it's hard to guess how we > might need to alter the autoconf tests. Anyway the important thing > for now is the external specification of the macros, and I think we're > good on that (modulo any better naming suggestions). I thought msvc supported _Static_assert as well, but after a short search it seems I misremembered and it only supports static_assert from C++11 (which is plausible, because I've worked on a C++11 project which was ported to windows ). I don't know how C and C++ compilation modes are different in msvc. I really don't understand why C and C++ standard development isn't coordinated more... They seem to come up with annoying incompatibilities all the time. > I'm fairly sure there are already a few cases of Asserts on > compile-time-constant expressions, so I made sure that there was a layer > allowing access to _Static_assert without the type-compatibility code. > I didn't go looking for anything to convert, but I think there's some > in the shared memory initialization code. Definitely a sensible goal. I wasn't really sure how well the idea would be received after I asked before and only heard echoes of my excitement and didn't want to spend too much time on it... Greetings, Andres -- Andres Freund http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, 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] embedded list v3
Hi, On Sunday, September 30, 2012 10:33:28 PM Tom Lane wrote: > Andres Freund writes: > > Current version is available at branch ilist in: > > git://git.postgresql.org/git/users/andresfreund/postgres.git > > ssh://g...@git.postgresql.org/users/andresfreund/postgres.git > > I'm still pretty desperately unhappy with your insistence on circularly > linked dlists. Not only does that make initialization problematic, > but now it's not even consistent with slists. The slist code originally grew out of the dlist code and thus was pretty similar, but at some point (after your dislike of the circular lists?, not sure) I thought about it again and found no efficiency differences for any of the common manipulations in single linked lists because you don't need to deal with prev and tail pointers, so I saw no point in insisting there. No external user should care. > A possible compromise that would fix the initialization issue is to > allow an empty dlist to be represented as *either* two NULL pointers > or a pair of self-pointers. Conversion from one case to the other > could happen like this: > It appears to me that of the inline'able functions, only dlist_push_head > and dlist_push_tail would need to do this; the others presume nonempty > lists and so wouldn't have to deal with the NULL/NULL case. > dlist_is_empty would need one extra test too. The problem is that dlist_push_head/tail and and dlist_is_empty are prety hot code paths. In transaction reassembly/wal decoding for every wal record that we need to look at in the context of a transaction the code very roughly does something like: /* get change */ Change *change; if (dlist_is_empty(&apply_cache->cached_changes)) change = dlist_container(..., dlist_pop_head_node(&apply_cache- >cached_changes)) else change = malloc(...); /* get data from wal */ fill_change_change(current_wal_record, change); /* remember change, till TX is complete */ dlist_push_tail(tx->changes, change->node); (In reality more of those happen, but anyway) We literally have tens of thousands list manipulation a second if the server is busy. Iteration only happens once a XLOG_COMMIT/ABORT is found (in combination with merging the subtransaction's changes). In the slab allocator I originally built this for it was exactly the same. The lists are manipulated for every palloc/pfree but only iterated at MemoryContextReset. I am really sorry for being stubborn here, but I changed to circular lists after profiling and finding that pipeline stalls & misprediced branches where the major thing I could change. Not sure how we can resolv this :( > BTW, the "fast path" in dlist_move_head can't be right can it? Yea, its crap, thanks for noticing. Shouldn't cause any issues except being slower, thats why I probably didn't notice I broke it at some point. ->next is missing. Greetings, Andres -- Andres Freund http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, 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] embedded list v3
Andres Freund writes: > Perhaps we need to decouple _Static_assert support from compound statement > support at some point, but we will see. Yeah, possibly, but until we have an example of a non-gcc-compatible compiler that can do something equivalent, it's hard to guess how we might need to alter the autoconf tests. Anyway the important thing for now is the external specification of the macros, and I think we're good on that (modulo any better naming suggestions). I'm fairly sure there are already a few cases of Asserts on compile-time-constant expressions, so I made sure that there was a layer allowing access to _Static_assert without the type-compatibility code. I didn't go looking for anything to convert, but I think there's some in the shared memory initialization code. 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] embedded list v3
On Sunday, September 30, 2012 06:57:32 PM Tom Lane wrote: > Andres Freund writes: > > Patch 0001 contains a assert_compatible_types(a, b) and a > > assert_compatible_types_bool(a, b) macro which I found very useful to > > make it harder to misuse the api. I think its generally useful and > > possibly should be used in more places. > > This seems like basically a good idea, but the macro names are very > unfortunately chosen: they don't comport with our other names for > assertion macros, and they imply that the test is symmetric which it > isn't. It's also unclear what the point of the _bool version is > (namely, to be used in expression contexts in macros). > > I suggest instead > > AssertVariableIsOfType(varname, typename) > > AssertVariableIsOfTypeMacro(varname, typename) > > Or possibly we should leave off the "Assert" prefix, since this will be > a compile-time-constant check and thus not really all that much like > the existing run-time Assert mechanism. Or write "Check" instead of > "Assert", or some other verb. > > Anybody got another color for this bikeshed? No, happy with the new name. Thanks for committing! Wondered for a minute what the point of autoconfiscation is/was but I see that e.g. clang already works... Nice. The bizarre syntactic placement requirements directly come from the standard btw. No idea why they thought that would be a good idea... (check 6.7.1, 6.7.2.1, 6.7.10). Perhaps we need to decouple _Static_assert support from compound statement support at some point, but we will see. Greetings, Andres -- Andres Freund http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, 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] embedded list v3
Andres Freund writes:
> Current version is available at branch ilist in:
> git://git.postgresql.org/git/users/andresfreund/postgres.git
> ssh://g...@git.postgresql.org/users/andresfreund/postgres.git
I'm still pretty desperately unhappy with your insistence on circularly
linked dlists. Not only does that make initialization problematic,
but now it's not even consistent with slists.
A possible compromise that would fix the initialization issue is to
allow an empty dlist to be represented as *either* two NULL pointers
or a pair of self-pointers. Conversion from one case to the other
could happen like this:
INLINE_IF_POSSIBLE void
dlist_push_head(dlist_head *head, dlist_node *node)
{
+ if (head->head.next == NULL)
+ dlist_init(head);
+
node->next = head->head.next;
node->prev = &head->head;
node->next->prev = node;
head->head.next = node;
dlist_check(head);
}
It appears to me that of the inline'able functions, only dlist_push_head
and dlist_push_tail would need to do this; the others presume nonempty
lists and so wouldn't have to deal with the NULL/NULL case.
dlist_is_empty would need one extra test too. dlist_foreach could be
something like
#define dlist_foreach(iter, ptr)
for (AssertVariableIsOfTypeMacro(iter, dlist_iter),
AssertVariableIsOfTypeMacro(ptr, dlist_head *),
iter.end = &(ptr)->head,
iter.cur = iter.end->next ? iter.end->next : iter.end;
iter.cur != iter.end;
iter.cur = iter.cur->next)
I remain unimpressed with the micro-efficiency of this looping code,
but since you're set on pessimizing list iteration to speed up list
alteration, maybe it's the best we can do.
BTW, the "fast path" in dlist_move_head can't be right can it?
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] embedded list v3
Andres Freund writes: > Patch 0001 contains a assert_compatible_types(a, b) and a > assert_compatible_types_bool(a, b) macro which I found very useful to make it > harder to misuse the api. I think its generally useful and possibly should be > used in more places. This seems like basically a good idea, but the macro names are very unfortunately chosen: they don't comport with our other names for assertion macros, and they imply that the test is symmetric which it isn't. It's also unclear what the point of the _bool version is (namely, to be used in expression contexts in macros). I suggest instead AssertVariableIsOfType(varname, typename) AssertVariableIsOfTypeMacro(varname, typename) Or possibly we should leave off the "Assert" prefix, since this will be a compile-time-constant check and thus not really all that much like the existing run-time Assert mechanism. Or write "Check" instead of "Assert", or some other verb. Anybody got another color for this bikeshed? 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] embedded list v3
> Add [ds]list's which can be used to embed lists in bigger data structures > without additional memory management > Alvaro, Andres, Review by Peter G. and Tom This is missing Robert. Sorry for that. Andres -- Andres Freund http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, 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] embedded list v2
On Saturday, September 29, 2012 01:54:37 AM Tom Lane wrote: > Andres Freund writes: > > On Saturday, September 29, 2012 01:39:03 AM Tom Lane wrote: > >> Right offhand it doesn't seem like it really gains that much even for > >> that use-case. You'd end up editing the include file either way, just > >> slightly differently. > > > > Well, with USE_INLINE you have to recompile the whole backend because you > > otherwise easily end up with strange incompatibilities between files. > > Eh? You would anyway, or at least recompile every .o file depending on > that header, if what you want is to inline or de-inline the functions. > There's no magic shortcut for that. Well, --enable-depend copes with changing that in the header fine. As long as its only used in a low number of files thats shorter than a full rebuild ;) Anyway, changed. Andres -- Andres Freund http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, 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] embedded list v2
Andres Freund writes: > On Saturday, September 29, 2012 01:39:03 AM Tom Lane wrote: >> Right offhand it doesn't seem like it really gains that much even for >> that use-case. You'd end up editing the include file either way, just >> slightly differently. > Well, with USE_INLINE you have to recompile the whole backend because you > otherwise easily end up with strange incompatibilities between files. Eh? You would anyway, or at least recompile every .o file depending on that header, if what you want is to inline or de-inline the functions. There's no magic shortcut for that. 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] embedded list v2
On Saturday, September 29, 2012 01:39:03 AM Tom Lane wrote: > Andres Freund writes: > > The reason I had the header declare DEFINE_ILIST_FUNCTIONS (or rather > > ILIST_USE_DEFINITION back then) instead of reusing USE_INLINE directly is > > that it makes it easier to locally change a "module" to not inlining > > which makes testing the !USE_INLINE case easier. Does anybody think this > > is worth something? I have no strong feelings but found it convenient. > > Right offhand it doesn't seem like it really gains that much even for > that use-case. You'd end up editing the include file either way, just > slightly differently. Well, with USE_INLINE you have to recompile the whole backend because you otherwise easily end up with strange incompatibilities between files. Andres -- Andres Freund http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, 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] embedded list v2
Andres Freund writes: > The reason I had the header declare DEFINE_ILIST_FUNCTIONS (or rather > ILIST_USE_DEFINITION back then) instead of reusing USE_INLINE directly is > that > it makes it easier to locally change a "module" to not inlining which makes > testing the !USE_INLINE case easier. Does anybody think this is worth > something? I have no strong feelings but found it convenient. Right offhand it doesn't seem like it really gains that much even for that use-case. You'd end up editing the include file either way, just slightly differently. 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] embedded list v2
On Friday, September 14, 2012 10:57:54 PM Tom Lane wrote: > Alvaro Herrera writes: > > One thing I would like more input in, is whether people think it's > > worthwhile to split dlists and slists into separate files. Thus far > > this has been mentioned by three people independently. > > They're small enough and similar enough that one header and one .c file > seem like plenty; but I don't really have a strong opinion about it. > > > Another question is whether ilist_container() should actually be a more > > general macro "containerof" defined in c.h. (ISTM it would be necessary > > to have this macro if we want to split into two files; that way we don't > > need to have two macros dlist_container and slist_container with > > identical definition, or alternatively a third file that defines just > > ilist_container) > > I'd vote for not having that at all, but rather two separate macros > dlist_container and slist_container. If we had a bunch of operations > that could work interchangeably on dlists and slists, it might be worth > having a concept of "ilist" --- but if we only have this, it would be > better to remove the concept from the API altogether. > > > Third question is about the INLINE_IF_POSSIBLE business as commented by > > Peter. It seems to me that the simple technique used here to avoid > > having two copies of the source could be used by memcxt.c, list.c, > > sortsupport.c as well (maybe clean up fastgetattr too). > > Yeah, looks reasonable ... material for a different patch of course. > But that would mean INLINE_IF_POSSIBLE should be defined someplace else, > perhaps c.h. Also, I'm not that thrilled with having the header file > define ILIST_USE_DEFINITION. I suggest that it might be better to do > > #if defined(USE_INLINE) || defined(DEFINE_ILIST_FUNCTIONS) > ... function decls here ... > #else > ... extern decls here ... > #endif > > where ilist.c defines DEFINE_ILIST_FUNCTIONS before including the > header. I am preparing a new version of this right now. So, some last ditch questions are coming up... The reason I had the header declare DEFINE_ILIST_FUNCTIONS (or rather ILIST_USE_DEFINITION back then) instead of reusing USE_INLINE directly is that it makes it easier to locally change a "module" to not inlining which makes testing the !USE_INLINE case easier. Does anybody think this is worth something? I have no strong feelings but found it convenient. Greetings, Andres -- Andres Freund http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, 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] embedded list v2
Hi,
On Sunday, September 16, 2012 04:23:14 PM Andres Freund wrote:
> What do you think about something like:
>
> typedef struct dlist_iter
> {
> /*
>* Use a union with equivalent storage as dlist_node to make it possible
> to * initialize the struct inside a macro without multiple evaluation. */
> union {
> struct {
> dlist_node *cur;
> dlist_node *end;
> };
> dlist_node init;
> };
> } dlist_iter;
>
> typedef struct dlist_mutable_iter
> {
> union {
> struct {
> dlist_node *cur;
> dlist_node *end;
> };
> dlist_node init;
> };
> dlist_node *next;
> } dlist_mutable_iter;
>
> #define dlist_iter_foreach(iter, ptr)
> \
> for (iter.init = (ptr)->head; iter.cur != iter.end;
> \
>iter.cur = iter.cur->next)
>
> #define dlist_iter_foreach_modify(iter, ptr)
>
\
> for (iter.init = (ptr)->head, iter.next = iter.cur->next;
> \
>iter.cur != iter.end
> \
>iter.cur = iter.next, iter.next = iter.cur->next)
>
> With that and some trivial changes *all* multiple evaluation possibilities
> are gone.
>
> (_iter_ in there would go, thats just so I can have both in the same file
> for now).
I am thinking whether a macro like:
#if __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 6)
#define assert_compatible_types(a, b) _Static_assert(\
__builtin_types_compatible_p(a, __typeof__ (b) ), \
"variable `" #b "` is not compatible to type `" #a "`" )
#else
#define assert_compatible_types(a, b) (void)0
#endif
used like:
#define dlist_iter_foreach(iter, ptr)
\
assert_compatible_types(dlist_iter, iter);
\
for (iter.init = (ptr)->head; iter.cur != iter.end;
\
iter.cur = iter.cur->next)
would be useful.
If you use the wrong type you get an error like:
error: static assertion failed: "variable `iter` is not compatible to type
`dlist_iter`"
Do people think this is something worthwile for some of the macros in pg? At
times the compiler errors that get generated in larger macros can be a bit
confusing and something like that would make it easier to see the originating
error.
I found __builtin_types_compatible while perusing the gcc docs to find whether
there is something like __builtin_constant_p for checking the pureness of an
expression ;)
Andres
--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, 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] embedded list v2
On Saturday, September 15, 2012 07:21:44 PM Tom Lane wrote:
> Andres Freund writes:
> > On Saturday, September 15, 2012 07:32:45 AM Tom Lane wrote:
> >> Well, actually, that just brings us to the main point which is: I do not
> >> believe that circular links are a good design choice here.
> >
> > I think I have talked about the reasoning on the list before, but here it
> > goes: The cases where I primarily used them are cases where the list
> > *manipulation* is a considerable part of the expense. In those situations
> > having less branches is beneficial and, to my knowledge, cannot be done
> > in normal flat lists.
> > For the initial user of those lists - the slab allocator for postgres
> > which I intend to finish at some point - the move to circular lists
> > instead of classical lists was an improvement in the 12-15% range.
>
> Let me make my position clear: I will not accept performance as the sole
> figure of merit for this datatype. It also has to be easy and reliable
> to use, and the current design is a failure on those dimensions.
> This question of ease and reliability of use isn't just academic, since
> you guys had trouble converting catcache.c without introducing bugs.
> That isn't exactly a positive showing for this design.
Uhm. I had introduced a bug there, true (Maybe Alvaro as well, I can't remember
anything right now). But it was something like getting the tail instead of the
head element due to copy paste. Nothing will be able to protect the code from
me.
> Furthermore, one datapoint for one use-case (probably measured on only
> one CPU architecture) isn't even a very convincing case for the
> performance being better. To take a handy example, if we were to
> convert dynahash to use dlists, having to initialize each hash bucket
> header this way would probably be a pretty substantial cost for a lot
> of hashtable use-cases. We have a lot of short-lived dynahash tables.
What do you think about doing something like:
#define DLIST_INIT(name) {{&name.head, &name.head}}
static dlist_head DatabaseList = DLIST_INIT(DatabaseList);
That works, but obviously the initialization will have to be performed at some
point.
> This also ties into the other problem, since it's hard to code such
> loop control as a macro without multiple evaluation of the list-head
> argument. To me that's a show stopper of the first order. I'm not
> going to accept a replacement for foreach() that introduces bug hazards
> that aren't in foreach().
What do you think about something like:
typedef struct dlist_iter
{
/*
* Use a union with equivalent storage as dlist_node to make it
possible to
* initialize the struct inside a macro without multiple evaluation.
*/
union {
struct {
dlist_node *cur;
dlist_node *end;
};
dlist_node init;
};
} dlist_iter;
typedef struct dlist_mutable_iter
{
union {
struct {
dlist_node *cur;
dlist_node *end;
};
dlist_node init;
};
dlist_node *next;
} dlist_mutable_iter;
#define dlist_iter_foreach(iter, ptr)
\
for (iter.init = (ptr)->head; iter.cur != iter.end;
\
iter.cur = iter.cur->next)
#define dlist_iter_foreach_modify(iter, ptr)
\
for (iter.init = (ptr)->head, iter.next = iter.cur->next;
\
iter.cur != iter.end
\
iter.cur = iter.next, iter.next = iter.cur->next)
With that and some trivial changes *all* multiple evaluation possibilities are
gone.
(_iter_ in there would go, thats just so I can have both in the same file for
now).
> There are certainly some multiple-evaluation macros, but I don't think
> they are associated with core data types. You will not find any in
> pg_list.h for instance. I think it's important that these new forms
> of list be as easy and reliable to use as List is. I'm willing to trade
> off some micro-performance to have that.
Just from what I had in open emacs frames without switching buffers when I read
that email:
Min/Max in c.h and about half of the macros in htup.h (I had the 9.1 tree open
at that point)...
Greetings,
Andres
--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, 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] embedded list v2
Andres Freund writes: > On Saturday, September 15, 2012 07:32:45 AM Tom Lane wrote: >> Well, actually, that just brings us to the main point which is: I do not >> believe that circular links are a good design choice here. > I think I have talked about the reasoning on the list before, but here it > goes: The cases where I primarily used them are cases where the list > *manipulation* is a considerable part of the expense. In those situations > having less branches is beneficial and, to my knowledge, cannot be done in > normal flat lists. > For the initial user of those lists - the slab allocator for postgres which I > intend to finish at some point - the move to circular lists instead of > classical lists was an improvement in the 12-15% range. Let me make my position clear: I will not accept performance as the sole figure of merit for this datatype. It also has to be easy and reliable to use, and the current design is a failure on those dimensions. This question of ease and reliability of use isn't just academic, since you guys had trouble converting catcache.c without introducing bugs. That isn't exactly a positive showing for this design. Furthermore, one datapoint for one use-case (probably measured on only one CPU architecture) isn't even a very convincing case for the performance being better. To take a handy example, if we were to convert dynahash to use dlists, having to initialize each hash bucket header this way would probably be a pretty substantial cost for a lot of hashtable use-cases. We have a lot of short-lived dynahash tables. > Inhowfar do they make iteration more expensive? ptr != head shouldn't be more > expensive than !ptr. That's probably true *as long as the head pointer is available in a register*. But having to reserve a second register for the loop mechanics can be a serious loss on register-poor architectures. This also ties into the other problem, since it's hard to code such loop control as a macro without multiple evaluation of the list-head argument. To me that's a show stopper of the first order. I'm not going to accept a replacement for foreach() that introduces bug hazards that aren't in foreach(). >> I don't really care. If you can't build it without multiple-evaluation >> macros, it's too dangerous for a fundamental construct that's meant to >> be used all over the place. Time to redesign. > Its not like pg doesn't use any other popularly used macros that have > multiple > evaluation hazarards. There are certainly some multiple-evaluation macros, but I don't think they are associated with core data types. You will not find any in pg_list.h for instance. I think it's important that these new forms of list be as easy and reliable to use as List is. I'm willing to trade off some micro-performance to have that. 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] embedded list v2
Hi Tom,
On Saturday, September 15, 2012 07:32:45 AM Tom Lane wrote:
> Andres Freund writes:
> > On Friday, September 14, 2012 10:48:35 PM Tom Lane wrote:
> >> Instead let's provide a macro for an empty list value, so that you can
> >> do something like
> >> static ilist_d_head DatabaseList = EMPTY_DLIST;
> >
> > I don't think that can work with dlists because they are circular and
> > need their pointers to be adjusted.
>
> Well, actually, that just brings us to the main point which is: I do not
> believe that circular links are a good design choice here. They prevent
> the possibility of trivial list initialization, they make plain
> iteration over the list more expensive, and you have provided no
> evidence that there's any meaningful savings in other operations, much
> less enough to justify those disadvantages.
I think I have talked about the reasoning on the list before, but here it
goes: The cases where I primarily used them are cases where the list
*manipulation* is a considerable part of the expense. In those situations
having less branches is beneficial and, to my knowledge, cannot be done in
normal flat lists.
For the initial user of those lists - the slab allocator for postgres which I
intend to finish at some point - the move to circular lists instead of
classical lists was an improvement in the 12-15% range.
Inhowfar do they make iteration more expensive? ptr != head shouldn't be more
expensive than !ptr.
Imo, that leaves initialization where I admit that you have a case. I don't
find it a big problem in practise though.
> >> The apparently random decisions to make some things inline functions
> >> and other things macros (even though they evaluate their args multiple
> >> times) will come back to bite us. I am much more interested in
> >> unsurprising behavior of these constructs than I am in squeezing out
> >> an instruction or two, so I'm very much against the unsafe macros.
> >
> > At the moment the only thing that are macros are things that cannot be
> > expressed as inline functions because they return the actual contained
> > type and/or because they contain a for() loop.
>
> I don't really care. If you can't build it without multiple-evaluation
> macros, it's too dangerous for a fundamental construct that's meant to
> be used all over the place. Time to redesign.
Its not like pg doesn't use any other popularly used macros that have multiple
evaluation hazarards. Even in cases where they *could* be replaced by inline
functions without that danger.
> One possible option, though it's a bit restrictive, is to insist that
> the list node be the first element of whatever it's embedded in,
> eliminating the need for ilist_container altogether. This would not
> work if we meant to put these kinds of list links into Node-derived
> structs, but I suspect we don't need that.
I already had list elements which are in multiple lists at the same time and I
think replacing some of the pg_list.h usages might be a good idea even for
Node derived structures given the List manipulation overhead we have seen in
several profiles.
> Then for instance (given the additional choice to not use circular links)
> dlist_get_head would degenerate to ((type *) (ptr)->head.next), which
> eliminates its multi-evaluation hazard and saves a few instructions as well.
I still fail to see why not using cirular lists removes instructions in such a
situation:
Get the first element in a circular list:
(ptr)->head.next
->head.next is at a constant offset from the start of *ptr, just as a ->first
pointer is.
In iterations like:
for(name = (ptr)->head.next;
name != &(ptr)->head;
name = name->next)
{
}
you have one potentially additional indexed memory access (&ptr->head) for the
whole loop to an address which will normally lie on the same cacheline as the
already accessed ->next pointer.
> Or if you don't want to do that, dlist_get_head(type, membername, ptr)
> could be defined as
> ((type *) dlist_do_get_head(ptr, offsetof(type, membername)))
> where dlist_do_get_head is an inline'able function, eliminating the
> multi-evaluation-of-ptr hazard.
Thats a rather neat idea. Let me play with it for a second, it might make some
of the macros safe, although I don't see how it could work for for() loops.
Just to make that clear, purely accessing the first node can be done without
any macros at al, its just the combination of returning the first node and
getting the contained element that needs to be a macro because of the variadic
type issues (at times, I really wish for c++ style templates...)
I will take a stab at trying to improve Alvaro's current patch wrt to those
issues.
Greetings,
Andres
--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-
Re: [HACKERS] embedded list v2
Andres Freund writes: > On Friday, September 14, 2012 10:48:35 PM Tom Lane wrote: >> Instead let's provide a macro for an empty list value, so that you can >> do something like >> static ilist_d_head DatabaseList = EMPTY_DLIST; > I don't think that can work with dlists because they are circular and need > their pointers to be adjusted. Well, actually, that just brings us to the main point which is: I do not believe that circular links are a good design choice here. They prevent the possibility of trivial list initialization, they make plain iteration over the list more expensive, and you have provided no evidence that there's any meaningful savings in other operations, much less enough to justify those disadvantages. >> The apparently random decisions to make some things inline functions >> and other things macros (even though they evaluate their args multiple >> times) will come back to bite us. I am much more interested in >> unsurprising behavior of these constructs than I am in squeezing out >> an instruction or two, so I'm very much against the unsafe macros. > At the moment the only thing that are macros are things that cannot be > expressed as inline functions because they return the actual contained type > and/or because they contain a for() loop. I don't really care. If you can't build it without multiple-evaluation macros, it's too dangerous for a fundamental construct that's meant to be used all over the place. Time to redesign. One possible option, though it's a bit restrictive, is to insist that the list node be the first element of whatever it's embedded in, eliminating the need for ilist_container altogether. This would not work if we meant to put these kinds of list links into Node-derived structs, but I suspect we don't need that. Then for instance (given the additional choice to not use circular links) dlist_get_head would degenerate to ((type *) (ptr)->head.next), which eliminates its multi-evaluation hazard and saves a few instructions as well. Or if you don't want to do that, dlist_get_head(type, membername, ptr) could be defined as ((type *) dlist_do_get_head(ptr, offsetof(type, membername))) where dlist_do_get_head is an inline'able function, eliminating the multi-evaluation-of-ptr hazard. 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] embedded list v2
Hi,
On Friday, September 14, 2012 10:48:35 PM Tom Lane wrote:
> Alvaro Herrera writes:
> > Here's an updated version of both patches, as well as a third patch that
> > converts the cc_node list link in catcache.c into an slist.
>
> There's a lot of stuff here that seems rather unfortunate and/or sloppy.
Most of that unfortunately my fault not Alvaro's...
> The documentation (such as it is) claims that the lists are circularly
> linked, which doesn't seem to be the case from the code; slist_foreach
> for instance certainly won't work if that's true. (As far as the
> docs go, I'd get rid of the README file and put the how-to-use-it
> comments into the header file, where they have some chance of being
> (a) seen and (b) maintained. But first they need to be rewritten.)
True, only dlist's are circular. The docs were in the header at first, then
somebody voted for moving them ;)
> The distinction between head and node structs seems rather useless,
> and it's certainly notationally tedious. Do we need it?
I think its useful. It makes the usage in structs its embedded to way much
clearer. The head struct actually has a different meaning than normal node
structs because its there even if the list is empty...
> I find the need for this change quite unfortunate:
>
> @@ -256,7 +258,7 @@ typedef struct
> static AutoVacuumShmemStruct *AutoVacuumShmem;
>
> /* the database list in the launcher, and the context that contains it */
> -static Dllist *DatabaseList = NULL;
> +static ilist_d_head DatabaseList;
> static MemoryContext DatabaseListCxt = NULL;
>
> /* Pointer to my own WorkerInfo, valid on each worker */
> @@ -403,6 +405,9 @@ AutoVacLauncherMain(int argc, char *argv[])
> /* Identify myself via ps */
> init_ps_display("autovacuum launcher process", "", "", "");
>
> + /* initialize to be empty */
> + ilist_d_init(&DatabaseList);
> +
> ereport(LOG,
> (errmsg("autovacuum launcher started")));
>
> Instead let's provide a macro for an empty list value, so that you can
> do something like
>
> static ilist_d_head DatabaseList = EMPTY_DLIST;
I don't think that can work with dlists because they are circular and need
their pointers to be adjusted. From my POV it seems to be better to keep those
in sync.
> and not require a new assumption that there will be a convenient place
> to initialize static list variables. In general I think it'd be a lot
> better if the lists were defined such that all-zeroes is a valid empty
> list header, anyway.
For the dlists thats a major efficiency difference in some use cases.
Unfortunately those are the ones I care about... Due to not needing to check
for NULLs several branches can be removed from the whole thing.
> The apparently random decisions to make some things inline functions
> and other things macros (even though they evaluate their args multiple
> times) will come back to bite us. I am much more interested in
> unsurprising behavior of these constructs than I am in squeezing out
> an instruction or two, so I'm very much against the unsafe macros.
At the moment the only thing that are macros are things that cannot be
expressed as inline functions because they return the actual contained type
and/or because they contain a for() loop. Do you have a trick in mind to
handle such cases?
Earlier on when talking with Alvaro I mentioned that I would like to add some
more functions that return the [sd]list_node's instead of the contained
elements. Those should be inline functions.
> I think we could do without such useless distinctions as slist_get_head
> vs slist_get_head_unchecked, too. We've already got Assert and
> ILIST_DEBUG, we do not need even more layers of check-or-not
> distinctions.
The _unchecked variants remove the check whether the list is already empty and
thus give up some safety for speed. Quite often that check is made before
calling dlist_get_head() or such anyway...
I wondered whether the solution for that would be to remove the variants that
check for an empty list (except an Assert).
> Not a full review, just some things that struck me in a quick scan...
Thanks!
Andres
--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, 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] embedded list v2
Excerpts from Tom Lane's message of vie sep 14 17:48:35 -0300 2012: > Alvaro Herrera writes: > > Here's an updated version of both patches, as well as a third patch that > > converts the cc_node list link in catcache.c into an slist. > > There's a lot of stuff here that seems rather unfortunate and/or sloppy. > > Does it even compile? The 0002 patch refers to a typedef ilist_d_head > that I don't see defined anywhere. (It would be good to shorten that > name by a couple of characters anyway, for tab-stop alignment reasons.) Hm, I might have submitted the wrong 0002 file. Sorry about that. (The correct file would have the right typedef names and a couple of bugfixes but it'd be pretty similar to what you read.) > [many useful comments] > > Not a full review, just some things that struck me in a quick scan... Great stuff nonetheless, many thanks. I will see about submitting an improved version. -- Álvaro Herrerahttp://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, 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] embedded list v2
Alvaro Herrera writes: > One thing I would like more input in, is whether people think it's > worthwhile to split dlists and slists into separate files. Thus far > this has been mentioned by three people independently. They're small enough and similar enough that one header and one .c file seem like plenty; but I don't really have a strong opinion about it. > Another question is whether ilist_container() should actually be a more > general macro "containerof" defined in c.h. (ISTM it would be necessary > to have this macro if we want to split into two files; that way we don't > need to have two macros dlist_container and slist_container with > identical definition, or alternatively a third file that defines just > ilist_container) I'd vote for not having that at all, but rather two separate macros dlist_container and slist_container. If we had a bunch of operations that could work interchangeably on dlists and slists, it might be worth having a concept of "ilist" --- but if we only have this, it would be better to remove the concept from the API altogether. > Third question is about the INLINE_IF_POSSIBLE business as commented by > Peter. It seems to me that the simple technique used here to avoid > having two copies of the source could be used by memcxt.c, list.c, > sortsupport.c as well (maybe clean up fastgetattr too). Yeah, looks reasonable ... material for a different patch of course. But that would mean INLINE_IF_POSSIBLE should be defined someplace else, perhaps c.h. Also, I'm not that thrilled with having the header file define ILIST_USE_DEFINITION. I suggest that it might be better to do #if defined(USE_INLINE) || defined(DEFINE_ILIST_FUNCTIONS) ... function decls here ... #else ... extern decls here ... #endif where ilist.c defines DEFINE_ILIST_FUNCTIONS before including the header. 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] embedded list v2
Alvaro Herrera writes:
> Here's an updated version of both patches, as well as a third patch that
> converts the cc_node list link in catcache.c into an slist.
There's a lot of stuff here that seems rather unfortunate and/or sloppy.
Does it even compile? The 0002 patch refers to a typedef ilist_d_head
that I don't see defined anywhere. (It would be good to shorten that
name by a couple of characters anyway, for tab-stop alignment reasons.)
The documentation (such as it is) claims that the lists are circularly
linked, which doesn't seem to be the case from the code; slist_foreach
for instance certainly won't work if that's true. (As far as the
docs go, I'd get rid of the README file and put the how-to-use-it
comments into the header file, where they have some chance of being
(a) seen and (b) maintained. But first they need to be rewritten.)
The distinction between head and node structs seems rather useless,
and it's certainly notationally tedious. Do we need it?
I find the need for this change quite unfortunate:
@@ -256,7 +258,7 @@ typedef struct
static AutoVacuumShmemStruct *AutoVacuumShmem;
/* the database list in the launcher, and the context that contains it */
-static Dllist *DatabaseList = NULL;
+static ilist_d_head DatabaseList;
static MemoryContext DatabaseListCxt = NULL;
/* Pointer to my own WorkerInfo, valid on each worker */
@@ -403,6 +405,9 @@ AutoVacLauncherMain(int argc, char *argv[])
/* Identify myself via ps */
init_ps_display("autovacuum launcher process", "", "", "");
+ /* initialize to be empty */
+ ilist_d_init(&DatabaseList);
+
ereport(LOG,
(errmsg("autovacuum launcher started")));
Instead let's provide a macro for an empty list value, so that you can
do something like
static ilist_d_head DatabaseList = EMPTY_DLIST;
and not require a new assumption that there will be a convenient place
to initialize static list variables. In general I think it'd be a lot
better if the lists were defined such that all-zeroes is a valid empty
list header, anyway.
The apparently random decisions to make some things inline functions
and other things macros (even though they evaluate their args multiple
times) will come back to bite us. I am much more interested in
unsurprising behavior of these constructs than I am in squeezing out
an instruction or two, so I'm very much against the unsafe macros.
I think we could do without such useless distinctions as slist_get_head
vs slist_get_head_unchecked, too. We've already got Assert and
ILIST_DEBUG, we do not need even more layers of check-or-not
distinctions.
Meanwhile, obvious checks that *should* be made, like slist_pop_head
asserting that there be something to pop, don't seem to be made.
Not a full review, just some things that struck me in a quick scan...
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] embedded list v2
Excerpts from Alvaro Herrera's message of vie sep 14 14:22:18 -0300 2012: > > Here's an updated version of both patches, as well as a third patch that > converts the cc_node list link in catcache.c into an slist. One thing I would like more input in, is whether people think it's worthwhile to split dlists and slists into separate files. Thus far this has been mentioned by three people independently. Another question is whether ilist_container() should actually be a more general macro "containerof" defined in c.h. (ISTM it would be necessary to have this macro if we want to split into two files; that way we don't need to have two macros dlist_container and slist_container with identical definition, or alternatively a third file that defines just ilist_container) Third question is about the INLINE_IF_POSSIBLE business as commented by Peter. It seems to me that the simple technique used here to avoid having two copies of the source could be used by memcxt.c, list.c, sortsupport.c as well (maybe clean up fastgetattr too). -- Álvaro Herrerahttp://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, 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] embedded list v2
Hi Alvaro, Thanks for the review! On Thursday, September 06, 2012 06:09:35 PM Alvaro Herrera wrote: > Here's a prettified version of this stuff. I found one bug in the macro > ilist_s_head: the test was reversed. Oh, good catch. I had only used the _unchecked version because my code checked that there are elements just some lines before that... > Also, curiously, the macro had the same name as the struct, so I renamed the > macro. I take it you haven't used this macro, so maybe it shouldn't be there at all? Or maybe I completely misread what the macro is supposed to do. According to my patches here that got introduced by me whe renaming _front/back to _head/tail according to Roberts wishes. Sorry for that. > I also renamed all the structs and functions by changing ilist_s_foo to > Slist_foo. Similarly for ilist_d_foo. This is all mechanical so any > subsequent patch should be trivial to refresh for this change. Ok. I concur with robert that a lower case first letter might be better readable but again, I don't really care that much. > I think README.ilist (which is what you had in the comment at the top of > ilist.h) should be heavily expanded. I don't find it at all clear. Hm. I agree :(. Let me have a go when you have a state you find acceptable otherwise... > There were other cosmetic changes, but the implementation is pretty much > the same you submitted. Good. > I didn't look at the other patch you posted, replacing dllist.c usage; > will do that next to verify that the list implementation works. Thanks! Greetings, Andres -- Andres Freund http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, 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] embedded list v2
On Thu, Sep 6, 2012 at 12:09 PM, Alvaro Herrera wrote: > Here's a prettified version of this stuff. I found one bug in the macro > ilist_s_head: the test was reversed. Also, curiously, the macro had the > same name as the struct, so I renamed the macro. I take it you haven't > used this macro, so maybe it shouldn't be there at all? Or maybe I > completely misread what the macro is supposed to do. > > I also renamed all the structs and functions by changing ilist_s_foo to > Slist_foo. Similarly for ilist_d_foo. This is all mechanical so any > subsequent patch should be trivial to refresh for this change. I think this is a good direction, but why not just slist_foo and dlist_foo? I don't see much value in capitalizing the first letter. It's not like it's the beginning of a word or anything. Plus, that way the new stuff will be more obviously different from Dllist, which it will (I think) replace. -- 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] embedded list v2
Here's a prettified version of this stuff. I found one bug in the macro ilist_s_head: the test was reversed. Also, curiously, the macro had the same name as the struct, so I renamed the macro. I take it you haven't used this macro, so maybe it shouldn't be there at all? Or maybe I completely misread what the macro is supposed to do. I also renamed all the structs and functions by changing ilist_s_foo to Slist_foo. Similarly for ilist_d_foo. This is all mechanical so any subsequent patch should be trivial to refresh for this change. I think README.ilist (which is what you had in the comment at the top of ilist.h) should be heavily expanded. I don't find it at all clear. There were other cosmetic changes, but the implementation is pretty much the same you submitted. I didn't look at the other patch you posted, replacing dllist.c usage; will do that next to verify that the list implementation works. -- Álvaro Herrerahttp://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Training & Services ilist.patch Description: Binary data -- 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] embedded list v2
Excerpts from Andres Freund's message of jue jun 28 17:06:49 -0400 2012: > On Thursday, June 28, 2012 10:03:26 PM Andres Freund wrote: > > What I wonder is how hard it would be to remove catcache.h's structs into > > the implementation. Thats the reason why the old and new list > > implementation currently is included all over the backend... > Moving them into the implementation isn't possible, but catcache.h being > included just about everywhere simply isn't needed. FWIW this got fixed during some header changes I made a couple of weeks ago. If you have similar fixes to propose, let me know. -- Álvaro Herrerahttp://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, 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] embedded list v2
On Monday, July 23, 2012 12:55:01 PM Peter Geoghegan wrote: > On 5 July 2012 02:49, Peter Geoghegan wrote: > > On 28 June 2012 19:20, Andres Freund wrote: > >> <0001-Add-embedded-list-interface.patch> > >> > >> Looks good now? > > > > I have a few gripes. > > We are passed the nominal deadline. Had you planned on getting back to > me this commitfest? If not, I'll shelve my review of > "0002-Remove-usage-of-lib-dllist.h-and-replace-it-by-the-n.patch" > until commitfest 2012-09, and mark this "returned with feedback". I was actually waiting for the second review ;). Sorry for the misunderstanding. There is no rule that review cannot happen outside the commitfest, so I would appreciate if we could push this further... Andres -- Andres Freund http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, 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] embedded list v2
On 5 July 2012 02:49, Peter Geoghegan wrote: > On 28 June 2012 19:20, Andres Freund wrote: >> <0001-Add-embedded-list-interface.patch> >> >> Looks good now? > > I have a few gripes. We are passed the nominal deadline. Had you planned on getting back to me this commitfest? If not, I'll shelve my review of "0002-Remove-usage-of-lib-dllist.h-and-replace-it-by-the-n.patch" until commitfest 2012-09, and mark this "returned with feedback". -- Peter Geoghegan http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Training and 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] embedded list v2
On 28 June 2012 19:20, Andres Freund wrote: > <0001-Add-embedded-list-interface.patch> > > Looks good now? I have a few gripes. + * there isn't much we can test in a single linked list except that its There are numerous references to "single linked lists", where, I believe, "singly linked list" is intended (the same can be said for "double" and "doubly" respectively). /* Functions we want to be inlined if possible */ + #ifndef USE_INLINE ... + #endif /* USE_INLINE */ A minor quibble, but that last line probably be: #endif /* ! defined USE_INLINE */ Another minor quibble. We usually try and keep these in alphabetical order: *** a/src/backend/lib/Makefile --- b/src/backend/lib/Makefile *** subdir = src/backend/lib *** 12,17 top_builddir = ../../.. include $(top_builddir)/src/Makefile.global ! OBJS = dllist.o stringinfo.o include $(top_srcdir)/src/backend/common.mk --- 12,17 top_builddir = ../../.. include $(top_builddir)/src/Makefile.global ! OBJS = dllist.o stringinfo.o ilist.o include $(top_srcdir)/src/backend/common.mk New files generally don't require this: + * Portions Copyright (c) 1994, Regents of the University of California This needs to be altered: + /* + * enable for extra debugging. This is rather expensive so its not enabled by + * default even with --enable-cassert + */ + /* #define ILIST_DEBUG */ I'm not sure that this extra error-detection warrants its own macro. syncrep.c similarly has its own rather expensive error-detection, with entire function bodies only compiled when USE_ASSERT_CHECKING is defined. Any of the other dedicated "debugging macros", like LOCK_DEBUG or WAL_DEBUG seem to exist to dump LOG messages when binaries were built with the macros defined (this can happen via pg_config_manual.h. I note that what you have here lacks a corresponding entry). I think that it would be more idiomatic to just use USE_ASSERT_CHECKING, and rewrite the debugging functions such that they are used directly within an Assert, in the style of syncrep.c . Now, I know Tom wasn't too enthusiastic about having this sort of thing within --enable-cassert builds, but I'm inclined to think that there is little point in having this additional error checking if they're not at least available when that configuration is used. Maybe we should consider taking the sophisticated asserts out of --enable-cassert builds, or removing them entirely, if and when they prove to be annoying? There is slight misalignment within the comments at the top of ilist.h. Within ilist.c, the following block exists: + #ifndef USE_INLINE + #define ILIST_USE_DECLARATION + #endif + + #include "lib/ilist.h" + + #ifndef USE_INLINE + #undef ILIST_USE_DECLARATION + #endif I see little reason for the latter "#undef" block within ilist.c. It isn't that exactly the same code already exists at the end of ilist.h (though there is that too) - it's mostly that it's unnecessary, because there is no need or logical reason to #undef within ilist.c. + /* + * The following function declarations are only used if inlining is supported + * or when included from a file that explicitly declares USE_DECLARATION + */ + #ifdef ILIST_USE_DECLARATION Shouldn't that be "The following function definitions..." and ILIST_USE_DEFINITIONS? I think the fact that it's possible in principle for ILIST_USE_DECLARATION to not be exactly equivalent to ! USE_INLINE is strictly speaking dangerous, since USE_INLINE needs to be baked into the ABI targeted by third-party module developers. What if a module was built that called a function that didn't have an entry in the procedure linkage table, due to ad-hoc usage of ILIST_USE_DECLARATION? That'd result in a libdl error, if you're lucky. Now, that probably sounds stupid - I'm pretty sure that you didn't intend that ILIST_USE_DECLARATION be set by just any old client of this infrastructure. Rather, you intended that ILIST_USE_DECLARATION be set either when ilist.h was included while USE_INLINE, so that macro expansion would make those functions inline, or within ilist.c, when !USE_INLINE, so that the functions would not be inlined. This should be much more explicit though. You simply describe the mechanism rather than the intent at present. I rather suspect that INLINE_IF_POSSIBLE should be a general purpose utility, perhaps defined next to NON_EXEC_STATIC within c.h, with a brief explanation there (rather than in any new header that needs to do this). I think you'd be able to reasonably split singly and doubly linked lists into their own headers without much repetition between the two then. You could formalise the idea that where USE_INLINE, another macro, defined alongside INLINE_IF_POSSIBLE (functionally equivalent to ILIST_USE_DECLARATION in the extant code - say, USE_INLINING_DEFINITIONS) is going to be generally defined everywhere USE_INLINE is defined. You're then going to have to deal with the hack whereby USE_INLINING_DEFINITIONS is set just "to suck th
Re: [HACKERS] embedded list v2
On Thursday, June 28, 2012 11:45:08 PM Alvaro Herrera wrote: > Excerpts from Andres Freund's message of jue jun 28 17:06:49 -0400 2012: > > On Thursday, June 28, 2012 10:03:26 PM Andres Freund wrote: > > > What I wonder is how hard it would be to remove catcache.h's structs > > > into the implementation. Thats the reason why the old and new list > > > implementation currently is included all over the backend... > > > > Moving them into the implementation isn't possible, but catcache.h being > > included just about everywhere simply isn't needed. > > > > It being included everywhere was introduced by a series of commits from > > Bruce: b85a965f5fc7243d0386085e12f7a6c836503b42 > > b43ebe5f83b28e06a3fd933b989aeccf0df7844a > > e0522505bd13bc5aae993fc50b8f420665d78e96 > > and others > > > > That looks broken. An implementation file not including its own header... > > A minimal patch to fix this particular problem is attached (looks like > > there are others in the series). > > Hmm, I think this is against project policy -- we do want each header to > be compilable separately. I would go instead the way of splitting > resowner.h in two or more pieces. It was done nearly the same way in catcache.h before Bruce changed things. You can see still the rememnants of that in syscache.h: /* list-search interface. Users of this must import catcache.h too */ extern struct catclist *SearchSysCacheList(int cacheId, int nkeys, Datum key1, Datum key2, Datum key3, Datum key4); The only difference is that gcc warns if you declare a struct in a parameter - thats why I forward declared it explicitly... resowner.h still compiles standalone and is still usable. You can even call ResourceOwnerRememberCatCacheListRef if you get the list parameter from somewhere else. Andres -- Andres Freund http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, 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] embedded list v2
Excerpts from Andres Freund's message of jue jun 28 17:06:49 -0400 2012: > On Thursday, June 28, 2012 10:03:26 PM Andres Freund wrote: > > What I wonder is how hard it would be to remove catcache.h's structs into > > the implementation. Thats the reason why the old and new list > > implementation currently is included all over the backend... > Moving them into the implementation isn't possible, but catcache.h being > included just about everywhere simply isn't needed. > > It being included everywhere was introduced by a series of commits from Bruce: > b85a965f5fc7243d0386085e12f7a6c836503b42 > b43ebe5f83b28e06a3fd933b989aeccf0df7844a > e0522505bd13bc5aae993fc50b8f420665d78e96 > and others > > That looks broken. An implementation file not including its own header... A > minimal patch to fix this particular problem is attached (looks like there > are > others in the series). Hmm, I think this is against project policy -- we do want each header to be compilable separately. I would go instead the way of splitting resowner.h in two or more pieces. -- Álvaro Herrera The PostgreSQL Company - Command Prompt, Inc. PostgreSQL Replication, Consulting, Custom Development, 24x7 support -- 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] embedded list v2
Excerpts from Andres Freund's message of jue jun 28 16:03:26 -0400 2012: > > On Thursday, June 28, 2012 09:47:05 PM Alvaro Herrera wrote: > > Excerpts from Andres Freund's message of jue jun 28 14:20:59 -0400 2012: > > > Looks good now? > > > > The one thing I dislike about this code is the names you've chosen. I > > mean, ilist_s_stuff and ilist_d_stuff. I mean, why not just Slist_foo > > and Dlist_bar, say? As far as I can tell, you've chosen the "i" prefix > > because it's "integrated" or "inline", but this seems to me a rather > > irrelevant implementation detail that's of little use to the callers. > Well, its not irrelevant because you actually need to change the contained > structs to use it. I find that a pretty relevant distinction. Sure, at that point it is relevant. Once you're past that, there's no point. I mean, you would look up how it's used in the header comment of the implementation, and then just refer to the API. > > Also, I don't find so great an idea to have everything in a single file. > > Is there anything wrong with separating singly and doubly linked lists > > each to its own file? Other than you not liking it, I mean. As a > > person who spends some time trying to untangle header dependencies, I > > would appreciate keeping stuff as lean as possible. However, since > > nobody else seems to have commented on this, maybe it's just me. > Robert had the same comment, its not just you... > > It would mean duplicating the ugliness around the conditional inlining, the > comment explaining how to use the stuff (because its basically used the same > way for single and double linked lists), you would need to #define > ilist_container twice or have a third file > Just seems to much overhead for ~100 lines (the single linked list > implementation). Well, then don't duplicate a comment -- create a README.lists and refer to it in the comments. Not sure about the ilist_container stuff, but in principle I don't have a problem with having a file with a single #define that's included by two other headers. > What I wonder is how hard it would be to remove catcache.h's structs into the > implementation. Thats the reason why the old and new list implementation > currently is included all over the backend... Yeah, catcache.h is a pretty ugly beast. I'm sure there are ways to behead it. -- Álvaro Herrera The PostgreSQL Company - Command Prompt, Inc. PostgreSQL Replication, Consulting, Custom Development, 24x7 support -- 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] embedded list v2
On Thursday, June 28, 2012 10:03:26 PM Andres Freund wrote: > What I wonder is how hard it would be to remove catcache.h's structs into > the implementation. Thats the reason why the old and new list > implementation currently is included all over the backend... Moving them into the implementation isn't possible, but catcache.h being included just about everywhere simply isn't needed. It being included everywhere was introduced by a series of commits from Bruce: b85a965f5fc7243d0386085e12f7a6c836503b42 b43ebe5f83b28e06a3fd933b989aeccf0df7844a e0522505bd13bc5aae993fc50b8f420665d78e96 and others That looks broken. An implementation file not including its own header... A minimal patch to fix this particular problem is attached (looks like there are others in the series). Andres -- Andres Freund http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Training & Services From 45e2c358e6a21e837f13731981da2644bcb57a88 Mon Sep 17 00:00:00 2001 From: Andres Freund Date: Thu, 28 Jun 2012 23:03:44 +0200 Subject: [PATCH] Stop including catcache.h from syscache.h syscache.h used to not rely on catcache.h and even today ships with the comment "Users of this must import catcache.h too" for the one function requiring catcache.h knowledge. This was changed in a series of commits including: b85a965f5fc7243d0386085e12f7a6c836503b42 b43ebe5f83b28e06a3fd933b989aeccf0df7844a e0522505bd13bc5aae993fc50b8f420665d78e96 Change it back. --- src/backend/access/transam/xact.c |1 + src/backend/catalog/namespace.c |1 + src/backend/catalog/pg_conversion.c |1 + src/backend/catalog/pg_enum.c |1 + src/backend/utils/adt/acl.c |1 + src/backend/utils/cache/attoptcache.c |1 + src/backend/utils/cache/catcache.c|1 + src/backend/utils/cache/inval.c |1 + src/backend/utils/cache/lsyscache.c |1 + src/backend/utils/cache/relcache.c|1 + src/backend/utils/cache/spccache.c|1 + src/backend/utils/cache/syscache.c|1 + src/backend/utils/cache/ts_cache.c|1 + src/backend/utils/cache/typcache.c|1 + src/backend/utils/resowner/resowner.c |5 +++-- src/include/utils/resowner.h | 10 ++ src/include/utils/snapmgr.h |1 + src/include/utils/syscache.h |2 +- 18 files changed, 25 insertions(+), 7 deletions(-) diff --git a/src/backend/access/transam/xact.c b/src/backend/access/transam/xact.c index 4755ee6..1f743f7 100644 --- a/src/backend/access/transam/xact.c +++ b/src/backend/access/transam/xact.c @@ -44,6 +44,7 @@ #include "storage/procarray.h" #include "storage/sinvaladt.h" #include "storage/smgr.h" +#include "utils/catcache.h" #include "utils/combocid.h" #include "utils/guc.h" #include "utils/inval.h" diff --git a/src/backend/catalog/namespace.c b/src/backend/catalog/namespace.c index 20850ab..10ad82b 100644 --- a/src/backend/catalog/namespace.c +++ b/src/backend/catalog/namespace.c @@ -46,6 +46,7 @@ #include "storage/sinval.h" #include "utils/acl.h" #include "utils/builtins.h" +#include "utils/catcache.h" #include "utils/guc.h" #include "utils/inval.h" #include "utils/lsyscache.h" diff --git a/src/backend/catalog/pg_conversion.c b/src/backend/catalog/pg_conversion.c index f86c84f..358bd39 100644 --- a/src/backend/catalog/pg_conversion.c +++ b/src/backend/catalog/pg_conversion.c @@ -25,6 +25,7 @@ #include "catalog/pg_proc.h" #include "mb/pg_wchar.h" #include "utils/builtins.h" +#include "utils/catcache.h" #include "utils/fmgroids.h" #include "utils/rel.h" #include "utils/syscache.h" diff --git a/src/backend/catalog/pg_enum.c b/src/backend/catalog/pg_enum.c index 41665c1..20e26c4 100644 --- a/src/backend/catalog/pg_enum.c +++ b/src/backend/catalog/pg_enum.c @@ -23,6 +23,7 @@ #include "storage/lmgr.h" #include "miscadmin.h" #include "utils/builtins.h" +#include "utils/catcache.h" #include "utils/fmgroids.h" #include "utils/syscache.h" #include "utils/tqual.h" diff --git a/src/backend/utils/adt/acl.c b/src/backend/utils/adt/acl.c index 77322a1..2cc87d8 100644 --- a/src/backend/utils/adt/acl.c +++ b/src/backend/utils/adt/acl.c @@ -29,6 +29,7 @@ #include "miscadmin.h" #include "utils/acl.h" #include "utils/builtins.h" +#include "utils/catcache.h" #include "utils/inval.h" #include "utils/lsyscache.h" #include "utils/memutils.h" diff --git a/src/backend/utils/cache/attoptcache.c b/src/backend/utils/cache/attoptcache.c index e01ae21..5d872ba 100644 --- a/src/backend/utils/cache/attoptcache.c +++ b/src/backend/utils/cache/attoptcache.c @@ -18,6 +18,7 @@ #include "access/reloptions.h" #include "utils/attoptcache.h" +#include "utils/catcache.h" #include "utils/hsearch.h" #include "utils/inval.h" #include "utils/syscache.h" diff --git a/src/backend/utils/cache/catcache.c b/src/backend/utils/cache/catcache.c index 0307b96..f27d90d 100644 --- a/src/backend/utils/cache/catcache.c +++ b/src/backend/utils/cache/catcache.c
Re: [HACKERS] embedded list v2
On Thursday, June 28, 2012 09:47:05 PM Alvaro Herrera wrote: > Excerpts from Andres Freund's message of jue jun 28 14:20:59 -0400 2012: > > Looks good now? > > The one thing I dislike about this code is the names you've chosen. I > mean, ilist_s_stuff and ilist_d_stuff. I mean, why not just Slist_foo > and Dlist_bar, say? As far as I can tell, you've chosen the "i" prefix > because it's "integrated" or "inline", but this seems to me a rather > irrelevant implementation detail that's of little use to the callers. Well, its not irrelevant because you actually need to change the contained structs to use it. I find that a pretty relevant distinction. > Also, I don't find so great an idea to have everything in a single file. > Is there anything wrong with separating singly and doubly linked lists > each to its own file? Other than you not liking it, I mean. As a > person who spends some time trying to untangle header dependencies, I > would appreciate keeping stuff as lean as possible. However, since > nobody else seems to have commented on this, maybe it's just me. Robert had the same comment, its not just you... It would mean duplicating the ugliness around the conditional inlining, the comment explaining how to use the stuff (because its basically used the same way for single and double linked lists), you would need to #define ilist_container twice or have a third file Just seems to much overhead for ~100 lines (the single linked list implementation). What I wonder is how hard it would be to remove catcache.h's structs into the implementation. Thats the reason why the old and new list implementation currently is included all over the backend... Greetings, Andres -- Andres Freund http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, 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] embedded list v2
On Thu, Jun 28, 2012 at 3:47 PM, Alvaro Herrera wrote: > > Excerpts from Andres Freund's message of jue jun 28 14:20:59 -0400 2012: > >> Looks good now? > > The one thing I dislike about this code is the names you've chosen. I > mean, ilist_s_stuff and ilist_d_stuff. I mean, why not just Slist_foo > and Dlist_bar, say? As far as I can tell, you've chosen the "i" prefix > because it's "integrated" or "inline", but this seems to me a rather > irrelevant implementation detail that's of little use to the callers. > > Also, I don't find so great an idea to have everything in a single file. > Is there anything wrong with separating singly and doubly linked lists > each to its own file? Other than you not liking it, I mean. As a > person who spends some time trying to untangle header dependencies, I > would appreciate keeping stuff as lean as possible. However, since > nobody else seems to have commented on this, maybe it's just me. Well, it's not JUST you. I agree entirely with all of your points. -- 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] embedded list v2
Excerpts from Andres Freund's message of jue jun 28 14:20:59 -0400 2012: > Looks good now? The one thing I dislike about this code is the names you've chosen. I mean, ilist_s_stuff and ilist_d_stuff. I mean, why not just Slist_foo and Dlist_bar, say? As far as I can tell, you've chosen the "i" prefix because it's "integrated" or "inline", but this seems to me a rather irrelevant implementation detail that's of little use to the callers. Also, I don't find so great an idea to have everything in a single file. Is there anything wrong with separating singly and doubly linked lists each to its own file? Other than you not liking it, I mean. As a person who spends some time trying to untangle header dependencies, I would appreciate keeping stuff as lean as possible. However, since nobody else seems to have commented on this, maybe it's just me. -- Álvaro Herrera The PostgreSQL Company - Command Prompt, Inc. PostgreSQL Replication, Consulting, Custom Development, 24x7 support -- 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] embedded list v2
On Thursday, June 28, 2012 06:23:05 PM Robert Haas wrote:
> On Tue, Jun 26, 2012 at 7:26 PM, Andres Freund
wrote:
> > Attached are three patches:
> > 1. embedded list implementation
> > 2. make the list implementation usable without USE_INLINE
> > 3. convert all callers to ilist.h away from dllist.h
>
> This code doesn't follow PostgreSQL coding style guidelines; in a
> function definition, the name must start on its own line.
Hrmpf. Yes.
> Also, stuff like this is grossly unlike what's done elsewhere; use the same
> formatting as e.g. foreach:
> +#define ilist_d_reverse_foreach(name, ptr) for(name =
> (ptr)->head.prev;\
> + name != &(ptr)->head;\
> + name = name->prev)
Its not only unlike the rest its also ugly... Fixed.
> And this is definitely NOT going to survive pgindent:
>
> +for(cur = head->head.prev;
> +cur != &head->head;
> +cur = cur->prev){
> + if(!(cur) ||
> + !(cur->next) ||
> + !(cur->prev) ||
> + !(cur->prev->next == cur) ||
> + !(cur->next->prev == cur))
> + {
> + elog(ERROR, "double linked list is corrupted");
> + }
> +}
I changed the for() contents to one line. I don't think I can write anything
that won't be changed by pgindent for the if()s contents.
> And this is another meme we don't use elsewhere; add an explicit NULL test:
>
> + while ((cur = last->next))
Fixed.
> And then there's stuff like this:
>
> + if(!cur){
> + elog(ERROR, "single linked list is corrupted");
> + }
Fixed the places that I found.
> Aside from the formatting issues, I think it would be sensible to
> preserve the terminology of talking about the "head" and "tail" of a
> list that we use elsewhere, instead of calling them the "front" and
> "back" as you've done here. I would suggest that instead of add_after
> and add_before you use the names insert_after and insert_before, which
> I think is more clear; also instead of remove, I think you should say
> delete, for consistency with pg_list.h.
Heh. Ive been poisoned from using c++ too much (thats partially stl names).
Changed.
> A number of these inlined functions could be rewritten as macros -
> e.g. ilist_d_has_next, ilist_d_has_prev, ilist_d_is_empty. Since some
> things are written as macros anyway maybe it's good to do all the
> one-liners that way, although I guess it doesn't matter that much.
I find inline functions preferrable because of multiple evaluation stuff. The
macros are macros because of the dynamic return type and other similar issues
which cannot be done in plain C.
> I also agree with your XXX comment that ilist_s_remove should probably
> be out of line.
Done.
Looks good now?
Andres
--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services
From c3c80925e780489351c4de210364e55d223f02a8 Mon Sep 17 00:00:00 2001
From: Andres Freund
Date: Sun, 6 May 2012 00:26:35 +0200
Subject: [PATCH 1/2] Add embedded list interface
Adds a single and a double linked list which can easily embedded into other
datastructures and can be used without additional memory allocations.
---
src/backend/lib/Makefile |2 +-
src/backend/lib/ilist.c | 123
src/include/lib/ilist.h | 468 ++
3 files changed, 592 insertions(+), 1 deletion(-)
create mode 100644 src/backend/lib/ilist.c
create mode 100644 src/include/lib/ilist.h
diff --git a/src/backend/lib/Makefile b/src/backend/lib/Makefile
index 2e1061e..c94297a 100644
--- a/src/backend/lib/Makefile
+++ b/src/backend/lib/Makefile
@@ -12,6 +12,6 @@ subdir = src/backend/lib
top_builddir = ../../..
include $(top_builddir)/src/Makefile.global
-OBJS = dllist.o stringinfo.o
+OBJS = dllist.o stringinfo.o ilist.o
include $(top_srcdir)/src/backend/common.mk
diff --git a/src/backend/lib/ilist.c b/src/backend/lib/ilist.c
new file mode 100644
index 000..f78ac51
--- /dev/null
+++ b/src/backend/lib/ilist.c
@@ -0,0 +1,123 @@
+/*-
+ *
+ * ilist.c
+ * support for integrated/inline double and single linked lists
+ *
+ * Portions Copyright (c) 1996-2012, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ * src/backend/lib/ilist.c
+ *
+ * NOTES
+ *
+ * This function only contains testing code for inline single/double linked
+ * lists.
+ *
+ *-
+ */
+
+#include "postgres.h"
+
+/*
+ * If inlines aren't available include the function as defined in the header,
+ * but without 'static inline' defined. That way we do not have to duplicate
+ * their functionality.
+ */
+#ifndef USE_INLINE
+#
Re: [HACKERS] embedded list v2
On Tue, Jun 26, 2012 at 7:26 PM, Andres Freund wrote:
> Attached are three patches:
> 1. embedded list implementation
> 2. make the list implementation usable without USE_INLINE
> 3. convert all callers to ilist.h away from dllist.h
This code doesn't follow PostgreSQL coding style guidelines; in a
function definition, the name must start on its own line. Also, stuff
like this is grossly unlike what's done elsewhere; use the same
formatting as e.g. foreach:
+#define ilist_d_reverse_foreach(name, ptr) for(name =
(ptr)->head.prev;\
+ name != &(ptr)->head;\
+ name = name->prev)
And this is definitely NOT going to survive pgindent:
+for(cur = head->head.prev;
+cur != &head->head;
+cur = cur->prev){
+ if(!(cur) ||
+ !(cur->next) ||
+ !(cur->prev) ||
+ !(cur->prev->next == cur) ||
+ !(cur->next->prev == cur))
+ {
+ elog(ERROR, "double linked list is corrupted");
+ }
+}
And this is another meme we don't use elsewhere; add an explicit NULL test:
+ while ((cur = last->next))
And then there's stuff like this:
+ if(!cur){
+ elog(ERROR, "single linked list is corrupted");
+ }
Aside from the formatting issues, I think it would be sensible to
preserve the terminology of talking about the "head" and "tail" of a
list that we use elsewhere, instead of calling them the "front" and
"back" as you've done here. I would suggest that instead of add_after
and add_before you use the names insert_after and insert_before, which
I think is more clear; also instead of remove, I think you should say
delete, for consistency with pg_list.h.
A number of these inlined functions could be rewritten as macros -
e.g. ilist_d_has_next, ilist_d_has_prev, ilist_d_is_empty. Since some
things are written as macros anyway maybe it's good to do all the
one-liners that way, although I guess it doesn't matter that much. I
also agree with your XXX comment that ilist_s_remove should probably
be out of line.
Apart from the above, mostly fairly superficial concerns I think this
makes sense.
--
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
[HACKERS] embedded list v2
Hi,
To recapitulate why I think this sort of embedded list is worthwile:
* minimal memory overhead (16 bytes for double linked list heads/nodes on
64bit systems)
* no additional memory allocation overhead
* no additional dereference to access the contents of a list element
* most modifications are completely branchless
* the current dllist.h interface has double the memory overhead and much more
complex manipulation operators
* Multiple places in postgres have grown local single or double linked list
implementations
* I need it ;)
Attached are three patches:
1. embedded list implementation
2. make the list implementation usable without USE_INLINE
3. convert all callers to ilist.h away from dllist.h
For 1 I:
a. added more comments and some introduction, some more functions
b. moved the file from utils/ilist.h to lib/ilist.h
c. actually included the c file with the check functions
d. did *not* split it up into single/double linked list files, doesn't seem to
be worth the trouble given how small ilist.(c|h) are
e. did *not* try to get an interface similar to dllist.h. I don't think the
old one is better and it makes the breakage more obvious should somebody else
use the old implementation although I doubt it.
I can be convinced to do d. and e. but I don't think they are an improvement.
For 2 I used ugly macro hackery to avoid declaring every function twice, in a
c file and in a header.
Opinions on the state of the above patches?
I did not expect any performance difference in the current usage, but just to
be sure I ran the following tests:
connection heavy:
pgbench -n -S -p 5501 -h /tmp -U andres postgres -c 16 -j 16 -T 10 -C
master: 3109 3024 3012
ilist: 3097 3033 3024
somewhat SearchCatCache heavy:
pgbench -n -S -p 5501 -h /tmp -U andres postgres -T 100 -c 16 -j 1
master: 98979.453879 99554.485631 99393.587880
ilist: 98960.545559 99583.319870 99498.923273
As expected the differences are on the level of noise...
Greetings,
Andres
--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services
From 2e9d955fbb625004061509a62ecca83fde68d027 Mon Sep 17 00:00:00 2001
From: Andres Freund
Date: Sun, 6 May 2012 00:26:35 +0200
Subject: [PATCH 1/3] Add embedded list interface (header only)
Adds a single and a double linked list which can easily embedded into other
datastructures and can be used without any additional allocations.
Problematic: It requires USE_INLINE to be used. It could be remade to fallback
to to externally defined functions if that is not available but that hardly
seems sensibly at this day and age. Besides, the speed hit would be noticeable
and its only used in new code which could be disabled on machines - given they
still exists - without proper support for inline functions
3 files changed, 509 insertions(+), 1 deletion(-)
diff --git a/src/backend/lib/Makefile b/src/backend/lib/Makefile
index 2e1061e..c94297a 100644
--- a/src/backend/lib/Makefile
+++ b/src/backend/lib/Makefile
@@ -12,6 +12,6 @@ subdir = src/backend/lib
top_builddir = ../../..
include $(top_builddir)/src/Makefile.global
-OBJS = dllist.o stringinfo.o
+OBJS = dllist.o stringinfo.o ilist.o
include $(top_srcdir)/src/backend/common.mk
diff --git a/src/backend/lib/ilist.c b/src/backend/lib/ilist.c
new file mode 100644
index 000..72de7a3
--- /dev/null
+++ b/src/backend/lib/ilist.c
@@ -0,0 +1,79 @@
+/*-
+ *
+ * ilist.c
+ * support for integrated/inline double and single linked lists
+ *
+ * Portions Copyright (c) 1996-2012, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ * src/backend/lib/ilist.c
+ *
+ * NOTES
+ *
+ * This function only contains testing code for inline single/double linked
+ * lists.
+ *
+ *-
+ */
+
+#include "postgres.h"
+
+#include "lib/ilist.h"
+
+#ifdef ILIST_DEBUG
+void ilist_d_check(ilist_d_head* head)
+{
+ilist_d_node *cur;
+
+if(!head ||
+ !(&head->head))
+ elog(ERROR, "double linked list head is not properly initialized");
+
+for(cur = head->head.next;
+cur != &head->head;
+cur = cur->next){
+ if(!(cur) ||
+ !(cur->next) ||
+ !(cur->prev) ||
+ !(cur->prev->next == cur) ||
+ !(cur->next->prev == cur))
+ {
+ elog(ERROR, "double linked list is corrupted");
+ }
+}
+
+for(cur = head->head.prev;
+cur != &head->head;
+cur = cur->prev){
+ if(!(cur) ||
+ !(cur->next) ||
+ !(cur->prev) ||
+ !(cur->prev->next == cur) ||
+ !(cur->next->prev == cur))
+ {
+ elog(ERROR, "double linked list is corrupted");
+ }
+}
+}
+
+void ilist_s_check(ilist_s_head* head)
+{
+ilist_s_node *cur;
+
+if(!head ||
+ !(&head->head))
+ elog(E
