Iterating shared QMap on multiple threads

BrianL

Hi,

I have multiple threads (3 in my test) that iterates the same QMap at the same time, I notice one of them gets stuck inside the for loop forever with the code below:

// entries data has been set before this and never changes
// so this grabs the reference, not copying
QMap<QString, QStringList> const& entries = GetEntries();

for (auto iter = entries.cbegin(); iter != entries.cend(); iter++)
{
    QStringList const& list = iter.value();
    // do work...
}

I have then checked the QMap interator example in https://doc.qt.io/qt-6/qmap-iterator.html, which initialize "end = map.cend()" so I changed the code to:

for (auto iter = entries.cbegin(), end = entries.cend(); iter != end; iter++)

which fixed the issue and never got stuck again.

What's the reason behind "iter != entries.cend()" not working?

Christian Ehrlicher

Don't access containers from two different threads without proper locking. I would guess you modify them somewhere.

JonB

@Christian-Ehrlicher
I read the OP's question earlier. So that I understand: if they genuinely do not "modify them somewhere", and the OP's original shown code is all there is and does reading only, would it then be OK if that reading code is called from multiple threads, potentially simultaneously?

Christian Ehrlicher

Read-only is safe as long as noone else is modifying it or accessing the code with non-const functions which the op is doing for sure somehwere - otherwise the problem would not arise.

BrianL

@Christian-Ehrlicher It definitely wasn't modified after initialization, but there might be some container quirk I wasn't aware about, I'll provided the code for GetEntries() as context:

Database.h

using Entries = QMap<QString, QStringList>;
using LanguageEntries = QMap<LanguageType, Entries>;
using EntryDatabase = QMap<QString, LanguageEntries>;

// this class is a singleton
class Database
{
private:
    static Database& instance();
    static EntryDatabase& GetEntryDatabase();

    static bool EnsureDatabase(QString const& path);
    static Entries const& GetEntries(QString const& path, LanguageType language);

    EntryDatabase m_entryDatabase;
}

Database.cpp

Database& Database::instance()
{
    static Database database;
    return database;
}

EntryDatabase &Database::GetEntryDatabase()
{
    return instance().m_entryDatabase;
}

bool Database::EnsureDatabase(const QString &path)
{
    // check if database already exist
    EntryDatabase& database = GetEntryDatabase();
    if (database.contains(path)) return true;

    // inserts into database, this is only run on GUI thread
    // BEFORE any thread get created that calls GetEntries()
    LanguageEntries languageEntries;
    for (...)
    {
        Entries entries;
        for (...)
        {
            entries.insert(it.key(), valueList);
        }
        languageEntries.insert(language, entries);
    }
    database.insert(path, languageEntries);
    return true;
}

const Entries &Database::GetEntries(const QString &path, LanguageType language)
{
    EntryDatabase const& database = GetEntryDatabase();
    if (database.contains(path))
    {
        LanguageEntries const& languageEntries = database[path];
        if (languageEntries.contains(language))
        {
            return GetEntryDatabase()[path][language];
        }
    }

    static Entries emptyEntries;
    return emptyEntries;
}

Christian Ehrlicher

@BrianL said in Iterating shared QMap on multiple threads:

LanguageEntries const& languageEntries = database[path];

Here you modify database when path is not yet in there. The same goes for GetEntryDatabase()[path][language].
So my your code shows what I already told you - you modify the container from different threads which results in undefined behavior.

BrianL

@Christian-Ehrlicher But I have made sure the path exist first before calling database[path] tho?

