Yes, that's true. Unfortunately, random access is exactly the worst case
for accessing a general FAT FS file.
> [One might even check that the container file is consecutive,
> and in that case skip bmap() entirely.]
Yes, that would help. Does this still correspond to the intended purpose ?
You can also get some significant improvement if you only have few (e.g.
< 16) fragments (CPU: O(file_size) -> O(log #fragments), memory (per FAT
FS file): O(1) -> O(#fragments)). Unfortunately, the number of fragments
tends to increase with the file size ... Did anybody do some studies on
the fragmentation of large FAT FS files ?
> But it is easy to change this O(n) into O(log n) with a somewhat larger
> constant, at least for lookup and add.
Of course you can.
However, the basic problem remains that it's an uphill battle - cache misses
get more expensive linearly with the file size (in the general case) and you
probably get more of them too for big files. The FAT FS simply isn't designed
to work well for random access to large files. UMSDOS avoids that problem by
(implicitly) using the inode cache as an intermediate step, so this ugly O(n)
should turn into something more like O(log n).
Also, you have to be very careful with modifications of the cache algorithm.
Any subtle bug won't show up for a long time but may have disastrous
consequences.
I'd certainly see some value in optimizing the FAT cache (provided that its
size is increased at the same time), but I'm rather sceptic about the idea
of using large fragmented FAT FS files as containers for Linux file systems.
- Werner
-- _________________________________________________________________________ / Werner Almesberger, DI-LRC,EPFL,CH werner.almesberger@lrc.di.epfl.ch / /_IN_R_133__Tel_+41_21_693_6621__Fax_+41_21_693_6610_____________________/