Dynamic Arrays Capacity

[Steven Schveighoffer]

On 6/2/22 1:04 AM, Salih Dincer wrote:
> Hi,
> 
> Do I misunderstand? A dynamic array is allocated memory according to the 
> `nextpow2()` algorithm(-1 lapse); strings, on the other hand, don't 
> behave like this...
> 
> ```d
>    string str = "0123456789ABCDEF";
>    char[] chr = str.dup;
> 
>    assert(str.length == 16);
>    assert(str.capacity == 0);
> 
>    import std.math: thus = nextPow2; //.algebraic
> 
>    assert(chr.capacity == thus(str.length) - 1);
>    assert(chr.capacity == 31);
> ```

The capacity is how many elements of the array can be stored without 
reallocating *when appending*.

Why 0 for the string literal? Because it's not from the GC, and so has 
no capacity for appending (note that a capacity of 0 is returned even 
though the string currently has 16 characters in it).

Why 31 for the GC-allocated array? Because implementation details. But I 
can give you the details:

1. The GC allocates in powers of 2 (mostly) The smallest block is 16 
bytes, and the next size up is 32 bytes.
2. In order to remember which parts of the block are used, it needs to 
allocate some space to record that value. For a 16-byte block, that 
requires 1 byte. So it can't fit your 16-byte string + 1 byte for the 
capacity tracker into a 16 byte block, it has to go into a 32 byte 
block. And of course, 1 byte of that 32 byte block is for the capacity 
tracker, hence capacity 31.

> Also, `.ptr` keeps the address of the most recent first element, right?

This statement suggests to me that you have an incorrect perception of a 
string. A string is a pointer paired with a length of how many 
characters after that pointer are valid. That's it. `str.ptr` is the 
pointer to the first element of the string.

There isn't a notion of "most recent first element".

-Steve