C++性能问题

Question

我在使用C++代码时有点进退两难。这实际上是一个性能问题。我正在尝试遍历两个hash_maps，这会导致很多速度变慢。下面是散列映射类代码。如果我遗漏了什么，请告诉我。

  template<class Handle, class Object, class HashFunc, vector<Object *> (*initFunc)()>
  class ObjMapping: public BaseCache
  {

  public:
    typedef ObjMapping<Handle, Object, HashFunc, initFunc> ObjMappingType;
    typedef InvalidObjectException<Handle> InvalidHandle;
    typedef typename ReferenceCounted<Object>::ObjRef ObjRef;

  protected:
    typedef dense_hash_map<Handle, pair<int, ObjRef> , HashFunc> ObjHashMap;
    typedef typename dense_hash_map<Handle, pair<int, ObjRef> , HashFunc>::iterator ObjHashMapIterator;
    typedef typename dense_hash_map<Handle, pair<int, ObjRef> , HashFunc>::const_iterator ObjHashMapConstIterator;

  public:

    class iterator
    {

    public:
      typedef Object &reference;
      typedef ObjRef pointer;

      iterator(ObjMappingType &container, ObjHashMapIterator start) :
        base(start), container_(&container)
      {
        incIterCount_();
      }

      iterator(const iterator &rhs) :
        base(rhs.base), container_(rhs.container_)
      {
        Monitor crit(container_->getIterMutex());
        incIterCount_();
      }

      void operator =(const iterator &rhs)
      {
        if (this != &rhs)
        {
          Monitor crit(container_->getIterMutex());
          decIterCount_();
          base = rhs.base;
          container_ = rhs.container_;
          incIterCount_();
        }
      }

      ~iterator()
      {
        Monitor crit(container_->getIterMutex());
        decIterCount_();
      }

      reference operator *() const
      {
        return *base->second.second;
      }
      pointer operator ->() const
      {
        return base->second.second;
      }

      iterator operator ++()
      {
        {
          Monitor crit(container_->getIterMutex());
          decIterCount_();
          ++base;
          incIterCount_();
        }
        return *this;
      }
      iterator operator ++(int)
      {
        iterator result = *this;
        {
          Monitor crit(container_->getIterMutex());
          decIterCount_();
          ++base;
          incIterCount_();
        }
        return result;
      }
      iterator operator --()
      {
        {
          Monitor crit(container_->getIterMutex());
          decIterCount_();
          --base;
          incIterCount_();
        }
        return *this;
      }
      iterator operator --(int)
      {
        iterator result = *this;
        {
          Monitor crit(container_->getIterMutex());
          decIterCount_();
          --base;
          incIterCount_();
        }
        return result;
      }

      bool operator ==(const iterator &i) const
      {
        return (base == i.base);
      }
      bool operator !=(const iterator &i) const
      {
        //return !(*this == i);
        return (base != i.base);
      }

    private:
      void incIterCount_()
      {
        if (!container_->endIterator(base))
        {
          ++base->second.first;
        }
      }
      void decIterCount_()
      {
        if (!container_->endIterator(base) && --base->second.first == 0)
        {
          container_->wake();
        }
      }

      ObjHashMapIterator base;
      ObjMappingType *container_;
    };

    ~ObjMapping()
    {
    }

    bool validObj(const Handle &id) const
    {
      Monitor crit(mutex);
      MethodTracker track ("ObjMapping::validObj");
      return objs.find(id) != objs.end();
    }

    ObjRef getObj(const Handle &id) const
    {
      Monitor crit(mutex);
      MethodTracker track ("ObjMapping::getObj");
      if (!validObj(id))
      {
        throw InvalidHandle(id);
      }
      return objs.find(id)->second.second;
    }

    void addObj(auto_ptr<Object> obj)
    {
      Monitor crit(mutex);
      Handle h(obj->getID());

      // Stop iterator changes while container is being altered
      Monitor iter(iterMutex_);
      objs.insert(typename ObjHashMap::value_type(h, make_pair(0, ReferenceCounted<Object>::alloc(
          obj))));
    }

    // Will remove the given object from the cache
    // NOTE: This is a dangerous operation: it will block until there are no references to the
    // object other than the one in the cache, which opens many possibilities for deadlocks, 
    // and means that it is not safe to store references from the cache outside it.
    void removeObj(const Handle &id)
    {
      Monitor crit(mutex);
      ObjHashMapIterator entry = objs.find(id);
      if (entry != objs.end())
      {
        // If there are other references to the object wait for them to be released
        entry->second.second.ensureUnique();

        // Wait until no further iterators for this entry
        Monitor crit(iterMutex_);
        while (entry->second.first != 0)
        {
          iterBlock_.wait(iterMutex_);
        }

        objs.erase(entry);
      }
    }

    // Will remove the given object from the cache if the cache contains the only reference to it,
    // returns true only if the object is not in the cache
    bool releaseObj(const Handle &id)
    {
      Monitor crit(mutex);
      ObjHashMapIterator entry = objs.find(id);
      if (entry != objs.end())
      {
        Monitor crit(iterMutex_);
        if (entry->second.first != 0 || entry->second.second.references() != 1)
        {
          return false;
        }

        objs.erase(entry);
      }
      return true;
    }

    size_t size() const
    {
      return objs.size();
    }

    iterator begin()
    {
      Monitor crit(iterMutex_);
      MethodTracker track ("ObjMapping::begin");
      return iterator(*this, objs.begin());
    }
    iterator end()
    {
      Monitor crit(iterMutex_);
      MethodTracker track ("ObjMapping::end");
      return iterator(*this, objs.end());
    }

    void wake()
    {
      iterBlock_.broadcast();
    }

    Mutex &getIterMutex()
    {
      return iterMutex_;
    }

    void dump(ostream &out)
    {
      Monitor crit(mutex);
      out << "Mapping cache contains " << objs.size() << " base objects" << endl;
    }

    // Will reload *all* objects from the cache
    // NOTE: This is a *VERY* dangerous operation: see comments above for removeObj
    void reload()
    {
      Monitor crit(mutex);

      // Delete all objects in cache
      ObjHashMapIterator i = objs.begin();
      while (i != objs.end())
      {
        // If there are other references to the object wait for them to be released
        i->second.second.ensureUnique();

        // Wait until no further iterators for this entry
        Monitor crit(iterMutex_);
        while (i->second.first != 0)
        {
          iterBlock_.wait(iterMutex_);
        }

        objs.erase(i++);
      }

      // Reload all objects from DB
      vector<Object *> base = initFunc();
      for (typename vector<Object *>::const_iterator i = base.begin(); i != base.end(); ++i)
      {
        Handle id = (*i)->getID();
        objs.insert(make_pair(id, make_pair(0, ReferenceCounted<Object>::alloc(
            auto_ptr<Object> (*i)))));
      }
    }

    static ObjMapping<Handle, Object, HashFunc, initFunc> &getTable()
    {
      static bool created = false;
      static Mutex createMutex;
      MethodTracker track ("ObjMapping::getTable");
      static auto_ptr<ObjMapping<Handle, Object, HashFunc, initFunc> > theTable;
      if (!created)
      {
        Monitor crit(createMutex);
        if (!created)
        {
          theTable.reset(new ObjMapping<Handle, Object, HashFunc, initFunc> );
          created = true;
        }
      }
      return *theTable;
    }

  protected:
    friend class iterator;
    bool endIterator(ObjHashMapIterator &it)
    {
      return it == objs.end();
    }

    ObjMapping() :
      mutex(Mutex::Recursive)
    {
      vector<Object *> base = initFunc();
      objs.set_empty_key(0);
      for (typename vector<Object *>::const_iterator i = base.begin(); i != base.end(); ++i)
      {
        Handle id = (*i)->getID();
        objs.insert(make_pair(id, make_pair(0, ReferenceCounted<Object>::alloc(
            auto_ptr<Object> (*i)))));
      }
    }

  private:
    ObjMapping(const ObjMapping &);
    const ObjMapping &operator =(const ObjMapping &);

    mutable Mutex mutex;
    ObjHashMap objs;
    Mutex iterMutex_;
    Condition iterBlock_;
  };

