lkml.org 
[lkml]   [1998]   [Sep]   [7]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
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 13:44    [W:0.087 / U:0.032 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site