memory optimization

[Evangelista Sami]

hello all

i am implementing an application in which a large number of (char *)
is stored into a hash table structure.
As there may be collisions, each (char *) inserted into my hash table
is put into an array. here is the definition of my hash table :

typedef struct
{
short size;
char **elements;
} hash_cell;
hash_cell hash_table[100000];

with this approach, each time i want to store an additional (char *) i
reallocate the array elements and add it an additional element.
this works fine but i have an overhead of a (char *) per element.

Another idea is to use a single (char *) by cell in the hash table and
to encode the size of each (char *) in this one with for instance 16
bits. the definition of this hash table should be :

typedef struct
{
short size;
char *elements;
} hash_cell;
hash_cell hash_table[100000];

For example if in the cell 0 i have three elements "toto", "abc", and
"peter",
i will have :
hash_table[0].elements[0 .. 1] = 4
hash_table[0].elements[2 .. 5] = "toto"
hash_table[0].elements[6 .. 7] = 3
hash_table[0].elements[8 .. 10] = "abc"
hash_table[0].elements[11 .. 12] = 3
hash_table[0].elements[13 .. 17] = "peter"

this makes me save 4 - 2 = 2 bytes if i assume that the size of (char
*) is 4 bytes and that the length of each element is encoded with 2
bytes.

However when i make the "ps aux" command during the execution, it
appears that the whole memory consumed by the first method is less
than with the second method and i cant see why.

Any explanation would be very useful

Sami Evangelista

[Eric Sosman]

Evangelista Sami wrote:

hello all

i am implementing an application in which a large number of (char *)
is stored into a hash table structure.
As there may be collisions, each (char *) inserted into my hash table
is put into an array. here is the definition of my hash table :

typedef struct
{
short size;
char **elements;
} hash_cell;
hash_cell hash_table[100000];

with this approach, each time i want to store an additional (char *) i
reallocate the array elements and add it an additional element.
this works fine but i have an overhead of a (char *) per element.
You haven't said so, but I'll assume that each `char*' points
to the start of a '\0'-terminated C string and not to a completely
arbitrary chunk of data.
Another idea is to use a single (char *) by cell in the hash table and
to encode the size of each (char *) in this one with for instance 16
bits.
The "size of each (char *)" is constant for any given
implementation. I'll assume that what you actually want to
do is encode the lengths of the C strings -- but using two
bytes to encode the information already provided by the one-
byte '\0' terminator seems a poor trade-off ...
the definition of this hash table should be :

typedef struct
{
short size;
char *elements;
} hash_cell;
hash_cell hash_table[100000];

For example if in the cell 0 i have three elements "toto", "abc", and
"peter",
i will have :
hash_table[0].elements[0 .. 1] = 4
hash_table[0].elements[2 .. 5] = "toto"
hash_table[0].elements[6 .. 7] = 3
hash_table[0].elements[8 .. 10] = "abc"
hash_table[0].elements[11 .. 12] = 3
hash_table[0].elements[13 .. 17] = "peter"

this makes me save 4 - 2 = 2 bytes if i assume that the size of (char
*) is 4 bytes and that the length of each element is encoded with 2
bytes.
Well, let's see. For each string you've discarded one '\0'
byte and added two length bytes, then discarded one `char*'. If
`sizeof(char*)' is four, the net savings is three bytes per string.
However when i make the "ps aux" command during the execution, it
appears that the whole memory consumed by the first method is less
than with the second method and i cant see why.
Some of what follows is speculation: The C language Standard
says nothing about how realloc() and friends are implemented, and
different versions behave differently. Still, a few things stand
out:

In the first version the three strings "toto", "abc", and
"peter" are stored somewhere in memory, along with their trailing
'\0' bytes -- that's fifteen bytes, if I've counted correctly.
To this you add three `char*' pointers (assumed to be four bytes
each, but that's not guaranteed), plus some unknown amount of
memory-management overhead for the `hash_table[n].elements'
array. If the overhead is eight bytes (again, not guaranteed),
the total is thirty-five bytes.

In the second version you *still* have the three strings
"toto", "abc", and "peter" lying around in memory someplace,
and you've made copies of them so you can make the copies
adjacent to one another and interleave them with the lengths.
So: fifteen bytes of original data, twelve more for the copies
(omitting the '\0' terminators), six more for the lengths, and
a presumed eight-byte overhead for the dynamic array. That's
forty-one bytes, six more than the first method used.

You have saved three bytes per string at the cost of making
a duplicate copy of the string's data. If the string is longer
than three bytes, this is a poor trade. (If the strings are
all three bytes long or less, you could use a much more efficient
data structure than a hash table!)
Any explanation would be very useful

Another effect to consider is the operation of realloc().
The first method reallocates small arrays of `char*', while
the second reallocates larger (presumably) arrays of string
data interleaved with lengths. Now, how do you suppose the
realloc() function works its magic? Details differ, but in
typical implementations realloc() will first try to see if
there's enough unused memory immediately following the array
you're resizing, and if so it will simply "claim" that memory
and return the same pointer it was given. If not, it will do
the equivalent of a malloc() of the new size, then copy the
pre-existing data from the old region to the new, and finally
free() the old region and return a pointer to the new. (Again
I emphasize that not all implementations behave this way, but
this is a typical strategy.)

