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

StackOverflow https://stackoverflow.com/questions/1606894

  •  05-07-2019
  •  | 
  •  

Вопрос

В примере 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 секунд.

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

Это было полезно?

Решение

Конструктор

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

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

Другие советы

Ответы пока не объясняют всю важность проблемы.

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

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

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

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

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

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

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top