Can't run a simple program. What's wrong, GC?

import std.stdio;
import std.date;

void f0()
{
	wstring a[];

	foreach(i; 0 .. 100_000_000)
	{
  		a ~= " "w;
  	}
}

void main()
{
	auto r = benchmark!(f0)(1);
	writeln(r, "ms");
}

DMD 2.047

On Wednesday, November 10, 2010 08:33:45 Xie wrote:
> Can't run a simple program. What's wrong, GC?
> 
> import std.stdio;
> import std.date;
> 
> void f0()
> {
> 	wstring a[];
> 
> 	foreach(i; 0 .. 100_000_000)
> 	{
>   		a ~= " "w;
>   	}
> }
> 
> void main()
> {
> 	auto r = benchmark!(f0)(1);
> 	writeln(r, "ms");
> }
> 
> DMD 2.047

You just tried to create an array with 100_000_000 elements, and arrays try and maintain extra capacity for extra appending, so you're actually trying to create one bigger than that. That's a _lot_ of memory, and it's _contiguous_ memory. You probably hit some sort of memory limit in there somewhere and would have the same problem if you tried to create an array that large in C or C++. That's an _enormous_ array. Maybe it's a 32-bit barrier which will go away once 64-bit dmd is complete, but it's not exactly normal to try and use an array wich 100 million elements in it. The computer does have limits you know.

- Jonathan M Davis

On Wed, 10 Nov 2010 11:33:45 -0500, Xie <xiemargl@gmail.com> wrote:

> Can't run a simple program. What's wrong, GC?
>
> import std.stdio;
> import std.date;
>
> void f0()
> {
> 	wstring a[];
>
> 	foreach(i; 0 .. 100_000_000)
> 	{
>   		a ~= " "w;
>   	}
> }
>
> void main()
> {
> 	auto r = benchmark!(f0)(1);
> 	writeln(r, "ms");
> }

The results on my machine with 1G of memory is that it consumes 2G of memory and the system starts thrashing.  I changed the value to 10_000_000, and it runs in a couple seconds, I change it to 50_000_000 and it runs in 200 seconds.

Something is definitely amiss here, because the following doesn't help (it still consumes 1.2GB of memory):

void f0()
{
	wstring a[];
	a.reserve(100_000_000);

	foreach(i; 0 .. 100_000_000)
	{
  		a ~= " "w;
  	}
}

This should take the explosive nature of appending out of the equation, because a reallocation should never occur.

I'll look into it.

-Steve

On Wed, 10 Nov 2010 13:33:11 -0500, Steven Schveighoffer <schveiguy@yahoo.com> wrote:

> On Wed, 10 Nov 2010 11:33:45 -0500, Xie <xiemargl@gmail.com> wrote:
>
>> Can't run a simple program. What's wrong, GC?
>>
>> import std.stdio;
>> import std.date;
>>
>> void f0()
>> {
>> 	wstring a[];
>>
>> 	foreach(i; 0 .. 100_000_000)
>> 	{
>>   		a ~= " "w;
>>   	}
>> }
>>
>> void main()
>> {
>> 	auto r = benchmark!(f0)(1);
>> 	writeln(r, "ms");
>> }
>
> The results on my machine with 1G of memory is that it consumes 2G of memory and the system starts thrashing.  I changed the value to 10_000_000, and it runs in a couple seconds, I change it to 50_000_000 and it runs in 200 seconds.
>
> Something is definitely amiss here, because the following doesn't help (it still consumes 1.2GB of memory):
>
> void f0()
> {
> 	wstring a[];
> 	a.reserve(100_000_000);
>
> 	foreach(i; 0 .. 100_000_000)
> 	{
>    		a ~= " "w;
>    	}
> }
>
> This should take the explosive nature of appending out of the equation, because a reallocation should never occur.
>
> I'll look into it.

Waaaait a second, a is not a wstring, it's an *array* of wstrings.  That's completely different.

This all makes sense now.  It's not 200MB, it's 800MB your code is asking for.  This might be a bit much for a test, a 32-bit system only supports 4GB of address space, and usually 1GB is reserved, so you are trying to allocate about 1/3 of the memory you could possibly allocate.

