Benchmarks

[Juha Nieminen]

Re: Benchmarks

Richard Harter wrote:

Big-O does not make big omega or big theta obsolete. Big omega
is any function asymptotically below the function of interest.

I fail to see how it does *not* make them obsolete.

Following your definition, "the worst case of insertion sort is
O(n^2)" and "the worst case of of insertion sort is Omega(n^2)" are
completely equivalent statements because both define bounds for the
"worst case of insertion sort" function.

Likewise "the best case of insertion sort is O(n)" and "the best case
of insertion sort is Omega(n)" are also completely equivalent.

Given that they specify upper and lower bounds, those are also
completely equivalent to the big-Theta notation.

In general, we can say "the behavior X for algorithm Y is O(f),
Omega(f) and Theta(f)".

[Antoninus Twink]

Re: Benchmarks

On 10 Nov 2008 at 23:07, Juha Nieminen wrote:

Richard Harter wrote:

>Big-O does not make big omega or big theta obsolete. Big omega
>is any function asymptotically below the function of interest.

>
I fail to see how it does *not* make them obsolete.

That's because you don't understand what they mean, and you refuse to
accept your ignorance and find out.

Following your definition, "the worst case of insertion sort is
O(n^2)" and "the worst case of of insertion sort is Omega(n^2)" are
completely equivalent statements because both define bounds for the
"worst case of insertion sort" function.

This is nonsense. They are not equivalent statements, for much the same
reason that "x >= 7" and "x <= 12" are not equivalent statements,
even though they both define bounds for x.

[Kai-Uwe Bux]

Re: Benchmarks

Juha Nieminen wrote:

Richard Harter wrote:

>As others have pointed out, this is seriously misinformed. This
>bit of folklore pops up every once in a while. Where does it
>come from?

>
No, what is folklore is the custom of using the big-O notation to
describe *all* possible asymptotic behaviors of an algorithm. While that
may work colloquially, it's technically incorrect.

Do you have a reference for that? As far as I know, Big-O notation is rooted
in mathematics and can be used to describe the behavior of any function
(regardless where it comes from).

The big-O notation specifies the asymptotic upper bound for the
behavior of the algorithm. It does not specify anything else.

That is clearly false as Big-O notation is used in many places without
reference to any algorithm whatsoever. It is true that Big-O implies an
upper bound. However, that could be an upper bound, e.g., on best case
space complexity.

If the big-O notation could be used to describe *any* asymptotic
behavior for a given algorithm, then please explain to me how it differs
from the big-Omega and big-Theta notations. Wouldn't the big-O make
those obsolete?

No, the definitions of Big-O, Big-Omega, and Big-Theta differ considerably:

If f and g are functions from positive numbers to positive numbers, then

f = O(g) if f(x) < C g(x) for some C>0 and all sufficiently large x

f = Omega(g) if f(x) C g(x) for some C>0 and all sufficiently large x

f = Theta(g) if c g(x) < f(x) < C g(x) for some c>0 and C>0 and all
sufficiently large x.

However, Big-Theta can be defined in terms of the other two:

f=Theta(g) if and only if f=O(g) and f=Omega(g)

E.g.:

n^2 = O( n^2 )
n^2 = O( n^3 )
n^3 = Omega( n^2 )
n^2 = Theta( n^2 + n )


None of the above has any implications whatsoever about where the functions
involved come from. In particular, any of those can be used to talk about

worst case runtime
avergage case runtime
best case runtime
worst case space
average space
best case space


Best

Kai-Uwe Bux

[Paul Hsieh]

Re: Benchmarks

On Nov 10, 10:38 am, Juha Nieminen <nos...@thanks. invalidwrote:

James Kanze wrote:

On Nov 8, 12:27 am, user923005 <dcor...@connx. comwrote:

On Nov 7, 2:47 pm, Juha Nieminen <nos...@thanks. invalidwrote:
Sure.  If hash(x) == return 1; then bad behavior is to be
expected.  The assumption is of maximally cascade free hash
functions like UMAC or Bob Jenkin's hash.

>

Do you have any references on those, particularly with an
implementation?  All I found for UMAC was a reference to book,
and Bob Jenkin's seems more concerned with cryptographic hashing
than anything else.  If these are standard and widely used
algorithms for look-up hashing, I'd like to add them to my set
of hashing benchmarks.

>

(Note that cryptographic hashing and look-up hashing have very
different constraints, and a good hash function for one isn't
necessarily a good hash function for the other.  Also, in
look-up hashing, speed counts.  Taking 10 times more time to get
1% better distribution on the average is a loss.)

