Здравствуйте, xobotik, Вы писали:

X>Здравствуйте, Кодт, Вы писали:

К>>int main()
К>>{
К>>    sources = vector< list<int> > {
К>>        list<int> { 1, 5, 12, 28, 31 },
К>>        list<int> { 6, 9, 13 },
К>>        list<int> { 3, 7, 10, 15 },
К>>    };
К>>}

X>Это не объединение ?)

Это — не объединение. Это три независимых списка, к которым сделан доступ по индексу.
Легко убедиться, заменив вектор списков на вектор указателей на списки, как у топикстартера.

Здравствуйте, B0FEE664, Вы писали:

<>
Хороший подход, но энергичный.
В случае, если списки длинные (и упорядоченные), то можно запустить столько потоков, сколько есть списков, и засыпать там
— либо к заданным моментам времени — sleep_until, естественно, отсчитывая от момента старта программы
— либо на время разности между смежными значениями (это хуже, т.к. набежит ошибка)

Здравствуйте, watchmaker, Вы писали:

W>list 590 ms // c и без автовекторизации
W>vector 103 ms // без автовекторизации

для сумирования списка критический путь — зависимые load из L1 cache, каждый требует 4 тактов на intel. для сумирования массива — выполняется один add каждый цикл. если вести чуть более сложны вычисления, то загрузка адреса след. элемента будет происходить параллельно с вычислениями, а вот от проверки на null на каждой итерации избавиться не удастся

Здравствуйте, watchmaker, Вы писали:

W>list 590 ms // c и без автовекторизации
W>vector 103 ms // без автовекторизации
W>vector 43 ms // c автовекторизацией
W>[/code]

То, что std::list делает allocate if N+1> CURRENT_SIZE then CURRENT_SIZE=CURRENT_SIZE+1 allocate(1) для каждой добавляемой ноды,
а std::vector по закону if N+1> CURRENT_SIZE then CURRENT_SIZE=CURRENT_SIZE*2 allocate(CURRENT_SIZE*2 ), тем самым уменьшая количество
brk в ядро.

W>Это верно разве что только после первичного заполнения списка.

Просто просмотрите как устроены slab аллокаторы в linux/solaris. А так тема долгая для этого форума.

W>А если вставки или удаления в середине не нужны, то зачем тем более выбирать список, а не массив?

Списки нужны как раз когда есть необходимость тасовать объекты. Непрерывный массив подходит
только для последовательных хранилищ, неизменяемых со временем элементов.

Здравствуйте, watchmaker, Вы писали:

W>Но, разумеется, скорость работы меряется не числом инструкций. Поэтому тест нужно ещё запустить. Возьмём миллион чисел, положим их в контейнер.

accumulate шёл сразу после заполнения? Если так, то многие из элементов могут быть уже в L3. Попробуй миллионов 100 — чтобы гарантированно вымыть весь кэш.

Здравствуйте, smeeld, Вы писали:

S>Здравствуйте, watchmaker, Вы писали:

W>>list 590 ms // c и без автовекторизации
W>>vector 103 ms // без автовекторизации
W>>vector 43 ms // c автовекторизацией
W>>[/code]

S>То, что std::list делает allocate if N+1> CURRENT_SIZE then CURRENT_SIZE=CURRENT_SIZE+1 allocate(1) для каждой добавляемой ноды,
S>а std::vector по закону if N+1> CURRENT_SIZE then CURRENT_SIZE=CURRENT_SIZE*2 allocate(CURRENT_SIZE*2 ), тем самым уменьшая количество
S>brk в ядро.
И что?
Во-первых, на время теста это не влияет, ведь std::accumulate не делает аллокаций.
Во-вторых, стратегия роста (+1) вместо (×2) для списка не так страшна как для вектора, ведь ему никогда не нужно переносить уже существующие элементы.
В-третьих, brk или mmap в ядро уйдут только когда уже выделенный буфер заполнится, до этого выделения памяти будет происходить лишь внутри аллокатора программы, что совсем не так страшно. А памяти после brk вернётся не мало — хватит на много элементов списка.
Но, да, если же замерять время с аллокациями, то картина для списка может стать ещё печальнее.

