Using a ConcurrentHashMap instead (I hope it doesn't cause issues for Scala.js?) makes it even faster.

One Supervisor per worker, but with ConcurrentHashMap for state (currently this PR):

Benchmark                       (size)   Mode  Cnt    Score    Error    Units
DispatcherBenchmark.scheduling    1000  thrpt   20  715.391 ± 28.495  ops/min

One Supervisor only (old Dispatcher.scala), but with ConcurrentHashMap for state:

Benchmark                       (size)   Mode  Cnt    Score   Error    Units
DispatcherBenchmark.scheduling    1000  thrpt   20  709.094 ± 8.640  ops/min

So we get most of the benefits from just changing to ConcurrentHashMap, but one Supervisor per CPU/worker still helps a bit, it seems.

The problem is that Supervisor can't use ConcurrentHashMap because it's fully pure. We could theoretically figure out whether the underlying F is secretly an Async and then have a different implementation (similar to what we're doing with Queue), but I'm not sure the performance gain (3% ish?) is worth that much effort.

Also Ref[ConcurrentHashMap] seems like a scary type. :-) You really want the contents of a Ref to be immutable.

@djspiewak Yeah, sure, I was actually inspired to try ConcurrentHashMap from reading your gist at https://gist.github.com/djspiewak/464c11307cabc80171c90397d4ec34ef last night, figuring this might be below the line, but maybe not. ;)

I did notice it's not used anywhere in cats or cats-effect today, and it's interesting to see that using ConcurrentHashMap improves the performance by another 20%. I can remove that commit, but I might still need help with the test failure (I'll try figuring it out tonight, but I don't have much time).

Yeah I'm working on the test failure right now.

My thought on the ConcurrentHashMap is let's jump that shark after we land this first one, and when we do we should leverage the Async typecase trick.

So the test failure is legitimate. The test in question is checking to make sure that finalizers in separate actions passed to the same Dispatcher are independent and invoked concurrently. This is true today with the existing singular Supervisor, but we lose this property between multiple Supervisors (who will all finalize sequentially). It's not entirely clear to me yet how to resolve this issue.

We'd need something like a more general version of Resource.both, then? I took a quick stab at it.

We'd need something like a more general version of Resource.both, then?

Resource.both does indeed run finalizers in parallel. I'm basically trying to make up my mind whether or not that's a thing we should be leaning on here. :-P

Not sure why some of those CI builds failed, but the last commit passes the tests on my machine (for both JVM and JS). Thanks for figuring out why it failed, then the fix was easy. Let me know if you think it's the right one. ;)

The thing with this solution is it basically replicates what Supervisor is already doing. :-P Like, it does work, but I'm not sure it's the best way of doing this. Need to think about it a bit more today…

Yeah, I'm not convinced either. The real issue is just the lock contention for that one shared Ref[Map], and there's more than one way to reduce/remove that, of course.

I see there's a StripedHashtable (backed by 4 ThreadSafeHashtable per CPU core) used only to store fiber error callbacks - I wonder if it would be reasonable to do the same (or almost the same) thing for fiber cancellation callbacks in Supervisor. Looks like it might have been created to solve a very similar problem. 🤔

Tangentially, even if it doesn't end up getting used here, something like Resource.all to do this type of concurrent acquire/release might be useful for other use cases, but maybe there's a reason why it doesn't already exist.

There's no particular reason that Supervisor is not more sophisticated, other than the fact that we were not aware of it being a hotspot, and no one working on optimizations for it. Feel free to try out things.

This latest push no longer reflects the title, and I would of course update it if this approach is accepted, but instead allows Dispatcher to use a Supervisor optimized for Async that uses a ConcurrentHashMap for keeping track of fibers.

Performance is still excellent, even better than the original PR:
DispatcherBenchmark.scheduling 1000 thrpt 20 703.589 ± 4.302 ops/min

The implementation of supervisor is shared between the Concurrent and Async cases, but Dispatcher calls the async constructor directly which allows us to do this without typecase tricks, but it would be trivial to enable the optimization also for the general case in Supervisor.

Yes, it does use an impure ConcurrentHashMap (which outperforms TrieMap here, by a significant margin) in the async case, but the interface is still pure. I think.

In my opinion, it is preferable to the "one Supervisor per CPU" approach, as that one requires a custom parallel resource implementation, and the approach here also requires less resources as there's only one shared Supervisor instance.

PS. I was able to get to around 725 ops/min by essentially duplicating the Supervisor logic with ConcurrentHashMap/mutable.Map in Dispatcher itself using a similar pattern as for latches etc., but that certainly does not seem to be worth it compared to this alternative.

Ah dang this is cool. I'll look into this more later today! Quick note on the compilation errors though: it's coming from the Scala 2.12 cross-build. I think it would be worth not using the collection shims and instead working against the Java API directly if at all possible.

Thanks for tackling this!!