On 05/02/2014 01:48 PM, Edward Shishkin wrote:
On 05/02/2014 01:51 AM, Ivan Shapovalov wrote:
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)!)
Why "2*" ?
I suppose they are filled in parallel...
Total complexity (when everything is serialized) is not interesting ;)
If lists look more simple for you, then do it with lists.
Eventually, we'll replace everything with fast-merge trees ;)
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...
"somebody modifying the bitmaps" will wait for commit_mutex.
Have you found where the bitmaps are modified? This is
pre_commit_hook_bitmap().
Again, for me, internals of reiser4 still mostly look
like heavy wizardry. :)
This is because the technical level of reiser4 is very high.
Many very strong scientists contributed to reiser4.
I also don't understand in details how some reiser4 subsystems work.
Once I need details, I open the respective code and read it with the
comments.
The most important thing is general understanding of how it works.
Nobody is able to grok this only by reading reiser4 code before
sleeping. You need to implement at least one feature by your hands.
Yes, it is not easy, and not for everyone. Like every high-level research
in the science...
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
