[fpc-devel] Loop unrolling question

[J. Gareth Moreton]

 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.

 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).

 Gareth aka. Kit

 On Sat 04/08/18 23:17 , Benito van der Zander benito at benibela.de sent:
    Hi,

case of strings could also use some optimization
  does it still call fpc_ansistr_compare_equal ? 

 fpc could hash the strings, or build a trie, even testing the length first
would help

 Cheers,
 Benito  

 Am 03.08.2018 um 21:57 schrieb J. Gareth Moreton:

 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 
 

_______________________________________________ 
fpc-devel maillist - fpc-devel at lists.freepascal.org 
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel 

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

 

Links:
------
[1] mailto:fpc-devel at lists.freepascal.org
[2] 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/20180804/32d469c1/attachment.html>