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.
--
To unsubscribe from this list: send the line "unsubscribe reiserfs-devel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
