freenode/#clasp - IRC Chatlog
Search
15:59:20
drmeister
Sorry - I've been wrapped up in this generic function multithreading issue and not getting 'dev' buildable.
16:01:06
drmeister
I'm not certain that 'dev' will build though - I'll push to testing and give it a try.
16:03:54
drmeister
frgo: The multi-threading issue is on both the lisp side and C++ side. It's the most complicated resource that I've tried to make thread safe - I'm having trouble figuring it out.
16:06:02
frgo
You mentioned "race condition" here ... I don't want to hold you up but I'd be interested to understand a tiny bit more - only if it is explainable in a few lines..
16:08:32
drmeister
Each generic function also has an a-list that maps previous invocation signatures to effective method functions.
16:10:03
drmeister
When a call history changes (several ways that can happen) the discriminating function is set to the 'invalidated-dispatcher' function.
16:10:43
drmeister
When a generic function call happens and it jumps to the invalidated-dispatcher function a new discriminating function is compiled from the call history.
16:12:09
drmeister
No generic functions are invoked when the discriminating function is compiled - but I have to put a write-lock on the code that compiles the discriminating function so that multiple threads don't try to compile/install discriminating functions at the same time.
16:12:57
drmeister
Besides that I need to put write locks on other code that updates the generic function call history, specializer profile, method list etc.
16:13:43
drmeister
Somewhere I'm getting a deadlock when something that has the lock calls something that wants a lock.
16:15:21
frgo
For that 1 generic function's dependent objects like call history etc - so for each GF just 1 lock - or do I misinterpret sth?
16:16:30
drmeister
So not one lock for all generic functions or one lock for each generic function resources - just one lock per generic function.
16:18:26
frgo
Ok - I am thinking: That one lock per GF must be enough - no other locks required as everything else is required to be sequential updates / needs to be synchronized to that one lock.
16:18:27
drmeister
I think I just need to struggle through this - I can barely describe the problem.
16:20:16
frgo
Now you need to pass on the lock through code that is allowed to update the resource - the lock has to be a thread-local variable. If the lock passed on and tghe lock being thread-global are the same the resource is allowed to update.
16:21:58
drmeister
src/lisp/kernel/clos/closfastgf.lsp and src/core/funcallableInstance.cc and src/core/funcallableInstance.h
16:23:14
drmeister
Don't trouble yourself too much - I think I just need to think about it harder. Also, I haven't pushed out the latest code - because it doesn't build yet.
18:21:14
drmeister
I can't write lock the entire generic function when there is a dispatch-miss - that deadlocks.
18:21:52
drmeister
It deadlocks because the same generic function is invoked in the course of the dispatch miss.
18:25:07
drmeister
I'm starting to think though that the generic function read/write lock should be to guard against two threads updating anything in the generic function other than the discriminator function.
18:25:33
drmeister
The discriminator function is an atomic object, a single pointer to a block of code.
18:28:01
drmeister
If two threads each evaluate the same generic function and they both lead to a dispatch miss - then I need to protect the call-history from being updated by two threads at the same time - but not the discriminating function.
18:28:33
drmeister
If one thread updates the discriminating function and then the other overwrites it - it's no big deal. There will be another dispatch-miss and that will rebuild the discriminating function again.
0:01:41
drmeister
It's a read/write lock where you can upgrade it from a read lock to a write lock without giving the lock up.
0:02:23
drmeister
There's a lot of reading and then a burst of writing in the dispatch-miss function.
0:08:46
drmeister
Crap - that won't be adequate - if two threads both dispatch-miss at the same time it will still deadlock
2:56:22
drmeister
Currently I'm setting up logging from separate threads during the slow path of fastgf to figure out where the problem might be.
2:58:46
drmeister
I'm worried that if two threads experience a dispatch-miss at the same time there will be a deadlock
2:59:53
beach
For SICL, I was planning to use some lock-free synchronization technique, but that has not been tested in real life of course.
3:00:56
beach
I don't think it would be possible to figure out the problem with any other technique. The description of it is too imprecise, as you probably understand.
3:01:43
beach
To update the call history, I was planning to require that each thread compute a new call history list (with fresh CONS cells) and then uses CAS to update the result.
3:03:41
drmeister
When you update the call history I do a sanity check to test if the entry is already in the call history - I don't need to do that - that would simplify things.
3:05:02
drmeister
What happens if each thread computes a new call history list with fresh CONS cells and then updates the result? The thread that updates last will clobber what the first thread updated the call-history with.
3:11:40
drmeister
So thread 1 and 2 each get the same call history and create a new call history by prepending their specializers/effective method to the list and then say thread 1 uses CAS to write the result and succeeds - then thread 2 uses CAS but it fails because there was already an update - so thread 2 starts over.
3:19:05
drmeister
What about updating the discriminating function? I guess if two threads start compiling a discriminating function and one thread sets the function and then the second overwrites it - there is no harm - they are the same discriminating function.
3:22:31
beach
One thread (say T1) might compute a discriminating function from the call history. Then, during that computation, a different thread (say T2) re-computes the call history. Then T1 sets the discriminating function. Finally T2 re-computes a new discriminating function from the new call history.
3:24:49
beach
There is a difference between preserving the integrity of the system and giving the "right" result in all situations.
3:25:50
beach
If an application uses a generic function in one thread and updates it in another, then that application is responsible for making sure that either the order doesn't matter, or it must introduce synchronization primitives in the application code.
3:27:04
beach
I think what you must do is to make sure the discriminating function is set to either the one that recomputes itself, or to one that corresponds to the current call history.
3:28:26
beach
Because if the discriminating function corresponds to an obsolete call history, then argument combinations may succeed that shouldn't and this case would not be detected.
3:31:52
beach
If the set of methods is not modified, then the call history grows monotonically. I.e. no call-history entry is ever removed. Correct me if I am wrong, it is still early in the morning here and I am working on my coffee.
3:32:41
beach
Then, it is safe to keep the discriminating function until there is a failure to recognize some argument combination.
3:33:14
beach
... because the discriminating function will be re-computed to recognize more combinations.
3:33:53
beach
But if the set of methods changes, then entries may be altered or removed from the call history. Now the discriminating function is wrong.
3:34:22
beach
... in that it may let argument combinations pass that do not correspond to existing methods.
3:38:04
beach
... and then you have to decide whether it violates the integrity of the system, or it only gives the wrong answer.
3:38:34
beach
If 2. you need to decide whether this is your problem or that of the application writer.
3:46:46
drmeister
I think anything that removes entries from the call history without coordinating it with the dispatch function will violate the integrity of the system. I saw plenty of that when I was getting everything to work.
3:50:01
drmeister
But it's late here and I'm heading to bed - my head will be clearer in the morning.
3:50:47
drmeister
I follow your suggestion to use CAS for the regular call history updates - thank you.
3:54:15
drmeister
I can set up the call history as a C++ atomic object and use compare_exchange_weak or compare_exchange_strong on it. http://en.cppreference.com/w/cpp/atomic/atomic/compare_exchange