This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: Hash Function for "switch statement"
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 doesn't
adopt any of hash table ways. In addition, the paper skimmed the
advantage of perfect hash table and it didn't even mention minimal
perfect hash table at all.
I think that for the "speed" optimization, perfect hash way is the
best candidate after jump table if it is applicable. I am currently
working on PlayStation3 game development, and we don't want to use
branch operation. Since 3d games value relatively more on speed than
space, I am still interested on perfect hash for switch statement,
because it is more generic than others the paper mentioned. It will
also require (possibly) zero branching. It would be not only my
personal preference but also the favorite of most game developers.
As usual for 3d game programming process, we have pre-calculation
steps for graphics data. During the process I am thinking to add one
more process that generates perfect hash table. The manual
implementation of perfect hash table as an alternative mean for switch
statement does not seem hard. So I may do it by myself without too
much pain, but It can make my job easier if gcc can play the role.
I wish to see gcc can adopt any of better switch optimization ways in
near future.
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?
Thank you anyway.
Without the reply mail, I couldn't be satisfied this much. :-)
Regards,
Jay
On Sun, Mar 14, 2010 at 3:59 PM, Basile Starynkevitch
<basile@starynkevitch.net> wrote:
> 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 much more complex than that. Read the Âpaper "A Superoptimizer
> Analysis of Multiway Branch Code Generation" by Roger A. Sayle in GCC summit
> 2008 proceedings. www.gccsummit.org/2008/gcc-2008-proceedings.pdf
>
> Regards.
> --
> Basile STARYNKEVITCH Â Â Â Â http://starynkevitch.net/Basile/
> email: basile<at>starynkevitch<dot>net mobile: +33 6 8501 2359
> 8, rue de la Faiencerie, 92340 Bourg La Reine, France
> *** opinions {are only mines, sont seulement les miennes} ***
>