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 [email protected] 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 - [email protected] http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel _______________________________________________ fpc-devel maillist - [email protected] [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:[email protected] [2] http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
_______________________________________________ fpc-devel maillist - [email protected] http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
