OK, now the code works. Besude the TST struct I have created this helper struct
that keeps a pool of tree nodes:
struct StructPool(TyStruct, int MAX_BLOCK_SIZE_BYTES=1 << 14) {
static assert(MAX_BLOCK_SIZE_BYTES >= 1);
struct Block {
// Block is not too much big nor too much small
const int MAXB = MAX_BLOCK_SIZE_BYTES / TyStruct.sizeof;
const int SIZE = MAXB >= 1 ? MAXB : 1;
TyStruct[StructPool.Block.SIZE] structs;
}
static TyStruct* next_free_struct_ptr, last_struct_ptr;
static Block*[] blocks;
static TyStruct* newStruct() {
if (StructPool.next_free_struct_ptr >= StructPool.last_struct_ptr) {
// then add new block
// this whole new block gets scanned by the GC even if you need
only 1 node
StructPool.blocks.length = StructPool.blocks.length + 1;
StructPool.blocks[$-1] = new Block;
StructPool.next_free_struct_ptr =
StructPool.blocks[$-1].structs.ptr;
StructPool.last_struct_ptr = StructPool.next_free_struct_ptr +
Block.SIZE;
}
return StructPool.next_free_struct_ptr++;
}
/// deallocate blocks of structs
static void free() {
foreach (block_ptr; StructPool.blocks)
delete block_ptr;
StructPool.blocks[] = null;
StructPool.blocks.length = 0;
StructPool.next_free_struct_ptr = null;
StructPool.last_struct_ptr = null;
}
}
alias StructPool!(TST!(char)) TSTpool;
(I have used to static pointers, one single index to the last filled up struct
is also enough.)
That newStruct() is fast, about as class allocations in Java :-)
It's not nice code yet, with that external alias and so on, but it seems to
work and it almost halves the total allocation time of a big ternary search
tree (but despite the improve cache coherence the positive lookups into such
TST are about as fast as in a normally allocated TST, maybe because the D GC
packs the nodes closely in memory anyway). So I think in certain situations it
can be useful.
Now I'm trying to make the code nicer and less bug-prone, for example turning
that StructPool struct into a template mixin that I can use to add such pool
capability to other structs too that need to allocate many small structs and to
deallocate them all at the same time. But so far I have had the same kinds
errors I have shown in the two past posts.
Bye,
bearophile
