OptimizingKaRL
C++ Guide Series
Architecture | Knowledge Base | Networking | Containers | Threads | Optimizations | KaRL | Encryption | Checkpointing | Knowledge Performance | Logging
By default, MADARA is setup to promote flexibility and ease-of-use, but MADARA, and especially the interfaces to the Knowledge and Reasoning Language (KaRL) have powerful optimizations available that take O(log n) operations and make them O(1)--a nice feature for real-time system developers who would like to make their rapid prototypes production-grade in minutes. In this Wiki, we explore some of the key optimizations that will supercharge your MADARA code.
- Optimizations
- 1. Compiled Expressions
- 2. Variable References
- 3. Expanding Logics for Static Variables
- 4. Containers
- More Information
All KaRL expressions that you pass to evaluate or wait calls via the KnowledgeBase or Variables classes are by default compiled and put into a cache for quick retrieval later. However, "quick" is relative. The cache will search through a balanced binary tree (which is O(log n)) and potentially do a string compare on the length of your expression per check in that binary tree (O (m log n), where m is the length of your string).
Example of Slow Lookup
...
madara::knowledge::KnowledgeBase knowledge ("", settings);
knowledge.evaluate (
" // Set number of agents ready to zero\n"
" agents.ready 0;\n"
"\n"
" // Count the number of agents that are ready\n"
" .i [0->max_agents)\n"
" (\n"
" agent{.i}.ready => ++agents.ready\n"
" )\n"
);
The slow lookup above is practical for prototyping, but it will require quite a few comparisons in the binary-tree-based cache. We can have an O(1) lookup mechanism here by compiling the expression and passing a CompiledExpression class into the evaluate function call.
Example of Fast Lookup with Compiled Expressions
...
madara::knowledge::KnowledgeBase knowledge ("", settings);
// Compile the code first and save it into counts_agent_ready
Madara::Knowledge_Engine::Compiled_Expression count_agents_ready =
knowledge.compile (
" // Set number of agents ready to zero\n"
" agents.ready = 0;\n"
"\n"
" // Count the number of agents that are ready\n"
" .i [0->max_agents)\n"
" (\n"
" agent{.i}.ready => ++agents.ready\n"
" )\n"
);
// Now, evaluate the compiled expression instead of the string
knowledge.evaluate (count_agents_ready);
Compiling an expression, as seen in the above example, will save you microseconds per evaluate statement, and will give you nanosecond execution times for many small logics.
Similar to compiled expressions, there are O(1) lookup primitives for usage with get and set as well. This saves us an O(m log n) lookup (where m is the length of the variable name and n is the number of variables currently in the context) with a very simple one-time lookup cost of O(m log n).
Example of Slow Variable Lookup
...
madara::knowledge::KnowledgeBase knowledge ("", settings);
while (!terminated)
{
int my_x = knowledge.get ("my_x").to_integer ();
int my_y = knowledge.get ("my_y").to_integer ();
...
}
To alleviate this lookup cost, we can use the VariableReference class and the get_ref function, which operates similarly to the get function.
Example of Fast Lookup with Variable References
...
madara::knowledge::KnowledgeBase knowledge ("", settings);
madara::knowledge::VariableReference my_x_ref
knowledge.get_ref ("my_x");
madara::knowledge::VariableReference my_y_ref
knowledge.get_ref ("my_y");
while (!terminated)
{
int my_x = knowledge.get (my_x_ref).to_integer ();
int my_y = knowledge.get (my_y_ref).to_integer ();
...
}
Each usage of get with a VariableReference will execute roughly 4x faster with a small context filled with dissimilar variables. With a large context of similarly named variables (i.e. many have the same prefix), the savings will be even larger. Consequently, VariableReference is extremely useful for real-time application developers to ensure predictable performance. Note that most containers use such variable references to get O(1), extremely fast access times to knowledge.
The MADARA KaRL mechanisms are developed for aiding programmers in creating distributed applications in modular code that can be ported anywhere. Many of our current programs use the same code base for each agent participating in the distributed application, and the only differentiation between them is an identifier variable such as .id. Other variables like the maximum number of processes, e.g. .processes, may be set from the command line and never changed again for the life of the program.
These references by themselves are pretty fast (low nanoseconds on Intel or AMD processors) in the scripting language, but if you have variable expansions (e.g., "agent{.id}.ready 1"), the expansion can take microseconds for building the variable name. If you know the expansion will have the same value everytime, or maybe it alternates between only one of two values and you'd like everything to execute as quickly as possible, you can use the expand_statement call to do variable expansion once, likely at the beginning of the program, and supercharge your evaluate, get, set, or wait statements that would have required variable expansion on static variables.
Let's look at an example of what we're talking about.
Example of Unnecessary, Frequent Variable Expansion
madara::knowledge::KnowledgeBase knowledge ("", settings);
... set id and number of processes through command line
while (!terminated)
{
// Move the agent
knowledge.evaluate (
" agent{.id}.ready 1;\n"
" agent{.id}.x = gps.get_lat ();\n"
" agent{.id}.y = gps.get_long ();\n"
" agent{.id}.z = gps.get_alt ();\n"
);
}
The problem with the above is that we have a while loop that is constantly expanding "agent{.id}", which will never change in that while loop. If we want to tighten up the loop, we can do the following:
Example of One-time Variable Expansion for Faster Execution
madara::knowledge::KnowledgeBase knowledge ("", settings);
... set id and number of processes through command line
// expand anything in braces {} into a more streamlined logic
std::string expanded = knowledge.expand (
" agent{.id}.ready 1;\n"
" agent{.id}.x = gps.get_lat ();\n"
" agent{.id}.y = gps.get_long ();\n"
" agent{.id}.z = gps.get_alt ();\n");
// the result should be agent1.ready|x|y|z for .id ## 1, etc.
// compile the resulting expanded logic to remove lookup cost
madara::knowledge::CompiledExpression move_agent = knowledge.compile (expanded)
while (!terminated)
{
// evaluate the expanded, compiled move_agent logic
knowledge.evaluate (move_agent);
}
C++ containers (found in the madara::knowledge::Containers namespace) use the above optimizations frequently, so using the Container classes often results in significant performance improvements for novice users. You can read more about some of the containers at the Containers Wiki page.
If you are looking for code examples and guides, your best bet would be to start with the tutorials (located in the tutorials directory of the MADARA root directory--see the README.txt file for descriptions). After that, there are many dozens of tests that showcase and profile the many functions, classes, and functionalities available to MADARA users.
Users may also browse the Library Documentation for all MADARA functions, classes, etc. and the Wiki pages on this website.
First Steps in MADARA: Covers installation and a Hello World program.
Intro to Networking: Covers creating a multicast transport and coordination and image sharing between multiple agents.
C++ Guide Series
Architecture | Knowledge Base | Networking | Containers | Threads | Optimizations | KaRL | Encryption | Checkpointing | Knowledge Performance | Logging