Re: [HACKERS] [PATCH 04/16] Add embedded list interface (header only)
Peter Geoghegan pe...@2ndquadrant.com writes: On 22 June 2012 01:04, Tom Lane t...@sss.pgh.pa.us wrote: This is nonsense. There are at least three buildfarm machines running compilers that do not pretend to be gcc (at least, configure recognizes them as not gcc) and are not MSVC either. So those three don't have medium to high degrees of compatibility with GCC? Uh, they all compile C, so perforce they have reasonable degrees of compatibility with gcc. That doesn't mean they implement gcc's nonstandard extensions. We ought to have more IMO, because software monocultures are dangerous. Of those three, two pass the quiet inline test and one --- the newest of the three if I guess correctly --- does not. So it is not the case that !USE_INLINE is dead code, even if you adopt the position that we don't care about any compiler not represented in the buildfarm. I note that you said that it doesn't pass the quiet inline test, and not that it doesn't support inline functions. What's your point? If the compiler isn't implementing inline the same way gcc does, we can't use the same inlining arrangements. I will be the first to agree that C99's definition of inline sucks, but that doesn't mean we can assume that gcc's version is implemented everywhere. 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] [PATCH 04/16] Add embedded list interface (header only)
Andres Freund and...@2ndquadrant.com writes: On Friday, June 22, 2012 02:04:02 AM Tom Lane wrote: This is nonsense. There are at least three buildfarm machines running compilers that do not pretend to be gcc (at least, configure recognizes them as not gcc) and are not MSVC either. Should there be no other trick - I think there is though - we could just specify -W2177 as an alternative parameter to test in the 'quiet static inline' test. What is that, an MSVC switch? If so it's rather irrelevant to non-MSVC compilers. I definitely do not want to bar any sensible compiler from compiling postgres but the keyword here is 'sensible'. If it requires some modest force/trickery to behave sensible, thats ok, but if we need to ship around huge unreadable crufty macros just to support them I don't find it ok. So you propose to define any compiler that strictly implements C99 as not sensible and not one that will be able to compile Postgres? I do not think that's acceptable. I have no problem with producing better code on gcc than elsewhere (as we already do), but being flat out broken for compilers that don't match gcc's interpretation of inline is not good enough. 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] [PATCH 04/16] Add embedded list interface (header only)
On Monday, June 25, 2012 05:15:43 PM Tom Lane wrote: Andres Freund and...@2ndquadrant.com writes: On Friday, June 22, 2012 02:04:02 AM Tom Lane wrote: This is nonsense. There are at least three buildfarm machines running compilers that do not pretend to be gcc (at least, configure recognizes them as not gcc) and are not MSVC either. Should there be no other trick - I think there is though - we could just specify -W2177 as an alternative parameter to test in the 'quiet static inline' test. What is that, an MSVC switch? If so it's rather irrelevant to non-MSVC compilers. HP-UX/aCC, the only compiler in the buildfarm I found that seems to fall short in the quiet inline test. MSVC seems to work fine with in supported versions, USE_INLINE is defined these days. I definitely do not want to bar any sensible compiler from compiling postgres but the keyword here is 'sensible'. If it requires some modest force/trickery to behave sensible, thats ok, but if we need to ship around huge unreadable crufty macros just to support them I don't find it ok. So you propose to define any compiler that strictly implements C99 as not sensible and not one that will be able to compile Postgres? I do not think that's acceptable. I have no problem with producing better code on gcc than elsewhere (as we already do), but being flat out broken for compilers that don't match gcc's interpretation of inline is not good enough. I propose to treat any compiler which has no way to get to equivalent behaviour as not sensible. Yes. I don't think there really are many of those around. As you pointed out there is only one compiler in the buildfarm with problems and I think those can be worked around (can't test it yet though, the only HP-UX I could get my hands on quickly is at 11.11...). 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] [PATCH 04/16] Add embedded list interface (header only)
Andres Freund and...@2ndquadrant.com writes: On Monday, June 25, 2012 05:15:43 PM Tom Lane wrote: So you propose to define any compiler that strictly implements C99 as not sensible and not one that will be able to compile Postgres? I propose to treat any compiler which has no way to get to equivalent behaviour as not sensible. Yes. Well, my response is no. I could see saying that we require (some) C99 features at this point, but not features that are in no standard, no matter how popular gcc might be. I don't think there really are many of those around. As you pointed out there is only one compiler in the buildfarm with problems This just means we don't have a wide enough collection of non-mainstream machines in the buildfarm. Deciding to break any platform with a non-gcc-equivalent compiler isn't going to improve 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] [PATCH 04/16] Add embedded list interface (header only)
On Monday, June 25, 2012 05:57:51 PM Tom Lane wrote: Andres Freund and...@2ndquadrant.com writes: On Monday, June 25, 2012 05:15:43 PM Tom Lane wrote: So you propose to define any compiler that strictly implements C99 as not sensible and not one that will be able to compile Postgres? I propose to treat any compiler which has no way to get to equivalent behaviour as not sensible. Yes. Well, my response is no. I could see saying that we require (some) C99 features at this point, but not features that are in no standard, no matter how popular gcc might be. I fail to see how gcc is the relevant point here given that there is equivalent definitions available from multiple compiler vendors. Also, 'static inline' *is* C99 conforming as far as I can see? The problem with it is that some compilers may warn if the function isn't used in the same translation unit. Thats doesn't make not using a function non standard- conforming though. I don't think there really are many of those around. As you pointed out there is only one compiler in the buildfarm with problems This just means we don't have a wide enough collection of non-mainstream machines in the buildfarm. Deciding to break any platform with a non-gcc-equivalent compiler isn't going to improve that. No, it won't improve that. But neither will the contrary. 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] [PATCH 04/16] Add embedded list interface (header only)
Andres Freund and...@2ndquadrant.com writes: On Monday, June 25, 2012 05:57:51 PM Tom Lane wrote: Well, my response is no. I could see saying that we require (some) C99 features at this point, but not features that are in no standard, no matter how popular gcc might be. Also, 'static inline' *is* C99 conforming as far as I can see? Hmm. I went back and re-read the C99 spec, and it looks like most of the headaches we had in the past with C99 inline are specific to the case where you want an extern declaration to be available. For a function that exists *only* as a static it might be all right. So maybe I'm misremembering how well this would work. We'd have to be sure we don't need any extern declarations, though. Having said that, I'm still of the opinion that it's not so hard to deal with that we should just blow off compilers where inline doesn't work well. I have no sympathy at all for the we'd need two copies argument. First off, if the code is at any risk whatsoever of changing intra-major-release, it is not acceptable to inline it (there would be inline copies in third-party modules where we couldn't ensure recompilation). So that's going to force us to use this only in cases where the code is small and stable enough that two copies aren't such a big problem. Second, it's not that hard to set things up so there's only one source-code copy, as was noted upthread. 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] [PATCH 04/16] Add embedded list interface (header only)
On 25 June 2012 20:59, Tom Lane t...@sss.pgh.pa.us wrote: Andres Freund and...@2ndquadrant.com writes: Also, 'static inline' *is* C99 conforming as far as I can see? Hmm. I went back and re-read the C99 spec, and it looks like most of the headaches we had in the past with C99 inline are specific to the case where you want an extern declaration to be available. For a function that exists *only* as a static it might be all right. So maybe I'm misremembering how well this would work. We'd have to be sure we don't need any extern declarations, though. Yeah, the extern inline functions sounds at least superficially similar to what happened with extern templates in C++ - exactly one compiler vendor implemented them to the letter of the standard (they remained completely unimplemented elsewhere), and subsequently went bust, before they were eventually removed from the standard last year. Note that when you build Postgres with Clang, it's implicitly and automatically building C code as C99. There is an excellent analysis of the situation here, under C99 inline functions: http://clang.llvm.org/compatibility.html Having said that, I'm still of the opinion that it's not so hard to deal with that we should just blow off compilers where inline doesn't work well. Fair enough. -- 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] [PATCH 04/16] Add embedded list interface (header only)
On Friday, June 22, 2012 12:23:57 AM Peter Geoghegan wrote: On 20 June 2012 14:38, Andres Freund and...@2ndquadrant.com wrote: It incurs a rather high performance overhead due to added memory allocations and added pointer indirections. Thats fine for most of the current users of the List interface, but certainly not for all. In other places you cannot even have memory allocations because the list lives in shared memory. Yes, in general lists interact horribly with the memory hierarchy. I think I pointed out to you once a rant of mine on -hackers a while back in which I made various points about just how badly they do these days. Yes, but how is that relevant? Its still the best data structure for many use- cases. Removing one of the two indirections is still a good idea, hence this patch ;) On modern architectures, with many layers of cache, the cost of the linear search to get an insertion point is very large. So this: /* * removes a node from a list * Attention: O(n) */ static inline void ilist_s_remove(ilist_s_head *head, ilist_s_node *node) is actually even worse than you might suspect. O(n) is O(n), the constant is irrelevant. Anybody who uses arbitrary node removal in a single linked link in the fast path is deserves the pain ;) Several of the pieces of code I pointed out in a previous email use open-coded list implementation exactly to prevent those problems. Interesting. So, it seems like this list implementation could be described as a minimal embeddable list implementation that requires the user to do all the memory allocation, and offers a doubly-linked list too. Not an unreasonable idea. I do think that the constraints you have are not well served by any existing implementation, including List and Dllist. Yep. Note though that you normally wouldn't do extra/manual memory allocation because you just use the already allocated memory of the struct where you embedded the list element into. Are you planning on just overhauling the Dllist interface in your next iteration? It needs to be unified. Not yet sure whether its better to just remove Dllist or morph my code into it. All of the less popular compilers we support we support precisely because they pretend to be GCC, with the sole exception, as always, of the Microsoft product, in this case MSVC. So my position is that I'm in broad agreement that we should freely allow the use of inline without macro hacks, since we generally resists using macro hacks if that makes code ugly, which USE_INLINE certainly does, and for a benefit that is indistinguishable from zero, at least to me. Tom already pointed out that not all compilers pretend to be gcc. I agree though that we should try to make all supported compilers support USE_INLINE. I think with some ugliness that should be possible at least for aCC. Will respond to Tom on that. Why are you using the stdlib's assert.h? Why have you used the NDEBUG macro rather than USE_ASSERT_CHECKING? This might make sense if the header was intended to live in port, but it isn't, right? That should probably be removed, yes. I did it that way that it could be tested independently of casserts because the list checking code turns some linear algorithms into quadratic ones which is noticeable even when --enable- cassert is defined. Why have you done this: #ifdef __GNUC__ #define unused_attr __attribute__((unused)) #else #define unused_attr #endif and then gone on to use this unused_attr macro all over the place? Firstly, that isn't going to suppress the warnings on many platforms that we support, and we do make an effort to build warning free on at least 3 compilers these days - GCC, Clang and MSVC. Secondly, compilers give these warnings because it doesn't make any sense to have an unused parameter - so why have you used one? At the very least, if you require this exact interface, use compatibility macros. I can't imagine why that would be important though. And even if you did want a standard unused_attr facility, you'd do that in c.h, where a lot of that stuff lives. If you look at the places its mostly used in functions like: /* * adds a node at the beginning of the list */ static inline void ilist_d_push_front(ilist_d_head *head, ilist_d_node *node) { node-next = head-head.next; node-prev = head-head; node-next-prev = node; head-head.next = node; ilist_d_check(head); } Where ilist_d_check doesn't do anything if assertions aren't enabled which gcc unfortunately groks and warns. The other case is functions like: static inline void ilist_s_add_after(unused_attr ilist_s_head *head, ilist_s_node *after, ilist_s_node *node) { node-next = after-next; after-next = node; } Where it makes sense for the api to get the head element for consistency reasons. It very well would be possible to add a checking
Re: [HACKERS] [PATCH 04/16] Add embedded list interface (header only)
On Friday, June 22, 2012 02:04:02 AM Tom Lane wrote: Peter Geoghegan pe...@2ndquadrant.com writes: All of the less popular compilers we support we support precisely because they pretend to be GCC, with the sole exception, as always, of the Microsoft product, in this case MSVC. This is nonsense. There are at least three buildfarm machines running compilers that do not pretend to be gcc (at least, configure recognizes them as not gcc) and are not MSVC either. We ought to have more IMO, because software monocultures are dangerous. Of those three, two pass the quiet inline test and one --- the newest of the three if I guess correctly --- does not. So it is not the case that !USE_INLINE is dead code, even if you adopt the position that we don't care about any compiler not represented in the buildfarm. I think you can make hpux's acc do the right thing with some trickery though. I don't have access to hpux anymore though so I can't test it. Should there be no other trick - I think there is though - we could just specify -W2177 as an alternative parameter to test in the 'quiet static inline' test. I definitely do not want to bar any sensible compiler from compiling postgres but the keyword here is 'sensible'. If it requires some modest force/trickery to behave sensible, thats ok, but if we need to ship around huge unreadable crufty macros just to support them I don't find it ok. 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] [PATCH 04/16] Add embedded list interface (header only)
Andres Freund and...@2ndquadrant.com writes: On Friday, June 22, 2012 12:23:57 AM Peter Geoghegan wrote: Why are you using the stdlib's assert.h? Why have you used the NDEBUG macro rather than USE_ASSERT_CHECKING? This might make sense if the header was intended to live in port, but it isn't, right? That should probably be removed, yes. I did it that way that it could be tested independently of casserts because the list checking code turns some linear algorithms into quadratic ones which is noticeable even when --enable- cassert is defined. As far as that goes, I wonder whether the list-checking code hasn't long since served its purpose. Neil Conway put it in when he redid the List API to help catch places that were using no-longer-supported hacks; but it's been years since I've seen it catch anything. I suggest that we might want to either remove it, or enable it via something other than USE_ASSERT_CHECKING (and not enable it by default). 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] [PATCH 04/16] Add embedded list interface (header only)
On Friday, June 22, 2012 04:18:35 PM Tom Lane wrote: Andres Freund and...@2ndquadrant.com writes: On Friday, June 22, 2012 12:23:57 AM Peter Geoghegan wrote: Why are you using the stdlib's assert.h? Why have you used the NDEBUG macro rather than USE_ASSERT_CHECKING? This might make sense if the header was intended to live in port, but it isn't, right? That should probably be removed, yes. I did it that way that it could be tested independently of casserts because the list checking code turns some linear algorithms into quadratic ones which is noticeable even when --enable- cassert is defined. As far as that goes, I wonder whether the list-checking code hasn't long since served its purpose. Neil Conway put it in when he redid the List API to help catch places that were using no-longer-supported hacks; but it's been years since I've seen it catch anything. I suggest that we might want to either remove it, or enable it via something other than USE_ASSERT_CHECKING (and not enable it by default). Oh, I and Peter weren't talking about the pg_list.h stuff, it was about my 'embedded list' implementation which started this subthread. The pg_list.h/list.c stuff isn't problematic as far as I have seen in profiles; its checks are pretty simple so I do not find that surprising. We might want to disable it by default anyway. In my code the list checking stuff iterates over the complete list after modifications and checks that all prev/next pointers are correct so its linear in itself... 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] [PATCH 04/16] Add embedded list interface (header only)
Andres Freund and...@2ndquadrant.com writes: Oh, I and Peter weren't talking about the pg_list.h stuff, it was about my 'embedded list' implementation which started this subthread. The pg_list.h/list.c stuff isn't problematic as far as I have seen in profiles; its checks are pretty simple so I do not find that surprising. We might want to disable it by default anyway. In my code the list checking stuff iterates over the complete list after modifications and checks that all prev/next pointers are correct so its linear in itself... Well, so does list.c, so I'd expect the performance risks to be similar. Possibly you're testing on longer lists than are typical in the backend. 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] [PATCH 04/16] Add embedded list interface (header only)
On Friday, June 22, 2012 04:41:20 PM Tom Lane wrote: Andres Freund and...@2ndquadrant.com writes: Oh, I and Peter weren't talking about the pg_list.h stuff, it was about my 'embedded list' implementation which started this subthread. The pg_list.h/list.c stuff isn't problematic as far as I have seen in profiles; its checks are pretty simple so I do not find that surprising. We might want to disable it by default anyway. In my code the list checking stuff iterates over the complete list after modifications and checks that all prev/next pointers are correct so its linear in itself... Well, so does list.c, so I'd expect the performance risks to be similar. Possibly you're testing on longer lists than are typical in the backend. I don't think list.c does so: static void check_list_invariants(const List *list) { if (list == NIL) return; Assert(list-length 0); Assert(list-head != NULL); Assert(list-tail != NULL); Assert(list-type == T_List || list-type == T_IntList || list-type == T_OidList); if (list-length == 1) Assert(list-head == list-tail); if (list-length == 2) Assert(list-head-next == list-tail); Assert(list-tail-next == NULL); } But yes, the lists I deal with are significantly longer, so replacing O(n) by O(n^2) is rather painful there... 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] [PATCH 04/16] Add embedded list interface (header only)
Andres Freund and...@2ndquadrant.com writes: On Friday, June 22, 2012 04:41:20 PM Tom Lane wrote: Well, so does list.c, so I'd expect the performance risks to be similar. I don't think list.c does so: Huh, OK. I seem to remember that the original version actually chased down the whole list and verified that the length matched. We must've soon decided that that was insupportable in practice. There might be a lesson here for your checks. 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] [PATCH 04/16] Add embedded list interface (header only)
On 20 June 2012 14:38, Andres Freund and...@2ndquadrant.com wrote: It incurs a rather high performance overhead due to added memory allocations and added pointer indirections. Thats fine for most of the current users of the List interface, but certainly not for all. In other places you cannot even have memory allocations because the list lives in shared memory. Yes, in general lists interact horribly with the memory hierarchy. I think I pointed out to you once a rant of mine on -hackers a while back in which I made various points about just how badly they do these days. On modern architectures, with many layers of cache, the cost of the linear search to get an insertion point is very large. So this: /* * removes a node from a list * Attention: O(n) */ static inline void ilist_s_remove(ilist_s_head *head, ilist_s_node *node) is actually even worse than you might suspect. E.g. in the ApplyCache, where I use the submitted ilist.h stuff, when reconstructing transactions you add to a potentially really long linked list of individual changes for every interesting wal record. Before I prevented memory allocations in that path it took about 12-14% of the time when applying changes in the same backend. Afterwards it wasn't visible in the profile anymore. I find that very easy to believe. Several of the pieces of code I pointed out in a previous email use open-coded list implementation exactly to prevent those problems. Interesting. So, it seems like this list implementation could be described as a minimal embeddable list implementation that requires the user to do all the memory allocation, and offers a doubly-linked list too. Not an unreasonable idea. I do think that the constraints you have are not well served by any existing implementation, including List and Dllist. Are you planning on just overhauling the Dllist interface in your next iteration? As to the question of inling, the C99 standard (where inlining is standardised by ANSI, but inspired by earlier extensions to C), unlike the C89 standard, seems to be well respected by vendors as far as it goes, with some compilers going to pains to implement it correctly, like ICC and Clang. We can't really switch to C99, because MSVC doesn't support it, and it is patently obvious that Microsoft have zero interest in it. Funnily enough, if anyone takes C89 as a standard seriously still, it's Microsoft, if only due to indifference to later standards. This hack exists purely for the benefit of their strict interpretation of C89, I think: /* Define to `__inline__' or `__inline' if that's what the C compiler calls it, or to nothing if 'inline' is not supported under any name. */ #ifndef __cplusplus /* #undef inline */ #endif If anyone today is using PostgreSQL binaries in production that were built with a compiler that does not USE_INLINE, I would be very surprised indeed. The idea that anyone intends to build 9.3 with a compiler that doesn't support inline functions is very difficult to believe. Other C open source projects like Linux freely use inline functions. Now, granted, it was only possible to build the kernel for a long time using gcc, but inline had nothing to do with the problem of building the kernel. My point is that broadly it makes more practical sense to talk about GNU C as a standard than C89, and GNU C supports inline functions (C99 is a different matter, but that isn't going to happen in the foreseeable future). Don't believe me? This is from our configure script: # Check if it's Intel's compiler, which (usually) pretends to be gcc, # but has idiosyncrasies of its own. We assume icc will define # __INTEL_COMPILER regardless of CFLAGS. All of the less popular compilers we support we support precisely because they pretend to be GCC, with the sole exception, as always, of the Microsoft product, in this case MSVC. So my position is that I'm in broad agreement that we should freely allow the use of inline without macro hacks, since we generally resists using macro hacks if that makes code ugly, which USE_INLINE certainly does, and for a benefit that is indistinguishable from zero, at least to me. Why are you using the stdlib's assert.h? Why have you used the NDEBUG macro rather than USE_ASSERT_CHECKING? This might make sense if the header was intended to live in port, but it isn't, right? Why have you done this: #ifdef __GNUC__ #define unused_attr __attribute__((unused)) #else #define unused_attr #endif and then gone on to use this unused_attr macro all over the place? Firstly, that isn't going to suppress the warnings on many platforms that we support, and we do make an effort to build warning free on at least 3 compilers these days - GCC, Clang and MSVC. Secondly, compilers give these warnings because it doesn't make any sense to have an unused parameter - so why have you used one? At the very least, if you require this exact interface, use compatibility macros. I can't imagine why
Re: [HACKERS] [PATCH 04/16] Add embedded list interface (header only)
Peter Geoghegan pe...@2ndquadrant.com writes: All of the less popular compilers we support we support precisely because they pretend to be GCC, with the sole exception, as always, of the Microsoft product, in this case MSVC. This is nonsense. There are at least three buildfarm machines running compilers that do not pretend to be gcc (at least, configure recognizes them as not gcc) and are not MSVC either. We ought to have more IMO, because software monocultures are dangerous. Of those three, two pass the quiet inline test and one --- the newest of the three if I guess correctly --- does not. So it is not the case that !USE_INLINE is dead code, even if you adopt the position that we don't care about any compiler not represented in the buildfarm. 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] [PATCH 04/16] Add embedded list interface (header only)
On 22 June 2012 01:04, Tom Lane t...@sss.pgh.pa.us wrote: This is nonsense. There are at least three buildfarm machines running compilers that do not pretend to be gcc (at least, configure recognizes them as not gcc) and are not MSVC either. So those three don't have medium to high degrees of compatibility with GCC? We ought to have more IMO, because software monocultures are dangerous. Of those three, two pass the quiet inline test and one --- the newest of the three if I guess correctly --- does not. So it is not the case that !USE_INLINE is dead code, even if you adopt the position that we don't care about any compiler not represented in the buildfarm. I note that you said that it doesn't pass the quiet inline test, and not that it doesn't support inline functions. -- 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] [PATCH 04/16] Add embedded list interface (header only)
On Wednesday, June 20, 2012 05:01:16 AM Robert Haas wrote: On Tue, Jun 19, 2012 at 4:22 PM, Andres Freund and...@2ndquadrant.com wrote: 1. dllist.h has double the element overhead by having an inline value pointer (which is not needed when embedding) and a pointer to the list (which I have a hard time seing as being useful) 2. only double linked list, mine provided single and double linked ones 3. missing macros to use when embedded in a larger struct (containerof() wrappers and for(...) support basically) 4. most things are external function calls... 5. way much more branches/complexity in most of the functions. My implementation doesn't use any branches for the typical easy modifications (push, pop, remove element somewhere) and only one for the typical tests (empty, has-next, ...) The performance and memory aspects were crucial for the aforementioned toy project (slab allocator for postgres). Its not that crucial for the applycache where the lists currently are mostly used although its also relatively performance sensitive and obviously does a lot of list manipulation/iteration. If I had to decide I would add the missing api in dllist.h to my implementation and then remove it. Its barely used - and only in an embedded fashion - as far as I can see. I can understand though if that argument is met with doubt by others ;). If thats the way it has to go I would add some more convenience support for embedding data to dllist.h and settle for that. I think it might be simpler to leave the name as Dllist and just overhaul the implementation along the lines you suggest, rather than replacing it with something completely different. Mostly, I don't want to add a third thing if we can avoid it, given that Dllist as it exists today is used only lightly. Well, if its the name, I have no problem with changing it, but I don't see how you can keep the api as it currently is and address my points. If there is some buyin I can try to go either way (keeping the existing name, changing the api, adjusting the callers or just adjust the callers, throw away the old implementation) I just don't want to get into that just to see somebody isn't agreeing with the fundamental idea. My guess is that it wouldn't be too hard to remove some of the extra pointers. Anyone who is using Dllist as a non-inline list could be converted to List * instead. There are only three users of the whole dllist.h. Catcache, autovacuum and postmaster. The latter two just keep a list of databases around. So any change will only be moderatively intrusive. Also, the performance-critical things could be reimplemented as macros. I question, though, whether we really need both single and doubly linked lists. That seems like it's almost certainly micro-optimization that we are better off not doing. It was certainly worthwile for the memory manager (lower per allocation overhead). You might be right that its not worth it for many other possible usecases in pg. Its not much code though. *looks around* A quick grep found: single linked list like code: guc_private.h, aset.c, elog.h, regguts.h (ok, irrelevant), dynahash.c, resowner.c, extension.c, pgstat.c, xlog.c Double linked like code: shmqueue.c, lwlock.c, dynahash.c, xact.c I stopped at that point because while surely not of all of the above usecases could be replaced by a common implementation several could from a quick look. Also, several pg_list.h users could benefit from a conversion. So I think adding a single linked list implementation is worthwile. The most contentious point is probably relying on USE_INLINE being available anywhere. Which I believe to be the point now that we have gotten rid of some platforms. I would be hesitant to chuck that even though I realize it's unlikely that we really need !USE_INLINE. But see sortsupport for an example of how we've handled this in the recent past. I agree its possible to resolve this. But hell, do we really need to add all that ugliness in 2012? I don't think its worth the effort of support ancient compilers that don't support inline anymore. If we could stop trying to support catering for probably non-existing compilers we could remove some *very* ugly long macros for example (e.g. in htup.h). If support for !USE_INLINE is required I would prefer to have an header define the functions like #ifdef USE_INLINE #define OPTIONALLY_INLINE static inline #define USE_LINKED_LIST_IMPL #endif #ifdef USE_LINKED_LIST_IMPL OPTIONALLY_INLINE void myFuncCall(){ ... } #endif which then gets included with #define USE_LINKED_LIST_IMPL by some c file defining OPTIONALLY_INLINE to something empty if !USE_INLINE. Its too much code to duplicate imo. Andres -- Andres Freund http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Training Services -- Sent via pgsql-hackers mailing list
Re: [HACKERS] [PATCH 04/16] Add embedded list interface (header only)
On Wed, Jun 20, 2012 at 6:59 AM, Andres Freund and...@2ndquadrant.com wrote: My guess is that it wouldn't be too hard to remove some of the extra pointers. Anyone who is using Dllist as a non-inline list could be converted to List * instead. There are only three users of the whole dllist.h. Catcache, autovacuum and postmaster. The latter two just keep a list of databases around. So any change will only be moderatively intrusive. Yeah. Also, the performance-critical things could be reimplemented as macros. I question, though, whether we really need both single and doubly linked lists. That seems like it's almost certainly micro-optimization that we are better off not doing. It was certainly worthwile for the memory manager (lower per allocation overhead). You might be right that its not worth it for many other possible usecases in pg. Its not much code though. *looks around* A quick grep found: single linked list like code: guc_private.h, aset.c, elog.h, regguts.h (ok, irrelevant), dynahash.c, resowner.c, extension.c, pgstat.c, xlog.c Double linked like code: shmqueue.c, lwlock.c, dynahash.c, xact.c I stopped at that point because while surely not of all of the above usecases could be replaced by a common implementation several could from a quick look. Also, several pg_list.h users could benefit from a conversion. So I think adding a single linked list implementation is worthwile. I can believe that, although I fear it may be a distraction in the grand scheme of getting logical replication implemented. There should be very few places where this is actually performance-critical, and Tom will complain about large amounts of code churn that don't improve performance. If we're going to do that, how about transforming dllist.h into the doubly-linked list and adding sllist.h for the singly-linked list? The most contentious point is probably relying on USE_INLINE being available anywhere. Which I believe to be the point now that we have gotten rid of some platforms. I would be hesitant to chuck that even though I realize it's unlikely that we really need !USE_INLINE. But see sortsupport for an example of how we've handled this in the recent past. I agree its possible to resolve this. But hell, do we really need to add all that ugliness in 2012? I don't think its worth the effort of support ancient compilers that don't support inline anymore. If we could stop trying to support catering for probably non-existing compilers we could remove some *very* ugly long macros for example (e.g. in htup.h). I don't feel qualified to make a decision on this one, so will defer to the opinions of others. If support for !USE_INLINE is required I would prefer to have an header define the functions like #ifdef USE_INLINE #define OPTIONALLY_INLINE static inline #define USE_LINKED_LIST_IMPL #endif #ifdef USE_LINKED_LIST_IMPL OPTIONALLY_INLINE void myFuncCall(){ ... } #endif which then gets included with #define USE_LINKED_LIST_IMPL by some c file defining OPTIONALLY_INLINE to something empty if !USE_INLINE. Its too much code to duplicate imo. Neat trick. Maybe we should revise the sortsupport stuff to do it that way. -- 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] [PATCH 04/16] Add embedded list interface (header only)
On Wednesday, June 20, 2012 02:51:30 PM Robert Haas wrote: On Wed, Jun 20, 2012 at 6:59 AM, Andres Freund and...@2ndquadrant.com wrote: Also, the performance-critical things could be reimplemented as macros. I question, though, whether we really need both single and doubly linked lists. That seems like it's almost certainly micro-optimization that we are better off not doing. It was certainly worthwile for the memory manager (lower per allocation overhead). You might be right that its not worth it for many other possible usecases in pg. Its not much code though. *looks around* A quick grep found: single linked list like code: guc_private.h, aset.c, elog.h, regguts.h (ok, irrelevant), dynahash.c, resowner.c, extension.c, pgstat.c, xlog.c Double linked like code: shmqueue.c, lwlock.c, dynahash.c, xact.c I stopped at that point because while surely not of all of the above usecases could be replaced by a common implementation several could from a quick look. Also, several pg_list.h users could benefit from a conversion. So I think adding a single linked list implementation is worthwile. I can believe that, although I fear it may be a distraction in the grand scheme of getting logical replication implemented. There should be very few places where this is actually performance-critical, and Tom will complain about large amounts of code churn that don't improve performance. Uh. I don't want to just go around and replace anything randomly. Actually I don't want to change anything for now except whats necessary to get the patch in. The point I tried to make was just that the relatively widespread usage of similar structure make it likely that it can be used in more places in future. If we're going to do that, how about transforming dllist.h into the doubly-linked list and adding sllist.h for the singly-linked list? I would be fine with that. I will go and try to cook up a patch, assuming for now that we rely on inline, the ugliness can be added back afterwards. The most contentious point is probably relying on USE_INLINE being available anywhere. Which I believe to be the point now that we have gotten rid of some platforms. I would be hesitant to chuck that even though I realize it's unlikely that we really need !USE_INLINE. But see sortsupport for an example of how we've handled this in the recent past. I agree its possible to resolve this. But hell, do we really need to add all that ugliness in 2012? I don't think its worth the effort of support ancient compilers that don't support inline anymore. If we could stop trying to support catering for probably non-existing compilers we could remove some *very* ugly long macros for example (e.g. in htup.h). I don't feel qualified to make a decision on this one, so will defer to the opinions of others. Ok. If support for !USE_INLINE is required I would prefer to have an header define the functions like #ifdef USE_INLINE #define OPTIONALLY_INLINE static inline #define USE_LINKED_LIST_IMPL #endif #ifdef USE_LINKED_LIST_IMPL OPTIONALLY_INLINE void myFuncCall(){ ... } #endif which then gets included with #define USE_LINKED_LIST_IMPL by some c file defining OPTIONALLY_INLINE to something empty if !USE_INLINE. Its too much code to duplicate imo. Neat trick. Maybe we should revise the sortsupport stuff to do it that way. Either that or at least add a comment to both that its duplicated... 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] [PATCH 04/16] Add embedded list interface (header only)
On Wed, Jun 20, 2012 at 9:12 AM, Andres Freund and...@2ndquadrant.com wrote: Uh. I don't want to just go around and replace anything randomly. Actually I don't want to change anything for now except whats necessary to get the patch in. The point I tried to make was just that the relatively widespread usage of similar structure make it likely that it can be used in more places in future. Well, the question is for anywhere you might be thinking of using this: why not just use List? We do that in a lot of other places, and there's not much reason to event something new unless there is a problem with what we already have. I assume this is related to logical replication somehow, but it's not clear to me exactly what problem you hit doing this in the obvious way. -- 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] [PATCH 04/16] Add embedded list interface (header only)
On Wednesday, June 20, 2012 03:24:58 PM Robert Haas wrote: On Wed, Jun 20, 2012 at 9:12 AM, Andres Freund and...@2ndquadrant.com wrote: Uh. I don't want to just go around and replace anything randomly. Actually I don't want to change anything for now except whats necessary to get the patch in. The point I tried to make was just that the relatively widespread usage of similar structure make it likely that it can be used in more places in future. Well, the question is for anywhere you might be thinking of using this: why not just use List? We do that in a lot of other places, and there's not much reason to event something new unless there is a problem with what we already have. I assume this is related to logical replication somehow, but it's not clear to me exactly what problem you hit doing this in the obvious way. It incurs a rather high performance overhead due to added memory allocations and added pointer indirections. Thats fine for most of the current users of the List interface, but certainly not for all. In other places you cannot even have memory allocations because the list lives in shared memory. E.g. in the ApplyCache, where I use the submitted ilist.h stuff, when reconstructing transactions you add to a potentially really long linked list of individual changes for every interesting wal record. Before I prevented memory allocations in that path it took about 12-14% of the time when applying changes in the same backend. Afterwards it wasn't visible in the profile anymore. Several of the pieces of code I pointed out in a previous email use open-coded list implementation exactly to prevent those problems. If you look at the parsing, planning execution of trivial statements you will also notice the overhead of memory allocations. A good bit of those is caused by list manipulation. Check Stephen Frost's Pre-alloc ListCell's optimization for workarounds.. 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] [PATCH 04/16] Add embedded list interface (header only)
On Wed, Jun 13, 2012 at 7:28 AM, Andres Freund and...@2ndquadrant.com wrote: Adds a single and a double linked list which can easily embedded into other datastructures and can be used without any additional allocations. dllist.h advertises that it's embeddable. Can you use that instead, or enhance it slightly to support what you want to do? -- 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] [PATCH 04/16] Add embedded list interface (header only)
On Tuesday, June 19, 2012 09:16:41 PM Robert Haas wrote: On Wed, Jun 13, 2012 at 7:28 AM, Andres Freund and...@2ndquadrant.com wrote: Adds a single and a double linked list which can easily embedded into other datastructures and can be used without any additional allocations. dllist.h advertises that it's embeddable. Can you use that instead, or enhance it slightly to support what you want to do? Oh, wow. Didn't know that existed. I had $subject lying around from a play- around project, so I didn't look too hard. Why is that code not used more widely? Quite a bit of our list usage should be replaced embedding list element in larger structs imo. There are also open- coded inline list manipulations around (check aset.c for example). *looks* Not really that happy with it though: 1. dllist.h has double the element overhead by having an inline value pointer (which is not needed when embedding) and a pointer to the list (which I have a hard time seing as being useful) 2. only double linked list, mine provided single and double linked ones 3. missing macros to use when embedded in a larger struct (containerof() wrappers and for(...) support basically) 4. most things are external function calls... 5. way much more branches/complexity in most of the functions. My implementation doesn't use any branches for the typical easy modifications (push, pop, remove element somewhere) and only one for the typical tests (empty, has-next, ...) The performance and memory aspects were crucial for the aforementioned toy project (slab allocator for postgres). Its not that crucial for the applycache where the lists currently are mostly used although its also relatively performance sensitive and obviously does a lot of list manipulation/iteration. If I had to decide I would add the missing api in dllist.h to my implementation and then remove it. Its barely used - and only in an embedded fashion - as far as I can see. I can understand though if that argument is met with doubt by others ;). If thats the way it has to go I would add some more convenience support for embedding data to dllist.h and settle for that. 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] [PATCH 04/16] Add embedded list interface (header only)
On Tue, Jun 19, 2012 at 3:48 PM, Andres Freund and...@2ndquadrant.com wrote: Why is that code not used more widely? Quite a bit of our list usage should be replaced embedding list element in larger structs imo. There are also open- coded inline list manipulations around (check aset.c for example). Because we've got a million+ lines of code and nobody knows where all the bodies are buried. 1. dllist.h has double the element overhead by having an inline value pointer (which is not needed when embedding) and a pointer to the list (which I have a hard time seing as being useful) 2. only double linked list, mine provided single and double linked ones 3. missing macros to use when embedded in a larger struct (containerof() wrappers and for(...) support basically) 4. most things are external function calls... 5. way much more branches/complexity in most of the functions. My implementation doesn't use any branches for the typical easy modifications (push, pop, remove element somewhere) and only one for the typical tests (empty, has-next, ...) The performance and memory aspects were crucial for the aforementioned toy project (slab allocator for postgres). Its not that crucial for the applycache where the lists currently are mostly used although its also relatively performance sensitive and obviously does a lot of list manipulation/iteration. If I had to decide I would add the missing api in dllist.h to my implementation and then remove it. Its barely used - and only in an embedded fashion - as far as I can see. I can understand though if that argument is met with doubt by others ;). If thats the way it has to go I would add some more convenience support for embedding data to dllist.h and settle for that. I think it might be simpler to leave the name as Dllist and just overhaul the implementation along the lines you suggest, rather than replacing it with something completely different. Mostly, I don't want to add a third thing if we can avoid it, given that Dllist as it exists today is used only lightly. -- 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] [PATCH 04/16] Add embedded list interface (header only)
On Wed, Jun 13, 2012 at 2:28 PM, Andres Freund and...@2ndquadrant.com wrote: +/* + * removes a node from a list + * Attention: O(n) + */ +static inline void ilist_s_remove(ilist_s_head *head, + ilist_s_node *node) +{ + ilist_s_node *last = head-head; + ilist_s_node *cur; +#ifndef NDEBUG + bool found = false; +#endif + while ((cur = last-next)) + { + if (cur == node) + { + last-next = cur-next; +#ifndef NDEBUG + found = true; +#endif + break; + } + last = cur; + } + assert(found); +} This looks weird. In cyclic list removal is: node-prev-next = node-next; node-next-prev = node-prev; And thats it. -- marko -- 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] [PATCH 04/16] Add embedded list interface (header only)
Hi, On Tuesday, June 19, 2012 09:59:48 PM Marko Kreen wrote: On Wed, Jun 13, 2012 at 2:28 PM, Andres Freund and...@2ndquadrant.com wrote: +/* + * removes a node from a list + * Attention: O(n) + */ +static inline void ilist_s_remove(ilist_s_head *head, + ilist_s_node *node) +{ + ilist_s_node *last = head-head; + ilist_s_node *cur; +#ifndef NDEBUG + bool found = false; +#endif + while ((cur = last-next)) + { + if (cur == node) + { + last-next = cur-next; +#ifndef NDEBUG + found = true; +#endif + break; + } + last = cur; + } + assert(found); +} This looks weird. In cyclic list removal is: node-prev-next = node-next; node-next-prev = node-prev; And thats it. Thats the single linked list, not the double linked one. Thats why it has a O(n) warning tacked on... The double linked one is just as you said: /* * removes a node from a list */ static inline void ilist_d_remove(unused_attr ilist_d_head *head, ilist_d_node *node) { ilist_d_check(head); node-prev-next = node-next; node-next-prev = node-prev; ilist_d_check(head); } 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] [PATCH 04/16] Add embedded list interface (header only)
On Tue, Jun 19, 2012 at 11:02 PM, Andres Freund and...@2ndquadrant.com wrote: On Tuesday, June 19, 2012 09:59:48 PM Marko Kreen wrote: On Wed, Jun 13, 2012 at 2:28 PM, Andres Freund and...@2ndquadrant.com wrote: +/* + * removes a node from a list + * Attention: O(n) + */ +static inline void ilist_s_remove(ilist_s_head *head, + ilist_s_node *node) +{ + ilist_s_node *last = head-head; + ilist_s_node *cur; +#ifndef NDEBUG + bool found = false; +#endif + while ((cur = last-next)) + { + if (cur == node) + { + last-next = cur-next; +#ifndef NDEBUG + found = true; +#endif + break; + } + last = cur; + } + assert(found); +} This looks weird. In cyclic list removal is: node-prev-next = node-next; node-next-prev = node-prev; And thats it. Thats the single linked list, not the double linked one. Thats why it has a O(n) warning tacked on... Oh, you have several list implementations there. Sorry, I was just browsing and it caught my eye. -- marko -- 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] [PATCH 04/16] Add embedded list interface (header only)
On Tuesday, June 19, 2012 09:58:43 PM Robert Haas wrote: On Tue, Jun 19, 2012 at 3:48 PM, Andres Freund and...@2ndquadrant.com wrote: Why is that code not used more widely? Quite a bit of our list usage should be replaced embedding list element in larger structs imo. There are also open- coded inline list manipulations around (check aset.c for example). Because we've got a million+ lines of code and nobody knows where all the bodies are buried. Heh, yes ;). Ive hit several times as you uncovered at least twice ;) 1. dllist.h has double the element overhead by having an inline value pointer (which is not needed when embedding) and a pointer to the list (which I have a hard time seing as being useful) 2. only double linked list, mine provided single and double linked ones 3. missing macros to use when embedded in a larger struct (containerof() wrappers and for(...) support basically) 4. most things are external function calls... 5. way much more branches/complexity in most of the functions. My implementation doesn't use any branches for the typical easy modifications (push, pop, remove element somewhere) and only one for the typical tests (empty, has-next, ...) The performance and memory aspects were crucial for the aforementioned toy project (slab allocator for postgres). Its not that crucial for the applycache where the lists currently are mostly used although its also relatively performance sensitive and obviously does a lot of list manipulation/iteration. If I had to decide I would add the missing api in dllist.h to my implementation and then remove it. Its barely used - and only in an embedded fashion - as far as I can see. I can understand though if that argument is met with doubt by others ;). If thats the way it has to go I would add some more convenience support for embedding data to dllist.h and settle for that. I think it might be simpler to leave the name as Dllist and just overhaul the implementation along the lines you suggest, rather than replacing it with something completely different. Mostly, I don't want to add a third thing if we can avoid it, given that Dllist as it exists today is used only lightly. Well, if its the name, I have no problem with changing it, but I don't see how you can keep the api as it currently is and address my points. If there is some buyin I can try to go either way (keeping the existing name, changing the api, adjusting the callers or just adjust the callers, throw away the old implementation) I just don't want to get into that just to see somebody isn't agreeing with the fundamental idea. The most contentious point is probably relying on USE_INLINE being available anywhere. Which I believe to be the point now that we have gotten rid of some platforms. 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] [PATCH 04/16] Add embedded list interface (header only)
On Tue, Jun 19, 2012 at 4:22 PM, Andres Freund and...@2ndquadrant.com wrote: 1. dllist.h has double the element overhead by having an inline value pointer (which is not needed when embedding) and a pointer to the list (which I have a hard time seing as being useful) 2. only double linked list, mine provided single and double linked ones 3. missing macros to use when embedded in a larger struct (containerof() wrappers and for(...) support basically) 4. most things are external function calls... 5. way much more branches/complexity in most of the functions. My implementation doesn't use any branches for the typical easy modifications (push, pop, remove element somewhere) and only one for the typical tests (empty, has-next, ...) The performance and memory aspects were crucial for the aforementioned toy project (slab allocator for postgres). Its not that crucial for the applycache where the lists currently are mostly used although its also relatively performance sensitive and obviously does a lot of list manipulation/iteration. If I had to decide I would add the missing api in dllist.h to my implementation and then remove it. Its barely used - and only in an embedded fashion - as far as I can see. I can understand though if that argument is met with doubt by others ;). If thats the way it has to go I would add some more convenience support for embedding data to dllist.h and settle for that. I think it might be simpler to leave the name as Dllist and just overhaul the implementation along the lines you suggest, rather than replacing it with something completely different. Mostly, I don't want to add a third thing if we can avoid it, given that Dllist as it exists today is used only lightly. Well, if its the name, I have no problem with changing it, but I don't see how you can keep the api as it currently is and address my points. If there is some buyin I can try to go either way (keeping the existing name, changing the api, adjusting the callers or just adjust the callers, throw away the old implementation) I just don't want to get into that just to see somebody isn't agreeing with the fundamental idea. My guess is that it wouldn't be too hard to remove some of the extra pointers. Anyone who is using Dllist as a non-inline list could be converted to List * instead. Also, the performance-critical things could be reimplemented as macros. I question, though, whether we really need both single and doubly linked lists. That seems like it's almost certainly micro-optimization that we are better off not doing. The most contentious point is probably relying on USE_INLINE being available anywhere. Which I believe to be the point now that we have gotten rid of some platforms. I would be hesitant to chuck that even though I realize it's unlikely that we really need !USE_INLINE. But see sortsupport for an example of how we've handled this in the recent past. -- 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