Gaetano Mendola <mendola@bigfoot.com> writes:
> [ use list with master node and circular linking ]
> now is very late here ( 04:17 AM ) so I wrote
> the wrong code ( not checked ) but show the idea of
> avoid "if".
This saves an "if" during addition of a list item, at the cost of
greater expense during list traversal. (Instead of a loop termination
test like "ptr != NULL", you need something like "ptr != master_node".
This may not take an extra cycle, but only if you can afford to dedicate
a register to holding the value of master_node within the loop. That
hurts, especially on architectures with not very many registers.)
Offhand I do not see a win here. Node addition implies a palloc which
means you are going to be jumping control all over the place anyway;
there's no way that eliminating one "if" in that path of control is
going to be a meaningful improvement. Saving a cycle or two during list
traversal could be a meaningful improvement, though.
By the same token, keeping a length count in the master node might be a
waste of cycles, but it's going to be a pretty tiny waste compared to
the other overhead of adding or removing a node. The potential savings
from making length() be a constant-time operation seem like a win to me.
Anyway, we should build the code that way and then do profiling with and
without support for constant-cost length().
regards, tom lane