# ASCII to uint16 using fallthrough

## Introduction

Watching this talk, I thought may be I could apply it on parsing smaller numbers, like std::uint16_t. I augmented it though, by using a fallthrough switch statement. Basically, it starts from the back of the std::string_view, and then keeps falling through towards start of the std::string_view.

constexpr std::uint16_t atou16(const std::string_view s)
{
auto first = s.crbegin();
std::uint16_t result = 0;
constexpr std::uint16_t powers[] = {1, 10, 100, 1'000, 10'000};

const std::size_t size = s.size();
switch (size)
{
case 5:
result += powers[4] * (first[4] - '0');
case 4:
result += powers[3] * (first[3] - '0');
case 3:
result += powers[2] * (first[2] - '0');
case 2:
result += powers[1] * (first[1] - '0');
case 1:
result += powers[0] * (first[0] - '0');
default:
;
}

return result;
}


## Baseline

Baseline implementation is the classic loop with multiplication by 10.

constexpr std::uint16_t simple_atou16(const std::string_view s)
{
auto first = s.cbegin();
std::uint16_t result = 0;
while (first != s.cend())
{
result = static_cast<std::uint16_t>(result * 10)
+ static_cast<std::uint16_t>(*first++ - '0');
}

return result;
}


## Timings

Timings show that the new version of the parser is indeed faster in simple cases.

Though it bothers me a bit that the runtime is not linear due to string length. I believe there is also overflow happening in some cases, since std::uint16_t doesn't cover all 5 digit numbers. I closed my eyes on it though, since it is a problem of the benchmark itself.

I've been doing normal stuff like playing music from youtube in the background, so I believe it should be considerable load. I thought about spawning dummy thread that would introduce some more load, but couldn't decide on the more appropriate one.

## Full code

atou16.cpp

#include <string_view>
#include <cstdint>

constexpr std::uint16_t simple_atou16(const std::string_view s)
{
auto first = s.cbegin();
std::uint16_t result = 0;
while (first != s.cend())
{
result = static_cast<std::uint16_t>(result * 10)
+ static_cast<std::uint16_t>(*first++ - '0');
}

return result;
}

constexpr std::uint16_t atou16(const std::string_view s)
{
auto first = s.crbegin();
std::uint16_t result = 0;
constexpr std::uint16_t powers[] = {1, 10, 100, 1'000, 10'000};

const std::size_t size = s.size();
switch (size)
{
case 5:
result += powers[4] * (first[4] - '0');
case 4:
result += powers[3] * (first[3] - '0');
case 3:
result += powers[2] * (first[2] - '0');
case 2:
result += powers[1] * (first[1] - '0');
case 1:
result += powers[0] * (first[0] - '0');
default:
;
}

return result;
}

#include <random>
#include <algorithm>

std::string generate_random_number(unsigned int digits)
{
static std::mt19937 twister{};
static std::uniform_int_distribution<char> distribution{'1', '9'};

std::string number(digits, '\0');
auto generator = [&](){return distribution(twister);};
std::generate(number.begin(), number.end(), generator);

return number;
}

#include <iostream>
#include <atomic>
#include <chrono>
#include <fstream>
#include <vector>

long run_test(unsigned int digits, unsigned int runcount)
{
std::vector<std::uint16_t> values(runcount);
std::vector<std::string> numbers(runcount);
auto generator = [digits](){return generate_random_number(digits);};
std::generate(numbers.begin(), numbers.end(), generator);

using namespace std::chrono;
auto start = high_resolution_clock::now();
for (unsigned int i = 0; i < runcount; ++i)
{
values[i] = atou16(numbers[i]);
}
auto end = high_resolution_clock::now();

for (auto x: values)
std::cout << x << '\n';

std::cout << '\n';

return duration_cast<microseconds>(end - start).count();
}

long run_test_simple(unsigned int digits, unsigned int runcount)
{
std::vector<std::uint16_t> values(runcount);
std::vector<std::string> numbers(runcount);
auto generator = [digits](){return generate_random_number(digits);};
std::generate(numbers.begin(), numbers.end(), generator);

using namespace std::chrono;
auto start = high_resolution_clock::now();
for (unsigned int i = 0; i < runcount; ++i)
{
values[i] = simple_atou16(numbers[i]);
}
auto end = high_resolution_clock::now();

for (auto x: values)
std::cout << x << '\n';

std::cout << '\n';
return duration_cast<microseconds>(end - start).count();
}

