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

[Hans Reiser <reiser@namesys.com>]

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.

Hans