Сообщение Re[6]: Оцените решение задачи от 17.10.2014 21:45
Изменено 17.10.2014 22:02 Evgeny.Panasyuk
Здравствуйте, alzt, Вы писали:
EP>>Линейный обход связного списка в общем случае на порядок(и) дороже чем соответствующий обход вектора. Если в задаче не указанно что нужен именно связный список, то по-умолчанию нужно брать vector.
A>Можешь ответить поподробнее? Судя по рейтингу ты знаешь о чём пишешь, а не глупость написал.
watchmaker выше хорошо описал, попробую дополнить.
A>Это как-то связано с попаданием в кеш процессора?
A>Но в этом случае тоже на мой взгляд сложно получить разницу на порядок. Список также легко влезет в кеш. Разница только в том, что надо хранить указатель на сл. элемент, но это не так много.
При определённом количестве элементов, в кэш не влезают ни массив ни связанный список, и при новом проходе нужно заново прочитать все значения из памяти в обоих случаях.
Важно понимать, что кэш это не просто хранилище уже считанных значений, точнее в нём хранятся не только они.
Из памяти приходят не отдельные байты, а целые куски размером с cache-line — по 64 байта (естественно зависит от конкретной архитектуры железа).
То есть считав с произвольного места в памяти 4 байта, будет происходить полноценная перекачка из памяти в кэш аж 64 байт.
Если удачно подобрать структуру данных и алгоритм обхода, то все те "лишние" 60 байт которые пришли в кэш при первом запросе, будут использоваться следующими итерациями, а значит КПД использования memory bandwidth будет 100%. То есть, например, требуется обработать гигабайт, и перекачиваться из памяти в кэш будет именно гигабайт.
Примером этого является линейных обход массива — все элементы лежат плотно рядом с друг другом. Прочитав первый элемент с границы в 64 байта — мы также получим следующие лежащие за ним, и они не окажутся невостребованными.
При работе же со списком, в общем случае, запросив из random'ного места в памяти узел с int'ом — всё что придёт в кэш помимо самого узла, скорей всего окажется невостребованным (точнее оно может понадобится, когда уже переедет в следующий уровнеь кэша, или вообще в память).
Вот и считай — КПД использования memory bandwidth примерно 4/64*100% = 6.25%, или в 16 раз меньше чем у массива.
Если же payload больше 4 байт, то и КПД для списка улучшится.
Но, КПД использования пришедших cache-line — это не единственная проблема списков, там ещё много других проблем, например ещё нужно учитывать prefetcher
Да, и главное, задачи вида "пройтись по всем элементам, и сделать не слишком долгое вычисление" — упираются в скорость работы памяти. То есть время непосредственно вычислений намного меньше чем время пересылки данных из памяти.
С другой стороны, если для каждого элемента делается очень много работы — то особо не важно массив там, или список.
4.812521s / 0.023067s ~ 208.6x
ASM:
LIVE DEMO on Coliru — тут уменьшенно N, чтобы вписаться в лимит времени.
P.S. Это относится не только к спискам. Например, если есть массив указателей на объекты (чем грешат многие "true-OO" языки), особенно перетасованных/пересортированных, то мы получим абсолютно аналогичный эффект — каждое чтение имеет малое КПД, да ещё и из произвольного места.
EP>>Линейный обход связного списка в общем случае на порядок(и) дороже чем соответствующий обход вектора. Если в задаче не указанно что нужен именно связный список, то по-умолчанию нужно брать vector.
A>Можешь ответить поподробнее? Судя по рейтингу ты знаешь о чём пишешь, а не глупость написал.
watchmaker выше хорошо описал, попробую дополнить.
A>Это как-то связано с попаданием в кеш процессора?
A>Но в этом случае тоже на мой взгляд сложно получить разницу на порядок. Список также легко влезет в кеш. Разница только в том, что надо хранить указатель на сл. элемент, но это не так много.
При определённом количестве элементов, в кэш не влезают ни массив ни связанный список, и при новом проходе нужно заново прочитать все значения из памяти в обоих случаях.
Важно понимать, что кэш это не просто хранилище уже считанных значений, точнее в нём хранятся не только они.
Из памяти приходят не отдельные байты, а целые куски размером с cache-line — по 64 байта (естественно зависит от конкретной архитектуры железа).
То есть считав с произвольного места в памяти 4 байта, будет происходить полноценная перекачка из памяти в кэш аж 64 байт.
Если удачно подобрать структуру данных и алгоритм обхода, то все те "лишние" 60 байт которые пришли в кэш при первом запросе, будут использоваться следующими итерациями, а значит КПД использования memory bandwidth будет 100%. То есть, например, требуется обработать гигабайт, и перекачиваться из памяти в кэш будет именно гигабайт.
Примером этого является линейных обход массива — все элементы лежат плотно рядом с друг другом. Прочитав первый элемент с границы в 64 байта — мы также получим следующие лежащие за ним, и они не окажутся невостребованными.
При работе же со списком, в общем случае, запросив из random'ного места в памяти узел с int'ом — всё что придёт в кэш помимо самого узла, скорей всего окажется невостребованным (точнее оно может понадобится, когда уже переедет в следующий уровнеь кэша, или вообще в память).
Вот и считай — КПД использования memory bandwidth примерно 4/64*100% = 6.25%, или в 16 раз меньше чем у массива.
Если же payload больше 4 байт, то и КПД для списка улучшится.
Но, КПД использования пришедших cache-line — это не единственная проблема списков, там ещё много других проблем, например ещё нужно учитывать prefetcher
Автор: koodeer
Дата: 06.04.14
.Дата: 06.04.14
Да, и главное, задачи вида "пройтись по всем элементам, и сделать не слишком долгое вычисление" — упираются в скорость работы памяти. То есть время непосредственно вычислений намного меньше чем время пересылки данных из памяти.
С другой стороны, если для каждого элемента делается очень много работы — то особо не важно массив там, или список.
Тест
#define _HAS_ITERATOR_DEBUGGING 0
#define _SECURE_SCL 0
#include <boost/exception/detail/type_info.hpp>
#include <boost/range/algorithm_ext.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/timer/timer.hpp>
#include <exception>
#include <iostream>
#include <iterator>
#include <vector>
#include <list>
#if defined(__GNUC__)
#define NOINLINE __attribute__ ((noinline))
#elif defined(_MSC_VER)
#define NOINLINE __declspec(noinline)
#else
#define NOINLINE
#endif
template<int> NOINLINE void ASM_MARKER() { volatile int x = 0; (void)x; }
/******************************************************************************/
using namespace std;
template<typename Range>
void test(Range &r)
{
cout << boost::type_name<Range>() << ": ";
boost::timer::auto_cpu_timer t;
ASM_MARKER<111>();
volatile int result = boost::accumulate(r, 0);
ASM_MARKER<222>();
(void)result;
}
int main() try
{
vector<int> v(40000000);
boost::iota(v, 0);
boost::random_shuffle(v);
list<int> l(begin(v), end(v));
l.sort();
boost::sort(v);
for(unsigned i=0; i!=2; ++i)
{
test(v);
test(l);
}
}
catch(const exception &e)
{
cout << e.what() << endl;
}class std::vector<int,class std::allocator<int> >: 0.022010s wall, 0.015600s user + 0.000000s system = 0.015600s CPU (70.9%)
class std::list<int,class std::allocator<int> >: 4.811541s wall, 4.820431s user + 0.000000s system = 4.820431s CPU (100.2%)
class std::vector<int,class std::allocator<int> >: 0.023067s wall, 0.031200s user + 0.000000s system = 0.031200s CPU (135.3%)
class std::list<int,class std::allocator<int> >: 4.812521s wall, 4.820431s user + 0.000000s system = 4.820431s CPU (100.2%)4.812521s / 0.023067s ~ 208.6x
ASM:
; vector
$LL61@test:
add ebx, DWORD PTR [rax]
add rax, 4
cmp rax, r11
jne SHORT $LL61@test
; list
$LL82@test@2:
add ebx, DWORD PTR [rax+16]
mov rax, QWORD PTR [rax]
cmp rax, r11
jne SHORT $LL82@test@2LIVE DEMO on Coliru — тут уменьшенно N, чтобы вписаться в лимит времени.
P.S. Это относится не только к спискам. Например, если есть массив указателей на объекты (чем грешат многие "true-OO" языки), особенно перетасованных/пересортированных, то мы получим абсолютно аналогичный эффект — каждое чтение имеет малое КПД, да ещё и из произвольного места.
Re[6]: Оцените решение задачи
Здравствуйте, alzt, Вы писали:
EP>>Линейный обход связного списка в общем случае на порядок(и) дороже чем соответствующий обход вектора. Если в задаче не указанно что нужен именно связный список, то по-умолчанию нужно брать vector.
A>Можешь ответить поподробнее? Судя по рейтингу ты знаешь о чём пишешь, а не глупость написал.
watchmaker выше хорошо описал, попробую дополнить.
A>Это как-то связано с попаданием в кеш процессора?
A>Но в этом случае тоже на мой взгляд сложно получить разницу на порядок. Список также легко влезет в кеш. Разница только в том, что надо хранить указатель на сл. элемент, но это не так много.
При определённом количестве элементов, в кэш не влезают ни массив ни связанный список, и при новом проходе нужно заново прочитать все значения из памяти в обоих случаях.
Важно понимать, что кэш это не просто хранилище уже считанных значений, точнее в нём хранятся не только они.
Из памяти приходят не отдельные байты, а целые куски размером с cache-line — по 64 байта (естественно зависит от конкретной архитектуры железа).
То есть считав с произвольного места в памяти 4 байта, будет происходить полноценная перекачка из памяти в кэш аж 64 байт.
Если удачно подобрать структуру данных и алгоритм обхода, то все те "лишние" 60 байт которые пришли в кэш при первом запросе, будут использоваться следующими итерациями, а значит КПД использования memory bandwidth будет 100%. То есть, например, требуется обработать гигабайт, и перекачиваться из памяти в кэш будет именно гигабайт.
Примером этого является линейных обход массива — все элементы лежат плотно рядом с друг другом. Прочитав первый элемент с границы в 64 байта — мы также получим следующие лежащие за ним, и они не окажутся невостребованными.
При работе же со списком, в общем случае, запросив из random'ного места в памяти узел с int'ом — всё что придёт в кэш помимо самого узла, скорей всего окажется невостребованным (точнее оно может понадобится, когда уже переедет в следующий уровнеь кэша, или вообще в память).
Вот и считай — КПД использования memory bandwidth примерно 4/64*100% = 6.25%, или в 16 раз меньше чем у массива.
Если же payload больше 4 байт, то и КПД для списка улучшится.
Но, КПД использования пришедших cache-line — это не единственная проблема списков, там ещё много других проблем, например ещё нужно учитывать prefetcher
Да, и главное, задачи вида "пройтись по всем элементам, и сделать не слишком долгое вычисление" — упираются в скорость работы памяти. То есть время непосредственно вычислений намного меньше чем время пересылки данных из памяти.
С другой стороны, если для каждого элемента делается очень много работы — то особо не важно массив там, или список.
4.812521s / 0.023067s ~ 208.6x
ASM:
LIVE DEMO on Coliru — тут уменьшенно N, чтобы вписаться в лимит времени.
P.S. Это относится не только к спискам. Например, если есть массив указателей на объекты (чем грешат многие "true-OO" языки), особенно перетасованных/пересортированных, то мы получим подобный эффект — каждое чтение имеет малое КПД, да ещё и из произвольного места.
EP>>Линейный обход связного списка в общем случае на порядок(и) дороже чем соответствующий обход вектора. Если в задаче не указанно что нужен именно связный список, то по-умолчанию нужно брать vector.
A>Можешь ответить поподробнее? Судя по рейтингу ты знаешь о чём пишешь, а не глупость написал.
watchmaker выше хорошо описал, попробую дополнить.
A>Это как-то связано с попаданием в кеш процессора?
A>Но в этом случае тоже на мой взгляд сложно получить разницу на порядок. Список также легко влезет в кеш. Разница только в том, что надо хранить указатель на сл. элемент, но это не так много.
При определённом количестве элементов, в кэш не влезают ни массив ни связанный список, и при новом проходе нужно заново прочитать все значения из памяти в обоих случаях.
Важно понимать, что кэш это не просто хранилище уже считанных значений, точнее в нём хранятся не только они.
Из памяти приходят не отдельные байты, а целые куски размером с cache-line — по 64 байта (естественно зависит от конкретной архитектуры железа).
То есть считав с произвольного места в памяти 4 байта, будет происходить полноценная перекачка из памяти в кэш аж 64 байт.
Если удачно подобрать структуру данных и алгоритм обхода, то все те "лишние" 60 байт которые пришли в кэш при первом запросе, будут использоваться следующими итерациями, а значит КПД использования memory bandwidth будет 100%. То есть, например, требуется обработать гигабайт, и перекачиваться из памяти в кэш будет именно гигабайт.
Примером этого является линейных обход массива — все элементы лежат плотно рядом с друг другом. Прочитав первый элемент с границы в 64 байта — мы также получим следующие лежащие за ним, и они не окажутся невостребованными.
При работе же со списком, в общем случае, запросив из random'ного места в памяти узел с int'ом — всё что придёт в кэш помимо самого узла, скорей всего окажется невостребованным (точнее оно может понадобится, когда уже переедет в следующий уровнеь кэша, или вообще в память).
Вот и считай — КПД использования memory bandwidth примерно 4/64*100% = 6.25%, или в 16 раз меньше чем у массива.
Если же payload больше 4 байт, то и КПД для списка улучшится.
Но, КПД использования пришедших cache-line — это не единственная проблема списков, там ещё много других проблем, например ещё нужно учитывать prefetcher
Автор: koodeer
Дата: 06.04.14
(помогающий скрыть latency при предсказуемых паттернах доступа (типа обхода массива), и бесполезный для списков, так как пока не пришёл новый узел — неизвестно что prefetch'ить).Дата: 06.04.14
Да, и главное, задачи вида "пройтись по всем элементам, и сделать не слишком долгое вычисление" — упираются в скорость работы памяти. То есть время непосредственно вычислений намного меньше чем время пересылки данных из памяти.
С другой стороны, если для каждого элемента делается очень много работы — то особо не важно массив там, или список.
Тест
#define _HAS_ITERATOR_DEBUGGING 0
#define _SECURE_SCL 0
#include <boost/exception/detail/type_info.hpp>
#include <boost/range/algorithm_ext.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/timer/timer.hpp>
#include <exception>
#include <iostream>
#include <iterator>
#include <vector>
#include <list>
#if defined(__GNUC__)
#define NOINLINE __attribute__ ((noinline))
#elif defined(_MSC_VER)
#define NOINLINE __declspec(noinline)
#else
#define NOINLINE
#endif
template<int> NOINLINE void ASM_MARKER() { volatile int x = 0; (void)x; }
/******************************************************************************/
using namespace std;
template<typename Range>
void test(Range &r)
{
cout << boost::type_name<Range>() << ": ";
boost::timer::auto_cpu_timer t;
ASM_MARKER<111>();
volatile int result = boost::accumulate(r, 0);
ASM_MARKER<222>();
(void)result;
}
int main() try
{
vector<int> v(40000000);
boost::iota(v, 0);
boost::random_shuffle(v);
list<int> l(begin(v), end(v));
l.sort();
boost::sort(v);
for(unsigned i=0; i!=2; ++i)
{
test(v);
test(l);
}
}
catch(const exception &e)
{
cout << e.what() << endl;
}class std::vector<int,class std::allocator<int> >: 0.022010s wall, 0.015600s user + 0.000000s system = 0.015600s CPU (70.9%)
class std::list<int,class std::allocator<int> >: 4.811541s wall, 4.820431s user + 0.000000s system = 4.820431s CPU (100.2%)
class std::vector<int,class std::allocator<int> >: 0.023067s wall, 0.031200s user + 0.000000s system = 0.031200s CPU (135.3%)
class std::list<int,class std::allocator<int> >: 4.812521s wall, 4.820431s user + 0.000000s system = 4.820431s CPU (100.2%)4.812521s / 0.023067s ~ 208.6x
ASM:
; vector
$LL61@test:
add ebx, DWORD PTR [rax]
add rax, 4
cmp rax, r11
jne SHORT $LL61@test
; list
$LL82@test@2:
add ebx, DWORD PTR [rax+16]
mov rax, QWORD PTR [rax]
cmp rax, r11
jne SHORT $LL82@test@2LIVE DEMO on Coliru — тут уменьшенно N, чтобы вписаться в лимит времени.
P.S. Это относится не только к спискам. Например, если есть массив указателей на объекты (чем грешат многие "true-OO" языки), особенно перетасованных/пересортированных, то мы получим подобный эффект — каждое чтение имеет малое КПД, да ещё и из произвольного места.