qbaum:

naive implementation:

1
4
16
64
256
1024
4096

struct node {
  node* parent; node* childs[4]; chunk* c;
}

leaf node has a non-null ptr to chunk.

node size (unoptimized) = 48 bytes
full tree has: 5461 nodes
max memory: 262 KB (~6% of 4MB root chunk size)

==> atrocious.


------

struct node {
  node* parent; void* childs[4];
}

impl 2: merge the last level nodes with the chunk headers: removes one recursion

- a child pointer is either another node or a chunk header.
- but we need a way to detect that a node is a leaf to know how to cast the child pointers
- solution: since all nodes are allocated from in the node pool and all chunk headers in the chunk header pool,
  an "is_node_pointer" boils down to "is this pointer in the node pool", which is two address compares
- Bonus: node gets smaller since we now do not need an explicit chunk pointer anymore

1
4
16
64
256
1024

node size: 40 bytes
full tree has: 1365 nodes
max memory: 54Kb (about 1.5% of 4MB root chunk size)
 
=> not too shabby

------

impl3: Similar to impl2, but we use not pointers ot nodes and pointers to chunks but indices. Since these structures live in arrays.
- we need to code a special value into the index to make clear from which pool it comes.

Nodes would get even smaller.

node size: 20 bytes
full tree still has: 1365 nodes
max memory: 27Kb (about .6 % of 4MB root chunk size)

==> very good, but problem with this is that it may be cpu intensive since we need to resolve an index each time we need a pointer, and the code may be more difficult to read? 

Earmarked for future improvement.

---------------------------------------
---------------------------------------
---------------------------------------


binary tree:


naive implementation:

1
2
4
8
16
32
64
128
256
512
1024
2048
4096

struct node {
  node* parent; node* child; node* sib; chunk* c;
}

node size: 32 bytes
full tree has: 8191 nodes
max memory: 262K
 
=> : ((

-------------------------------------------------------

Remove last level:

1
2
4
8
16
32
64
128
256
512
1024
2048
>>> 4096<<<

struct node {
  node* parent; void* child; node* sib;
}

node size: 24 bytes
full tree has: 4095 nodes
max memory: 98K

=> meh

------------------------------------------------------

Using 32bit references instead like described above under impl3

1
2
4
8
16
32
64
128
256
512
1024
2048
>>> 4096<<<

struct node {
  ref_t parent; ref_t child; ref_t sib;
}

node size: 12 bytes
full tree has: 4095 nodes
max memory: 49K

=> meh


===================================================================

Okay, most pragmatic impl is impl2 (quaternary tree with the last level merged, but still using pointers); 56K

best but more difficult to code impl and maybe more cpu intensive is impl3, which halfs the memory to 27K