std :: pair <int, int> против структуры с двумя целыми числами

Question

В примере с ACM мне пришлось построить большую таблицу для динамического программирования. Мне пришлось хранить два целых числа в каждой ячейке, поэтому я решил пойти на std::pair<int, int>. Однако выделение огромного массива из них заняло 1,5 секунды:

std::pair<int, int> table[1001][1001];

Впоследствии я изменил этот код на

struct Cell {
    int first;
    int second;
}

Cell table[1001][1001];

и выделение заняло 0 секунд.

Чем объясняется такая огромная разница во времени?

Answer 1

Конструктор

std::pair<int, int>::pair() инициализирует поля значениями по умолчанию (ноль в случае int), а ваш struct Cell - нет (поскольку у вас есть только автоматически сгенерированный конструктор по умолчанию, который ничего не делает).

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

Answer 2

Ответы до сих пор не объясняют всю масштабность проблемы.

Как указал sharptooth, решение для пары инициализирует значения до нуля. Как указал Лемурик, парное решение не просто инициализирует непрерывный блок памяти, но и вызывает конструктор пар для каждого элемента в таблице. Однако даже это не означает, что это займет 1,5 секунды. Что-то еще происходит.

Вот моя логика:

Если предположить, что вы работали на древней машине, скажем, на частоте 1,33 ГГц, тогда 1,5 секунды - это 2e9 тактов. У вас есть 2e6 пар для построения, так что каждый конструктор пары требует 1000 циклов. Для вызова конструктора, который просто устанавливает два целых числа в ноль, не требуется 1000 циклов. Я не могу понять, как из-за отсутствия кэша это заняло бы столько времени. Я бы поверил, если бы число было меньше 100 циклов.

Я подумал, что было бы интересно посмотреть, куда еще идут все эти циклы ЦП. Я использовал самый дрянной самый старый компилятор C ++, который я смог найти, чтобы увидеть, смогу ли я достичь требуемого уровня потерь. Этот компилятор был VC ++ v6. В режиме отладки он делает что-то, чего я не понимаю. У него есть большой цикл, который вызывает конструктор пар для каждого элемента в таблице - достаточно справедливо. Этот конструктор устанавливает два значения в ноль - достаточно справедливо. Но непосредственно перед этим он устанавливает все байты в области 68 байтов равными 0xcc. Этот регион как раз перед началом большого стола. Затем он перезаписывает последний элемент этого региона с 0x28F61200. Каждый вызов конструктора пар повторяет это. Предположительно это какая-то бухгалтерия компилятора, поэтому он знает, какие области инициализируются при проверке ошибок указателя во время выполнения. Я хотел бы знать точно, для чего это.

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

Answer 3

Это все очень хорошие догадки, но, как все знают, догадки ненадежны.

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

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

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

Answer 4

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

Answer 5

это действительно хороший пример того, что нужно писать на C ++ и осторожно использовать STL. есть мысли?

мой проект работает над инструментом для тестирования производительности на уровне кода C & C ++, в котором мы сделаем много примеров кода, чтобы выяснить, что такое «хороший» код и что такое «плохая» привычка кодирования. см. http://effodevel.googlecode.com, чтобы узнать больше о C9B.M. планирование. Если у вас было много таких случаев, пожалуйста, присоединяйтесь к нам, чтобы помочь нам.