Naive

The natural method one may think of is a byte-by-byte approach.

#include <stdint.h>
#include <stdlib.h>
typedef uint8_t byte_t;

void add_bytes_naive(byte_t *ret, byte_t *a, byte_t *b, size_t n)
{
  byte_t *carry = ret + n;
  *carry = 0;
  for (size_t i = 0; i < n; ++i)
  {
    ret[i] = a[i] + b[i] + *carry;
    if (UINT8_MAX - a[i] < b[i] || UINT8_MAX - a[i] - *carry < b[i])
      *carry = 1;
    else
      *carry = 0;
  }
}

For the uninitiated and, frankly, lame people who don’t know C, here’s an explanation of the function per loop:

1. Perform an addition
2. Store the result
3. Compute if a carry is needed or not

This is the simplest algorithm I could think of, and should be the kind of thing you reach for in those stupid Leetcode questions with arbitrary precision decimal numbers through… linked lists… (the horror… the absurdity…).

Can we do better?

Optimising the hot loop

The hot part of this solution is obviously the loop: it’s where all the actual computation happens. If we optimise the loop, we optimise the algorithm.

for (int i = 0; i < 5; ++i)
  printf("%d\n", i);

printf("%d\n", 0);
printf("%d\n", 1);
printf("%d\n", 2);
printf("%d\n", 3);
printf("%d\n", 4);

typedef uint64_t word_t;
#define WORD_SIZE sizeof(word_t)

const word_t bound = (size / WORD_SIZE) + (size % WORD_SIZE == 0 ? 0 : 1)

for (word_t i = 0; i < bound; ++i)
{
  const word_t index = WORD_SIZE * i;
  const word_t _size = MIN(WORD_SIZE, size - index);
  const word_t max =
      _size == WORD_SIZE ? UINT64_MAX : ((word_t)1LU << _size) - 1;

word_t a_i = 0, b_i = 0;
memcpy(&a_i, a + index, _size);
memcpy(&b_i, b + index, _size);

word_t res = a_i + b_i + ret[size];
memcpy(ret + index, &res, _size);

if ((max - a_i) < b_i || (max - a_i - ret[size]) < b_i)
  ret[size] = 1;
else
  ret[size] = 0;

Profiling code in C

The idea behind profiling is to run a lot of inputs against the algorithm, then measure the resources consumed. Any solution to this problem shouldn’t require any heap usage, so CPU time is the only metric to measure.

For a good sample set, one should have multiple trials of any one input instance, generating a mean and standard deviation on that input. These measures make it very clear when something is off and whether your testing setup needs more tweaking, so it’s a good idea to calculate them. In total you should have \(mn\) data points, where m is the number of unique input instances and n is the number of trials per instance.

So what input should we use? Let’s use powers of 2 for the sizes of the input, with the input data being filled with random bytes generated at runtime. From my own testing, no statistically interesting results occur until we go for really large powers, so I chose the range of \(2^{20}\) to \(2^{29}\). Though it’s severely unlikely you’re ever going to be computing numbers with 8 million bits of precision, this should force the fast CPUs of today to actually expend some noticeable time in computing it. For the number of trials, I chose 10 for no particular reason. Large number of trials would increase the amount of data, but it would take more than a couple of minutes to compute all these trials if I chose higher.

With just a glance at the problem at hand, we can see that the performance is clearly bounded by size; the larger the input, the longer the computation will take. With some tissue paper mathematics, if it takes n seconds to compute \(2^{20}\) byte numbers, then it should take roughly \(n2^{9}\) seconds to compute \(2^{29}\) byte numbers. This gives us an hypothesis to see if the measurements are correct.

In C we can use time.h, in particular clock(), to get CPU time.

A rough template of the profiler would be:

clock_t start = clock(), diff;
algorithm(); // perform computation
diff = clock() - start;
long msec = (diff * 1000) / CLOCKS_PER_SEC;

The variable msec is the number of milliseconds the algorithm took to compute. Note the use of CLOCKS_PER_SEC, such that msec will be the actual CPU time taken.

The machine I used to get measurements has a 2nd gen i7 (8 cores), 16GB RAM and quite literally nothing else to do; it’s a headless server with no other processes running on it. This should provide clear data with little to obfuscate the results.

Pretty graph

Here’s a graph of powers of 2 against time taken, with error bars for the deviation:

It really displays the difference in the two algorithms at scale.

Conclusion

This article and the measurements made are a testament to performance measuring, in particular the fact that one cannot provide any assertions on performance without statistical evidence. Under any number of heuristics the optimised code may be considered “less optimal” than the naive code, but the performance metrics prove that it is indeed the optimal solution.

My next article will be on exploring x86… maybe.

Finally, all the code written (including the profiler) are stored here so go take a look at it.