On Sunday, 3 February 2013 at 11:47:21 UTC, Steven Schveighoffer
wrote:
On Sun, 03 Feb 2013 03:53:10 -0500, timotheecour
<[email protected]> 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.
