[ntp:hackers] singly-linked list template macros for NTP

Dave Hart davehart at gmail.com
Tue Jul 14 05:28:14 UTC 2009


On Tue, Jul 14, 2009 at 3:18 AM, Danny Mayer wrote:
> Singly-linked lists are not simpler or faster and
> has the amount of memory used by doubly linked lists is negligible.

The extra storage for previous and tail pointers isn't negligible,
it's twice the size compared to singly-linked.  Far more interesting
is the size of the code to manipulate the lists.  I decided to take a
look at the impact of switching from doubly-linked to singly-linked
lists in my environment.  I chose set_peerdstadr() as it contains one
of each of the interesting cases, inserting/linking and
deleting/unlinking.  Since my patch is against 4.2.5p185 I looked at
that function in a Windows nodebug p185, compared with one built with
the singly-linked macros.  See:

http://davehart.net/ntp/linkedlists/set_peerdstadr-doubly-disasm.txt
http://davehart.net/ntp/linkedlists/set_peerdstadr-singly-disasm.txt

Summary: 308 octets vs 234.  Singly-linked function is 24% smaller, or
from the other perspective, the doubly-linked version is 32% bigger.
I think that's out of the noise range and qualifies as both simpler
and faster.

Cheers,
Dave Hart


More information about the hackers mailing list