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

lpd>Во-первых, как я понял, ты пытаешься измерить задержки из-за cache-miss с помощью listа.

cache-miss'ы будут и в случае vector<int*> и в случае list<int>.
В случае с list<int> помимо cache-miss'а добавляется зависимость по данным — чтобы узнать адрес следующего узла, надо загрузить предыдущий и так далее — поэтому он и медленнее на два порядка, а не на один как vector<int*>.
Подобная зависимость по данным создаётся и в управляемом коде, где чтобы обратиться к полю под-объекта ... под-объекта объекта нужно сделать похожий забег по указателям, разве что цепочки не такие длинные.

Кстати, чтобы исключить эти cache-miss, достаточно закомментировать все сортировки — тогда получается следующий расклад:
* массив указателей в 2.5 раза медленее
* список медленее на порядок

lpd>Думаю, что это не очень хороший подоход,

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

lpd>т.к. элементы list могут быть расположены в памяти последовательно.

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

lpd>В моем же тесте, я точно обращаюсь к элементам в случайном порядке.

Я вообще-то сравниваю ТРИ варианта — в случае vector<int*> — как раз идёт обращение в случайном порядке

lpd>Во-вторых, ты измеряешь производительность stl контейнеров, а не процессора.

ШТА? Я уже выше привёл вывод ассемблера:

.L152:
    mov    rcx, QWORD PTR [rax]
    add    rax, 8
    add    edx, DWORD PTR [rcx]
    cmp    rsi, rax
    jne    .L152

Или другой пример:

.L152:
    add    edx, DWORD PTR [rax]
    add    rax, 4
    cmp    rcx, rax
    jne    .L152

Покажи где тут "производительность stl контейнеров"
Итератор vector'а это по сути указатель, и даже если над ним тонкая обёртка в виде класса, то он всё равно оптимизируется в итоге до обычного указателя.
Или думаешь например там список как-то криво реализован с дополнительными индерекциями?
Я могу конечно всё расписать в рукопашную (и сравнить ASM выхлоп, который скорей всего будет идентичным), но пока не вижу в смысла

lpd>Результаты изменились:
lpd>Последовательное сложение с индирекцией оказалось ровно в два раза медленне, чем с индирекцией. Это ожидаемо, т.к. выполняется две инструкции, вместо одной.

Ты опять меряешь в инструкциях
У тебя результат в примерно два раза медленней потому что тебе нужно перелопатить в два раз больший объём памяти, а алгоритм memory bandwidth bounded. Вместо одного массива, нужно выкачать два (причём одинакового размера). Замени массив четырёх-байтных индексов на массив восьми-байтных — и получишь другое соотношение, при том же количестве инструкций

lpd>Сложение со случайным доступом(и вечным cache-miss) оказалось еще в два раза медленнее, чем с последовательным. Это обозначает верхнюю границу эффективности кэша при доступе к данным, и для меня интересно.

Приведи конкретные цифры, в какой среде запускаешь, какие опции и т.п. Заполни map2 возрастающей последовательностью, а потом перетасуй std::random_shuffle — так чтобы у тебе гарантированно был обход всего массива.