Быстрее фундаментальный datastructures на многоядерных машинах?
В вашей реализации есть три проблемы, на которые я хочу обратить внимание:
- Основная проблема в том, что ваша реализация в
Nextневерна. Поскольку обход по порядку равенleft->root->right, частьif (node.left != None):верна, но здесь:
elif (node.right != None):
node = node.right
while (node.left != None):
self.stack.append(node)
node = node.left
return node
вы должны сначала вернуть сам узел, прежде чем иметь дело с right child.
else:
if self.stack != []:
node = self.stack.pop()
node.left = None
return node
и вы должны не только pop, когда узел является листом, вы должны помещать каждый узел в стек и вставлять каждый Next.
- Вы не можете поместить
Nextв оба условия и блок, потому что он будет вызываться дважды.
while (self.Next(node) != None):
node = self.Next(node)
-
!= Noneвif (node.left != None):не требуется в python, вы можете просто использоватьif node.left:
, потому что Next имеет много проблем, поэтому Я должен переписать Next, вот версия, которую я отредактировал на основе вашего кода, и я прокомментировал в деталях:
class BTIterator:
def __init__(self, root):
self.stack = [] # Use a list as a stack by using pop() & append()
self.root = root
def Run(self):
# find the left most node, which means then first node
node = self.root
while node.left:
self.stack.append(node)
node = node.left
# start from left most node
while node:
print(node.val)
node = self.Next(node)
def Next(self, node):
# find right node, if it is none, it's ok, we will deal with it afterwards
node = node.right
# reach the end
if not self.stack and not node:
return None
# push left child iteratively
while node:
self.stack.append(node)
node = node.left
# this is next node we want
return self.stack.pop()
Надеюсь, что это поможет вам, и прокомментируйте, если у вас есть дополнительные вопросы. :)
7 ответов
Проблема состоит в том, что совместно используемые данные являются самостоятельно отравой параллельных вычислений. Идеально Вы хотите, чтобы каждое ядро работало над отдельными данными, иначе там будет наверху связан с синхронизацией. (Как связаться без общего состояния? Передачей сообщений.)
Кроме того, немного странно говорить об ускоряемых структурах данных. Я нахожу более естественным говорить об операциях на ускоряемой структуре данных, так как различные операции на различных структурах данных имеют различные характеристики. Существует ли конкретный тип доступа, который Вы хотите ускорить?
РЕДАКТИРОВАНИЕ, в ответ на дополнительные детали: Я предполагаю, что цель состоит в том, чтобы иметь единственную карту хеша, к которой можно получить доступ параллельно, и ее основы могли быть несколькими хеш-таблицами, но который будет прозрачно представлен пользователю этой структуры данных как единственная хеш-таблица. Естественно, мы были бы обеспокоены пребыванием в течение слишком большого количества времени, вращаясь на блокировках. Также на этом уровне, мы должны знать о проблемах непротиворечивости кэша. Таким образом, если ядра или процессоры имеют отдельные кэши, указывающие на те же данные, и каждый изменяет данные, то кэшированные данные на другом делаются недействительным. Если это неоднократно происходит, это может наложить огромные затраты, и параллелизм мог бы быть хуже, чем наличие вещей на одноядерном. Таким образом, я очень опасаюсь совместно используемых данных.
Мой инстинкт должен был бы иметь пул потоков, каждый из которых владеет различным разделом хеш-таблицы. Хеш сначала отобразился бы от ключа до раздела хеш-таблицы, и затем к смещению в том разделе. Обновление было бы передано как сообщение тому потоку, который владеет тем разделом хеш-таблицы. И тот путь, никто не пытается изменить то же самое сразу. Естественно, это легче на языках (Erlang), которые имеют функции асинхронного параллелизма передачи сообщений, чем в других.
Я имею дело с этим вопросом каждый день. Я нашел, что вещи как связанные списки действительно полезны, поскольку у Вас может быть каждый поток Вашего параллельного алгоритма, создают его собственный связанный список, затем просто шьют их вместе на ведущем устройстве, когда Вы сделаны. Почти никакие издержки, пока Ваши потоки действительно независимы
Если у Вас каждый есть массивы данных для использования, я нахожу, что почти всегда лучше выделить меньший массив, чтобы продолжить работать для каждого потока, затем объединить небольшие массивы назад в основной массив после завершения - на самом деле, если Вы находитесь в кластерной среде, использование "того же" массива не является даже возможностью!
При реализации алгоритма, который использует ассоциативные массивы (думайте Словарь.NET), Вы почти всегда собираетесь копировать некоторую работу где-нибудь между потоками. Старайтесь избегать их, если это возможно.
При кодировании для CUDA (GPU) среды Вы узнаете очень быстро, что целый мир может (нет, должен!) быть переделанным как массив перед работой :)
Я думал бы, что необходимо будет посмотреть на структуры данных и спросить, "Что в этом может быть сделано Асинхронно?"
И для большого количества структур данных, нет очень, если что-либо, что я вижу.
Но для некоторых более тайных или менее используемых структур, я держал пари, что существует. Я держал пари, что изменение баланса некоторых видов деревьев могло быть параллелизировано. Я держал пари, что пересекающие графики могли быть (хотя это может быть большим количеством алгоритма, чем структура данных). Я держал пари, что пересечение двунаправленного связанного списка (от каждого конца) могло быть.
Я не полагаю, что существует много параллелизма, который будет иметься в единственном поиске. Но если у Вас есть весь список объектов для поиска, это - другой случай.
Возьмите хеш-таблицу и возьмите большой список ключей для поиска в хеш-таблице или дереве. Это удвоило бы производительность для разделения списка ключей среди 2 центральных процессоров.
Или возьмите большой список объектов для вставки. Разделите хеш-таблицу на области на ЦП и разделите ключевой список. Затем каждый ЦП может наполнить объекты в свою собственную хеш-таблицу.
Это также относится к векторам, B+trees и двоичным деревьям, хотя я верю, хеш-таблицы могут быть созданы для необходимости в немного меньшем количестве блокировки для обновлений.
во-первых, я не думаю, что уместно выдержать сравнение pthread_create() время с hashmap операцией. лучше сравните с (ООН) времена блокировки, и в спорившем, и не спорил случаи.
тем не менее Вы правы, времена синхронизации являются узким местом и ухудшением, так как они должны перейти к шине/мосту/каналу меж-ЦП, безотносительно, в то время как большинство других datastructs пытается остаться в кэше (или даже в теневых регистрах).
существует два основных направления для принятий за решение этой проблемы:
лучше совместно использованные структуры: проверьте свободные от блокировок структуры и/или транзакционную память. обе попытки максимизировать доступность путем замены 'lock-modify-release' цикла 'try-check-commit/rollback'. в большинстве случаев проверка должна успешно выполниться, таким образом, откат не должен влиять на среднюю производительность. обычно проверка/фиксация сделана атомарно, таким образом, это дорого с точки зрения пропускной способности ЦП, но это намного меньше, чем традиционные блокировки.
меньше совместного использования: это - то, что подчеркивают erlang/haskell языки. при упрощении и недорогой для передачи маленьких сообщений коммуникация межпотока больше походит на вызовы функции с параметрами и меньше, чем общая память. это намного более масштабируемо, так как только два процесса должны синхронизироваться, и мог (в теории) каналы не-RAM использования с более низкими задержками.
править: я удивлен, что ни у кого нет мнения о свободных от блокировок структурах. проверьте этот (PDF) и этот (видео) о свободной от блокировок реализации хеш-таблицы в Java, который масштабирует (почти) линейно до 300 CPU
У Javier есть положительная сторона: при выполнении операций параллельно Вы уже получили потоки, просто необходимо дать им что-то, чтобы сделать.
Я думаю многое из того, к чему это сводится, стандартная проблема со средствами чтения и устройствами записи. Необходимо смочь иметь фактически неограниченное количество потоков с помощью хеш-таблицы, если все, что они делают, является чтениями или другими неразрушающими операциями. Однако, после того как один из них должен сделать запись, затем они должны захватить монопольную блокировку на целой хеш-таблице (если Вы не хешируете свой ключ внешне сначала, затем они могли в теории просто получать блокировку на блоке, к которому они хешируют, в зависимости от Вашего механизма разрешения коллизий).
Одна вещь рассмотреть имеет один (или маленький пул) потоков на структуру данных и доступа обработки как "сервис". Таким образом, вместо потока, ищущего что-то в карте хеша, это выпускает синхронный запрос к потоку, обслуживающему ту структуру данных. Это локализует операции блокировки (только потоки, обслуживающие запросы, должны знать о методе блокировки), но может выполнить запрос поставить узкое место в очередь.
Я думаю, поскольку кто-то еще сказал, что лучший способ использовать параллелизм через Ваши алгоритмы, не структуры данных.
Поместите все в очереди заданий. Это - ключ - и получает Вас ближе к масштабированию через несколько машин. Синхронизация является дорогой и только станет более дорогой позже (предположите иметь барьер памяти с 128 центральными процессорами).