[CLJ-988] the locking in MultiFn.java (synchronized methods) can cause lots of contention in multithreaded programs Created: 08/May/12 Updated: 21/Sep/12 Resolved: 21/Sep/12
|Fix Version/s:||Release 1.5|
|Reporter:||Kevin Downey||Assignee:||Stuart Sierra|
|Attachments:||clj-988-tests-only-patch-v1.txt issue988-lockless-multifn+tests-120817.diff issue988-lockless-multifn+tests.diff|
|Patch:||Code and Test|
if you call a single multimethod a lot in multithreaded code you get lots of contention for the lock on the multimethod. this contention slows things down a lot.
this is due to getMethod being synchronized. it would be great if there was some fast non-locking path through the multimethod.
|Comment by Kevin Downey [ 08/May/12 11:30 AM ]|
|Comment by David Santiago [ 11/May/12 6:38 AM ]|
Here's a stab in the dark attempt at rewriting MultiFn to use atoms to swap between immutable copies of its otherwise mutable state.
The four pieces of the MultiFn's state that are mutable and protected by locks are now contained in the MultiFn.State class, which is immutable and contains convenience functions for creating a new one with one field changed. An instance of this class is now held in an atom in the MultiFn called state. Changes to any of these four members are now done with an atomic swap of these State objects.
The getMethod/findAndCacheBestMethod complex was rewritten to better enable the atomic logic. findAndCacheBestMethod was replaced with findBestMethod, which merely looks up the method; the caching logic was moved to getMethod so that it can be retried easily as part of the work that method does.
As it was findAndCacheBestMethod seemingly had the potential to cause a stack overflow in a perfect storm of heavy concurrent modification, since it calls itself recursively if it finds that the hierarchy has changed while it has done its work. This logic is now done in the CAS looping of getMethod, so hopefully that is not even an unlikely possibility anymore.
There is still seemingly a small race here, since the check is done of a regular variable against the value in a ref. Now as before, the ref could be updated just after you do the check, but before the MultiFn's state is updated. Of course, only the method lookup part of a MultiFn call was synchronized before; it could already change after the lookup but before the method itself executed, having a stale method finish seemingly after the method had been changed. Things are no different now in general, with the atom-based approach, so perhaps this race is not a big deal, as a stale value can't persist for long.
The patch passes the tests and Clojure and multimethods seems to work.
|Comment by Kevin Downey [ 12/May/12 8:59 PM ]|
this patch gets rid of the ugly lock contention issues. I have not been able to benchmark it vs. the old multimethod implementation, but looking at it, I would not be surprised if it is faster when the system is in a steady state.
|Comment by Stuart Halloway [ 08/Jun/12 12:11 PM ]|
This looks straightforward, except for getMethod. Can somebody with context add more discussion of how method caching works?
Also, it would be great to have tests with this one.
|Comment by David Santiago [ 15/Jun/12 4:44 AM ]|
Obviously I didn't write the original code, so I'm not the ideal
There are four pieces of state that change as the multimethod is either
I think reset(), addMethod(), removeMethod(), preferMethod(),
Invoking a multimethod through its invoke() function will call
The biggest change in the patch is to the
In the original code, getFn() does nothing but bounce through
1. It checks if there's a method for the dispatch value in the
2. If not, it calls findAndCacheBestMethod() on the
1. It iterates through every map entry in the method table,
2. If it did not find a suitable entry, it returns null.
3. Otherwise, it checks if the hierarchy has been changed since the cache
3. Failing all else, it will return the method for the default
Again, remember everything in the list above happens in a call to a
Moving on now to the patch in this issue. As mentioned, the main
To implement this change, I pulled the implicit looping logic from
I'll now describe the operation of the logic in the for loop. The
1. First we dereference our state, and assign this value to both
2. Check if the cache is stale, and flush it if so. If the cache
3. Check if the methodCache has an entry for this dispatch
4. The value was not in the methodCache, so call the function
The one thing that is possibly questionable is the check at this
5. Finally, if findBestMethod() failed to find us a method for the
So the organization of getMethod() in the patch is complicated by two
|Comment by David Santiago [ 15/Jun/12 4:45 AM ]|
I've updated this patch (removing the old version, which is entirely superseded by this one). The actual changes to MultiFn.java are identical (modulo any thing that came through in the rebase), but this newer patch has tests of basic multimethod usage, including defmulti, defmethod, remove-method, prefer-method and usage of these in a hierarchy that updates in a way interleaved with calls.
|Comment by David Santiago [ 15/Jun/12 6:38 AM ]|
I created a really, really simple benchmark to make sure this was an improvement. The following tests were on a quad-core hyper-threaded 2012 MBP.
With two threads contending for a simple multimethod:
With four threads contending for a simple multimethod:
You can get the code at https://github.com/davidsantiago/multifn-perf
|Comment by David Santiago [ 14/Aug/12 10:02 PM ]|
It's been a couple of months, and so I just wanted to check in and see if there was anything else needed to move this along.
Also, Alan Malloy pointed out to me that my benchmarks above did not mention single-threaded performance. I actually wrote this into the tests above, but I neglected to report them at the time. Here are the results on the same machine as above (multithreaded versions are basically the same as the previous comment).
With a single thread performing the same work:
So the lockless multimethods are still faster even in a single-threaded case, although the speedup is more modest compared to the speedups in the multithreaded cases above. This is not surprising, but it is good to know.
|Comment by Stuart Sierra [ 17/Aug/12 2:58 PM ]|
Screened. The approach is sound.
I can confirm similar performance measurements using David Santiago's benchmark, compared with Clojure 1.5 master as of commit f5f4faf.
My only concern is that the extra allocations of the State class will create more garbage, but this is probably not significant if we are already using persistent maps. It would be interesting to compare this implementation with one using thread-safe mutable data structures (e.g. ConcurrentHashMap) for the cache.
|Comment by David Santiago [ 17/Aug/12 7:05 PM ]|
I think your assessment that it's not significant compared to the current implementation using persistent maps is correct. Regarding the extra garbage, note that the new State is only created when the hierarchy has changed or there's a cache miss (related, obviously)... situations where you're already screwed. Then it won't have to happen again for the same method (until another change to the multimethod). So for most code, it won't happen very often.
ConcurrentHashMap might be faster, it'd be interesting to see. My instinct is to keep it as close to being "made out of Clojure" as possible. In fact, it's hard to see why this couldn't be rewritten in Clojure itself some day, as I believe Chas Emerick has suggested. Also, I would point out that two of the three maps are used from the Clojure side in core.clj. I assume they would be happier if they were persistent maps.
Funny story: I was going to point out the parts of the code that were called from the clojure side just now, and alarmingly cannot find two of the functions. I think I must have misplaced them while rewriting the state into an immutable object. Going to attach a new patch with the fix and some tests for it in a few minutes.
|Comment by David Santiago [ 17/Aug/12 7:44 PM ]|
Latest patch for this issue. Supersedes issue988-lockless-multifn+tests.diff as of 08/17/2012.
|Comment by David Santiago [ 17/Aug/12 7:49 PM ]|
As promised, I reimplemented those two functions. I also added more multimethod tests to the test suite. The new tests should definitely prevent a similar mistake. While I was at it, I went through core.clj and found all the multimethod API functions I could and ensured that there were at least some basic functionality tests for all of them. The ones I found were: defmulti, defmethod, remove-all-methods, remove-method, prefer-method, methods, get-method, prefers (Some of those already had tests from the earlier version of the patch).
Really sorry about catching this right after you vetted the patch. 12771 test assertions were apparently not affected by prefers and methods ceasing to function, but now there are 12780 to help prevent a similar error. Since you just went through it, I'm leaving the older version of the patch up so you can easily see the difference to what I've added.
|Comment by Rich Hickey [ 15/Sep/12 9:05 AM ]|
https://github.com/clojure/clojure/commit/83ebf814d5d6663c49c1b2d0d076b57638bff673 should fix these issues. The patch here was too much of a change to properly vet.
If you could though, I'd appreciate a patch with just the multimethod tests.
|Comment by Andy Fingerhut [ 15/Sep/12 10:59 AM ]|
Patch clj-988-tests-only-patch-v1.txt dated Sep 15 2012 is a subset of David Santiago's
|Comment by Rich Hickey [ 17/Sep/12 9:20 AM ]|
tests-only patch ok