Performance comparison with @justinasvd art_map - laurynas-biveinis/unodb GitHub Wiki

Test branch, including art_map at this commit

Value size fixed at eight bytes to avoid having to deal with differences in value construction.

key prefix operation microbenchmarks: split slower by 23%, cut by 19%, prepend faster by 33%, get shared length about the same.

Node4 microbenchmarks: tree sizes about the same with art_map being slightly larger, except for shrinking tests, where it is slightly smaller. Speed: inserts are faster for smaller trees (17% dropping off to 5%) until 32768 elements, where they become 5%-9% slower. Scans 3%-8% slower. Random searches 1%-2% slower. Deletes 0%-87% slower. N16->N4 shrinking 6%-76% slower.

Node16: tree sizes about the same with art_map being 1%-10% smaller, except for shrinking tests where it reports to be 4x smaller (!). N4->N16 sequential growing 5%-15% faster until 4096 size, when it becomes 30% slower. Random growing 8%-11% faster with a 0% outliers at 512 and 16383 sizes. Sequential inserts 5%-6% faster. Random inserts 1%-10% slower. Scans 5%-30% slower, with much larger variance. Random searches almost identical. Deletes 8%-23% slower. N48->N16 shrinking 3%-6% faster for small trees, 9%-155% slower for large trees.

Node48: tree sizes 2x-4x smaller (!), except for shrinking tests, where it is only slightly smaller. Speed: sequential N16->N48 growing 8% faster for the smallest tree size, equal for the next larger, 80%-103% slower on the larger ones. Random N16->N48: 10% faster for the smallest tree size, 30%-43% slower on the middle sizes, 18% faster on the largest size. Sequential inserts 2%-12% faster. Random inserts 4%-7% faster on small trees, 2%-4% slower on middle-sized ones, 11% faster on the largest ones. Scans 11%-20% slower. Random searches almost identical. Deletes 6%-36% slower, except for sequential delete at 196608 where it's 3% slower, and random delete at 4096, where it's 14% faster, but with extremely unstable performance. N256->N48 shrinking 4%-241% slower, with variance issues.

Node256: tree sizes 10%-20% smaller. Speed: sequential N48->N256 growing 3%-260% slower. Sequential inserts: 23% then 12% slower at the smallest tree sizes, then 14%-35% faster. Random adds: 6%-9%-18%-19% faster. Scans: 12%-51% slower. Random searches almost identical. Deletes: 13%-35% slower for small trees, 24% faster for large trees, except for randomg deletes at 4096 (3% faster) and 196608 (about the same).