int main(int argc, char* argv[])
{
if (argc != 2)
{
std::cerr << "usage: atou16 <output-file-csv>\n";
return 1;
}

std::ofstream timings_out{argv[1]};
if (!timings_out)
{
std::cerr << "output file opening failed\n";
return 1;
}

timings_out << "\"digit count\",fallthrough,simple\n";
for (unsigned int digits = 2; digits < 6; ++digits)
{
timings_out << digits << ','
<< run_test(digits, 1'000'000) << ','
<< run_test_simple(digits, 1'000'000) << '\n';
}
}


CMakeLists.txt

cmake_minimum_required(VERSION 3.2)
project(atou16)

set(CMAKE_CXX_STANDARD 17)

if (NOT CMAKE_BUILD_TYPE)
set(CMAKE_BUILD_TYPE Release)
endif()

if(CMAKE_BUILD_TYPE EQUAL "Release")
set(CMAKE_CXX_FLAGS "\${CMAKE_CXX_FLAGS} -O3 -march=native")
endif()



plotter.py:

#!/usr/bin/python3

import matplotlib.pyplot as plt
import csv
import argparse
import sys

parser = argparse.ArgumentParser()
parser.add_argument('csv_filename', help='file which contains data to plot from')
parser.add_argument('--noshow', action='store_true', help="don't show resulting plot")
parser.add_argument('--nosave', action='store_true', help="don't save resulting plot")
args = parser.parse_args()

labels = []
x = []
fallthrough_y = []
simple_y = []

with open(args.csv_filename, 'r') as csvfile:
labels_row = next(plots)
labels.append(labels_row[0])
labels.append(labels_row[1])
labels.append(labels_row[2])

for row in plots:
x.append(int(row[0]))
fallthrough_y.append(int(row[1]))
simple_y.append(int(row[2]))

fig = plt.figure('ASCII to uint16 timings')
plt.locator_params(axis='x', nbins = 4)
plt.plot(x, fallthrough_y, label=labels[1])
plt.plot(x, simple_y, label=labels[2])

plt.xlabel(labels[0])
plt.ylabel('microseconds')

plt.legend()

if not args.nosave:
fig.savefig('plot.png')

if not args.noshow:
plt.show();


## Concerns

• Benchmark accuracy

Is there anything I can do to remove background noise?

• Powers table

The table might take up the precious space in CPU registers. May be it could be packed somehow?

• Benchmarking methodology

Is it correct?

• Anything else

Any code present here. I know python script is horrible.

• Most of the time program spends generating data. It might be a little bit confusing because the timings are small. Also it prints out a lot of giberrish, it might be a good idea to redirect stdout into /dev/null. It shouldn't affect timings. – Incomputable May 17 '18 at 17:17
• Forgot to add system specs. I’ll add them tomorrow. – Incomputable May 17 '18 at 17:50
• The fall through method. Here you have basically manually unrolled the loop (a standard optimization technique). – Martin York May 17 '18 at 20:07
• @MartinYork, compiler will not unroll because it doesn’t know that size is less than 6 (even though exceeding 5 is UB). Sorry, I thought you implied that fallthrough is redundant. – Incomputable May 17 '18 at 20:10
• Yep. The compiler is not unrolling because it can't determine the run-time size at compile time. But you have basically done the same job. An advanced compiler with good optimizer may have been able to use Duffs Device to un-role the last 5 iterations of the loop. – Martin York May 17 '18 at 21:33

Multiplying each digit by a different power has the same number of multiplications as multiplying each partial sum by 10. But if you look at the generated code, as I found in this post (see function decode) that multiplying by 10 was done with two simple instructions: multiply by 5 is adding via the addressing generator port by using LEA RAX,[RAX+4*RAX] scaled indexing and the index and offset being the same register; then multiplying by 2 is folded into the += with a similar trick.

Multiplying by the various other values will probably not use such tricks, but will need the regular MUL instruction or a longer sequence of adds.

Another thing I found (in that article) is that using 16-bit ints is slowest! The x86 is especially slow for some operations in 16 bits. Using 32 or 64 (in a x64 build) is the fastest. So, I suggest simply changing your data type and running the timing again, to see what happens.

I’ve also found (see this post) that some operations have different speed for signed and unsigned of the same length. Meanwhile, I see presentations that show examples of how unsigned generates worse code with less room for optimization. So, explore different types and chart the results.

Your unrolled loop, like the normal way, has a running dependency on the total. Each line requires the previous to finish before it can be added in.

I’ve had success running two computations in parallel by dividing the problem up and then combining them at the end. So, interleave two different sums, and add them together at the end of the chain.

The compiler will unroll loops by itself.

The switch statement will cause poor branch prediction, and (as noted in the referenced articles) that is a killer for performance.

If you could use SIMD to do all the multiplications in parallel, that would be cool. Load one YMM register with the powers of 10, and the other with the digits.