Re: Singly Linked List in C

From: Ian Woods (newspub2_at_wuggyNOCAPS.org)
Date: 10/28/03 

Date: Tue, 28 Oct 2003 22:18:56 +0000 (UTC)

Calum <calum.bulk@ntlworld.com> wrote in
news:bnmn64$j1k$1@newsg2.svr.pol.co.uk:

> Ian Woods wrote:

<stuff about the xored pointer trick to get pseudo-doubly linked lists
being completely unncessary>

>>>
>>>Saving a pointer per node is completely unnecessary? Often, yes,
>>>overoptimization is counterproductive. But not always.
>>
>>
>> It's not much of an optimisation. The only case for it that I can see
>> is for programs running on systems where memory is very tight, but
>> even that's a weak one. You can achieve a greater increase in memory
>> saving using other techniques more easilly.
>
> Bear in mind, it is not my invention before I take the discredit for
> it.

My intention wasn't to discredit you - but to highlight to others that
the technique is not without problems. My apologies if I've come across
that way.

> But in this particular example it would save 50%/33% of the memory
> size, which I think is significant. There are plenty of little
> gadgets with limited memory, and of course running times on modern
> processors is defined by how well the data fits into the L1 or L2
> cache. Memory bandwidth is more of a bottleneck than processor
> bandwidth.

Surely other techniques get you even greater gains, and in a way that the
XOR technique can be applied - in ANSI C - without relying on
implimentation defined behaviour.

There are a few things which occur to me:

Using dynamic memory allocation functions requires there to be some data
stored for internal housekeeping (64 bits per allocated block on most 32
bit platforms I imagine). You can reduce the amount of housekeeping by
allocating a block of nodes as a flat array and use indexes instead of
pointers. If your linked list nodes are 64 bits in size themselves, this
alone could save you almost 50%.

Pointers generally have a range much larger than is necessary to index
the available memory. Why not use a type just large enough? Just dropping
2 bytes of the index of a list node with 32 bits of data and 32 bits of
'next' is a saving of 25%.

If your indices are unsigned int (or even just arrays of chars which you
'unpack' into an unsigned int), you can use a relation like the XOR
technique without any issues whatsoever since there's no pointers
involved. The benefit is the same, you get the ability to walk forwards
and backwards through the list using only a single index value.

>From here there are still plenty of things which can be done, but they
get stranger. :) I'll stop here.
 
Ian Woods

Relevant Pages

  • Re: A modern way to solve the "callback problem" from a subroutine?
    ... Many Fortran "tricks" are based on how to use that memory within ... pointers allow more efficient memory usage. ... if linked lists are so overwhelmingly beneficial, ... that the system supplies a pointer to the data in the input buffer ...
    (comp.lang.fortran)
  • Re: How to allocate memory for a linked list of pointers in a kernel process
    ... are you sure you access memory at proper ... lists using pointers of course. ... When the kernel routines need to allocate a ... Are you aware that the kernel contains routines to do doubly linked lists ...
    (microsoft.public.win32.programmer.kernel)
  • Re: Problem with offset based linked list
    ... offset's instead on pointers to store the linked list in the shared ... Shared memory is not guaranteed to be at the same address in all process ... That's the reason why one needs to use offsets in place of pointers ... when having linked lists in the shared memory? ...
    (comp.lang.c)
  • Re: void pointers
    ... > I have two different linked lists that each use nodes of different ... structs might be different. ... instead of using container nodes with pointers to your ... there is no need to allocate/free memory for the container nodes. ...
    (comp.lang.c)
  • Re: Is this math test too easy?
    ... communications glitch; one of the more laughable cartoons ... (A note on "in memory", which for virtual memory machines can get ... Or one can interpret the character string as one of the values ... DOS allowed NULL pointers; the value was in fact interpreted as ...
    (sci.math)