Bug 14467 – arr.capacity sometimes erroneously returns 0

Works in 2.066.1, fails in 2.067: void main() { auto arr = new int[10]; assert(arr.capacity == 15); arr = arr[5..$]; assert(arr.capacity == 10); } I'll take a look at the code, see if I can figure out the fix.

it looks right to me. consider this code: void main () { auto a0 = new int[10]; auto a1 = a0[5..$]; a1 ~= 42; a0 ~= 667; } here if `a1.capacity` will not be 0, the last item of `a1` will become `667`, as druntime will reuse memory for `a0`, and that memory is already used by `a1`. as there is no dataflow analysis, compiler can't tell if `arr` in your case is the only ref to the array. so compiler conservatively sets slice capacity to `0`, triggering copy-on-append behavior.

(In reply to Ketmar Dark from comment #1) > it looks right to me. consider this code: > > void main () { > auto a0 = new int[10]; > auto a1 = a0[5..$]; > a1 ~= 42; > a0 ~= 667; > } > > here if `a1.capacity` will not be 0, the last item of `a1` will become > `667`, as druntime will reuse memory for `a0`, and that memory is already > used by `a1`. > > as there is no dataflow analysis, compiler can't tell if `arr` in your case > is the only ref to the array. so compiler conservatively sets slice capacity > to `0`, triggering copy-on-append behavior. It would be the runtime, not the compiler, since it would be done at runtime. But regardless, your example involves appending to one of the slices, whereas Steven's does not. As I understand it, the runtime knows what the farthest point into the memory block is that a slice has referred to is - which in Steven's example would be 10. It doesn't matter how many arrays refer to that block of memory, until one of the expands into the free space at the end, the farthest point used stays the same, and they should all have the capacity to grow into that space. That should only change once one of the actually uses some of that space - like in your example. Once that happens, the array which refers to the farthest point in the block of memory has the remainder of the block of memory as part of its capacity, whereas the others would not - their capacity would have to be either their length or 0 - and then when one of them is appended to, it would have to be reallocated. But as I understand it, it doesn't matter if more than one array refers to to the end of the used portion of the memory block. It only matters whether an array refers to the last portion used. If it doesn't, then it has no capacity to grow. If it does, then it does, even if other arrays refer to the same memory. And whichever array grows into that memory is the one that gets it, and the others will have to be reallocated if they are appended to. capacity is a calculated property. The arrays themselves only have a ptr and length property, and the runtime does not keep track of which slices refer to which memory block. It only keeps track of stuff like the farthest that an array has grown into it, and capacity is calculated by looking at the array passed in to the capacity function and looking at the block that it refers to, not by actually keeping track of the capacity of the array. That's part of why appending can be expensive, but we're kind of stuck with that without making the arrays themselves more complicated and doing stuff like making them reference-counted, which has a different set of pros and cons, but definitely would be harder to make work with having dynamic arrays being able to refer to static arrays and malloced buffers and the like, which works just fine right now.

ah, i see. somehow i was thinking that `capacity` is stored in the array struct. that's strange, 'cause i know that array struct consists of `ptr` and `length` only. thank you, and sorry for the noise.

but to rehabilitate myself a little i can tell you what was changed since 2.066. `GC.query` used to return block info regardless of the address passed, and now it works only if base address passed. with the following patch assert is ok again: diff --git a/src/rt/lifetime.d b/src/rt/lifetime.d index 23c611b..dde17af 100644 --- a/src/rt/lifetime.d +++ b/src/rt/lifetime.d @@ -719,7 +719,7 @@ body // step 1, get the block auto isshared = typeid(ti) is typeid(TypeInfo_Shared); auto bic = isshared ? null : __getBlkInfo((*p).ptr); - auto info = bic ? *bic : GC.query((*p).ptr); + auto info = bic ? *bic : GC.query(GC.addrOf((*p).ptr)); auto tinext = unqualify(ti.next); auto size = tinext.tsize; version (D_InlineAsm_X86)

Thank you, that is indeed the root cause. I have to investigate why that change was made, as most of the lifetime.d assumes GC.query will get the correct block info. Doing a double-lookup does not sound appealing to me as a fix, we need a function that finds the block info even for interior pointers. At this point, the array runtime is going to be severely broken performance-wise.

PR: https://github.com/D-Programming-Language/druntime/pull/1226 Note, the issue is strictly with the bits retrieved. The other aspects of the info block are correct, just the bits retrieved was not correct. Thanks, Ketmar for finding the root cause, it would have been much more difficult to find without that legwork!

Commits pushed to stable at https://github.com/D-Programming-Language/druntime https://github.com/D-Programming-Language/druntime/commit/0a740491d19a92cd12667ed2f3007ed23936f0e4 Fix issue 14467. When using GC.query, bits retrieved should be for base address, not interior pointer bitset. https://github.com/D-Programming-Language/druntime/commit/eeb01a68b992af0e87cbcf884a5aaf7a2035d2d6 Merge pull request #1227 from schveiguy/fixgcquery Fix issue 14467 - arr.capacity sometimes erroneously returns 0

Commits pushed to master at https://github.com/D-Programming-Language/druntime https://github.com/D-Programming-Language/druntime/commit/0a740491d19a92cd12667ed2f3007ed23936f0e4 Fix issue 14467. When using GC.query, bits retrieved should be for base address, not interior pointer bitset. https://github.com/D-Programming-Language/druntime/commit/eeb01a68b992af0e87cbcf884a5aaf7a2035d2d6 Merge pull request #1227 from schveiguy/fixgcquery

Commits pushed to dmd-cxx at https://github.com/dlang/druntime https://github.com/dlang/druntime/commit/0a740491d19a92cd12667ed2f3007ed23936f0e4 Fix issue 14467. When using GC.query, bits retrieved should be for base address, not interior pointer bitset. https://github.com/dlang/druntime/commit/eeb01a68b992af0e87cbcf884a5aaf7a2035d2d6 Merge pull request #1227 from schveiguy/fixgcquery