freenode/#clasp - IRC Chatlog
Search
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
5:05:14
beach
Here is an interesting scenario: Suppose some class C is updated. Now, all existing instances of C are obsolete. Suppose that two different threads T1 and T2 use the same obsolete instance (say O) as arguments to perhaps two different generic functions F1 and F2 respectively. Is it possible that the discriminating function of F1 has been updated, but that of F2 has not?
5:05:15
beach
If so, the following could happen: T2 runs the discriminating function, and the result is an accessor that goes directly to some slot, but then T2 is delayed, and T1 executes. The discriminating function of F1 fails, so T1 detects that O is obsolete. It now alters the contents of the slots of O. Now, T2 executes again and accesses the wrong slot of O, perhaps even outside of O.