Re: Array and memory usage

[Robert A Duff <bobduff@shell01.TheWorld.com>]

Preben Randhol <randhol+news@pvv.org> writes:

> I was a bit puzzeled to see that if I do:
> 
>    type Str_Array_Type is array (1 .. 1000) of String (1 .. 800);
> 
>    type User_Data is
>       record
>          Name     : Str_Array_Type;
>          Hostname : Str_Array_Type;
>       end record;
> 
> my program uses 800 bytes of memory, while if I only change the program
> like this:
> 
>    type User_Data is
>       record
>          Name     : Str_Array_Type := (others => (others => ' '));
>          Hostname : Str_Array_Type := (others => (others => ' '));
>       end record;
> 
> then the program uses 2356 bytes.
> 
> I thought all the memory needed for an array would be claimed when the
> program started no matter if the array was filled or not.

I presume you mean you declared one object of type User_Data at library
package level?

A good operating system will allocate *virtual* memory for that object
(among other things), but will not allocate physical memory until is is
needed.  If you initialize it to all-blanks, physical memory is needed
to store those blanks (on typical operating systems).  If you don't
initialize it, that physical memory is not needed (until later,
presumably).

You don't say what tool you're using to measure memory usage, or what it
claims to measure.  It may well be that it is measuring physical memory,
which may be quite low at first, but might grow as you assign data into
that object.

All of this applies only if you have a proper operating system running
on hardware with memory protection.  Many embedded systems do not, and
therefore would allocate as much physical memory as they need for that
variable up front.

> Is this correct or am I just being tricked by the program that measures
> the memory used by my program? 
> 
> If it is correct then it doesn't matter if I define my array as (1 ..
> 100) or (1 .. 10_000) as long as I don't initialize the strings.
> I can just add to User_Data a:
> 
>    type Used_Type is array (1 .. 1000) of Boolean;
> 
>    Used : Used_Type := (others => False);
> 
> And then I don't need to add any linked list etc... to my small server.

Well, if you're allocating randomly all over the place, this won't help,
because physical memory is allocated in pages.

But one thing you can do is if you're allocating "used slots" at the
beginning of an array, you can keep a count of the "last used" slot.  On
a good operating system you can safely allocate an enormous array (say,
hundreds of megabytes), trusting the OS to allocate physical memory near
the beginning of the array as needed.  This is useful in cases where you
don't know ahead of time how much data you need -- it might be huge, but
probably is quite small, and you don't want to waste physical memory
when it is small.

If you use this trick on Windows, it will allocate backing store for all
that virtual memory.  I believe most Unix systems are smarter than that.

This trick is sometimes more efficient than linked lists for growable
data structures.  The links waste space, plus if you're not careful, the
list gets scattered all over the place, damaging cache behavior.  The
nice thing about arrays is that they are contiguous.

If you try to use this trick for an array of pointers, Ada will defeat
you by implicitly initializing to all-nulls.  It is possible to do
better, but that requires some cooperation between OS and compiler.

As a rule of thumb, virtual memory is perhaps 1000 times cheaper than
physical memory, depending on hardware and OS.

> I use GNAT 3.14p on i386 Linux (Debian).

I believe a page on that system is 2**12 bytes.  So if my explanation is
correct, you should be seeing your memory usage grow in chunks of that
size.  It doesn't match the numbers you mentioned above...

- Bob