Какие простые методы вы используете для повышения производительности?

21

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

for(int i = 0; i < collection.length(); i++ ){
   // stuff here
}

Но я обычно делаю это, когда foreachне применимо:

for(int i = 0, j = collection.length(); i < j; i++ ){
   // stuff here
}

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

Cristian
источник
34
+1 только за то, что у тебя есть девушка, которая скажет тебе, когда твой код неясен.
Кристо
76
Вы просто публикуете это, чтобы сообщить нам, что у вас есть девушка.
Джош К
11
@Christian: не забывайте, что есть оптимизация компилятора, которая может сделать это для вас, так что вы можете повлиять только на читабельность и не повлиять на производительность вообще; преждевременная оптимизация - корень всего зла ... Старайтесь избегать более одного объявления или присвоения в одной строке, не заставляйте людей читать его дважды ... Вы должны использовать обычный способ (ваш первый пример) или поставить второе объявление вне цикла for (хотя это также снижает читабельность, так как вам нужно будет прочитать обратно, чтобы увидеть, что означает j).
Тамара Вийсман
5
@ TomWij: Правильная (и полная) цитата: «Мы должны забыть о малой эффективности, скажем, в 97% случаев: преждевременная оптимизация - корень всего зла. Однако мы не должны упускать наши возможности в эти критические 3%». "
Роберт Харви
3
@ tomwij: Если вы тратите три процента, то по определению вы должны делать это в критичном по времени коде, а не тратить свое время на другие 97%.
Роберт Харви

Ответы:

28

вставить лекцию о преждевременном обсуждении "корня зла"

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

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

Знай своего биг-о

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

for (i = 0; i < strlen(str); i++) {
    ...
}

Это займет ужасное количество времени, если строка действительно длинная, потому что длина пересчитывается на каждой итерации цикла. Обратите внимание, что GCC фактически оптимизирует этот случай, потому что strlen()помечен как чистая функция.

При сортировке миллиона 32-битных целых чисел пузырьковая сортировка была бы неправильным способом . В общем, сортировка может быть выполнена за O (n * log n) (или лучше, в случае радикальной сортировки), поэтому, если вы не знаете, что ваши данные будут небольшими, ищите алгоритм, который по крайней мере O (n * войти n).

Аналогично, при работе с базами данных следует помнить об индексах. Если у вас SELECT * FROM people WHERE age = 20и у вас нет индекса по людям (возрасту), для этого потребуется последовательное сканирование O (n), а не намного более быстрое сканирование индекса O (log n).

Целочисленная арифметическая иерархия

При программировании на C имейте в виду, что некоторые арифметические операции стоят дороже, чем другие. Для целых чисел иерархия выглядит примерно так (сначала дешевле):

  • + - ~ & | ^
  • << >>
  • *
  • /

Конечно, компилятор обычно Оптимизировать вещи , как n / 2к n >> 1автоматически , если вы ориентируетесь на основной компьютер, но если вы ориентируетесь встроенное устройство, вы можете не получить такую роскошь.

Также % 2и & 1имеют разную семантику. Деление и модуль обычно округляются до нуля, но его реализация определена. Хорошо >>и &всегда округляет к отрицательной бесконечности, что (на мой взгляд) имеет гораздо больше смысла. Например, на моем компьютере:

printf("%d\n", -1 % 2); // -1 (maybe)
printf("%d\n", -1 & 1); // 1

Следовательно, используйте то, что имеет смысл. Не думайте, что вы хороший мальчик, % 2когда используете, когда изначально собирались писать & 1.

Дорогие операции с плавающей точкой

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

int parseInt(const char *str)
{
    const char *p;
    int         digits;
    int         number;
    int         position;

    // Count the number of digits
    for (p = str; isdigit(*p); p++)
        {}
    digits = p - str;

    // Sum the digits, multiplying them by their respective power of 10.
    number = 0;
    position = digits - 1;
    for (p = str; isdigit(*p); p++, position--)
        number += (*p - '0') * pow(10, position);

    return number;
}

