C++ 性能问题

Question

我对 C++ 代码有点进退两难。它实际上是一个性能问题。我正在尝试遍历两个 hash_maps，这导致了很多缓慢。这是 HashMap 类代码。如果我遗漏了什么，请告诉我。

  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 是数据库查询，提取数据作为 vector 返回。

导致缓慢的遍历代码如下，

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 语句，它运行良好。您还可以在 HashMap 类中看到，我对大多数可能导致死锁的方法进行了互斥。请帮忙!

Answer 1

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