On Sat, Jul 19, 2014 at 03:49:04PM +0200, Pavel Machek wrote:
> Hi!
>
> > These patches improve the data structure by adding a radix
> > tree to the linked list structure to improve random access
> > performance from O(n) to O(log_b(n)), where b depends on the
> > architecture (b=512 on amd64, 1024 in i386).
>
> Are you sure? From your other mail, you said you are adding just a
> single page. I'd expect random access performance to go from
>
> O(n) to O(n/1024) in such case?
No, for the 4GB case the additional page is used as an index page into
the block-bitmap pages. On AM64 a page can hold 512 references and a
single block-bitmap page is enough for 128MB of RAM. This means that for
systems with up to 64GB of RAM we can get the block-bitmap page directly
from the index page. For systems with more than 64GB of RAM we need
another level of index pages, and now we need two memory accesses to get
to the block-bitmap page (okay, with this implementation its actually 2
memory accesses per level, because the index-pages refer to a struct
rtree_node which itself contains the pointer to the index/data page).
A two-level radix tree would be enough for systems with up to 32TB of
RAM. After that we need 3 levels, but you can already see that this
doesn't scale linearly anymore but with log_512(n), where n is the
number of block-bitmap pages required.
Joerg
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
