#include <cstdlib>
#include <algorithm>
#include <chrono>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <string>
#include <thread>
#include <vector>
struct Obj
{
Obj* next;
unsigned x;
Obj() : x(::rand()) {}
void update()
{
++x; // как-то меняем данные объекта
}
};
template<typename F>
void test(const char* name, F f)
{
std::vector<unsigned> times(100);
for (auto& dt : times)
{
std::this_thread::yield();
auto t1 = std::chrono::high_resolution_clock::now();
f();
auto t2 = std::chrono::high_resolution_clock::now();
dt = (unsigned)std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count();
}
std::cout << name << ": " << std::accumulate(times.begin(), times.end(), 0) / times.size() << " ms" << std::endl;
}
int main()
{
std::srand((unsigned)std::time(nullptr));
std::vector<Obj> vObj(1 * 1000 * 1000);
std::vector<Obj*> vPtr;
for (auto& o : vObj)
vPtr.push_back(&o);
std::random_shuffle(vPtr.begin(), vPtr.end()); // убиваем memory locality при последовательном доступе
Obj* lst = nullptr;
for (auto p : vPtr)
{
p->next = lst;
lst = p;
}
test("vector<Obj>", [&]{ for (auto& o : vObj) o.update(); });
test("vector<Obj*>", [&]{ for (auto& o : vPtr) o->update(); });
test("intrusive list", [&]{ for (auto o = lst; o; o = o->next) o->update(); });
}
Типичный результат на моей машине
vector<Obj>: 0 ms
vector<Obj*>: 10 ms
intrusive list: 76 ms
Почему так?
В случае с vector<Obj> объект лежат друг за другом, и эффективно читаются в кеш процессора
У vector<Obj*> перемешаны указатели, по этому кешировать доступ к данным объектов не получается.
Однако, сам vector<Obj*> прекрасно кешируется, а вот для связанного списка кеширование не работает вообще.
Говорить о "производительности структур данных" — некорректно. Производительность может быть у алгоритмов, работающих на этих структурах. А еще точнее — у конкретных реализаций этих алгоритмов.
Здравствуйте, wildwind, Вы писали:
W>Говорить о "производительности структур данных" — некорректно. Производительность может быть у алгоритмов, работающих на этих структурах. А еще точнее — у конкретных реализаций этих алгоритмов.
точно?
в некоторых случаях, скорость работы с вот такими массивами
int A[MaxX][MaxY]
и
int B[MaxY][MaxX]
при использовании одних и тех же алгоритмов, может различаться на несколько порядков, т.е. настолько сильно, что иногда приходится это учитывать и оптимизировать.
Всё сказанное выше — личное мнение, если не указано обратное.
может это быть свяхано с тем что у последней структуры степень параллелизма меньще??
понятно что если это вектор указаетлей то операции update над разными элементами независимы и даже на 1 роцуссоре конвейер моэет быть испольхован более эффективно
А у последней структуры каждый следующий элемммент хависит от предыдущего
ну вообще-то в последних двух случаях одинаково рандомный доступ к памяти. Вопрос в том почему 2 последних отличаются. То что первый бысттрее это всем понятно.
Здравствуйте, Abyx, Вы писали:
A>Почему так? A>В случае с vector<Obj> объект лежат друг за другом, и эффективно читаются в кеш процессора A>У vector<Obj*> перемешаны указатели, по этому кешировать доступ к данным объектов не получается. A>Однако, сам vector<Obj*> прекрасно кешируется, а вот для связанного списка кеширование не работает вообще.
Разницу дает вот что
for (auto& o : vPtr) ...
for (auto o = lst; o; o = o->next) ...
Слишком много лишних присваиваний. То есть, нужно взять да глянуть в ассемблерный код, что бы убедиться, что третий вариант цикла дает самый неэффективный код, а массивы очень сильно оптимизированы.
Здравствуйте, Ikemefula, Вы писали:
A>>Почему так? A>>В случае с vector<Obj> объект лежат друг за другом, и эффективно читаются в кеш процессора A>>У vector<Obj*> перемешаны указатели, по этому кешировать доступ к данным объектов не получается. A>>Однако, сам vector<Obj*> прекрасно кешируется, а вот для связанного списка кеширование не работает вообще.
I>Разницу дает вот что I>
I>for (auto& o : vPtr) ...
I>for (auto o = lst; o; o = o->next) ...
I>
I>Слишком много лишних присваиваний. То есть, нужно взять да глянуть в ассемблерный код, что бы убедиться, что третий вариант цикла дает самый неэффективный код, а массивы очень сильно оптимизированы.
*много* это одно?
ассемблерный код несложно сгенерить в уме:
for (auto& o : vPtr) ++o->x; это
mov esi, [vPtr._MyFirst]
mov edi, [vPtr._MyLast]
loo:
cmp esi, edi
jz end_loop ; низкая вероятность перехода
mov eax, [esi]
add [eax+4], 1
add esi, 4
jmp loo
end_loop:
for (auto o = lst; o; o = o->next) ++o->x; это
mov esi, [lst]
loo:
test esi, esi
jz end_loop ; низкая вероятность перехода
mov eax, esi
mov esi, [esi]
add [eax+4], 1
jmp loo
end_loop:
Здравствуйте, Ikemefula, Вы писали:
A>>ассемблерный код несложно сгенерить в уме:
I>Сложно, и ты, к тому же, привел не тот код.
почему не тот? где там разница?
I>00201446 mov edx,dword ptr [edx] // причина тормозов
и в чем тут причина? лишнее присваивание?
Здравствуйте, Abyx, Вы писали:
I>>Сложно, и ты, к тому же, привел не тот код. A>почему не тот? где там разница?
А что, лень поставить два фрагмента в один редактор и сравнить ?
I>>00201446 mov edx,dword ptr [edx] // причина тормозов A>и в чем тут причина? лишнее присваивание?
Здравствуйте, Ikemefula, Вы писали:
I>Здравствуйте, Abyx, Вы писали:
I>>>Сложно, и ты, к тому же, привел не тот код. A>>почему не тот? где там разница?
I>А что, лень поставить два фрагмента в один редактор и сравнить ?
я сравнил и не заметил разницы, за исключением разных регистров и т.п.
I>>>00201446 mov edx,dword ptr [edx] // причина тормозов A>>и в чем тут причина? лишнее присваивание?
I>AGI
Здравствуйте, Abyx, Вы писали:
I>>А что, лень поставить два фрагмента в один редактор и сравнить ?
A>я сравнил и не заметил разницы, за исключением разных регистров и т.п.
Здравствуйте, Ikemefula, Вы писали:
I>Address Generation Interlock
т.е. ты хочешь сказать, что из за того что две инструкции не выполняются параллельно, мы получили падение производительности в 6-8 раз?
т.е. вместо X + max(T1, T2) получилось X + T1 + T2, и X + max(T1, T2) = (X + T1 + T2) / 6 ?
не, это конечно круто, что ты помнишь что такое Address Generation Interlock, я вот совсем забыл как там работает pipeline, но к счастью я еще не забыл арифметику.
видишь ли, если между инструкциями воткнуть еще несколько инструкций, время работы практически не поменяется
Здравствуйте, Abyx, Вы писали:
A>т.е. ты хочешь сказать, что из за того что две инструкции не выполняются параллельно, мы получили падение производительности в 6-8 раз? A>т.е. вместо X + max(T1, T2) получилось X + T1 + T2, и X + max(T1, T2) = (X + T1 + T2) / 6 ?
Опережающей выборки не будет — это и есть причина тормозов.
A>(по вертикали — время, по горизонтали — количество замеров с этим временем (всего 100 тестов))
Здравствуйте, Abyx, Вы писали:
I>>Опережающей выборки не будет — это и есть причина тормозов.
A>о... это уже что-то новое, близкое к истине. A>а как же "много присваиваний"? а что с Address Generation Interlock?
Здравствуйте, Ikemefula, Вы писали:
I>Здравствуйте, Abyx, Вы писали:
I>>>Опережающей выборки не будет — это и есть причина тормозов.
A>>о... это уже что-то новое, близкое к истине. A>>а как же "много присваиваний"? а что с Address Generation Interlock?
I>Опережающей выборки не будет как раз из-за AGI.
угу, осталась только самая малость — как-то подтвердить это.
не, я не говорю что там нет AGI, но только как-то неочевидно, что именно AGI дает разницу в производительности
извини, но после того как тебе понадобился пяток постов чтобы сформулировать словосочетание "опережающая выборка", поверить тебе на слово как-то не получается
Здравствуйте, Abyx, Вы писали:
A>угу, осталась только самая малость — как-то подтвердить это. A>не, я не говорю что там нет AGI, но только как-то неочевидно, что именно AGI дает разницу в производительности A>извини, но после того как тебе понадобился пяток постов чтобы сформулировать словосочетание "опережающая выборка", поверить тебе на слово как-то не получается
Я на асме не писал около 12 лет , кода показать не смогу
Здравствуйте, Ikemefula, Вы писали:
I>Здравствуйте, Abyx, Вы писали:
A>>угу, осталась только самая малость — как-то подтвердить это. A>>не, я не говорю что там нет AGI, но только как-то неочевидно, что именно AGI дает разницу в производительности A>>извини, но после того как тебе понадобился пяток постов чтобы сформулировать словосочетание "опережающая выборка", поверить тебе на слово как-то не получается
I> Я на асме не писал около 12 лет , кода показать не смогу
да при чем тут вообще асм? и без асма понятно, что
o = o->next;
o->update();
o = o->next;
можно выполнить только последовательно.
для массива указателей достаточно внести такую же зависимость между итерациями, вместо
for (auto it = vPtr.begin(); it < vPtr.end(); ++it)
(*it)->update();
написать
for (auto it = vPtr.begin(); it < vPtr.end(); it += (*it)->x & 1)
(*it)->update();
