| Commit message (Collapse) | Author | Age |
|---|
| |
|
|
|
|
|
|
|
| |
We use a fixed version of the previous algorithm. See the comments for details.
Fancier algorithms exist. I thought of a cool one that makes use of BatchKeyedLocker (would give me an excuse to revive it, heh), but fancy algorithms would be overkill. As noted in the initial commit of NaiveMultisetSemaphore, performance isn't critical.
RELNOTES: None
PiperOrigin-RevId: 208560559
|
| |
|
|
|
|
|
| |
use Semaphore#availablePermits. I have no idea why I didn't do this initially.
RELNOTES: None
PiperOrigin-RevId: 207883650
|
| |
|
|
|
|
|
|
| |
Blaze had its own class to avoid GC from varargs array creation for the precondition happy path. Guava now (mostly) implements these, making it unnecessary to maintain our own.
This change was almost entirely automated by search-and-replace. A few BUILD files needed fixing up since I removed an export of preconditions from lib:util, which was all done by add_deps. There was one incorrect usage of Preconditions that was caught by error prone (which checks Guava's version of Preconditions) that I had to change manually.
PiperOrigin-RevId: 175033526
|
| |
|
|
|
| |
RELNOTES: None
PiperOrigin-RevId: 174062560
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
a boring naive synchronized implementation.
There's a race condition in my design of the lockless data structure. I haven't been able to come up with a lockless algorithm that actually works, and the naive one seems to be fine. In Blaze's usage, performance actually isn't super important so the naive implementation is fine.
Consider three threads and a MultisetSemaphore with 2 max unique values.
T1: acquireAll({a, b})
T2: acquireAll({a, c})
T3: acquireAll({a, d})
For the for-loop before the 'acquire' call, suppose:
-T1 wins the race to acquire 'a' [1] and also wants to acquire 'b' [1]
-T2 loses the race to acquire 'a' [2] and also wants to acquire 'c' [1]
-T3 loses the race to acquire 'a' [2] and also wants to acquire 'd' [1]
So then in [3] we have:
-T1 tries to acquire 2 permits
-T2 tries to acquire 1 permit
-T3 tries to acquire 1 permit
Suppose the execution order in [3] is T2, T3, T1. So that means we then have T1 still at [3] and both T2 and T3 at [4], which is a deadlock.
[1] https://github.com/bazelbuild/bazel/blob/fa96b04f6c8ca6b6b3464727672267133e852959/src/main/java/com/google/devtools/build/lib/concurrent/MultisetSemaphore.java#L184
[2] https://github.com/bazelbuild/bazel/blob/fa96b04f6c8ca6b6b3464727672267133e852959/src/main/java/com/google/devtools/build/lib/concurrent/MultisetSemaphore.java#L191
[3] https://github.com/bazelbuild/bazel/blob/fa96b04f6c8ca6b6b3464727672267133e852959/src/main/java/com/google/devtools/build/lib/concurrent/MultisetSemaphore.java#L199
[4] https://github.com/bazelbuild/bazel/blob/fa96b04f6c8ca6b6b3464727672267133e852959/src/main/java/com/google/devtools/build/lib/concurrent/MultisetSemaphore.java#L210
--
PiperOrigin-RevId: 148272171
MOS_MIGRATED_REVID=148272171
|
|
|
at most K unique things at once.
--
MOS_MIGRATED_REVID=138684040
|
nharmata
tomlu