Joseph Wakeling wrote:
> Thanks to all again for the discussion, examples and explanations. :-)

[snip]
> My needs are in some ways quite narrow -- numerical simulations in
> interdisciplinary physics -- hence the C background, and hence the premium
> on performance.  They're also not very big programs -- simple enough for me
> to generally keep a personal overview on the memory management, even though
> with C++ that's usually all taken care of automatically (no new or delete
> statements if I can avoid it).
> 
> What I'm fairly confident about is that, given not too much time, D will
> become a _far_ preferable language for that kind of development.

There are quite a lot of us here with exactly that kind of background.

Something about the array issue -- D dynamic arrays are heavily geared towards algorithms which perform an initial allocation and afterwards avoid memory allocation entirely.
In D, such slicing algorithms are extremely clean, extremely fast, and memory safe.
In C++, it's much more difficult to write code in that manner. A straightforward translation from C++ will generally miss the benefits of D arrays, and you'll end up with slower code.

A kind of "Zen of D" is to use array slices as much as possible.

Steven Schveighoffer wrote:
> On Mon, 12 Apr 2010 12:03:38 -0400, Joseph Wakeling <joseph.wakeling@gmail.com> wrote:
> 
>> I thought dev effort was now focusing back on GDC ... ? :-P
> 
> AFAIK, gdc hasn't been actively developed for a few years.
> 
> ldc, on the other hand, has regular releases.  I think ldc may be the future of D compilers, but I currently use dmd since I'm using D2.

http://bitbucket.org/goshawk/gdc/wiki/Home

:-)

Either way I'm happy.  I don't have any issues with dmd, but I do want to see a properly free D compiler that can be prepackaged in all the Linux distros.

> Yes, you get around this by preallocating.

Sure.  But that wasn't what shocked me -- what I was amazed by was setting up a situation where I _had_ preallocated the memory and still seeing the memory usage explode, because D was preserving the memory from each round of the loop.

(Actually I'm still having some issues with this, despite using assumeSafeAppend, but more on that in a separate email.)

> It's often these types of performance discrepancies that critics point to (not that you are a critic), but it's the cost of having a more comprehensive language.  Your appetite for the sheer performance of a language will sour once you get bit by a few of these nasty bugs.

For sure.

> But D fosters a completely different way of thinking about solving problems.

I can see how the example you give would be fantastically useful.

More generally, I think this is the point -- I need to adjust my head to writing D-ish code, just as when moving from C to C++ I needed to switch to various new ways of doing things.

> There are many in the community that use D for numerical stuff.  It's definitely not as mature as it could be, but getting better.  Don is adding a lot of cool stuff to it, including a builtin exponent operator and arbitrary precision numbers.

I guessed there would be -- I knew for example that there was someone out there working on a fairly major mathematical/numerical library for D, but it's a while since I checked that out.

So take my earlier comment about numerical work to refer only to doing things the way I'm used to ... ;-)

> Yes, but that's not what I meant ;)  I mean, you can write your own
> types, like the Appender (or what the appender *should* be) that
> optimize the behavior of code to meet any needs.  And it can do it with
> a much better syntax than C.  D's template system and ability to make
> user-types seem like builtins I think is unparalleled in C-like languages.

Hence much pleasure and excitement in learning D ... :-)

Don wrote:
> There are quite a lot of us here with exactly that kind of background.
> 
> Something about the array issue -- D dynamic arrays are heavily geared towards algorithms which perform an initial allocation and afterwards avoid memory allocation entirely.
> In D, such slicing algorithms are extremely clean, extremely fast, and memory safe.
> In C++, it's much more difficult to write code in that manner. A straightforward translation from C++ will generally miss the benefits of D arrays, and you'll end up with slower code.

Exactly my current situation. :-P

> A kind of "Zen of D" is to use array slices as much as possible.

I will look into this more and see if this approach can help with some of my code -- are there existing projects I could take a look at to get some examples?

Thanks & best wishes,

    -- Joe

