Ternary Search Trees
bearophile
bearophileHUGS at lycos.com
Fri Apr 17 14:27:43 PDT 2009
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
More information about the Digitalmars-d
mailing list