Re: reiser4: discard support

[Edward Shishkin <edward.shishkin@gmail.com>]

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)

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? :)

 >
 > 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.