2 ConvertToBase3 methods with great disparity of execution time

Question

I have two methods to do the same thing: convert a number to ternary.

 void dectotern1(int dec) {
 
   const int dim = 9;

   const char* idigits[dim]  = { "00", "10", "20", "01", "11", "21", "02", "12", "22" };
   const char* ldigit[dim]   = {   "",  "1",  "2", "01", "11", "21", "02", "12", "22" };
 
   std::string result;
   for(; dec > dim; dec = dec / dim)
     result += idigits[dec % dim];
   result += ldigit[dec];
 
   std::reverse(result.begin(), result.end());
   printf("> %s \n", result.c_str());
 }

and

void dectotern2(int dec) {
   int termsg[3];
   int i = 2;
   do {
     if(dec != 0) {
       termsg[i] = dec % 3;
       dec = (int)dec / 3;
     } else
       termsg[i] = 0;
     --i;
   } while(i > -1);
 
   printf("%d %d %d", termsg[2], termsg[1], termsg[0]);
 }

And I discovered, contrary to what I expected, that the first method is a lot slower than the latter. I send the decimal 20 to both functions and the execution time is:

exec time dectotern1: 66 microseconds
exec time dectotern2: 1 microseconds

How come I get this result? I thought the string operation would be a lot quicker than the long division method. Am I comparing it right? How could I improve the speed of these methods?

Without displaying (printf), the time captured (in microseconds) is:

exec time dectotern1: 6 microseconds
exec time dectotern2: 0 microseconds

Answer 1

The first way, you are using high-overhead string manipulation. That will dominate the time.

The second way is closer to a "normal" implementation. Instead of an array of int for the digits produced, which you then format using printf(!), generate the char for each digit. Fill the buffer from right to left so you have the finished string of characters ready to use when you are done.

You have two separate conditional jumps in your loop: The while loop looking for how many digits you plan to produce, and testing for 0 each time within the loop. Do it with only one condition around the loop.

The best way is to loop until your value reaches 0 and make sure your buffer is large enough to handle the highest possible number, so you don't have to check for room in the buffer too. If you want zero-filled, you can add more zeros afterwards in a separate step.

string_view format_as_ternary (int32_t val, char* buf, size_t buflen)
{
    // At most 20 ternary digits in a 31-bit number, plus a possible negative sign,
    // plus trailing `\0` just to be nice, means buflen must be >=22.
    // > TODO:  check buflen and generate usage error
    // > TODO:  handle or reject negative numbers (not in original)
    char* const End= buf+buflen;
    char* p = End-1;
    *p-- = '\0';
    while (val) {
        const auto rem = val / 3;
        val %= 3;
        *p-- = char(rem+'0');
    }
    size_t len = End-p-1;  // don't count the nul
    constexpr size_t min_len = 3;
    while (len < min_len) {
        *p-- = '0';
        ++len;
    }
    return {p,End};
}

Typos and mistakes are left as an exercise for the reader to find.

This illustrates the "orthodox"/simple loop to generate digits. Let's look at the expected performance limitations:

There is no dynamic memory allocation. The caller can create the buffer on its stack.

Data is not re-copied.

The division operation on modern CPUs is terribly slow and add insult to injury by utilizing a great deal of CPU resources (execution ports) for the duration, preventing the "superscalar" parallelism you expect of most code. This is mitigated by having the base 3 as a compile-time constant so the division can be eliminated. Generally, the compiler will replace it with a multiply and a few simple instructions (shifts and adds).

Putting the / and % lines back-to-back with the same arguments will help the compiler optimize these together, as the algorithm can produce both simultaneously.

You only have one condition, that of the loop itself. This will predict that the loop will continue and only mis-predicts on the last iteration. This is optimal, compared with some if statement inside a loop that may variously take the true or false paths on different iterations. A mis-predicted branch is slow.

The loop can't do its superscalar magic and work ahead multiple iterations, though, since each iteration needs the value computed by the previous modulo operation. So, you may not use all the instruction-level parallelism that the CPU would be capable of.

That's where tricks to do multiple digits at a time would help. But, would it help enough to be worth the added complexity? I doubt it, especially since the number of iterations is relatively small. You could use Intel-supplied instruction analysis tools that show the pipeline stages, to see how much potential service you are missing. Naturally, that depends on the specific CPU too.

general notes

You are not "converting from decimal". The parameter is not a "decimal" value. It is a built-in integer as represented by the CPU registers. When you do a printf, it has to do a similar process as this to "convert" it to decimal digits! Thus, it clearly is not decimal to begin with.

You are formatting an integer as base-3.

dec = (int)dec / 3;
Here, you not only use a C-style cast, but you are casting to the type it already is! What's the point?

const char* idigits[dim]  = { "00", "10", "20", "01", "11", "21", "02", "12", "22" };
const char* ldigit[dim]   = {   "",  "1",  "2", "01", "11", "21", "02", "12", "22" };

The const in these declarations refer to the character being pointed to, but there is no const on the variable itself. So, every time this function is called it will build the arrays with the pointers to constant character data. That contributes to the slow speed. Use constexpr for things like this.

Stop using printf in C++.

I have two methods to do the same thing:

You have two functions. The term "method" is often used casually to refer to member functions (or possibly just the virtual member functions; it's not a C++ term), but these are not member functions at all.