I have a header file header.hpp in which is declared this function:

#ifndef COMMON_HPP
#define COMMON_HPP

#include <string>
#include <map>

extern std::string func( const std::map <std::string, std::string>& generic_map, const std::string& feat_string )

#endif

and that function is defined in a .cpp file:

#include "header.hpp"

#include <string>
#include <map>

std::string func( const std::map <std::string, std::string>& map_s, const std::string& str )
 {
  if( map_s.find( str ) == map_s.end() ) 
   {
    throw std::runtime_error( "Error!" );
   }
  return map_s.at( str );
 }

Benchmarking registered an execution time of 292 ns in 2684415 iterations. Do you know if there is any way to improve the function in order to make it faster?

CodePudding user response：

You're doing two lookups into the map to get the element you seek:

Here's an immediate improvement:

std::string func( const std::map <std::string, std::string>& map_s, const std::string& str )
 {
    auto itor = map_s.find(str);
    if (itor == map_s.end())
    {
      throw std::runtime_error( "Error!" );
    }
    return itor->second;
 }

The other improvement you can make is to use a std::unordered_map instead of std::map. If you don't need to enumerate keys in the map in any sorted or consistent order, you should use unordered_map, which is O(1) for insertion and lookup. The ordered map will likely have O(lg N) runtime for insertion and lookup. (i.e. hash table vs binary tree implementations for the collections). std::unordered_map and std::map have near identical interfaces, so it's an easy drop-in replacement.

CodePudding user response：

First, it returns std::string instead of const std::string&, which is slow (involves a copy).

Also, exceptions in current compilers are very expensive. A possible way around them is to return a const std::string* and return nullptr in case element is not found (also removed double lookup):

const std::string* func( const std::map <std::string, std::string>& map_s, const std::string& str )
 {
  auto it = map_s.find( str );
  if( it == map_s.end() ) 
   {
    return nullptr;
   }
  return &(it->second);
 }

An advanced technique is continuation passing style, which can further optimize your code (and save you a branching). In this case, instead of returning something, you pass what should be done with the result:

template<typename Found, typename NotFound>
void func( const std::map <std::string, std::string>& map_s, const std::string& str Found found, NotFound notFound)
{
  auto it = map_s.find( str );
  if( it == map_s.end() ) 
  {
    return notFound();
  }
  return found(it->second);
}

// usage:
std::map<std::string, std::string> m;
std::string s;
func(m, s, [&](const std::string& elem) {
  /* found - do something with elem */
}, [&]() {
  /* not found - error handler */
});

This is like if you had your own control structures. Of course, you could make the return type different from void (in case you'd like to 'tunnel' the result of found(elem) and notFound()). If you'd like, you can share e.g. the error handler among multiple calls to the function (in which case, you store it in a variable, like const auto onNotFound = [&]() { /* ... */ };). Of course, when you're optimizing, you might limit the capture of the lambda to what's necessary.

CodePudding user response：

Given how small the code is, there is really not many changes you can make to it, but there are a few:

• use the iterator that map::find() returns, you don't need to call map::at() afterwards. You are actually performing the same search 2 times, when you really want to perform it only 1 time.

• return a reference to the found value, to avoid making a copy of it (map::at() returns a reference anyway). The exception you are throwing will ensure the returned reference is never invalid.

• If you don't need the map to be sorted, use std::unordered_map instead of std::map.

Try this:

const std::string& func( const std::map <std::string, std::string>& map_s, const std::string& str )
{
    auto iter = map_s.find( str );
    if (iter == map_s.end() ) 
        throw std::runtime_error( "Error!" );
    return iter->second;
}

That being said, if you don't mind what kind of error message is thrown, you can replace map::find() with map::at(), since map::at() throws its own std::out_of_range exception if the key is not found (that is the whole purpose of map::at() vs map::operator[]), eg:

const std::string& func( const std::map <std::string, std::string>& map_s, const std::string& str )
{
  return map_s.at( str );
}