If you happened to get that accidental blank send, sorry, I tried to
cancel it.
On Sat, 23 Mar 2013 19:45:21 -0400, Ivan Kazmenko <[email protected]> wrote:
On Saturday, 23 March 2013 at 19:33:06 UTC, Jonathan M Davis wrote:
You might want to check out this article where someone ran into similar
issues:
https://www.semitwist.com/articles/article/view/don-t-use-arrays-as-stacks
And if you haven't read Steven's article on arrays, you should do so:
http://dlang.org/d-array-article.html
That was a good reading, thank you! The whole matter became clearer for
me.
But now, I have one more example which confuses me, and the articles
don't seem to help right away with it. In this example, I am moving a
"sliding window" of length n; now that we're done with the stack, here
is a simple usage pattern of the queue. What I do is repeatedly (n
times also) add an element to the back of the array and then remove an
element from the front of it, keeping the whole queue constantly large.
Before the start, I reserve c*n entries for my array, where c is a real
number between 1 and 2. I track reallocations by monitoring the address
of an element of a which should remain still as long as the array is not
reallocated.
-----
import std.algorithm;
import std.array;
import std.range;
import std.stdio;
void main ()
{
int n = 2_000_000;
double c = 1.5;
auto a = array (iota (n));
a.reserve (cast (int) (n * c));
auto prev = &a[$ - 1];
int changes = 0;
foreach (i; 0..n)
{
debug {writeln (a.capacity);}
a.length++;
a = a[1..$];
auto next = &a[$ - i - 1];
if (prev != next)
{
changes++;
prev = next;
}
}
writeln (changes);
}
-----
Now, if I set c to 2, there are no reallocations: all the work goes with
the 2*n pre-allocated elements. But as I decrease c down to 1, the
number of reallocations grows *linearly*, roughly 1 per 2000 appends.
So for c = 1, there are 1044 reallocations in total. And that's still
quadratic behavior, albeit divided by a large constant (~2000)!
So here is how the appender tries to add data:
1. if the block is less than a page, memory is tracked as a bin of
like-sized blocks that fit into a page. Starting at 16-byte blocks, then
doubling until you reach half-page size. So if you need something that
consumes less than 16-bytes, a 16-byte chunk is allocated out of a 16-byte
bin (which is a page that has nothing but 16-byte chunks in it).
2. When you reallocate to a larger block size (16 to 32 for instance), the
block MUST be moved into another bin, because only 16-byte blocks are
allowed in that bin.
3. When you get to PAGE size (4096 bytes) and larger, the appender takes a
different approach:
a. If the page following your block is unallocated, and it can simply
extend the block into that next page, it will do so. This avoids copying
the data to another block, which arguably would be more expensive than
trying to double the capacity (not sure if this is true, but that's how it
works).
b. If not, it will reallocate into a new or existing empty block that
can hold the entire data, plus some additional space calculated by an
algorithm that is not quite double, but aims to amortize appending (if you
search in the lifetime.d file in druntime, look for newCapacity to find
the function that calculates this extra space).
HOWEVER, setting the length is NOT considered appending by the runtime.
The runtime takes a different approach when just setting the length -- it
does NOT add any extra capacity to try and amortize the allocations. The
idea is that you set the length usually once, and then use the array
without appending. It is more efficient if you are appending to give it
the elements to append rather than zero-init them first.
You will likely get better performance if you use:
a ~= int.init;
instead of:
a.length++;
What happens (locally) is, once the array size is not enough, it starts
being grown by blocks of 1024 or 891 (?!) elements in a repeating
pattern; one of these reallocates, the other does not. The textbook
growth implementation suggests doubling the array size, but it looks
like D attempts something smarter here. However, in my case, the result
is ~8x slower behavior when not pre-allocating. The more is n, the
slower is the version without pre-allocation (c = 1) compared to the
version with pre-allocation (c = 2). And this means that a D array is
not also an efficient queue out-of-the-box. However, as in the case
with stack, it could perhaps be efficient with a bit of tweaking (some
custom tailored calls to reserve perhaps?).
growth of 1024 is when the new pages are tacked onto the end (4096 /
sizeof(int)), growth of 891 is interesting. I can explain it though :)
you have allocated 2,000,001 ints at the time you increment length, or
8,000,004 bytes. The page size is 4096. So the block size you will need
to hold this is 8,003,584 (must be a multiple of pages).
So you now have 3580 extra bytes to grow into, divide by 4 (because
capacity is in terms of int elements), and you get... 896.
Hm... where are those extra 5 ints? The answer is weird, but the way the
array runtime can 'tack on' extra pages requires we store capacity (see my
previously referenced array article for more explanation) at the
beginning, and we require 16-byte alignment. So the capacity requires 16
extra bytes, even though it only uses 4 or 8 of them (depending on
architecture). But wait, that's only 4 ints! Where's that extra int?
Now, this is REALLY weird. Because blocks in memory can be sequential,
and we consider pointer at the end of a block to actually be pointing at
the beginning of the next block (for GC and other reasons), we add an
extra byte of padding at the END of the block to buffer it from
accidentally pointing at the next block. Consider if you had a
max-capacity slice, and you did sl[$..$], that would now be pointing at
the NEXT block (which may not even be allocated!) and you could wreak some
havoc by appending to that block or setting its length. Since ints must
be 4-byte aligned, we can't use the last 4 bytes of the block because of
that one padding byte, so you lose one more int for that.
-Steve
