Я долго размышлял над этим вопросом:
Можете ли вы построить более быструю фундаментальную структуру данных (например, связанный список, хэш-таблицу, набор, пропускающий список, фильтр Блума, красно-черное дерево и т. Д.) На многоядерном компьютере, воспользовавшись тем, что у вас есть более один процессор?
Я провел некоторые предварительные эксперименты с pthreads и обнаружил, что pthread_create () занимает порядка 30us, но простая вставка hash_map занимает гораздо меньше времени, чем на одном ядре. И поэтому мне стало трудно представить создание более быстрого hash_map <>, поскольку примитивы синхронизации и создание потоков выполняются очень медленно. Я также могу представить параллельный обход и балансировку деревьев, но опять-таки примитивы синхронизации, казалось бы, увеличивают время выполнения, а не сокращают его.
Мне все еще кажется интуитивно понятным, что «у меня больше ЦП, и, следовательно, я должен быть в состоянии сделать это быстрее», но я не могу полностью обернуть голову вокруг доказательства или контр-доказательства этого утверждения , Я довольно много экспериментировал с C ++, но теперь подозреваю, что другие языки могут предложить лучшие решения (erlang?) Для этой задачи. Мысли?
РЕДАКТИРОВАТЬ детали: я думаю, что есть несколько парадигм программирования / структуры данных, которые часто используются и которые могут быть ускорены. Например, я часто пишу код, который в основном выглядит следующим образом (где реальные данные были заменены на «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()]++;
Этот вид парадигмы часто используется для таких вещей, как настройки значений и данных конфигурации, пакетная обработка и т. Д. 10-кратное (или более) соотношение поиска / вставки - это то, что делает традиционный hash_map <> идеальным для операций такого типа. ,
Это может быть легко разделено пополам, с фазой вставки и фазой поиска, и в параллельном мире может быть некоторая операция «очистки очереди» между двумя половинами. Более сложным является чередующийся вариант вставки + поиска:
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;
}