https://johnnysswlab.com/horrible-code-clean-performance/ Johnny's Software LabJohnny's Software Lab Johnny's Software Lab We help you deliver fast software * Home * Performance + 2 Minute Reads + C++ Performance + Standard Library and Performance + Algorithms and Performance + Toolchain and Performance + Help the Compiler + Performance Analysis Tools + Computational Performance + Low Level Performance + Parallelization + Multithreaded Performance + Performance Contest * Debugging * Developer Tools * Need help? * Talks * Contact * About us Menu [image-14][svg] Horrible Code, Clean Performance Posted on April 14, 2023April 14, 2023Author Ivica Bogosavljevic Posted in Help the Compiler2 Replies We at Johnny's Software Lab LLC are experts in performance. If performance is in any way concern in your software project, feel free to contact us. When it comes to software performance, it seems there is no limit to how much one can complicate things in order to make performance improvements. Here we present a short example of optimizations went wild - horrible code with clean performance. Homage to Clean Code, Horrible Performance. Clean Code Let's say we have a class called my_string, that looks like this: class my_string { char* ptr; size_t size; }; The class implements a string, but not a null-terminated kind. Pointer to character block is kept in ptr, and the size of string is stored in size. Let's say we want to implement a find_substring(substring) method, which, tries to find the first occurrence of substring in a string. Here is the naive and straightforward implementation of such method: std::pair find_substring(const my_string& substr) { if (substr.size > size) { return { false, 0 }; } size_t s = size - substr.size; char* ptr_str = ptr; char* ptr_substr = substr.ptr; size_t size_substr = substr.size; for (int i = 0; i < s; ++i) { bool found = true; for (int j = 0; j < size_substr; j++) { if (ptr_str[i + j] != ptr_substr[j]) { found = false; break; } } if (found) { return { true, i }; } } return { false, 0 }; } The hot loop is on lines 10-21. The loop over i iterates the string, and the loop over j tries to find the substring inside the string at position i. This is a very simple and straight-forward solution. The Problem The problem with this approach is the inner loop, which iterates over the substring. It reads the same data from the data cache to the registers over and over. The inner loop over j will most likely break very quickly after it starts. From the performance point of view, it would be very convenient if the data belonging to the substring were kept in CPU registers and not the data caches. If the size of substring were known at compile-time, and small, the compiler could perform an optimization: place the whole substring in registers and never touch memory again. In our case, the compiler doesn't know the size of the substring. In theory, it could put a part of the substring in a register, in our case, the first part. And, when needed, grab the rest from the memory. This would be very beneficial, as part of the substring that is accessed the most is the beginning of the substring. But compilers never do that automatically. Like what you are reading? Follow us on LinkedIn , Twitter or Mastodon and get notified as soon as new content becomes available. Need help with software performance? Contact us! Horrible Code Well, what the compiler can't do, we can do for it. Let's rewrite the original code by allocating a small, fixed sized array to hold the beginning of the substring. Here is the code: std::pair find_substring2(const my_string& substr) { if (substr.size > size) { return { false, 0 }; } static constexpr size_t substring_buffer_max_size = 8; char substring_buffer[substring_buffer_max_size]; // Fill the statically allocated substring size_t substring_buffer_size = std::min(substring_buffer_max_size, substr.size); for (int i = 0; i < substring_buffer_size; ++i) { substring_buffer[i] = substr.ptr[i]; } size_t s = size - substr.size; char* ptr_str = ptr; char* ptr_substr = substr.ptr; size_t size_substr = substr.size; for (int i = 0; i < s; ++i) { bool found = true; int j; for (j = 0; j < substring_buffer_size; ++j) { if (ptr_str[i + j] != substring_buffer[j]) { found = false; break; } } if (found) { for (; j < size_substr; ++j) { if (ptr_str[i + j] != ptr_substr[j]) { found = false; break; } } } if (found) { return { true, i }; } } return { false, 0 }; } This code is much more complex than the original. We introduce a new fixed size array substring_buffer (line 7) and fill it with data from the original substring lines 11-13. In hot loop, we first check if we have a match from the substring_buffer (lines 22-27). If no, we break the inner loop and move to the next value of i. Else, we check if the rest of the substring is a match (lines 30-35). The compiler actually takes this into account when generating code. Here is the assembly output: [image-13][svg] First four characters are kept in registers sil, dil, r8b and r9b. The rest of the characters for the substring are reloaded from memory, but this is not a problem with us because comparison most of the time fails on first character of the substring. Yet, this assembly indicates it makes sense to decrease the size of substring_buffer to 4 characters. It is quite clear why we call this code horrible. A developer unfamiliar with compiler optimizations would look with disgust at this code. But is it worth it? Let's find out. Like what you are reading? Follow us on LinkedIn , Twitter or Mastodon and get notified as soon as new content becomes available. Need help with software performance? Contact us! Benchmarking We measure the performance of this solution on both GCC 11 and Clang 15. As an input we use a string which is 256 MB in size. We are looking for a substring that is not present; this will make sure that the whole string is processed. Here are the runtimes: Original With substring caching Runtime: 0.368 s Runtime: 0.255 s GCC 11 Instr: 2966 M Instr: 2426 M CPI: 0.473 CPI: 0.357 Runtime: 0.272 s Runtime: 0.169 s Clang 15 Instr: 2964 M Instr: 2155 M CPI: 0.35 CPI: 0.301 On both compilers the runtime of the original is worse and the optimized version is both faster and more efficient. Bottom Line Is this code horrible? Yes, it is. Is it fast? As demonstrated, it is fast. Is this performance portable? The speed improvement is portable between GCC and CLANG. It would be possible for a compiler to make this optimization without our intervention, but my gut feeling suggest that compilers that do this are rare. Is it worth it? This is debatable and to a certain extent more a preference than a fact. For me personally, you should never write such a code as a first implementation. It is messy, and the intention is not clear to an average developer. But, if there is a performance bottleneck that you need to address, then this solution would be acceptable. Like what you are reading? Follow us on LinkedIn , Twitter or Mastodon and get notified as soon as new content becomes available. Need help with software performance? Contact us! Tagged: compilercompiler optimizationsdata cacheregisters Post navigation - Decreasing the Number of Memory Accesses: The Compiler's Secret Life 2/2 2 comments / Add your comment below 1. [c234a875ec][svg] Luke says: April 15, 2023 at 7:06 am I immediately implemented this in my own string class, for me implementation details are unimportant, its all API and performance. Ta! Reply 2. [8b82110c3a][svg] Nathanoy says: April 15, 2023 at 5:11 pm Awesome article! Very good read. I think that when deciding to implement an optimization like this, its very important to state the reasoning in surrounding comments. Perhaps even together with an equivalent readable representation. Reply Leave a Reply Cancel reply Your email address will not be published. Required fields are marked * [ ] [ ] [ ] [ ] [ ] [ ] [ ] Comment *[ ] Name * [ ] Email * [ ] Website [ ] [ ] Save my name, email, and website in this browser for the next time I comment. [Post Comment] [ ] [ ] [ ] [ ] [ ] [ ] [ ] D[ ] Like what you're reading? Follow us! * [image-14-][svg]Horrible Code, Clean Performance * [gnu-llvm-][svg]Decreasing the Number of Memory Accesses: The Compiler's Secret Life 2/2 * [IslandOut][svg]Decreasing the Number of Memory Accesses 1/2 * [Basic5-10][svg]Frugal Programming: Saving Memory Subsystem Bandwidth * [image-8-1][svg]Loop Optimizations: interpreting the compiler optimization report Search for: [ ] [Search] Recent Posts * Horrible Code, Clean Performance * Decreasing the Number of Memory Accesses: The Compiler's Secret Life 2/2 * Decreasing the Number of Memory Accesses 1/2 * Frugal Programming: Saving Memory Subsystem Bandwidth * Loop Optimizations: interpreting the compiler optimization report Recent Comments * Nathanoy on Horrible Code, Clean Performance * Healthster on Make your programs run faster: avoid function calls * Luke on Horrible Code, Clean Performance * Ivica Bogosavljevic on The true price of virtual functions in C++ * nowave7 on The true price of virtual functions in C++ Archives * April 2023 * March 2023 * February 2023 * January 2023 * December 2022 * November 2022 * October 2022 * September 2022 * August 2022 * July 2022 * June 2022 * May 2022 * April 2022 * March 2022 * February 2022 * January 2022 * December 2021 * November 2021 * October 2021 * September 2021 * August 2021 * July 2021 * June 2021 * May 2021 * April 2021 * March 2021 * February 2021 * January 2021 * December 2020 * November 2020 * October 2020 * September 2020 * August 2020 * July 2020 * June 2020 * May 2020 Categories * 2 Minute Reads * Algorithms and Performance * C++ Performance * Computational Performance * Data Structure Performance * Debugging * Developer Tools * Help the Compiler * Kernel Space and Performance * Low Level Performance * Memory Footprint * Memory Subsystem Performance * Multithreaded Performance * Parallelization * Performance * Performance Analysis Tools * Performance Contest * Reliability * Standard Library and Performance * System Design * Toolchain and Performance Meta * Log in * Entries feed * Comments feed * WordPress.org (c)2023 Johnny's Software Lab | WordPress Theme by Superb WordPress Themes