Hi,
the discussion so far did omit one specific aspect. When comparing two
implementations for a switch, you have to compare the full code. For the hash
you have to include the code to calculate the hash function. This might be more
code than a simple tree lookup.
The example function:
public
Unruh, Erwin wrote:
Hi,
the discussion so far did omit one specific aspect. When comparing two
implementations for a switch, you have to compare the full code. For the hash
you have to include the code to calculate the hash function. This might be more
code than a simple tree lookup.
The
On 03/22/2010 12:43 PM, Robert Dewar wrote:
the code for computing the hash has to be taken into account, but
nothing else than actual benchmarks will give an accurate
comparison.
I agree. I'd also like to point out that as it is not very difficult
to do these benchmarks, the proponent(s)
Jae Hyuk Kwak wrice...@gmail.com writes:
[...]
Is that true that current implementation of gcc on i386 optimizes
switch statement with decision tree?
I was expecting somebody who can confirm this.
You can see for yourself by writing a variety of switch{} statements
and observing the assembly
Let me correct my mistake.
If I understood correctly, your point is that O(log N) is fast enough
because the size of switch is small in practice.
But I am still not convinced that using hash table would not increase the
speed.
As we know hash table requires O(N) only.
There must be some
On 03/18/2010 05:22 AM, Jae Hyuk Kwak wrote:
On Wed, Mar 17, 2010 at 1:04 PM, Michael Meissner
meiss...@linux.vnet.ibm.com wrote:
Note, that many hash tables are computed by the modulus operation, which is
often fairly expensive (and on machines without a hardware divide unit,
requiring a
Hi Michael,
Thank you for the detailed response.
On Fri, Mar 19, 2010 at 9:54 AM, Michael Meissner
meiss...@linux.vnet.ibm.com wrote:
On Thu, Mar 18, 2010 at 05:10:18PM -0700, Jae Hyuk Kwak wrote:
Hi Michael,
Thank you for the details.
If I understood correctly, your point is that O(log N)
Jae Hyuk Kwak wrote:
For the issue of Modulus operation, it does not need to be divide or
hardware modulus operation.
Let me give you an example here:
13 % 2 = 1
13 (2-1) = 1
Yes, of course, we all know that, and of course the compiler does
these simple optimizations. However, for computing
Hi Robert,
On Fri, Mar 19, 2010 at 2:13 PM, Robert Dewar de...@adacore.com wrote:
Jae Hyuk Kwak wrote:
For the issue of Modulus operation, it does not need to be divide or
hardware modulus operation.
Let me give you an example here:
13 % 2 = 1
13 (2-1) = 1
Yes, of course, we all know
Jae Hyuk Kwak wrote:
Hi Robert,
On Fri, Mar 19, 2010 at 2:13 PM, Robert Dewar de...@adacore.com wrote:
Jae Hyuk Kwak wrote:
For the issue of Modulus operation, it does not need to be divide or
hardware modulus operation.
Let me give you an example here:
13 % 2 = 1
13 (2-1) = 1
Yes, of
On 19/03/2010 21:13, Robert Dewar wrote:
Jae Hyuk Kwak wrote:
For the issue of Modulus operation, it does not need to be divide or
hardware modulus operation.
Yes, of course, we all know that, and of course the compiler does
these simple optimizations. However, for computing hashes you
On 19/03/2010 22:07, Robert Dewar wrote:
You miss my point, doing a mod with 256 is an AWFUL hash algorithm
since it only uses the low order 8 bits!
This statement is only true contingent on a number of significant
assumptions you haven't stated - assumptions which can easily be violated.
Thanks for the fast reply,
On Fri, Mar 19, 2010 at 3:07 PM, Robert Dewar de...@adacore.com wrote:
In many situations, hash tables turn out to be more efficient than
search trees or any other table lookup structure.
The above quote from Wikipedia is indeed misleading because it does
not make
Dave Korn wrote:
Please, nobody bring up the old saw that prime numbers are a good choice for
hashtable sizes. They aren't, they're a crude workaround for a poor hash
function.
Well on a machine with a fast modulus operation, the crude workaround
is often the most efficient algorithm in
By the way, in practice I have found that in many situations, the
input to hash functions is nowhere near pseudo-random, e.g. this
is very much true of identifiers in programs, so the best hash
algorithm is often one that is specialized for the particular
non-pseudo-random domain.
Of course in
Dave Korn wrote:
On 19/03/2010 22:07, Robert Dewar wrote:
You miss my point, doing a mod with 256 is an AWFUL hash algorithm
since it only uses the low order 8 bits!
This statement is only true contingent on a number of significant
assumptions you haven't stated - assumptions which can
Jae Hyuk Kwak wrote:
A quote from this article:
... the switch very efficiently, even constructing a hash table if this
method of switching is ...
Yes, it does. Such a old paper mentioned it and we are still not doing it.
So it makes me wonder why.
Why? Perhaps because it is not helpful
Jae Hyuk Kwak wrote:
Now we have a switch statement that has 400 cases or whatever.
switch ( valueFormUser )
{
case 0: do1(); break;
case 1: do2(); break;
case 2: do3(); break;
...
case 399: do399(); break;
default: break;
Well clearly if you have 400 cases like this,
On 03/18/2010 05:22 AM, Jae Hyuk Kwak wrote:
On Wed, Mar 17, 2010 at 1:04 PM, Michael Meissner
meiss...@linux.vnet.ibm.com wrote:
Note, that many hash tables are computed by the modulus operation, which is
often fairly expensive (and on machines without a hardware divide unit,
requiring a
Hi Michael,
Thank you for the details.
On Thu, Mar 18, 2010 at 8:17 AM, Michael Meissner
meiss...@linux.vnet.ibm.com wrote:
Note, that many hash tables are computed by the modulus operation, which is
often fairly expensive (and on machines without a hardware divide unit,
requiring a
On Wed, Mar 17, 2010 at 1:04 PM, Michael Meissner
meiss...@linux.vnet.ibm.com wrote:
Note, that many hash tables are computed by the modulus operation, which is
often fairly expensive (and on machines without a hardware divide unit,
requiring a function call). I would expect many switch
Thank you Basile.
The article you pointed is exactly what I wanted to find.
The paper summarized switch optimization very well, and it enlightened me.
I am also glad that it mentioned imperfect and perfect hash for switch
statement.
Unfortunately, the super-optimization that the paper suggests
I found that I had a wrong assumption on this issue.
In order to use Perfect Hash Table, we need to know every key values
at compile time, but the key values are determined at run-time so that
it is not feasible idea.
On my project, however, the key values were fixed amount, so that I
confused
On 15/03/2010 07:19, Jae Hyuk Kwak wrote:
I think that for the speed optimization, perfect hash way is the
best candidate after jump table if it is applicable.
It should be pointed out that your article contains a false assumption
about how fast the various options are relative to each
Hello, GCC developers.
I'm not sure whether this is a proper mail address to talk about this or not.
But I am giving a shot.
Last week, I was pondering a way to get Enum values from other unique
values like string and integer.
My thought reached at an idea of using Hash table as usual..
In
Jae Hyuk Kwak wrote:
Hello, GCC developers.
In addition, I found that switch statement can use Hash Table rather
than just replacing with else if.
Besides using jump table, Hash Table can increase speed.
Hash table idea can alleviate the problem of a huge size of jump table as well.
It is
26 matches
Mail list logo
