On Mon, Nov 21, 2022 at 4:20 PM John Naylor <john.nay...@enterprisedb.com> wrote: > > > On Fri, Nov 18, 2022 at 2:48 PM I wrote: > > One issue with this patch: The "fanout" member is a uint8, so it can't hold > > 256 for the largest node kind. That's not an issue in practice, since we > > never need to grow it, and we only compare that value with the count in an > > Assert(), so I just set it to zero. That does break an invariant, so it's > > not great. We could use 2 bytes to be strictly correct in all cases, but > > that limits what we can do with the smallest node kind. > > Thinking about this part, there's an easy resolution -- use a different macro > for fixed- and variable-sized node kinds to determine if there is a free slot. > > Also, I wanted to share some results of adjusting the boundary between the > two smallest node kinds. In the hackish attached patch, I modified the fixed > height search benchmark to search a small (within L1 cache) tree thousands of > times. For the first set I modified node4's maximum fanout and filled it up. > For the second, I set node4's fanout to 1, which causes 2+ to spill to node32 > (actually the partially-filled node15 size class as demoed earlier). > > node4: > > NOTICE: num_keys = 16, height = 3, n4 = 15, n15 = 0, n32 = 0, n128 = 0, n256 > = 0 > fanout | nkeys | rt_mem_allocated | rt_load_ms | rt_search_ms > --------+-------+------------------+------------+-------------- > 2 | 16 | 16520 | 0 | 3 > > NOTICE: num_keys = 81, height = 3, n4 = 40, n15 = 0, n32 = 0, n128 = 0, n256 > = 0 > fanout | nkeys | rt_mem_allocated | rt_load_ms | rt_search_ms > --------+-------+------------------+------------+-------------- > 3 | 81 | 16456 | 0 | 17 > > NOTICE: num_keys = 256, height = 3, n4 = 85, n15 = 0, n32 = 0, n128 = 0, > n256 = 0 > fanout | nkeys | rt_mem_allocated | rt_load_ms | rt_search_ms > --------+-------+------------------+------------+-------------- > 4 | 256 | 16456 | 0 | 89 > > NOTICE: num_keys = 625, height = 3, n4 = 156, n15 = 0, n32 = 0, n128 = 0, > n256 = 0 > fanout | nkeys | rt_mem_allocated | rt_load_ms | rt_search_ms > --------+-------+------------------+------------+-------------- > 5 | 625 | 16488 | 0 | 327 > > > node32: > > NOTICE: num_keys = 16, height = 3, n4 = 0, n15 = 15, n32 = 0, n128 = 0, n256 > = 0 > fanout | nkeys | rt_mem_allocated | rt_load_ms | rt_search_ms > --------+-------+------------------+------------+-------------- > 2 | 16 | 16488 | 0 | 5 > (1 row) > > NOTICE: num_keys = 81, height = 3, n4 = 0, n15 = 40, n32 = 0, n128 = 0, n256 > = 0 > fanout | nkeys | rt_mem_allocated | rt_load_ms | rt_search_ms > --------+-------+------------------+------------+-------------- > 3 | 81 | 16520 | 0 | 28 > > NOTICE: num_keys = 256, height = 3, n4 = 0, n15 = 85, n32 = 0, n128 = 0, > n256 = 0 > fanout | nkeys | rt_mem_allocated | rt_load_ms | rt_search_ms > --------+-------+------------------+------------+-------------- > 4 | 256 | 16408 | 0 | 79 > > NOTICE: num_keys = 625, height = 3, n4 = 0, n15 = 156, n32 = 0, n128 = 0, > n256 = 0 > fanout | nkeys | rt_mem_allocated | rt_load_ms | rt_search_ms > --------+-------+------------------+------------+-------------- > 5 | 625 | 24616 | 0 | 199 > > In this test, node32 seems slightly faster than node4 with 4 elements, at the > cost of more memory. > > Assuming the smallest node is fixed size (i.e. fanout/capacity member not > part of the common set, so only part of variable-sized nodes), 3 has a nice > property: no wasted padding space: > > node4: 5 + 4+(7) + 4*8 = 48 bytes > node3: 5 + 3 + 3*8 = 32
IIUC if we store the fanout member only in variable-sized nodes, rt_node has only count, shift, and chunk, so 4 bytes in total. If so, the size of node3 (ie. fixed-sized node) is (4 + 3 + (1) + 3*8)? The size doesn't change but there is 1 byte padding space. Also, even if we have the node3 a variable-sized node, size class 1 for node3 could be a good choice since it also doesn't need padding space and could be a good alternative to path compression. node3 : 5 + 3 + 3*8 = 32 bytes size class 1 : 5 + 3 + 1*8 = 16 bytes Regards, -- Masahiko Sawada Amazon Web Services: https://aws.amazon.com
