On Wednesday 30 April 2014 at 19:51:03, Edward Shishkin wrote: > On 04/30/2014 05:04 PM, Ivan Shapovalov wrote: > [...] > > >> There is a ready implementation of rb-trees in the kernel (see > >> ./lib/rbtree.c, > >> ./lib/rbtree_test.c). Could you please take a look at this? > > > > I've checked it already. Well, in case of trees: > > - combined extent insertion+adjacent extent merge complexity is > > O(n*log(n)) > > Actually, this is: > > 1) Add n extents one-by-one to empty tree: > log(1) + log(2) + ... + log(n-1) > > 2) Merge 2 trees of n extents: > log(n) + log(n+1) + ... + log(2n-1) > > Total: log(1*2*...*2n-1) = log((2n-1)!) > > in accordance with Stirling's formula: > > log((2n)!) = log(((2n)^(1/2))*(2n/e)^n) = > = (1/2)*log(2n) + n*log(2n/e) < n + n*log(n) Hm. Consider we fill two data structures with N extents each, then merge these two data structures and prepare the resulting one for traversal (for lists it will be sorting, for trees that's no-op). For trees: 1) Adding 2*log((n-1)!) 2) Merging log((2n-1)!/(n-1)!) 3) Sorting none Total: log((2n-1)!) + log((n-1)!) For lists: 1) Adding 2N 2) Merging constant 3) Sorting 2N*log(2N) Total: 2N+2N*log(2N) Quick testing in WolframAlpha shows that, if these estimations are correct, lists tend to have lesser complexity starting with approx. N=160. > > Since atoms can be merged in parallel, we have that > trees work better than lists. Also tree of extents has > better memory consumption because of merging extents. > > > against O(n+n*log(n)) in lists; > > > > - joining two trees is not less than O(log(n)) against O(1) in lists. > > > > So I can't see any benefit in using trees, and join performance is a > > downside of these. Am I missing something? > > [...] > > > Why after reiser4_invalidate_list()? I thought that it should be > > called between reiser4_write_logs(), but before reiser4_invalidate_list(). > > OK, insert before. I think, it doesn't matter, since we don't look > at this list when issuing discard requests, no? :) I just don't understand what implications does that function have. It seems to mess with jnodes, and I can imagine that this leads to races with somebody modifying the bitmaps while issue_discard_requests() tries to read them to check discard extents... Again, for me, internals of reiser4 still mostly look like heavy wizardry. :) Thanks for guidance, -- Ivan Shapovalov / intelfx / > > > And why not after all reiser4_invalidate_list() calls? > > > >> Thanks, > >> Edward. > >> P.S.: You'll need to set up a debugging environment. Take a look at this: > >> http://bipinkunal.blogspot.cz/2012/05/kgdb-tutorial.html > >> Do you have a second machine with a serial port? > > > > No, I don't. Will a VM suffice? > > Yes, if it works for you.. > > Thanks, > Edward.
Attachment:
signature.asc
Description: This is a digitally signed message part.