Мало того, что это использование pow()(и преобразования int<->, doubleнеобходимые для его использования) довольно дорого, но оно создает возможность для потери точности (кстати, код выше не имеет проблем с точностью). Вот почему я морщусь, когда вижу, что этот тип функций используется в нематематическом контексте.

Также обратите внимание, что приведенный ниже «умный» алгоритм, который умножается на 10 на каждой итерации, на самом деле является более кратким, чем приведенный выше код:

int parseInt(const char *str)
{
    const char *p;
    int         number;

    number = 0;
    for (p = str; isdigit(*p); p++) {
        number *= 10;
        number += *p - '0';
    }

    return number;
}
Джои Адамс
источник
Очень подробный ответ.
паддислакер
1
Обратите внимание, что обсуждение преждевременной оптимизации не относится к мусорному коду. Вы всегда должны использовать реализацию, работающую в первую очередь.
Обратите внимание, что GCC фактически оптимизирует этот случай, потому что strlen () помечен как чистая функция. Я думаю, вы имеете в виду, что это константная функция, а не чистая.
Энди Лестер
@ Энди Лестер: На самом деле, я имел в виду чистый. В документации GCC говорится, что const немного строже, чем чистый, поскольку функция const не может читать глобальную память. strlen()проверяет строку, на которую указывает аргумент указателя, то есть она не может быть константой Кроме того, strlen()действительно отмечен как чистый в glibcstring.h
Джои Адамс
Вы правы, моя ошибка, и я должен был перепроверить. Я работал над проектом Parrot, аннотируя функции как pureили, constи даже задокументировал их в заголовочном файле из-за тонкой разницы между ними. docs.parrot.org/parrot/1.3.0/html/docs/dev/c_functions.pod.html
Энди Лестер
13

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

Я поклонник философии Кента Бека :

«Заставь это работать, сделай это правильно, сделай это быстро».

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

Например, для проверки скорости с помощью кода .NET я использую атрибут Timeout от NUnit, чтобы записать утверждения, что вызов определенного метода будет выполнен в течение определенного периода времени.

Используя что-то вроде атрибута timeout NUnit с примером кода, который вы дали (и большое количество итераций для цикла), вы могли фактически доказать, действительно ли ваше «улучшение» кода действительно помогло с выполнением этого цикла.

Один отказ от ответственности: хотя это эффективно на «микро» уровне, это, конечно, не единственный способ тестирования производительности и не учитывает проблемы, которые могут возникнуть на «макро» уровне - но это хорошее начало.

Paddyslacker
источник
2
Несмотря на то, что я большой сторонник профилирования, я также считаю, что разумно учитывать советы, которые Кристиан ищет. Я всегда выберу более быстрый из двух одинаково читаемых методов. Быть вынужденным к пост-зрелой оптимизации - это не весело.
AShelly
Нет необходимости в модульных тестах, но всегда стоит потратить эти 20 минут, чтобы проверить, верен ли какой-то миф о производительности, особенно потому, что ответ часто зависит от компилятора и состояния флагов -O и -g (или Debug / Отпустите в случае VS).
МБк
+1 Этот ответ дополняет мой связанный комментарий к самому вопросу.
Тамара Вийсман
1
@AShelly: если мы говорим о простых переформулировках синтаксиса цикла, изменить его после факта очень легко. Кроме того, то, что вы считаете одинаково читабельным, может быть не так для других программистов. Лучше всего использовать «стандартный» синтаксис, насколько это возможно, и изменять его только тогда, когда это необходимо.
Джори Себрехтс
@ Конечно, если вы можете придумать два одинаково читаемых метода и выбрать менее эффективный, который вы просто не выполняете свою работу? Будет ли кто-нибудь на самом деле это сделать?
Гленатрон
11

Имейте в виду, что ваш компилятор вполне может включить:

for(int i = 0; i < collection.length(); i++ ){
   // stuff here
}

в:

int j = collection.length();
for(int i = 0; i < j; i++ ){
   // stuff here
}

или что-то подобное, если collectionэто не изменилось в цикле.

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

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

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

