Hi everyone,

I've just written up a new segment on the Wiki about how jump tables work.  Since I want to look at implementing my binary search option, I thought I'd document what already exists;

http://wiki.freepascal.org/Case_Compiler_Optimization

The "Jump Table" section is what I've added.  Can people check to see that I've got it correct? I had to go back and edit it a few times because I got the AT&T and Intel operand ordering mixed up!

Gareth aka. Kit

Op 2018-12-11 om 17:12 schreef J. Gareth Moreton:

I'm not really a compiler person, but afaik for large n, the number of tests can be log(n) using a bisection algorithm. The microchip C (pic16/18/24/33) compilre implements this. IOW the number of linear tests is not the metric to compare to.

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.

The jump table is of O(1), but starts becoming prohibitive if the range is sparse.

Gareth

On Tue 11/12/18 19:48 , Marco van de Voort sent:

Op 2018-12-11 om 17:12 schreef J. Gareth Moreton:

[1]">http://wiki.freepascal.org/Case_Compiler_Optimization

The "Jump Table" section is what I've added.  Can people check to see that I've got it correct? I had to go back and edit it a few times because I got the

AT">http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel

Links:
------
[1] http://wiki.freepascal.org/Case_Compiler_Optimization

I've also discovered that my binary search algorithm is unfortunately slower than what already exists.  Jump trees are faster if they're used. Gareth

On Fri 28/12/18 17:45 , Florian Klämpfl sent:

Marco van de Voort wrote

Op 2018-12-11 om 17:12 schreef J. Gareth Moreton: > > I've just written up a new segment on the Wiki about how jump tables

work.  Since I want to look at implementing my

> binary search option, I thought I'd document what already exists; > > http://wiki.freepascal.org/Case_Compiler_Optimization

[1]">http://wiki.freepascal.org/Case_Compiler_Optimization

> > The "Jump Table" section is what I've added.  Can people check to see

that I've got it correct? I had to go back and

> edit it a few times because I got the AT">> I'm not really a compiler person, but afaik for large n, the number of

tests can be log(n) using a bisection algorithm.

The microchip C (pic16/18/24/33) compilre implements this. IOW the

number of linear tests is not the metric to compare to.

FPC does this if needed.

FPC does this if needed.