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)
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 exam
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
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, perfec
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
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 eas
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 th
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 pra
Thanks for the fast reply,
On Fri, Mar 19, 2010 at 3:07 PM, Robert Dewar 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 a cleare
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.
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
Jae Hyuk Kwak wrote:
Hi Robert,
On Fri, Mar 19, 2010 at 2:13 PM, Robert Dewar 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
Hi Robert,
On Fri, Mar 19, 2010 at 2:13 PM, Robert Dewar 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 that
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 Michael,
Thank you for the detailed response.
On Fri, Mar 19, 2010 at 9:54 AM, Michael Meissner
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) is fast enough
>>
On 03/18/2010 05:22 AM, Jae Hyuk Kwak wrote:
> On Wed, Mar 17, 2010 at 1:04 PM, Michael Meissner
> 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 woul
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 so
Jae Hyuk Kwak 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 code (-fverbos
Hi Michael,
Thank you for the details.
On Thu, Mar 18, 2010 at 8:17 AM, Michael Meissner
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
On 03/18/2010 05:22 AM, Jae Hyuk Kwak wrote:
> On Wed, Mar 17, 2010 at 1:04 PM, Michael Meissner
> 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 woul
On Wed, Mar 17, 2010 at 1:04 PM, Michael Meissner
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 statements would slow
> down if
Jae Hyuk Kwak wrote:
I haven't heard about "MELT" before and still don't know what exactly
it is. Is it able to deal with this kind of problem?
MELT is a GCC branch and a GCC plugin. It provides a Lispy domain
specific language to code GCC extensions in. More details on the GCC
wiki, in parti
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 o
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 at
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 doe
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.
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 a
27 matches
Mail list logo
