Оптимизация кода: процессор

Все программы должны быть правильными, но некоторые программы должны быть быстрыми. Если программа обрабатывает видео-фреймы или сетевые пакеты в реальном времени, производительность является ключевым фактором. Недостаточно использовать эффективные алгоритмы и структуры данных. Нужно писать такой код, который компилятор легко оптимизирует и транслирует в быстрый исполняемый код.

image

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

На написание этой статьи меня вдохновила пятая глава из книги Computer Systems: A Programmer's Perspective. Все программы протестированы на машине с процессором Pentium 2117U, производительность на вашей машине может быть другая. В другой статье из этой серии, «Оптимизация кода: память», мы рассматриваем техники оптимизации для лучшего использования кэша.

Блокировщики оптимизации


Компиляторы сами пытаются оптимизировать код. Когда GCC запущен с параметром -Og, он выполняет базовый уровень оптимизации, с параметром -O1 первый уровень оптимизации. Существует и более высокие уровни оптимизации: -O2, -O3 и т. д. Чем выше уровень оптимизации, тем более радикальные изменения компилятор вносит в программу. Компиляторы могут применять только безопасные оптимизации. Это значит, что компилятор может изменять программу только так, чтобы это не изменило её поведение для всех входных данных.

Нам, как программистам, нужно понимать, что существуют определённые характеристики кода, которые не позволят компилятору совершить оптимизацию. Мы их называем блокировщиками оптимизации. Рассмотрим два типа блокировщиков оптимизации. Одним из них являются указатели. Компилятор не может точно знать, будут ли два указателя указывать на одну и ту же область памяти, и поэтому не выполняет некоторые оптимизации. Рассмотрим пример:

void twiddle1(long *xp, long *yp) {
    *xp += *yp;
    *xp += *yp;
}

void twiddle2(long *xp, long *yp) {
    *xp += 2*(*yp);
}

Функция twiddle2 выглядит более эффективной, она выполняет всего три запроса к памяти (прочитать *xp, прочитать *yp, записать *xp), в то время, как twiddle1 выполняет шесть запросов (четыре чтения и две записи). Можно ожидать, что эти две функции имеют одинаковое поведение. Однако представьте, что xp и yp указывают на одну и ту же ячейку памяти. Тогда twiddle1 увеличит *xp в четыре раза, а twiddle2 — в три раза. Эти функции имеют разное поведение в некотором случае. По этой причине компилятор не посмеет трансформировать менее эффективную функцию в более эффективную.

Другой блокировщик оптимизации — вызов функций. Вообще, вызовы функций влекут накладные расходы, и нам нужно стараться их избегать. Рассмотрим пример:

long f();

long func1() {
    return f() + f() + f() + f();
}

long func2() {
    return 4*f();
}

Первая функция вызывает f четыре раза, когда вторая — только один раз. Мы ожидаем, что компилятор догадается и преобразует первую функцию во вторую. Но функция f может иметь побочные эффекты, она может изменять глобальное состояние, как в этом примере:

long counter = 0;

long f() {
    return counter++;
}

В этом члучае func1 и func2 вернут разные результаты. Компилятору тяжело определить, имеет вызов функции побочные эффекты или нет. Когда он не может этого сделать, он рассчитывает на худшее и не выполняет оптимизацию.

Демонстрационная программа


Обычно медленные программы выполняют вычисления над большими массивами данных. Разумно будет оценивать эффективность таких программ в среднем количестве тактов, которые процессор тратит на обработку одного элемента массива. Введём метрику CPE (cycles per element). Если мы говорим, что программа имеет производительность CPE 2.5, значит она в среднем тратит 2.5 такта процессора на обработку одного элемента.

Мы представим простую программу, на примере которой продемонстрируем мощные приёмы оптимизации. Структура vec является вектором элементов типа float. Функция combine0 вычисляет результат перемножения всех элементов вектора. Эту функцию мы и будем оптимизировать. Размер массива сделаем 5000 и инициализируем его случайными числами.

typedef struct {
    long len;
    float *data;
} vec;

long vec_len(vec *v) {
    return v->len;
}

void combine0(vec *v, float *dest)
{
    long i;
    *dest = 1;
    for (i = 0; i < vec_len(v); i++) {
        *dest *= v->data[i];
    }
}

#define SIZE 5000
float a[SIZE];
vec v = {SIZE, a};

int main() {
    float res;
    for (i = 0; i < SIZE; i++)  // инициализация вектора случайными числами
        a[i] = rand();

    combine0(&v, &res);
}

Все программы в этой статье мы будем компилировать при помощи GCC с параметром -Og (базовый уровень оптимизации). Скомпилировав программу и сделав необходимые замеры, я получаю производительность CPE 11.05.

Для измерения CPE можно использовать инструкцию rdtsc, это счётчик тактов с момента последнего сброса процессора. Нужно сравнить значения счётчика до и после выполнения программы. Предупреждаю, что это ненадёжный метод. Для большей надёжности можно просто замерять потраченное процессорное время. Следующая программа пусть будет шаблоном, который демонстрирует оба метода.

Измерение производительности кода
#include <time.h>
#include <stdio.h>

// Получить количество тактов с момента последнего сброса процессора
static __inline__ unsigned long long rdtsc(void)
{
    unsigned hi, lo;
    __asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
    return ( (unsigned long long)lo)|( ((unsigned long long)hi)<<32 );
}

// Количество элементов, обрабатываемых в цикле
#define SIZE 100000000

int main(void)
{
    double time1 = clock() / (double)CLOCKS_PER_SEC;
    long cycles1 = rdtsc();
    //---------- ИЗМЕРИТЬ ЭТОТ КОД ----------
    for (int i = 0; i < SIZE; i++) {
        i * i;
    }
    //----------------------
    double time2 = clock() / (double)CLOCKS_PER_SEC;
    long cycles2 = rdtsc();

    long cycles = cycles2 - cycles1;      // Столько тактов было потрачено
    double cpe = cycles / (double)SIZE;   // Столько тактов было потрачено на один элемент
    double cpu_time = time2 - time1;      // Потраченное процессорное время

    printf("CPU TIME: %.2f sec\n", cpu_time);
    printf("CPE:      %.2f\n", cpe);
}



Избавляемся от неэффективностей цикла


Обычно самым интенсивным местом программы являются циклы, особенно самый внутренний цикл. Именно там и нужно прежде всего искать возможности для оптимизации. В цикле нашей программы мы постоянно вызываем функцию vec_len, которая возвращает длину вектора. Бессмысленно делать это в каждой итерации, потому что длина вектора на протяжении цикла не меняется. Разумнее будет вызвать эту функцию один раз и сохранить результат в переменную. Поэтому вынесем вызов этой функции за пределы цикла.

void combine1(vec *v, float *dest)
{
    long i, len = vec_len(v);
    *dest = 1;
    for (i = 0; i < len; i++) {
        *dest *= v->data[i];
    }
}

Производительность новой версии не изменилась — CPE 11.05. Видимо, компилятор сам догадался выполнить эту оптимизацию. Давайте запустим GCC без параметра -Og и скомпилируем обе версии функции вообще без оптимизации. Теперь разница заметна: combine0CPE 12.7, combine1CPE 11.1.

В данном случае компилятор догадался вставить тело функции в место вызова этой функции. Но часто компилятор не будет этого делать, потому что не сможет определить, имеет функция побочные эффекты или нет. Если функция производит какие-то дополнительные действия, подобная трансформация может изменить поведение программы. Как экстремальный пример рассмотрим цикл, который превращает прописные буквы в строчные:

void lower(char *s) {
    for (long i = 0; i < strlen(s); i++)
        if (s[i] >= 'A' && s[i] <= 'Z')
            s[i] -= ('A' - 'a'); 
}

Функция strlen обходит всю строку пока не встретит нулевой символ, и делает это в каждой итерации. Это катастрофически замедляет программу. Для больших строк цикл будет выполняться в тысячи раз медленнее, чем более эффективный. В идеале компилятор должен распознать, что вызов strlen всегда возвращает то же самое значение, и вынести его за пределы цикла. Но для этого нужно глубоко проанализировать тело цикла и определить, что хотя программа и изменяет символы в строке, никакой символ она не превращает в нулевой. Это за пределами возможностей современных компиляторов.

Избавляемся от лишних обращений к памяти


Многие программы часто обращаются к памяти для чтения или записи. Это занимает много времени. Желательно работать с регистрами процессора, а не с памятью. Для таких программ нужно искать возможность ввести временную локальную переменную, в которую производить запись, и только через какое-то время произвести запись из этой переменной в память.

Подсчитаем сколько раз мы обращаемся к памяти в каждой итерации. Мы читаем элемент из массива, читаем dest, складываем эти значения и записываем результат в dest. Всего три обращения к памяти. Нам не нужно каждый раз читать и писать в dest после обработки очередного элемента. Мы введём временную переменную-аккумулятор, в которой будем хранить результат, и только в самом конце произведём запись в dest. Саму переменную-аккумулятор компилятор разместит в регистре, поэтому мы избавимся от ненужных обращений к памяти.

void combine2(vec *v, float *dest)
{
    long i, len = vec_len(v);
    float acc = 1;
    for (i = 0; i < len; i++) {
        acc *= v->data[i];
    }
    *dest = acc;
}

Теперь мы выполняем только одно обращение к памяти в каждой итерации. Производительность улучшается с CPE 11.05 до CPE 5.02. Если вы ожидаете, что компилятор сам догадается и выполнит эту оптимизацию, то подумайте что будет если dest указывает на какой-либо элемент в векторе. В этом случае версии с аккумулятором и без вычислят разное значение. Компилятор не может знать чему будут равны указатели, поэтому готовится к наихудшему и не выполняет оптимизацию. Вызовы функций и указатели серьёзно блокируют оптимизирующие возможности компилятора.

Раскрутка цикла


Мы достигли CPE 5.02. Это не простое число, мой процессор тратит 5 тактов на выполнение умножения чисел с плавающей точкой. Можно сказать, что мы достигли определённой нижней границы.

Мой процессор тратит один такт на выполнение сложения чисел типа int. Интересно, если вместо перемножения значений типа float, я буду складывать значения типа int, добьюсь ли я производительности CPE 1.0? Я вношу необходимые изменения в свою программу. Запускаю и получаю всего CPE 1.58. Откуда такая неэффективность?

Всё дело в том, что при выполнении цикла, процессор выполняет не только инструкции вычисления, в которых мы заинтересованы, но также инструкции, обслуживающие цикл: инкрементирование счётчика, проверка условия, переход в начало цикла. То есть обслуживание цикла имеет свои накладные расходы, и процессор производит много ненужной работы. Если тело цикла маленькое, эти «пустые» вычисления занимают большую долю процессорного времени.

Техника раскрутки цикла заключается в том, что за одну итерацию обрабатываются не один, а несколько элементов. Мы как бы «раскручиваем» цикл, увеличивая длину его тела и уменьшая количество витков. Таким образом мы выполняем меньше итераций, за одну итерацию совершаем больше полезной работы, и накладные расходы составляют уже не такую большую долю. Давайте немного изменим функции, складывающую целые числа:

void combine_plus(vec *v, int *dest)
{
    long i, limit = vec_len(v)-1;
    int acc = 0;
    for (i = 0; i < limit; i+=2) {
        acc = acc + v->data[i] + v->data[i+1];
    }
    if (i < len) acc += v->data[i];  // добавить последний элемент, если он не обработан
    *dest = acc;
}

Теперь программа добавляет к аккумулятору два элемента за итерацию. Обратите внимание, что последний элемент может быть не обработан в цикле, поэтому его нужно добавить к аккумулятору позже. CPE падает с 1.58 до 1.15. Обрабатывая четыре элемента за итерацию, я получаю CPE 1.03, что близко к тому значению, которое хотел получить.

CPE 5.02, который мы получили, равно количеству тактов, которые тратит мой процессор на совершение умножения чисел с плавающей точкой. Для обработки одного элемента мы выполняем одно умножение, и, казалось бы, это предел, ниже которого мы не опустимся. Но на самом деле мы можем достигнуть CPE 1.04 . Чтобы понять более продвинутые техники оптимизации, нужно сперва разобраться, как работает процессор.

Введение в работу процессора


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

Процессор разбит на части, которые выполняют разные типы задач, мы их называем функциональными блоками. Каждый блок выполняет определённый ряд задач: чтение из памяти, запись в память, сложение целых чисел, умножение чисел с плавающей точкой и т. д. Мой процессор имеет два блока, которые выполняют сложение целых чисел. Это значит, что он может параллельно выполнять два сложения.

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

Считывание инструкций наперёд называется предвыборкой. Если во время предвыборки процессор встречает ветвление (к примеру, конструкция if-else), он пытается угадать, какая ветвь будет взята и считывает инструкции оттуда. Если позже он понимает, что была взята неправильная ветвь, он сбрасывает произведённые вычисления, восстанавливает предыдущее состояние и идёт по другой ветви. Такая ошибка стоит процессору нескольких потерянных тактов. Для многих процессоров это примерно 20 тактов.

Конвейер


Мой процессор имеет один функциональный блок, выполняющий умножения чисел с плавающей точкой, и на одно умножение он тратит пять тактов. И казалось бы, если нам нужно выполнить N умножений, нам придётся потратить 5*N тактов. Но это не так, благодаря такому устройству как конвейер.

В американских фильмах вы наверняка видели как клиент в столовой проходит с подносом нескольких поваров, и каждый ковшом накладывает ему что-то своё. Это и есть конвейер. Представим столовую с пятью поварами, и обслужиться у одного из них занимает один такт. Они могли бы обслуживать клиентов так: сначала один клиент проходит всех поваров, потом второй, потом третий и так далее. В этом случае каждые пять тактов от них отходил бы клиент с полным подносом. Но это неэффективно. Лучше если все клиенты выстроятся в очередь, и каждый такт эта очередь будет продвигаться к следующему повару. В этом случае каждый такт от поваров будет отходить клиент с полным подносом. Заметьте, что обслуживание одного клиента всё равно будет занимать пять тактов, но обслуживание N клиентов (если N велико) займёт примерно N тактов.

По принципу конвейера устроены функциональные блоки в процессоре. Они разделяют всю работу на несколько этапов, и на разных этапах могут одновременно обрабатываться разные инструкции. Несмотря на то, что выполнение одной инструкции может занимать несколько тактов, многие блоки могут принимать в конвейер новую инструкцию каждый такт. Такие блоки называются полностью конвейерными. Все операции, кроме деления, выполняются в полностью конвейерном режиме. Деление считается сложной операцией, занимает 3-30 тактов и вообще не имеет конвейера.

Зависимость данных и несколько аккумуляторов


