As already written several times in this thread, the right way to go is to use a specialized concurrent map. That being said, since the OP insists on using Qt containers, I can see two ways to hack around the limitations of QHash and improve the mutex-based solution.
Improvement 1: compute the hash outside the critical section
All retrieval operations (QHash::contains(), QHash::operator[], QHash::value()) must be performed in the critical section, which means that threads perform the (costly) hash computation in the critical section. This is suboptimal, because the hash computation does not touch the QHash's structure. A possible optimization consists in wrapping the QString key in an object that already knows its hash, and to construct this object outside the critical section. Proof of concept code (I haven't even tried to compile it):
class HashedString {
public:
uint hash() const {return m_hash;}
bool operator==(const HashedString &other) const {return m_s == other.m_s;}
private:
uint m_hash;
};
HashedString
::HashedString(QString s
) : m_s
(s
) { m_hash = qHash(s);
}
inline uint qHash(const HashedString &key) {
return key.hash(); // Super fast, because the hash is already known
}
QHash<HashedString, QMap<int, Data *> *> hashmap;
QMap<int, Data *> *Manager::getDataMap(const QString& key) {
HashedString hashedKey(key); // Compute the hash outside the critical section
QMap<int, Data *> *&val = hashmap[hashedKey]; // Notice the '&', which is required to be able to update the value
if (val == NULL)
// New value; compute it
val = newDataMap_private(key);
return val;
}
class HashedString {
public:
HashedString(QString s);
uint hash() const {return m_hash;}
bool operator==(const HashedString &other) const {return m_s == other.m_s;}
private:
QString m_s;
uint m_hash;
};
HashedString::HashedString(QString s) : m_s(s) {
m_hash = qHash(s);
}
inline uint qHash(const HashedString &key) {
return key.hash(); // Super fast, because the hash is already known
}
QHash<HashedString, QMap<int, Data *> *> hashmap;
QMutex mutex;
QMap<int, Data *> *Manager::getDataMap(const QString& key) {
HashedString hashedKey(key); // Compute the hash outside the critical section
QMutexLocker locker(&mutex);
QMap<int, Data *> *&val = hashmap[hashedKey]; // Notice the '&', which is required to be able to update the value
if (val == NULL)
// New value; compute it
val = newDataMap_private(key);
return val;
}
To copy to clipboard, switch view to plain text mode
Improvement 2: allow concurrent read accesses
If it is expected that many accesses will be made for the same key, then we can be optimistic and consider that most reads will return an existing binding. We can then use a QReadWriteLock instead of a mutex. Again, here is code I haven't tried to compile:
QMap<int, Data *> *Manager::getDataMap(const QString& key) {
HashedString hashedKey(key); // Compute the hash outside the critical section
lock.lockForRead(); // Let's be optimistic
QMap<int, Data *> *val = hashmap.value(hashedKey); // Read-only access to the QHash
if (val == NULL) {
// New value; relock the map for writing
lock.unlock();
// Some other thread might have time to insert a value for the same key here
lock.lockForWrite();
QMap<int, Data *> *&val2 = hashmap[hashedKey]; // Notice the '&', which is required to be able to update the value
if (val2 == NULL)
// No one has inserted the value
val2 = newDataMap_private(key);
val = val2;
}
lock.unlock();
return val;
}
QReadWriteLock lock;
QMap<int, Data *> *Manager::getDataMap(const QString& key) {
HashedString hashedKey(key); // Compute the hash outside the critical section
lock.lockForRead(); // Let's be optimistic
QMap<int, Data *> *val = hashmap.value(hashedKey); // Read-only access to the QHash
if (val == NULL) {
// New value; relock the map for writing
lock.unlock();
// Some other thread might have time to insert a value for the same key here
lock.lockForWrite();
QMap<int, Data *> *&val2 = hashmap[hashedKey]; // Notice the '&', which is required to be able to update the value
if (val2 == NULL)
// No one has inserted the value
val2 = newDataMap_private(key);
val = val2;
}
lock.unlock();
return val;
}
To copy to clipboard, switch view to plain text mode
QAtomicPointer lazy initilization
Reply With Quote
Originally Posted by QtCrawler
Bookmarks