if (database.contains(path))
{
    LanguageEntries const& languageEntries = database[path];

Christian Ehrlicher

@BrianL said in Iterating shared QMap on multiple threads:

anguageEntries const& languageEntries = database[path];

And here database container gets modified when the path does not yet exists. So the container might grow.
Use a proper locking mechanism

BrianL

@Christian-Ehrlicher
I'm sorry if I'm missing something 😅, as I said I've checked

if (database.contains(path))

before calling

LanguageEntries const& languageEntries = database[path];

so path should already existed in database?

Christian Ehrlicher

@BrianL said in Iterating shared QMap on multiple threads:

so path should already existed in database?

You're right here but

https://doc.qt.io/qt-6/qmap.html#operator-5b-5d-1

operator[] const returns a value. So the reference you return goes out of scope.

BrianL

@Christian-Ehrlicher
ohh I see it now, I was trying to avoid using .value() because that returns a copy, but didn't notice operator[] const also returns a copy....

In that case is there no way to return a reference from QMap unless I made it return a non-const reference?

IgKh

@Christian-Ehrlicher @BrianL

The LanguageEntries const& languageEntries = database[path]; part is indeed problematic, but not because of what you think. database is a reference to a constant, so the const version of operator[] is called. However do notice that unlike the non-const version it returns a T, not a T&. Assigning it to a const l-value reference performs lifetime extension of the temporary that got returned until the end of the scope, but you are playing with fire doing it like that (e.g if you tried to return it). Due to the Copy-on-Write nature of Qt containers (which will lead me to the next point), they should generally be passed and assigned by value and not by reference (which might seem strange, but they are all actually shared-ownership reference wrappers anyway).

On the other hand GetEntryDatabase()[path][language] is exactly a mutating call, since it invokes the non-const operator[]. ANY non-const method on a CoW Qt container will first detach() the caller, even if it didn't end up modifying anything. The detach itself is thread-safe, as the copy-on-write semantics are implemented with atomic operations, but it does cause some iterator invalidation. The Qt documentation actually has a specific section on this - Implicit sharing iterator problem.

That specific case of detaching operation that doesn't actually modify the container is why it looks like if you fix the end iterator it works fine. It doesn't really. In such cases you should stick to external synchronization, or perhaps use the STL containers - they aren't thread safe as well, but their semantics are more obvious to C++ programmers.

BrianL

@IgKh said in Iterating shared QMap on multiple threads:

ANY non-const method on a CoW Qt container will first detach() the caller, even if it didn't end up modifying anything. The detach itself is thread-safe, as the copy-on-write semantics are implemented with atomic operations, but it does cause some iterator invalidation.

So even if I change my code to use T& operator[], it would still invalidate currently in-use iterator from other threads?

Entries &EntryDatabase::GetEntries(const QString &path, LanguageType language)
{
    EntryDatabase& database = GetDatabase();
    if (database.contains(path))
    {
        LanguageEntries& languageEntries = database[path];
        if (languageEntries.contains(language))
        {
            return languageEntries[language];
        }
    }

    static OCREntries emptyEntries;
    return emptyEntries;
}

IgKh

@BrianL said in Iterating shared QMap on multiple threads:

So even if I change my code to use T& operator[], it would still invalidate currently in-use iterator from other threads?

Basically yes. It is more nuanced than that, but discussing that would be just an academic exercise. As said, I think you are better served by std::vector and std::map for this use case.

BrianL

@IgKh Thanks for the answer! I have switch to using std::map now

JonB

@IgKh said in Iterating shared QMap on multiple threads:

Basically yes. It is more nuanced than that, but discussing that would be just an academic exercise. As said, I think you are better served by std::vector and std::map for this use case.

Without getting deep into a "nuanced" discussion, could you just summarise why these std ones are more suited here than the Qt ones, please? Is it because they do not get into references or temporaries or detaches or what? And the problem/difference would not arise/matter if multi-thread was not involved?

Christian Ehrlicher

@JonB said in Iterating shared QMap on multiple threads:

Is it because they do not get into references or temporaries or detaches or what?

std::map operator[] returns a reference whereas QMap operator[] const returns a temporary. That's the problem here.

sierdzio

I guess it's also an option to use QMap::find() to get a const iterator which will not be a copy of the data, unless I misremember stuff.

SimonSchroeder

@JonB said in Iterating shared QMap on multiple threads:

Without getting deep into a "nuanced" discussion, could you just summarise why these std ones are more suited here than the Qt ones, please?

I would say the most important point for this would be the "detaching" issue. Especially in the context of multithreading it is quite hard to figure out when detaches might happen. I guess the best way with QMap is to sprinkle qAsConst (or now even std::as_const) as often as possible. std::map just doesn't have this problem, so it is easier to get right with the STL compared to Qt.