On Sat, Jun 6, 2009 at 10:53 AM, bearophile<bearophileHUGS@lycos.com> wrote:
> BCS:
>> bring up task manager
>
> That's what I have done to take those numbers. Then I have used another small program that has given me similar numbers...

You can add extra columns to the task manager to see all sorts of information.

That, or use procexp.

在 Sat, 06 Jun 2009 22:53:27 +0800，bearophile <bearophileHUGS@lycos.com> 写道:

> BCS:
>> bring up task manager
>
> That's what I have done to take those numbers. Then I have used another small program that has given me similar numbers...
>
> Bye,
> bearophile

You need to bring up the column of virtual memory usage

-- 
使用 Opera 革命性的电子邮件客户程序: http://www.opera.com/mail/

On Sat, Jun 6, 2009 at 8:03 AM, Vladimir Panteleev<thecybershadow@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.

davidl:
> You need to bring up the column of virtual memory usage

Ah, thank you for the suggestion\tip.
Now it shows it's using 1033 MB of virtual memory!

Bye,
bearophile

On Sat, 06 Jun 2009 18:12:58 +0300, Jarrett Billingsley <jarrett.billingsley@gmail.com> wrote:

> On Sat, Jun 6, 2009 at 8:03 AM, Vladimir
> Panteleev<thecybershadow@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.

Bulls-eye. I think mr. Dave Fladebo deserves a math lesson or something, and mr. Walter Bright should review patches that go into the language's runtime more carefully. :P

Can we discuss a suitable replacement? I suggested in #d that we look at how other platforms do it. For example, Java's Vector just doubles its capacity by default ( http://java.sun.com/javase/6/docs/api/java/util/Vector.html ).

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

On 2009-06-06 17:12:58 +0200, Jarrett Billingsley <jarrett.billingsley@gmail.com> said:

> On Sat, Jun 6, 2009 at 8:03 AM, Vladimir
> Panteleev<thecybershadow@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 upo
> n 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.

Indeed we were discussing this in the IRC,
Actually it is interesting to note that the continuos function written as comment in newCapacity
	double mult2 = 1.0 + (size / log10(pow(newcap * 2.0,2.0)));
does *not* have that behaviour.
It seems to me that it is generally much better to work on the total memory rather than on the number of elements.
I would use something like
           long mult = 100 + 200L / log2plus2(newcap)
and round up
           newext = cast(size_t)((newcap * mult) / 100);
           newext += size-(newext % size);

This is what I am adding in tango.

One could add something that further favors large sizes, but I miss the rationale behind that, I would rather expect that one typically concatenates strings (size=1..4) and so there is more to gain by making that faster.
I can also understand if someone wants to use only the number of elements (rather than the total size), but what was implemented wasn't that either.

If someone has some insight, or good benchmarks to choose a better function it would be welcome.

Fawzi

> Indeed we were discussing this in the IRC,
> Actually it is interesting to note that the continuos function written as comment in newCapacity
> 	double mult2 = 1.0 + (size / log10(pow(newcap * 2.0,2.0)));
> does *not* have that behaviour.
> It seems to me that it is generally much better to work on the total memory rather than on the number of elements.
> I would use something like
>             long mult = 100 + 200L / log2plus2(newcap)
> and round up
>             newext = cast(size_t)((newcap * mult) / 100);
>             newext += size-(newext % size);
> 
> This is what I am adding in tango.

thinking more about this, given that one starts at pagesize ~4024, log2=12 this might be too conservative, I will test a little bit more...

> One could add something that further favors large sizes, but I miss the rationale behind that, I would rather expect that one typically concatenates strings (size=1..4) and so there is more to gain by making that faster.
> I can also understand if someone wants to use only the number of elements (rather than the total size), but what was implemented wasn't that either.

maybe the number of elements is really the correct thing to do...

> 
> If someone has some insight, or good benchmarks to choose a better function it would be welcome.
> 
> Fawzi

Jarrett Billingsley wrote:
> On Sat, Jun 6, 2009 at 8:03 AM, Vladimir
> Panteleev<thecybershadow@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?  Particularly in D2 where append operations on arrays are probably less common as a result of string being invariant.  I'll fix newCapacity and run some tests, depending on their result I may disable it entirely.

Sean Kelly wrote:
> Jarrett Billingsley wrote:
>> On Sat, Jun 6, 2009 at 8:03 AM, Vladimir
>> Panteleev<thecybershadow@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?  Particularly in D2 where append operations on arrays are probably less common as a result of string being invariant.  I'll fix newCapacity and run some tests, depending on their result I may disable it entirely.

I think that's a great point.

Andrei

Sean Kelly:
> Particularly in D2 where append operations on arrays are probably less common as a result of string being invariant.

They aren't much common maybe because they are currently dead-slow. Appending to an immutable string is a common operation. But I guess Array appenders will get more common...

Bye,
bearophile