[Question] Reader/Writer Locks

[nicfb]

I am working on a concurrent implementation of your C++ Pattern Matching Library. Currently I am working with the vtblmap3st file using reader/writer locks to see if this out performs a single lock. I have a question whether or not locking/unlocking the shared and non-shared locks where the reference to the pointer ce is returned is safe, or this could corrupt the data in the cache.

[solodon4]

Hi Nicholas,

I am not sure I understand your question properly, can you elaborate a bit please?

Here is some general information. cache_descriptor contains cache[] array at the end of itself, whose size depends on the number of totally allocated items. Items themselves (of type stored_type) are allocated in chunks (arrays) and once allocated they are never reallocated or deleted until the program is terminated. cache_descriptor itself gets reallocated when the optimal configuration for the cache needs to be recomputed, but it then inherits all the stored_type entries allocated by the previous cache_descriptors. The idea was also that in lock-free implementation vtbl_map<T>::update would prepare a new cache_descriptor and then would CAS it with an existing one.

cache_descriptor::cache both contains pointers to all allocated stored_type entries and is used to fast access them. Given a certain vtbl pointer, we compute where it most likely would be in the cache array and try to access it. We then compare the vtbl stored by that pointer and if they match, we get a cache hit and return immediately the pointer. If they don't match, we need to find which index of the array contains the actual vtbl pointer and swap it with the one we tried to access assuming we'd be accessing it again. The main invariant here is that all the allocated stored_type entries must be referenced in some cache entries (so that we don't leak any) and each of them should be there only once.

I don't think you need to worry about locking anything in stored_type itself. That information is updated in the same way always, so it doesn't matter which thread does the update. What you need to worry is the invariant I mentioned above. Basically to the outside world the swap cache[i] and cache[j] needs to look atomically so that they either see the old stored_type or the new one.

Does that clarify anything? Please ask me more questions so that I can guide you further.

Thank you!

[solodon4]

P.S. stored_type is initially allocated with its vtbl==0 indicating it is not occupied by anything. If we couldn't find a given vtbl pointer anywhere in the cache, we look for such a free entry and start using it for a given vtbl. Once we've started using that stored_type for a given vtbl pointer, we would never change it to be used for other vtbl pointers. What you need to make sure in your implementation is that no 2 threads grab a single free stored_type entry for 2 different vtbl pointers. Only one of them can succeed, in which case the other thread must look for another free entry. What my previous comment meant was that you need not worry about safeguarding access to the T part of stored_type. The caller would if he has to.

[nicfb]

Yes, that information helped a lot. Thank you! As for the lock free portion, I was thinking about making the caches thread local. What is your opinion on this idea? Do you think this would work well or be too cumbersome and slow down the runtime?

[solodon4]

I thought about that initially, but there is too much duplication of information to avoid: now if I use a Match statement inside a thread procedure and create 1000 threads, i'll have 1000 of these vtbl_maps for the same Match statement while 1 is perfectly sufficient. In reality though, the compiler implementation of Match statement can reuse the same vtbl_map for multiple Match statements, when they satisfy certain conditions.

The size of the map is proportional to the number of dynamic types coming through the Match statements (more precisely it is proportional to the number of different sub-objects of object's static type in all the dynamic types) and this number for typical cases of a compiler application were in hundreds. You can certainly do it just to try timing it, but that is not the ultimate goal because these data-structures are quite heavy and never shrink.

The ultimate goal is to have vtbl_map lock-free. This effort will be rewarded by the fact that eventually this same data-structure would be used by the compiler to implement a Match statement on the level of the language.

[nicfb]

With my reader/writer lock implementation of the single threaded vtblmap class, I am having some trouble building it. I can compile it just fine after I add the -pthread and -std=c++17 flags in the Makefile, but when I made a fork of the repository I could not build it without commenting out the lines dealing with the shared_locks. I do not have much experience with CMake, do you have any suggestions so that I can build it without having to comment out those lines?

[solodon4]

I don't know unfortunately. I usually search on the internet the error message that it gave me and see if other people hit something similar. What error does it give you without those changes?

[nicfb]

It is saying that shared_mutex isn't a part of standard library, which makes me think I need to add the -std=c++17 flag somewhere, i'm just not sure where.

[solodon4]

Can you make a small repro that includes the header you need and uses the type you need (nothing else from mach7)? I'll try to see what's needed to build it. Also let me know what compilers and their versions your have access to.

[nicfb]

Sorry it took me so long to get back to you.. The only thing I need aside from the Mach7 essentials in the header file is mutex and shared_mutex. I am currently using the gcc version 6.2.1 20160830 (GCC) compiler.

[solodon4]

Were you able to resolve your issue Nicholas?

[nicfb]

Yes, I was! I haven't looked at the project for quite some time but I was able to move past that road block. Thanks for your help!

[elfprince13]

@solodon4 - I am wondering which vtblmap implementations, if any, are thread safe? @nicfb references vtblmap3st but there is also a vtblmap3mt that purports to support multithreading, and vtblmap4 is the one that is actually used everywhere?

[solodon4]

@elfprince13 vtblmap4 was an evolution of vtblmap3 to support multiple subjects directly, which is why you see it used in all the headers experimenting with multiple subjects. IIRC it was evolved from vtblmap3st. I remember I was looking for people to help implement lock-free version of vtblmap4 but that never materialized. vtblmap3mt would be the closest multi-threading support there is, but it only works on a single subject.