Re: reiser4: discard support

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

On 04/30/2014 07:55 PM, 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:


BTW, (2) is an excess component, since merging of 2 trees
looks like adding one-by-one extents to a tree, and the final
number of extents to discard is n.
So, when using trees, complexity is (1/2)log(n)+ nlog(n/e).


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