Large array literals cause noticeable slowdown

[Guilherme-Soares-Sequeira]

Parsing files containing large array literals with Clava results in linear slow-downs proportional to the size of the arrays. The same is true for Queries, even when the type that is being searched is unrelated to the array or its elements.

The script used in the tests presented below is the following:

console.log("");

// Query.search(Varref).get().forEach(vr => {
//     console.log(vr.code);
// });

with the query being left out or included in each test variant. The query purposefully finds no elements. The C programs used in the tests all follow the same structure of this program, containing only the declaration of the matrices. Each test was run 5 times consecutively, with 1 warmup run preceding them. The full results of the test can be seen in this spreadhseet (note the multiple sheets).

I have also tested, although rather hastily, how the shape of the matrices impacts performance. The full range of experiments is summarized in the following table:

Shape	No. Elements
1x1	1
128x128	16384
256x128	32768
128x256	32768
2 * 128x128 (equal matrices)	32768
2 * 128x128 (diff. matrices)	32768
4 * 128x128	65536
640x128	81920
6 * 128x128	98304
8 * 128x128	131072

The C program in the 2 * 128x128 (equal matrices) test case contains the declaration of two variables with the same array literal (which is also the same used in the program supplied above). In the 2 * 128x128 (diff. matrices) test case two variables are also declared, but the array literals are different (the first is equal to the one in the program supplied previously, the second one's elements are different but the shape is the same). In the following tests using 4, 6 and 8 128x128 matrices, the two matrices used in the 2 * 128x128 (diff. matrices) test case were duplicated, triplicated and quadruplicated accordingly.

As we can see in the graphic below (look up the tables in the spreadsheet for finer detail), the impact of using different matrices, or even matrices with different shape (128x256 vs 256x128 vs 2 * 128x128) seems to be small, although not entirely negligible in the case with different matrices (~11% increase with the query, ~9% without).

The following graphic depicts the relative amount of time taken by the variants of each test. The test variant with the query seems to add a somewhat constant % of execution time.

Since the shape of the input seems to impact the execution time minimally, I also compared the execution time based on the total amount of input elements. For the N = 32768 case, I used the 2 * 128x128 (diff. matrices) since that is most similar to the other tests. The execution time seems to increase linearly with the number of input elements.

[tiagolascasas]

This is a known issue, and it's good to have some numbers to back it up. In the meanwhile, if this problem is bogging you down, I recommend doing a first pass over your program to replace all Literals on an InitList with a single unparsed statement, e.g.,

const blob = initList.code;
const blobExpr = ClavaJoinPoints.exprLiteral(blob);
initList.removeChildren();
initList.setFirstChild(blob);

This ensures that you only have a single node on your AST representing all of those numbers, instead of thousands of Literals. Assuming that your scripts don't need to interact with these Literals in any way, this works fine. When you rebuild Clava, though, the expression will be parsed back into a list of Literals. You can also decide on a threshold by only folding arrays with over N Literals, while keeping smaller arrays intact, like I've done here.

The long-term solution to the actual problem, I think, would also involve something like this. Maybe the InitList could keep an internal list of Literals, separate from the AST? There is precendent for this, like in static array decls: in the expression int arr[size_expr], size_expr is not an Expression findable by the generic Query, as it exists only inside the Vardecl's VariableArrayType object (e.g., vardecl.type.sizeExpr). @joaobispo thoughts?

[lm-sousa]

I am of the notion that the long term solution is to re-architect the way nodes are stored and traversed in the LARA Framework from scratch. There are fundamental problems in the way this is done that cause massive performance problems.
There are some ideas in the pipeline but not enough time to test and implement them. Plus, a long, technical discussion should be had before making that decision.

[lm-sousa]

I have a PR in the works that should cut this runtime by 40 to 50%