Re: sizeof([ALLOCATED MEMORY])

In article <44594dcf$1@xxxxxxxxxxxxxxx>,
"Nils O. Selåsdal" <noselasd@xxxxxxxxxxxxxxxxxxxxx> wrote:

However when you allocate the memory, you don't know precisely how much
you received. It could be more than you requested. And common
applications exist which could make use of that extra memory if only
they knew it existed (e.g. a dynamic array).

Why would they make use of more memory than they requested instead of
just requesting that much memory in the first place ?

Perhaps I should elucidate "dynamic array".

Consider a general purpose library which manages an array of short.
This array has a length to be determined at run time, and that length
can grow or shrink over the lifetime of the array via functions such as
"insert", "resize" or "append".

A typical use case might be:

struct array_of_short
{
short* data;
size_t size;
};

array_of_short my_array = create_array_short(N);
// ...
// Fill my_array with values and do some computation with it
// ...
if (some_condition)
{
append_array_short(&my_array, M, value);
// ...
// continue computation with modified array
// ...
}

The data structure as described above has an efficiency concern:
Repeated growth in size can lead to quadratic expense due to continually
reallocating for a slightly larger size. A well known fix is to have
the array keep track of both a logical size and a physical capacity
which it can cheaply grow into:

struct array_of_short
{
short* data;
size_t size;
size_t capacity;
};

Use as before, but this new struct has an invariant: size <= capacity.

"append_array_short" and its brethren can now increase the size very
rapidly if the new size is still less than the capacity. When the new
size is greater than the capacity, these functions can reallocate the
capacity at a geometric rate (say by some growth factor between 1.5 and
2, (1+sqrt(5))/2 has been theorized as an optimum growth factor). Using
a geometric growth factor for the capacity bounds the number of
reallocations that a given array will see over its lifetime to a very
small number (compared to an incremental growth strategy).

No matter what the growth strategy for capacity, its existence is a
major motivation for finding out the amount of memory actually
allocated. create_array_short(N) may request only N*sizeof(short)
bytes, but may receive slightly more than that (for alignment purposes
or whatever). If create_array_short(N) had some way to find out how
much memory it actually received, then it makes perfect sense to set
capacity to size_received/sizeof(short) instead of to N. It makes for
higher performing code in the average case.

-Howard
.

Relevant Pages

  • Re: Framework 2.0 array redim unsatisfactory performance
    ... > Implements the System.Collections.Generic.IListinterface using an array ... initial capacity is specified 92.6% memory is used by objects. ... long usedMem0 = GC.GetTotalMemory; ...
    (microsoft.public.dotnet.languages.vb)
  • Re: std::vector erase is not freeing mem?
    ... > say regarding freeing memory when you 'erase' a value. ... > some other array. ... I wouldn't be surprised if the capacity of the vector stays the same, ...
    (comp.lang.cpp)
  • Re: Framework 2.0 array redim unsatisfactory performance
    ... | Listreally copies array to twice bigger when needed - the model ... expand its buffer (the internal array) it doubles its size & copies the ... If you set the initial capacity ... | initial capacity is specified 92.6% memory is used by objects. ...
    (microsoft.public.dotnet.languages.vb)
  • Re: Pointer To A Vector Elements While Still Adding
    ... As I understand it, when you add an element to the end of a list, memory is ... there is sufficient capacity. ... elements to 10,000 lists. ... better to allocate them statically). ...
    (comp.lang.cpp)
  • Re: Pointer To A Vector Elements While Still Adding
    ... that deque has equal or better Big-O performance in equivalent operations, ... > there is sufficient capacity. ... > memory to the new. ... > elements to 10,000 lists. ...
    (comp.lang.cpp)