Потенциально длинный цикл и объявление переменных внутри

Question

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

Мой код похож (не фактический код с момента его назначения)):

while(!file.eof){
   string line;
   int sizeY, sizeX;

   //get first strand
   getline(db, line)

   //second strand
   getline(db, line)

   double ** ary = new double[sizeY];
   //loop to initialize array

   for(i to sizeY)
   {
      for(i to sizex)
      {
            pair<string,string> p,d;
            p.first = "A";
            p.second = "T";
            d.first = "G";
            d.second = "C";
            //do some comparisons
      }
   }
}

Приведенный выше код займет около 40 минут для файла с ~ 2400 строками.Если я переместу пару p, d и присвоения за пределы вложенного цикла for и запусту точно такой же файл, это завершится примерно через ~ 1 минуту.

Я читал в других темах, что производительность практически одинакова.Я также скомпилировал его с -O2.

Почему код выше намного медленнее?

Answer 1

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

1. Выделение парного объекта в стеке
2. Выделите четыре пустых строки, каждая, вероятно, 1-байтовое распределение в куче
3. Четыре строковых назначения, для которых может потребоваться 4 освобождения кучи и новые выделения
4. Уничтожение строк, включающих 4 освобождения кучи
5. Уничтожение парного объекта

Игнорирование выделений стека (которые должны быть относительно дешевыми), что в сумме составляет 8 выделений кучи и еще 8 освобождений (или лучший вариант 4/4). Если это отладочная сборка, могут возникнуть дополнительные издержки при проверке каждой операции кучи.

Если ваши константы sizeX / sizeY равны 2400, то вы выполняете в общей сложности 92 миллиона операций с кучей. Если вам повезет, каждая из этих операций займет примерно одно и то же время, поскольку вы выделяете объект одного размера в каждом цикле. Если вам не повезло, то некоторые операции с кучей могут занять значительно больше времени из-за фрагментации кучи.

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

Answer 2

Вероятно, потому, что переменная является объектом.Поскольку p и d не являются примитивными типами, если компилятор не встроит их в конструктор и деструктор (что может произойти, если вы используете -O3 вместо -O2), он будет создавать и уничтожать две пары std :: pair (и, как следствие, четыре std:: строка) каждая итерация.Если бы это была примитивная переменная (например, int), компилятор мог бы оптимизировать это, даже если у вас не включена встроенная оптимизация.

РЕДАКТИРОВАТЬ: обратите внимание, что поскольку std :: string внутренне использует выделения кучи, даже не встроенныеоптимизировал бы эти распределения (но вы все равно сэкономили бы некоторые издержки со встроенным).Для std :: pair of int с -O3 производительность должна быть одинаковой внутри или снаружи цикла.

Answer 3

Общий ответ: Казалось бы, вы используете gcc (то есть g ++); вы всегда можете выполнить g ++ -S [вещи], чтобы увидеть, что G ++ делает с вашим кодом (при условии, что вы можете читать ассемблер достаточно хорошо, чтобы обойтись).

Конкретный ответ: Я удивлен, что разница в 40 раз, но в вашем коде, каждый раз, когда вы завершаете цикл, он должен дважды вызывать create_new_pair (и я бы подумал, что для «освобождения» пришлось бы немного очистить старая пара, но учитывая, что она в стеке, я думаю, что это не так сложно, как я думал, или, по крайней мере, я этого не вижу ... чтение кода из Gcc раньше было намного проще, чем чтение кода C ++ на данный момент)

Answer 4

В скомпилированном языке с хорошим компилятором (который выполняет хотя бы посредственную оптимизацию) наличие переменных, объявленных внутри цикла, никогда не будет «проигравшим» и часто (особенно для компиляторов с только скромной оптимизацией) будет «победителем»Msgstr ".

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

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

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

[Ах, при повторном чтении (и, возможно, при повторном редактировании плаката), я вижу, что это не просто переменная DECLARATION, а создание OBJECT, которое перемещаетсявне петли.]