From mboxrd@z Thu Jan  1 00:00:00 1970
Date: Mon, 29 Sep 1997 21:15:15 -0500
From: G. David Butler gdb@dbSystems.com
Subject: [9fans] adding directory indexes to plan9 file server
Topicbox-Message-UUID: 6718f6ae-eac8-11e9-9e20-41e7f4b1d025
Message-ID: <19970930021515.Ji9j2plFnoE9b-SDx-ZwKmaBSVAS_V3TENbN1BXmzwo@z>

Whew, that was a bunch of work...

I just created 1,000,000 zero length files in a single directory.
The files are named 1,2,3,...,999998,999999,1000000.

term% mkdir test;cd test
term% time makebigdir
101.53u 2416.18s 14443.96r

That is 69 file create(2)s a second!  Remember a create(2) sends
a walk(5) first and if it fails, then a create(5)...

term% time cat . | wc -c
116000000
0.54u 27.15s 355.18r   [yes, some magic happened here too]

Don't try that with 'ls' unless you have some VM!

(My DIRPERBUF is 34 instead of the usual 46 on a PC because I put
NDBLOCK from 6 to 13, so the real number of directory blocks is
at least 29412 instead of 21740.  That is over 115Mb!)

The index overhead is between 1970 and 983 pages depending on
splits during inserts.  In either case, the index depth is 3.
That represents a 6.7% to 3.3% overhead.  Indexes do not put
any limits on the size of a directory.

For the following times the file server is a 100Mhz Pentium w/32Mb
RAM and a 2Gb disk on an adaptec SCSI controller.  The terminal is
a 486 DX4/100.

term% time ls 0
ls: 0: file does not exist
0.00u 0.00s 0.36r

term% time ls 5z
ls: 5z: file does not exist
0.00u 0.01s 0.29r

term% time ls z
ls: z: file does not exist
0.00u 0.01s 0.05r

term% time ls 1
1
0.00u 0.00s 0.03r

term% time ls 2
2
0.00u 0.02s 0.21r

term% time ls 3
3
0.00u 0.03s 0.27r

term% time ls 4
4
0.00u 0.02s 0.24r

term% time ls 5
5
0.00u 0.01s 0.22r

term% time ls 6
6
0.00u 0.02s 0.04r

term% time ls 7
7
0.00u 0.01s 0.16r

term% time ls 8
8
0.00u 0.01s 0.15r

term% time ls 9
9
0.00u 0.01s 0.06r

term% time cat /dev/null > 0
0.00u 0.01s 0.02r

term% time rm 0
0.00u 0.00s 0.05r

term% time cat /dev/null > 5z
0.00u 0.02s 0.02r

term% time cat /dev/null > z
0.00u 0.01s 0.02r

term% time rm 5z
0.00u 0.01s 0.04r

term% time rm z
0.00u 0.00s 0.03r

On to the next project...

David Butler
gdb@dbSystems.com