Re: [Ext2-devel] Re: Shrinking ext3 directories

Daniel Phillips
2002-06-22T21:00:21Z

On Saturday 22 June 2002 07:53, Andreas Dilger wrote:
> 4) it is probably better to have the most uniform hash function we can
> find than to do lots more block split/coalesce operations, so the
> extra cost of half-MD4 may be a benefit overall

That's the thing: we already know the extra cost of half-MD4 is dominant
here. It only saves about 1.3% of the splitting, and splitting itself is a
small part of overall costs.

Argument (1), "cpus are getting faster all the time" a little weak -
directories are getting bigger all the time too, and... you know, it just
isn't stylish to waste cycles in common operations.

However, I buy the stability and predictability arguments, and we should go
with half-md4 for the alpha-test period. But also, we should see what we can
do to trim some of the fat off half-MD4 without degrading its nice properties
too much. During the same period, I think I see if I can find a better
multiplier for dx_hack_hash, to even out its distribution a bit. Armed with
these results, the release version should use the fastest hash that exhibits
acceptable statistical behaviour.

I do agree there's a lot to be said for going with a hash that has been
analyzed rigorously.

> It would be interesting to re-run this test to create a few million
> entries, but with periodic deletes.

Changing the topic slightly, I'm running the following stupid program to test
for directory growth during steady state operation similar to a mailer:

/* steady.c */

#include <stdlib.h>

int main (int argc, char *argv[])
{
int target = (argc > 2)? strtol(argv[2], 0, 10): 0;
int range = (argc > 3)? strtol(argv[3], 0, 10): 0;
int size = 50, show = argc > 3 && !strncmp(argv[4], "y", 1);
int balance = 0, deletes = 0;
char name[size];

if (!range) return -1;

while (1)
{
snprintf(name, size, "%s%i", argv[1], rand() % range);
if (balance < target)
{
int fd = open(name, 0100);
if (fd >= 0)
{
if (show) printf("create %s\n", name);
close(fd);
balance++;
}
} else
if (!remove(name))
{
if (show) printf("remove %s (%i), ", name, ++deletes);
balance--;
}
}
return 0;
}

when run with:

steady <basename> <count> <range> [y=print output]

it will create up to <count> files with names <basename><rand> with <rand> in
the range 0 to range-1, then it will start alternately deleting and creating
random files. Its algorithm is braindead - it just keeps trying to delete a
random file until it hits one that exists, and on create, it creates a random
file and tries again if it hits one already there. I'm running it now with:

steady foo 10000 1000000000 y

meaning it's working with a 10,000 file, creating/deleting files with names
in the rand foo0 to foo999999999, i.e., a billion possible names. It's a
horribly inefficient thing to do, since it has about a hundred thousand
failures for every success, but it was quick to write. I'm watching for
directory expansion. The directory started at 385024 bytes (38.5 bytes/entry
and grew a block after about 300 steady state remove/create cycles. Another
block was added around 500 cycles. It's up to 1100 cycles now, and hasn't
added another block. It sort of looks like the expansion is getting slower.
This is with dx_hack_hash. I'll let it run overnight to get a feeling of how
urgent the steady-state problem is.

What I expect to find is that directory expansion is slower with half-md4,
perhaps significantly slower. However, even if it is slower, we can't really
tolerate any steady-state expansion at all, so it's no excuse for not
implementing the coalesce.

> Hmm, now that I think about it, split/coalesce operations are only
> important on create and delete, while the hash cost is paid for each
> lookup as well. It would be interesting to see the comparison with
> a test something like this (sorry, don't have a system which has both
> hash functions working right now):
>
> [code]

Yes, good test: performance against name length. Well, I don't plan to try
it just now, since I've run out of time and must get ready for the pilgrimage
to Ottawa.

--
Daniel