Re: [reiserfs-dev] Re: Ext2 directory index: ALS paper and benchmarks

From: Hans Reiser (
Date: Sat Dec 08 2001 - 14:55:06 EST

Ragnar Kj°rstad wrote:

>So, I think the _only_ way to get the optimal performance for a growing
>directory is to do allocation and ordering by creating-time.
We could set the key to the starting packing locality plus starting name
hash, check to see if object with that key already exists, and then if
it does already exist we use a generation counter as originally planned
(though now it must start at some number large enough to avoid collision
with the previous technique, which can happen because generation
counters soak up some bits). This way in most practical situations (the
99% case where you don't have lots of files all created with the same
name in the same directory and renamed to a variety of other things) we
win performance-wise. For the 1% case, we can merely perform as well as
we do now. Comments? Maybe this could work..... Hate being slower
than ext2 at ANYTHING.....;-)

I wonder if Daniel is showing that the cost of our having to slide a
whole node sideways for every directory entry insertion is significant.
 I'd better wait for some benchmarks before concluding. Leaving
airholes in directories is one of those optimizations we are putting off
until after v4 is very stable (which means fully coded;-) ).

Daniel, you didn't mention though whether leaking collision bits is a
problem for Htrees. Is it? Do you need to rehash every so often to
solve it? Or it is rare enough that the performance cost can be ignored?

Interesting work you do Daniel, good work.


To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
More majordomo info at
Please read the FAQ at

This archive was generated by hypermail 2b29 : Sat Dec 15 2001 - 21:00:13 EST