Pop quiz [memory usage]

[Vladimir Panteleev]

On Sat, 06 Jun 2009 20:19:45 +0300, Sean Kelly <sean at invisibleduck.org>
wrote:

> Jarrett Billingsley wrote:
>> On Sat, Jun 6, 2009 at 8:03 AM, Vladimir
>> Panteleev<thecybershadow at gmail.com> wrote:
>>> // Works for DMD1/Phobos, DMD1/Tango and DMD2/Phobos
>>> version(Tango) import tango.io.Console;
>>> else           import std.stdio;
>>>
>>> struct S
>>> {
>>>        ubyte[40_000] data;
>>> }
>>>
>>> void main()
>>> {
>>>        S[] a;
>>>        a ~= S();
>>>
>>>        // QUESTION: How much memory will this program consume upon  
>>> reaching
>>> this point?
>>>        version(Tango) Cin.copyln();
>>>        else           readln();
>>> }
>>>
>>  There seems to be something wrong with the newCapacity function that
>> _d_arrayappendcT calls.  From an element size of 20000 (I halved it
>> just to make the allocation faster) and an array length of 1, it
>> somehow calculates the new size to be 266686600.  Hm.  That seems a
>> bit off.
>>  It seems this line:
>>  long mult = 100 + (1000L * size) / log2plus1(newcap);
>>  is to blame.  I don't think large value types were taken into account
>> here.  The resulting multiplier is 1,333,433, which is hilariously
>> large.
>
> I've been debating for a while whether newCapacity shoulds exist at all.  
>   The GC already tends to leave free space at the end of blocks, so why  
> should the runtime second-guess it?

Do you mean at the end of pages, or pools?

Pages are only 4K in size, causing a reallocation on every 4K doesn't make
sense performance-wise.

If you mean that DMD will allocate memory pools larger than the immediate
memory requirement, that's true, however D's GC is "greedy" in that it
always allocates memory at the lowest address possible. This means that
when all previous pools fill up, the next object will "cap" the new array,
and the array will no longer be able to extend.

Allow me to demonstrate:

-----------------------
import std.gc;
import std.stdio;

struct S1
{
	ubyte[4095] data;
}

struct S2
{
	ubyte[4095*4] data;
}

void main()
{
	S1[] a;
	S2*[] b;
	for (int i=0;i<1024;i++)
	{
		a ~= S1();
		b ~= new S2;
		writefln("%d", i);
	}
}
-----------------------

This program allocates 4-page blocks and appends 1-page blocks to an array
in a loop.

Here's a Diamond[1] analysis screenshot from before and after the first
two garbage collects:
http://dump.thecybershadow.net/b4af5badf32c954b7a18b848b7d9da64/1.png

The P+++ segments are S2 instances. The segments with the longer tails of
+es are copies of S1[].

As you can see, as soon as the previous pools fill up, the pool containing
the S1[] gets rapidly filled, because it's just a loop of reallocating
S1[] every time an S2[] is allocated at its end.

So, I don't think that your idea is feasable with the current GC
implementation. I wonder how much would things get improved if objects
would be divided between "growing" and "non-growing", with the GC
prioritizing allocating new objects in free space not directly following
"growing" objects.

[1] http://www.dsource.org/projects/diamond

-- 
Best regards,
    Vladimir                          mailto:thecybershadow at gmail.com