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

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

std::vector<typename ilist::value_type> objects(NumElements);
ilist l;
for(int i = 0; i < NumElements; ++i)
   l.push_back(objects[i]);
//Elements are unlinked in ilist's destructor
//Elements are destroyed in vector's destructor

Для интрузивных контейнеров все значения создаются в векторе и после этого вставляются в интрузивный список.

stdlist l;
for(int i = 0; i < NumElements; ++i)
   l.push_back(typename stdlist::value_type(i));
//Elements unlinked and destroyed in stdlist's destructor

Для стандартного списка элементы отталкиваются с помощью push_back().

std::vector<typename stdlist::value_type> objects(NumElements);
stdptrlist l;
for(int i = 0; i < NumElements; ++i)
   l.push_back(&objects[i]);
//Pointers to elements unlinked and destroyed in stdptrlist's destructor
//Elements destroyed in vector's destructor

Для стандартного компактного списка указателей элементы создаются в векторе и отталкиваются в списке указателей с помощью push_back().

stdlist objects;  stdptrlist l;
for(int i = 0; i < NumElements; ++i){
   objects.push_back(typename stdlist::value_type(i));
   l.push_back(&objects.back());
}
//Pointers to elements unlinked and destroyed in stdptrlist's destructor
//Elements unlinked and destroyed in stdlist's destructor

Длядисперсного списка указателейэлементы создаются в списке и выталкиваются обратно в списке указателей с помощью push_back().

Это время в микросекундах для каждого случая и нормированное время:

Результаты логичны: навязчивые списки требуют лишь одного распределения. Время разрушениянормального_linkнавязчивого контейнера тривиально (сложность:O)), тогда какбезопасного_linkиавто_unlinkнавязчивые контейнеры должны помещать крючки стертых значений в состояние по умолчанию (сложность:ONumElements). Вот почемунормальный_linkнавязчивый список сияет в этом тесте.

Неинтрузивные контейнеры должны выделять гораздо больше ресурсов, и именно поэтому они отстают.дисперсныйуказательсписокдолжен сделатьНумэлементы*2распределения, поэтому результат неудивителен.

Тест Linux показывает, что стандартные контейнеры очень хорошо работают против навязчивых контейнеров с большими объектами. Почти та же версия GCC в MinGW работает хуже, поэтому, возможно, хороший распределитель памяти является причиной этих отличных результатов.

В следующем испытании измеряется время, необходимое для завершения вызовов функции членаобратно[]. Значенияtest_classиitest_classи списки создаются, как объяснено в предыдущем разделе.

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

Вот результаты:

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

//Object list (holding `test_class`)
stdlist objects;
//Pointer list (holding `test_class` pointers)
stdptrlist l;
for(int i = 0; i < NumElements; ++i){
   //Allocation from the object list
   objects.push_back(stdlist::value_type(i));
   //Allocation from the pointer list
   l.push_back(&objects.back());
}

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

В следующем испытании измеряется время, необходимое для завершения вызовов на функцию членаPredpred. Значенияtest_classиitest_classи списки создаются, как объясняется в первом разделе. Значения будут сортироваться по восходящему и нисходящему порядку каждой итерации. Например, еслиlявляется списком:

for(int i = 0; i < NumIter; ++i){
   if(!(i % 2))
      l.sort(std::greater<stdlist::value_type>());
   else
      l.sort(std::less<stdlist::value_type>());
}

Для списка указателей объект функции будет адаптирован с использованиемfunc_ptr_adaptor:

for(int i = 0; i < NumIter; ++i){
   if(!(i % 2))
      l.sort(func_ptr_adaptor<std::greater<stdlist::value_type> >());
   else
      l.sort(func_ptr_adaptor<std::less<stdlist::value_type> >());
}

Обратите внимание, что для списков указателейсортвозьмет функциональный объект, которыйполучит доступ кзначениям test_class, хранящимся в другом списке или векторе, поэтому списки указателей будут страдать от дополнительного опосредования: им потребуется доступ кзначения test_class, хранящиеся в другом контейнере для сравнения двух элементов.

Вот результаты:

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

Следующий тест измеряет время, необходимое для повторения всех элементов списка, и увеличивает значение внутреннегоi_элемента:

stdlist::iterator it(l.begin()), end(l.end());
for(; it != end; ++it)
   ++(it->i_);

Значенияtest_classиitest_classи списки создаются, как объясняется в первом разделе. Обратите внимание, что для списков указателей итерация будет иметь дополнительное опосредование: им потребуется доступ к значениямtest_class, хранящимся в другом контейнере:

stdptrlist::iterator it(l.begin()), end(l.end());
for(; it != end; ++it)
   ++((*it)->i_);

Вот результаты:

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

Интрузивные контейнеры могут предложить преимущества производительности, которые не могут быть достигнуты с эквивалентными неинтрузивными контейнерами. Улучшения локализации памяти заметны, когда вставленные объекты малы. Минимизация вызовов выделения/выделения памяти также является важным фактором, и интрузивные контейнеры делают это простым, если все объекты, подлежащие вставке в интрузивные контейнеры, распределяются с использованиемstd::вектораилиstd::deque.