QCache maxcost not respected

[maitai]

Hello all,

I am using version 4.7.1

I am accessing a QCache in threads with a QFuture. Because I didn't want to slow down cache accesses with mutexes, I did the following:

1)I set maxCost to a really big value which I will never reach
2)I fill the cache with missing objects (kind of polygons in my case) in the main thread
3)I launch the threads, which will use polyCache->object(key) to do their job. Because of step 2 I am 100% sure that all needed polys will be in the QCache. Note that threads do not modify the polys in any way, they just "read" them.
4)When QFuture is finished, I set maxCost to 16384, reducing the cache size but keeping the last accessed polys, ready for the next call.

It works well, except that after a lot of calls of this sequence, the QCache is not cleaned properly, and I end up with much more polys stored in the QCache than 16384...

The documentation says:
int QCache::totalCost() const
Returns the total cost of the object in the cache.
This value is normally below maxCost(), but QCache makes an exception for QT's implicitely shared classes. If a cached object shares its internal data with another instance, QCache may keep the object lying around, possibly contributing to making totalCost() greater than maxCost().

The objects stored in the cache are just a struct, containing some strings, ints and QPolygonFs... I doubt this can be considered as a "Qt's implicitely shared class". Checking the code of Qt I can see that objects are not removed from the cache if qIsDetached returns false, but what exactly qIsDetached is checking is not exactly clear to me...

Also note that if I run this program on a mono-cpu machine, then this problem never occurs. I suspect the problem occurs whenever a QCache:: object() is accessed simultaneously by several threads, but I cannot prove this easily.

Any suggestion on what is not correct in this implementation or what I should do to correctly clean the QCache is welcomed

Thanks

[wysota]

QPolygonF is definitely implicitly shared, so is QString.

[oxygen77]

to complete maitai post, the data put in QCache is:
112 struct tilePoly
113 {
114 gpc_polygon p1, p2, p3, p4, p5;
115 };

and

67 struct gpc_polygon /* Polygon set structure */
68 {
69 int num_contours; /* Number of contours in polygon */
70 QList<int> hole; /* Hole / external contour flags */
71 QList<gpc_vertex_list> contour; /* Contour array */
72 } ;

so is it possible that gcc detects that tilePoly contains a properties that is a struct that itself contains QList ?

QCache index is done using QString: QCache<QString,tilePoly> myCache;

[wysota]

How are you inserting data into the cache? Are you leaving the default cost of "1"? If so, then the cost is expressed in terms of items and not real memory usage. I'd say you are abusing QCache but if you insist on using it this way, at least protect it with a mutex. This class is not safe to use by more than one thread.

[maitai]

We are inserting with default value 1 and we do realize that this is meaning 1 item and not 1 * something_linked_to memory. We also realize that this (ie multithread access) is somehow abusing QCache.

Inserts are never made from threads but before in the main process. Accesses from threads are always "read-only". We have already decided to build our own cache mechanism since obviously QCache cannot be used in this way... but we would like to understand exactly why qt considers that in some cases objects are considered "not qDetached" and therefore not clearable from QCache...

[wysota]

Inserts are never made from threads but before in the main process. Accesses from threads are always "read-only".

Protect the cache with a mutex and see if it solves the problem. Then you'll know that the problem is caused by multithreading. Besides, it doesn't make much sense to fill the cache with all objects. If you operate on all objects, you can bypass the cache completely. There is no benefit from using the cache for this purpose. You waste more time by inserting items into the cache than you gain by having them there after the iteration of all items.

[maitai]

Inserts are made from the main thread to avoid inserting from threads. But in the main thread, of course most often inserts are not even necessary because all objects (polys) are already in the cache. Using this mechanism does save a lot of time.

Using a mutex "around" QCache->object(key) solves the problem of cleaning, the question is why? I don't want to use a mutex because most often it is useless, since this particular object is not already use by another thread... A mutex would lock QCache accesses even if not necessary...

We will build our own cache mechanism anyway to turn around this, but we wanted to raise your attention about the fact that even without inserts, QCache seems to be not-thread-safe (or we missed something )

[wysota]

Inserts are made from the main thread to avoid inserting from threads. But in the main thread, of course most often inserts are not even necessary because all objects (polys) are already in the cache. Using this mechanism does save a lot of time.

Does it? If all objects are in cache, then you don't have a cache but a hash with additional time penalty resulting from having to update the item removal order.

Using a mutex "around" QCache->object(key) solves the problem of cleaning, the question is why? I don't want to use a mutex because most often it is useless, since this particular object is not already use by another thread... A mutex would lock QCache accesses even if not necessary...

Qt has a smart implementation for mutexes. It doesn't really use a mutex unless a second thread tries to access the critical section protected by it. So if you use only one thread, the overhead is minimal.

We will build our own cache mechanism anyway to turn around this, but we wanted to raise your attention about the fact that even without inserts, QCache seems to be not-tread-safe (or we missed something )

And who said QCache was thread-safe? That was only your false assumption. The class is reentrant but not thread-safe, just look at the docs.

[maitai]

Does it? If all objects are in cache, then you don't have a cache but a hash with additional time penalty resulting from having to update the item removal order.

In fact it does because all objects are in cache "during-threading", but caching is efficient before that, because we don't regenerate polys that are already cached, we just make sure all are cached before threading, and pratically most of them are already cached (after a while)

Qt has a smart implementation for mutexes. It doesn't really use a mutex unless a second thread tries to access the critical section protected by it. So if you use only one thread, the overhead is minimal.

If I put a mutex on each and every call to QCache:: object(key) it will lock the piece of code even if the key is different... That's my understanding but I am ready (i.e. very happy) to hear the opposite...

And who said QCache was thread-safe? That was only your false assumption. The class is reentrant but not thread-safe, just look at the docs.

We wrongly assumed that concerned "inserts", not "reads". That is not the case, ok.

[wysota]

In fact it does because all objects are in cache "during-threading", but caching is efficient before that, because we don't regenerate polys that are already cached, we just make sure all are cached before threading, and pratically most of them are already cached (after a while)

And how does it differ from using say... QHash?

If I put a mutex on each and every call to QCache:: object(key) it will lock the piece of code even if the key is different...

Only if two threads access the method at the same time. Otherwise the overhead will be equal to bumping up an int and checking its value (which is one machine instruction most of the time).

We wrongly assumed that concerned "inserts", not "reads". That is not the case, ok.

Maybe your code accesses some non-const method somewhere? Or QCache modifies some data in one of its const methods (though I see no proof of that in the source code).

[maitai]

Maybe your code accesses some non-const method somewhere? Or QCache modifies some data in one of its const methods (though I see no proof of that in the source code).

Our code uses only object(key) while running in threads, nothing else (no insert, no delete, no set). My humble opinion is that when an object is returned through object() QCache moves this object to the begining of the pile (which seems to be an internal QHash), and that if another thread tries to access the same object(key) "while" QCache is moving this to the top of the pile... something goes wrong.