Re: equal() perf tweak

Gaetano Mendola <mendola(at)bigfoot(dot)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