понедельник, июля 10, 2006

Оценка производительности контейнеров

Standard Container Benchmark - программка, сравнивающая прозиводительность различных контейнеров. Задача, которая выбрана для оценки производительности: удаление дубликатов из последовательности чисел типа double. Примечательно в этой программке то, что ее написали Степанов со Страуструпом специально для программистов. Чтобы было удобнее выбирать контейнер для своей задачи, чтобы можно было сравнить различные реализации контейнеров, поэкспериментировать с настройками оптимизации в компиляторе. В результате получается что-то вроде такого:


size array vector with pointers vector with iterators deque list set multiset
10 1.91 2.48 4.66 8.20 22.50 6.95 11.05
100 1.39 1.34 3.09 4.67 8.52 5.03 7.22
1000 1.25 1.25 2.97 3.98 7.52 4.56 7.05
10000 1.41 1.31 2.75 3.77 8.28 4.81 7.61
100000 1.17 1.19 2.52 3.25 11.08 7.53 14.48
1000000 1.48 1.56 3.23 4.27 12.34 9.86 11.08


Ссылки по теме:
comp.lang.c++.moderated Container Performance. Пост Страуструпа с этой программой, который вылился в обсуждение производительности контейнеров на разных платформах.
openwatcom.contributors OWSTL benchmark experiment. Сравнительно недавнее обсуждение прозводительности контейнеров в OWSTL.

6 коммент.:

Анонимный комментирует...

хм. а _CRT_SECURE_NO_DEPRECATE и
#define _SECURE_SCL 0 ? а то и вовсе стл порт. цифры какието странные....

Alena комментирует...

цифры какието странные

Я эту табличку привела, чтобы было понятно что получится на выходе, как оно выглядеть будет. Сами цифры вряд ли представляют какой-то интерес.

D.K. комментирует...

А там время считается хитрым образом. Число прогона тестов объемом N обратно пропорционально N*log(N). Почему уж так решили - не знаю :)
Данные, наверное, могли быть и такие, как в посте. У меня было:

size array vec_p vec_i deque list set multiset
0000010 0.91 0.75 0.75 1.16 2.94 1.28 2.20
0000100 0.44 0.42 0.42 0.73 1.83 1.03 1.53
0001000 0.39 0.41 0.39 0.61 1.44 0.89 1.20
0010000 0.44 0.42 0.39 0.56 1.39 0.83 1.11
0100000 0.42 0.44 0.42 0.56 2.19 1.13 2.28
1000000 0.47 0.47 0.47 0.63 1.72 1.50 2.08

Vladimir комментирует...

Подскажите пожалуйста что за величина О(х) используется при оценке производительности контейнеров?

Никак не могу найти точное определение...

Алёна комментирует...

2Vladimir:
Подскажите пожалуйста что за величина О(х) используется при оценке производительности контейнеров?

Никак не могу найти точное определение...


Это большое О.

Vladimir комментирует...

Спасибо за информацию, теперь понятно как оценивается производительность операций со стандартными контейнерами