Re: Long `rm` times.

Mikulas Patocka (mikulas@artax.karlin.mff.cuni.cz)
Tue, 1 Jun 1999 19:30:10 +0200 (CEST)

> > I guess it's because of stupid design of ext2 indirect blocks. Indirect
> > blocks are scattered over that 1G. Imagine how long it would take to read
> > 4M of non-contignuous blocks in 1G file. When you delete it immediatelly,
> > it's probably still in buffers.
> >
> > It would be much better to have pairs (position,length) instead of list of
> > all blocks. This would
> > - speed up bmap
> > - save disk space
> > - speed up delete & truncate
> >
> HPFS use position,length pairs. But its a tradeoff, not a clear win.
>
> Consider the case of a huge file with lots of fragments. We want to
> find block x in the last half of the file.
>
> This is quick with ext2. No matter how fragmented, we calculate
> one indirect block, read it, look up one direct block, read
> it, and then we look up the disk block. The number of disk accesses
> to find one particular block is fixed and low, fragmentation won't
> matter.
>
> We can do something similiar with pairs - the indirect block
> would specify that the first direct block have pairs from 0 to x,
> the next have pairs from x+1 to y and so on.
>
> The amount of disk accesses would not increase with this scheme,
> even with severe fragmentation. But it is more cpu intensive.
> We must search the indirect
> and direct blocks instead of doing a simple lookup.

Ext2 is maybe better for random acces on heavily fragmented files. But for
sequential access or when files are not very fragmented (most common case)
it is bad. We once go through HPFS-like tree, remember the current
fragment and on next bmap requests, we just return sector directly
_without_ any bread. However, on ext2, few breads are done on every bmap.
Binary search could be used - it is not so slow (well, my driver doesn't
do it because I'm too lazy :-)

As there are _much_ less sectors spent on allocation info in HPFS, it
saves disk accesses.

Mikulas Patocka

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/