Но если конвейер позволяет нам тратить один такт на операцию, почему тогда мы получили CPE 5.02, а не CPE 1.02? Всё дело в такой плохой вещи как зависимость данных. Вернёмся к примеру со столовой. Допустим, первый повар в столовой накладывает или рис или гречку, и по странному правилу, каждый клиент, пройдя всех поваров, решает что должен наложить первый повар следующему клиенту. Тогда мы не можем начать обслуживание следующего клиента пока текущий клиент не пройдёт всех поваров. Нам приходится ждать, потому что есть определённая зависимость. Также и в работе процессора. Мы говорим, что между данными есть зависимость, если для начала работы над одними данными нам нужны другие данные, и мы должны дождаться завершения работы над ними.

В нашей программе такую зависимость данных создаёт переменная-аккумулятор. Процессор мог бы вычислять инструкции цикла на несколько итераций вперёд. Но в каждой итерации мы вычисляем новое значение аккумулятора, учитывая его значение, вычисленное в предыдущей итерации. Поэтому мы не можем начать умножение в следующей итерации, пока полностью не завершится умножение в предыдущей. То есть каждое умножение должно пройти весь конвейер, прежде чем мы отправим в конвейер следующее. Это и мешает нам загрузить конвейер.

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

Для большей наглядности мы упростим код и будем передавать в функцию не векторную структуру, а сразу массив чисел. Такое изменение на производительность не повлияет, зато читать код станет проще. Следующая техника называется раскруткой цикла с несколькими аккумуляторами.

float combine3(float a[], long size)
{
    long i, limit = size-1;
    float acc0 = 1;
    float acc1 = 1;

    for (i = 0; i < limit; i+=2) {
        acc0 *= a[i];
        acc1 *= a[i+1];
    }
    while (i < size) acc0 *= a[i++];
    return acc0 * acc1;
}

Как видите, мы поддерживаем два независимых аккумулятора, которые в конце перемножаются, чтобы дать окончательный результат. CPE падает до с 5.02 до 2.5. Давайте сделаем раскрутку с четырьмя аккумуляторами:

float combine4(float a[], long size)
{
    long i, limit = size-3;;
    float acc0 = 1;
    float acc1 = 1;
    float acc2 = 1;
    float acc3 = 1;

    for (i = 0; i < limit; i+=4) {
        acc0 *= a[i];
        acc1 *= a[i+1];
        acc2 *= a[i+2];
        acc3 *= a[i+3];
    }
    while (i < size) acc0 *= a[i++];
    return acc0 * acc1 * acc2 * acc3;
}

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

Мой процессор имеет только один функциональный блок, который выполняет умножение чисел с плавающей точкой. Core i7 Haswell имеет два таких блока, на нём наше приложение может достичь CPE 0.5, но пришлось бы использовать больше аккумуляторов. Вообще, если операция занимает C тактов и её выполняют N блоков, необходимое количество аккумуляторов может быть C*N.

Ассоциативность


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

Если у нас есть последовательность целых чисел, то неважно в каком порядке мы их будем складывать или перемножать, мы всё равно получим один и тот же результат, даже если будет переполнение. Мы говорим, что операции сложения и умножения для целых чисел являются ассоциативными операциями. Сложение и умножение для чисел с плавающей точкой не являются ассоциативными. Допустим в последовательности чисел типа float есть очень маленькие числа и очень большие. Если мы сначала перемножим очень маленькие, то получим ноль. Умножая все остальные на ноль, мы в итоге получим ноль. Если же изначально очень маленькие мы будем умножать на очень большие, в итоге мы могли бы получить адекватный результат.

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

Векторизация


Мы ещё можем улучшить производительность. CPE 1.04, который мы достигли — не предел. Современные процессоры поддерживают специальные расширения, называемые SSE или AVX, которые позволяют работать над векторами данных. В процессоре есть специальные векторные регистры, называемые %ymm0-%ymm15, размером 16 или 32 байта. Текущие AVX регистры имеют размер 32 байта и могут содержать четыре 64-битных числа, или восемь 32-битных числа, не важно целых или с плавающей точкой. Можно считать из памяти в один такой регистр сразу 32 байта данных, считать 32 байта данных в другой регистр и выполнить арифметическую операцию сразу над четырьмя или восьмью числами параллельно.

Это железо находится в процессоре неиспользуемое, пока вы явно не задействуете его. GCC поддерживает расширение языка C, которое позволит вам это сделать. Можно, конечно, написать код на ассемблере, но тогда программа перестанет быть переносимой. Используя эти возможности процессора, можно дальше увеличить производительность программы в 4 или 8 раз, в зависимости от размера регистров. В нашем случае, мы могли бы понизить CPE до 0.25 или 0.12.

Итоги оптимизации


Мы начали с программы, которая имела производительность CPE 11.05. Потом мы избавились от лишних вызовов функций и запросов к памяти и улучшили производительность до CPE 5.02. Потом использовали раскрутку цикла с несколькими аккумуляторами. Так смогли избавиться от зависимости данных, смогли полностью загрузить конвейер и получили CPE 1.04. То есть мы увеличили скорость выполнения программы в 11 раз. Используя векторизацию, можно заставить программу выполняться в 44-88 раза быстрее по сравнению с первоначальной версией.

Вы можете возразить, что мы применяем все эти техники оптимизации и сравниваем производительность с первоначальной версией, которая была скомпилирована лишь с базовым уровнем оптимизации. И, возможно, нам не нужно знать все эти техники, потому что компилятор применит их за нас, если мы прикажем ему компилировать с высоким уровнем отпимизции. Хорошо, давайте скомпилируем первоначальную версию программы с высоким, третьим уровнем оптимизации и посмотрим на что способен компилятор. Я получаю производительность CPE 5.02. Это далеко от CPE 1.04, которое мы получили, вручную трансформируя код. Знание всех этих приёмов оптимизации позволило нам добиться пятикратного увеличения производительности. Мы можем использовать векторизацию, чтобы дальше увеличить производительность в 4-8 раз, компилятор за вас этого не сделает.

Проблемы и ограничения


Количество функциональных блоков, которые выполняют чтение и запись в память, может быть узким местом производительности. Заметим, что эти блоки полностью конвейерные и могут принимать новую инструкцию каждый такт. Мой процессор имеет один блок, выполняющий чтение данных из памяти в процессор. Если для обработки одного элемента, мне нужно будет получить из памяти два числа, я не смогу сделать лучше, чем CPE 2.0, потому что получение двух чисел займёт два такта. Core i7 Haswell имеет четыре блока, которые выполняют сложения целых чисел. Но если вам нужно сложить элементы целочисленного вектора, вы не сможете добиться CPE 0.25. Потому что этот процессор имеет только два блока, выполняющих чтение из памяти — это устанавливает нижнюю границу на CPE 0.5.

Значение каждого аккумулятора хранится в отдельном регистре. x86-64 процессор имеет 16 регистров для целых чисел и 16 YMM регистров для чисел с плавающей точкой. Если мы будем использовать слишком много аккумуляторов, для них может не хватить регистров. Придётся хранить значения некоторых из них в памяти, что ухудшит производительность. Если увеличить количество аккумуляторов в нашей программе с 8 до 20, производительность падает с CPE 1.04 до CPE 1.35.

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

Другие техники оптимизации: реассоциация


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

for (long i = 0; i < limit; i+=3) {
        float x = a[i], y = a[i+1], z = a[i+2];
        acc = acc * x * y * z;
}

Этот цикл имеет производительность CPE 5.02. По правилам языка C, когда нет скобок, операции умножения выполняются слева направо. В данном случае, легко увидеть, что все операции умножения зависят от переменной acc. Процессор не может начать умножать в следующей итерации, пока не завершит все умножения в текущей. Расставим скобки по-другому:

acc = acc * ((x * y) * z);

Значение переменных x, y и z в одной итерации не зависят от их значений в любой другой. Поэтому, пока выполняется текущая итерация, процессор может заранее вычислять два последних умножения в следующих итерациях. Производительность улучшается до CPE 1.69.

Другие техники оптимизации: условная передача данных


Как уже было сказано, процессор выполняет предвыборку, то есть считывает инструкции наперед. Если ему встречается ветвление (команды ассемблера je, jg, jl и т. д. ), он пытается угадать по какой ветви пойдёт вычисление. Если он угадывает неправильно, то теряет несколько тактов. Это называется условная передача управления.

Существует команда ассемблера cmov. Выполняя эту команду, процессор проверяет какое-то условие. Если это условие верно, он копирует значение из одного регистра в другой. Это называется условная передача данных. В данном случае не создаётся ветвления и процессору не надо ничего угадывать и рисковать потерей тактов.

Идея заключается в том, чтобы уменьшить количество ветвлений в программе, сделав поток выполнения более прямым. Для этого некоторые передачи управления выгодно заменить на передачу данных. Обычно компилятор транслирует конструкции if-else, используя команды ассемблера je, jg, jl и т. д., но иногда может использовать команду cmov. Рассмотрим такую конструкцию if-else:

if (условие)
    v = выражение1;
else
    v = выражение2;

Если транслировать этот код, используя передачу управления, то при выполнении программы будет вычислено или одно выражение или другое, но есть вероятность, что процессор совершит ошибку в выборе ветвления и потеряет такты. Компилятор может избежать ветвления, если преобразует этот код следующим образом:

v1 = выражение1;
v2 = выражение2;

v = (условие) ? v1 : v2;

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

Иногда компилятор не выполняет эту оптимизацию, потому что считает, что это ухудшит производительность. Мы можем заставить его выполнить её если перепишем код в более функциональном стиле, как представлено в предыдущем примере. Рассмотрим реальную программу.

void minmax1(int a[], int b[], int n)
{
    for (int i = 0; i < n; i++) {
        if (a[i] > b[i]) {
            int t = a[i];
            a[i] = b[i];
            b[i] = t;
        }
    }
}

void minmax2(int a[], int b[], int n)
{
    for (int i = 0; i < n; i++) {
        int min = a[i] < b[i] ? a[i] : b[i];
        int max = a[i] < b[i] ? b[i] : a[i];
        a[i] = min;
        b[i] = max;
    }
}

Обе функции делают одно и то же. Они параллельно обходят пары чисел из двух массивов, устанавливая в массив a наименьшее из них, а в массив b наибольшее. Только вторая функция использует хитрую технику: она вычисляет минимальное число, вычисляет максимальное число и записывает каждое из чисел в своё место. Условия в вычислении переменных min и max настолько простые, что компилятор использует для них условную передачу данных. Разница в производительности наибольшая, если выполнить компиляцию с третьим уровнем оптимизации: minmax1CPE 15.6, minmax2CPE 1.18 (в 13.2 раз быстрее).

Заключение


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

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

Мы предложили базовую стратегию оптимизации кода:

  • Высокоуровневый дизайн. Выбирайте эффективные алгоритмы и структуры данных. Никакой компилятор не заменит плохие алгоритмы или структуры данных на хорошие.
  • Базовые принципы кодирования. Избегайте блокировщиков оптимизации, чтобы помочь компилятору генерировать эффективный код. Избавьтесь от ненужных вызовов функций. Если возможно, вынесите вычисления за пределы цикла. Избавьтесь от ненужных запросов к памяти. Введите временные переменные для хранения промежуточных результатов.
  • Низкоуровневая оптимизация. Применяйте раскрутку циклов, чтобы уменьшить накладные расходы на цикл. Задействуйте параллелизм на уровне инструкций, используя несколько аккумуляторов и реассоциацию. Пишите инструкции if-else в функциональном стиле, чтобы компилятор мог использовать условную передачу данных.
Поделиться публикацией

