On Mon 2014-07-21 10:32:11, Joerg Roedel wrote:
> 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.
Ok, so you have sped it up from O(n) to O(log(n)) speed, and increased
memory requirements from O(n) to O(n * log(n)), right?
does enough_swap() or reqd_free_pages() need to be updated?
Best regards,
Pavel
--
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures)
http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html
--
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/
