Static analysis is typically used to find errors in software, often serious bugs, such as buffer overruns that lead to quality or security issues. GrammaTech CodeSonar is an advanced static analysis tool that finds problems in source code early during the software development cycle.
One of the strengths of CodeSonar is the fact that it parses the exact same source code that the compiler uses to create the final executable. This creates a very accurate model of the source code, including information about the size of variables and how they are laid out in memory in C structs and arrays, for example.
Memory lay-out of data structures can have a significant impact on program performance, especially if those structures are accessed in tight loops. The reason for this is the processor cache which stores variables in high speed local CPU memory to speed up execution. The order of the fields in C struct, for example, combined with the way that the program accesses these fields dictate how efficiently the cache is used. Take for example a large array of type:
struct Test_Struct{ char a; int b; char c; float d; char e;} ;
If the program runs through these in a tight loop, the processor loads the fields into processor cache. Due to the layout of the fields in this struct, the fields ‘a’ and ‘c’ will each occupy a full word segment of the cache line because of compiler byte alignment. Therefore, wasting cache space, decreasing the likelihood that the requested data is located in the cache, and increasing the number of fetches to the cache and resulting in sub-optimal performance.
The cause of this is the order of the fields, the sizes of the types of the fields and the order that the program access the fields in a tight loop. CodeSonar has information about all three of these attributes; the order of the field, the size of the data type of the fields and it can analyze program flow.
CodeSonar also has an extensive extensibility interface that allows access to the entire program model. This extensibility interface can be used to write a static analysis checker that analyzes cache usage and provides suggestions on how to order the struct fields, or how to change program flow to improve performance significantly. This is not a typical use case for static analysis. The typical use case is to hunt for bugs in source code. Still, static analysis can provide us with valuable feedback in this cache optimization use case as well.
struct Test_Struct{ char a; int b; char c; float d; char e;} ;struct Test_Struct *precord;…for (i = 0; i < ARRAYSIZE; i++){ precord[i].a++; precord[i].b++; precord[i].c++; precord[i].d++; precord[i].e++;}This ordering results in bad cache utilization, triggering the following warning in CodeSonar:
Re-ordering the fields can improve cache utilization and hence performance as clarified in the below diagram.
Figuring out what the optimal configuration could be done through iterative performance testing. Build a benchmark test. Run it, change the ordering of the data structure, run the benchmark again and compare. However, this is potentially expensive since it’s needed for each data type in an application.
The benefit of static analysis is that it can compute through the possibilities statically and provide suggestions. As mentioned, this is not a typical use case for static analysis, but valuable if you care about early performance optimization. A sample extensibility script is available in the GrammaTech user community.
Like what you read? Download our white paper “Advanced Static Analysis for C++” to learn more.
{{cta(’42fd5967-604d-43ad-9272-63d7c9d3b48f’)}}