Is there any reason you expect this to perform well?

-Steve

On 11/10/2010 11:33 AM, Xie wrote:
> Can't run a simple program. What's wrong, GC?
>
> import std.stdio;
> import std.date;
>
> void f0()
> {
> 	wstring a[];
>
> 	foreach(i; 0 .. 100_000_000)
> 	{
>    		a ~= " "w;
>    	}
> }
>
> void main()
> {
> 	auto r = benchmark!(f0)(1);
> 	writeln(r, "ms");
> }
>
> DMD 2.047

In addition to what everybody else is suggesting you look at, you may want to look into using an appender (defined in std.array).  Not sure if it will help with the memory usage, but it's supposed to be faster for appending data to an array.

Casey

On Wed, 10 Nov 2010 13:55:26 -0500, sybrandy <sybrandy@gmail.com> wrote:

> On 11/10/2010 11:33 AM, Xie wrote:
>> Can't run a simple program. What's wrong, GC?
>>
>> import std.stdio;
>> import std.date;
>>
>> void f0()
>> {
>> 	wstring a[];
>>
>> 	foreach(i; 0 .. 100_000_000)
>> 	{
>>    		a ~= " "w;
>>    	}
>> }
>>
>> void main()
>> {
>> 	auto r = benchmark!(f0)(1);
>> 	writeln(r, "ms");
>> }
>>
>> DMD 2.047
>
> In addition to what everybody else is suggesting you look at, you may want to look into using an appender (defined in std.array).  Not sure if it will help with the memory usage, but it's supposed to be faster for appending data to an array.

Just tried it, Appender is actually slower.  This *is* a problem, it should be way faster than builtin array appending.

I will look into it.

-Steve

On Wed, 10 Nov 2010 14:06:40 -0500, Steven Schveighoffer <schveiguy@yahoo.com> wrote:

> Just tried it, Appender is actually slower.  This *is* a problem, it should be way faster than builtin array appending.
>
> I will look into it.

More data, Appender taking an array of elements is significantly slower than taking a single element (by an order of magnitude).

I'll try to figure out why.

BTW, if you append individual wchars instead of a string of a single wchar, Appender does beat the pants off of builtin appends.

-Steve

Sorry, it a mistypo (i began from wchar[], later changed to wstring)

Real problem can be seen here

import std.stdio;
import std.date;

void f0()
{
	wstring a;

	foreach(i; 0 .. 100_000_000)
	{
  		a ~= " "w;
  	}
}

void main()
{
	auto r = benchmark!(f0)(10);
	writeln(r, "ms");
}

On Wed, 10 Nov 2010 14:38:02 -0500, Xie <Xiemargl@gmail.com> wrote:

> Sorry, it a mistypo (i began from wchar[], later changed to wstring)
>
> Real problem can be seen here
>
> import std.stdio;
> import std.date;
>
> void f0()
> {
> 	wstring a;
>
> 	foreach(i; 0 .. 100_000_000)
> 	{
>   		a ~= " "w;
>   	}
> }
>
> void main()
> {
> 	auto r = benchmark!(f0)(10);
> 	writeln(r, "ms");
> }

OK, this actually makes sense to me.

It's a manifestation of this issue: http://d.puremagic.com/issues/show_bug.cgi?id=3929

In essence, in order to aid performance, there is an 8-element cache of arrays that are being appended.  At the moment, the append code relies on this cache keeping the array from being collected to remain sane.  However, as I wrote in the last message on that bug report, I think I can fix it so the cache is not considered a pointer to the memory, and it should be collected.  But I haven't done that yet.

So what's happening in your code is the first 8 times executing that function, the memory is not collected.  This results in you allocating actually 800 million wchars, or 1.6GB before anything can be collected.

So in the meantime, jump on the CC for that bug, and I hope to get to it sometime in the near future (maybe by 2.051-2.052).

-Steve

>OK, this actually makes sense to me.

>It's a manifestation of this issue: http://d.puremagic.com/issues/show_bug.cgi?id=3929

I'm think - it's truth but not at all.

Sorry, but i'm give incomplete data.

My example run fine, when benchmark(1), (2), but not 10.
This means, that memory not collected _between_ calls.