Re: embedded list v3

On Monday, October 01, 2012 05:33:01 PM Tom Lane wrote:
> Andres Freund <andres(at)2ndquadrant(dot)com> 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