Производительность OrderedDict (по сравнению с deque)

Я пытался оптимизировать производительность реализации BFS на Python, и моя первоначальная реализация использовала deque для хранения очереди расширяемых узлов и dict для хранения тех же узлов, чтобы у меня был эффективный поиск чтобы увидеть, открыт ли он уже.

Я попытался оптимизировать (простоту и эффективность), перейдя на OrderedDict. Однако на это уходит значительно больше времени. Выполнение 400 примеров поиска занимает 2 секунды с deque / dict и 3,5 секунды с помощью только OrderedDict.

У меня вопрос: если OrderedDict выполняет те же функции, что и две исходные структуры данных, не должно ли оно хотя бы быть схожим по производительности? Или мне что-то здесь не хватает? Примеры кода ниже.

Использование только OrderedDict:

open_nodes = OrderedDict()
closed_nodes = {}
current = Node(start_position, None, 0)
open_nodes[current.position] = current

while open_nodes:
  current = open_nodes.popitem(False)[1]
  closed_nodes[current.position] = (current)

  if goal(current.position):
    return trace_path(current, open_nodes, closed_nodes)

  # Nodes bordering current
  for neighbor in self.environment.neighbors[current.position]:
    new_node = Node(neighbor, current, current.depth + 1)
    open_nodes[new_node.position] = new_node

Использование двухсторонней очереди и словаря:

open_queue = deque()
open_nodes = {}
closed_nodes = {}
current = Node(start_position, None, 0)
open_queue.append(current)
open_nodes[current.position] = current

while open_queue:
  current = open_queue.popleft()
  del open_nodes[current.position]
  closed_nodes[current.position] = (current)

  if goal_function(current.position):
    return trace_path(current, open_nodes, closed_nodes)

  # Nodes bordering current
  for neighbor in self.environment.neighbors[current.position]:
    new_node = Node(neighbor, current, current.depth + 1)
    open_queue.append(new_node)
    open_nodes[new_node.position] = new_node