From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from resqmta-a1p-077435.sys.comcast.net (resqmta-a1p-077435.sys.comcast.net [IPv6:2001:558:fd01:2bb4::3]) by sourceware.org (Postfix) with ESMTPS id 0552B3858D28 for ; Mon, 18 Apr 2022 14:41:05 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 0552B3858D28 Received: from resomta-a1p-076786.sys.comcast.net ([96.103.145.235]) by resqmta-a1p-077435.sys.comcast.net with ESMTP id gRdpn8767sGdHgSYrn7jRi; Mon, 18 Apr 2022 14:41:05 +0000 Received: from smtpclient.apple ([73.60.223.101]) by resomta-a1p-076786.sys.comcast.net with ESMTPSA id gSYpn7g6SE6QUgSYqnWDir; Mon, 18 Apr 2022 14:41:05 +0000 X-Xfinity-VAAS: gggruggvucftvghtrhhoucdtuddrgedvvddrvddtuddgjeekucetufdoteggodetrfdotffvucfrrhhofhhilhgvmecuvehomhgtrghsthdqtfgvshhipdfqfgfvpdfpqffurfetoffkrfenuceurghilhhouhhtmecufedtudenucenucfjughrpefhtgfgggfukfffvffosehtqhhmtdhhtddvnecuhfhrohhmpefrrghulhcumfhonhhinhhguceophgruhhlkhhonhhinhhgsegtohhmtggrshhtrdhnvghtqeenucggtffrrghtthgvrhhnpedufeeugfffgeffveffffetvedvjeeigffgtdelkeduueeltdevkedvgeegkeekveenucfkphepjeefrdeitddrvddvfedruddtudenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhephhgvlhhopehsmhhtphgtlhhivghnthdrrghpphhlvgdpihhnvghtpeejfedriedtrddvvdefrddutddupdhmrghilhhfrhhomhepphgruhhlkhhonhhinhhgsegtohhmtggrshhtrdhnvghtpdhnsggprhgtphhtthhopedupdhrtghpthhtohepghgttgesghgttgdrghhnuhdrohhrgh X-Xfinity-VMeta: sc=0.00;st=legit From: Paul Koning Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: quoted-printable Mime-Version: 1.0 (Mac OS X Mail 14.0 \(3654.120.0.1.13\)) Subject: Switch statement optimization Message-Id: <321638F8-8BF6-4AFC-8434-471B05F6BBFA@comcast.net> Date: Mon, 18 Apr 2022 10:41:03 -0400 To: GCC Development X-Mailer: Apple Mail (2.3654.120.0.1.13) X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, JMQ_SPF_NEUTRAL, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=no autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: gcc@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 18 Apr 2022 14:41:11 -0000 In switch statements with dense case values, the typical result is a = jump table, which is fast. If the values are sparse, a tree of compares = is generated instead. What if nearly all cases are dense but there are a few outliers? An = example appears in the NFS protocol parser, where you get a switch = statement with cases for each of the opcode values. All but one are = small integers assigned in sequence, but one is 10044. So the "sparse" = case kicks in and a compare tree is generated for everything. I can avoid this by putting in special case code for the 10044 case, = then all the rest ends up being a jump table. That brings up the = question if GCC should recognize such scenarios and break up the switch = statement into "dense parts" handled by a jump table, leaving the = sorting between those as a compare tree. paul