7
\$\begingroup\$

My goal is to take a uint64_t that represents a fixed-point decimal, and output a string representation of the decimal. The fixed-point representation always has eight decimal places, so for example 1.12345678 is represented as 112345678.

How can I make the following code cleaner and/or faster? Obviously all the character insertions/deletions are very slow, but what's the best way to get rid of those?

std::string uint64_to_string(uint64_t n) {
  auto retval = std::to_string(n);  // Initial conversion to string

  if(retval.size() <= 8) {
    // Add leading zeros if necessary, so for example n=1 becomes 000000001
    size_t num_leading_zeros = 9 - retval.size();
    retval.insert(0, num_leading_zeros, '0');
  }

  // Insert decimal, so 000000001 becomes 0.00000001
  retval.insert(retval.size() - 8, 1, '.');

  // Trim trailing zeros, and trim '.' if it is the last character
  boost::trim_right_if(retval, [](char c) { return (c == '0' || c == '.'); });
  return retval;
}
\$\endgroup\$
4
\$\begingroup\$

You can go old school, and do everything manually in a local character array before doing one string conversion at the end.

std::string uint64_to_string(uint64_t n) {
    const int NDIG = 24;
    const int DECIMALS = 8;
    char buf[NDIG];
    int idx = NDIG;
    int digits = 0;
    bool add_zeros = false;

    buf[--idx] = 0;    // the terminating nul character
    do {
        char ch = '0' + n % 10;
        // Only add the digit if it isn't a trailing zero
        if (add_zeros || ch != '0') {
            buf[--idx] = ch;
            add_zeros = true;
        }
        // Once we have enough decimal digits, add in the decimal point
        if (++digits == DECIMALS) {
            // If we've added something, add in the decimal otherwise leave it off
            if (add_zeros)
                buf[--idx] = '.';
            add_zeros = true;
        }
        n /= 10;
    } while (digits < DECIMALS + 1 || n != 0);
    return std::string(&buf[idx]);
}

We run the loop enough times to process the 8 decimal digits, and one more to get the ones digit (so 0 should come back as 0).

idx initially points to the end of the character buffer, and we build the result string backwards until we've processed the entire number.

Edit: The OP wants to know how to make the function faster. This rewrite is how I would write it. It avoids any time consuming memory allocations (except for the final conversion to string) by starting with a local stack based, fixed sized buffer that is large enough to hold the entire built string. The built string is constructed into this buffer in reverse, which avoids having to figure out what the final length will be.

In addition, the optimizer can work with the entire function, as it does not make any other function calls while building the result string.

It avoids doing work that gets thrown away, like adding trailing zeros or a decimal point.

It can be called by multiple threads, with the only point of contention/block being within the string constructor.

\$\endgroup\$
6
\$\begingroup\$
std::string uint64_to_string(uint64_t n) {

Make interfaces easy to use correctly and hard to use incorrectly.

The function name is confusing as it would lead me to believe that if I called uint64_to_string(1ull), I would expect a returned value of "1".

From your problem statement:

My goal is to take a uint64_t that represents a fixed-point decimal

Instead of using a built-in integer type, leverage the type system by using a fixed-point decimal class.


Ensure you are using <cstdint> and prefix the namespace on the integral type std::uint64_t.


Avoid magic numbers. If 8 is supposed to represent a fixed radix point, you should document that by assigning it to a descriptive variable name. If you use a fixed-point decimal class, you could just refer to its radix point instead.


How can I make the following code cleaner and/or faster? Obviously all the character insertions/deletions are very slow, but what's the best way to get rid of those?

If you've measured and multiple allocations are slowing you down, calculate the string length of your result first, then fill it with the characters. I highly recommend you watch Andrei Alexandrescu's Fastware talk he's been giving for the past few years. He covers this exact topic of converting integers to strings using specific optimization techniques.

\$\endgroup\$
3
\$\begingroup\$

The first thing to do is benchmark what we have. The sample code wasn't complete; I had to add some headers and definitions to make it compile successfully:

#include <boost/algorithm/string/trim.hpp>
#include <cstdint>
#include <string>
using std::uint64_t;
using std::size_t;

I was then able to try a few test cases and spot the bug:

// This should output "10" but instead we get "1":
std::cout << uint64_to_string(1000000000) << std::endl;

This is obviously caused by deleting (in regex notation) [.0]* from the end of the string, when actually \.0* is required.


I then added a main() to exercise the function, taking care to use the results of the function (to avoid having it optimised out):

#include <iostream>
int main()
{
    static const int BITS = 24;
    std::size_t total = 0;

    for (std::uint64_t i = 0;  i < 1<<BITS;  ++i)
        total += uint64_to_string(i << (64-BITS)).size();

    std::cout << total << std::endl;
}

These sixteen million calls consistently take around 2.30 seconds on my machine, when compiled with g++ -O3. That compares to 1.65 seconds for a simple return std::to_string(n), to give an idea of our likely scope for improvement (most of the overhead is in formatting the digits, when small-string optimization does its job properly).


Time to try some variants. I first tried using ostringstream to format the output, but that was significantly slower.

I got fastest results using C-style formatted output, and dividing the input into the whole and fractional parts:

#include <cinttypes>
#include <cstdint>
#include <cstdio>
#include <limits>
#include <string>

// helper - only used at compilation time
static constexpr std::uint64_t pow10(int n)
{
    return n ? 10 * pow10(n-1) : 1;
}

std::string uint64_to_string(std::uint64_t n) {
    static const int frac_digits = 8;
    static const auto frac_10 = pow10(frac_digits);
    static const auto string_length
        = std::numeric_limits<std::uint64_t>::digits10
        + 1 /*round up*/
        + 1 /*decimal point*/
        + 1; /* terminating NUL */

    char s[string_length];
    auto end = s + std::snprintf(s, sizeof s,
                                 "%" PRIu64".%0*" PRIu64,
                                 n/frac_10, frac_digits, n%frac_10);

    // Now remove trailing zeros and point
    while (*--end == '0')
        ;
    if (*end != '.')
        // move the end pointer back, unless we
        // have a decimal point to remove
        ++end;

    *end = '\0';
    return s;
}

With the same compilation options, the benchmark now takes a consistent 2.15 seconds - saving something like 6% of total, or 23% of our potential improvement.

Note that on most processors, the compiler can compute the results of / and % simultaneously, so this splitting is less computational than it looks.


There's still an issue with naming: this isn't really a std::uint64_t, so it would be better treated as a distinct type:

struct fixedpoint_8d {
    std::uint64_t value;
};

You would need then to provide the usual arithmetic operators (don't forget to rescale when you multiply or divide), but unless I'm mistaken, there will be no space or speed penalty to using this abstraction.

That would help prevent mixups with any fixed-point fractions with different scale factor or radix, or with ordinary unsigned 64-bit integers.

You could go further and make it a template if you needed different scale factors (and you'd want to make frac_digits a template parameter of fixedpoint_to_string()).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.