Re: Qi Symbols parser performance

On 12/01/2018 9:15 PM, Stephan Menzel wrote:

[snips]

> Now, that would be my first question: Why is that? The 'beast' impl strikes me as very 
> inefficient as it goes through all the substrings, calls iequals every time, while it 
> would be able to cache the lowercase.
> I thought surely qi would do a binary search upon the keywords I added to a symbols 
> parser. But is doesn't look like it does.
> 
> So I came up with my own, also trivial impl and use a static map with a cached lowercase 
> temporary (see impl3 in attached source).
> Test yielded:
> 
>   - Static Map Impl averages at about 2400 nanoseconds a run
> 
> Sooo, I guess the question is why?
> Am I misusing qi::symbols somehow? Does it actually do a binary search but the performance 
> is lost some other place?
> Does anybody have some thoughts about this?

I'm not sure if I can find the time to inspect deeper into this. Perhaps the
least I can offer are some right-off-the-bat thoughts:

1) Why use grammars and rules? Those are unnecessary. You can use
    symbols directly.
2) Symbols use ternary search tries: http://tinyurl.com/ydy3fnnp
3) They might not be the best choice for your use case. They are best
    used for parsing languages, especially when you expect lots of partial
    matches and misses (e.g. keywords in a language, where you expect other
    lexemes apart from just keywords.

To understand the use cases TSTs are good choices for, see:

http://www.drdobbs.com/database/ternary-search-trees/184410528
https://en.wikipedia.org/wiki/Ternary_search_tree

Apart from language parsers, they may be good for e.g. autocompletion,
spell checking and storage and detection of strings with a lot of
common prefixes (e.g. file paths). In most cases, you are better off
other search means using a hash map, for example.


Regards,
-- 
Joel de Guzman
http://www.ciere.com
http://boost-spirit.com
http://www.cycfi.com/

------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot
_______________________________________________
Spirit-general mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/spirit-general