Поведение очереди STL

Question

Я сталкиваюсь с поведением в очереди STL, которое я не совсем понимаю.

В принципе, у меня есть две структуры

structA{
  string a;
}

structB{
 char b[256];
}

structA st1;
structB st2;

...assign a 256 characters string to both st1 and st2...


queue<structA> q1;
queue<structB> q2;
for(int i=0 ; i< 10000; i++){
  q1.push(st1);
}

 for(int i=0 ; i< 10000; i++){
  q2.push(st2);
}

Что я понимаю, так это то, что очередь, использующая структуру char, будет использовать намного больше времени (например, 5X) при передаче структуры по сравнению со структурой строки Изучив отдельные push, я понимаю, что производительность push структуры char имеет множество пиков (в диапазоне от 2X до 10X) здесь и там. В чем причина?

Спасибо.

Answer 1

Каждый раз, когда вы помещаете st1 или st2 в очередь, вы фактически нажимаете на копию (а не на ссылку или указатель). Разница в стоимости заключается в копировании данных. В structB вы должны копировать полные 256 байтов каждый раз. В structA вы только копируете экземпляр строки, который, скорее всего, имеет семантику копирования при записи, и, следовательно, до тех пор, пока один из них не будет изменен, все они будут иметь одну и ту же ссылку на базовые данные строки.

Answer 2

Ваша реализация C ++, вероятно, использует реализацию строки копирования при записи, что означает, что при копировании строки на самом деле не копируется строка (а вместо этого выполняется обратная ссылка на копию), а копируется только строка «по-настоящему», когда вы пишете

Чтобы проверить, так ли это, поместите это в цикл, после строки q1.push(st1):

++st1.a[0];

, затем снова.

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

Answer 3

std :: queue является адаптером для другого контейнера (который реализует front, back, push_back и pop_front), если вы не укажете, какой контейнер нужно адаптировать, он будет использовать std :: deque. Deque выполняет некоторую магию выделения блоков в фоновом режиме, которая должна обеспечивать изменение размера, аналогичное вектору, но работает лучше, поскольку она управляет несколькими несмежными блоками и не должна копировать все при каждом изменении размера. Во всяком случае, это предположение, но я бы сказал, что причина.

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

Теперь у вас есть шанс познакомиться с вашим профилировщиком и узнать наверняка! Запустите valgrind (--callgrind) или любой другой профилировщик, который поддерживает ваша платформа, и посмотрите, какие вызовы используют время и где.

Answer 4

Причины наиболее вероятны из-за:

1) Динамическое выделение памяти для хранения символьных данных внутри каждой строки
2) Возможно, но гораздо менее вероятно изменение размера буфера страницы deque, который поддерживает очередь.

Answer 5

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

Если строки не пусты, то копирование при записи срабатывает в любом случае, поэтому вы торгуете некоторым увеличением времени блокировки / счетчика ссылок и т. Д. С использованием памяти: что быстрее зависит от системы.