Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!news.szaf.org!news.gnuher.de!rz.uni-karlsruhe.de!feed.news.schlund.de!schlund.de!news.online.de!not-for-mail From: Bernd Paysan Newsgroups: comp.lang.forth Subject: Re: CASE mis-understanding? Date: Fri, 24 Jan 2014 15:01:17 +0100 Organization: 1&1 Internet AG Lines: 30 Message-ID: References: <52e03ea6.129724862@news.demon.co.uk> <52e0e8dd.173300325@news.demon.co.uk> <7xob32sfp5.fsf@ruckus.brouhaha.com> NNTP-Posting-Host: p5dcd724c.dip0.t-ipconnect.de Mime-Version: 1.0 Content-Type: text/plain; charset="ISO-8859-1" Content-Transfer-Encoding: 7Bit X-Trace: online.de 1390572164 24391 93.205.114.76 (24 Jan 2014 14:02:44 GMT) X-Complaints-To: abuse@einsundeins.com NNTP-Posting-Date: Fri, 24 Jan 2014 14:02:44 +0000 (UTC) User-Agent: KNode/4.11.4 Xref: csiph.com comp.lang.forth:28068 Paul Rubin wrote: > Bernd Paysan writes: >> If you want performance, you have two cases: dense case statements, which >> can be implemented as jump-table, i.e. O(1), and sparse case statements, >> which can be implemented as tree search, i.e. O(log n). > > I wonder if anyone uses perfect hashing for sparse case statements, O(1). There's a paper on gperf that shows that some applications gain about 10% in speed with perfect hasing. However, gperf is designed to generate perfect hashes for strings, not for integers. As string comparison takes more time than a simple integer comparison, it really does make sense to optimize this stuff. For integers and perfect hashing, I would use the following generic algorithm: : phash#x#n ( value hashsel -- ) * #n rshift $x and ; $x is the next power of two -1 of the number space, and the search for the best hashsel is to randomly choose values until you find some without colissions. Each matching statement still needs to compare against the desired value and the ELSE case is the default case. -- Bernd Paysan "If you want it done right, you have to do it yourself" http://bernd-paysan.de/