Комментарии 142

    0

    Спасибо за статью.


    x86-64 процессор имеет 16 регистров для целых чисел и 16 YMM регистров для чисел с плавающей точкой.

    Читал, что в суперскалярных процессорах (по крайней мере, начиная с Pentium) число физических регистров существенно превышает число архитектурных (физических несколько сотен, архитектурных 16). Почему ухудшение производительности у вас проявлялось при 20 аккумуляторах? Можете нащупать границу более точно? Возможно, производительность ограничивалась чем-то другим?

      +1
      Производительность ограничивается именно архитектурными регистрами. Физические регистры компилятор использовать не может, их может только сам процессор использовать для своих внутренних оптимизаций, потому когда счётчиков становится много компилятору ничего не остаётся кроме как сложить их на стек. А дальше — читайте раздел про указатели, но уже применительно к «оптимизирующему» процессору, а не оптимизирующему компилятору.
      0
      Прочел на одном дыхании, спасибо за статью. Подскажите, можно ли как-то узнать количество функциональных блоков того или иного назначения и прочие параметры процессора в рантайме?
        +1
        Читайте мануалы производителя процессора — там всё есть.
        Ну или нагуглите сайт за авторством Agner-а нашего Fog-а.
        0
        Последний пример впечатлил. Казалось, что в функции minmax1 операций меньше и она должна работать быстрее, чем в minmax2, где и операций больше и присваивания происходят на каждой итерации.
          0
          Как раз то, что присваивания происходят на каждой итерации и спасает: можно обойтись без проверок. А это — для процессора самое страшное.
            –1
            Насколько я знаю, minmax2 можно ещё ускорить заменив [ ] на указатели, поскольку выражение a[ i ] воспринимается компилятором как: *(a + i * sizeof(int)), если вместо a[ i ] использовать *( a + i ), то необходимость в умножении отпадает, значит должна возрасти производительность.

            void minmax2(int * a, int * b, int n)
            {
            for (int i = 0; i < n; i++) {
            int min = *(a + i) < *(b + i)? *(a + i): *(b + i);
            int max = *(a + i) < *(b + i)? *(b + i): *(a + i);
            *(a + i) = min;
            *(b + i) = max;
            }
            }
              +2

              a[i] и *(a+i) эквивалентны, и поэтому компилируются абсолютно одинаково.

            +8
            Эти оптимизации были актуальны году так в 90.
            Через двадцать лет компиляторы таки научились понимать основные паттерны, и правильно генерировать для них код.
            Конечно баловаться указателями не стоит и сейчас, это ничуть не поможет производительности. С другой стороны тенденции процессоростроения приводят к тому что циклы, которые 5 лет назад нельзя было векторизовать, сейчас векторизуются.
            Кстати про векторизацию в статье я не заметил — как же так?? (Заметил небольшой абзац… Очень странно что такой мелкий — векторизация это ключ к эффективности).

            Вообщем мой совет — перестаньте думать о том как написать А+Б. Думаете алгоритмами, О-сложностями. Ручной анролл цикла — самая плохая идея, потому что мне надоело их заанроливать обратно. Компилятор прекрасно делает это сам, причем учитывает количество регистров на целевой архитектуре автоматически, делает вершнинг, если ваша развертка не кратна длинне вектора.

            Так что — думайте алгоритмикой, не стесняйтесь пользоваться матбиблиотеками (где цикл вида A=B+C) уже и так вылизан. А такую оптимизацию — бросьте, не нужна она…
              +3
              IMHO, вы путаете пример и метод. Всегда найдётся алгоритм, которого нет в стандартных библиотеках. Или он есть, но неизвестно где. Или известно, но эту библиотеку нельзя использовать по причине несовпадения лицензий.
              Так или иначе, нужно как минимум иметь представление о базовых методах оптимизации.
                +4
                Или если вы автор матбиблиотеки. Почему-то проповедники подхода «оставьте оптимизацию профессионалам» забывают о самих профессионалах, которые должны делать оптимизацию. Им же тоже надо где-то учиться.
                0
                Эти оптимизации были актуальны году так в 90.
                Да ну? А что сейчас произошло? Почему сегодня, сейчас, мы получаем десятикратную оптимизацию от этих техник?

                Через двадцать лет компиляторы таки научились понимать основные паттерны, и правильно генерировать для них код.
                Тем не менее они остались связаны рамками стандартов C/C++. Пример minmax1 vs minmax2 — очень показателен.

                Кстати про векторизацию в статье я не заметил — как же так?? (Заметил небольшой абзац… Очень странно что такой мелкий — векторизация это ключ к эффективности).
                В очень ограниченном числе алгоритмов. Подавляющее большинство алгоритмов либо векторизуются плохо (и с этим ничего нельзя поделать), либо, наоборот — векторизуются очень хорошо (и тогда GPGPU — наше всё).

                А такую оптимизацию — бросьте, не нужна она…
                Разработчики TensorFlow тоже так думали. Потому сделали логику на Питоне и «молотилку» — на C++ (и даже, говорят, специализированные железки есть). В результате на больших серверах больше половины времени уходит на исполнение питоновского скрипта, который «никого тормозить не может».
                  +1
                  Ваша ссылка на TensorFlow лишний раз показывает что вы поверхностно вникаете в тему.
                  Да будет вам известно, для молотилки было сделано абсолютно ровно то, что я посоветовал ответом выше — «не стесняйтесь пользоваться матбиблиотеками». Для молотилки в TF используется Eigen.
                  https://www.google.ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0ahUKEwiryoftyorPAhXmJJoKHdkNDUMQFggeMAA&url=http%3A%2F%2Feigen.tuxfamily.org%2F&usg=AFQjCNGi0wxMLU4MgkIA4YRyJUH2dkiKCg&sig2=kMAXRZVw6H3HNc_Yw85JRg

                  Про TF я могу вам много чего рассказать. Главная к нему претензия что distributed версия там написана сыро.

                  >>В очень ограниченном числе алгоритмов. Подавляющее большинство алгоритмов либо векторизуются плохо (и с этим ничего нельзя поделать), либо, наоборот — векторизуются очень хорошо (и тогда GPGPU — наше всё).
                  Я бы сначала взглянул на вашу статистику, чтобы понять откуда взялось это странное высказывание.
                  Особенно в свете того что я выше написал «тенденции процессоростроения приводят к тому что циклы, которые 5 лет назад нельзя было векторизовать, сейчас векторизуются».
                    +2
                    Ага. Вот как раз сейчас разбираюсь, почему в Eigen процедура умножения RowMajor матрицы на 3d вектор работает в 18 раз медленнее, чем написанная самостоятельно, при компиляции в в VS2015.
                    0

                    Вообще, в статьях не описаны различные хинты для C++, позволяющие ему автоматически векторизовать код и т.д.


                    Например, есть модификатор для pointer, который говорит о том, что его область данных (на которую он указывает со всеми adds/subs) не пересекается с другими.


                    Что автоматом разрешает кучу оптимизаций.


                    И таких модификаторов в C++ сейчас много.

                      0
                      Формально в C++ такого модификатора нет. Это расширение языка, пусть и поддерживаемое многими компиляторами.
                    0
                    Эх, примкну к меньшинству — согласен с тем, что на одном размышлении о тривиальных операциях много не получишь в скорости. За исключением очень (очень!) специфичных задач с которыми 99.9% процентов программистов не сталкиваются, любая проблема производительности решается тремя основными подходами:
                    1. Алгоритм (нотация большого О, о чем говорит предыдущий оратор)
                    2. Локальность данных (вот отличная статья на эту тему)
                    3. Отсутствие блокировок и узких мест (многопотчность)
                      +1
                      Эх, примкну к меньшинству — согласен с тем, что на одном размышлении о тривиальных операциях много не получишь в скорости.
                      Я получал в нескольких случаях ускорение от 3 до 10 раз на вот таких «тривиальных операциях». Да, код становилось сложнее читать и править — но подобное ускорение может быть, в зависимости от задачи, очень полезным.

                      2. Локальность данных (вот отличная статья на эту тему)
                      Собственно почти вся описанная тут статья является небольшой частью этого подхода. В данном случае речь идёт о том, что обращение к регистрами — на порядок быстрее, чем даже к кешу L1, а вычисления — на порядок быстрее, чем принятие решений (ветвления) и нужно бы сделать так, чтобы компилятору ничто не мешало их использовать.

                      +1
                      Ручной анролл цикла — самая плохая идея, потому что мне надоело их заанроливать обратно

                      Мой скромный опыт говорит ровно об обратном — развертки цикла очень хорошая техника. Я лично смог ускорить одну из операций (конвертация одного colorspace в другой) в 5 раз (одна из последних версий GCC). И такие примеры мне встречаются постоянно. В данном случае я занимался оптимизацией нашего медиасервера.
                        –3
                        Ну давайте, скопируйте последний пример в http://gcc.godbolt.org/ и увидите что первый цикл ни один компайлер не смог осилить.
                        Второй (minmax2) был успешно векторизован, чем и обьясняется ускорение.

                        >> Думаете алгоритмами, О-сложностями.
                        Вот это как раз совет из 90х
                        Это конечно важно, но паттерны работы с памятью важнее.
                          +1
                          Три дня я гналась за Вами — да! — чтобы сказать Вам, как Вы мне безразличны!

                          Откопал год как пылящийся хабровский пароль только ради выражения своего «фи». У вас получился невероятно самодовольный категоричный комментарий напрочь игнорирующий контр-примеры из статьи. Что забавно, вы продолжили игнорировать их упоминание и в последующих обсуждениях. Можете уже ясно и без экивоков пояснить, как пафосная фраза про
                          Через двадцать лет компиляторы таки научились понимать основные паттерны, и правильно генерировать для них код

                          может существовать в мире с оптимизацией minmax1() в minmax2()?
                            0
                            Ускорил код в 123 раза ручными оптимизациями. Шёл 2017 год. Компилятор — не искуственный интеллект. Он видит код, но не Понимает его. Ему надо ручками всё показывать, всё самому делать. Тогда и код быстрый будет.
                            0
                            Очень приятная статья. Прочитал с удовольствием, хотя всё это я знаю и применяю. Буду кидать этой ссылкой в начинающих программистов.
                              +1
                              Статья замечательная, но может не стоит в начинающих-то ей кидаться — многие новички и так норовят все и вся оптимизировать, даже не проверив профайлером, нужна ли оптимизация вообще.
                                0
                                Я подразумевал, что буду использовать эту статью вместо того, чтобы самому придумывать правильные слова и показательные примеры. Понятно, что это всё в контексте нужности оптимизации как таковой будет подаваться.
                              +1
                              Насчет ветвлений — я лично столкнулся с проблемой производительности LFSR. Внутренний цикл LFSR Галуа проверяет равенство младшего бита нулю и в зависимости от этого ксорит или не ксорит содержимое регистра с константой. Когда мне удалось (путем написания программы на ассемблере) избавиться от условного перехода во внутреннем цикле — производительность возросла очень ощутимо. Во сколько раз — не измерял, но до оптимизации программа не справлялась с нагрузкой, а после оптимизации стала справляться. А все дело в том, что LFSR — это практически генератор случайных чисел, поэтому процессор, пытаясь предсказать переход на следующем проходе цикла, ошибается в среднем в 50% случаев. Это приводит к частому обнулению конвейера и большим задержкам в работе программы. Поэтому избавление от условного перехода и дает такой прирост производительности.
                                0
                                Кстати, избавление от условного перехода я делал не на основе cmovcc (хотя это было бы возможно), а на основе старого доброго sbc eax,eax. Это такой красивый трюк, и его можно реализовать на множестве процессоров. Познакомился я с ним на Z80 (SBC A,A). Даже там, без конвейера, он зачастую позволяет сильно оптимизировать программу за счет избавления от условных переходов.
                                  0
                                  Дык компилятор делает также — зачем вам ассемблер приспичил?
                                    +2
                                    Если бы мой компилятор (VS2013) такое тогда делал — то я бы ассемблером и не занимался. Компилятор не смог — а какие у меня были основания ожидать, что какой-то другой компилятор это сможет? Плюс время на установку другого компилятора, портирование программы под него, испытания? Вы считаете, что это быстрее, чем написать внутренний цикл на ассемблере?

                                    Если я знаю и умею, как написать на ассемблере быстрый код, и это быстрее, чем найти способ «подшаманить» C-код так, чтобы компилятор его хорошо скомпилировал — то почему не сделать на ассемблере? Если мы начинаем вникать в тонкости процессора с целью оптимизации программ — то логичный шаг писать на ассемблере, где все под контролем. Знание ассемблера в любом случае требуется. Но в первом случае требуется знание только ассемблера и процессора, а во втором — еще и знание тонкостей компилятора и/или библиотек. Что проще?
                                      +2
                                      только MSVC не умеет компилировать ассемблерные вставки для x64 и ARM.
                                        0
                                        Я забыл уточнить, что разрабатываемая программа была предназначена для испытаний некоего железа, и она должна была работать именно и только на отдельно взятом компьютере — том, который стоял у меня на столе. Надеюсь, вы не станете утверждать, что при разработке такой программы необходимо обеспечить ее портируемость? Или что мне надо было купить более быстрый комп?
                                        +1
                                        Вы считаете, что это быстрее, чем написать внутренний цикл на ассемблере?
                                        Я считаю что если вас волнует скорость работы вашей программы то первым делом нужно выкинуть никуда негодный интсрумент (MSVC) и взять годный (Intel C++ или Clang). Потом заниматься чем-то ещё.

                                        Если я знаю и умею, как написать на ассемблере быстрый код, и это быстрее, чем найти способ «подшаманить» C-код так, чтобы компилятор его хорошо скомпилировал — то почему не сделать на ассемблере?
                                        Потому что всю программу вы не сможете писать на ассемблере. И «подшаманивать» код не нужно — достаточно сделать так, чтобы его можно выло ускорить хитрыми манипуляциями не меняя семантики — дальнейшее приличные компиляторы сделают за вас. Ещё раз, для тех кто в танке: MSVC приличным компилятором не является и никогда не являлся (хотя потихоньку движется в этом направлении — но качество генерируемого кода для его разработчиков имеет явно не самый высокий приоритет).

                                        P.S. Есть случаи, когда даже clang, gcc и intel compiler не умеют генерировать хороший код (работа с битовыми массивами, например). В этом случае ассемблерные вставки вполне уместны.
                                          0
                                          первым делом нужно выкинуть никуда негодный интсрумент (MSVC) и взять годный (Intel C++ или Clang)

                                          В общем случае — может быть. Но я решал частную задачу. И я ее решил наиболее быстрым и дешевым из доступных способов. Intel C++ стоит немалых денег. Clang нужно было ставить, портировать программу под него и испытывать. На это нужно время. Значительно большее, чем занимает написание на ассемблере внутреннего цикла LFSR. А что если бы и Clang не смог ускорить программу необходимым образом? Откуда мне было знать, может он это или нет? Вот в данном конкретном случае люди подсказали, что он может. Интересно, в 2014 мог ли? А ведь есть и другие случаи оптимизации, когда и Clang/Intel C++ не поможет. И что тогда? Так что ваше решение даже как общее не всегда годится. Оно затратнее.
                                          Потому что всю программу вы не сможете писать на ассемблере.

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

                                          То, что вы описали, я и имел в виду под «подшаманить». Подумайте: чтобы написать C-код таким образом, чтобы компилятор смог его ускорить хитрыми манипуляциями, необходимо: 1) знать ассемблер и тонкости работы процессора; 2) знать, как данный конкретный компилятор компилирует те или иные конструкции языка в ассемблер, особенно те моменты, которые могут повлиять на возможность оптимизации; 3) написать программу, проверить с помощью дизассемблера, как она компилируется, и если не так, как хочется — то продолжать «шаманить»; 4) при необходимости сменить компилятор и вернуться к п. 2).

                                          Это затратнее и по времени на подготовку, и по времени собственно работы. Даже по деньгам затратно (если требуется покупать лицензию на дорогой компилятор). Напротив, для написания нужного фрагмента на ассемблере требуется осуществить только п. 1).

                                          Добавлю, что иногда оптимизация не помогает — код не удается ускорить в достаточной степени ни с помощью компилятора, ни с помощью ассемблера. В таких случаях приходится искать другие решения. Такие, как отказ от обработки данных в реальном времени, покупка вычислительных мощностей и т.д. И если действительно окажется, что оптимизация не помогает — то желательно это выяснить как можно раньше, чтобы избежать лишних затрат на нее времени и денег.
                                            0
                                            Есть случаи, когда даже clang, gcc и intel compiler не умеют генерировать хороший код (работа с битовыми массивами, например). В этом случае ассемблерные вставки вполне уместны.

                                            Лучше уж интринсики, ИМХО. Больше информации для аллокатора регистров у компилятора, больше типобезопасность, ну и всё такое.
                                              0
                                              Лучше уж интринсики, ИМХО.

                                              Интринизики — это хорошо, но они не всё покрывают. Скажем у процессора, начиная c лохматого 1985 года, есть операции для работы с битовыми массивами. И они реально дают ускорение. Но вот интринзиков — нету. В подобных случаях — выбора нет, только вставки на ассемблере.

                                              А так — да, конечно, интринзики — безопаснее. Хотя «внутри» компилятора разницы нет.

                                              Больше информации для аллокатора регистров у компилятора
                                              Столько же. Вот не больше, не меньше, а ровно столько же. По крайней мере если использовать gcc/clang. Вставки на ассемблере и интринзики используют один и тот же синтаксис вообще! Фактически интринзики — это ассемблерные вставки, которые разработчики компилятора в него включили при «изготовлении». Разница только в том, что на интринзики — больше «глаз» смотрят, ошибки менее вероятны. Но с точки зрения генерации кода — разницы никакой.

                                              Многие удивляются, откуда в GCC/Clang'е такой сложный и хитрый способ описания ассеблерных вставок — а ларчик просто открывался: этот синтаксис изначально не для ассемблерных вставок делался! Он используется при «изготовлении» компилятора для описания того, чего умеет CPU. Соответственно в RTL ассемблерные вставки, интринзики и даже «обычные» операции порождают более-менее одинаковые узлы…
                                        0
                                        а что за трюк? Если я не забыл, такая команда выставит флаг нуля и сбросит флаг переноса — независимо от того, что было в регистре А. И что дальше? Все равно же нужен переход.

                                        К тому же — в чем смысл? На Z80 каждая команда занимает свое фиксированное кол-во тактов, которое задокументировано. Там надо избавляться от тактов, а не от переходов.
                                          +1
                                          Трюк в том, что будет в регистре eax после выполнения этой команды. Поскольку число вычитается само из себя — то результат был бы всегда 0, но команда sbc учитывает значение флага переноса ©. Если C=1, то в регистре после вычитания окажутся все единицы — 0xFFFFFFFF. Если C=0, то будет 0. После этого можно выполнить команду AND с константой. Таким образом, в eax будет либо 0, либо эта константа. Потом с ней ксорим состояние LFSR. Ксор регистра с нулем не изменяет его значение. Вот и получается, что мы либо ксорим регистр с константой, либо не ксорим, что и требовалось. И все без переходов.

                                          Что же касается Z80, то там на переходы тоже требуется время (такты), хоть и фиксированное. Избавление от переходов = экономия тактов. Также облегчается выравнивание веток по количеству тактов, если это требуется для процедур реального времени, таких, как работа с магнитофоном или звуком.
                                            +1
                                            вот пример для Z80 решения задачи: загрузить в аккумулятор число 1 либо число 6 в зависимости от состояния флага C:
                                            SBC A,A
                                            AND 7
                                            XOR 1
                                            

                                            Выполняется всегда за 18 тактов. С условными переходами было бы что-то вроде:
                                            JP NC,XXX
                                            LD A,6
                                            JP YYY
                                            XXX: LD A,1
                                            YYY:
                                            

                                            Это выполняется за 17 либо за 27 тактов, в среднем 22 (если оба значения флага C при входе в программу равновероятны).
                                              +1
                                              спасибо, идея понятна. Как-то забыл что sbc учитывает флаг переноса.
                                          0
                                          Внутренний цикл LFSR Галуа проверяет равенство младшего бита нулю и в зависимости от этого ксорит или не ксорит содержимое регистра с константой.
                                          Вы имеете в виду что-то подобное, как я понял:
                                          constexpr int xor_const = 57;
                                          int foo(unsigned int a, unsigned int b) {
                                            return a ^ ((b & 1) ? 0 : 57);
                                          }
                                          

                                          Так вроде бы компилятор с этим отлично справляется:
                                          $ g++ -std=c++11  -O3 -S test.c -o- | c++filt
                                          	.file	"test.c"
                                          	.text
                                          	.p2align 4,,15
                                          	.globl	foo(unsigned int, unsigned int)
                                          	.type	foo(unsigned int, unsigned int), @function
                                          foo(unsigned int, unsigned int):
                                          .LFB0:
                                          	.cfi_startproc
                                          	andl	$1, %esi
                                          	cmpl	$1, %esi
                                          	sbbl	%eax, %eax
                                          	andl	$57, %eax
                                          	xorl	%edi, %eax
                                          	ret
                                          	.cfi_endproc
                                          .LFE0:
                                          	.size	foo(unsigned int, unsigned int), .-foo(unsigned int, unsigned int)
                                          	.ident	"GCC: (Ubuntu 4.8.4-2ubuntu1~14.04.3) 4.8.4"
                                          	.section	.note.GNU-stack,"",@progbits
                                          

                                          Зачем тут ассемблер? Избавление от условного перехода — штука хорошая, но в ассеблер-то сразу зачем ударяться?
                                            0
                                            Мой компилятор (VS 2013) на момент написания программы (2014г) такого не сумел. Может быть, нужно было написать C-код с какими-то плясками с бубном, чтобы он смог оптимизировать, но я такой вариант не нашел. Может быть, это мог уже тогда GCC или LLVM, но… Скажу честно, мне проще и быстрее написать на ассемблере, чем выяснять, какой компилятор умеет делать такую оптимизацию и как надо писать C-код, чтобы он это сделал.

                                            Я вообще не понимаю стремления «избавиться от ассемблера во что бы то ни стало». Может быть, для тех, кто с ассемблером знаком чисто теоретически, такой совет и полезен. Но не для меня. Я на нем писал большие и сложные программы много лет.
                                              0
                                              Может быть, для тех, кто с ассемблером знаком чисто теоретически, такой совет и полезен.
                                              Такой совет полезен для тех, кто работает в команде. Где, ужас, да, бывают люди, не знающие x86 ассемблера, а знающие ассемлер SPARC или там PowerPC. А C — у них у всех один.
                                                0
                                                Вы, случайно, не из тех людей, кто рекомендует писать программу «Hello World» в стиле "Enterprise"?

                                                Упомянутая программа писалась мной единолично и для личного же применения. Вы этого не учли.
                                          +1
                                          в функциях combine3 и combine4 переменная i объявляется 2 раза. статья норм.
                                            +1
                                            Хорошая статья и просто написано. Жаль не указана версия gcc, но с векторизацией что gcc что msvc пока только делают первые робкие шаги.
                                              0
                                              С интересом прочёл про реассоциацию и условное копирование, такие простые вещи я не знал. Но постоянное в статье: «оптимизируем цикл на несколько циклов» это просто жесть, программисты узнают слово такты, раньше чем начинают учить ассемблер и это статья от программиста!?
                                                +1
                                                «Поскольку не все наши лентопротяжные устройства были в порядке, я в срочном порядке был призван к порядку, чтобы сортировать данные разных порядков на несколько порядков быстрее.» Если не ошибаюсьэто Хигмана «Сравнительное изучение языков программирования», 1969 год
                                                  0
                                                  Как думают другие хабражители, стоит ли заменить «цикл» в статье на «такт»?
                                                    +1
                                                    Давно пора.
                                                  +3
                                                  Автор, спасибо за статью! Хотелось бы добавить небольшое уточнение:

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

                                                  Может. Стандарт С99 ввёл ключевое слово restrict, которое сообщает компилятору, что области памяти не могут пересекаться. Разумеется, ответственность за непересечение ложится на программиста, но компилятор может применять оптимизации «как в Фортране». В С++ это ключевое слово так и не попало, но разработчики компиляторов его часто реализуют в виде расширения, например __restrict__ в GCC.
                                                    +3
                                                    > Компиляторы могут применять только безопасные оптимизации. Это значит, что компилятор может изменять программу только так, чтобы это не изменило её поведение для всех входных данных.

                                                    Это несколько упрощенно.

                                                    1) Поведение может быть изменено для ситуации, не документированной в стандарте. Как пример — gcc 6.1 при -O2 выкидывает проверки this на NULL.
                                                    https://habrahabr.ru/company/abbyy/blog/308346/

                                                    2) Компилятор может выкинуть memset, используемый для очистки автоматической переменной от чувствительных данных (например, паролей). Ну и вообще плохо понимает, что кроме программы — есть ещё и окружение.
                                                    http://www.viva64.com/ru/d/0208/

                                                    3) gcc, начиная с -O2 использует strict-aliasing, то есть подразумевает, что в разных параметрах указатели указывают на разную память.
                                                    https://habrahabr.ru/post/114117/

                                                    4) В оптимизаторе могут быть ошибки. То есть автор оптимизации считает, что она безопасна, а на самом деле — не так. И в некоторых случаях это приводит к катастрофе. Классический пример — FORTRAN OE на OS 360, который выкидывал проверку на делителя на ноль. Точнее сначала делил, а потом уже проверял, не равен ли нуля делитель. Это у него так оптимизация общих подвыражений отработала.

                                                    5) -Ofast в gcc включает, например, такую небезопасные оптимизации, как -funsafe-math-optimizations и -fno-math-errno

                                                    Так что вариантов, как получить небезопасную оптимизацию — много. Мораль простая — отлаживаться сразу на нужном уровне оптимизации.
                                                      +2
                                                      Поведение может быть изменено для ситуации, не документированной в стандарте.
                                                      Не может.

                                                      Как пример — gcc 6.1 при -O2 выкидывает проверки this на NULL.
                                                      Эта ситуация документирована в стандарте. В правильно написанной программе она возникать не должна.

                                                      Компилятор может выкинуть memset, используемый для очистки автоматической переменной от чувствительных данных (например, паролей).
                                                      Эта ситуация также документирована, да.

                                                      gcc, начиная с -O2 использует strict-aliasing, то есть подразумевает, что в разных параметрах указатели указывают на разную память.
                                                      И это — тоже задокументеровано.

                                                      В оптимизаторе могут быть ошибки.
                                                      И не только в оптимизаторе. В любой программе на сотни тысяч строк могут встречаться ошибки, увы.

                                                      Мораль простая — отлаживаться сразу на нужном уровне оптимизации.
                                                      Да, причина тут другая: очень много вещей в разных библиотеках C++ рассчитаны на то, что компилятор будет оптимизировать программу. Оптимизируя программу под -O0 вы породите кучу ужаса…
                                                        –1
                                                        Опровержение простое — https://habrahabr.ru/post/136283/ — посмотрите на пример 2. Ну и на https://habrahabr.ru/post/216189/ на разделение между undefined, unspecified и implementation-defined. Для undefined — поведение может меняться между неоптимизированным и оптимизированным кодом.

                                                        Насчет кучи ужаса — очень спорно. Оптимизируя алгоритм — я иногда получаю выигрыш по скорости в тысячу раз. А оптимизация компилятора — дает процентов 5-10 общего времени выполнения программы. Если у вас медленный кусок исполняется миллион раз в цикле — оптимизация сильно поможет. А если исполняется один раз — вы этого не заметите.

                                                        Ну ещё одно. Ориентация на возможности оптимизатора — это привязка к конкретному компилятору. Если нужна переносимость — лучше не закладываться на наличие оптимизаций. А inline — это не оптимизация, это свойство языка такое. Его как раз есть смысл всегда включать.
                                                          0
                                                          Для undefined — поведение может меняться между неоптимизированным и оптимизированным кодом.
                                                          И любое из них будет корректным. Я уже писал статью про это: неопределённого поведения в программе быть не должно. Точка. Есть разные интсрументы, помогающие это реализовать, но если ваша программа содержит в себе неопределённое поведение, то вы ССЗБ.

                                                          А оптимизация компилятора — дает процентов 5-10 общего времени выполнения программы.
                                                          Вы это серьёзно? Вы вообще когда-нибудь что-нибудь бенчмаркали? -O2 от -O0 отличается в типичном случае раза в 2-3, а иногда разница может быть и десятикратной.

                                                          Ориентация на возможности оптимизатора — это привязка к конкретному компилятору. Если нужна переносимость — лучше не закладываться на наличие оптимизаций.
                                                          О как. А ничего что вся стандартная библиотека завязана на предположения о том, что оптимизирующий компилятор сделает с программой? Снизу доверху? Все эти iterator_traits и std::begin без приличного оптимизатора смысла не имеют.

                                                          А inline — это не оптимизация, это свойство языка такое.
                                                          О как. Ну ладно.

                                                          Его как раз есть смысл всегда включать.
                                                          А зачем? В соответствии со спецификациями от него одни беды: нужно убеждаться что разные модули включают одно и то же определение, что нет никаких конфликтов и т.д. и т.п. При этом на скорость работы программы это не влияет никак. Компилятор интерпретирующий inline как satic — является полностью соответствующим стандарту, а вы же сами сказали, что завязываться на свойства конкретного компилятора как бы нехорошо.
                                                            0
                                                            Прошу прощения за поздний ответ. Просто долго собирался померить.

                                                            > И любое из них будет корректным.
                                                            В это верится до первой лично пойманной ошибки в оптимизаторе. Ну, например, crash компилятора — явно не является корректным поведением. Правильная программа или нет — но компилятор вылетать не должен…

                                                            > если ваша программа содержит в себе неопределённое поведение, то вы ССЗБ.
                                                            Не факт. Это просто ограничение переносимости. Пример:

                                                            J.2 Undefined behavior
                                                            A program in a hosted environment does not define a function named main using one
                                                            of the specified forms (5.1.2.2.1).

                                                            Вы действительно думаете, что это запрет на написание ОС, драйверов, dll и библиотек, вызываемых из других языков? Нет, это лишь намек на то, что линкер может выкинуть все, не вызываемое из main. И ему надо специальным образом указать, что main отсутствует, и пролог вызывать не нужно (или нужно его явно вызвать нестандартными способами)

                                                            Так что когда вы пишите про то, что Си создан для написания переносимой ОС — не забывайте, что по стандарту Си написание ОС — это UB, то есть ССЗБ с вашей точки зрения.

                                                            А отношение авторов стандарта к UB хорошо показывает вот это место
                                                            J.5 Common extensions
                                                            J.5.1 Environment arguments
                                                            1 In a hosted environment, the main function receives a third argument, char *envp[],
                                                            that points to a null-terminated array of pointers to char, each of which points to a string
                                                            that provides information about the environment for this execution of the program

                                                            То есть третий аргумент в main — это UB. Но пользоваться можно.

                                                            > -O2 от -O0 отличается в типичном случае раза в 2-3, а иногда разница может быть и десятикратной.
                                                            Вы думаете оптимизация ускоряет передачу данных по ком-порту? Или работу с файлами? Даже если приложение работает с файлом данных и не ждет комп-порта — скорость определяется временем работы с диском. А уж на ARM920 при отсутствии FPU — и подавно. Ну вот вам результаты по самому затратному для процессора куску. На АРМ было лень, мерял на I386. Если интересно — перемеряю на ARM.

                                                            Счетная задача (кусок реальной), 10 тысяч циклов.
                                                            GCC 4.8.4 I386/ubuntu-IA64:
                                                            -O0 132.5 мкс на цикл
                                                            -Og 76.5 мкс на цикл
                                                            -Os 55.2 мкс на цикл
                                                            -O1 42.3 мкс на цикл
                                                            -O2 39.6 мкс на цикл
                                                            -O3 42.2 мкс на цикл
                                                            -Ofast 34.2 мкс на цикл

                                                            CLang 3.4-1 I386/ubuntu-IA64 FPU:
                                                            -O0 116.2 мкс на цикл
                                                            -Os 35.4 мкс на цикл
                                                            -O1 35.3 мкс на цикл
                                                            -O2 37.8 мкс на цикл
                                                            -O3 37.6 мкс на цикл
                                                            -Ofast 37.5 мкс на цикл

                                                            С++ Builder 5.0, FPU
                                                            без оптимизации — 122 мкс на цикл
                                                            с оптимизацией — 128 мкс на цикл
                                                            без оптимизации и с автоматическими регистровыми переменным — 120.5 мкс на цикл
                                                            с оптимизацией и с автоматическими регистровыми переменным — 52 мкс на цикл

                                                            Выводы:
                                                            1) Как и предполагалось, разница между -O1 и O2-O3 — порядка 7%.
                                                            2) -O2 и -O3 не обязательно ускоряют программу. Могут и тормозить.
                                                            3) -O1 нужен как-минимум из за inline и размещений локальных переменных в регистрах.
                                                            4) -O2 и -O3 в наших задачах применять не стоит. Ускорения почти нет, а опасность сбоя при оптимизации достаточно велика.
                                                            Если интересно, то можно исследовать подробнее, какие оптимизации что дают.

                                                            > А ничего что вся стандартная библиотека завязана на предположения о том, что оптимизирующий компилятор сделает с программой? Снизу доверху?
                                                            Да ну?! sin завязан? или read???

                                                            > Все эти iterator_traits и std::begin без приличного оптимизатора смысла не имеют.
                                                            А вот это — в нашей области ССЗБ. Использовать кучу есть смысл только, если виртуальная памяти больше физической. То есть имеется swap. А когда swap нету, зато памяти 480 килобайт — кучу можно использовать только одним спосбом — при старте выделить все нужно и дальше не трогать. Иначе это даже не ССЗБ — это МИНА. Из-за фрагментации кучи в любой момент может просто памяти не хватить.

                                                            Да и медленное это дело, куча. Если бы в выше протестированном примере вместо размещения массивов в стеке использовалось бы их размещение в куче — ну было бы минимум раза в 3 тормознее.

                                                            > Компилятор интерпретирующий inline как satic — является полностью соответствующим стандарту,
                                                            И что? Это не отменяет, что inline и register — свойства языка.

                                                            > а вы же сами сказали, что завязываться на свойства конкретного компилятора как бы нехорошо.
                                                            ОТНЮДЬ. я сказал, что не стоит завязываться на наличие оптимизаций. Потому что в любой момент может оказаться, что единственный компилятор — это gcc 2.95.4 из МСВС 3.0. Или что-то ещё хуже. Так что пишем примерно на С89 + пара фишек из С++ + нестандартные, но обычные вещи типа #pragma pack.

                                                            С другой стороны, следование стандарту не дает полной переносимости. Как вам машинка с 32битными байтами? Все ваши программы там пойдут? А машинка без кучи? А машинка, куда не влезает большая часть стандартной библиотеки? А машинка, где не все служебные подпрограммы gcc есть? То есть нету тех частей, что завязаны на ОС. Например — не работает инициализация статических переменных из подпрограмм.

                                                            Так что все оценивается комплексно. Если уж у вас Windows и GUI — так явно у вас машина с дополнительным кодом с litle endian. И все, что будет UB при big endian — тогда уж неважно.
                                                              0
                                                              > Все эти iterator_traits и std::begin без приличного оптимизатора смысла не имеют.
                                                              > кучу, кучу, кучи, куча, куче
                                                              При чем здесь куча? std::array, например, на стеке живет, но для него работают итераторы.
                                                                0
                                                                СПС, согласен. НО:
                                                                1) Непонятно, чем это лучше обычного массива
                                                                2) Это С++11, а у нас часть компиляторов понимает только С89 и С++ v.2 по Страустрапу
                                                                3) Думаю, что -O1 тоже хватит. Ибо главное — включить inline.
                                                                  0
                                                                  1) Непонятно, чем это лучше обычного массива
                                                                  — Унифицирован с остальными контейнерами
                                                                  — Есть свойство size()
                                                                  — На нем определены оператор присвоения, swap
                                                                    0
                                                                    Но это же не наследование, а только унификация… То есть для написания короткого кода — удобно, А библиотеку матобработки на него переписывать смысла нету.

                                                                    И вообще, пока жива МСВС — за рамки gcc 2.95.4 не выходим.

                                                                    В МСВС просто код или собственноручно написанный или пришедший вместе с МСВС. И ВСЕ. Никакого другого кода ставит нельзя, ибо нарушается защищенность.
                                                                      0
                                                                      >Но это же не наследование
                                                                      В STL и нет наследования. Там другие механизмы — концепты и черты (traits).
                                                                        0
                                                                        Потому и непонятно, зачем они нужны. Городить огород на темплейтах, ради совместимости с std::vector? Так вектор это куча. А куча — это уже нужна большая виртуальная память…
                                                                          0
                                                                          Вы не понимаете STL…
                                                                            0
                                                                            УГУ. я не понимаю, зачем в Си использовать STL. Более того, очень похоже, что это и комитет по стандартизации не понимает. В С++ есть несколько элементов, которые хочется использовать в Си. Но это далеко не STL.

                                                                            Если можете — то объясните.

                                                                            P.S. Если ещё точнее — я не понимаю, какие преимущества в конкретной задаче мне даст STL.
                                                                              0
                                                                              УГУ. я не понимаю, зачем в Си использовать STL

                                                                              Если вопрос «зачем STL именно в Си» — я вас обрадую: его там и нет. Ежели стоит вопрос «зачем STL если можно писать в Си-стиле»: используя STL, мы получаем более простой в написании и чтении, быстрый в написании, отладке и изменении, а также переносимый код с примерно таким же быстродействием, (высоковероятно) меньшим числом ошибок и всё за те же деньги.
                                                                                0
                                                                                Повторю вопрос «какие преимущества в конкретной задаче мне даст STL»? Именно в конкретной. С математической обработкой матриц небольшого, заранее известного размера.

                                                                                АНАЛОГИЯ. Преимущества классов начинаются с наследования и полиморфизма. И если у нас в программе 3 солитона (и более никаких объектов) — скорее всего такую программу лучше писать без классов.

                                                                                Прtимущества STL — это независимость от базового типа. Но базовый тип у нас всегда double.

                                                                                Недостатки STL (точнее std::vector и аналогичных вещей):
                                                                                1) До появления auto (C++11) код малочитаем.
                                                                                2) Если использовать С++ — получается резкое уменьшение числа платформ. Фактически на С++11 есть всего 3 компилятора: gcc, clang и VCC++. Вылетает полувоенное и военное применение — МСВС
                                                                                3) Разбухает размер кода (важно на FreeRTOS)
                                                                                4) Ухудшается скорость за счет худшего использования кэша (заметно, когда мы бегаем по столбцам матрицы)
                                                                                5) значительно ухудшается отладка алгоритма. Попробуйте сделать условный брейпоинт на A[1.1] > A[2,2]*100.
                                                                                6) При передаче в качестве dll значительные части алгоритма передабтся исходным кодом в .h.

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

                                                                                Это только слова. Для какой-то области они могут быть верны, для нашей — маловероятно. Перепишите этот метод на STL — посмотрим, что будет с читаемостью и переносимостью. язык- лучше С++ ver 2 (2ое издание Страустрапа)

                                                                                Обращение матриц методом Гаусса, переписано с Фортрана
                                                                                bool Gauss_T1(int  N, MATRIX&  m1)
                                                                                {
                                                                                   const double eps=1.0e-8;
                                                                                   const double minuseps=-eps;
                                                                                
                                                                                   bool Res = true;
                                                                                   for (int k = 0; k < N; k++) {
                                                                                      double mdiag = m1.A[k][k];
                                                                                      if ((mdiag < eps)&&(mdiag > minuseps)) {
                                                                                         for (int it = 0; it < N; it++)
                                                                                            m1.A[it][k] = m1.A[k][it] = 0.0;
                                                                                         Res = false;
                                                                                      } else {
                                                                                         double d = 1.0 / mdiag;
                                                                                         m1.A[k][k] = d;
                                                                                         double minusd = -d; // Чтобы избежать ошибки при оптимизации BC 3.1
                                                                                         int i;
                                                                                         for (i = 0; i < N; i++) {
                                                                                             if (i != k) {
                                                                                                m1.A[i][k] *=  minusd;
                                                                                                m1.A[k][i] *= d;
                                                                                             };
                                                                                         };
                                                                                         for (i = 0; i < N; i++) {
                                                                                            if (i != k) {
                                                                                               for (int j = 0; j < N; j++) {
                                                                                                  if (j != k)
                                                                                                     m1.A[i][j] += m1.A[i][k] * m1.A[k][j] / d;
                                                                                               } // end for j
                                                                                            } // end if i != k
                                                                                         } // end for i
                                                                                      } // end else
                                                                                   }; // end for k
                                                                                   return Res;
                                                                                }
                                                                                

                                                                                  0
                                                                                  >1) До появления auto (C++11) код малочитаем.
                                                                                  >2)… Вылетает полувоенное и военное применение — МСВС
                                                                                  Вместо того, чтобы доносить до нас то, что МСВС не может в C++11, лучше доносите до ВНИИИНС, или кого там, что C++11 — это хорошо.
                                                                                  >3) Разбухает размер кода
                                                                                  Только если в отладочной версии.
                                                                                  >4) Ухудшается скорость за счет худшего использования кэша
                                                                                  Поясните, с чего бы это хуже используется кэш?
                                                                                  >5) значительно ухудшается отладка алгоритма. Попробуйте сделать условный брейпоинт на A[1.1] > A[2,2]*100
                                                                                  Поясните. Не вижу проблем с этим у C++.
                                                                                    0
                                                                                    лучше доносите до ВНИИИНС, или кого там, что C++11 — это хорошо.

                                                                                    Точные цены не помню, но сертификация МСВС на конкретную железку — это примерно год и куча денег. Если железка уже сертифицирована — никто заново платить не будет.

                                                                                    >3) Разбухает размер кода
                                                                                    Только если в отладочной версии..

                                                                                    В любой. Разбухание идет за счет библиотечного кода. Судя по всему там iostream'овское ядро прилинковывается. Напишите программу без iostream но с STL и посмотрите по MAP, что подлинкуется, а что нет. Но на 100% не поручусь, просто разок эффект видел.

                                                                                    Поясните, с чего бы это хуже используется кэш?

                                                                                    Когда мы работаем с матрицей, она выделяется не одним куском, а построчно, причем при неудаче — в очень разных местах кучи. Проявляется, если мы ходим по столбцам. Ну как пример. 16К кэша.данных, две матрицы double 30*30. Если одним куском — они влезает в кэш. Если строки в 10 разных частях памяти — скорее всего не влезет.

                                                                                    >Попробуйте сделать условный брейпоинт на A[1.1] > A[2,2]*100
                                                                                    Поясните. Не вижу проблем с этим у C++.

                                                                                    Ну расскажите, как это сделать? И в каких отладчиках это возможно? Даже если отладчик позволяет вызывать функции, он не умеет на лету компилировать темплейты.
                                                                                      0
                                                                                      >Точные цены не помню, но сертификация МСВС на конкретную железку — это примерно год и куча денег. Если железка уже сертифицирована — никто заново платить не будет.
                                                                                      Я имел в виду вообще, а не «прямо сейчас». А то уже не в первый раз слышу, что в военных старинный компилятор.

                                                                                      >Когда мы работаем с матрицей, она выделяется не одним куском, а построчно, причем при неудаче — в очень разных местах кучи
                                                                                      А как вы это в Си делаете?

                                                                                      На счет условных брейкпоинтов — потыкался, действительно, работает через раз.
                                                                                        0
                                                                                        Я имел в виду вообще, а не «прямо сейчас».

                                                                                        А «вообще» там люди грамотные, цену проверки кода gcc на закладки понимают.

                                                                                        А как вы это в Си делаете?

                                                                                        double  A[_MATR_SIZE_][_MATR_SIZE_];
                                                                                        

                                                                                        Вся матрица — одним куском памяти.
                                                                                          0
                                                                                          Вся матрица — одним куском памяти.

                                                                                          std::array<double,_MATR_SIZE_,_MATR_SIZE_> A;
                                                                                          

                                                                                          Вся матрица — тем же самым одним куском памяти.
                                                                                            0
                                                                                            Согласен. Вот только std::array — это С++11. А в С++ ver 2 по Страустрауп — только std:vector.
                                                                                              0
                                                                                              Да один фиг, хоть вектор, хоть std::array, за минуту пишется обёртка, которая внутри делает std::vector<T> vec { Size * Size } или std::array<T, Size * Size>, а дальше уже делает всю нужную арифметику с размерностями.

                                                                                              А лучше взять что-то готовое, тот же dlib::matrix или eigen (но я с эйгеном мало работал).
                                                                                                0
                                                                                                Вспомнился бородатый анекдот
                                                                                                — Армяне, лучше, чем грузин.
                                                                                                — Чем лучше?
                                                                                                — Чем грузин!

                                                                                                Да, можно взять явно непригодное средство и приделать к нему костыли. Но инженеры (в отличие от школьников), при выборе решения оценивают его плюсы и минусы.

                                                                                                Примерно понятно, что выиграет eigen от добавки туда наших алгоритмов. А что выиграем мы? Затраты на переделку кода понятны. Но что окупит хотя бы 10% этих затрат?
                                                                                                  0
                                                                                                  Eigen — это не фреймворк, а библиотека. Чтобы воспользоваться некоторыми её абстракциями, не обязательно туда что-то добавлять.

                                                                                                  Но лучше навелосипедить самим, конечно.
                                                                                                    0
                                                                                                    Поскольку все равно переписывать, то лучше добавить в eigen отсутствующие методы. Ну то же быстрое обращение симметричных матриц. Скорее всего у нас оно быстрее, чем то, что в eigen.

                                                                                                    Когда делаешь что-то как хобби — можно делать как лучше. Когда работаешь — вопрос в том, как сделать эффективнее. И в ближайше переспективе и на 5-10 лет вперед. я не вижу преимуществ для нас от переделки под eigen.

                                                                                                    Почитайте вот. Люди навелосипедили — и обогнали всех. Потому что любой велосипед — будет хорош для конкретной задачи, под которую его делали. А библиотека — делается под многие задачи, она проиграет велосипеду в конкретных тестах, но выиграет в куче других областей.
                                                                                                      0
                                                                                                      Поскольку все равно переписывать, то лучше добавить в eigen отсутствующие методы.

                                                                                                      Не понял этого логического перехода, ну да ладно.

                                                                                                      Ну то же быстрое обращение симметричных матриц. Скорее всего у нас оно быстрее, чем то, что в eigen.

                                                                                                      Вы проверяли?

                                                                                                      Впрочем, вот псевдообратной Пенроуза-Мура там напрямую нет. Можно через SVD получить, конечно, но выглядит стрёмно. Поэтому я предпочитаю dlib для матриц (оно заодно Intel MKL умеет, не знаю, как оно с этим у Eigen).

                                                                                                      Когда делаешь что-то как хобби — можно делать как лучше. Когда работаешь — вопрос в том, как сделать эффективнее.

                                                                                                      Для меня эффективнее, во-первых, входит в критерии «лучше», во-вторых, включает время на разработку и отладку.

                                                                                                      Почитайте вот. Люди навелосипедили — и обогнали всех. Потому что любой велосипед — будет хорош для конкретной задачи, под которую его делали.

                                                                                                      К этому бенчмарку много вопросов.

                                                                                                      Во-первых, там велосипед точно той же библиотеки линейной алгебры, не под какую-то конкретную задачу, а вообще.
                                                                                                      Во-вторых, да, у меня тоже бывало, что clang генерировал более эффективный код, чем, скажем, Intel IPP. Но это было для совсем простых задач вроде «посчитать скалярное произведение двух векторов длиной 10000». Чтобы с матрицами что-то серьёзное компилятор считал быстрее MKL'я — не, никогда.
                                                                                                        0
                                                                                                        Не понял этого логического перехода, ну да ладно.

                                                                                                        для перехода на eigen 5 тысяч строк кода надо будет переписать. При этом разумно оставить деление на прикладной код и библиотеку. И отсутствующие в eigen библиотечные методы добавить в него же.

                                                                                                        Вы проверяли?

                                                                                                        и у нас и в eigen — N**3. Но у нас ускорение за счет того, что метод применяется к заведомо симметричной матрице. Значит на больших N — выиграем. Дело же не в качестве кодирования, дело в алгоритмах. Найти бы хотя бы N*N*log(N) — ускорение было бы приличное.

                                                                                                        Для меня эффективнее, во-первых, входит в критерии «лучше»

                                                                                                        Ноев Ковчег строили любители, профессионалы строили Титаник.
                                                                                                        Путь любителей — это делать шедевр. Увеличить качество на 5% за счет увеличения трудоемкости в 10 раз.
                                                                                                        А путь профессионалов — работать с высоким КПД. Результат должен быть приличным по качеству. Но не таким идеальным, как у любителей.

                                                                                                        у меня тоже бывало, что clang генерировал более эффективный код,

                                                                                                        Вот-вот, я об этом. Пара процентов быстродействия — это путь любителей. Меня интересует только О(N). Вот сменить N**3 на N*logN — это классно. А мелочи оптимизации — малоинтересны. Чуть иная плата — и все меняется. Потому что скорость памяти на разных платах разная, тактовая проца разная… А когда мы оптимизируем последние проценты — речь идет о балансе между процом, памятью и кэшем.

                                                                                                        Потому у них и ровные графики для их библиотеки — они оптимизировали ровно на свой комп.
                                                                                                          0
                                                                                                          При этом разумно оставить деление на прикладной код и библиотеку. И отсутствующие в eigen библиотечные методы добавить в него же.

                                                                                                          Совершенно необязательно.

                                                                                                          Я нужный мне код писал поверх dlib без добавления его в dlib, например. Никто не мешает одной библиотеке зависеть от другой библиотеки.

                                                                                                          Найти бы хотя бы N*N*log(N) — ускорение было бы приличное.

                                                                                                          Дело ещё и в константах. Если у вас матрица 30х30, судя по тому, что вы писали ранее чуть выше, то n3 может оказаться быстрее.

                                                                                                          Путь любителей — это делать шедевр. Увеличить качество на 5% за счет увеличения трудоемкости в 10 раз.
                                                                                                          А путь профессионалов — работать с высоким КПД. Результат должен быть приличным по качеству. Но не таким идеальным, как у любителей.

                                                                                                          Вы как-то сами себе противоречите.

                                                                                                          Высокий КПД — не переизобретать, отлаживать и доказывать корректность обратной (кстати, а что, если у вас некоторые собственные значения будут близки к нулю?), а взять eigen/dlib.

                                                                                                          Пара процентов быстродействия — это путь любителей. Меня интересует только О(N). Вот сменить N**3 на N*logN — это классно. А мелочи оптимизации — малоинтересны. Чуть иная плата — и все меняется. Потому что скорость памяти на разных платах разная, тактовая проца разная… А когда мы оптимизируем последние проценты — речь идет о балансе между процом, памятью и кэшем.

                                                                                                          Мне нравится, как это перекликается с вашими же словами про профессионалов, КПД и трудоёмкость.

                                                                                                          Впрочем, как это относится к моим словам, процитированным вами, я не очень понял.

                                                                                                          Потому у них и ровные графики для их библиотеки — они оптимизировали ровно на свой комп.

                                                                                                          Графики у них ровные потому, что они на свою библиотеку нормировали. У них там даже вверху графиков написано «Relative to Mir».

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

                                                                                                          Матрица перестала влезать в L1 — привет, ступенька. Матрица перестала влезать в L2 — привет, ещё одна. Матрица перестала влезать в L3 — ступень, ступенище! Матрица стала жрать столько, что TLB не хватает — ещё немного.
                                                                                              0
                                                                                              Увы, нет, std::array строго одномерный, посмотрите документацию.
                                                                                              Правда можно написать свою реализацию подобного массива с произвольной мерностью.
                                                                                          0
                                                                                          Когда мы работаем с матрицей, она выделяется не одним куском, а построчно, причем при неудаче — в очень разных местах кучи.

                                                                                          А кто мешает выделить одним куском на куче?
                                                                                        0
                                                                                        Прtимущества STL — это независимость от базового типа. Но базовый тип у нас всегда double.

                                                                                        А завтра я подумал, что double — многовато, и поменял тип на float. А в тестах оставил double, чтобы проверить погрешности или что-нибудь такое, поэтому просто поменять везде код не получится.

                                                                                        1) До появления auto (C++11) код малочитаем.

                                                                                        Это проблема языка, а не STL. Причём, надо сказать, весьма старого.

                                                                                        2) Если использовать С++ — получается резкое уменьшение числа платформ. Фактически на С++11 есть всего 3 компилятора: gcc, clang и VCC++. Вылетает полувоенное и военное применение — МСВС

                                                                                        Недостаток велосипеда как средства передвижения — я не могу на нём ездить под водой. Плохой, негодный велосипед, откажусь от него, даже когда мне надо сгонять в магазин за хлебом. А то вдруг я в магазин, а он под водой?

                                                                                        3) Разбухает размер кода (важно на FreeRTOS)

                                                                                        Не более, чем если бы вы писали весь тот же код руками с сохранением таких же гарантий со стороны типизации (ежу понятно, что можно вместо мономорфизации фигачить везде функции, которые жрут всё void*, но мне с таким подходом не по пути, извините).

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

                                                                                        Ну так смените row-major на column-major layout, проблем-то, тоже мне.

                                                                                        5) значительно ухудшается отладка алгоритма. Попробуйте сделать условный брейпоинт на A[1.1] > A[2,2]*100.

                                                                                        Я написал существенно более одного математического алгоритма, и ни разу мне не нужно было ставить подобные брейкпоинты. Более того, обычно отладка происходит карандашом на бумажке, когда всё, что нужно, из логов получено.

                                                                                        6) При передаче в качестве dll значительные части алгоритма передабтся исходным кодом в .h.

                                                                                        То у вас хипа нет и код разбухает, то аж shared object'ы есть.

                                                                                        Это только слова. Для какой-то области они могут быть верны, для нашей — маловероятно.

                                                                                        Вспоминая недавний наш с вами разговор, random forest — достаточно наша область? А там и std::sort, и std::unordered_map, и std::vector, который впоследствии был заменён на std::array (привет, унифицированный API!), и std::partition, и std::adjacent_difference…

                                                                                        А обращение матриц лучше не переизобретать, а взять dlib, eigen или, упаси б-же, GSL.
                                                                                          0
                                                                                          А завтра я подумал, что double — многовато,

                                                                                          я всегда говорю деткам, что я старый и глупый. Я не думаю — я знаю Расстояние до спутника GPS — 20 тысяч км. Точность измерения (псевдофаза) — 0.01 герц, то есть 2 миллиметра. 11 значащих цифр — это минимум. А во float — 7.5. Уж не говорю том, что по стандарту Си все вычисления идут в double (но это gcc умеет обходить). И вам придется переписывать sin и cos, причем ускорение вы получите только на машинах, с аппаратной float-математикой, но без аппаратного double.

                                                                                          Это проблема языка, а не STL. Причём, надо сказать, весьма старого.

                                                                                          Это проблема STL. В eigen её просто нет, потому что eigen использует модель индексов, а не указателей.

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

                                                                                          ЕЩЁ РАЗ. я старый дурак, я не думаю — я знаю. Нам по болотам надо. Деньги мы так зарабатываем. По болотам — в болотных сапогах, в театр — в смокинге. А одна одежка на все — это для тех, кто «думает». А мы — знаем, куда мы идем. И почему мы одеты именно так.

                                                                                          Отдыхать и играться — можно и с STL и с кучей других технологий. Но на болото в смокинге я не полезу.

                                                                                          МСВС 3.0 с gcc 2.95.4 — это наши будни. Точнее были буднями, сменили все-таки на 5.0. Ибо ядро 2.4 — это очень жестоко. Но в любой момент может появится железка с ровно этой системой. или ещё хуже — с MS-DOS.

                                                                                          Ну так смените row-major на column-major layout, проблем-то, тоже мне

                                                                                          вы умный вы думаете. а я глупый. я знаю, что с одной и той же матрицей — то по строкам, то по столбцам. А транспонировать — медленно. Да и вообще, зачем героически преодолевать трудности, когда можно их просто не делать?

                                                                                          Я написал существенно более одного математического алгоритма, и ни разу мне не нужно было ставить подобные брейкпоинты

                                                                                          Ноль проблем. Приходите к нам работать. Это сильно дешевле — взять вас к нам на работу, чем мне в 50 лет переучиваться. я же не математик, так что с удовольствием всю матобработку вам отдам.
                                                                                          Вот только когда вы неделю просидите за ловлей хитрого плавающего бага — приду я и за день найду. Тупыми методами грубой силы. Но за конечное известное время. Зарабатывал я этим. Ловлей багов в чужих программах, в которых я ни черта не понимаю.
                                                                                          Так что давай уж сойдемся на том, что мне брекпоинты нужны. Причем хитрые, на комбинацию данных.

                                                                                          То у вас хипа нет и код разбухает, то аж shared object'ы есть.
                                                                                          Речь о другом. У нас есть алгоритмы, которые мы даже под NDA не хотим распространять. А вы мне их предлагаете в темплейт вставить и в .h передавать.
                                                                                          Вспоминая недавний наш с вами разговор, random forest — достаточно наша область?

                                                                                          НЕ-А. Какая у вас железка? Можете фото кинуть? Вт если вы скажите, что у вас влезло на плату весом 110 грамм (без БП разумеется) — будет наша область. :-) Ну вот вам одна из наших железок. Старая, железо ещё не наше, а смежников, наш только софт. Тяжелая, килограмм 5, ибо рассчитана на то, что пара кубометров льда может влететь на капитанский мостик.
                                                                                          Наша программа - в ящике справа
                                                                                          image
                                                                                            0
                                                                                            Расстояние до спутника GPS — 20 тысяч км. Точность измерения (псевдофаза) — 0.01 герц, то есть 2 миллиметра. 11 значащих цифр — это минимум. А во float — 7.5.

                                                                                            Я не хочу вас расстраивать, но не во всех задачах обрабатываются данные со спутника GPS.

                                                                                            И вам придется переписывать sin и cos,

                                                                                            Не придётся, у меня тут плюсы.

                                                                                            причем ускорение вы получите только на машинах, с аппаратной float-математикой, но без аппаратного double.

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

                                                                                            Это проблема STL. В eigen её просто нет, потому что eigen использует модель индексов, а не указателей.

                                                                                            Это как бы немножко разные вещи, и сравнивать их некорректно.

                                                                                            А одна одежка на все — это для тех, кто «думает». А мы — знаем, куда мы идем. И почему мы одеты именно так.

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

                                                                                            Да ладно там, согласны. Вы ведь почему-то ещё считаете, что это единственно правильный путь.

                                                                                            вы умный вы думаете. а я глупый. я знаю, что с одной и той же матрицей — то по строкам, то по столбцам. А транспонировать — медленно.

                                                                                            Транспонировать медленно. Поэтому я у себя, где надо, например, заранее делаю две копии матрицы, одна с row-major layout, другая — с column-major. Это всё даже одной функцией делается, шаблонной, параметризованной нужным layout-типом. Но это так.

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

                                                                                            Вот только когда вы неделю просидите за ловлей хитрого плавающего бага — приду я и за день найду. Тупыми методами грубой силы. Но за конечное известное время. Зарабатывал я этим. Ловлей багов в чужих программах, в которых я ни черта не понимаю.

                                                                                            Ну хватит писюнами меряться уже, в самом деле.

                                                                                            Я тоже не раз и не два ловил баги. И даже в чужих программах. И даже когда там понимал, ну, очень мало. И тоже за день, а иногда и за 10 минут. Опыт позволяет-с.

                                                                                            Речь о другом. У нас есть алгоритмы, которые мы даже под NDA не хотим распространять. А вы мне их предлагаете в темплейт вставить и в .h передавать.

                                                                                            Зачем в .h? У меня весь мой рэндом форест в одном translation unit, откуда наружу торчит одна функция std::function<double (SampleType)> train(std::vector<SampleType> xs, std::vector<double> ys). А внутри там вся эта шаблонная вакханалия уже.

                                                                                            НЕ-А. Какая у вас железка? Можете фото кинуть?

                                                                                            Какой-то сервер то ли HP, то ли Dell, то ли кого-то ещё, кто там ещё серверы производит. 40 ядер (20, если гипертрединг выключить). И таких машин больше одной.

                                                                                            И 384 гига оперативки. Периодически упираюсь, и памяти хватает только на то, чтобы запустить 4-5 потоков выполнения. Ну, это к разговору о даблах и флоатах чуть выше.
                                                                                              0
                                                                                              Я не хочу вас расстраивать, но не во всех задачах обрабатываются данные со спутника GPS.
                                                                                              Зато я вас огорчу — вы забыли тему разговора. Напоминаю мои слова "Прtимущества STL — это независимость от базового типа. Но базовый тип у нас всегда double.". У нас — так. Примите это как данность. Ей богу, я знаю наши задачи.

                                                                                              И вам придется переписывать sin и cos,
                                                                                              Не придётся, у меня тут плюсы.

                                                                                              Прошу пояснений. Что, в С++ завелся float sin(float)? А если не переписывать — считать он будет в double.

                                                                                              Это как бы немножко разные вещи, и сравнивать их некорректно.
                                                                                              Есть задача — представление векторов и матриц неопределенного (заранее неизвестного) размера. STL её решает неудобно. Eigen — намного более удобней. Сравнивается решение конкретной, нужной задачи. А сравнивать решения ненужных задач — это к тем, у кого сервера со 128 ядрами. Пусть опыты на себе ставят (типа на кошках. :-) ).

                                                                                              Да ладно там, согласны. Вы ведь почему-то ещё считаете, что это единственно правильный путь

                                                                                              УГУ. Потому что мы не ДУМАЕМ, а ЗНАЕМ. Но это уже политика. На нашем рынке -5-6 западных фирм. больших, по тысяче человек. И мы, вообще-то единственная российская компания. Нас — семеро. Мы делаем в 2 раза хуже, но в 10-20 раз дешевле. И собираемся на несколько лет захватить некий сегмент мирового рынка (пока китайцы не скопируют).

                                                                                              Вы предлагаете отказываться от контрактов, закрыть фирму и клепать, как все на PHP. А нам это неинтересно. Зато интересна наша работа. Более того, мы многое делаем под чужими именами. Контракт выигрывает огромная госкорпорация, а делаем-то все равно мы.

                                                                                              МСВС — это семечки. Ягодки — это грядущая работа микропроцессором с российскими микросхемами объемом… не падайте… 128 килобайт. Чтобы набрать 32 мега под linux — надо 256 корпусов. Нравится? Потому придется без линкуса совсем. ТЗ там такое, забавное, пару страниц прочитать можно, остальные — вообще говоря, нельзя. :-)

                                                                                              Потому что вы согласны туда идти. Не были бы согласны, авось, стоимость поиска адекватных специалистов была бы повыше.

                                                                                              УГУ. Мы решаем задачи. Решаем методами, пригодными для конкретных задач. А вы — дальше верьте, что ваши методы идеальны и… отказывайтесь от решения. Чем больше народу будут думать в «one C++ STL way» — тем больше контрактов перепадет нам. И тем больше будет лично у меня зарплата.

                                                                                              Так что разубеждать вас мне не выгодно. Выгодней для личного кармана — поддерживать ваши заблуждения, что только так и можно работать.

                                                                                              Какой-то сервер то ли HP, то ли Dell,

                                                                                              То есть у вас совсем другие работы. Ну тогда вы правы. Ставьте на себе опыты, обкатывайте технологию. Лет через 10-20 на вас технология обкатается — вот тогда и мы её применим.
                                                                                                +1
                                                                                                >Что, в С++ завелся float sin(float)?
                                                                                                Не только float sin(float) http://en.cppreference.com/w/cpp/numeric/math/sin
                                                                                                но даже и complex<T> sin(const complex<T>&) http://en.cppreference.com/w/cpp/numeric/complex/sin
                                                                                                  0
                                                                                                  Вот только flt / 2.f все равно по стандарту Си будет иметь тип double. Или они и это заломали?
                                                                                                    +1
                                                                                                    Стандарт C11 (думаю, и более старые тоже) гласит:
                                                                                                    >6.3.1.8 Usual arithmetic conversions
                                                                                                    >…
                                                                                                    > Otherwise, if the corresponding real type of either operand is float, the other operand is converted, without change of type domain, to a type whose
                                                                                                    corresponding real type is float

                                                                                                    >The values of floating operands and of the results of floating expressions may be represented in greater range and precision than that required by the type; the types are not changed thereby

                                                                                                    Так что компилятору разрешено промоутить промежуточный результат, но в результате все равно будет float.
                                                                                                    C++ работает так же, ясное дело.

                                                                                                    Так что если ваш компилятор выражение flt / 2.f превращает в double в результате, то он работает не по стандарту.
                                                                                                  0
                                                                                                  Напоминаю мои слова «Прtимущества STL — это независимость от базового типа. Но базовый тип у нас всегда double.».

                                                                                                  Это ещё и туева хуча алгоритмов. Пяток контейнеров — самая выступающая, но далеко не единственно важная часть STL.

                                                                                                  У нас — так. Примите это как данность. Ей богу, я знаю наши задачи.

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

                                                                                                  Прошу пояснений. Что, в С++ завелся float sin(float)?

                                                                                                  Ага, товарищ профессионал, завёлся. Даже до C++11. Наверное, даже в gcc 2.95 есть.

                                                                                                  Вы предлагаете отказываться от контрактов, закрыть фирму и клепать, как все на PHP.

                                                                                                  Зачем сразу PHP? Я на PHP не клепаю, и ничего, своим собственным предложениям вполне следую.

                                                                                                  STL её решает неудобно. Eigen — намного более удобней.

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

                                                                                                  Ягодки — это грядущая работа микропроцессором с российскими микросхемами объемом… не падайте… 128 килобайт.

                                                                                                  Да что мне падать, я и с микросхемками поменьше работал. ATTiny23, там в окрестности килобайта флеша и 512 что ли байт оперативки. Давно это было, в 2008-м году где-то, и тогда я умудрялся писать на плюсах с компилятором gcc 4. На плюсах. С шаблонами. Без исключений и векторов, конечно, но оно там не было нужно. А вот, скажем, std::stable_sort уже был.

                                                                                                  А вы — дальше верьте, что ваши методы идеальны и… отказывайтесь от решения. Чем больше народу будут думать в «one C++ STL way» — тем больше контрактов перепадет нам.

                                                                                                  С чего вы взяли, что я отказываюсь от решения? Наоборот. STL — это не только вектор, лист и мапа, в конце концов.

                                                                                                  Выгодней для личного кармана — поддерживать ваши заблуждения, что только так и можно работать.

                                                                                                  Мы с вами всё равно не соревнуемся, так что не волнуйтесь. Я не пишу под МСВС, а микроконтроллер сегодня возьму только ради развлечения. Вы не используете C++ для регрессии и классификации на данных из миллиона объектов и ста тысяч признаков, да и компиляторы на хаскеле вряд ли пишете. Мы в разных экологических нишах.

                                                                                                  Ставьте на себе опыты, обкатывайте технологию.

                                                                                                  Наличие кучи вычислительной мощности не означает, что я могу себе позволить неэффективные алгоритмы.
                                                                                              0
                                                                                              А обращение матриц лучше не переизобретать, а взять dlib, eigen или, упаси б-же, GSL.

                                                                                              Так может вообще, не писать самим, а взять стандартный RTKLIB? Этим путем пошли конкуренты. Вот только на все просьбы показать или устроить сравнительные испытания идет отказ. Потому что оно работает. Иногда. Когда помех совсем нету. А в реальных условиях — ну в общем не пашет. Так что у конкурентов решение как бы есть, статьи писать можно. Но вживую его никто никогда не видел. А мы — готовы показать в любой момент. Хоть у нас, хоть в Москве…
                                                                                              Из протокола испытаний лет 20 назад
                                                                                              Прибор работает: потребляет заданную мощность. Задача: обеспечить выработку требуемых измерений.

                                                                                              Так что уж разрешите нам своим путем идти.Чтобы оно работалоЮ а не только мощность потребляло Можно?
                                                                                        0
                                                                                        Я уже пытался ему объяснить вкус устриц.

                                                                                        Если вкратце, то стоит просто посмотреть, в какой машинный код превращается программа с использованием STL при компиляции с разной степенью оптимизации. Тогда можно начинать спорить.

                                                                                        Смотреть после опытов
                                                                                        Как ни странно, но STL-шаблоны бывают эффективнее С-кода. И можно сделать кастомный аллокатор на стеке, если смущает куча.
                                                                                          0
                                                                                          Сложно объяснять вкус устриц тому, кто ими уже отравился.

                                                                                          По опытам модернизации кода с STL
                                                                                          1) Код плохо читается. За нагромождением итераторов не видно структуры двухмерных и трехмерных массивов. Возможно «пару лет так пролежите, а потом привыкните».
                                                                                          2) Код плохо отлаживается. Сложно посмотреть содержимое массивов, не говоря уже о том, чтобы поставить условный брекпоинт.
                                                                                          3) Целый ряд специфических ошибок, связанных с указателями на уже отданную в систему память, выходом за границы массивов и так далее. Чуть исходные данные вышли из ожидаемого программистом — и опаньки. Возможно — дело в квалификации, но там, где STL не использовался, код был более толерантен к данным у тех же программеров.
                                                                                          4) Размер исходного кода больше, скорость написания и модернизации — ниже.

                                                                                          ВЫВОД: Не вижу смысла использовать STL, пока не нужно основное его преимущество — независимость от типа данных. Ну или хотя бы дополнительное преимущество — контейнеры переменного размера.

                                                                                          И можно сделать кастомный аллокатор на стеке

                                                                                          Не на стеке, а в статике надо. Ну как пример — объект, инкапсулирующий матрицу и алгоритмы к ней. При этом, чтобы все данные были внутри объекта, то есть адресуемы просто по адресу объекта. И чтобы была возможность статически создать такой объект. Выйдет? :-))))
                                                                                            0
                                                                                            Вообще то статья не о качестве исходного кода, а об оптимизации.

                                                                                            STL наоборот, дает еще преимущества отсутствия необходимости работы с указателями и дает некоторую защиту от выхода за рейнж при отладке.

                                                                                            Зачем оптимизировать метод Гаусса компилятором или пытаться прикрутить к нему STL, если есть гораздо более эффективные _алгоритмы_? Неудачный пример, но не надо конечно везде совать шаблоны, согласен.

                                                                                            Статически или на стеке — для скорости работы не важно. Но невозможно для компилятора создать объект неизвестного заранее размера с фиксированным адресом. Да и не нужно.
                                                                                            Пример стекового аллокатора я привел, как оптимизация в плане исключения запросов выделения памяти ОС.

                                                                                              0
                                                                                              STL наоборот, дает еще преимущества отсутствия необходимости работы с указателями

                                                                                              А зачем работать с указателями, когда можно обойтись индексами? Тип фиксирован, максимальный размер известен, зачем городить указатели?

                                                                                              Зачем оптимизировать метод Гаусса компилятором или пытаться прикрутить к нему STL, если есть гораздо более эффективные _алгоритмы_?

                                                                                              Буду крайне благодарен более эффективному алгоритму обращения матрицы. Мы искали, но не нашли.

                                                                                              Но невозможно для компилятора создать объект неизвестного заранее размера с фиксированным адресом.

                                                                                              КОНЕЧНО. Но даже когда размер известен — это очень трудно сделать с помощью STL. Зато запросто — на обычных массивах.

                                                                                              Пример стекового аллокатора я привел, как оптимизация в плане исключения запросов выделения памяти ОС.

                                                                                              Стек плох тем, что ссылка на такой объект перестает быть валидной при завершении процедуры. Или передавать десяток объектов параметрами, или наворачивать умные указатели… Объект в стеке — это все-таки временный объект. А не постоянный.
                                                                                                0
                                                                                                А зачем работать с указателями, когда можно обойтись индексами? Тип фиксирован, максимальный размер известен, зачем городить указатели?
                                                                                                Ммм, ну я не знаю, откуда ты взял проблемы в своем п.3

                                                                                                Индексы в С это и есть указатели, точнее смещение к указателю.

                                                                                                Ладно, с алгоритмом обращения я похоже спутал какой то другой алгоритм, который в новостях недавно пробегал.

                                                                                                Прекращаю оффтопить.
                                                                                                  0
                                                                                                  Индексы в С это и есть указатели, точнее смещение к указателю.

                                                                                                  Не совсем так… Арифметика с указателями пришла в язык Си от языка B и PDP-8, которая была словной машиной. То есть p+3 в B — на самом деле означало добавит 3 к указателю. А в Си это означает добавить 3 * sizeof(элемента).

                                                                                                  Ммм, ну я не знаю, откуда ты взял проблемы в своем п.3

                                                                                                  Задача — хранить списки подобластей в массиве.

                                                                                                  Индекс 3 — валиден всегда. Итератор, указывающий на третий элемент — валиден лишь до переаллокации массива. Внесли в середину алгоритма метод, меняющий число элементов — все, итераторы поехали. Значит — итераторы отставляем, храним индексы.

                                                                                                  Но тогда получается, что нам нужно и крутить цикл по индексами — и двигать итератор. Но тогда легко словить рассинхронизацию.

                                                                                                  В итоге получается, что итераторы — это зло. В смысле для данной задачи зло.
                                                                                                    0
                                                                                                    Есть ещё проблемка с указателями. При 10 элементах в массиве индекс 11 — это индекс за границей массива, но это не UB (пока не пытаемся взять 11ый элемент). А вот итератор за end — это уже UB, он может быть как больше end, так и меньше.

                                                                                                    То есть мы не можем просто так прибавить к итератору 7 и проверить, не вышел ли он за end.

                                                                                                    Нужно это было для выделения в траектории (наборе точек) разных интересных участков.
                                                                                                      0
                                                                                                      То есть мы не можем просто так прибавить к итератору 7 и проверить, не вышел ли он за end.
                                                                                                      Вы и индексами не всегда можете это сделать. Или вы Borland C++ не застали и все эти Compact и Large модели памяти?

                                                                                                      А в конкретном компиляторе это может и не быть UB — сразу или при использовании какого-нибудь флажка. Точно также проверка «if x + 1 < x» бессмысленна и будет выкинута из вашей программы компилятором — но только если вы не используете опцию -fwrapv.

                                                                                                      А вообще все ваши потуги очень явственно показывают, что эту статью вам читать рано. Просто… рано. Вы просто ещё работаете с технологиями, которые устарели лет 10-15 назад. Вот в 2040м — может быть и поймёте почему люди, которым нужно работать с матрицами сегодня, сейчас, используют STL, шаблоны и Eigen, а не MSVC и индексы в массивах.

                                                                                                      А сегодня — с вами это обсуждать смысла нет. Проблемы работы с памятью на машинах со 128 ядрами вам неинтересны и не нужны. Но они не интересны и не нужны вам, потому что вы просто проигнорировали всё, что в XXI веке в IT-индустрии произошло — но почему вы считаете что это стандартная точка отсчёта для других читателей этой статьи???
                                                                                                        0
                                                                                                        Вы и индексами не всегда можете это сделать

                                                                                                        Могу. Причем ВСЕГДА. Всегда найдется тип, максимальное значение которого будет больше максимального реального размера массива. Связано это с тем, что даже в гарвардской архитектуре массив не может занимать всю память. — нужно будет место хотя бы для служебных переменных RTL.

                                                                                                        Видимо вы имели ввиду, что не всегда нужным типом будет int. Это верно. Иногда нужен long unsigned. Или long long, Но ввиду некоторых особенностей языка си — нужный тип найдется.

                                                                                                        Проблемы работы с памятью на машинах со 128 ядрами вам неинтересны и не нужны. Но они не интересны и не нужны вам, потому что вы просто проигнорировали всё, что в XXI веке в IT-индустрии

                                                                                                        "Молодёжь нынче пошла испорченная, старших не слушает" (с) Геродот.

                                                                                                        1. Когда вы подрастете, то сами поймете, что средство выбирается под задачу. А вовсе не потому, что оно модное, современное и так далее. Это только в молодости кажется, что модное средство — затычка для каждой бочки. С годами приходит понимание, для какой бочки оно годится, а для какой — нет. Ну и умение пропускать мимо ушей маркетинговые крики.
                                                                                                        2. Все новое — хорошо забытое старое. То, что вам так нравится — было новым и очень модным в 1966ом году. А к 1975ому — стало на свое, очень незначительное, место. Сейчас новый всплеск моды, через 10 лет он пройдет, а на его место вылезет другая, тоже очень старая технология. Например — введение в язык собственных конструкций (типа if then elif).
                                                                                                        3. ЭВМ разработки 1969ого года поддерживала работу 5-6 программистов в режиме разработки и отладки программ на 63 килобайтах памяти и 2Мгц тактовой. Сумеете сделать на «современных» технологиях систему в 100 хуже? 6.3Мб памяти и одно ядро на 200Мгц? А на старых — делается. Да, новые технологи удобнее в 10 раз. Зато и затратнее — в тысячи раз. Сейчас мы делаем прибор в 10 раз дешевле западных аналогов. Хотим — в 100 раз. Потому и технологиии нам лучшее старые, быстрые и не затратные. Но это не означает, что старые технологии лучше везде.
                                                                                                        4. Ещё один момент. Знаете какой GPS-приемник на тех аирбасах и боингах, на которых вы летаете? А приемник там — в 10 раз хуже, чем в китайском GPS-навигаторе. Нечувствительный, неточный, медленный… Приемник примерно 1985ого года на элементарной базе 1975ого года. У него одно преимущество — НАДЕЖНОСТЬ.. А для надежности железа -недостаточно расчетов. Нужно чтобы компоненты 5-10-20 лет отработали и была бы реальная статистика отказов. Нужно дать отработать плате в сборе. Аналогично и для софтверных технологий. Сначала — проводить эксперименты на кошках. На тех самых серверах со 128 ядрами. И лишь потом, выяснив на кошках все плюсы и минусы — использовать новую технологию в ответственных применениях. Вот потому и работает в банкоматах Windows XP, а не Windows 7/8/10. И у нас аналогично — брать модную сырую технологию вроде С++14 — это ССЗБ.


                                                                                                        почему вы считаете что это стандартная точка отсчёта для других читателей этой статьи???

                                                                                                        Потому что читателей — вряд ли дома есть «машина со 128 ядрами». Зато у них есть:
                                                                                                        • домофон
                                                                                                        • лифт
                                                                                                        • микроволновка
                                                                                                        • стиральная машина
                                                                                                        • телевизор
                                                                                                        • клавиатура
                                                                                                        • принтер
                                                                                                        • GSM-модем

                                                                                                        И во всех них — embedded. То есть принципы написания — примерно те же. Так что ваши «сервера со 128 ядрами» — всего лишь «испытания на кошках» для той техники, что нас окружает постоянно.

                                                                                                        За наводку на eigen спасибо. Надо будет математику перекинуть одну идею, подсмотренную там. Но это не единственная библиотека, а темплейты — не единственный метод реализации. GSL, например, написан на чистом Си без всяких темплейтов.
                                                                                                        0
                                                                                                        При 10 элементах в массиве индекс 11 — это индекс за границей массива, но это не UB (пока не пытаемся взять 11ый элемент).

                                                                                                        Вообще-то UB: «If both the pointer operand and the result [of P + N] point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined.»
                                                                                                          0
                                                                                                          СПАСИБО. Так юность навеяло. Эх, где мои 15 лет и одноклассницы, путавшие индекс с индексацией.
                                                                                                          Объяснение на уровне одноклассниц
                                                                                                          #define VECT_SIZE 10
                                                                                                          double v[VECT_SIZE] = {0};
                                                                                                          int i=11;                    // это не UB
                                                                                                          if (i < VECT_SIZE)  / / и это не UB, ибо индекс, а не итератор
                                                                                                             v[i] = 42;
                                                                                                          else {
                                                                                                          //  v[i] = 15;             // вот тут было бы UB
                                                                                                             printf("ЛОПАТА, сэр!\n");
                                                                                                          }
                                                                                                          

                                                                                                            0
                                                                                                            Стоп, а откуда у вас тогда вообще итератор взялся?
                                                                                                              0
                                                                                                              Итератор не у нас, итератор в STL. Дизайн у него такой.
                                                                                                                0
                                                                                                                Я не умею задавать понятные вопросы, очевидно.

                                                                                                                Откуда вы его такой сильно за end'ом получили?
                                                                                                                  0
                                                                                                                  А какая разница? Получили из-за ошибки в коде. Движемся по массиву точек траектории. Подозреваем что-то интересное (поворот) — запускаем внутренний цикл на проверку — поворот или просто шум такой. Ну и где-то пропустили сравнение. Бед тут две:
                                                                                                                  1. Итератор запросто в коде не проверить. И брекпоинт сложно поставить.
                                                                                                                  2. Если компилятор сумеет понять, что итератор всегда вылезает за end — это UB. А UB компилятор может просто выкинуть из кода.

                                                                                                                  То есть использование STL в этом случае привело к плохо отлаживаемому коду.

                                                                                                                  На самом деле основная ошибка была в том, что взяли на работу программиста, верящего в STL и всякие новомодные технологии. Ну он и навалял. То есть со сферической лошадью в вакууме его код работает идеально. А с реальными данными хреново. Потому что в реальных данных бывает что угодно.

                                                                                                                  ПРИМЕР. Надо определить момент начала движения. Теоретически, нашли СКО на первых точках, вышли за 3 СКО — значит едем. Практически бывает:
                                                                                                                  • движение может начаться с первой точки
                                                                                                                  • может выброс в 5 СКО, не означающий движения
                                                                                                                  • движение может начинаться с медленного дрейфа


                                                                                                                  Товарищ в общем-то полным идиотом не был и ассерты поставил. И если данные нормальные и ассерты не срабатывали — все работало. Но нам-то надо, чтобы работало на любых РЕАЛЬНЫХ данных! Пришлось ассерты убирать. И тут полез вагон плавающих ошибок.

                                                                                                                  Самый эффективный метод — это в точке ошибки глянуть на данные и поставить точку останова по этим данным пораньше. И в динамике посмотреть, как работает алгоритм и как его надо переписать.

                                                                                                                  Но с STL это не проходит. Так что или вычитывать 5 тысяч строк кода — или, как вы, по логам. Но с брекпоинтами ошибка находится за 15-20 минут. А по логам — медленней раз в 10.

                                                                                                                  Ну скажем так: я пока не видел мест, где использование одного std::vector привело к более понятному и более качественному коду. Они, несомненно, существуют, но — не в нашей области. Скорее всего что для получения выгоды от STL надо задействовать пяток разных контейнеров.
                                                                                                                    0
                                                                                                                    Тут были некоторые соображения на тему отлова ошибок в коде, но я вспомнил некоторые предыдущие дискуссии с вами о практиках написания кода и подумал знал подумал, что мы тут с вами не договоримся.

                                                                                                                    В любом случае, с тем, что есть вещи, которые удобнее написать на индексах, никто не спорит. Даже я сам периодически пишу вещи на индексах.

                                                                                                                    Скорее всего что для получения выгоды от STL надо задействовать пяток разных контейнеров.

                                                                                                                    На всякий случай повторю мысль, что STL — далеко не только контейнеры.
                                                                      +2
                                                                      Надеялся почитать в такой же лёгкой манере про «SSE или AVX» — не написали. Жаль. Буду ждать продолжения про векторизацию вычислений.
                                                                        –1
                                                                        Все программы должны быть корректными, но некоторые программы должны быть быстрыми.

                                                                        Почему собственно некоторые? Если бы все были быстрыми — может наступило бы счастье?
                                                                          0
                                                                          Но нужно немного подождать =)
                                                                            +2

                                                                            быстрые программы медленно пишутся, и, соответственно, дорого стоят

                                                                              +1
                                                                              Встречный вопрос, нужно ли программе быть настолько быстрой, если через такт она ждёт ответа от периферии? Требуется ли быть максимально быстрой программе, которая запускается один раз в день, глубокой ночью, и формирует суточные отчёты о проделанной работе (30 минут или 40 она проработает тут разницы нет).
                                                                                0
                                                                                Электричества больше сожрет, например. Тоже денежка
                                                                                  0
                                                                                  а почему она ждет ответа от периферии?
                                                                                  может потому что драйвер периферии корректный, но медленный ;)?
                                                                                    +2
                                                                                    А может потому что периферия — это механические детали, сервоприводы и т.п., которые требуют время на выполнение своих действий?
                                                                                      0
                                                                                      Потому что физические процессы таковы. что скорость не нужна. Можно измерять температуру больного каждую миллисекунду, но чаще раза в минуту это в принципе никому не нужно.
                                                                                        0
                                                                                        Я бы например не отказался в онлайне видеть свою температуру. И в пределах минуты разве не может быть скачков температуры, а вдруг это проявление симптомов какой-то болезни, а мы это пропустим.
                                                                                          0
                                                                                          Теплоемкость тела слишком велика. И цепи обратной связи медленные.За минуту можно разогреть локально ладошку, но не весь организм. Чуть подробнее http://biofile.ru/chel/1975.html Скачок — это минут за 15. Но пусть медики уточнят.
                                                                                      0
                                                                                      Ну тут дело не в том, что надо каждый код вылизывать подобным образом отдельно, а в том что можно (и может быть даже нужно) использовать паттерны эффективного программирования вообще.

                                                                                      То есть вы не оптимизируете алгоритмы в своей программе для отчетов один раз в день глубокой ночью, а просто изначально пишете эту программу с использованием пресловутых паттернов. Ну и вообще, везде их используете)
                                                                                        0
                                                                                        А я разве против этого возражал?
                                                                                      0
                                                                                      Потому что скорость многих программ определяется скоростью прокладки между экраном и клавиатурой. Или скоростью прихода данных. И вместо быстроты используется критерий требовательности к ресурсам процессора и памяти. И, если ресурсов хватает, намного важнее требование надежности работы. Или требование не задирать цену разработки.

                                                                                      Мы можем сделать быстро, качественно, дешево — выбирайте два из трех. Как правило — лучше дешево и качественно. Выполнение программы в 10 раз быстрее — это часто экономия 9 миллисекунд раз в минуту.
                                                                                      0
                                                                                      Спасибо огромное за статью — некоторые вещи делал не задумываясь, а теперь понял что к чему (учителя не объясняли — а говорили:«Так нужно делать и все»). Добавил в свою мини библиотеку полезных вещей. Очень жду следующую часть.
                                                                                        0
                                                                                        >Компилятору тяжело определить, имеет вызов функции побочные эффекты или нет.
                                                                                        Ой чёйто? Ему это довольно просто определить. Но в некоторых редких случаях, когда хотя бы часть f() линкуется динамически, ему это сделать вообще невозможно*.
                                                                                          0
                                                                                          Я верю профессорам Carnegie Mellon, которые написали книгу, которая вдохновила эту статью. Они в своей книге написали, что компилятору часто трудно это сделать (имеется вообще, а не в отношении моего примера).
                                                                                            0
                                                                                            Можно ссылку или хотя бы название?
                                                                                              0
                                                                                              В начале статьи книга упоминается. Computer Systems: A Programmer's Perspective. Пятая глава про оптимизацию.
                                                                                                +1
                                                                                                Извините, читал вступление по диагонали :)

                                                                                                В книге, во всех трех изданиях написано:
                                                                                                >Most compilers do not try to determine whether a function is free of side effects and hence is a candidate for optimizations such as those attempted in func2. Instead, the compiler assumes the worst case and leaves all function calls intact.
                                                                                                Что переводится как «Большинство компиляторов НЕ ПЫТАЮТСЯ определить, имеет ли функция побочные эффекты...». Так что утверждение «тяжело определить» не имеет под собой оснований. Эта цитата кочует из издания к изданию с 2001 года, но разработчики компиляторов не даром свой хлеб едят и за 15 лет таки наверняка этот анализ добавили. Более того, в третьем издании таки сказано, что GCC встраивает f() и поэтому имеет все возможности для оптимизации (хотя вышеприведенный абзац все равно там остался).
                                                                                                  0
                                                                                                  оптимизация вызовов функций возможна либо внутри translation unit, либо на этапе линковки (LTO). Второе поддерживается gcc начиная с 4.6 (2011-й год)
                                                                                                    0
                                                                                                    Ну в MSVC LTCG появился еще в 2001 году.
                                                                                            0

                                                                                            Вообще есть модификатор функции, прямо говорящий — функция не имеет побочных эффектов. Как называется — не помню, давно не пишу на C++.

                                                                                              0
                                                                                              В стандарте нет ничего такого. Но многие компиляторы поддерживают атрибуты const/pure. MSVC, однако, не поддерживает.
                                                                                            +1
                                                                                            >Считывание инструкций наперёд называется предвыборкой. Если во время предвыборки, процессор встречает ветвление (к примеру, конструкция if-else), он пытается угадать, какая ветвь будет взята и считывает инструкции оттуда.
                                                                                            Предвыборка — это считывание [в нашем случае] инструкций в кэш кода. Во время нее никакого анализа на ветвления не производится. А то, что вы назвали «предвыборкой» на самом деле просто «конвейерное исполнение».
                                                                                            А попытка исполнения предсказанной ветви называется спекулятивным исполнением.
                                                                                              +1
                                                                                              >cmove
                                                                                              >тернарный оператор
                                                                                              Да что же у вас за конпелятор такой тупой?! У меня на простом примере обе версии транслировались в ИДЕНТИЧНЫЙ код. Для разных уровней оптимизации он был разный, либо с cmove, либо без, но всегда ОДИНАКОВЫЙ. Вот, смотрите: https://godbolt.org/g/n9kaSN
                                                                                              Более того, переписав кода как вы сказали, вы, скорее всего, заставите компилятор вычислять оба подвыражения ВСЕГДА, хотя это компилятор должен решать, когда ему выгодней вычислить одну ветку, но с условным переходом, а когда обе, но с cmove.
                                                                                                0
                                                                                                gcc (Ubuntu 4.8.4-2ubuntu1~14.04.3) 4.8.4
                                                                                                Коммпилятор не всегда решает рравильно. Компилятор может решить не использовать cmov, хотя при использовании программа работала бы чуть быстрее.
                                                                                                  0
                                                                                                  Я ссылку привел на онлайн компилятор. Сейчас попробовал выставить там x86-64 gcc 4.8.4, но на нем результат такой же.
                                                                                                  >чуть быстрее
                                                                                                  Скорее всего только на вашем процессоре. А если ошибка существенная, то это просто недоработка/баг в компиляторе.
                                                                                                  Это только Интеловский компилятор может точно* посчитать, что сколько на каком их процессоре будет выполняться. Остальные компиляторы могут только прикидывать. Так же как и вы.
                                                                                                    0
                                                                                                    Просто автор один из тех, кто занимается оптимизацией DEBUG-сборки:
                                                                                                    Все программы в этой статье мы будем компилировать при помощи GCC с параметром -Og (базовый уровень оптимизации).
                                                                                                      0
                                                                                                      Цель статьи и примеров — продемонстрировать техники оптимизации. Какие из них будут работать на вашей машине с вашим процесором и компилятором смотреть вам.
                                                                                                0
                                                                                                Спасибо за статью! На днях разбирал функцию преобразования картинки с камеры (YUYV -> YV12) и думал почему нельзя было выполнить всё в один проход for, а разбивать на 4 идентичных участка внутри одного цикла. Теперь всё встало на свои места.
                                                                                                  0
                                                                                                  Интересно что на моем AMD 8350 функция combine4 с четырьмя аккумуляторами работает значительно медленнее чем та которая все перемножает в один цикл. На интеле же все соответствует ожидаемому результату.
                                                                                                    0
                                                                                                    а что там в дизассемблинге?
                                                                                                      0
                                                                                                      потому что float, попробуйте что-нибудь целочисленное, результат будет веселее.
                                                                                                        0
                                                                                                        Если дуднет/джава, то это значит, что после расписывания цикла компилятор не выкинул проверку на OutOfRange, у Гольдшейтна опять же это было :)
                                                                                                        0
                                                                                                        Кстати к слову про SSE у гольдштейна есть замечательный пример переписывания `String.Contains(...)` на SIMD (причем в подсчете учитывается еще и время на интероп между дотнетом и С):
                                                                                                        image
                                                                                                          0

                                                                                                          Только это уже не SSE, а AVX.

                                                                                                        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                                                                        Самое читаемое