From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 29717 invoked by alias); 10 Jul 2006 14:48:02 -0000 Received: (qmail 29689 invoked by uid 22791); 10 Jul 2006 14:48:01 -0000 X-Spam-Check-By: sourceware.org Received: from lon-del-03.spheriq.net (HELO lon-del-03.spheriq.net) (195.46.50.99) by sourceware.org (qpsmtpd/0.31) with ESMTP; Mon, 10 Jul 2006 14:47:56 +0000 Received: from lon-out-02.spheriq.net ([195.46.50.130]) by lon-del-03.spheriq.net with ESMTP id k6AElr4L023604 for ; Mon, 10 Jul 2006 14:47:53 GMT Received: from lon-cus-01.spheriq.net (lon-cus-01.spheriq.net [195.46.50.37]) by lon-out-02.spheriq.net with ESMTP id k6AElqRD012495 for ; Mon, 10 Jul 2006 14:47:52 GMT Received: from beta.dmz-eu.st.com (beta.dmz-eu.st.com [164.129.1.35]) by lon-cus-01.spheriq.net with ESMTP id k6AElf60003141 (version=TLSv1/SSLv3 cipher=EDH-RSA-DES-CBC3-SHA bits=168 verify=OK); Mon, 10 Jul 2006 14:47:44 GMT Received: from zeta.dmz-eu.st.com (ns2.st.com [164.129.230.9]) by beta.dmz-eu.st.com (STMicroelectronics) with ESMTP id 5D9C5DA48; Mon, 10 Jul 2006 14:47:35 +0000 (GMT) Received: from mail1.bri.st.com (mail1.bri.st.com [164.129.8.218]) by zeta.dmz-eu.st.com (STMicroelectronics) with ESMTP id C922B475F8; Mon, 10 Jul 2006 14:47:29 +0000 (GMT) Received: from st.com (bri1042.bri.st.com [164.129.15.48]) by mail1.bri.st.com (MOS 3.5.8-GR) with ESMTP id CHU71069 (AUTH renneckej); Mon, 10 Jul 2006 15:47:24 +0100 (BST) Message-ID: <44B2687E.6050701@st.com> Date: Mon, 10 Jul 2006 14:48:00 -0000 From: Joern RENNECKE User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.6) Gecko/20040113 MIME-Version: 1.0 To: Ben Elliston Cc: Christian Hildner , gcc mailing list Subject: Re: Switch statement optimization 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/msg00158.txt.bz2 In http://gcc.gnu.org/ml/gcc/2006-07/msg00156.html, your wrote: > A paper at this year's GCC Summit talked about this: > http://www.gccsummit.org/2006/view_abstract.php?content_key=18 > You might like to follow up with Edmar (the author of the paper). But that was about optimizing the trees for an uneven probability distribution which could be found by profiling. This does not address the issue what to do when the distribution is mostly uniform or unknown. 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. Moreover, on a target that can do effectively multi-way compares like the x86, in order to increase ILP, we can put into the table entry for each hash bin, in addition to the jump address, a value to compare i against before the dispatch jump takes place. If a cheap hash can be chosen so that there is no more than one entry per hash bin, we can even do a single compare in the dispatch code, go to the default case for non-match, and dispatch right to the handling code if we have a match.