The arena of "practical non-cryptographic hash functions" is clearly a
relatively new field. Outside of crypto-hashes, Bob Jenkin's function
and my function, the quality of everything else out there is truly
pathetic.

Bob Jenkins, for a long time, set the standard with his lookup2
function (I think he wrote and publicized it in Dr. Dobb's journal in
1996 or so.) However, in a kind of "first attempt" I was able to
design a hash function myself that was dramatically faster and had
similar quality. (My function passes Bob Jenkins' avalanche test as
well as my own far more stringent bit distribution and correlation
test; Bob's function performs slightly worse on my test.) So its
clear that there is plenty of room for research here if anyone cares
to take the time or put in the effort. Bob rewrote a version of his
function, which apparently comes much closer to the performance of my
function, but I have not gone back to check it.

Bob and I took different approaches. He started with something
cryptographic, and knocked it down to a point where it was faster,
though losing the cryptographic properties that were no longer
required. I instead took some ideas of his, and built a function from
the ground up that has no pedigree from any cryptographic function.
My design took modern CPU architecture into account as well as trying
to get to "the heart of the matter" for hash function quality
requirements. So I started with a framework which I knew would
deliver a high performance result and injected quality into it.

The key point behind both our functions is that they are not only good
quality, they are objectively faster than all the other typically used
hash functions (CRC, Dan Bernstein's ASCII hash, FNV hash, etc). The
only things that even compete with our functions are things people
already know are worthless (like just summing up the bytes.)

This situation has lead to *some* efforts from other people. In
particular the author of the "murmur hash" (or whatever its called) is
a major proponent of his own function which is even faster than my
function, however it also has clear weaknesses and seems quite
affixedly tied to the x86 architecture. Others have used genetic
algorithms to come up with weird stuff in x86 assembly language which
is very hard to analyze.

In short, hunting around in "the literature" is not going to lead to
too much insightful information. Aside from Bob and myself, there has
been very little serious work in high performance hash functions.
That said, both his function and mine are very usable in real world
practical environments.

  I'm pretty sure Jenkin's hashing function (which uses the same
algorithm as his ISAAC random number generator) is faster than anything
you could ever create yourself, having even a fraction of the same quality.

Is that a commentary on what you think of James Kanze's abilities, or
are you just indirectly praising people like Bob Jenkins and myself as
being some kind of untouchable uber-programmers? If the latter, I
would say its likely unwarranted. This problem is wide open for
anyone with good math/programming skills with a good rough idea about
modern CPU performance. Specifically: the mantle is up for grabs for
anyone to come up with a good *64 bit* hash function. Ironically, my
gut feeling is that it should be possible to come up with a function
nearly twice as fast as mine if you can make the assumption that your
platform natively supports 64 bit scalars (which modern systems now
do.) So its not like Bob and I have set some unattainable bar for
performance. (The only thing that prevents *ME* from setting that
high bar again these days is that I have a day job.)

--
Paul Hsieh

http://www.pobox.com/~qed/hash.html

http://bstring.sf.net/

[James Kanze]

Re: Benchmarks

On Nov 10, 8:43 pm, Juha Nieminen <nos...@thanks. invalidwrote:

Andre Kostur wrote:

Not necessarily true.  The big-O could refer to best-case,
average, worst- case, or anything in between.  You just need
to specify it.  As I recall, quicksort is O(n lg n) in the
average case, O(n^2) worst case.  Both say something
interesting about the algorithm.

While you can say that colloquially, it's formally quite
shaky.

Yes and no.

In computational complexity theory big-O is not a generic
notation used to describe some asymptotic behavior of an
algorithm. It's used to specify an upper bound to the
asymptotic behavior of an algorithm.

More or less. It's usually defined in terms of numbers of some
specific operation, or numbers of some specific object, rather
than in terms of runtime or memory. And of course, who ever is
using the term must define the conditions involved. It does
make sense to speak of a "typical big-O", i.e. a value which
holds "most of the time", even if there isn't a very rigorous
definition for "typically" .

Saying, for example, "insertion sort is O(2^n)" is completely
valid. O(n^100) is equally valid. The big-O notation does not
even require for the upper bound to be tight. Any upper bound
is valid as long as the algorithm never behaves slower than
that. However, saying "insertion sort is O(n)" is not valid
because with some inputs insertion sort performs
asymptotically more steps than that.

Even if you say "quicksort is O(n lg n) in average", the upper
bound is still not correct. Even when measuring average
behavior quicksort will behave slower than (n lg n) with some
inputs, and thus the given upper bound is incorrect.

I don't think anyone has ever claimed that "quicksort is O(n lg
n) in average", or typically. The claim is that it is
"typically close to O(n lg n)". And yes, I know: throw in
enough weasel words, and anything is true. In this case,
however, there is some useful (albeit not very precise)
information being communicated: if you use quick sort, it's
highly unlikely that your performance will be significantly
worse than O(n lg n). (More weasel words:-): "highly unlikely"
and "significan tly worse".) The fact remains that I've done a
fair amount of benchmarking of sorting routines, and unless I
did it intentionally (e.g. use the first element for a pivot
with an already sorted array), quick sort was always the
fastest, and the actual plotted curve was pretty close to O(n lg
n).

