Method FindUniqueHashes

tensorflow/core/grappler/graph_analyzer/sig_node.cc:274–327

}

void Signature::FindUniqueHashes(size_t* next_node_id_p) {
  // Start by sorting by the hash value.
  std::sort(nodes.begin() + *next_node_id_p, nodes.end(),
            SigNode::NodeOrderLess());

  // At each call, if no nodes have unique hashes, one node that has a
  // non-unique (shared) hash can be made unique by assigning a unique id.
  // This node gets picked predictably by taking the last node.
  // TODO(babkin): Technically, more than one node can be unshared,
  // as long as their last_hashed_nodes_ overlap only by the nodes that
  // already had the assigned ids before the current round. But it's not clear
  // yet, how often would this beneficial, because it looks like for many
  // subgraphs unsharing one node should be enough to untangle them. This
  // would need more measurement before implementing.
  bool found_unique = false;
  for (size_t n = *next_node_id_p; n < nodes.size(); ++n) {
    size_t cur_hash = nodes[n]->GetHighTopoHash();
    if (n + 1 < nodes.size() && nodes[n + 1]->GetHighTopoHash() == cur_hash) {
      // A sequence of nodes sharing the same hash. Skip over it.
      // TODO(babkin): check here for the arbitrary hash conflicts and resolve
      // them.
      for (++n;
           n + 1 < nodes.size() && nodes[n + 1]->GetHighTopoHash() == cur_hash;
           ++n) {
      }
      if (found_unique || n != nodes.size() - 1) {
        // Either some unique nodes have already been found, or this is
        // not the last chance, keep trying to find the unique nodes.
        continue;
      }
      // Here we're at the last node and haven't found any unique ones.
      // So fall through and make this last node unique.
    }

    found_unique = true;
    size_t id = (*next_node_id_p)++;
    nodes[n]->unique_rank_ = id;

    size_t last_hash = nodes[n]->GetHighTopoHash();
    CombineHash(last_hash, &sig_short);
    sig_full.push_back(last_hash);

    // Take the hash at 0 and mix the unique rank into it. After that it will
    // stay fixed.
    nodes[n]->topo_hash_.resize(1);
    nodes[n]->topo_hash_[0] = id + 1;  // Avoid the value of 0.

    nodes[n]->hash_is_final_ = true;
    nodes[n]->last_hashed_nodes_ = nodes[n]->node_mask_;
    if (n != id) {
      std::swap(nodes[id], nodes[n]);
    }
  }
}

void Signature::ComputeOneRound(size_t next_node_id) {
  // Reset the state of the nodes.