ChrisF
источник
1
Почему бы просто не сделать это явно?
3
В некоторых языках, которые ограничивают проверку, вы ЗАМЕДЛИТЕ свой код, если вы сделаете это явно. С помощью цикла для collection.length компилятор перемещает его для вас и пропускает проверку границ. С помощью цикла с некоторой константой из другого места в вашем приложении вы будете проверять границы на каждой итерации. Вот почему важно измерять - интуиция о производительности почти никогда не бывает правильной.
Кейт Грегори
1
Вот почему я сказал: «Это стоит узнать».
ChrisF
Как может компилятор C # знать, что collection.length () не изменяет collection, как это делает stack.pop ()? Я думаю, что было бы лучше проверить IL, чем предполагать, что компилятор оптимизирует это. В C ++ вы можете пометить метод как const («не изменяет объект»), поэтому компилятор может безопасно выполнить эту оптимизацию.
JBRWilkinson
1
@JBRW Оптимизаторы, которые делают это, также знают о методах коллекций, которые можно назвать «давайте будем называть это константой, хотя и не это». В конце концов, вы можете только проверить границы, можете ли вы заметить, что что-то является коллекцией, и знать, как получить ее длину.
Кейт Грегори
9

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

tactoth
источник
1
Подари ей книгу о программировании;)
Джори Себрехтс
1
+1, так как большинство наших подруг, скорее всего, больше интересуются Lady Gaga, чем ясностью кода.
Гаплоид
Не могли бы вы объяснить, почему это не рекомендуется?
Макнейл
@ macneil хорошо ... этот трюк делает коды не такими уж общими и совершенно не работает, эта часть оптимизации должна выполняться компилятором.
Такт
@macneil, если вы работаете на языке более высокого уровня, думайте на том же уровне.
Такт
3

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

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

В качестве конкретного примера, для нашего текущего процессора ветки очищают конвейер, останавливая процессор на 8 циклов. Компилятор принимает этот код:

 bool isReady = (value > TriggerLevel);

и превращает его в эквивалент сборки

isReady = 0
if (value > TriggerLevel)
{
  isReady = 1;
}

Это займет либо 3 цикла, либо 10, если он перепрыгнет isReady=1;. Но в процессоре есть maxинструкция с одним циклом , поэтому гораздо лучше написать код для генерации этой последовательности, которая гарантированно всегда занимает 3 цикла:

diff = value-TriggerLevel;
diff = max(diff, 0);
isReady = min(1,diff);

Очевидно, что цель здесь менее ясна, чем оригинал. Итак, мы создали макрос, который мы используем всякий раз, когда мы хотим логическое сравнение Greater-Than:

#define BOOL_GT(a,b) min(max((a)-(b),0),1)

//isReady = value > TriggerLevel;
isReady = BOOL_GT(value, TriggerLevel);

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

AShelly
источник
3

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

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

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

Guffa
источник
3

У меня очень простая техника.

  1. Я заставляю свой код работать.
  2. Я проверяю это на скорость.
  3. Если это быстро, я вернусь к шагу 1 для некоторых других функций. Если это медленно, я профилирую это, чтобы найти узкое место.
  4. Я исправляю узкое место. Вернитесь к шагу 1.

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

Джейсон Бейкер
источник
2

Воспользуйтесь преимуществами короткого замыкания:

if(someVar || SomeMethod())

занимает столько же времени, чтобы кодировать, и так же читабельно, как:

if(someMethod() || someVar)

все же это собирается оценить быстрее со временем.

realworldcoder
источник
1

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

Kristo
источник
6
Э ... Как насчет производительности, которую видят ваши клиенты? Вы достаточно богаты, чтобы покупать новые компьютеры для них?
Роберт Харви
2
И мы почти достигли стены производительности; Многоядерные вычисления - единственный выход, но ожидание не заставит ваши программы использовать их.
барбекю
+1 Этот ответ дополняет мой связанный комментарий к самому вопросу.
Тамара Вийсман
3
Нет времени программирования не дороже, чем аппаратное обеспечение, когда у вас тысячи или миллионы пользователей. Время программиста НЕ более важно, чем время пользователя, проясните это как можно скорее.
HLGEM
1
Привыкайте к хорошим привычкам, тогда программисту не потребуется время, потому что это то, что вы делаете все время.
Доминик Макдоннелл
1

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

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

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

