Iterator через призму С

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

Проиллюстрируем

[code lang="cpp"]
template
class carray
{
public:
typedef TT * iterator;
carray ( TT * pData, int length )
: m_pData(pData)
, m_iLength(length)
{};
iterator begin() const { return m_pData; }
iterator end() const { return m_pData + m_iLength; };
protected:
TT * m_pData;
int m_iLength;
};
[/code]

Несложно заметить, что для TT==int

[code lang="cpp"]
typedef int * iterator;
[/code]

Зачем всё это надо (ну кроме очевидной изотерики типа boost::array)? Для уменьшения abstraction penalty, как бы удивительно это не звучало. Здесь итератор это абстракция, которую можно убрать.

А на практике это работает вот так. В STL есть алгоритмы, например qsort. Этими алгоритмами можно пользоваться. Результат работает быстрее чем С эквивалент (за счёт inline-ов). Кроме того он синтаксически проще.

Итак тест

[code lang="cpp"]
#define TEST_LENGTH 1023
#define REPEAT_COUNT 100000

int cmp_int ( const void * a, const void * b )
{
return *((int *)a) - *((int *)b);
}

void main ( void )
{
int reference_data[TEST_LENGTH];
std::vector v_reference_data;
carray a_reference_data ( reference_data, TEST_LENGTH );
int c_array[TEST_LENGTH];
std::vector v_array;
carray cv_array ( c_array, TEST_LENGTH );

v_array.resize(TEST_LENGTH);

v_reference_data.resize(TEST_LENGTH);
for ( int i=0; i {
reference_data[i] =
v_reference_data[i] =
rand();
}

clock_t t0_C = clock();
for ( int r=0; r {
for ( int i=0; i c_array[i] = reference_data[i];
qsort ( c_array, TEST_LENGTH, sizeof(int), cmp_int );
}
clock_t t1_C = clock();

clock_t t0_V = clock();
for ( int r=0; r {
std::copy ( v_reference_data.begin(),
v_reference_data.end(), v_array.begin() );
std::sort ( v_array.begin(), v_array.end() );
}
clock_t t1_V = clock();

clock_t t0_CV = clock();
for ( int r=0; r {
std::copy ( a_reference_data.begin(),
a_reference_data.end(), cv_array.begin() );
std::sort ( cv_array.begin(), cv_array.end() );
}
clock_t t1_CV = clock();

printf ( "c-array %f\n", int((t1_C-t0_C)*10.0/CLK_TCK)/10.0 );
printf ( "v-array %f\n", int((t1_V-t0_V)*10.0/CLK_TCK)/10.0 );
printf ( "cv-array %f\n", int((t1_CV-t0_CV)*10.0/CLK_TCK)/10.0 );
}
[/code]

И результат

c-array 15.3
v-array 6.3
cv-array 6.2

Мерял и почти удивлялся. CV-array чуть-чуть быстрее, исключительно за счёт std::copy. C-array отстаёт исключительно из-за inline-а.

Результат на уровне фокуса. В отличие от большинства функциональных языков, С++ позволяет избавляться от abstraction penalty на всевозможных уровнях. Он очевидно будет быстрее, если такой penalty специально не добавлять. Цена такого penalty варьируется от процентов, до тысяч раз.

Вывод всегда одинаковый - мерять самому, проверять 10 раз, в urban legends не верить. STL таки бывает быстрее чем нативный C. С фокусами.

P.S. .net 2005 со стандартными настройками в release

  • http://vshabanov-ru.blogspot.com/ vshabanov

    > Мерял и почти удивлялся.
    Не пойму только чему удивляться. Разве только тому, что такая маленькая разница между заинлайненным std::sort и qsort, который на каждое сравнение вызывает внешнюю _cdecl функцию, да еще и перемещает потом 4 байта место одного int (хотя это наверное соптимизено). Кстати, если бы ф-я cmp была-бы потяжелее, а структура данных потолще, то разница, скорее всего, измерялась бы процентами.

    > В отличие от большинства функциональных языков, С++ позволяет избавляться от abstraction penalty на всевозможных уровнях.
    Таки начинаем интересоваться функциональными языками ) Вся эта тема с abstraction penalty очень напоминает мне тему с дороговизной вызовов виртуальных функций в С++, которая была лет 7-10 назад. Тогда плюсы были еще высокоуровневым языком и многие боялись внезапных тормозов. Для производительности тогда юзали асмовые вставки. Теперь наблюдаем поиски тормозов в очередных высокоуровневых языках, а избавляемся от них сишными/плюсовыми вставками. Что будет еще лет через десять? )

    > Вывод всегда одинаковый – мерять самому
    Вот это правильно. Замер времени-профайлер-замер-профайлер. Еще очень важно понимание того, что на самом деле творится при выполнении программы. У многих его нет. И даже тех, у кого есть, профайлер все равно может удивить )

  • look4awhile

    удивляюсь маленькой разнице между v-sort и vc-sort. т-е тому что реально инстанциируется один и тот-же шаблон (!!!). а именно std::_Sort(int *,int). в обоих случаях. и тормоза от std::copy, точне от проверки параметров при них.

    функциональными языками интересуюсь очень давно. сносно могу писать на хаскеле, scheme. по ощущениям ocaml с C++ вставками уже можно. хаскель нельзя. scheme-подобное можно, и очень давно уже – видел на практике, очень живенько работало на PS2.

    тема с abstraction penalty никуда не делась. vptr дереференс как не был бесплатный, так и не стал бесплатный, к сожалению. очень измеримо. объём кода только слегка вырос. другой момент что критерии “бесплатности” поменялись в пользу успеть делать в срок больше объёма. вопрос пока только квалификации, к сожалению.

  • http://-winnie.livejournal.com _winnie

    >urban legends не верить. STL таки бывает быстрее чем нативный. С фокусами.
    Эм. Каких legends? Вроде именно инлайном все книжки по шаблонам и понтуются, когда объясняют как алгоритмы STL могут быть быстрее алгоритмов на C.

    Замечу, что итератор std::vector может быть как указателем, так и структурой, в зависимости от дефайнов и версии STL, что было в этом тесте я не понял. Компилятор тоже не указан, злобная инлайновость VC известна. Поэтому вывод не очень четкий…

    Кстати, иногда бывают неожиданные сюрпризы.

  • look4awhile

    приписал компилятор и настройки

  • http://vshabanov-ru.blogspot.com/ vshabanov

    > и тормоза от std::copy, точне от проверки параметров при них.
    Я бы тут вообще memcpy вставил (хотя оно заметно опаснее, чем std::copy). А то, что инстациируется одинаковый шаблон, так компиляторы не дураки делают все-таки )

    > по ощущениям ocaml с C++ вставками уже можно.
    Чем я и занимаюсь последние 3 года. Только лучше с C-вставками. Т.е. все, что сложнее прочесывания по массиву или матрице надо делать на кемле. Только недавно это окончательно понял. До этого некоторую относительно высокоуровневую логику тоже делал, по привычке, на плюсах — лишняя трата времени, плюс потеря надежности. Также есть потеря производительности, т.к. сборщик мусора дает лучшую locality (складывает ссылающиеся друг на друга структуры данных близко в памяти), не говоря уже о большей эффективности аллокаций (хотя они тоже не бесплатны и “no malloc per frame” по прежнему рулит, правда не столько из соображений фрагментации памяти, сколько из-за тупого перформанса — кемловская часть проекта может легко проводить процентов 40 времени в сборщике, если неаккуратно писать).

    > хаскель нельзя.
    Да. Причем не по соображениям производительности, а по соображениям надежности. Очень уж у многих людей возникают утечки памяти из-за ленивых вычислений, а форсить все подряд стрикт аннотейшнами как-то парит. Еще хаскеловские type classes со всякими неявными fromRational/toRational могут изрядно удивить. Хотя в С тоже есть неявное приведение типов, так что этим настоящего джигита не испугать (просто в кемле с этим жестко, многих бесит, но это сильно увеличивает надежность и понимание того, что на самом деле делает прога).

    > scheme-подобное можно
    Динамическая типизация, в топку. Пройденный этап. Я хочу знать, что скрипт не будет работать до того, как его запущу.

    > другой момент что критерии “бесплатности” поменялись в пользу успеть делать в срок больше объёма.
    И будут менять в пользу все большего и большего объема. По-этому я особо никого не убеждаю писать на кемле или хаскеле. У меня есть преимущество (хотя непосредственно кодинг — достаточно малая часть игрового проекта), а остальные к этому сами придут, когда некуда будет деваться.

    > вопрос пока только квалификации, к сожалению.
    Вот с этим непонятно что делать. Требования такие, что человека неопытного просто страшно пускать к определенным частям проекта. А пока он их не покодит, опытным не станет. Брать сразу опытного — а где ты его найдешь (и сколько он попросит), а учить неопытного — тоже долго.

  • http://-winnie.livejournal.com _winnie

    >P.S. .net 2005 со стандартными настройками в release

    Если добавить
    #define _SECURE_SCL 0
    #define _HAS_ITERATOR_DEBUGGING 0

    результат чуть-чуть изменится…

    Разный результат для двух последних похоже исходит просто из разного положения в памяти c_array и v_array, если попросить cv_array указывать на тот же v_array, то результат не будет неожиданным.

  • http://aruslan.livejournal.com/ aruslan

    Собственно, у меня с нормальными настройками в release v_array устойчиво быстрее cv_array.
    Самописный cv_array не спасает ни выравнивание ни настройки типа buffer security checks.

    А проблема очевидно в том, что end() возвращает m_pData + m_iLength.
    Простое добавление m_pDataEnd( pData+length ) в конструктор – и вуаля cv_array таки on par with v_array.

    Бойтесь данайцев.

  • http://aruslan.livejournal.com/ aruslan

    Но после включения всякого cv_array дрожит чуть ниже уровня v_array даже при выравниваниях и т.п.

    Включал ради интереса (VS 9.0):
    /Ox /Ob2 /Oi /Ot /GL /D “WIN32″ /D “NDEBUG” /D “_CONSOLE” /D “_SECURE_SCL=0″ /D “_HAS_ITERATOR_DEBUGGING=0″ /D “_MBCS” /FD /MT /GS- /Gy /arch:SSE /Fo”Release\\” /Fd”Release\vc90.pdb” /W3 /nologo /c /Zi /TP /errorReport:prompt

    Что конкретно повлияло не смотрел.

  • cyberursus

    Зато как вдумчиво Dinkumware заимплементили std::vector::push_back() – интересно, компилятор может это скомпилировать в принципе?

    void push_back(const _Ty& _Val)
    { // insert element at end
    if (size()

  • Dront

    Я вот чего не понимаю. Причем тут С и С++? Причем тут язык вообще? Сравниваются две реализации quick sort. Одна с инлайн-сравнением, другая без. Очевидно, в случае простой функции сравнения, первое быстрее. Но это разница в библиотеках, а не языках. Что мешает в С++ сделать тормозно (например вызвав qsort обычный)? Что мешает в С сделать макрос, генерящий qsort с inline сравнением?

  • leshikru

    Cи-шную версию зря так затормозили.
    Ведь std::copy для вектора int-ов скомпилируется в memmove_s, а в сишном варианте простой цикл, думаю помедленнее будет.

  • http://www.codygain.com neteraser

    >> С точки зрения С итератор это такой плохой указатель с неочевидным оверхедом. Что удивительно, обратное тоже верно. С точки зрения С++ указатель, это такой unsafe итератор с очевидным отсутствием оверхеда.

    Удивительно сформулировал :) Отличная фраза – уйдет на цитаты.

  • Dmitry Tyurev

    > Каких legends? Вроде именно инлайном все книжки по шаблонам и понтуются, когда объясняют как алгоритмы STL могут быть быстрее алгоритмов на C.

    Поддержу winnie. Хотел написать то же самое, но решил пробежать сначала комментарии.

  • nol

    В продолжение темы. Не только int скомпилируется в memmove_s, очевидно что множество типов которые можно безболезненно перемещать гораздо мощнее. К сожалению, большинство реализаций СТЛ об этом не задумываются, поэтому сортировку сложных структур делают сортировкой индексов с разыменовывающим предикатом (что очень неудобно). А ведь типы которые, например, PIML, можно было бы и так, ан нет… конструктор копирования дороговат. Румынский дядя Андрей подсказывает, что с этим можно, и нужно бороться (впрочем, все, как всегда, просто :)).