Adding an item to `AsyncQueue<Serial>` is linear in the number of pending queue items, thus adding n items to an `AsyncQueue` before any can execute is in O(n^2). This decision was made intentionally because the primary use case for `AsyncQueue` was to track pending LSP requests, of which we don’t expect to have too many pending requests at any given time.
`SourceKitIndexDelegate` was also using `AsyncQueue` to track the number of pending units to be processed and eg. after indexing SourceKit-LSP, I have seen this grow up to ~20,000. With the quadratic behavior, this explodes time-wise.
Turns out that we don’t actually need to use a queue here at all, an atomic is sufficient and much faster.
Independently, we should consider mitigating the quadratic behavior of `AsyncQueue<Serial>` or `AsyncQueue` in general.
We used C atomics but these were allocated as Swift variables. Even thought they were atomic, concurrent accesses to them could violate Swift’s exclusivity laws, raising thread sanitizer errors.
Allocate the C atomics using malloc to fix this problem.
rdar://129170128
This also means that you can use the index log to view which tasks are currently being executed.
Since we only have a single log stream we can write to, I decided to prefix every line in the index log with two colored emojis that an easy visual association of every log line to the task that generated them.
