Кто Вы любимые низкоуровневые приемы оптимизации кода? [закрытый]

gcc -O2

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

Свободное использование __ ограничивает для устранения остановов хранилища хита загрузки.

В дополнение к комментарию Joshua о генерации кода (большая победа), и другие хорошие предложения...

Я не уверен, назвали ли Вы это "низким уровнем", но (и это - downvote-приманка), 1) больше избегают использования уровней абстракции, чем абсолютно необходимый, и 2) избегают событийно-ориентированного программирования стиля уведомления, если это возможно.

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

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

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

Свертывание циклов.

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

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

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

Если Вы собираетесь микрооптимизировать, у Вас должна быть разумная идея двух вещей: архитектура, которую Вы на самом деле используете (который весьма отличается от систем, я рос с, по крайней мере, в целях микрооптимизации), и что компилятор сделает для Вас.

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

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

• Переработка указателя кадра внезапно
• Соглашение о вызовах Паскаля
• Перепишите последний вызов стекового фрейма optimizarion (хотя он иногда смешивает с вышеупомянутым),
• Используя vfork() вместо fork() прежде exec()
• И один я все еще ищу, оправдание использовать: управляемая данными генерация кода во времени выполнения

В SQL, если только необходимо знать, существуют ли какие-либо данные или нет, не беспокойтесь COUNT(*):

SELECT 1 FROM table WHERE some_primary_key = some_value

Если Ваш WHERE пункт является вероятным возвратом несколько строк, добавьте a LIMIT 1 также.

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

Тот от Ассемблера:

xor ax, ax

вместо:

mov ax, 0

Классическая оптимизация для размера программы и производительность.

Эффективные Программы Записи Jon Bentley являются большим источником низких - и высокоуровневых методов - если можно найти копию.

Устранение ответвлений (if/elses) при помощи булевой математики:

if(x == 0)
    x = 5;

// becomes:

x += (x == 0) * 5;
// if '5' was a base 2 number, let's say 4:
x += (x == 0) << 2;

// divide by 2 if flag is set
sum >>= (blendMode == BLEND);

Это ДЕЙСТВИТЕЛЬНО ускоряет вещи особенно, когда те, которые IFS находится в цикле или где-нибудь который называют много.

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

Например.

for (i = 0;  i < n;  ++i)
    *p++ = ...; // some complicated expression

по сравнению с.

for (i = 0;  i < n;  ++i)
    p[i] = ...; // some complicated expression

Считание в обратном порядке цикла. Более дешево выдержать сравнение с 0, чем N:

for (i = N; --i >= 0; ) ...

Смещение и маскирование полномочиями два являются более дешевыми, чем подразделение и остаток, / и %

#define WORD_LOG 5
#define SIZE (1 << WORD_LOG)
#define MASK (SIZE - 1)

uint32_t bits[K]

void set_bit(unsigned i)
{
    bits[i >> WORD_LOG] |= (1 << (i & MASK))
}

Править

(i >> WORD_LOG) == (i / SIZE) and
(i & MASK) == (i % SIZE)

потому что РАЗМЕР равняется 32 или 2^5.

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

Я был поражен ускорением, которое я получил путем замены для чисел добавления цикла вместе в структурах:

const unsigned long SIZE = 100000000;

typedef struct {
    int a;
    int b;
    int result;
} addition;

addition *sum;

void start() {
    unsigned int byte_count = SIZE * sizeof(addition);

    sum = malloc(byte_count);
    unsigned int i = 0;

    if (i < SIZE) {
        do {
            sum[i].a = i;
            sum[i].b = i;
            i++;
        } while (i < SIZE);
    }    
}

void test_func() {
    unsigned int i = 0;

    if (i < SIZE) { // this is about 30% faster than the more obvious for loop, even with O3
        do {
            addition *s1 = &sum[i];
            s1->result = s1->b + s1->a;
            i++;
        } while ( i<SIZE );
    }
}

void finish() {
    free(sum);
}

Почему не делает gcc, оптимизируют для циклов в это? Или есть ли что-то, что я пропустил? Некоторый эффект кэша?

Не делайте развертывания цикла. Не делайте устройства Вареного пудинга. Сделайте свои циклы как можно меньше, что-либо еще запрещает x86 производительность и gcc производительность оптимизатора.

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

И специально для x86 попытайтесь сохранить количество переменных используемым в любой момент вниз. Трудно сказать то, что компиляторы сделают с такой вещью, но обычно имеющий меньше итеративных переменных/индексов массива цикла закончится с лучше asm вывод.

Конечно, это для настольных центральных процессоров; медленный ЦП с доступом быстродействующей памяти может предварительно вычислить намного больше, но в эти дни, который мог бы быть встроенной системой с небольшой общей памятью так или иначе …

предварительное вычисление значений.

Например, вместо sin(a) или because(a), если для Вашего приложения не обязательно нужны углы, чтобы быть очень точным, возможно, Вы представляете углы в 1/256 круга и создаете массивы плавающего синуса [] и косинус [] предварительное вычисление греха и из-за тех углов.

И при необходимости в векторе под некоторым углом данной длины часто Вы могли бы предварительно вычислить все те синусы и косинусы, уже умноженные на ту длину.

Или, выражаясь в более общем плане, торговая память для скорости.

Или, еще в более общем плане, "Все программирование является упражнением в кэшировании" - Terje Mathisen

Некоторые вещи менее очевидны. Например, пересекая двумерную матрицу, Вы могли бы сделать что-то как

    for (x=0;x<maxx;x++)
       for (y=0;y<maxy;y++)
          do_something(a[x,y]);

Вы могли бы найти, что кэшу процессора нравится он лучше, если Вы делаете:

   for (y=0;y<maxy;y++)
       for (x=0;x<maxx;x++)
           do_something(a[x,y]);

или наоборот.

Несколько лет назад с not-so-smart compilier, я крайне экономично расходовал горючее от встраивания функции, обхода указателей вместо того, чтобы индексировать массивы и выполнить итерации вниз для обнуления вместо до максимума.

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

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

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

• Наличие кэша LRU запросов базы данных (или любой другой основанный на IPC запрос).
• Запоминание последнего неудавшегося запроса базы данных и возврат отказа, если повторно требуется в течение определенного периода времени.
• Запоминание местоположения в большой структуре данных, чтобы гарантировать, что, если следующий запрос для того же узла, поиск является бесплатным.
• Кэширование вычисления заканчивается для предотвращения дублирующейся работы. В дополнение к более сложным сценариям это часто находится в if или for операторы.

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

++i может быть быстрее, чем i++, потому что это старается не создавать временный файл.

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

Но я приехал для симпатии синтаксиса... он читает как "инкремент i", который является разумным порядком.

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

Выбирая питание два для фильтров, кольцевых буферов, и т.д.

Так очень, очень удобный.

- Adam

Один из самых полезных в научном коде должен заменить pow(x,4) с x*x*x*x. Голова является почти всегда более дорогой, чем умножение. Это сопровождается

  for(int i = 0; i < N; i++)
  {
    z += x/y;
  }

кому:

  double denom = 1/y;
  for(int i = 0; i < N; i++) 
  {
    z += x*denom;
  }

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

Да ведь взломы битового жонглирования, конечно!

Оптимизация местности кэша - например, при умножении двух матриц, которые не вписываются в кэш.