On Tuesday 18 January 2005 04:00, Jacob Dall wrote:
> Hello Charles,
>
> All file names are on a 8.3 format, and NO, I'm not using
> SHORT_NAMES_IN_RAM.
>
> I've just recompiled my project defining CONFIG_YAFFS_SHORT_NAMES_IN_RAM,
> but unfortunately I notice no change in time used to perform the dumpDir().
>
> The files I'm listing, was written before I defined short names in RAM. In
> this case, should one expect the operation to take less time?
>
> The CPU I'm running this test on, is comparable to a Pentium I-200MHz.


NB This only applies to yaffs_direct, not to Linux.

I did some tests using yaffs direct as a user application on a ram emulation 
under Linux.

This too showed slowing. I did some profiling with gprof which pretty quickly 
pointed to the problem...

The way yaffs does the directory searching is to create a linked list of 
items found so far in the DIR handle. When it does a read_dir, it has to walk 
the list of children in the directory and check if the entry in in the list 
of items found so far. This makes the look up time increase proportional to 
the square of the number of items found (O(n^2)) so far ( ie. each time it 
looks at more directory entries as well as compare them to a longer "already 
found" list).

The current implementation could be sped up somewhat by using a balanced 
binary tree for the "found list". This would reduce the time to O(n log n). I 
could be motivated to do something about this but it is not a current 
priority for me.

The other approach is the weasle approach. Don't use such large directories. 
but rather structure your directory tree to use smaller sub-directories.

-- Charles