From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 3905 invoked by alias); 11 Jul 2006 10:03:25 -0000 Received: (qmail 3897 invoked by uid 22791); 11 Jul 2006 10:03:24 -0000 X-Spam-Check-By: sourceware.org Received: from mailgate.hob.de (HELO mailgate.hob.de) (62.91.19.101) by sourceware.org (qpsmtpd/0.31) with ESMTP; Tue, 11 Jul 2006 10:03:22 +0000 Received: from localhost (localhost.localdomain [127.0.0.1]) by mailgate.hob.de (Postfix) with ESMTP id A33D51D37C; Tue, 11 Jul 2006 12:03:19 +0200 (CEST) Received: from mailgate.hob.de ([127.0.0.1]) by localhost (mailgate.hob.de [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 04265-09; Tue, 11 Jul 2006 12:03:19 +0200 (CEST) Received: from imap.hob.de (mail2.hob.de [172.25.1.102]) by mailgate.hob.de (Postfix) with ESMTP id 72DAB1D37E; Tue, 11 Jul 2006 12:03:19 +0200 (CEST) Received: from hob.de (hildnecn-1.hob.de [172.22.80.122]) by imap.hob.de (Postfix on SuSE eMail Server 2.0) with ESMTP id C7FD72DD2; Tue, 11 Jul 2006 12:03:18 +0200 (CEST) Message-ID: <44B37766.9020205@hob.de> Date: Tue, 11 Jul 2006 10:03:00 -0000 From: Christian Hildner User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; de-DE; rv:1.0.2) Gecko/20030208 Netscape/7.02 MIME-Version: 1.0 To: Joern RENNECKE Cc: Ben Elliston , gcc mailing list Subject: Re: Switch statement optimization References: <44B2687E.6050701@st.com> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Mailing-List: contact gcc-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Archive: List-Post: List-Help: Sender: gcc-owner@gcc.gnu.org X-SW-Source: 2006-07/txt/msg00187.txt.bz2 Joern RENNECKE schrieb: > In http://gcc.gnu.org/ml/gcc/2006-07/msg00156.html, your wrote: > > We could use a cheap hash and base start compare / branch trees in > every hash bin. > Say we have a 16 k range, 200 nodes, and want to keep the hash > bin/node ratio between 2 and 4. > Let i be the switch argument. Then we can calculate a 9 bit hash as > (i ^ (x << n)) & 0x3fffffff, where n is a value between 5 and 9. We > can pick the one which produces the flattest > average search trees. > Note that we no longer need to check that i is in range, as for > ordinary switch dispatch tables. What I suggest is to implement a cost-estimation based decision. This should include an architecture dependent modelling that could deliver an exact cost (in terms of size) for size-optimization and as well a good approximation for speed. For example in my case of 1500 labels inside the 16K range I would perfer a branch table instead of a binary compare tree. The size of the table is 16K * 4/8 bytes and this is really ok for a huge program. The frequently used entries are likely to be in the cache, so I expect the whole thing to perform well. However if I would optimize it for my case that may not help in general? So all modifications should be verified with a common standard benchmark like SPEC. Is there someone on the list who wants to support me with these tests or may deliver models for common architectures? Christian