message: Change node name index in InstantiateFunction from an unordered map to an ordered map. Use ordering to improve control edge instantiation algorithm from O(num control edges * num nodes) algorithm to ~O(num control edges * log(num nodes)).
diff: @@ -15,6 +15,7 @@ limitations under the License.
  #include "tensorflow/core/framework/function.h"
  +#include <map>
  #include <unordered_map>
  #include <utility>
  #include <vector>
  @@ -271,12 +272,17 @@ class FunctionInstantiationHelper {
  int nid = -1;
  const string node_name = input.substr(1);
  const string node_colon = node_name + ":";
  - for (const auto& p : index_) {
  - if (p.first == node_name ||
  - tensorflow::StringPiece(p.first).starts_with(node_colon)) {
  - nid = p.second.nid;
  + const string node_colon_bound = node_name + ";";
  + // index_ is a map sorted lexicographically, so the key we are looking for
  + // must lie in the range [node_name, node_colon_bound).
  + auto it = index_.lower_bound(node_name);
  + while (it != index_.end() && it->first <= node_colon_bound) {
  + if (it->first == node_name ||
  + tensorflow::StringPiece(it->first).starts_with(node_colon)) {
  + nid = it->second.nid;
  break;
  }
  + ++it;
  }
  if (nid == -1) {
  return errors::InvalidArgument("input[", i, "] == '", input,
  @@ -421,7 +427,7 @@ class FunctionInstantiationHelper {
  GetFunctionSignature get_function_;
  InstantiationResult& result_;
  // A small index for all names that can be used as a node's input arguments.
  - std::unordered_map<string, NameInfoItem> index_;
  + std::map<string, NameInfoItem> index_;
  // This contains information about a node in the new graph including the node
  // names and input nodes' indexes.
  struct NodeInfo {
  