Computational complexity of rm & ls

[Chris Torek]

In article <7919 at chinet.chi.il.us> les at chinet.chi.il.us (Leslie Mikesell)
writes:
>The maximum optimal size probably varies with the OS version.  I've
>been told that directory access becomes much less efficient when
>the directory inode goes to triple indirect blocks (300 files?).

300?!?  (Maybe 300! :-) [read `300 factorial'])

Assuming the SysV file system is unchanged from the V7 file system of
1976 or so (which, for the most part, it is), an inode remembers 13
blocks maximum.  Of these, the first 10 are direct, the 11th is single
indirect, the 12th is double indirect, and the 13th is triple indirect.
(All this from memory of 4.1BSD, and correspondingly suspect.)  If
the block size is 512 bytes (it is either 512 or 1024), and a directory
entry is 16 bytes (it is), the directory first switches to *single*
indirects at 5120 bytes, or 5120/16=320 entries.  Using 1 kbyte blocks
this doubles to 640.

A single indirect block points to up to 170 (I think---this is 512/3)
more blocks (512 bytes each again), so to reach double indirects you
need (10*512 + 170*512)/16 = 5760 entries.  By then you will have run
out of inodes due to the SysV inode eater bug :-) .  With 1024 byte
blocks a single indirect should handle 341 more blocks, for a total
of (10*1024 + 341*1024)/16 = 22464 entries.

4.[23]BSD uses a block size of 4096 or 8192 bytes, and has 12 direct
blocks, so while its directory entries can be larger (but probably
average about the same---an 8 character file name uses roundup(8,4) +
4 + 4 = 16 bytes; 9 to 12 character names use 20 bytes), it takes
either 12*4096=49152 bytes or 12*8192=98304 bytes, or more than 2450
20-byte entries (more than 4950 with 8 kbyte blocks) before it needs
to go to indirects.  (The same, of course, goes for plain files.)
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163)
Domain:	chris at mimsy.umd.edu	Path:	uunet!mimsy!chris