Настоящая оптимизация на C/C++

+-----------------+---------------+--------------------+-----------------------+ |                 | 250МГц,R10000 | 400 МГц,Pentium II | Строк в исходном коде | +-----------------+---------------+--------------------+-----------------------+ | C               | 0,36с         | 0,30с              | 150                   | | Java            | 4,6           | 9,2                | 105                   | | C++/STL/очередь | 2,6           | 11,2               | 70                    | | C++/STL/список  | 1,7           | 1,5                | 70                    | | Awk             | 2,2           | 2,1                | 20                    | | Perl            | 1,8           | 1,0                | 18                    | +-----------------+---------------+--------------------+-----------------------+

На первый взгляд все закономерно, но если читать книгу а не смотреть красивые таблицы, то выясняется что на языке C, был реализован хэш массив для строк, а на C++ использовалась очередь или список вместо хэш, потому что текущая версия их компилятора не поддерживала хэши, при этом идет упоминание что есть компиляторы с хэш контейнерами, хорошо тут можно понять, любители «идиоматичного» кода, но дальше идет откровенный подлог тестирования, для языков Awk и Perl меняется сам алгоритм, за счет этого достигается скорость и малый размер кода, Собственно читатель и сам может увидеть и протестировать код из книги, он есть в открытом доступе по ссылке, что автор и проделал, действительно код на современном железе и компиляторе сохранял относительные коэффициенты скорости, но стоило переписать код C++ на хэш контейнер, и таким образом скорость C и C++ сравнивается, но можно пойти дальше и переписать алгоритм как это сделано на Awk или Perl, в итоге на моей машине код C++ в 3 раза быстрее чем на C.

#include <iostream> #include <string> #include <unordered_map> #include <vector> std::vector<std::string_view> splitSV(std::string_view str, std::string_view delims = " \t\n\r") {     std::vector<std::string_view> output;     output.reserve(str.size() / 2);     for (auto first = str.data(), second = str.data(), last = first + str.size(); second != last && first != last; first = second + 1) {         second = std::find_first_of(first, last, std::cbegin(delims), std::cend(delims));         if (first != second)             output.emplace_back(first, second - first);     }     return output; }  int main(void) {     srand(time(nullptr));      std::string NONWORD = "\n";     std::string_view w1 = NONWORD;     std::string_view w2 = NONWORD;     std::unordered_map<std::string, std::vector<std::string_view>> statetab;     statetab.reserve(15000);      std::ifstream file("c:\\!\\psalms.txt");     std::vector<char> data(std::istreambuf_iterator<char>(file), {});     auto book = splitSV(std::string_view(data.data(), data.size()));      std::string t;     t.reserve(1000);     for (auto &w3 : book) {         t.clear();         t += w1;         t += w2;         statetab[t].emplace_back(w3);         w2 = w3;         w1 = w2;     }      w1 = w2 = NONWORD;     for (int i = 0; i < 10000; i++) {         t.clear();         t += w1;         t += w2;         auto &vec = statetab[t];         w2 = vec[rand() % vec.size()];         w1 = w2;         //std::cout << w2 << "\n";     }     return 0; }

Задача Алгоритм перевода числа (байтов) в приставку СИ

// From: https://programming.guide/the-worlds-most-copied-so-snippet.html public static strictfp String humanReadableByteCount(long bytes, boolean si) {     int unit = si ? 1000 : 1024;     long absBytes = bytes == Long.MIN_VALUE ? Long.MAX_VALUE : Math.abs(bytes);     if (absBytes < unit) return bytes + " B";     int exp = (int) (Math.log(absBytes) / Math.log(unit));     long th = (long) (Math.pow(unit, exp) * (unit - 0.05));     if (exp < 6 && absBytes >= th - ((th & 0xfff) == 0xd00 ? 52 : 0)) exp++;     String pre = (si ? "kMGTPE" : "KMGTPE").charAt(exp - 1) + (si ? "" : "i");     if (exp > 4) {         bytes /= unit;         exp -= 1;     }     return String.format("%.1f %sB", bytes / Math.pow(unit, exp), pre); }

