> I've edited out a few I wish to point out.
>
> 2.1.119 2.1.119 2.1.119
> plain avl fuzzyhash
>
> do_mmap 33 25 19
> do_munmap 18 20 17
> insert_vm_struct 10 23 8
Hello David,
I think one must be careful when looking at some isolated values like this.
What is `8' in one run can easily be `12' in the next run.
Furthermore, in "2.1.119 plain" some functions walked the lists themselves,
whereas in the other two cases they call `find_vma' to do the job. That's
why I have more confidence in the "total mmap.c" times.
> These three contribute highly to Linux's fork, exec, and exit
> latencies. I'd really like to see the smallest numbers possible here.
I agree.
> Really, from all the data I've every been shown, fhash is the only
> scheme which gives the right balance of both worlds, low latency and
> good scalability characteristics.
Here I don't agree. In the common case, as I measured, fuzzyhash has the
same latencies as AVL. (And recall that, among my test, is to configure
a GNU package, which is fork/exec intensive, and the boot-up process as
well.)
And I dispute the "good scalability" claim. In the case of the app David
Gadbois sketched (lots of 64KB VMA segments), the hash function of all
segments returns the same value, thus we are back to n/2 VMA accesses in
each operation on average, as in the linear-list scheme. Whereas AVL has
2*log(n)/log(2) accesses in the _worst_case_.
Bruno
-
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/faq.html