Я размышлял над этим вопросом некоторое время:
Можете ли вы построить более быструю фундаментальную структуру данных (т.е. связанный список, хеш-таблицу, набор, скипист, фильтр цветения, красно-черное дерево и т.д.) на многоядерной машине, воспользовавшись тем, что у вас есть больше, чем один процессор?
Я провел предварительные эксперименты с pthreads и обнаружил, что pthread_create() принимает порядок 30us, но простая вставка hash_map занимает гораздо меньше времени, чем на одном ядре. И, таким образом, мне становится трудно представить себе создание более быстрого hash_map < > , поскольку примитивы синхронизации и создание потоков настолько медленны. Я также могу представить обход дерева и балансировку параллельно, но опять же, примитивы синхронизации, казалось бы, делают время автономной работы длиннее, а не короче.
Мне по-прежнему кажется интуитивным, что "у меня больше процессора, и, следовательно, я должен быть в состоянии сделать это быстрее", но я не могу полностью обернуть голову доказательством или встречным доказательством для этого утверждения, Я довольно много экспериментировал на С++, но теперь я подозреваю, что другие языки могут предложить лучшие решения (erlang?) Для этой задачи. Мысли?
Детали EDIT: Я думаю, что есть несколько парадигм программирования/данных, которые часто используются, которые могут быть ускорены. Например, я часто нахожу код, который в основном выглядит так (где реальные данные были заменены на "rand()" )
static const int N = 1000000;
static const int M = 10000000; // 10x more lookups
hash_map<int, int> m;
// batch insert a bunch of interesting data
for (int i = 0; i < N; i++) m[rand()] = rand();
// Do some random access lookups.
for (int i = 0; i < M; i++) m[rand()]++;
Такая парадигма часто используется для таких вещей, как настройки имени и конфигурации, пакетная обработка и т.д. Коэффициент поиска/вставки 10x (или более) - это то, что делает традиционным hash_map < > ideal для такого рода операций,
Это можно легко разделить пополам, с фазой вставки и фазой поиска, и в параллельном мире может быть какая-то операция "флеш-очереди" между двумя половинами. Более сложной является чередованная вставка + версия для поиска:
hash_map<int, int> m;
for (int i = 0; i < N; i++) {
if (rand() % LOOKUP_RATIO == 0)
hash_map[rand()]++; // "lookup"
else
hash_map[rand()] = rand(); // "insert"
}
В этом случае вставка может быть асинхронной, если очередь вставки была сброшена перед каждым поиском, и если LOOKUP_RATIO достаточно большой (скажем, > 1000), то он становится очень похожим на приведенный выше пример партии, но с некоторой очередью, Хотя в очереди есть примитивы синхронизации.
Представьте себе секунду, следующий фрагмент:
hash_map<int,int> a;
hash_map<int,int> b;
for (int i = 0; i < N; i++) {
// the following 2 lines could be executed in parallel
a[rand()] = rand();
b[rand()] = rand();
}
И таким образом, поиск можно выполнить в "параллельном" путем:
int lookup(int value) {
// The following 2 lines could be executed in parallel:
v1 = a[value];
v2 = b[value];
if (v1) // pseudo code for "value existed in a"
return v1;
else
return v2;
}