Now, what happens to the old region after it's released?
It becomes available for future allocations -- but note that
your `char*' arrays or concatenated strings are always growing,
never shrinking. The released areas are likely to be too small
to satisfy future allocations, unless you get lucky and happen
to release an abutting region as well. The next malloc() or
realloc() *might* be able to re-use one of these "fragments,"
but it's more likely to need to claim some brand-new memory
because the fragments tend to be too small. And in your second
method the amount of data you're reallocating is probably larger,
so the useless fragments are also larger, the brand-new claimed
areas are larger, and the total memory used is larger.

As I say, lots of speculation. Your mileage may vary.

--
Er*********@sun.com

[Evangelista Sami]

Eric Sosman <Er*********@sun.com> wrote in message news:<40**************@sun.com>...

Evangelista Sami wrote:

hello all

i am implementing an application in which a large number of (char *)
is stored into a hash table structure.
As there may be collisions, each (char *) inserted into my hash table
is put into an array. here is the definition of my hash table :

typedef struct
{
short size;
char **elements;
} hash_cell;
hash_cell hash_table[100000];

with this approach, each time i want to store an additional (char *) i
reallocate the array elements and add it an additional element.
this works fine but i have an overhead of a (char *) per element.

You haven't said so, but I'll assume that each `char*' points
to the start of a '\0'-terminated C string and not to a completely
arbitrary chunk of data.

Another idea is to use a single (char *) by cell in the hash table and
to encode the size of each (char *) in this one with for instance 16
bits.

The "size of each (char *)" is constant for any given
implementation. I'll assume that what you actually want to
do is encode the lengths of the C strings -- but using two
bytes to encode the information already provided by the one-
byte '\0' terminator seems a poor trade-off ...

i may have '\0' in my strings so i can't use to indicate the end of the string

the definition of this hash table should be :

typedef struct
{
short size;
char *elements;
} hash_cell;
hash_cell hash_table[100000];

For example if in the cell 0 i have three elements "toto", "abc", and
"peter",
i will have :
hash_table[0].elements[0 .. 1] = 4
hash_table[0].elements[2 .. 5] = "toto"
hash_table[0].elements[6 .. 7] = 3
hash_table[0].elements[8 .. 10] = "abc"
hash_table[0].elements[11 .. 12] = 3
hash_table[0].elements[13 .. 17] = "peter"

this makes me save 4 - 2 = 2 bytes if i assume that the size of (char
*) is 4 bytes and that the length of each element is encoded with 2
bytes.

Well, let's see. For each string you've discarded one '\0'
byte and added two length bytes, then discarded one `char*'. If
`sizeof(char*)' is four, the net savings is three bytes per string.

However when i make the "ps aux" command during the execution, it
appears that the whole memory consumed by the first method is less
than with the second method and i cant see why.

Some of what follows is speculation: The C language Standard
says nothing about how realloc() and friends are implemented, and
different versions behave differently. Still, a few things stand
out:

In the first version the three strings "toto", "abc", and
"peter" are stored somewhere in memory, along with their trailing
'\0' bytes -- that's fifteen bytes, if I've counted correctly.
To this you add three `char*' pointers (assumed to be four bytes
each, but that's not guaranteed), plus some unknown amount of
memory-management overhead for the `hash_table[n].elements'
array. If the overhead is eight bytes (again, not guaranteed),
the total is thirty-five bytes.

In the second version you *still* have the three strings
"toto", "abc", and "peter" lying around in memory someplace,
and you've made copies of them so you can make the copies
adjacent to one another and interleave them with the lengths.
So: fifteen bytes of original data, twelve more for the copies
(omitting the '\0' terminators), six more for the lengths, and
a presumed eight-byte overhead for the dynamic array. That's
forty-one bytes, six more than the first method used.

You have saved three bytes per string at the cost of making
a duplicate copy of the string's data. If the string is longer
than three bytes, this is a poor trade. (If the strings are
all three bytes long or less, you could use a much more efficient
data structure than a hash table!)

what structure for example ?

Any explanation would be very useful

Another effect to consider is the operation of realloc().
The first method reallocates small arrays of `char*', while
the second reallocates larger (presumably) arrays of string
data interleaved with lengths. Now, how do you suppose the
realloc() function works its magic? Details differ, but in
typical implementations realloc() will first try to see if
there's enough unused memory immediately following the array
you're resizing, and if so it will simply "claim" that memory
and return the same pointer it was given. If not, it will do
the equivalent of a malloc() of the new size, then copy the
pre-existing data from the old region to the new, and finally
free() the old region and return a pointer to the new. (Again
I emphasize that not all implementations behave this way, but
this is a typical strategy.)

Now, what happens to the old region after it's released?
It becomes available for future allocations -- but note that
your `char*' arrays or concatenated strings are always growing,
never shrinking. The released areas are likely to be too small
to satisfy future allocations, unless you get lucky and happen
to release an abutting region as well. The next malloc() or
realloc() *might* be able to re-use one of these "fragments,"
but it's more likely to need to claim some brand-new memory
because the fragments tend to be too small. And in your second
method the amount of data you're reallocating is probably larger,
so the useless fragments are also larger, the brand-new claimed
areas are larger, and the total memory used is larger.

