[fpc-devel] Case block optimisation

[J. Gareth Moreton]

 So I've been doing a bit more research, and I think my binary search
algorithm is, unfortunately, a failure.  Even after restructuring my
lookup table and making some minute optimisations, it's still slower
overall in my test program, and slower than a jump tree if that gets
used.  I'm figuring the slowdowns come from constantly polling the lookup
table.  Oh well, you can't win them all!

 Nevertheless, I believe I have learnt some things and I may be able to
build some special cases.  The case block used in the peephole optimiser
is a particularly challenging test case for me because it contains a number
of branches, but are all very sparse, since the domain of values is almost
1,000.

 Gareth aka. Kit

 On Wed 26/12/18 00:39 , "J. Gareth Moreton" gareth at moreton-family.com
sent:
  Just to clarify, the patch does NOT contain the binary search
algorithm.  It does contain a utility function that was accidentally left
over when I stripped the code out, named "CreateCMOVInstr", but this can be
safely removed.

 Gareth aka. Kit

 On Wed 26/12/18 00:27 , "J. Gareth Moreton" gareth at moreton-family.com
sent:
  Merry Christmas everyone!

 I've uploaded my improvements to a bug report, along with a test program
that gives timings and verifies correctness.

 https://bugs.freepascal.org/view.php?id=34762

 It turns out that my binary search algorithm runs slower on average
"Domain of 1024" tests (which are based on the design of the peephole
optimizer) that I had set up (which currently still compile into linear
lists) except in the case where the correct branch is the midpoint of the
valid set (in a jump tree, this is the first value tested).  Jump trees
are also faster than a binary search currently despite the large number of
conditional branches required - nevertheless, I will continue to research
this algorithm to see if it can find a role - I suspect that it might still
find a place where each branch calls an identically-structured procedure...
if I can get the compiler to identify that in the branches.  Successfully
doing this will also improve case blocks that are compiled into jump tables
instead.

 Gareth aka. Kit

 On Sat 15/12/18 19:12 , "J. Gareth Moreton" gareth at moreton-family.com
sent:
  I'll see what I can do!

 The one thing about my case optimisations here is that they're done at the
node level.  Some parts are platform-independent, but unfortunately,
things like jump table generation have to be implemented for each platform.

 The aint shuffling is a little difficult to test for sure, but what's
worse is the use of TConstExprInt, and not just because of the overhead
involved with reading and writing to them.  I used logic in some places
though, like when I do a sort of for-loop between max_ and hv, I subtracted
1 from each variable (sometimes implicitly) to account for a potential
overflow situation.  It's impossible for it to trigger an underflow
because max_ is greater than min_, and they wouldn't be equal otherwise a
jump table won't even be generated.

 Either way, I'm just enjoying myself with this!

 Gareth aka. Kit

 On Sat 15/12/18 19:55 , Martok listbox at martoks-place.de sent:
 Am 15.12.2018 um 18:08 schrieb J. Gareth Moreton: 
 > So here's something else I've been playing with in the interim... I've
been 
 > working on improving the algorithms used when compiling case blocks. 
It was 
 > driven partly by my binary search idea for certain kinds of case block,
which I 
 > wrote up over here:
http://wiki.freepascal.org/Case_Compiler_Optimization
[1]">http://wiki.freepascal.org/Case_Compiler_Optimization 

 Feel free to include '0033093_Casenode_order.patch' from 
  [2]; 
 It's actually already a bit simpler in your version ;-) 

 The one thing that still bugs me (but I know it's not really seen as a
problem 
 in FPC) is that every platform cg theoretically has to implement all of
that, 
 causing a lot of duplication. 

 I like the use of more expressive intermediate names. But there was a lot
of 
 overflowed-aint-shuffling, are you sure that still works everywhere? 

 Bug 0032115 provides a "nice" test case for things that can go wrong with 
 different word sizes, and is also a good test for the true label count. 

 -- 
 Regards, 
 Martok 

 _______________________________________________ 
 fpc-devel maillist - fpc-devel at lists.freepascal.org [3] 
 http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
[4]">http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel 

  _______________________________________________
 fpc-devel maillist - fpc-devel at lists.freepascal.org [5]
 http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
[6]">http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel

  _______________________________________________
 fpc-devel maillist - fpc-devel at lists.freepascal.org [7]
 http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
[8]">http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel

  _______________________________________________
 fpc-devel maillist - fpc-devel at lists.freepascal.org [9]
 http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
[10]">http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel

 

Links:
------
[1] http://secureweb.fast.net.uk/ http:=
[2] https://bugs.freepascal.org/view.php?id=33093>
[3] mailto:fpc-devel at lists.freepascal.org
[4] http://secureweb.fast.net.uk/ http:=
[5] mailto:fpc-devel at lists.freepascal.org
[6] http://secureweb.fast.net.uk/ http:=
[7] mailto:fpc-devel at lists.freepascal.org
[8] http://secureweb.fast.net.uk/ http:=
[9] mailto:fpc-devel at lists.freepascal.org
[10] http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freepascal.org/pipermail/fpc-devel/attachments/20181227/2a4cea04/attachment.html>