W>>Это верно разве что только после первичного заполнения списка.
S>Просто просмотрите как устроены slab аллокаторы в linux/solaris. А так тема долгая для этого форума.
Да, я исходил именно из тех допущений, что аллокатор устроен на аналогичном принципе. И именно в этом случае при использовании slab-подобных подходов у редактируемого списка возникают проблемы с локальностью. Впрочем эти проблемы возникнут у изменяемого списка в любом случае.

W>>А если вставки или удаления в середине не нужны, то зачем тем более выбирать список, а не массив?
S>Списки нужны как раз когда есть необходимость тасовать объекты.
Ну так именно об этом я и говорю: если нужно тасовать объекты, то о каком попадании в кеш идёт речь? После хорошей перетасовки каждый следующий элемент списка будет находится чуть ли не в случайной области памяти. А кеш-промахи — это намного-намного страшнее любой ерунды вроде чтения адреса следующего элемента вместо сдвига указателя у вектора.

Здравствуйте, sokel, Вы писали:

EP>>Легко приводится к интерфейсу GetNext.
S>ага, как то так наверное:

Да, так.
Как вариант можно на std::priority_queue. Но с ручным вызовом pop_heap/push_heap/make_heap мне даже чуть больше нравится — не нужно доставать элемент, а потом класть обратно (точнее нужно, но тут чуть эффективней получается — так как он меньше двигается).

Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>Здравствуйте, watchmaker, Вы писали:

W>>Но, разумеется, скорость работы меряется не числом инструкций. Поэтому тест нужно ещё запустить. Возьмём миллион чисел, положим их в контейнер.

EP>accumulate шёл сразу после заполнения? Если так, то многие из элементов могут быть уже в L3. Попробуй миллионов 100 — чтобы гарантированно вымыть весь кэш.
На таких объёмах уже привлекает внимание факт, что список занимает почти в 6 раз больше памяти чем вектор :)
А относительная скорость осталась почти такой же.

Здравствуйте, watchmaker, Вы писали:

W>А кеш-промахи — это намного-намного страшнее любой ерунды вроде чтения адреса следующего элемента вместо сдвига указателя у вектора.

Все элементы находятся в пределах одного непрерывного массива, список обеспечивает лишь
политику доступа и управления элементами, которые в реальности распологаются в виде массива.
О каких промахах, идёт речь, которых не будет при политике доступа и управления объектами
по принципу непрерывного последовательного массива?

Здравствуйте, smeeld, Вы писали:

S>>>Списки нужны как раз когда есть необходимость тасовать объекты.
W>>Ну так именно об этом я и говорю: если нужно тасовать объекты, то о каком попадании в кеш идёт речь? После хорошей перетасовки каждый следующий элемент списка будет находится чуть ли не в случайной области памяти. А кеш-промахи — это намного-намного страшнее любой ерунды вроде чтения адреса следующего элемента вместо сдвига указателя у вектора.
S>Все элементы находятся в пределах одного непрерывного массива, список обеспечивает лишь
S>политику доступа и управления элементами, которые в реальности распологаются в виде массива.
S>О каких промахах, идёт речь, которых не будет при политике доступа и управления объектами
S>по принципу непрерывного последовательного массива?

От того что у тебя все узлы(или только элементы) списка лежат в одном массиве последовательно, не лишает обход перетасованного списка его random'ной сущности

Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>От того что у тебя все узлы(или только элементы) списка лежат в одном массиве последовательно, не лишает обход перетасованного списка его random'ной сущности

если доступ будет идти последовательно по адресам n,n+8,n+16... то это будет так же предсказуемо, как доступ к массиву по адресам n,n+4,n+8...

Здравствуйте, watchmaker, Вы писали:

W>На таких объёмах уже привлекает внимание факт, что список занимает почти в 6 раз больше памяти чем вектор
W>А относительная скорость осталась почти такой же.

а не в 3 — int vs int+int*? во-второрых, вариант с padd ещё быстрее, так что дело не в памяти

