Code performance between if else statements and length of string

Question

I'm writing code that takes a number from a user and prints in back in letters as string. I want to know, which is better performance-wise, to have if statements, like

if (n < 100) {
    // code for 2-digit numbers
} else if (n < 1000) {
    // code for 3-digit numbers
} // etc..

or to put the number in a string and get its length, then work on it as a string.

The code is written in C++.

Answer 1

Of course if-else will be faster.

To compare two numbers you just compare them bitwise (there are different ways to do it but it's a very fast operation).

To get the length of the string you will need to make the string, put the data into it and compute the length somehow (there can be different ways of doing it too, the simplest being counting all the symbols). Of course it takes much more time.

On a simple example though you will not notice any difference. It often amazes me that people get concerned with such things (no offense). It will not make any difference for you if the code will execute in 0.003 seconds instead of 0.001 seconds really... You should make such low-level optimizations only after you know that this exact place is a bottleneck of your application, and when you are sure that you can increase the performance by a decent amount.

Answer 2

Until you measure and this really is a bottleneck, don't worry about performance.

That said, the following should be even faster (for readability, let's assume you use a type that ranges between 0 and 99999999):

if (n < 10000) {
    // code for less or equal to 4 digits
    if (n < 100)
    {
       //code for less or equal to 2 digits
       if (n < 10)
          return 1;
       else
          return 2;
    }
    else
    {
       //code for over 2 digits, but under or equal to 4
       if (n>=1000)
          return 4;
       else
          return 3;
    }
} else {
    //similar
} // etc..

Basically, it's a variation of binary search. Worst case, this will take O(log(n)) as opposed to O(n) - n being the maximum number of digits.

Answer 3

The string variant will be slower:

std::stringstream ss;       // allocation, initialization ...
ss << 4711;                 // parsing, setting internal flags, ...
std::string str = ss.str(); // allocations, array copies ...    

// cleaning up (compiler does it for you) ...
str.~string();
ss.~stringstream();         // destruction ...

The ... indicate there's more stuff happening.

A compact (good for cache) loop (good for branch prediction) might be what you want:

int num_digits (int value, int base=10) {
    int num = 0;
    while (value) {
        value /= base;
        ++num;
    }
    return num;
}

int num_zeros (int value, int base=10) {
    return num_decimal_digits(value, base) - 1;
}

Depending on circumstances, because it is cache and prediction friendly, this may be faster than solutions based on relational operators.

The templated variant enables the compiler to do some micro optimizations for your division:

template <int base=10>
int num_digits (int value) {
    int num = 0;
    while (value) {
        value /= base;
        ++num;
    }
    return num;
}

Answer 4

The answers are good, but think a bit, about relative times.

Even by the slowest method you can think of, the program can do it in some tiny fraction of a second, like maybe 100 microseconds.

Balance that against the fastest user you can imagine, who could type in the number in maybe 500 milliseconds, and who could read the output in another 500 milliseconds, before doing whatever comes next.

OK, the machine does essentially nothing for 1000 milliseconds, and in the middle it has to crunch like crazy for 100 microseconds because, after all, we don't want the user to think the program is slow ;-)