C++性能问题

Question

我在使用 C++ 代码时遇到了一些困境。这实际上是一个性能问题。我试图遍历两个 hash_map，这导致速度很慢。这是哈希映射类代码。如果我遗漏了什么，请告诉我。

  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 语句，它会正常运行。您还可以在哈希映射类中看到，我对大多数可能导致死锁的方法进行了互斥。请帮忙！

Answer 1

方法 ++() 和 --() 真的需要受到保护吗？两个线程什么时候使用同一个迭代器？您需要保护哈希图，而不是迭代器。锁定和解锁是昂贵的操作。删除它肯定会提高性能。

Answer 2

任何人都可以看到可以采取任何措施来改进此代码吗？

您的线程/锁定模型很幼稚。我认为至少有四个问题。

• 递归锁；
• 锁定每个成员函数；
• 某些功能缺少锁定；
• 使用函数局部静态变量的方式不是线程安全的。

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

然而，锁定每个成员函数也不是最理想的。许多使用容器的操作必须在（语义上）原子操作期间多次锁定/解锁容器。这也可能是不正确的。虽然容器上的各个操作是互斥的，但容器的状态可能会以代码不期望的方式在这些操作之间发生变化。除非您知道/可以证明您的情况并非如此，否则对整个容器使用外部锁定。

另外，至少 size() 缺少锁。

Answer 3

您有哈希映射，但您想遍历所有元素，对吧？

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

这样，当用户想要遍历所有元素时，您只需提供遍历此容器的迭代器即可。

它的成本（低），但它以简单的方式使事情变得更快。

Answer 4

从不同的角度来看：我不知道你在哪里存储员工 ID，但在填充你的 RosterTable 之前，你是否可以在数据库上完成所有这些工作？