As I say, lots of speculation. Your mileage may vary.

[David Resnick]

ev******@cnam.fr (Evangelista Sami) wrote in message news:<5f**************************@posting.google. com>...

hello all

i am implementing an application in which a large number of (char *)
is stored into a hash table structure.
As there may be collisions, each (char *) inserted into my hash table
is put into an array. here is the definition of my hash table :

typedef struct
{
short size;
char **elements;
} hash_cell;
hash_cell hash_table[100000];

with this approach, each time i want to store an additional (char *) i
reallocate the array elements and add it an additional element.
this works fine but i have an overhead of a (char *) per element.

Another idea is to use a single (char *) by cell in the hash table and
to encode the size of each (char *) in this one with for instance 16
bits. the definition of this hash table should be :

typedef struct
{
short size;
char *elements;
} hash_cell;
hash_cell hash_table[100000];

For example if in the cell 0 i have three elements "toto", "abc", and
"peter",
i will have :
hash_table[0].elements[0 .. 1] = 4
hash_table[0].elements[2 .. 5] = "toto"
hash_table[0].elements[6 .. 7] = 3
hash_table[0].elements[8 .. 10] = "abc"
hash_table[0].elements[11 .. 12] = 3
hash_table[0].elements[13 .. 17] = "peter"

this makes me save 4 - 2 = 2 bytes if i assume that the size of (char
*) is 4 bytes and that the length of each element is encoded with 2
bytes.

However when i make the "ps aux" command during the execution, it
appears that the whole memory consumed by the first method is less
than with the second method and i cant see why.

Any explanation would be very useful

Sami Evangelista

I don't have an explaination for you about the memory usage you see
reported by ps.

You could probably save some more space by putting your short into
your string as the first two bytes. On many (32 bit at least)
systems, your short will followed by two padding bytes in the struct
that you could save here. This would save two bytes for occupied
cells and 4 bytes in unoccupied cells (where you would have a NULL
in the char* to implicitly say there are 0 elements). You would
need to do a sizeof (struct hash_cell) to see if this will help.
You could squeeze a bit more space out of the table if you are willing
to accept the limitation that the strings stored are <= 256 bytes in
length and use only one byte there. Or that there will be no more
than 256 strings in a single cell (if there are, your hash table
is presumably either way too small or your hash algorithm is not
doing it's job, assuming that duplicate entries are not being
added).

-David

[Eric Sosman]

Evangelista Sami wrote:

Eric Sosman <Er*********@sun.com> wrote in message news:<40**************@sun.com>...

Evangelista Sami wrote:

hello all

i am implementing an application in which a large number of (char *)
is stored into a hash table structure.
As there may be collisions, each (char *) inserted into my hash table
is put into an array. here is the definition of my hash table :

typedef struct
{
short size;
char **elements;
} hash_cell;
hash_cell hash_table[100000];

with this approach, each time i want to store an additional (char *) i
reallocate the array elements and add it an additional element.
this works fine but i have an overhead of a (char *) per element.

You haven't said so, but I'll assume that each `char*' points
to the start of a '\0'-terminated C string and not to a completely
arbitrary chunk of data.
[...]

i may have '\0' in my strings so i can't use to indicate the end of the string

(Let's avoid the term "string" for such an array: "string"
has a specific meaning in C, and this isn't it.)

If you don't use a terminator, you must have some other way
to determine the array length. Perhaps there's some way to
calculate it from the array contents (for example, consider the
way an LZW-compressed sequence denotes its endpoint), but more
likely there's another piece of "overhead" you failed to mention:
You're storing the array lengths somewhere.

You have saved three bytes per string at the cost of making
a duplicate copy of the string's data. If the string is longer
than three bytes, this is a poor trade. (If the strings are
all three bytes long or less, you could use a much more efficient
data structure than a hash table!)

what structure for example ?

How about a bit-map for single-byte "arrays," another for
two-byte arrays, and another for three-byte arrays? Assuming
an eight-bit byte, this requires 256 + 65536 + 16777216 bits,
or 32 + 8192 + 2097152 bytes. No space required for pointers
or lengths or copies of the array contents -- in fact, you can
discard the "original" arrays after entering them in the bit
map, for even more savings.

Depending on the distribution of the data, it might be
advantageous to use a trie instead of the largest bit-map, or
even instead of all three.

... but comp.lang.c is not a "Data Structures 101" course.

--
Er*********@sun.com