How to use MAQAO to improve application performance

MAQAO is an open-source project, from its home page:

MAQAO (Modular Assembly Quality Analyzer and Optimizer) is a performance analysis and optimization framework operating at binary level with a focus on core performance. Its main goal is to guide application developers along the optimization process through synthetic reports and hints.
MAQAO mixes both dynamic and static analyses based on its ability to reconstruct high level structures such as functions and loops from an application binary. Since MAQAO operates at binary level, it is agnostic with regard to the language used in the source code and does not require recompiling the application to perform analyses. MAQAO has also been designed to concurrently support multiple architectures. Currently the Intel64 and Xeon Phi architectures are implemented.

While MAQAO is well suited to the analysis of assembly and machine code in the context of compiler development, it can be useful to analyze loops and functions for the improvement of an application’s performance.

It comes with a top-level interface, oneview, which calls its various underlying tools, and greatly simplifies the analysis.

oneview is also well suited to an HPC environment because the results are saved to text files (or HTML), which can be retrieved for inspection on a graphical user environment such as a web browser.

In this HowTo we’ll be using oneview, and its text report format.

For a better illustration of MAQAO, we’ll work with a simple application, developed specifically for this How-To guide, it will serve as our running example.

Sequential search

The application takes as input a sequence of words, and will generate a list of all unique words, along with their occurrences (count). The list of word counts is initially empty, new words are incrementally added.

A sample of the result expected from the application is shown below (the input text is H. Thoreau’s Walden and Civil Disobedience from Project Gutenberg):

The sequential search is chosen for this How-To guide because of its simplicity, the successive program changes guided by MAQAO all fit in a single source file (see the appendix, referred to as search.c in this How-To guide).

Sequential search can be applied when the records to be searched cannot be compared (not ordering relation), and thus cannot be sorted. We will assume this to be the case in this How-To guide, although in our running example, words are obviously comparable.

A hash table would be a more natural structure for such a purpose (counting word occurrences). However, this How-To guide also provides the opportunity to explore a heuristic (see Art of Computer Programming – Volume 3 Sorting and Searching): move to top.

Whenever a word is found (or added to the list if previously unseen) it is moved to the top of the list (rest of the list remains in order).

The idea is to exploit the underlying structure in natural languages (and in many real-world data). Sequential search is also a good match when the input data size is unknown (as growing a hash-table to an unknown size can be expensive).

The source code below shows the first, naive, implementation of sequential search (so, not the move to top heuristic).

35 static struct result naive(char **word, int n) {
36    int page = 1024;
37    struct record *rec = malloc(page * sizeof(*rec));
38    int i, end=-1, score = 0;
39    for (int iw=0; iw<n; ++iw) {
40        // the basic sequential search:
41        for (i=0; i<=end; i++) {
42            if (strcmp(word[iw], rec[i].word) == 0) {
43                rec[i].count++;
44                score += i;
45                break;
46            }
47        }
48        // word not found, add it to our list
49        if (i>end) {
50            // last record, extend stoeage:
51            if (end >= page-1) {
52               page *=2;
53               rec= realloc (rec, page*sizeof(*rec));
54            }
55            end++;
56            rec[end]=struct record) {word[iw], 1};
57            score += end;
58        }
59    }
60    return (struct result) {end, rec, score/n};
61 }

Unseen words are added to the end of the list, implemented as an array of indices. The array is introduced for performance reasons (a priori), it enables the use of a memory pool (batching memory allocations), which reduces the number of allocation calls, and allows to easily grow the list (line 53, realloc which changes memory addresses implicitly) when the result size is not known in advance.

Below is the initial implementation of the move to top heuristic.

69 static struct result heur(char **word, int n) { 
70    int page = 1024; 
71    struct record *rec = malloc(page * sizeof(*rec)); 
72    int i=0, end=-1, score = 0; 
73    struct record r; 
74    for (int iw=0; iw<n; ++iw) { 
75        // the basic sequential search: 
76        for (i=0; i <= end; i++) { 
77            if (strcmp(word[iw], rec[i].word) == 0) { 
78                rec[i].count++; 
79                score += i; 
80                if (i==0)  
81                    break; 
82                // move to top: 
83                r = rec[i]; 
84                memmove(rec+1, rec, i*sizeof(struct record)); 
85                rec[0] = r; 
86                break; 
87            } 
88        } 
89        // word not found, add it to our list 
90        if (i > end) { 
91            // last record, extend storage: 
92            if (end >= page-1) { 
93                page *= 2;     
94                rec = realloc(rec, page*sizeof(*rec)); 
95            } 
96            // move to top: 
97            memmove(rec+1, rec, i*sizeof(struct record)); 
98            rec[0] = (struct record) {word[iw], 1}; 
99            end++; 
100           score += end; 
101        } 
102    } 
103    return (struct result) {end, rec, score/n}; 
104 }

