C++ 3d.Комментарии




STL-контейнеры - часть 3


Data(int v, Data* p=0, Data* n=0) : val(v), prev(p), next(n) {}

// для собственного распределения памяти static Data* free; static void allocate(); void* operator new(size_t); void operator delete(void*, size_t); };

Data *head, *tail;

DList() { head=tail=0; }

~DList() { for (Data *ptr=head, *n; ptr; ptr=n) { // удаляем все элементы n=ptr->next; delete ptr; } }

void push_back(int v) // добавляем элемент { if (!head) head=tail=new Data(v); else tail=tail->next=new Data(v, tail); } };

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

односвязный односвязный с собственным
распределителем памяти
двусвязный с собственным
распределителем памяти
f1() f2() f1() f2() f1() f2()
реализация 1 9.6 12.1 1.1 12.1 1.3 12.1
реализация 2 20.2 2.5 1.8 2.5 1.9 2.5

И что же мы здесь видим?

    добавление собственного распределителя памяти существенно ускоряет программу (в нашем примере, от 9 до 11 раз). Также замечу, что это приводит и к существенной экономии памяти (как правило, для борьбы с внутренней фрагментацией стандартные распределители памяти выделяют отрезки памяти, кратные некоторому числу, например 16 байт; плюс память теряется на структурах, поддерживающих список выделенных блоков. Т.е. желательно выделять память большими блоками и как можно реже.

    в зависимости от качества компилятора/реализации STL, использование STL может быть как почти приемлемым (замедление 30% для двусвязного и 40% для односвязного списков), так и неприемлемым совершенно (замедление от 9 до 11 раз!)

    двусвязный список является вполне приемлемой альтернативой односвязному (замедление 5 - 20%)

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




    Содержание  Назад  Вперед