<HTML>
<style> BODY { font-family:Arial, Helvetica, sans-serif;font-size:12px; }</style>I'll have to look that one up. I might have reinvented the wheel a bit with the binary search algorithm that I put on there ages ago, which is of O(log n) and works even if the range of test values is sparse (I came up with the algorithm originally for the case block in the peephole optimiser, where there are many hundreds if not thousands of individual opcodes, but only a handful actually have branches.<br>
<br>
The jump table is of O(1), but starts becoming prohibitive if the range is sparse.<br>
<div><br>
</div><div>Gareth<br>
</div> <br>
<br>
<span style="font-weight: bold;">On Tue 11/12/18 19:48 , Marco van de Voort fpc@pascalprogramming.org sent:<br>
</span><blockquote style="BORDER-LEFT: #F5F5F5 2px solid; MARGIN-LEFT: 5px; MARGIN-RIGHT: 0px; PADDING-LEFT: 5px; PADDING-RIGHT: 0px">
<br>
Op 2018-12-11 om 17:12 schreef J. Gareth Moreton:
<br>
<span style="color: rgb(102, 102, 102);">>
</span><br>
<span style="color: rgb(102, 102, 102);">> I've just written up a new segment on the Wiki about how jump tables
</span><br>
<span style="color: rgb(102, 102, 102);">> work. Since I want to look at implementing my binary search option, I
</span><br>
<span style="color: rgb(102, 102, 102);">> thought I'd document what already exists;
</span><br>
<span style="color: rgb(102, 102, 102);">>
</span><br>
<span style="color: rgb(102, 102, 102);">> <a target="_blank" href="<a href="http://wiki.freepascal.org/Case_Compiler_Optimization">http://wiki.freepascal.org/Case_Compiler_Optimization</a>"><span style="color: red;">http://wiki.freepascal.org/Case_Compiler_Optimization</span></a>
</span><br>
<span style="color: rgb(102, 102, 102);">>
</span><br>
<span style="color: rgb(102, 102, 102);">> The "Jump Table" section is what I've added. Can people check to see
</span><br>
<span style="color: rgb(102, 102, 102);">> that I've got it correct? I had to go back and edit it a few times
</span><br>
<span style="color: rgb(102, 102, 102);">> because I got the AT&T and Intel operand ordering mixed up!
</span><br>
<br>
I'm not really a compiler person, but afaik for large n, the number of
<br>
tests can be log(n) using a bisection algorithm. The microchip C
<br>
(pic16/18/24/33) compilre implements this. IOW the number of linear
<br>
tests is not the metric to compare to.
<br>
<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>
<br>
</blockquote></HTML>