Здравствуйте, Evgeny.Panasyuk, Вы писали:



EP> не лишает обход перетасованного списка его random'ной сущности

Мы говорим о реальных задачах, и существующих оптимальных механизмах
их решения, или о вакуумном, строго последовательном расположении
объектов и таком же доступе к ним? Понятно, что аккумулировать на
непрерывный массив c paddd/addpd быстрее, но что если у нас, скажем,
протокол обмена с форматом сообщений и с полнсотью рандомной их обработкой?
Тогда наоборот, доступ и управление данными по принципу непрерывного
массива-это качели.

Здравствуйте, BulatZiganshin, Вы писали:

W>>На таких объёмах уже привлекает внимание факт, что список занимает почти в 6 раз больше памяти чем вектор
W>>А относительная скорость осталась почти такой же.

BZ>а не в 3 — int vs int+int*?

x64 (и не забываем про alignment)
односвязный список: Node*+int32, sizeof = 16, то есть 4x
двусвязный список: 2*Node*+int32, sizeof = 24, то есть 6x

Здравствуйте, BulatZiganshin, Вы писали:

EP>>От того что у тебя все узлы(или только элементы) списка лежат в одном массиве последовательно, не лишает обход перетасованного списка его random'ной сущности
BZ>если доступ будет идти последовательно по адресам n,n+8,n+16... то это будет так же предсказуемо, как доступ к массиву по адресам n,n+4,n+8...

Я же не зря подчеркнул и выделил жирным:
S>>>>Списки нужны как раз когда есть необходимость тасовать объекты.

P.S. ИМХО, затенение старых сообщений не нужно.

Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>>>От того что у тебя все узлы(или только элементы) списка лежат в одном массиве последовательно, не лишает обход перетасованного списка его random'ной сущности
EP>Я же не зря подчеркнул и выделил жирным:
S>>>>>Списки нужны как раз когда есть необходимость тасовать объекты.

так написал-то ты прямо противоположное! если элементы лежат последовательно, то и доступ будет последователен как в массиве. чи ни то ни

Здравствуйте, BulatZiganshin, Вы писали:

EP>>>>От того что у тебя все узлы(или только элементы) списка лежат в одном массиве последовательно, не лишает

обход перетасованного списка

его random'ной сущности
EP>>Я же не зря подчеркнул и выделил жирным:
S>>>>>>Списки нужны как раз когда есть необходимость тасовать объекты.
BZ>так написал-то ты прямо противоположное! если элементы лежат последовательно, то и доступ будет последователен как в массиве. чи ни то ни

Написал я про обход перетасованного списка.
Список который всегда последовательно обходит элементы заданного массива — избыточен (разве что нужен для совместимости с каким-то API, принимающим только список)

Здравствуйте, smeeld, Вы писали:

EP>> не лишает обход перетасованного списка его random'ной сущности
S>Мы говорим о реальных задачах, и существующих оптимальных механизмах
S>их решения, или о вакуумном, строго последовательном расположении
S>объектов и таком же доступе к ним? Понятно, что аккумулировать на
S>непрерывный массив c paddd/addpd быстрее, но что если у нас, скажем,
S>протокол обмена с форматом сообщений и с полнсотью рандомной их обработкой?
S>Тогда наоборот, доступ и управление данными по принципу непрерывного
S>массива-это качели.

Не пойму что ты пытаешься сказать. То что у списка есть своя область применения? Так с этим никто и не спорил

Здравствуйте, PM, Вы писали:


PM>А учитывая, что в стандартной библиотеке для индексов и количества элементов в контейнере используется беззнаковый size_t
Разве это гарантируется?

Здравствуйте, slava_phirsov, Вы писали:

_>Ну вот, да, а в Qt наоборот сплошь и рядом int. Люди не смогли договориться о порядке следования байт, где уж тут знаковость индексов уединообразить. Только диктатура спасет человечество, ИМХО

А исчо некоторые ызврошэнци трактуют отрицательные индексы, как индексы с конца массива...