Array append performance

[Lionello Lunesu]

"bearophile" <bearophileHUGS at lycos.com> wrote in message 
news:g8ni6o$12k2$1 at digitalmars.com...
> Note2: In the D code the final deallocation of the array is fast enough, 
> and its allocation is fast too (you can see this timing just the for loop 
> in the middle of the program). The really slow part seems to be the loop 
> itself.

If the others are right, D's probably using std.gc.capacity to constantly 
check the capacity of the array. Interestingly, the Phobos GC caches the 
pointer/size in a call to "capacity", so that requesting the capacity of the 
same pointer immediately returns its capacity without any look-up. See 
function sizeOfNoSync, in internal/gc/gcx.d. Additionally, if there are no 
other threads, the GC lock is not taken, so capacity() should be O(1).

It would be interesting to check whether the cached pointer/size in the GC 
is actually being used. If it is not, it would result in a call to 
findSize() which in turn calls findPool(). findPool() is O(n), n = number of 
pools. The pooltable is already sorted, so this can be made O(log n). 
findSize() then does a linear search to check the size of the alloced block, 
which is O(m), m = size of block.

Result: getting the capacity of a pointer is O(m+n). There's a lot of room 
for improvement right there.

L.