CODEWITHSUNDEEP
c++multithreadingtemplatesstl
user2411693
user2411693

Reputation: 543

Thread-Safe Unordered Map that is being Continuously Iterated Over

I have collections of classes that can be accessed using the following template:

template <typename T> using RegistryMap = std::unordered_map <std::string, T *>;
template <typename T> class Registry {
  static RegistryMap<T> registry;

public:
  static T* get(const std::string& name) {
    auto it = registry.find(name);
    return it == registry.end() ? nullptr : it->second;
  }

  static const RegistryMap<T>& getAll() {
    return registry;
  }

 static bool add(const std::string &name, T *object) {
    T* &store = registry[name];
    if (store)
      return false;
    else {
      store = object;
      return true;
    }
  }

  static bool remove(const std::string &name) {
    auto it = registry.find(name);
    if (it == registry.end())
      return false
    else {
      registry.erase(it);
      return true;
    }
  }
};

Many classes in this registry define a method called run, which a thread thread will be calling a tight loop. While this is happening other threads may add/remove elements from the map using the methods above.

void workerThread() {
     examples = Registry<ExampleClass>::getAll();
     auto it = examples.begin();
     while (true) {
         if (it != examples.end())
             it++->second->run();
         else
             it = examples.begin();
     }
}

Is there a way to make this template threadsafe? I can add a static lock to the Registry template class and acquire it within the add or remove methods. But how do I handle the tight-looping thread? Especially in cases where the registry grows very large. Open to replacing the unordered_map and losing linear lookup time if necessary.

Upvotes: 1

Views: 182

Answers (2)

Amit
Amit

Reputation: 46331

A simple way would be to use a cyclic linked list. That doesn't require locking at all - Just have to make sure insertions and deletions are atomic operations on the list itself (simple to achieve).

If linear lookup is of importance, the solution can be extended by holding a map between a key (string...) and the link in the list for easy deletion or any other operation.

Upvotes: 1

Ami Tavory
Ami Tavory

Reputation: 76317

There are zillions of ways. Here is a very simple one, with little chances of an implementation bug.

In your internal implementations, keep not a single hash table, but p pairs of hash tables and locks (p being some prime).

To modify (that is insert or delete) an entry, first find its hash value, then modulo it to one of the p table, then lock and do the operation.

Meanwhile, the tight-loop thread will iterate over the p groups. For each group it will lock the lock, iterate over the group, and release it.

There is a tradeoff in p. A too small value of p (relative to the total number of objects) will result in high probability of locked contention. A too high value of p will result in a high lock-to-payload-op overhead for the tight-loop thread.

Depending on the situation, you might want also to consider read-write locks, with only the modifying operations taking write access.

Upvotes: 1

Related Questions