Hi, On Sunday, September 30, 2012 10:33:28 PM Tom Lane wrote: > Andres Freund <and...@2ndquadrant.com> 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