lkml.org 
[lkml]   [1998]   [Sep]   [7]   [last100]   RSS Feed
Views: [more markup]  [less markup]  [headers]  [forward] 
 
Messages in this thread
/
DateMon, 7 Sep 1998 14:31:18 +0400
FromSavochkin Andrey Vladimirovich <>
SubjectRe: [TIMINGS] Re: 2.1.xxx makes Electric Fence 22x slower
On Mon, Sep 07, 1998 at 03:07:51AM -0700, David S. Miller wrote:
>    From: Bruno Haible <haible@ilog.fr>
>    Date: Mon, 7 Sep 1998 12:02:12 +0200 (MET DST)
> 
>    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_.
> 
> All you have shown is that the hash function needs tuning, and nothing
> more.
> 
> Talk to researchers on this topic (I do), tree schemes only begin to
> give you back _lookup_ performance at 1,000 or so entires compared to
> any hash or skiplist scheme.  And trees _never_ give you the
> insert/delete characteristics hash/skiplist schemes do (balancing
> overhead of trees vs. hash's constant time insert delete).
> 
> I picked a suboptimal hash function in my "not ready for prime time,
> untuned" implementation, so shoot me.

Well, I'm finishing a fuzzy hash implementation with find_vma not less
than 20% better than the previous for the case of small number of VMAs.
It's not only the hash function that can be tuned :-)

Best regards
					Andrey V.
					Savochkin

-
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