lkml.org 
[lkml]   [1998]   [Sep]   [7]   [last100]   RSS Feed
Views: [more markup]  [less markup]  [headers]  [forward] 
 
Messages in this thread
/
FromBruno Haible <>
DateMon, 7 Sep 1998 12:02:12 +0200 (MET DST)
SubjectRe: [TIMINGS] Re: 2.1.xxx makes Electric Fence 22x slower
David Miller writes:

> 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

\
 
 \ /
  Last update: 2005-03-22 12:44    [from the cache]
©2003-2008