Likewise the big-Omega notation is used to set a lower bound
to the asymptotic behavior of an algorithm. For example if you
say "insertion sort is Omega(n)", you are telling that
insertion sort never performs less steps than an amount
linearly relative to the size of the input.

Saying "the best case for insertion sort is O(n)" is exactly
as silly as saying "the worst case for insertion sort is
Omega(n^2)". They don't make sense as bounds in these
sentences. They are misused to describe some special cases.

You have to be careful when discussing vocabulary. Different
people use the same words differently. And in the end, there's
no real right or wrong.

--
James Kanze (GABI Software) email:james.kan ze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

[James Kanze]

Re: Benchmarks

On Nov 10, 8:52 pm, Pete Becker <p...@versatile coding.comwrote :

On 2008-11-10 14:43:06 -0500, Juha Nieminen <nos...@thanks. invalidsaid:

Even if you say "quicksort is O(n lg n) in average", the
upper bound is still not correct. Even when measuring
average behavior quicksort will behave slower than (n lg n)
with some inputs, and thus the given upper bound is
incorrect.

You can't ignore the qualifier "on average", which implies
some constraints on input sequences.

That's not my understanding of "on average". My understanding
is that given enough different input sequences, the "average" of
all of the times will be O(n lg n). But as far as I know, that
isn't the case for quicksort. It's been a long time since I
studied this, so there may be some advances, but as I recall,
the mathematical analysis of the average behavior of quicksort
was too complex to be done. All that one could say is that the
results of many trials seemed to indicate that the average
performance wasn't too much greater than O(n lg n), despite a
few outlying values.

Yes, it's O(n^2) for some input sequences, but if you rule out
those input sequences, then it's O(nlogn), and that's all that
"on average" means.

