From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 2192 invoked by alias); 27 Aug 2010 14:47:46 -0000 Received: (qmail 2182 invoked by uid 22791); 27 Aug 2010 14:47:45 -0000 X-SWARE-Spam-Status: No, hits=-2.0 required=5.0 tests=AWL,BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,SPF_HELO_PASS,T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from smtp-out.google.com (HELO smtp-out.google.com) (216.239.44.51) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Fri, 27 Aug 2010 14:47:38 +0000 Received: from wpaz5.hot.corp.google.com (wpaz5.hot.corp.google.com [172.24.198.69]) by smtp-out.google.com with ESMTP id o7RElare021916 for ; Fri, 27 Aug 2010 07:47:36 -0700 Received: from pvg7 (pvg7.prod.google.com [10.241.210.135]) by wpaz5.hot.corp.google.com with ESMTP id o7RElYs2003297 for ; Fri, 27 Aug 2010 07:47:35 -0700 Received: by pvg7 with SMTP id 7so1180198pvg.3 for ; Fri, 27 Aug 2010 07:47:34 -0700 (PDT) Received: by 10.142.222.8 with SMTP id u8mr1249536wfg.214.1282920453777; Fri, 27 Aug 2010 07:47:33 -0700 (PDT) Received: from coign.google.com ([66.109.106.2]) by mx.google.com with ESMTPS id t11sm4522054wfc.16.2010.08.27.07.47.31 (version=TLSv1/SSLv3 cipher=RC4-MD5); Fri, 27 Aug 2010 07:47:32 -0700 (PDT) From: Ian Lance Taylor To: "Paulo J. Matos" Cc: gcc@gcc.gnu.org Subject: Re: Clustering switch cases References: Date: Fri, 27 Aug 2010 15:03:00 -0000 In-Reply-To: (Paulo J. Matos's message of "Fri, 27 Aug 2010 14:39:41 +0100") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.1 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-System-Of-Record: true X-IsSubscribed: yes 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-08/txt/msg00399.txt.bz2 "Paulo J. Matos" writes: > In the first case, it generates a binary tree, and in the second two > jump tables. The jump tables solution is much more elegant (at least > in our situation), generating less code and being faster. > Now, what I am wondering is the reason why GCC doesn't try to cluster > the cases trying to find for clusters of contiguous values in the > switch. > > If there is no specific reason then I would implement such pass, which > would before expansion split switches according to value clustering, > since I find it would be a good code improvement. > > Currently GCC seems to only use jump table is the range of the switch > is not much bigger than its count, which works well in most cases > except when you have big switches with clusters of contiguous values > (like the first example I sent). I don't know of any specific reason not to look for clusters of switch cases. The main issue would be the affect on compilation time. If you can do it with an algorithm which is linear in the number of cases, then I think it would be an acceptable optimization. Ian