[lkml]   [1998]   [Sep]   [5]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    Subject[TIMINGS] Re: makes Electric Fence 22x slower

    Here are timings of the three alternatives, for the "common" case.
    At the end, you find also some discussion of the many-vmas case.

    I did the following experiment: Compiled each of

    * plain 2.1.119
    * 2.1.119 with AVL trees,
    * 2.1.119 with fuzzy hashing patch from Andrey.

    For the sake of profiling, I made `find_vma' notinline, and the auxiliary
    functions inline, so they don't show up in the histogram. For each of
    them, I took the profiling over the following actions:

    - let it boot,
    - log in and start X with fvwm and an xterm,
    - start apache,
    - start netscape v3 and browse four directories and one 24k html file,
    - unpack, configure and build a GNU package (gperf), this calls g++,
    - finally "readprofile -v -m /".

    Here are the figures.

    2.1.119 2.1.119 2.1.119
    plain avl fuzzyhash

    vm_enough_memory 4 4 6
    vma_insert_hash - - 6
    vma_remove - - 3
    sys_brk 6 6 8
    do_mmap 33 25 19
    get_unmapped_area 6 2 3
    find_vma 27 44 67
    unmap_fixup 4 1 6
    do_munmap 18 20 17
    build_mmap_avl - 13 -
    sys_munmap 1 0 1
    exit_mmap 14 5 13
    insert_vm_struct 10 23 8
    merge_segments 17 36 28

    total of mmap.c 140 179 185

    total of kernel 6783 6806 6661


    * AVL and fuzzyhash have equal timings, within the standard deviation.(*)

    * Both are about 30% slower than plain 2.1.119. The mmap.c code percentage
    in the total system time thus increases from 2.1% to 2.6%.

    Now for the many-vmas case: In a task with n VMAs, a single VMA operation
    (lookup, insert, delete) costs

    * "Plain" on average: n/2 VMA accesses.
    worst case: n VMA accesses.

    * "Fuzzyhash" effectively uses 16 ordered lists instead of 1 ordered list,
    hence on average: n/32 VMA accesses.
    worst case: n VMA accesses.
    The worst case will happen when a program allocates only 64KB aligned

    * "AVL" on average: log(n)/log(2) accesses,
    worst case: log(n)/log(2) accesses for lookup,
    2*log(n)/log(2) for insert/delete.

    So, AVL scales better for large mmap uses. To make "fuzzyhash" scale
    better, you would have to increase the number of lists - a traditional
    space-time tradeoff. And then AVL still behaves much better in some cases -
    say, 2000 64KB-aligned 64KB-sized VMAs.


    (*) A math book tells me that if the sum of N samples comes out to be N*p,
    then the standard deviation is sqrt(N*p*(1-p)). In our case, N = 6800,
    p = 0.0206, hence the standard deviation is about 13.5.

    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to
    Please read the FAQ at

     \ /
      Last update: 2005-03-22 13:44    [W:0.023 / U:3.496 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site