It is simple and probably inefficient as it relies on memory copies (memmove) to reorder the words when either found or added.

Initial results

Let’s compile the program with the 2 above search methods, and execute it on some input data (Thoreau’s Walden, Civil Disobedience and Journal from project Gutemberg).

$ gcc -Og -g -std=gnu11 search.c -o search-Og.out

The program executes the search for a number of iterations (5 in the example above) and reports:

• the runtime in seconds, averaged over iterations,
• a score: how many loop iterations were needed to find or add the word (averaged across the words). This score helps us observe the behaviour of move to top.

From this very first run we see that on such input size move to top is slower although iterating less.

Our running example is fast enough such that this How-To guide can be replicated on a personal computer. To follow the How-To guide on an HPC, for example EuroHPC’s Meluxina, the following Lmod modules are required.

For our first analysis with MAQAO, we’ll compile the program without proper attention to compilation options:
$ gcc -Og -g -std=gnu11 search.c -o search-Og.out

On a larger input le of 675 391 words (the sum of Thoreau’s works mentioned before, plus Jane Eyre and Moby Dick), the results of the execution of the sequential search are reported below (still 5 iterations).

We see that for this input size the move to top outperforms the naive sequential search, in both runtime and score (average position in the word count list).
The initial performance is 9.10 seconds, we’ll use this as our reference.

MAQAO recommendations

Now we are ready to use MAQAO. The command line below lists the typical parameters to oneview.

• create-report=one is required.
• xp is the directory for the report les.
• output-format=text selects the text format, default is html, all formats can be generated too (all).
• executable and run-commands set the program execution options.
• with-POP includes additional information.
• lprof-params allows to pass extra parameters to the profiler tool, called by oneview.
  Although some lprof parameters are directly settable via oneview, it is better to add them here as it offers all lprof parameters and are better documented (note the space between parameters, this is incorrectly documented). The lprof parameters set here are useful to obtain accurate metrics, but because they introduce more overhead (slows down execution), specifying a pro ling start condition (and eventually stop) provides a nice tradeoff. The pro ling start condition is the presence on stdout of the word “parsed”, which is actually output by the program.
• dbg=2 this is recommended because it provides more information on what is actually run (necessary to validate the parameters set are actually applied), and lists example commands to later access specific parts of the MAQAO report.

The MAQAO report is quite long. Starting from the top, section 2.1 – Stylizer already provides useful recommendations, here are the most interesting items:

In the next section we will apply those recommendations.

Applying previous recommendations

The recommendations are simple to apply:

$ gcc -O3 -g -fno-omit-frame-pointer -std=gnu11 -march=native search.c -o search-O3.out

We run MAQAO again, setting a different output directory and log file:

All the previous problems reported in section 2.1 - Stylizer are now fixed.
Let’s observe the results of these changes on an execution of our sequential search application (outside the MAQAO tool):

The recommendations translate to a 14% improvement.

Looking for new recommendations

Let us now inspect the new MAQAO report for additional improvement suggestions.

Section 1.3 – Potential Speedups does not report anything.

Section 2.1 – Stylizer (idem).

Section 2.2 – Strategizer (idem).

Section 2.3 – Optimizer mentions a few interesting recommendations, but unfortunately they point to loop IDs. To map these ids to the source code we must refer to a table in 5.1 – Top 10 Loops,
reproduced below:

Referring back to the source code, we observe that:

• Loop id 18 is the innermost loop of the naive function.
• Loop id 15 is the innermost loop of the heur function.
• Loop id 12 includes the memmove call, and the append operation. It has a relatively small impact however.

The interesting recommendations for loop IDs 18 and 15 are:

• Presence of (function) calls.
  Looking at section 4.1 – Top 10 Functions we see that one function is dominating usage: __strcmp_avx2 with 89.47% of the time. This obviously is our word comparison function. Although we could try to accelerate this, for the purpose of this How-To guide, we will consider it as out of scope (otherwise we could switch the libc standard implementation with a custom string comparison function, or switch to another strncmp implementation).
