Efficient static map creation

Question

I am writing a simple C ++ parser that works using a map of pointers to the “triggers” functions in the “handler”, my question is what would be the most “static” and efficient method for implementing map generation and access?

First I looked at a method, for example. Parser::add_handler , which will add a trigger / handler to the parser card, but as far as I know, this will need to be done every time the program starts, while the data is known at compile time. (Although on the positive side, they would need to be executed only once, and not for each instance of Parser.)

Then I thought about using a virtual method, for example. Parser::get_handlers in Parser, which will be implemented in derived classes to return a handler map for this parser. This seems like a more beautiful encapsulated solution, although for each created parsing instance, a virtual function call with at least one call to the parser card generation function will be required.

Using the latter approach seems to be preferable at the moment, but it still leaves a dynamic map display at each execution, is there any way to avoid this?

Answer 1

If you do not want to dynamically build a map, you can use a sorted static array with std::lower_bound to search in O (log n) time.

If you have a good implementation of a hash map, you may find that the overhead of filling it out is less than the increase in performance at runtime, depending on how many searches you need to do.

Answer 2

If you know all the lines and their handlers at compile time and want to combine them at runtime, and if you don't have a heck of a lot of lines, and their length is not very long, and if the range of possible characters in these lines is not huge (i.e. as in ASCII), then you can create a static distribution table at compile time using templates or simply using hard coding. This approach can also lead to poor performance, depending on which lines and how many of them you have.

Alternatively, you can have an array for the length of the string, where the key is the sum of the characters (their numeric representations) in that string.

But I would advise you to start with Google dense_hash_map . Don't spend too much time prematurely optimizing your software. Once your program is complete, and if you are not satisfied with the performance, use the profiler to find where this bottleneck is and to improve performance there.

Good luck.

Answer 3

First of all, this seems like unnecessary, are you trying to spend some time optimizing what you don’t need to optimize, or are you just wondering?

It depends ... if everyone knows the function names, then it all depends on the number of functions that you have. You can simply create an array of string pointers so that the pointers are sorted and then do a manual search. If the list has only a few functions, you can perform a linear search. If you have a lot, then for performance reasons, do a binary search manually (but the pointers should be ordered in sort order).

BUT, for real work, in no case use std :: map! It is specially designed for your case: inserts are expensive, but as soon as a map is created once, the search is very fast (binary search). You will get a clean code.

Answer 4

If you want to be super efficient, you create a processing tree as Plain Old data structures. If you want to do it beautifully, you create a program that generates a parse tree from the specification (this is what lex / flex does for you), and then compile the resulting data structure into your program.

You then do not need add_handler , since all data is added at compile time.

However, you probably won't need this level of optimization for most tasks, so I always recommend getting functionality first and then looking at how to optimize the use of such methods later.

Answer 5

There are many interesting solutions based on your requirements.
A faster method than your second is to use the Parser template for a class that has a function pointer element for each trigger, so there is no overhead at runtime. In fact, this is the only solution that allows embedding. This has the limitation that a single class must have all handlers.

 template<class handler> struct Parser { void ParseLines() { if (lineBeginsWith('+') handler.lineBeginsPlus(); if (lineBeginsWith('-') handler.lineBeginsMinus(); } }; struct LineHandlers { void lineBeginsPlus() { printf("handle + line"); } void lineBeginsMinus() { printf("handle - line"); } }; struct OtherLineHandlers { void lineBeginsPlus() { printf("handle + line differently"); } void lineBeginsMinus() { printf("handle - line differently"); } }; int main() { Parser<LineHandlers> ParserInstance; ParserInstance.ParseLines(); Parser<OtherLineHandlers> OtherParserInstance; OtherParserInstance.ParseLines(); }