Тем не менее, именно к вашему значению я нахожу, что много раз использование логической противоположности подходу по умолчанию иногда помогает:

for(int i = 0, j = collection.length(); i < j; i++ ){
// stuff here
}

может стать

for(int i = collection.length(); i > 0; i-=1 ){
// stuff here
}

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

в c # например:

        string[] collection = {"a","b"};

        string result = "";

        for (int i = 0, j = collection.Count() - 1; i < j; i++)
        {
            result += collection[i] + "~";
        }

также может быть написано как:

        for (int i = collection.Count() - 1; i > 0; i -= 1)
        {
            result = collection[i] + "~" + result;
        }

(и да, вы должны сделать это с помощью соединения или строителя строк, но я пытаюсь привести простой пример)

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

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

Билл
источник
это решение, но компилятор, скорее всего, выдаст предупреждения, так как для большинства распространенных классов length () возвращает тип без знака
stijn
Но при обращении индекса сама итерация может стать более сложной.
Тамара Вийсман
@stijn Я думал о c #, когда писал его, но, возможно, это предложение также попадает в категорию для конкретного языка по этой причине - см. правку ... @ Конечно, я не думаю, что есть много, если есть предложения такого рода которые не рискуют этим. Если ваш // материал был какой-то манипуляцией со стеком, возможно, даже невозможно правильно изменить логику, но во многих случаях это и не слишком запутанно, если делать это осторожно в большинстве из этих случаев IMHO.
Билл
ты прав; в C ++ я бы все же предпочел «нормальный» цикл, но с вызовом length (), взятым из итерации (как в const size_t len ​​= collection.length (); for (size_t i = 0; i <len; ++ i) {}) по двум причинам: я считаю «нормальный» цикл прямого счета более читабельным / понятным (но это, вероятно, только потому, что он более распространен), и он выводит из цикла вызов инварианта цикла length ().
Стейн
1
  1. Профиль. У нас вообще есть проблемы? Где?
  2. В 90% случаев, когда это как-то связано с IO, примените кеширование (и, возможно, получите больше памяти)
  3. Если это связано с процессором, примените кеширование
  4. Если производительность по-прежнему остается проблемой, мы оставили простую технику - посчитаем.
Maglob
источник
1

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

работа
источник
1

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

Простой пример C (до):

void some_hotspot_called_in_big_loops(int n, ...)
{
    // 'n' is, 99% of the time, <= 64.
    int* values = calloc(n, sizeof(int));

    // do stuff with values
    ...
    free(values);
}

И после:

void some_hotspot_called_in_big_loops(int n, ...)
{
    // 'n' is, 99% of the time, <= 64.
    int values_mem[64] = {0}
    int* values = (n <= 64) ? values_mem: calloc(n, sizeof(int));

    // do stuff with values
    ...
    if (values != values_mem)
        free(values);
}

Я обобщил это примерно так, так как такие виды горячих точек часто возникают при профилировании:

void some_hotspot_called_in_big_loops(int n, ...)
{
    // 'n' is, 99% of the time, <= 64.
    MemFast values_mem;
    int* values = mf_calloc(&values_mem, n, sizeof(int));

    // do stuff with values
    ...

    mf_free(&values_mem);
}

Вышеупомянутый стек используется, когда выделяемые данные достаточно малы в этих 99,9% случаях, и использует кучу в противном случае.

В C ++ я обобщил это с помощью небольшой последовательности, соответствующей стандарту (похожей на SmallVectorреализацию), которая вращается вокруг той же концепции.

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


источник
0

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

Просто быстрый пример повышения производительности для SQL Server: используйте соответствующие индексы, избегайте курсоров - используйте логику на основе множеств, используйте предложения sargable where, не складывайте представления поверх представлений, не возвращайте больше данных, чем нужно, или больше столбцы, чем вам нужно, не используйте коррелированные подзапросы.

HLGEM
источник
0

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

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

Дэвид Торнли
источник
0

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

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

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

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

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

То, как вы пишете циклы, не имеет к этому никакого отношения.

Майк Данлавей
источник