PDA

View Full Version : QAtomicPointer lazy initilization



QtCrawler
17th November 2015, 13:45
Hello,

I have a multithreaded application and I want to implement lazy initialization via QAtomicPointer. I read the docs and tried to implement it, but I need help.

My initilization without QAtomicPointer looks like the following snippet:



//member of class
QHash<QString, QMap<int,Data*>* > hash;

//...

//method
QMap<int,Data*>* Manager::getDataMap(const QString& key)
{
mutex.lock();

if(!hash.contains(key)){
getDataMap_private(key);//private method does lazy initialization
}

mutex.unlock();
return hash.value(key);
}


Can you show, or explain, how I could achieve the wanted behaviour by using QAtomicPointer? fetchAndStoreOrdered is the right method, isn't it?
Thank you!

anda_skoa
17th November 2015, 14:24
You mean having QAtomicPointer as the value in the hash and creating all possible entries in "hash" but with empty pointers?

Cheers,
_

QtCrawler
17th November 2015, 15:42
Thank you for your resp.
no, i mean not creating all values. i mean creating the qmap for the key. so the qmap has to be wrapped by qatomicpointer?

yeye_olive
17th November 2015, 16:20
QAtomicPointer lets you atomically change the value of a pointer. This is far different from what you want: atomically look up a QHash and, if the key is not present, allocate and add a new binding. There is no way to make such a complex operation atomic without a mutex. That is what they are for.

QtCrawler
17th November 2015, 16:54
ok, thank you for the conclusion.so qatomicpointer is not usable in my case. do you have a hint, how i could solve my problem? performance is very important, and several threads questions the map for the same key at the same time.

anda_skoa
17th November 2015, 16:54
no, i mean not creating all values. i mean creating the qmap for the key.

Yes, that is what I meant.
You would start with the hash fully "populated" but each entry would be an empty QAtomicPointer, no?

If you need to dynamically add to "hash", then you need to protect access to it with a mutex, as yeye_olive explained.

Cheers,
_

yeye_olive
17th November 2015, 18:47
ok, thank you for the conclusion.so qatomicpointer is not usable in my case. do you have a hint, how i could solve my problem? performance is very important, and several threads questions the map for the same key at the same time.
There are two separate issues here.

About the structure of the hash map: if the set of possible keys is small enough, I urge you to follow anda_skoa's suggestion and pre-populate the hash map so that the structure is immutable during concurrent accesses. If you cannot do that, you could look for libraries that specifically address this problem. See http://stackoverflow.com/questions/16118889/c-11-equivalent-of-java-util-concurrenthashmap for instance.

About allocating the values stored in the map: the values in your map are of type QMap<int,Data*>*. Adding a new binding is a long operation because you need to construct a new QMap<int,Data*>; that cannot be done atomically without locking. I suggest two possible solutions:

turn the QMap<int, Data*>* into an atomic pointer and attach a mutex to it (this means changing the value type of the hash map to a pair). You can then use double-checked locking (https://en.wikipedia.org/wiki/Double-checked_locking) when reading the pointer; your threads will only lock when the binding is added, not on subsequent accesses. Beware, turning the value type of the hash map into a pair means that allocating this pair is not atomic, which may prevent you from using concurrent hash map implementations (see "About the structure of the hash map" above).
turn the QMap<int, Data*>* into an atomic pointer and, when reading it as nullptr, construct a QMap<int, Data*> and use a test-and-set operation to try and set the pointer; if some other thread has already set it in the meantime, just abandon and destroy the QMap<int, Data*> you have just constructed. Use this solution if you can tolerate, in rare cases, that a QMap<int, Data*> be uselessly constructed and destroyed.


Oh, and QMap<int, Data*> itself does not sound too good as far as concurrent accesses are concerned. I hope you do not plan to concurrently update *those QMaps* too...

QtCrawler
19th November 2015, 15:31
Thank you for your explanation. Now I'm a bit more clued up on QAtomicPointer.


Oh, and QMap<int, Data*> itself does not sound too good as far as concurrent accesses are concerned. I hope you do not plan to concurrently update *those QMaps* too...

Can you explain why QMap<int,Data*> is not too good for this purpose? Because of performance?

Added after 53 minutes:

It's no option for me to pre-populate the QHash, cause the keys are not known at init-time.
I would like to implement a pure Qt - Solution, instead of using the 3rd part libs.

yeye_olive
20th November 2015, 10:22
Can you explain why QMap<int,Data*> is not too good for this purpose? Because of performance?
Because you have exactly the same problem with these QMaps as with the QHash: you must not allow concurrent accesses to a QMap if one of them mutates the structure.

Similarly, I do not know what Data is, but if you plan to allow concurrent accesses to a Data instance, you will probably need synchronization.


It's no option for me to pre-populate the QHash, cause the keys are not known at init-time.
I would like to implement a pure Qt - Solution, instead of using the 3rd part libs.
Then you have to lock the QHash with a mutex -- or a double-checked lock, which could improve performance -- on every access, whether it is a read or a write. If that it not enough, then I really suggest looking for specialized libraries. The problem you are trying to solve is notoriously hard.

QtCrawler
20th November 2015, 10:52
yeye_olive, thank you for your help.

Ok, if you say double-checked locking. What do you say about following pattern?
I think that would be sufficient, wouldn't it?
Or do you see week points?




//member of class
QHash<QString, QMap<int,Data*>* > hash;

//...

//method
QMap<int,Data*>* Manager::getDataMap(const QString& key)
{
QMap<int,Data*>* map = hash.value(key,0);

if(!map){
mutex.lock(); //only the first thread, which enters will create the QMap
map = hash.value(key,0);
if(!map){
getDataMap_private(key);//private method does lazy initialization
}
mutex.unlock();
}

return hash.value(key);

}

yeye_olive
20th November 2015, 12:38
Your code has undefined behavior. For instance, line 9 inspects the structure of the QHash without synchronization, which means that a thread may be doing that while another is modifying the QHash at line 15. Your code only protects multiple writers from each other, but it does not protect readers from writers.

By the way, the code snippet in your first post suffered from this problem too. Here is a fixed version:

QMap<int,Data*>* Manager::getDataMap(const QString& key)
{
mutex.lock();

if(!hash.contains(key)){
getDataMap_private(key);//private method does lazy initialization
}

QMap<int,Data*>* result = hash.value(key); // We must be protected by the mutex when calling QHash::value()
mutex.unlock();
return result;
}
However, you can rewrite that in a simpler way with a QMutexLocker:

QMap<int,Data*>* Manager::getDataMap(const QString& key)
{
QMutexLocker locker(&mutex);

if(!hash.contains(key)){
getDataMap_private(key);//private method does lazy initialization
}

return hash.value(key); // Notice how the QMutexLocker protects this read
}
Note that you can do even better by calling hash[key], which returns a reference to the value bound to key, adding it if not present (with a default NULL value). That way you only compute the hash once per access.

I was wrong in my previous post about double-checked locking. It only applies when initializing an atomic value, e.g. if the QHash were pre-populated with null QAtomicPointer<QMap<int,Data*>> (see the previous posts in the thread). I cannot think of a better solution than using a mutex.

wysota
20th November 2015, 17:28
yeye_olive, thank you for your help.

Ok, if you say double-checked locking. What do you say about following pattern?
I think that would be sufficient, wouldn't it?
Or do you see week points?




//member of class
QHash<QString, QMap<int,Data*>* > hash;

//...

//method
QMap<int,Data*>* Manager::getDataMap(const QString& key)
{
QMap<int,Data*>* map = hash.value(key,0);

if(!map){
mutex.lock(); //only the first thread, which enters will create the QMap
map = hash.value(key,0);
if(!map){
getDataMap_private(key);//private method does lazy initialization
}
mutex.unlock();
}

return hash.value(key);

}

Google for "lock free data structures". Maybe you can find something that fits your needs. The standard containers are not thread-safe and if you use mutexes, you will lose performance.

yeye_olive
21st November 2015, 10:10
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:
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;
}

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:


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;
}

QtCrawler
23rd November 2015, 17:55
Thank you for your help. I think this thread can be marked as solved.