Algorithm Selection on x86_64 vs AArch64 Part II

This is part 2 of a series on algorithm benchmarking and selection on x86_64 and AArch64 systems. You can find part 1 here. In the previous post we went through the algorithms we're to benchmark and broke some of their workings down, providing predictions along the way as to how they would stack up. Now it's time to put them to the test and see which comes out on top.

You may have noticed there was a gap in the numbering of the algorithms, between vol2.c and vol4.c. vol3.c is a dummy program provided to us without the volume scaling algorithm, so we can isolate the performance of that one function. Alternatively, we can do so with code by including the C time library and timing the scaling function. This method is less error prone so I'll be benchmarking the algorithms in this way.

The first step is to increase the sample size in our header to work with a substantial enough dataset in our benchmarking to get some meaningful results. I cranked up the sample number to 1600000000, after which I got to work inserting the timing code into each of the programs.

For example vol0.c looks like so:

// ---- This is the part we're interested in!
// ---- Scale the samples from in[], placing results in out[]

        clock_t t;
        t = clock();

        for (x = 0; x < SAMPLES; x++) {
                out[x]=scale_sample(in[x], VOLUME);
        }

        t = clock() - t;

        printf("Time elapsed: %f\n", ((double)t)/CLOCKS_PER_SEC);

I then ran it in a loop to execute 20 times and send the output to a log file like so:

for ((i = 0; i < 20; i++)) ; do ./vol0 ; done |&tee vol0output.log

After following these steps for all the programs I had my results for the AArch64 system ready to compare. I did the same for the x86_64 algorithms, omitting the last two algorithms that use SIMD as they won't run on that architecture. The results are as follows:

AArch64 Results

It looks like these results more or less confirm what we predicted, with the fastest 2 being those that took advantage of SIMD optimization to run concurrently. Vol2.c was way behind in execution time at a whopping average of 11.238 seconds per execution, over double the next slowest algorithm. This confirms that precalculating a table of results can be incredibly costly in compute time due to the cache not being fast enough to outpace the math unit of the processor. The naïve approach in Vol0.c of multiplying each sample by a scale factor with multiple type conversions in the process somewhat unsurprisingly takes the second slowest pace. Avoiding the conversions by bit shifting in Vol1.c yields a slightly faster runtime. Now onto the x86_64 results:

x86_64 Results

The execution times on x86_64 tell a similar story, although there are a few interesting distinctions. First, the type conversions that set Vol0.c back so much in the AArch64 benchmarks seem to have much less of an impact here. Vol0.c and Vol1.c share almost exactly the same runtime, although working with one type and bit shifting did shave off a few milliseconds. Also of note is that Vol2.c doesn't seem to incur the massive performance penalty seen on its AArch64 counterpart. This is evidence that the cache on this machine's processor is much closer to the math unit in terms of getting the results we need.

In conclusion, this was an eye opening experience that confirmed my knowledge about the advantages of SIMD while giving specific evidence to support just how fast it is compared to traditional processing. We also learned just how important it is to know the machine you're optimizing for intimately, to account for differences like that between the algorithm using the precalculated table on the AArch64 machine vs the x86_64 one. Doing so can inform your programming decisions and help avoid making costly assumptions that in this case might mean more than doubling your runtime.