Joseph Wakeling wrote:
> (Actually I'm still having some issues with this, despite using assumeSafeAppend, but more on that in a separate email.)

... solved; it's interesting to note that assumeSafeAppend has to be used in _exactly_ the same scope as the append ~= itself.

e.g. with this loop, the memory blows up:

    ////////////////////////////////////////////////////////////////
    foreach(uint i;0..100) {
        x.length = 0;

        assumeSafeAppend(x);

        foreach(uint j;0..5000)
            foreach(uint k;0..1000)
                x ~= j*k;

        writefln("At iteration %u, x has %u elements.",i,x.length);
    }
    ////////////////////////////////////////////////////////////////

... while with this one it's OK:

    ////////////////////////////////////////////////////////////////
    foreach(uint i;0..100) {
        x.length = 0;

        foreach(uint j;0..5000) {
            foreach(uint k;0..1000) {
                assumeSafeAppend(x);
                x ~= j*k;
            }
        }

        writefln("At iteration %u, x has %u elements.",i,x.length);
    }
    ////////////////////////////////////////////////////////////////

Curious question: how come with a registered email address my messages have to be moderated, whereas via the http interface I can post straight away? :-P

Best wishes,

    -- Joe

On Mon, 12 Apr 2010, Joseph Wakeling wrote:

> Curious question: how come with a registered email address my messages have to be moderated, whereas via the http interface I can post straight away? :-P
> 
> Best wishes,
> 
>     -- Joe

All new subscribers to the lists start off moderated until a post flows through that isn't obvious spam.  As soon as I see that, I remove the moderated flag.  The list is a much bigger spam target than the news server is.  I deflect dozens of spam messages a day, some of which are clever enough to register for the list first (not daily, but probably monthly).

Later,
Brad

On Mon, 12 Apr 2010 15:36:19 -0400, Joseph Wakeling <joseph.wakeling@webdrake.net> wrote:

> Joseph Wakeling wrote:
>> (Actually I'm still having some issues with this, despite using
>> assumeSafeAppend, but more on that in a separate email.)
>
> ... solved; it's interesting to note that assumeSafeAppend has to be
> used in _exactly_ the same scope as the append ~= itself.
>
> e.g. with this loop, the memory blows up:
>
>     ////////////////////////////////////////////////////////////////
>     foreach(uint i;0..100) {
>         x.length = 0;
>
>         assumeSafeAppend(x);
>
>         foreach(uint j;0..5000)
>             foreach(uint k;0..1000)
>                 x ~= j*k;
>
>         writefln("At iteration %u, x has %u elements.",i,x.length);
>     }
>     ////////////////////////////////////////////////////////////////

This should work as you expect.  Can you produce a full code example?  Are you reserving space in x before-hand?

>
> ... while with this one it's OK:
>
>     ////////////////////////////////////////////////////////////////
>     foreach(uint i;0..100) {
>         x.length = 0;
>
>         foreach(uint j;0..5000) {
>             foreach(uint k;0..1000) {
>                 assumeSafeAppend(x);
>                 x ~= j*k;
>             }
>         }
>
>         writefln("At iteration %u, x has %u elements.",i,x.length);
>     }
>     ////////////////////////////////////////////////////////////////

The first assumeSafeAppend is the only one that matters.  Subsequent ones are wasted cycles.  I'm unsure why this one works and the other doesn't.  Again, I need full compilable examples.

-Steve

Steven Schveighoffer wrote:
> This should work as you expect.  Can you produce a full code example? Are you reserving space in x before-hand?

Weird; now it works.  I wonder if because I upgraded to 2.043 ... ?  I understand there was a fix in there for array append.

On the other hand, if the assumeSafeAppend takes place outside the loops entirely, blow-up occurs -- because the command is not issued after the array resize to zero?  I've attached examples.

Thanks & best wishes,

    -- Joe

Joseph Wakeling wrote:
> On the other hand, if the assumeSafeAppend takes place outside the loops entirely, blow-up occurs -- because the command is not issued after the array resize to zero?  I've attached examples.

If I include a line

     x.reserve(5_000_000);

before the assumeSafeAppend, the memory does not explode indefinitely -- but it uses about 3x as much memory as the 'NoLeak' code even when the latter lacks advance reservation of memory.

On Tue, 13 Apr 2010 08:24:57 -0400, Joseph Wakeling <joseph.wakeling@webdrake.net> wrote:

> Steven Schveighoffer wrote:
>> This should work as you expect.  Can you produce a full code example?
>> Are you reserving space in x before-hand?
>
> Weird; now it works.  I wonder if because I upgraded to 2.043 ... ?  I
> understand there was a fix in there for array append.

2.043 has fixed a corruption bug, one which you are unlikely to have triggered with a simple program like you wrote.  However, 2.041 had a severe corruption bug, which any array could fall victim to.  If you upgraded from 2.041, it's quite possible that fixed the problem.  If you just upgraded from 2.042, I think this may be a case of stale object/binary files ;)

>
> On the other hand, if the assumeSafeAppend takes place outside the loops
> entirely, blow-up occurs -- because the command is not issued after the
> array resize to zero?  I've attached examples.

Yes, assumeSafeAppend must be called every time you want to overwrite memory.  The runtime cannot tell if you still have references to the memory that was in use you don't want to be changed by appending to the header.  So it makes a conservative decision, "hey, this memory was in use, I'm not sure if it's in use anymore, so I'll reallocate rather than stomp on it."  assumeSafeAppend tells the runtime "yes, it was in use, but I'm no longer using it, so it is safe to stomp on it."  However, you only have to call it once per loop, because a single assumeSafeAppend assumes the remainder of the memory block after the array you pass as an argument to assumeSafeAppend is ok to stomp on.

-Steve

On Tue, 13 Apr 2010 08:30:57 -0400, Joseph Wakeling <joseph.wakeling@webdrake.net> wrote:

> Joseph Wakeling wrote:
>> On the other hand, if the assumeSafeAppend takes place outside the loops
>> entirely, blow-up occurs -- because the command is not issued after the
>> array resize to zero?  I've attached examples.
>
> If I include a line
>
>      x.reserve(5_000_000);
>
> before the assumeSafeAppend, the memory does not explode indefinitely --
> but it uses about 3x as much memory as the 'NoLeak' code even when the
> latter lacks advance reservation of memory.

x.reserve(5_000_000) will reserve the memory for the first loop.  But the second time through the loop will start reallocating from scratch unless you tell the runtime it's safe to reuse that memory.

Most likely it uses less memory than the noleak code because it has a nice continuous 40MB region to use in subsequent loops.  Because of the size of the array, it will naturally gravitate towards that region, and once it finds it, it will happily grow in place for a while.

assumeSafeAppend is needed to avoid reallocating the memory when setting the length back to 0.  It is an optimization designed specifically for this purpose.

My recommended approach for your little code sample is this:


import std.array;
import std.stdio;

void main()
{
	double[] x;
	x.reserve(5_000_000); // heads up, runtime, I'm about to use 40MB of continuous space

	foreach(uint i;0..100) {
		x.length = 0;
	
		assumeSafeAppend(x); // you can reuse that memory I just got done filling, I don't need it anymore.
		
		foreach(uint j;0..5_000) {
			foreach(uint k;0..1_000) {
				x ~= j*k;
			}
		}
		
		writefln("At iteration %u, x has %u elements.",i,x.length);
	}
}

If you don't use reserve, here is what happens during the loop:

1st append: The smallest block possible to hold 1 double is found and allocated
2nd append: If the block holding the first double can hold 2, the "allocated" size of the block is increased to 2 doubles.  Otherwise, the smallest block possible to hold 2 doubles is found and allocated.
...

Which means the first loop will consume extra memory on its way to building the full array.  With reserve, the array is preallocated, so every append is able to simply update the allocated length instead of reallocating, increasing performance and saving memory.

Note that every time the reallocation occurs because the block isn't big enough, the old block is left behind until the GC cleans it up.  But even when the GC cleans it up, it doesn't necessarily release it back to the OS, so your program may still be consuming that memory.

-Steve

On Tue, 13 Apr 2010 08:56:03 -0400, Steven Schveighoffer <schveiguy@yahoo.com> wrote:


> If you don't use reserve, here is what happens during the loop:
>
> 1st append: The smallest block possible to hold 1 double is found and allocated
> 2nd append: If the block holding the first double can hold 2, the "allocated" size of the block is increased to 2 doubles.  Otherwise, the smallest block possible to hold 2 doubles is found and allocated.
> ...
>

Assuming you may ask questions about this, it's not an exact description of what happens.  The append code and GC are smarter about it than this, I just wanted to explain it in an easy-to-understand way :)  The real code uses algorithms to determine optimal grow sizes and can extend into consecutive blocks if possible.

-Steve