On 3/31/21 5:32 PM, ludo wrote:
Hi guys,
I am working on an old software in D1, which defines at some point an
array.d module. See my github file: https://tinyurl.com/5ffbmfvz
If you go line 347, you see an ArrayBuilder struct, which is supposed to
behave exactly like an array but with faster concatenation. The class
comment says:
/**
* Behaves the same as built-in arrays, except about 6x faster with
concatenation at the expense of the base pointer
* being 4 system words instead of two (16 instead of 8 bytes on a 32-bit
system).
*/
I created a unittest, line 586, to test this statement. You can git
clone + dub test, to see the result. On my machine I get:
*** ArrayBuilder benchmark ***
1) Concatenation with std: 745 μs and 7 hnsecs
2) Concatenation with Arraybuilder: 236 μs and 8 hnsecs
3) Concatenation with Reserve: 583 μs and 5 hnsecs
4) Concatenation with Length: 611 μs and 8 hnsecs
5) Concatenation with Appender: 418 μs
In (1) I use standard array concatenation, in (2) I use the ArrayBuilder
struct, in (3) I test standard concat with a call to reserve()
before-hand, in (4) standard + length= beforehand, and finally I dug out
the Appender class in (5).
None of the D library tools beat the ArrayBuilder class! Note though,
that Appender is only two times slower, not 6x slower.
Can someone explain to me why ArrayBuilder is so fast (or the others so
slow)? What is this base pointer being "4 system words instead of 2"? I
read the code of ArrayBuilder, but I can not spot any magic trick... Has
this anything to do with standard array concat being "safer"
(thread-wise, bounds-wise, etc)?
ArrayBuilder should be similar in performance to Appender. I think part
of the issue with appender could be the ref counted design. Only 1000
elements is going to show heavily the setup/teardown time of allocation
of the implementation struct. But that is a guess. You may want to up
the repetition count to 100 or 1000.
Note your code for appending with length is not doing what you think:
void concat_withLength()
{
int[] array;
array.length = 1000;
for (int j=0; j<1000; j++)
array ~= j;
}
This allocates 1000 elements, and then append 1000 *more* elements.
I think you meant in the loop:
array[j] = j;
This should be the fastest one.
-Steve
