In this post, I summarized a YouTube video I enjoyed watching recently.
https://www.youtube.com/watch?v=fV6qYho-XVs
It covers optimizing a function that takes variables of specific types and creates a string, and I really liked the way it analyzed why the results came out that way and improved the code step by step.
- Code 1 (550ns)
The code below takes 550ns to run.
#include <sstream>
using namespace std;
string newOrder(string id, int price, int quantity) {
stringstream s;
s << "NEW " << id << " " << price << " " << quantity;
return s.str();
}
It simply combines characters and values in a stringstream object and returns a single string. If you pass values into that function, the result will look like this.
newOrder("20",10000,30)
-> "NEW 20 10000 30"
What can we optimize in this code?
Just looking at it intuitively, it feels like the slowest part would be that the parameter is passed by value, so a temporary string object is created every time, and the cost of creating a stringstream also feels nontrivial, and so on.
But if you analyze this code with the perf tool, it apparently comes out like this.
26.46% __dynamic_cast
6.00% ostream:_M_insert
5.12% __strcmp_sse2_unaligned
4.10% _int_free
3.99% _basic_streambuf::xsputn
3.72% newOrder
...
Looking at the results, the dynamic conversion routine is producing the heaviest load.
If you look inside that, the locale-related overhead is especially high, and there is also a routine that compares whether it is the locale I configured inside the template (has_facet).
Those parts are causing the overhead from dynamic_cast and strcmp_sse2 logic, so 30% of the time was being spent only on behavior unrelated to the main logic.
(This part gets too long if I write it in detail, so I shortened it. If you are curious, refer to the video.)
- Code 2 (550ns -> 130ns, 4x)
This time, instead of using a string object, it was implemented with sprintf, and the result became more than 4 times faster than before.
void newOrder(char *buf, const char *id, int price, int quantity) {
sprintf(buf, "NEW %s %d %d", id, price, quantity);
}
Now it looks a bit more reasonable, right? Here are the perf results for this.
47.38% vfprintf
21.51% _IO_default_xsputn
9.81% __strchrnul
6.80% _itoa_word
Looking at them one by one from the top,
printf-family functions only differ in where they output, and in the end they call the vfprintf function, so they go through that.
Then _IO_default_xsputn is used to output the string into the buffer, and __strchrnul checks whether it is the end of the string.
The last one, _itoa_word, is responsible for converting numbers into characters.
Evaluating this overall, you can see that 80% of that time is being spent on work unrelated to the functionality we want.
Next, we will make a formatter that contains only the functionality we actually need, and also make itoa a bit faster.
- Code 3 (550ns -> 130 -> 20ns, 27x)
This became code that is 6.5 times faster than the previous result and 27 times faster than the first code.
Here, we will look at the following three things one by one in order.
The Format class, itoa optimization, and the actual usage. The code is a bit long, but the implementation is simple.
class Format {
char _buffer[2048];
int _ptr;
public:
Format() : _ptr(0) {}
void append(char c) { _buffer[_ptr++] = c; }
void append(const char *data) {
while (*data) append(*data++);
}
void finish() { append(' '); }
...
}
Looking at the Format class, it has an internal buffer and cursor (_ptr) when it is created, and its append function receives either a char or a sequence of char* and adds them to the buffer one by one. It is a simple piece of functionality.
There is also a finish function that adds a terminating character at the end.
And the code below is the itoa optimization. It separates digits one by one starting from the last digit, converts them into characters, appends them, and finally reverses that string.
void decimalAppendNonNeg(unsigned value) {
int startPos = _ptr;
do {
append((char)(value % 10) + '0');
value /= 10;
} while (value);
// Reverse the digits.
auto end = &_buffer[_ptr - 1];
auto start = &_buffer[startPos];
while (end > start) swap(*start++, *end--);
}
void decimalAppend(int value) {
if (value < 0) {
append('-');
value = -value;
}
decimalAppendNonNeg(value);
}
It had been a while since I had looked at C code, so adding '0' somehow looked like string concatenation in JavaScript and confused me for a moment, but that is just code that adds the ASCII code for '0'.
For example, if value is 3, it would be like this.
3 + '0' = 3 + 48 = 51 = '3'
In the overall logic, if value is 365, then when the first while loop ends, '563' will be in the buffer, and when the reverse logic below it runs, it will be converted properly into the value '365'.
And if the type is int, it also adds the '-' character when the value is negative.
The actual usage changed as below.
void newOrder(Format &format, const char *id, int price, int quantity) {
format.append("NEW ");
format.append(id);
format.append(' ');
format.decimalAppend(price);
format.append(' ');
format.decimalAppendNonNeg(quantity);
format.finish();
}
It became slightly more complicated than the existing stringstream version, but the performance has improved a lot.
Stopping here would be enough, but there is still a little more to think about.
- Code 4 (550ns -> 130 -> 20ns -> 13ns, 42x)
This code is a full 35% improvement over the previous one.
Which part of the previous code needed to be improved to get this kind of effect?
To list them simply, instead of calculating one digit at a time, calculating two digits at a time should make it twice as fast, right? The loop will also run fewer times. On top of that, if we create a lookup table from 0 to 99 so we do not have to add +'0' every time, it will get even faster.
And reverse is also a problem. After going to the trouble of converting and adding the digits into the buffer, we have to loop digit count / 2 times and swap the back digits with the front digits, right?
If we knew the number of digits in advance, we could fill from that position, so we would not need to reverse it.
I will go through the code that applies these improvements one by one.
static uint16_t _lookup[100];
static void init() {
for (int i = 0; i < 100; ++i) {
auto dig1 = '0' + (i % 10);
auto dig2 = '0' + ((i/10) % 10);
_lookup[i] = dig2 | dig1 << 8;
}
}
First, the lookup table is simple. It assigns the matching characters to the indexes from 0 to 99 and uses them.
At this point, instead of char[2] for each index, it stores the two bytes bundled into a uint16_t with the OR operator.
And finally, to avoid using reverse, we will look at code that finds the number of digits and references that lookup table. This is the most interesting part of this post.
static unsigned const PowersOf10[] =
{1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
static unsigned numDigits(unsigned v) {
auto log2 = 31 - __builtin_clz(v);
auto log10Approx = (log2 + 1) * 1233 >> 12;
auto log10 = log10Approx - (v < PowersOf10[log10Approx]);
return log10 + 1;
}
First, numDigits is a function that returns the number of digits in the number it receives.
But you can see log while calculating the digit count, right? Here, logN means the common logarithm with base 10, and this table makes it easy to understand.
log(10) = 1
log(100) = 2
log(1000) = 3
...
Then floor(log(v))+1 gives us the number of digits right away, doesn't it? Yes. But you know that the log function is very expensive, right? So here, log10 is optimized one more time using integer operations.
This uses the built-in function __builtin_clz, which returns the number of consecutive zeros in the variable passed to it.
For example, the number 35 is 100011 in binary, which has 6 digits, so if you count the consecutive zeros from the front, it returns 26. (32-6=26)
The value returned by clz is the remaining bits, so if you subtract it from 31, you can ultimately get the log2(v) value.
Using the clz built-in function this way, we get log2, then multiply and divide by log2 for the log10 we want to obtain. Since log10(x) / log2(x) is the same no matter what x is, precomputing it gives about 0.30103.
If we multiply by that as-is, it becomes a floating-point operation, so if we convert that value into a fraction whose denominator is a perfect power of 2, it can be converted to about 1233/4096.
Since 4096 is 2^12, the formula below divides by it using a bit operation. Beautiful, isn't it?
log2(x) = 31 - __builtin_clz(v)
log10(x) = log2(x) * log10(x) / log2(x)
log10(x) / log2(x) = 0.301029996...
log10(x) = log2(x) * 1233 / 4096
log10(x) = log2(x) * 1233 >> 12
With this, it was possible to obtain log10(v) by replacing floating-point operations with multiplication plus bit operations.
However, because it is decomposed using logs, it is not an exact value but an approximation, so the PowersOf10 table is used to correct it.
Since using the formula makes it generalizable, it is possible even for 128-bit numbers as well as 32-bit numbers, but for small numbers, I think using branches would not be bad either. (It would also be much easier to analyze later.)
if (v < 10) return 1;
else if (v < 100) return 2;
else if (v < 1000) return 3;
else if (v < 10000) return 4;
...
That was the part that gets the number of digits. Now I will wrap up by looking only at the code that uses it to reference the lookup table.
void decimalAppendNonZero(unsigned value) {
auto digits = numDigits(value);
#define CASE(XX) case XX: decimalPadAppend2<XX>(value); break
switch (digits) {
CASE(1);
CASE(2);
CASE(3);
...
}
}
template<int N>
inline void decimalPadAppend2(unsigned value) {
if (N >= 2) {
for (int i = N - 2; i >= 0; i -= 2) {
auto twoDigits = value % 100;
value /= 100;
*reinterpret_cast<uint16_t *>(_buffer + _ptr + i) = _lookup[twoDigits];
}
}
if (N & 1) _buffer[_ptr] = value % 10 + '0';
_ptr += N;
}
It creates and calls a template function with define, where N is the number of digits. Here you can see that it fills _buffer at address _ptr+i starting from the trailing digits.
You can check the final completed code at this link.
https://godbolt.org/z/3befMz74j
- Reflections (feat. perf)
When writing this post, I wanted to compile the example code myself and base it on results from running perf directly, so I spent all day yesterday trying, but I could not get the results I wanted and eventually copied the metrics from YouTube as they were.
perf is a tool that receives perf_events from the kernel and measures performance, and naturally, since it is tied to the Linux kernel, it was not easy to run Linux with Docker on a Mac and apply it there.
When starting Docker, I had to map privilege mode and the seccomp configuration file, and inside it I also had to install linux_tools separately, but the versions did not match well, so I tried installing several of them and so on.
After all those twists and turns, I installed perf, compiled the same logic, and ran it, but my results looked somewhat different and messy, so it was not going to work.
(I also tried it on WSL2, and there were quite a few things to configure there too.)
Maybe it is because my proficiency is low, but since it feels wasteful to have spent a whole day on it, I will attach just one result from running Code 2 (sprintf) with perf. The command line was like this.
perf record --call-graph dwarf ./test2
- 83.14% 47.97% test2 libc.so.6
+ 47.97% _start
- 35.17% __vfprintf_internal
- 23.66% outstring_func (inlined)
- __GI__IO_default_xsputn (inlined)
__GI__IO_default_xsputn (inlined)
6.65% _itoa_word
- 3.24% __find_specmb (inlined)
__strchrnul
1.62% __GI_strlen (inlined)
- Conclusion
1) When optimizing, do not follow intuition; careful performance measurement must come first.
2) I want to get good at using perf..
3) godbolt is awesome
Previous post: https://frogred8.github.io/
#frogred8 #c++ #performance