public static String humanReadableByteCountBin(long bytes) {     long b = bytes == Long.MIN_VALUE ? Long.MAX_VALUE : Math.abs(bytes);     return b < 1024L ? bytes + " B"             : b <= 0xfffccccccccccccL >> 40 ? String.format("%.1f KiB", bytes / 0x1p10)             : b <= 0xfffccccccccccccL >> 30 ? String.format("%.1f MiB", bytes / 0x1p20)             : b <= 0xfffccccccccccccL >> 20 ? String.format("%.1f GiB", bytes / 0x1p30)             : b <= 0xfffccccccccccccL >> 10 ? String.format("%.1f TiB", bytes / 0x1p40)             : b <= 0xfffccccccccccccL ? String.format("%.1f PiB", (bytes >> 10) / 0x1p40)             : String.format("%.1f EiB", (bytes >> 20) / 0x1p40); }

Возьмем из поста два кода: один общий для 10-ого основания и второй для 2-ого. Сразу хочу заметить, если код для 10-ого был исправлен для округлений, то код для 2-ого на самом деле не работает, все числа округлятся неверно, поэтому возьмем его лишь для ориентировочного сравнения по скорости.

Сразу бросается в глаза, что код для 10-ого основания выражен через тип double. Известно, что плавающие числа вычисляются дольше чем целые. Заменим код на

std::string sufx[]{"b", "Kb", "Mb", "Gb", "Tb", "Pb", "Eb"}; void bytes_to_print(unsigned long long bytes) {     unsigned long long index{0};     unsigned long long fract;     while (1000 <= bytes) {         fract = bytes;         bytes /= 1000;         index++;     }     fract = fract % 1000 * 1000 / (1000 * 1000 / 100);     std::cout << std::setw(4) << bytes << '.' << std::setfill('0') << std::setw(2) << fract << std::setfill(' ') << ' ' << sufx[index] << '\n'; }

В коде решается проблема округления, а также целый тип не переводится в плавающий тип, хорошо. Можно ли избавиться от цикла и множества делений? Можно, но для 2-ого основания, вот на это коде:

std::string sufx[]{"b", "Kb", "Mb", "Gb", "Tb", "Pb", "Eb"}; void bytes_to_print(unsigned long long bytes) {     unsigned long long index = bytes;     index |= index >> 1;     index |= index >> 2;     index |= index >> 4;     index |= index >> 8;     index |= index >> 16;     index |= index >> 32;     index &= 0b0001'0000'0000'0100'0000'0001'0000'0000'0100'0000'0001'0000'0000'0100'0000'0000ull;     index += index << 30;     index += (index << 20) + (index << 10);     index >>= 60;     unsigned long long fract = bytes;      bytes >>= index * 10;     fract >>= (index - 1) * 10;     fract = fract & 0b11'1111'1111'00'0000'0000 / 10485;          std::cout << std::setw(4) << bytes << '.' << std::setfill('0') << std::setw(2) << fract << std::setfill(' ') << ' ' << sufx[index] << '\n'; } 

сводная таблица производительности на одной конкретной машине с конкретными версиями операционной системы и компиляторов. Ваши коофиценты скорости времени могут отличаться от заявленных, критическое время это когда алгоритм проходит все итерации цикла (при больших числах)

+-------------+---------------+-------------------+ | Алгоритм    | среднее время | критическое время | +-------------+---------------+-------------------+ | Java 10-ого | 3.53c         | 9.43c             | | Java 2-ого  | 2.65c         | 7.43c             | | С++ 10-ого  | 1.81c         | 3.29c             | | C++ 2-ого   | 1.12с         | 1.24c             | +-------------+---------------+-------------------+

При большем количестве кода алгоритм выполняется быстрее за счет бинарных операций, суперскалярности системы, а также кэшируемости таблицы приставок и нулевой нагрузки на шину оперативной памяти.

Литература к прочтению

• Практика программирования [Брайан У. Керниган, Роб Пайк] The Practice of Programming — о том как должен мыслить программист с точки зрения эффективности кода.
• Жемчужины творчества программистов [Д. Бентли] Programming Pearls — Какие мозголомные решение принимаються когда ты программируешь на машине с ограниченымии ресурсами(первое издание).
• Пионеры программирования. Диалоги с создателями наиболее популярных языков программирования [Федерико Бьянкуцци, Шейн Уорден] Masterminds of Programming, Conversations with the Creators of Major Programming Languages — почему так много языков, и большенство из них медленные.