我已经创建了两个这样的对象，

typedef ObjMapping<RosterID, Roster, __gnu_cxx::hash<RosterID>, Roster::readAllRosters> RosterTable;
typedef ObjMapping<RosterHeaderID, RosterHeader, __gnu_cxx::hash<RosterID>, RosterHeader::readAllRosterHeaders> RosterHeaderTable;

两个方法Roster::readAllRosters & RosterHeader::readAllRosterHeaders是数据库查询，它将数据返回提取为一个向量。

下面给出了导致缓慢的遍历代码，

for (RosterTable::iterator it = RosterTable::getTable().begin(); it != RosterTable::getTable().end(); ++it) {
  if (RosterHeaderTable::getTable().getObj( it->getHeader() )->getEmployee() == getID())
  {
    // Adding a roster to a map.
  }
}

有没有人知道可以做些什么来改进这段代码？还要注意，如果我在遍历代码中注释掉if语句，它运行得很好。您还可以在hash map类中看到，我已经互斥了大多数可能导致死锁的方法。请帮帮我！

Answer 1

有人能看到可以做些什么来改进这段代码吗？

你的线程/锁定模型太天真了。我至少可以看到四个问题。

在某些函数中锁定每个成员中的递归locking;

• locking；

• 使用函数局部静态变量的方式不是线程安全的。

递归锁定不是最优的。它的成本更高，既因为它更复杂，也因为您在一个线程中多次获得独占访问权限。通过将实现划分为公共/前端和内部/后端函数，可以避免递归锁定。前端函数执行锁定，并调用不包含任何锁定的后端函数，并且从不调用任何前端函数。

然而，锁定每个成员函数仍然是次优的。许多使用容器的操作必须在(语义上)原子操作期间多次锁定/解锁容器。它也可能是不正确的。虽然容器上的各个操作是独占的，但容器的状态可以在这些操作之间以代码不期望的方式进行更改。除非您知道/可以证明情况并非如此，否则会对整个容器使用外部锁定。

此外，至少size()缺少一个锁。

Answer 2

++()和--()方法真的需要保护吗？什么时候两个线程会使用相同的迭代器？您需要保护散列映射，而不是迭代器。锁定和解锁是开销很大的操作。删除它肯定会提高性能。

Answer 3

您有散列映射，但您希望遍历所有元素，对吗？

那么为什么不添加另一个以线性方式保存数据的容器呢？就像向量或列表？

这样，您只需提供迭代器，当用户希望遍历所有元素时，这些迭代器就会遍历该容器。

它有(低)成本，但它以一种简单的方式使事情变得更快。