title: OrderedDict performance (compared to deque)
body: <p>I've been trying to performance optimize a BFS implementation in Python and my original implementation was using deque to store the queue of nodes to expand and a dict to store the same nodes so that I would have efficient lookup to see if it is already open.</p>
  
  <p>I attempted to optimize (simplicity and efficiency) by moving to an OrderedDict. However, this takes significantly more time. 400 sample searches done take 2 seconds with deque/dict and 3.5 seconds with just an OrderedDict.</p>
  
  <p>My question is, if OrderedDict does the same functionality as the two original data structures, should it not at least be similar in performance? Or am I missing something here? Code examples below.</p>
  
  <p>Using just an OrderedDict:</p>
  
  <pre><code>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
  </code></pre>
  
  <p>Using both a deque and a dictionary:</p>
  
  <pre><code>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
  </code></pre>