From mboxrd@z Thu Jan 1 00:00:00 1970 From: Hans Reiser Subject: Re: lexicographic ordering is not always best Date: Tue, 18 Feb 2003 14:10:38 +0300 Message-ID: <3E5214AE.9050102@namesys.com> References: <3E517263.3030504@namesys.com> <15954.4300.300740.395383@laputa.namesys.com> Mime-Version: 1.0 Content-Transfer-Encoding: 7bit Return-path: list-help: list-unsubscribe: list-post: Errors-To: flx@namesys.com In-Reply-To: <15954.4300.300740.395383@laputa.namesys.com> List-Id: Content-Type: text/plain; charset="us-ascii"; format="flowed" To: Nikita Danilov Cc: ReiserFS 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