mirror of https://lore.kernel.org/lkml/
 help / color / mirror / Atom feed
From: Patrik Hagglund <patha@ida.liu.se>
To: "David S. Miller" <davem@dm.cobaltmicro.com>
Cc: linux-kernel@vger.rutgers.edu
Subject: Re: [TIMINGS] Re: 2.1.xxx makes Electric Fence 22x slower
Date: Fri, 11 Sep 1998 13:13:24 +0200	[thread overview]
Message-ID: <199809111113.NAA06473@portofix.ida.liu.se> (raw)
In-Reply-To: Your message of "Thu, 10 Sep 1998 18:18:27 PDT." <199809110118.SAA27332@dm.cobaltmicro.com>

David S. Miller wrote:

>   Date: Thu, 10 Sep 1998 22:22:32 +0100
>   From: "Stephen C. Tweedie" <sct@redhat.com>
>
>   David, not only is the fuzzy hash O(n) (with low constant) for lookup,
>   it is also O(n) for insert, requiring insertion onto two separate
>   ordered lists...
>
> No it isn't, for the insert case you have to find the neighbours
> anyways so the cost of a lookup is what you eat and this is an
> unavoidable overhead no matter what algorithm you use.

I don't think your arguments make sense. I think you can avoid finding
the neighbors (explicitly) in insert by coding it differently.
Unfortunately, I'm to busy to produce any code right now.

One the other hand, the argument that the algorithm is O(n) (instead
of O(log n)) doesn't say that much unless we are talking of really big
n:s (because of the low constant), which as I understood was not the
case here.

By the way, I just found out that the very first Forth implementation
also used a "fuzzy hashing" data structure to implement its
dictionary. See http://www.dnai.com/~jfox/f70c5.html.

Regards,
Patrik Hägglund

-
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

           reply	other threads:[~1998-09-11  8:33 UTC|newest]

Thread overview: expand[flat|nested]  mbox.gz  Atom feed
 [parent not found: <199809110118.SAA27332@dm.cobaltmicro.com>]

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=199809111113.NAA06473@portofix.ida.liu.se \
    --to=patha@ida.liu.se \
    --cc=davem@dm.cobaltmicro.com \
    --cc=linux-kernel@vger.rutgers.edu \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox

all inboxes | Powered by JetHome®