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" gar...@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" gar...@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 list...@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@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@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@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 Links: ------ [1] http://secureweb.fast.net.uk/ http:= [2] https://bugs.freepascal.org/view.php?id=33093> [3] mailto:fpc-devel@lists.freepascal.org [4] http://secureweb.fast.net.uk/ http:= [5] mailto:fpc-devel@lists.freepascal.org [6] http://secureweb.fast.net.uk/ http:= [7] mailto:fpc-devel@lists.freepascal.org [8] http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
_______________________________________________ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
