From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 14885 invoked by alias); 16 Mar 2010 01:32:43 -0000 Received: (qmail 14876 invoked by uid 22791); 16 Mar 2010 01:32:42 -0000 X-SWARE-Spam-Status: No, hits=-0.1 required=5.0 tests=AWL,BAYES_00,SARE_MSGID_LONG40,SPF_NEUTRAL X-Spam-Check-By: sourceware.org Received: from fencepost.gnu.org (HELO fencepost.gnu.org) (140.186.70.10) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Tue, 16 Mar 2010 01:32:38 +0000 Received: from mail.gnu.org ([199.232.76.166]:45392 helo=mx10.gnu.org) by fencepost.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1NrLe9-0003Li-1w for gcc@gnu.org; Mon, 15 Mar 2010 21:32:37 -0400 Received: from eggs.gnu.org ([140.186.70.92]:56530) by monty-python.gnu.org with esmtps (TLS-1.0:RSA_AES_256_CBC_SHA1:32) (Exim 4.60) (envelope-from ) id 1NrLVc-0003w5-4m for gcc@gnu.org; Mon, 15 Mar 2010 21:23:48 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1NrLVZ-0006td-7y for gcc@gnu.org; Mon, 15 Mar 2010 21:23:47 -0400 Received: from mail-iw0-f175.google.com ([209.85.223.175]:63355) by eggs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1NrLVZ-0006tX-5D for gcc@gnu.org; Mon, 15 Mar 2010 21:23:45 -0400 Received: by iwn5 with SMTP id 5so599956iwn.24 for ; Mon, 15 Mar 2010 18:23:44 -0700 (PDT) MIME-Version: 1.0 Received: by 10.231.191.131 with SMTP id dm3mr760407ibb.45.1268702623305; Mon, 15 Mar 2010 18:23:43 -0700 (PDT) In-Reply-To: <8ac33cd71003150019u6d30acbfp2fb1493bf7ebb17@mail.gmail.com> References: <8ac33cd71003141343g7ae78185s378fd52205e2deb1@mail.gmail.com> <4B9D6A36.6050802@starynkevitch.net> <8ac33cd71003150019u6d30acbfp2fb1493bf7ebb17@mail.gmail.com> Date: Tue, 16 Mar 2010 01:41:00 -0000 Message-ID: <8ac33cd71003151823h51c7e22dte9074169591dd7d1@mail.gmail.com> Subject: Re: Hash Function for "switch statement" From: Jae Hyuk Kwak To: gcc@gnu.org Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 2) X-detected-operating-system: by monty-python.gnu.org: GNU/Linux 2.6 (newer, 3) Mailing-List: contact gcc-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-owner@gcc.gnu.org X-SW-Source: 2010-03/txt/msg00164.txt.bz2 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 that point. I'm sorry... Jay On Mon, Mar 15, 2010 at 12:19 AM, Jae Hyuk Kwak wrote: > 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 > 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 =C2=A0paper "A Superoptimizer >> Analysis of Multiway Branch Code Generation" by Roger A. Sayle in GCC su= mmit >> 2008 proceedings. www.gccsummit.org/2008/gcc-2008-proceedings.pdf >> >> Regards. >> -- >> Basile STARYNKEVITCH =C2=A0 =C2=A0 =C2=A0 =C2=A0 http://starynkevitch.ne= t/Basile/ >> email: basilestarynkevitchnet mobile: +33 6 8501 2359 >> 8, rue de la Faiencerie, 92340 Bourg La Reine, France >> *** opinions {are only mines, sont seulement les miennes} *** >> >