<HTML>
I think the fastest approach with case of strings, especially if it's more than a few entries, is to sort them into alphabetical order (by ASCII code) then length, as then you only have to test one character at a time and the moment you find no match, you can drop out completely. (e.g. searching for "ANNUL" in a list that contains "A, ALL, AND, ANSWER"... it finds a match in A, a mismatch in L but then sees N, but when it reaches the second N, it find D and then S, and S is after N, so there can't be a match). In other words, this would be a trie, although there would have to be safeguards against a false partial match (e.g. the non-existent "ANS" which appears as a part of "ANSWER") such as encoding a jump to the else block.<br>
<br>
<div>I've done a bit more theoretical work on the binary search loop, and managed to get the loop count down from ceil(log(n)) to floor(log(n)), with the last iteration being much simpler than the others. I'm tempted to write up a Wiki article with the proposal once I've got my notes in order. If programmed, there would be two good test cases for it... the x86-64 peephole optimizer, which has, as of writing, a case block with 36 branches (counting each case label separately) that all call identically-structured functions, and the source code analyser of Lazarus that hashes words and makes them bold if they match a list of keywords (this is also another approach to the 'case of strings' problem).<br>
</div><div><br>
</div><div>Gareth aka. Kit<br>
</div> <br>
<br>
<span style="font-weight: bold;">On Sat 04/08/18 23:17 , Benito van der Zander benito@benibela.de sent:<br>
</span><blockquote style="BORDER-LEFT: #F5F5F5 2px solid; MARGIN-LEFT: 5px; MARGIN-RIGHT:0px; PADDING-LEFT: 5px; PADDING-RIGHT: 0px">
<defanged_meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<defanged_body smarttemplateinserted="true">
<div id="smartTemplate4-template">Hi,<br>
<br>
<p>case of strings could also use some optimization<br>
</p>
does it still call fpc_ansistr_compare_equal ? <br>
<br>
fpc could hash the strings, or build a trie, even testing the
length first would help<br>
<br>
<br>
Cheers,<br>
Benito </div>
<br>
<br>
<br>
<div class="moz-cite-prefix">Am 03.08.2018 um 21:57 schrieb J.
Gareth Moreton:<br>
</div>
<blockquote type="cite" cite="mid:61669.1533326234@web-cluster.fastnet.co.uk">
<pre wrap=""> Hi everyone,
So I'm pondering about attempting to implement the binary search system I
devised for case blocks. To find the correct case label, you need to
iterate a search loop a fixed maximum of ceil(log2(n)) times, where n is
the number of individual case values (excluding "else"). Given that this
is quite a low number and I managed to get the loop itself down to just 8
instructions (not including the comparison and conditional jump at the
end), this could be unwrapped for low values of ceil(log2(n))... possibly
up to 7 or 8, I'd say. However, if an exact match is found early, how
serious is the penalty of having a conditional jump forward on each
unrolled iteration for x86-64, whether it's taken or not? (This would be
the equivalent of a Break command)
Gareth aka. Kit
</pre>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
fpc-devel maillist - <a class="moz-txt-link-abbreviated" href="mailto:fpc-devel@lists.freepascal.org">fpc-devel@lists.freepascal.org</a>
<a class="moz-txt-link-freetext" href="http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel">http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel</a>
</pre>
</blockquote>
<br>
_______________________________________________<br>
fpc-devel maillist - <a href="mailto:fpc-devel@lists.freepascal.org">fpc-devel@lists.freepascal.org</a><br>
<a target="_blank" href="<a href="http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel">http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel</a>"><span style="color: red;">http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel</span></a><br>
<br>
</defanged_body></defanged_meta></blockquote></HTML>