Any time you make a tree with the same number of nodes less balanced you
increase its average depth. Layering makes the tree less balanced.
Anyone with balanced tree experience knows that making the tree less
balanced is a major error. Actually, the math for stating this
correctly is quite complex, and caching makes it more complex. I don't
have the time to say more than it is generally understood that you don't
want to unbalance trees, and this popular wisdom has a basis, sorry, I
need to go write some code.
> Hans may be wrong, but you are obviously wrong. log(n) is not very
> different from 2 log(sqrt(n)), but there is obviously an extra
> layer with an extra cost.
>
> There are two parts to this, path lookup and block lookup.
>
> Normal paths, paths that extend into kernel-supported multi-fork files,
> and paths that extend into *.doc files all form the same kind of tree.
> When using a *.doc file though, there must be _two_ hash tables for
> lookup cache. (kernel and user may not share) Clearly two hash table
> lookups will take longer than one, even if the one would need to be
> larger. At the extreme, P hash table lookups for P objects will be O(P).
>
> Let's consider a document with P parts, each composed of B blocks.
> >From the name lookup, already we have the root of the allocation tree
> used for the desired part. When operating directly on a block device
> (via kernel support), block lookups are O(log(B)). When operating
> within a normal file, access performance is much worse. You start
> with the above, but every one of those blocks must also be looked
> up with a cost of O(log(B*P)). This is the filesystem overhead.
> So the total is O(log(B)+log(B*P)), also known as
> O( log(P) + 2*log(B) ). That is much worse than O(log(B)).
>
> Oh, that applies to the path lookup too. Normal kernel-supported
> directories are done on the physical media. So the part of a path
> lookup that occurs within a userspace document is going to be
> slower by a factor of O(log(B*P)).
>
> >> Recovery is necessarily much uglified, more than twice as ugly,
> >> and this makes performance worse since performance normally has
> >> recovery as the primary crippling factor that prevents the use
> >> of various desired algorithms.
>
> I like this comment. With a normal filesystem and normal compound
> document files, you really should run fsck.doc on all your files
> after a system crash. Kernel-supported compound documents let one
> fsck handle everything at once. I expect fewer bugs from the single
> tool, since it can fix document and filesystem structure with mostly
> the same code. I also expect better performance for the same reasons
> as I listed above.
>
>
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/