No. For it to hold "on average", you have to consider those
input sequences as well. On average, in this case, means that
they will occur rare enough that they won't have a measurable
effect on the average. (If you do a million different trials,
and one takes 1000 seconds, and all of the others take 10
seconds, what is the average?

Big-oh notation tells you what happens when the input sequence
gets long. It doesn't tell you anything about the contents of
input sequences.

No, but you have to define what you are measuring. Whether you
are measuring worst-case behavior, best-case behavior, average
behavior, or median behavior? Or something else completely,
like memory use. (And of course, you also have to define the
units you're measuring in---seconds, comparisons, comparisons
and swaps...)

--
James Kanze (GABI Software) email:james.kan ze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

[James Kanze]

Re: Benchmarks

On Nov 11, 11:54 am, Pete Becker <p...@versatile coding.comwrote :

It's well understood what sort of input causes O(n^2) behavior.

Really? If I post a quicksort implementation here, could you
give me an algorithm which would generate the worst case?
(I guess there should a smiley here, because I don't think that
that's really what you meant. But just a half of one, because
I'd really like to find such. There are times where you do want
to test worst case.)

--
James Kanze (GABI Software) email:james.kan ze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

[James Kanze]

Re: Benchmarks

On Nov 10, 7:36 pm, Juha Nieminen <nos...@thanks. invalidwrote:

Richard Harter wrote:

As others have pointed out, this is seriously misinformed.
 This bit of folklore pops up every once in a while.  Where
does it come from?

No, what is folklore is the custom of using the big-O notation
to describe *all* possible asymptotic behaviors of an
algorithm. While that may work colloquially, it's technically
incorrect.

The big-O notation specifies the asymptotic upper bound for
the behavior of the algorithm. It does not specify anything
else.

Big-O predates computer algorithms by at least 50 years. Big-O
defines an asymptotic upper bound for a function. That function
can be the number of comparisons in the worst case execution of
quick sort, for a given array size, or it can be the average
number of comparisons, for a given array size, or it can be the
best case, for a given array size. Or it can include data
moves, or it can measure memory use in some unit. What is true
is that it has nothing to do with "algorithms ", per se; it can
only be applied to algorithms when you define a function which
involves an algorithm.

--
James Kanze (GABI Software) email:james.kan ze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

[James Kanze]

Re: Benchmarks

On Nov 10, 7:38 pm, Juha Nieminen <nos...@thanks. invalidwrote:

James Kanze wrote:

On Nov 8, 12:27 am, user923005 <dcor...@connx. comwrote:

On Nov 7, 2:47 pm, Juha Nieminen <nos...@thanks. invalid>
wrote: Sure.  If hash(x) == return 1; then bad behavior is
to be expected.  The assumption is of maximally cascade
free hash functions like UMAC or Bob Jenkin's hash.

Do you have any references on those, particularly with an
implementation?  All I found for UMAC was a reference to
book, and Bob Jenkin's seems more concerned with
cryptographic hashing than anything else.  If these are
standard and widely used algorithms for look-up hashing, I'd
like to add them to my set of hashing benchmarks.

(Note that cryptographic hashing and look-up hashing have
very different constraints, and a good hash function for one
isn't necessarily a good hash function for the other.  Also,
in look-up hashing, speed counts.  Taking 10 times more time
to get 1% better distribution on the average is a loss.)

I'm pretty sure Jenkin's hashing function (which uses the same
algorithm as his ISAAC random number generator) is faster than
anything you could ever create yourself, having even a
fraction of the same quality.

We can easily find out. If someone will post a link to the
algorithm, I'll implement it and measure. I've already got the
harness. (The hash table being used is a template, so all I
need to do is implement a traits class with isEqual and hashCode
functions for std::string. Or just have it derive from
StrIsEqual, which provides the isEqual function. Or just point
me to the algorithm, and I'll translate it myself.)

FWIW: I've got a JenkinsHash already, from
http://burtleburtle.net/bob/hash/doobs.html. It is considerably
worse than any of my own hashing functions or FNV hashing, for
all measured inputs. If this is the one you're talking about,
don't bother. For look-up hashing, it's not particularly good.
(It may be cryptographicly secure, which mine aren't. That's
something I don't know about.)

--
James Kanze (GABI Software) email:james.kan ze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

[Richard Harter]

Re: Benchmarks

On Tue, 11 Nov 2008 06:15:20 -0800 (PST), James Kanze
<james.kanze@gm ail.comwrote:

>On Nov 11, 11:54=A0am, Pete Becker <p...@versatile coding.comwrote :
>

>It's well understood what sort of input causes O(n^2) behavior.

>
>Really? If I post a quicksort implementation here, could you
>give me an algorithm which would generate the worst case?
>(I guess there should a smiley here, because I don't think that
>that's really what you meant. But just a half of one, because
>I'd really like to find such. There are times where you do want
>to test worst case.)

There is a published procedure that is very general that is one
the web somewhere that I can't find at the moment. The essence,
though, is that you use an oracle. It works like this: At each
step you tell me how you're going to pick your pivot, i.e., what
O(1) elements you are going to look at to choose the pivot. I
get to choose the values of the all of the rest. I choose them
so that they are all bigger (smaller) than your pivot. I don't
actually have to set their values until you look at them; I just
have to place bounds on them.


Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.

[Juha Nieminen]

Re: Benchmarks

James Kanze wrote:

>Even if you say "quicksort is O(n lg n) in average", the upper
>bound is still not correct. Even when measuring average
>behavior quicksort will behave slower than (n lg n) with some
>inputs, and thus the given upper bound is incorrect.

>
I don't think anyone has ever claimed that "quicksort is O(n lg
n) in average", or typically. The claim is that it is
"typically close to O(n lg n)". And yes, I know: throw in
enough weasel words, and anything is true. In this case,
however, there is some useful (albeit not very precise)
information being communicated: if you use quick sort, it's
highly unlikely that your performance will be significantly
worse than O(n lg n). (More weasel words:-): "highly unlikely"
and "significan tly worse".) The fact remains that I've done a
fair amount of benchmarking of sorting routines, and unless I
did it intentionally (e.g. use the first element for a pivot
with an already sorted array), quick sort was always the
fastest, and the actual plotted curve was pretty close to O(n lg
n).

I think that what I really misunderstood with "is O(n lg n) in
average" is what is (mathematically ) meant with "average" in this
particular context.

I have understood "upper bound" to mean that the behavior *never*
exceeds that bound. In other words, if g(n) is the upper bound of f(n),
then f(n) is *never* larger than k*g(n), for a sufficiently large k (at
least from a given n forward). From this I understand that if f(n) ever
gets larger than k*g(n), then g(n) is not the true upper bound for f(n).
Even if f(n) does not exceed k*g(n) "in average", if it exceeds it even
once, then g(n) is simply not the correct upper bound.

However, apparently the "in average" in this particular context means
something slightly different. More precisely, the function f(n) is
defined as:

f(n) = the average amount of steps the algorithm performs for an input
of size n (with all possible different inputs of that size)

In this case the f(n) function can indeed have a smaller upper bound
than the worst case for the algorithm in question.

I think the "in average" is a bit confusing.

[Juha Nieminen]

Re: Benchmarks

Paul Hsieh wrote:

> I'm pretty sure Jenkin's hashing function (which uses the same
>algorithm as his ISAAC random number generator) is faster than anything
>you could ever create yourself, having even a fraction of the same quality.

>
Is that a commentary on what you think of James Kanze's abilities, or
are you just indirectly praising people like Bob Jenkins and myself as
being some kind of untouchable uber-programmers?

It wasn't my intention to belittle Kanze's abilities. I used that
expression as a kind of colloquialism. I admit that it can easily be
understood as belittling. I apologize for that.

What I objected to was Kanze's suggestion that a cryptographical ly
strong hashing function may often be significantly slower than a
good-enough hashing function for a generic hash table. In my experience
Jenkin's algorithm is both cryptographical ly strong and very very fast
at the same time (much faster than eg. simple linear congruential
generators, which are usually cryptographical ly extremely weak).

If the latter, I would say its likely unwarranted.

If you say so. But I still admire Jenkin's rng. It's extremely fast
and the randomness is of superb quality.

[Juha Nieminen]

Re: Benchmarks

James Kanze wrote:

>I'm pretty sure Jenkin's hashing function (which uses the same
>algorithm as his ISAAC random number generator) is faster than
>anything you could ever create yourself, having even a
>fraction of the same quality.

>
We can easily find out.

As I commented in the other post, I didn't mean that to be belittling
or as a challenge, but as a colloquial expression. I see now how it can
be understood in the wrong way. Thus I apologize for my poor choice of
words.

[James Kanze]

Re: Benchmarks

On Nov 11, 5:18 am, Paul Hsieh <websn...@gmail .comwrote:

On Nov 10, 10:38 am, Juha Nieminen <nos...@thanks. invalidwrote:

James Kanze wrote:

On Nov 8, 12:27 am, user923005 <dcor...@connx. comwrote:
On Nov 7, 2:47 pm, Juha Nieminen <nos...@thanks. invalid>
wrote: Sure.  If hash(x) == return 1; then bad behavior
is to be expected.  The assumption is of maximally
cascade free hash functions like UMAC or Bob Jenkin's
hash.

Do you have any references on those, particularly with an
implementation?  All I found for UMAC was a reference to
book, and Bob Jenkin's seems more concerned with
cryptographic hashing than anything else.  If these are
standard and widely used algorithms for look-up hashing,
I'd like to add them to my set of hashing benchmarks.

(Note that cryptographic hashing and look-up hashing have
very different constraints, and a good hash function for
one isn't necessarily a good hash function for the other.
 Also, in look-up hashing, speed counts.  Taking 10 times
more time to get 1% better distribution on the average is
a loss.)

The arena of "practical non-cryptographic hash functions" is
clearly a relatively new field.

Yes and no. The problem has certainly been around for awhile,
but you're right that it doesn't seem to have attracted much
interest. The published works I've seen mostly just present a
function, and claim that it is good, with no analysis, and most
of the time with no real comparitive benchmarks either.

Outside of crypto-hashes, Bob Jenkin's function and my
function, the quality of everything else out there is truly
pathetic.

As I said, I'm interested, because I've been collecting
benchmarks of various hashing functions. Post a link to the
algorithm, and I'll add it in.

OK, I just saw a link at the end of your posting. So I've got a
model for your implementation. I'll add it to my tests at the
first possible occasion.

Bob Jenkins, for a long time, set the standard with his
lookup2 function (I think he wrote and publicized it in Dr.
Dobb's journal in 1996 or so.)

According to the link on your page, this is one I've already
tested. And found it to be slower than FNV or my own hash
functions. It is, IMHO, a typical example where being overly
complicated to match a particular machine doesn't pay. The
distribution isn't significantly better than FNV or my own, and
in fact it takes more time (on the machines I have access to) to
calculate.

However, in a kind of "first attempt" I was able to design a
hash function myself that was dramatically faster and had
similar quality.  (My function passes Bob Jenkins' avalanche
test as well as my own far more stringent bit distribution and
correlation test; Bob's function performs slightly worse on my
test.)  So its clear that there is plenty of room for research
here if anyone cares to take the time or put in the effort.
Bob rewrote a version of his function, which apparently comes
much closer to the performance of my function, but I have not
gone back to check it.

What is certain is that there is a lot of folklore floating
around, and very little real research. I'm not really much into
mathematical analysis of functions myself, so I can't do much on
that end. My basic idea was based on linear congruential random
number generators; intuitively, it seemed to me that whatever
made a good random number generator would also make a good
hashing algorithm. I also took into account that the execution
time of the hashing algorithm must be balanced against its
distribution characteristic; multiplying the execution time by
10 to gain 1% better distribution will result in slower
accesses, on the average. In my case, I was (at the time)
working on a machine (an 8086) with very, very slow
multiplication, so I became intrigued with the idea of using a
Mersenne prime as the multiplier (so that the multiplication
could be converted into a shift and a subtraction). And my
algorithm did beat out the few other examples I had at hand at
the time.

That was all a long time ago, but I've never really lost
interest in the subject. When Peter K. Pearons published his
article "Fast Hashing of Variable-Length Text Strings" in the
CACM, I created a small test harness, and compared it with the
others; my own turned out to be several times faster. Some time
later, someone in fr.comp.lang.c+ + mentionned FNV hashing; by
that time, I had my "standard" benchmark harness designed, so I
whipped up a benchmark with that and all of the others I could
find, and wrote up the results in
http://kanze.james.neuf.fr/code/Docs/html/Hashcode.html. Since
then, I've modified my harness to use my own AssocArray class,
rather than the g++ hash_map (so that I could also test with Sun
CC, VC++, etc.), and have added quite a few additional
algorithms. The fundamental results haven't changed, however;
either a FNV or my Mersenne prime function are always amongst
the fastest (depending on multiplication speed and probably a
number of other factors I'm not aware of). The Pearson and the
Jenkens functions (at least the variants I'm using) are,
depending on the data, between 20% and 35% slower.

I've since extended the benchmark program to support
instrumentation . A quick check showed very little difference in
the actual distributions, so the difference is due to the fact
that the Mersenne prime function or FNV are faster to calculate.

Bob and I took different approaches.  He started with
something cryptographic, and knocked it down to a point where
it was faster, though losing the cryptographic properties that
were no longer required.  I instead took some ideas of his,
and built a function from the ground up that has no pedigree
from any cryptographic function. My design took modern CPU
architecture into account as well as trying to get to "the
heart of the matter" for hash function quality requirements.
So I started with a framework which I knew would deliver a
high performance result and injected quality into it.

The key point behind both our functions is that they are not
only good quality, they are objectively faster than all the
other typically used hash functions (CRC, Dan Bernstein's
ASCII hash, FNV hash, etc).  The only things that even compete
with our functions are things people already know are
worthless (like just summing up the bytes.)

It's interesting to note that on a modern machine, FNV or my own
functions do not take any more time than just summing the bytes,
but result in a very good distribution.

I'm pretty sure Jenkin's hashing function (which uses the
same algorithm as his ISAAC random number generator) is
faster than anything you could ever create yourself, having
even a fraction of the same quality.

Is that a commentary on what you think of James Kanze's
abilities, or are you just indirectly praising people like Bob
Jenkins and myself as being some kind of untouchable
uber-programmers?  If the latter, I would say its likely
unwarranted.

I think we both agree that the final word hasn't been written.
I'm curious to see how you code does, however, because on your
web page, you say you find that Bob's function is faster than
FNV, on an Athlon. Where as I find just the opposite, on a wide
variety of machines (Sun Sparc, some older Intel, and now on
both Intel and AMD based Linux boxes.)

FWIW, I just reran one set of tests on my machine here, an AMD
64 bit machine. Jenkins is almost exactly the same as FNV, and
slightly slower than my Mersenne prime hash using 2^7-1 as
multiplier. This was for a set of 8554 symbols extracted from
my code. A second trial with 1259 URL's (extracted from
somewhere, I forget where), did show Jenkins as slightly better.
So maybe it depends on typical length; the URL's are longer, on
the average, than my program symbols.

At any rate, my recommendation still stands: Mersenne primes
with 2^7-1 as multiplier. That seems to give the best results
over a wide variety of data and hardware. But if your algorithm
is significantly faster than Jenkins, it's definitely worth
looking at. I'll add it to my tests.

>This problem is wide open for anyone with good math/programming
>skills with a good rough idea about modern CPU performance.
> Specifically: the mantle is up for grabs for anyone to come up
>with a good *64 bit* hash function. Ironically, my gut feeling
>is that it should be possible to come up with a function nearly
>twice as fast as mine if you can make the assumption that your
>platform natively supports 64 bit scalars (which modern systems
>now do.)

Note that on a modern CPU, I would expect the byte accesses in
FNV or my own algorithms to have very little impact, since the
entire inner loop will be in cache, all intermediate variables
in registers, so the only memory access will be the characters
in the string, and the CPU will find the data in its pipeline
for all of the reads except for the first in each cache line.

So I think that the word length factor is really a red herring.

--
James Kanze (GABI Software) email:james.kan ze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

[user923005]

Re: Benchmarks

On Nov 11, 8:02 am, James Kanze <james.ka...@gm ail.comwrote:

On Nov 11, 5:18 am, Paul Hsieh <websn...@gmail .comwrote:

On Nov 10, 10:38 am, Juha Nieminen <nos...@thanks. invalidwrote:

James Kanze wrote:
On Nov 8, 12:27 am, user923005 <dcor...@connx. comwrote:
On Nov 7, 2:47 pm, Juha Nieminen <nos...@thanks. invalid>
wrote: Sure.  If hash(x) == return 1; then bad behavior
is to be expected.  The assumption is of maximally
cascade free hash functions like UMAC or Bob Jenkin's
hash.
Do you have any references on those, particularly with an
implementation?  All I found for UMAC was a reference to
book, and Bob Jenkin's seems more concerned with
cryptographic hashing than anything else.  If these are
standard and widely used algorithms for look-up hashing,
I'd like to add them to my set of hashing benchmarks.
(Note that cryptographic hashing and look-up hashing have
very different constraints, and a good hash function for
one isn't necessarily a good hash function for the other.
 Also, in look-up hashing, speed counts.  Taking 10 times
more time to get 1% better distribution on the average is
a loss.)

The arena of "practical non-cryptographic hash functions" is
clearly a relatively new field.

>
Yes and no.  The problem has certainly been around for awhile,
but you're right that it doesn't seem to have attracted much
interest.  The published works I've seen mostly just present a
function, and claim that it is good, with no analysis, and most
of the time with no real comparitive benchmarks either.
>

Outside of crypto-hashes, Bob Jenkin's function and my
function, the quality of everything else out there is truly
pathetic.

>
As I said, I'm interested, because I've been collecting
benchmarks of various hashing functions.  Post a link to the
algorithm, and I'll add it in.
>
OK, I just saw a link at the end of your posting.  So I've got a
model for your implementation.  I'll add it to my tests at the
first possible occasion.
>

Bob Jenkins, for a long time, set the standard with his
lookup2 function (I think he wrote and publicized it in Dr.
Dobb's journal in 1996 or so.)

>
According to the link on your page, this is one I've already
tested.  And found it to be slower than FNV or my own hash
functions.  It is, IMHO, a typical example where being overly
complicated to match a particular machine doesn't pay.  The
distribution isn't significantly better than FNV or my own, and
in fact it takes more time (on the machines I have access to) to
calculate.

There is an updated version of Bob Jenkin's hash that is faster.
Another excellent hash is this one:

http://www.geocities.com/drone115b/Goulburn06.pdf

If you are hashing big keys, UMAC is marvelous.

http://fastcrypto.org/umac/2000/perf00.html

However, in a kind of "first attempt" I was able to design a
hash function myself that was dramatically faster and had
similar quality.  (My function passes Bob Jenkins' avalanche
test as well as my own far more stringent bit distribution and
correlation test; Bob's function performs slightly worse on my
test.)  So its clear that there is plenty of room for research
here if anyone cares to take the time or put in the effort.
Bob rewrote a version of his function, which apparently comes
much closer to the performance of my function, but I have not
gone back to check it.

>
What is certain is that there is a lot of folklore floating
around, and very little real research.  I'm not really much into
mathematical analysis of functions myself, so I can't do much on
that end.  My basic idea was based on linear congruential random
number generators; intuitively, it seemed to me that whatever
made a good random number generator would also make a good
hashing algorithm.  I also took into account that the execution
time of the hashing algorithm must be balanced against its
distribution characteristic; multiplying the execution time by
10 to gain 1% better distribution will result in slower
accesses, on the average.  In my case, I was (at the time)
working on a machine (an 8086) with very, very slow
multiplication, so I became intrigued with the idea of using a
Mersenne prime as the multiplier (so that the multiplication
could be converted into a shift and a subtraction).  And my
algorithm did beat out the few other examples I had at hand at
the time.
>
That was all a long time ago, but I've never really lost
interest in the subject.  When Peter K. Pearons published his
article "Fast Hashing of Variable-Length Text Strings" in the
CACM, I created a small test harness, and compared it with the
others; my own turned out to be several times faster.  Some time
later, someone in fr.comp.lang.c+ + mentionned FNV hashing; by
that time, I had my "standard" benchmark harness designed, so I
whipped up a benchmark with that and all of the others I could
find, and wrote up the results inhttp://kanze.james.neu f.fr/code/Docs/html/Hashcode.html.  Since
then, I've modified my harness to use my own AssocArray class,
rather than the g++ hash_map (so that I could also test with Sun
CC, VC++, etc.), and have added quite a few additional
algorithms.  The fundamental results haven't changed, however;
either a FNV or my Mersenne prime function are always amongst
the fastest (depending on multiplication speed and probably a
number of other factors I'm not aware of).  The Pearson and the
Jenkens functions (at least the variants I'm using) are,
depending on the data, between 20% and 35% slower.

I use frog.cpp as my testing harness. Is your hash testing harness
code available?

I've since extended the benchmark program to support
instrumentation .  A quick check showed very little difference in
the actual distributions, so the difference is due to the fact
that the Mersenne prime function or FNV are faster to calculate.
>
>
>
>
>

Bob and I took different approaches.  He started with
something cryptographic, and knocked it down to a point where
it was faster, though losing the cryptographic properties that
were no longer required.  I instead took some ideas of his,
and built a function from the ground up that has no pedigree
from any cryptographic function.  My design took modern CPU
architecture into account as well as trying to get to "the
heart of the matter" for hash function quality requirements.
So I started with a framework which I knew would deliver a
high performance result and injected quality into it.
The key point behind both our functions is that they are not
only good quality, they are objectively faster than all the
other typically used hash functions (CRC, Dan Bernstein's
ASCII hash, FNV hash, etc).  The only things that even compete
with our functions are things people already know are
worthless (like just summing up the bytes.)

>
It's interesting to note that on a modern machine, FNV or my own
functions do not take any more time than just summing the bytes,
but result in a very good distribution.

FNV is not as good as some of the others. It cascades a bit.

I'm pretty sure Jenkin's hashing function (which uses the
same algorithm as his ISAAC random number generator) is
faster than anything you could ever create yourself, having
even a fraction of the same quality.

Is that a commentary on what you think of James Kanze's
abilities, or are you just indirectly praising people like Bob
Jenkins and myself as being some kind of untouchable
uber-programmers?  If the latter, I would say its likely
unwarranted.

>
I think we both agree that the final word hasn't been written.
I'm curious to see how you code does, however, because on your
web page, you say you find that Bob's function is faster than
FNV, on an Athlon.  Where as I find just the opposite, on a wide
variety of machines (Sun Sparc, some older Intel, and now on
both Intel and AMD based Linux boxes.)
>
FWIW, I just reran one set of tests on my machine here, an AMD
64 bit machine.  Jenkins is almost exactly the same as FNV, and
slightly slower than my Mersenne prime hash using 2^7-1 as
multiplier.  This was for a set of 8554 symbols extracted from
my code.  A second trial with 1259 URL's (extracted from
somewhere, I forget where), did show Jenkins as slightly better.
So maybe it depends on typical length; the URL's are longer, on
the average, than my program symbols.

Is your Mersenne prime hash based on the Mersenne twister RNG or are
just just big Mersenne primes as a large prime for modulus operations
with a very long period?

At any rate, my recommendation still stands: Mersenne primes
with 2^7-1 as multiplier.  That seems to give the best results
over a wide variety of data and hardware.  But if your algorithm
is significantly faster than Jenkins, it's definitely worth
looking at.  I'll add it to my tests.
>

This problem is wide open for anyone with good math/programming
skills with a good rough idea about modern CPU performance.
 Specifically: the mantle is up for grabs for anyone to come up
with a good *64 bit* hash function.  Ironically, my gut feeling
is that it should be possible to come up with a function nearly
twice as fast as mine if you can make the assumption that your
platform natively supports 64 bit scalars (which modern systems
now do.)

>
Note that on a modern CPU, I would expect the byte accesses in
FNV or my own algorithms to have very little impact, since the
entire inner loop will be in cache, all intermediate variables
in registers, so the only memory access will be the characters
in the string, and the CPU will find the data in its pipeline
for all of the reads except for the first in each cache line.
>
So I think that the word length factor is really a red herring.

I think it is a good idea to test everything, and then later on retest
it all because assumptions are based on models that can change over
time.