Aleksandar Donev said:
> I am starting to play with dynamic data structures, such as linked lists and
[...]
> following question: hat is the preferred strategy for allocating a lot of
> small data, such as for example allocating nodes to be inserted in a large
> linked list or tree?
That depends on many things, including hardware alignment
considerations and the quality of the vendor's memory allocator.
Unless you are allocating a huge amount of data, it is almost
certainly not worthwhile trying to second-guess the vendor - just do
it the natural way for the algorithm.
> I assume most UNIX Fortran implementations dellegate all allocations
> to malloc?
Some do, some do not.
The C "malloc" does have some unfortunate characteristics, e.g. it
adds an unnecessary storage overhead to each item, to store the size
of that item. (Well, there are techniques to avoid that, but not
many implementations of malloc do.)
> Using the memory profiler memprof I came to the following scary conclusion:
> EACH allocation allocate(next_node) allocates a total of 48 bytes !!! The
> basic unit next_node costs only 12 bytes though, 4 for the integer key and 8
> for the pointer (I am not sure why the pointer is 8 and not 4 bytes
> either...).
You probably have a machine with a bigger-than-32 bit address space,
thus 8 byte (64 bit) pointers.
Then, hardware alignment probably rounds your 12 bytes up to 16 bytes
before we start adding any malloc overhead; the minimum(!) malloc
overhead on a 64 bit machine is 8 bytes (for the maximum object size)
so we are already at 24 bytes.
> exist. But 48 bytes is way too much for a datum of 12 bytes. I would
It certainly does appear to be large, though not worth worrying about
unless you are going to be creating hundreds of thousands of them.
Perhaps you should talk to your vendor directly?
He is certainly in a better position to explain his own memory
allocator!
Cheers,
--
...........................Malcolm Cohen, NAG Ltd., Oxford, U.K.
([log in to unmask])
_____________________________________________________________________
This message has been checked for all known viruses by Star Internet delivered
through the MessageLabs Virus Control Centre. For further information visit
http://www.star.net.uk/stats.asp
|