On Sat, 02 Feb 2013 23:37:10 -0500, Ali Çehreli <acehreli@yahoo.com> wrote:

> Rather, a better growth factor is 150%. It has been shown that 150% growth factor works much better with memory allocators.

in fact, D's appender uses something more than doubling.  I did not write that part (though I did massage it for optimizations), so I don't know the rationale behind it or how it is designed to work, but the code is here:

https://github.com/D-Programming-Language/druntime/blob/master/src/rt/lifetime.d#L1651

-Steve

On Sunday, 3 February 2013 at 10:32:10 UTC, timotheecour wrote:
>
>> One more: Did you try using std.container.Array?
>>
>> Even if appender is more optimized than naked array appending, it still has to work with the underlying system. std.container.Array should be able to do just as well as vector, or better (D move semnantics).
>
> it's a bit better (see below for timings), with T=22.628 sec total vs 14s for C++'s std::vector.
>
> Note, I'm not sure how to get address of 1st element in an std.container.Array (is it even possible??? seems like an overreaching limitation for the sake of safety in a system language) so I don't know how to tell the reallocations. But I guess the scheme is clear (reserve(1+3/2*capacity)). In any case, there's still a noticable gap with C++. Also, I'm curious whether you have a reference explaining why 3/2 works better than 2x (as in std::vector) in resizing?

Yeah: std.container.Array does not allow references to its internals. D's design is more of a safety first, compared to C++'s performance first.

On Sunday, 3 February 2013 at 11:47:21 UTC, Steven Schveighoffer wrote:
> On Sun, 03 Feb 2013 03:53:10 -0500, timotheecour <thelastmammoth@gmail.com> wrote:
>
>>> Note that dynamic arrays are generic containers, so they aren't exactly optimized for anything. You could try that test with the "made for appending" std.array.appender: It always tries to extend without reallocating, and only relocates when the current memory segment is 100% full.
>>>
>>> Furthermore, when it *does* relocate, it use D-style memmove without calling postblit. Independent of language, and with the requirement of contiguous memory, I can't really think of a scheme that could be better than that...?
>>
>>
>> modified a bit (see below) to include timing etc. I'm on OSX (16GB ram, core i7 2.3GHz).
>> dmd is slow even with optimizations so I used ldc:
>>
>> ldmd2 -inline -O -release -noboundscheck  (similar results with ldc2 -O3 -release)
>> for C++: g++ -O2
>>
>> It seems that:
>> * the number of moves is up to 2x (resp. 1.8x) as the C++ version for T[] (resp. appender)
>> * the C++ version is 7x (resp 1.8x) times faster .
>> * it seems even the appender version grows super-linearly whereas C++ version stays roughly linear in that regime in terms of time.
>>
>> Based on this, I'm curious whether the current growing scheme could be improved, or be closer to the simple doubling scheme used in C++.
>
> The performance increase is due to a) using malloc instead of GC allocation, which would run quite a few collection cycles while allocating.  If you profile the D code, you will see this.  b) vector is FREEING its previously used array space, D array appending is relying on the GC to free that space.  The consumed D space will grow more rapidly.
>
> You are essentially comparing apples to oranges here.
>
> -Steve

True...

But not true for std.container.Array though. Array uses malloc. That's an apples to apples comparison right there.

On 02/03/2013 02:32 AM, timotheecour wrote:

> I'm curious whether you have a reference explaining why
> 3/2 works better than 2x (as in std::vector) in resizing?

I had heard about this years ago first on comp.lang.c++.moderated. I am pretty sure it is common practice in modern libraries.

This may be the thread:


https://groups.google.com/forum/?fromgroups=#!topic/comp.lang.c++.moderated/asH_VojWKJw/discussion[1-25-false]

Scott Meyers refers to an older thread there. So it may have been that one. But it doesn't matter, there are articles online now. :)

Ali

On 02/03/2013 03:57 AM, Steven Schveighoffer wrote:
> On Sat, 02 Feb 2013 23:37:10 -0500, Ali Çehreli <acehreli@yahoo.com> wrote:
>
>> Rather, a better growth factor is 150%. It has been shown that 150%
>> growth factor works much better with memory allocators.
>
> in fact, D's appender uses something more than doubling. I did not write
> that part (though I did massage it for optimizations), so I don't know
> the rationale behind it or how it is designed to work, but the code is
> here:
>
> https://github.com/D-Programming-Language/druntime/blob/master/src/rt/lifetime.d#L1651 

>
>
> -Steve

If the comments are current, the implementer is Dave Fladebo. That algorithm considers arrays differently by how large they are:

/*
* Better version by Dave Fladebo:
* This uses an inverse logorithmic algorithm to pre-allocate a bit more
* space for larger arrays.
* - Arrays smaller than PAGESIZE bytes are left as-is, so for the most
* common cases, memory allocation is 1 to 1. The small overhead added
* doesn't affect small array perf. (it's virtually the same as
* current).
* - Larger arrays have some space pre-allocated.
* - As the arrays grow, the relative pre-allocated space shrinks.
* - The logorithmic algorithm allocates relatively more space for
* mid-size arrays, making it very fast for medium arrays (for
* mid-to-large arrays, this turns out to be quite a bit faster than the
* equivalent realloc() code in C, on Linux at least. Small arrays are
* just as fast as GCC).
* - Perhaps most importantly, overall memory usage and stress on the GC
* is decreased significantly for demanding environments.
*/

The comments include some test results as well and where the diminishing return is.

Ali