Re: list optimization

From: The Real OS/2 Guy (os2guy_at_pc-rosenau.de)
Date: 10/29/03 

Date: Wed, 29 Oct 2003 10:24:08 +0000 (UTC)

On Tue, 28 Oct 2003 14:12:09 UTC, evangeli@cnam.fr (Evangelista Sami)
wrote:

> "The Real OS/2 Guy" <os2guy@pc-rosenau.de> wrote in message news:<wmzsGguTDN6N-pn2-gyr4P8EY0fCk@moon>...
> > On Mon, 27 Oct 2003 14:44:34 UTC, evangeli@cnam.fr (Evangelista Sami)
> > wrote:
> >
> > > Hi all
> > >
> > > i have implemented a list type as an array of pointer like this
> > >
> > > typedef struct {
> > > int nb_elements;
> > > void **elements;
> > > } list;
> > >
> > > to avoid having a pointer for each element as it is done with a recursive
> > > definition.
> > >
> >
> > Use simply either a linked list or a tree.
> >
> > A linket list would contain a single node and points to the next one
> > like
> >
> > struct list {
> > struct list *pNext;
> > /* any kind of data follows here, e.g.: */
> > int flags;
> > char *name; /* a pointer because names are different in lengh */
> > /* must be malloced separately but saves amount of
> > memory */
> > char postalcode[6]; /* string with almost fixed length */
>
> > ......
> > } list;
> >
> > So when you needs a new member of the list you would simply malloc()
> > one member and insert it anywhere in the list. No need to copy
> > anything around (except the data for that single element.
> >
> > If you have a high freyuence in inserting/removing accessing single
> > elements in unspecified order it would be a good idea to have them
> > listed as tree because this will shorten the access time when you have
> > to search it.
> >
> > struct tree {
> > struct tree *pNext; /* greater than the current */
> > struct tree *pPre; /* lower than the current */
> > /* any data gets here */
> > } tree;
>
>
> hi
> thanks for all your responses
>
> the problem with your solution is that it takes a pointer for each
> element of my list. so the total size of your solution for a list of N
> elements is
> N * (sizeof(list *) + sizeof(element)) :
>
> whereas the array solution "only" takes :
> N * (sizeof(element)) + sizeof(int)
>
> As far as my first goal is to save as much memory as possible i prefer
> the array solution.
>
> any idea?

As you have the need of dynamic memory allocation AND the problem that
realloc can be really time expansive AND you needs to save pointers
you may simple use a compromise of using an array and pointers between
the structs.

e.g.:

struct address {
  struct address *pNext
  struct address *pPre;
  size_t cb; /* count the number of used entries */
  struct {
     char *name; /* instead of name[35] */
     char *address1; /* instead of address1[35] */
     char *address2; /* and so on */
     ....
  } member[1000];
} addresses;

Holds up to 1000 addresses in one block. When this block is full
another block of 1000 addresses gets allocated.....

Using pointers for the true data helps to reduce the memory usage
because the same name - but with different addresses needs only ONE
string that holds the name, different names but same address 1 or 2
.... saves more memory because each string exists only once but has
multiple pointers to it. When you defines the space a field needs you
have to define the maximum size - even as the middle will only use the
half. Having a pointer to an dynamic allocated string will save space
- and if the same string can occure multiple times in the whole list
you can compact it more by using the same string again.

But consider that this solution costs a lot more of code that needs to
be debugged! Holding things a bit simple. Here use a single element of
data and spend a pointer for each is better, even as the memory usage
increases. This ends up with a big amount of allocated memory unused.
Look what you get when you have 10001 addresses. You've allocated 2
times 1000 ones! When you have each record separately you saves 999 *
the size of a record - but yes, you'll spend 1000 * sizeof(pointer to
struct) extra.

Having the records separately makes it easy to sort them in many cases
without copying they around, because sorting them by its pointers is
much quicker. Sorted insert reduces runtime too. 

-- 
Tschau/Bye
Herbert
eComStation 1.1 Deutsch wird jetzt ausgeliefert!

Relevant Pages

  • Re: Is this string input function safe?
    ... return a pointer to mallocated memory holding one input string, ... complains about use of deallocated pointers, ... mallocating an appropriate amount of memory. ... the contents of the buffer are indeterminate (for different ...
    (comp.lang.c)
  • Re: get text from listbox
    ... The first character is the low byte of the low word of the DWORD item data ... addressing memory in a virtual address space of 2 GB (memory allocation ... To prove that these are pointers get the item data of the list items as ... string pointer; check it by reading some bytes from the memory to which the ...
    (microsoft.public.vb.winapi)
  • Re: Pointer of Struct
    ... Right now you have a struct with two pointers that point to string data. ... When I try to run this Code as a Windows Desktop Application it runs ...
    (microsoft.public.pocketpc.developer)
  • Re: std::map question
    ... If you are allocating memory dyanmically and it is possible for exceptions ... is an object that is responsible for managing the memory. ... Also, reference counted pointers can provide other benefits, ... especially when you consider that the string is probably managing ...
    (comp.lang.cpp)
  • Re: fscanf issues, please help.
    ... those pointers point to strings of whatever length. ... An array of pointers is an array of pointer, ... they pont to some random places in memory. ... be an integer, the next one a string, followed by a hash etc., ...
    (comp.lang.c)