lexicographic ordering is not always best

lexicographic ordering is not always best

[Hans Reiser]

Suppose that you have small directories, such that the time to do linear 
searching within the directory is not significant.

Suppose that you have a tendency to access files in readdir() order, and 
having files laid out in an order that is the same as the directory 
order is performance valuable.

Suppose that you create files too slowly for allocate on flush to fix 
this problem, and access them too soon for the repacker to fix this problem.

In that case, ordering both directory entries and file bodies in a first 
created first ordered order is optimal.

How much work would it be to create a reiser4 directory plugin to order 
in creation time order?  Could you do this by simply setting the hash 
field always to zero for that plugin, and letting the duplicate key code 
handle things?  If it is trivial to do, it might be useful.  Especially 
for the analysis of the performance of our algorithms on various benchmarks.

Are you ready to work on implementing file body key assignment in order 
of directory entries?

-- 
Hans

Re: lexicographic ordering is not always best

[Nikita Danilov]

Hans Reiser writes:
 > Suppose that you have small directories, such that the time to do linear 
 > searching within the directory is not significant.
 > 
 > Suppose that you have a tendency to access files in readdir() order, and 
 > having files laid out in an order that is the same as the directory 
 > order is performance valuable.
 > 
 > Suppose that you create files too slowly for allocate on flush to fix 
 > this problem, and access them too soon for the repacker to fix this problem.
 > 
 > In that case, ordering both directory entries and file bodies in a first 
 > created first ordered order is optimal.
 > 
 > How much work would it be to create a reiser4 directory plugin to order 
 > in creation time order?  Could you do this by simply setting the hash 
 > field always to zero for that plugin, and letting the duplicate key code 
 > handle things?  If it is trivial to do, it might be useful.  Especially 
 > for the analysis of the performance of our algorithms on various benchmarks.

I do not see how this is possible. Lookup has to find the directory
entry given a name. If directory entries are ordered in the "creation"
order, some component(s) of directory entry key (ones that order
directory entry by creation) are unknown at the lookup time.

The only solutions that come to my mind are either double index
directory entries (this will solve a bunch of other problems as well),
or resort to a sequential scan (this is exactly what ext2 does, and, by
the way ext2 also mostly sorts directory entries by the creation time).

Have I missed something in your proposal?

Nikita.

Re: lexicographic ordering is not always best

[Hans Reiser]

Nikita Danilov wrote:

>Hans Reiser writes:
> > Suppose that you have small directories, such that the time to do linear 
> > searching within the directory is not significant.
> > 
> > Suppose that you have a tendency to access files in readdir() order, and 
> > having files laid out in an order that is the same as the directory 
> > order is performance valuable.
> > 
> > Suppose that you create files too slowly for allocate on flush to fix 
> > this problem, and access them too soon for the repacker to fix this problem.
> > 
> > In that case, ordering both directory entries and file bodies in a first 
> > created first ordered order is optimal.
> > 
> > How much work would it be to create a reiser4 directory plugin to order 
> > in creation time order?  Could you do this by simply setting the hash 
> > field always to zero for that plugin, and letting the duplicate key code 
> > handle things?  If it is trivial to do, it might be useful.  Especially 
> > for the analysis of the performance of our algorithms on various benchmarks.
>
>I do not see how this is possible. Lookup has to find the directory
>entry given a name. If directory entries are ordered in the "creation"
>order, some component(s) of directory entry key (ones that order
>directory entry by creation) are unknown at the lookup time.
>
No, they are 0 (identical, duplicates).

>
>The only solutions that come to my mind are either double index
>directory entries (this will solve a bunch of other problems as well),
>or resort to a sequential scan (this is exactly what ext2 does, and, by
>the way ext2 also mostly sorts directory entries by the creation time).
>
Yes, sequential scan is what I meant.  I do not intend this as the 
default, but merely as an option.

>
>Have I missed something in your proposal?
>
>Nikita.
>
>
>  
>


-- 
Hans