Replace strings by views when you can

C++ programmers tend to represent strings using the std::string class. Though the implementation might vary, each instance of an std::string might use 32 bytes. Though it is not a large amount of memory, it can add up.

In the Node.js runtime, as part of the build tools, there is a function which precomputes the string representation of all 16-bit integers, followed by a comma.

std::vector<std::string> precompute_string() {
  size_t size = 1 << 16;
  std::vector<std::string> code_table(size);
  for (size_t i = 0; i < size; ++i) {
    code_table[i] = std::to_string(i) + ',';
  }
  return code_table;
}        

Creating 65536 strings uses 2 megabytes on most systems.

What could we do instead?

We could create a single string buffer made of the string ‘0,1,2,…,65535,’, and record the offsets within the string so that we can locate quickly where a given value is. That is, given the integer 500, I want to get immediately the location of the substring ‘500,’. I need two offsets: the offset of the current value and the offset of the next value.

The unique string requires only 382106 bytes, which is quite a bit, but several times less than the 2 megabytes needed by the array of std::string instances.

In C++, you might code it as follows. For simplicity, we can roll our own integer-to-string routine.

std::pair<std::array<char, 382106>, 
  std::array<uint32_t, 65537>> precompute_string_fast() {
  std::array<char, 382106> str;
  std::array<uint32_t, 65537> off;
  off[0] = 0;
  char *p = &str[0];
  constexpr auto const_int_to_str = 
        [](uint16_t value, char *s) -> uint32_t {
    uint32_t index = 0;
    do {
      s[index++] = '0' + (value % 10);
      value /= 10;
    } while (value != 0);

    for (uint32_t i = 0; i < index / 2; ++i) {
      char temp = s[i];
      s[i] = s[index - i - 1];
      s[index - i - 1] = temp;
    }
    s[index] = ',';
    return index + 1;
  };
  for (int i = 0; i < 65536; ++i) {
    size_t offset = const_int_to_str(i, p);
    p += offset;
    off[i + 1] = off[i] + offset;
  }
  return {str, off};
}        

We do not actually need to store the offsets. We can compute them on the fly instead quite economically. However, it takes some effort and unless you are stressed for memory, it is likely better to compute the offsets as they require only 256 KB.

I wrote a benchmark to see how long it takes to precompute the data. On my M2 macBook, I get the following numbers:

So constructing just one string might be twice as fast.

What about query time? Retrieving a reference to an std::string instance is trivial in the case of the array of std::string instances. For the big string case, we return a compute std::string_view instance.

  auto GetCodeFast = [&fast_table, &offsets](uint16_t index) {
    return std::string_view(&fast_table[offsets[index]],
                            offsets[index + 1] - offsets[index]);
  };        

Though it looks like a fair amount of work, I find that processing 65536 randomly generated values is significantly faster with the one-big-string approach.

Generating many non-trivial objects is a performance anti-pattern. Put all your data together when you can.