vma * vma_low_byte[256];
inline vma * treefind(vma * treeroot, uint32 vma_key)
{
/* usual avl lookup */
}
vma * vmafind(vma ** vma_low_byte, uint32 vma_key)
{
return treefind(vma_low_byte[vma_key & 0x000000FF], vma_key);
}
Would a structure like this work, instead of the < 32 linear list
traversal and > 32 single avl tree? You get an avl tree under each
8-bit low byte partition of the theoretic search space. Pathological
worst case is avl efficiency + some tiny array lookup overhead if all
vma nodes end up with the same low byte value, which can only happen
up to a total of 256 nodes, and somewhere in between direct array
indexing and single avl tree if you have nodes not all in the same low
byte partition. For an application that uses enough vma structures to populate
all 256 trees, the 8-bit index gives you a jump on the search space
partition on the first lookup, improving worst case (in terms
of total vma allocation per process) performance at not much cost to the
case with a small number of nodes thus indexed.
Regards, Clayton Weaver cgweav@eskimo.com (Seattle)
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/faq.html