• Presence of constant non unit stride data access.
  This relates to our use of arrays instead of pointers which introduce an additional indirection. As mentioned in the presentation of the sequential search, we traded the disadvantage of arrays for the simplicity and the fewer memory allocations (a system call) by using a memory pool. So, not a relevant option in our case.

So, no clear improvement is proposed so far.Looking further at the static code analysis (which MAQAO refers to as CQA), which is also presented by loop ID, the following recommendations are proposed:

•  Try another compiler or update/tune your current one: recompile with fassociative-math (included in Ofast or ffast-math) to extend loop vectorization to FP reductions.
• Remove inter-iterations dependences from your loop and make it unit-stride:

As we do not use any floating point operations, and have settled for array indirections, there is still nothing actionable.Reading forward, we do notice the following recommendations for loop id 12:

• memmove@plt: 1 occurrences<<list_path_3_call_1>>
• Detected COMPLEX INSTRUCTIONS

Although this relates to a loop with a low coverage, it is actionable, as we will see next.

Applying previous recommendations

To improve on the performance of loop id 12, we aim to reduce the calls to memmove, while keeping the move to top heuristic.

A possible change is to keep the array of word counts as in function heur, but to start the search from the end of the array, instead of the beginning. This way, adding a new word simply means lling in the next available slot (provided by the memory pool), and updating the top of list, thus eliminating one memmove call for each new word encountered.

This change is implemented in the new function heurinv (for heuristic inversed) is presented below (line 133 highlights the change):

126 static struct result3 heurinv(char **word, int n) { 
127     int page = 1024; 
128     struct record *rec = malloc(page * sizeof(*rec)); 
129     int i, top=-1, score = 0; 
130     struct record r; 
131     for (int iw=0; iw<n; ++iw) { 
132         // the basic sequential search: 
133         for (i=top; i>=0; i--) { 
134             if (strcmp(word[iw], rec[i].word) == 0) { 
135                 rec[i].count++; 
136                 score += top-i; 
137                 if (i == top) 
138                     break; 
139                 // move to top: 
140                 r = rec[i]; 
141                 memmove(rec+i, rec+i+1, (top-i)*sizeof(struct record)); 
142                 rec[top] = r; 
143                 break; 
144             } 
145         } 
146         // word not found, add it to our list 
147         if (i<0) { 
148             // last record, extend storage: 
149             if (top >= page-1) { 
150                 page *= 2; 
151                 rec = realloc(rec, page*sizeof(*rec)); 
152             } 
153             // place on top: 
154             top++; 
155             rec[top] = (struct record) {word[iw], 1}; 
156             score += top; 
157         } 
158     } 
159     return (struct result3) {top, rec, score/n}; 
160 }

Adding our new heuristic function to the previous two functions in the application, yields the following execution output:

The new heuristic heurinv is faster than the previous heur, and so even more than the original naive search.

The MAQAO guided change translates to a 16% improvement.

This reflects the low coverage reported by MAQAO.

This concludes our practical use case with MAQAO

There are other interesting MAQAO features, but to keep this How-To guide short, we will just mention them now.

The MAQAO runs presented in this How-To guide were fast enough to be executed interactively, however MAQAO does support the use of SLURM’s sbatch.

MAQAO also supports the comparison of different reports. In this How-To guide, we could have used this feature to compare the search functions heurinv to heur.

Finally, since MAQAO works on binary executables, other source languages could have been benchmarked from their executables, such as Rust, Golang or Ocaml (compiled). This feature of MAQAO is also helpful for compiler developers: different optimizations can be analyzed from the binary file generated.

Hopefully, this short and practical use case was beneficial and introduced the following:

• MAQAO is very straightforward to use in your performance tuning activity (after choosing the minimum, useful parameters)
• even simple approaches such as the sequential search can be insightful!
• Knuth’s Art of Computer Programming is worth opening every once in a while : )

Producing input data files

To simplify the loading of the input data (relying on libc’s getline and strsep), we must convert a raw text le (such as downloaded from project Gutenberg) to a le with a single line of space separated, upper-case words. The following command can perform this:
cat thoreau.txt | tr -s -c [:alnum:] " " | tr a-z A-Z > THOREAU.txt

Move to top

The heuristic introduced was quali ed as appropriate for many real-world data sets. Move to top can be seen as yet another instance of a general heuristic: what happens next is often what happened recently. Another instance is the Lindy effect.
One caveat, as N. Taleb observed, this heuristic applies well to natural, physical phenonema. It may not apply to artificial, information world.
Finally, G. Gigerenzer has studied and published many results on heuristics.

Full source code (search.c)