perf(executor): `ArrayQueue` is slow

[George-Miao]

ArrayQueue is used each time a task is scheduled:

• When scheduling locally, ArrayQueue::pop is called repeatedly to piggyback remote schedules
• When scheduling remotely, ArrayQueue::push is called

And ArrayQueue::pop is EXPENSIVE, really expensive: multiple atomic load and a SeqCst atomic fence when empty.

[George-Miao]

We may want to roll our own MPSC queue with batch receiving. I have benched all the popular queues and channels with MPSC/MPMC support I can find on crates.io, seems we're out of luck using 3rd party library. Also, if we don't care about multithread scheduling fairness, we can get rid of piggyback and only let executor to receive everything in tick.

[abh1nav10]

Hi @George-Miao. I tried to implement a batched MPSC queue. I tried to optimize for the scenario where the queue is empty and we don't have to pay the cost of a SeqCst fence. Here is the implementation:
https://github.com/abh1nav10/memrec/blob/master/src/fastsync.rs.

I have kept the flags that signal the complete filling of batches on a single cache line so that the executor can fetch them once and just has do Relaxed loads on them to check if there is data to be read which would have been bad in a highly contentious scenario because of false sharing but, in our case when cross threads wake-ups are rare, this should not be a problem.

For draining when the queue is empty, I benchmarked it with 16 slots against ArrayQueue and the results show that this implementation takes roughly 2.5ns whereas ArrayQueue takes almost 6ns.
https://github.com/abh1nav10/memrec/blob/master/benches/fast.rs#L180-L186

What I am still thinking is the increased latency of some operations as the implementation currently does not drain them until the batch is full.
Happy to hear your thoughts.

[George-Miao]

@abh1nav10 Hi! I have read the implementation, it's certainly a very interesting design. Though by batching I originally mean when receiving, copy all items in the queue to local and mark all slots to be available since we just need a fixed size queue.

[abh1nav10]

I see, thanks for clarifying.

[George-Miao]

Anyway, can you try to benchmark compio-executor with your impl swapped in? Though not sure what bench would be best...
The idea seems pretty solid to me.

[abh1nav10]

Sure, I shall get back.

[abh1nav10]

Hi! @George-Miao .
I performed the benchmark for both when the sync queue is empty and the executor just has to poll local futures and when there is pressure on the sync queue.
I used the implementation with 8 batches as increasing further to 16 was degrading performance and it was under-performing as compared to ArrayQueue. This happened when I swapped the implementation in the executor but when I was benchmarking individually, 16 batches were able to perform better than ArrayQueue on the empty drain.

Following is the link to the setup for the first case when the executor just polls local futures.
https://github.com/abh1nav10/compio/blob/benchmark-executor/compio-executor/benches/comparison.rs#L58-L78
The is the result that I got-

BatchedQueue	ArrayQueue
2.3 us	6.45 us
4.5 us	8.5 us
13.4 us	17.64 us

I tried two setups for putting pressure on the sync queue-
Following is the link to the first one-
https://github.com/abh1nav10/compio/blob/benchmark-executor/compio-executor/benches/remote.rs#L65-L88
I have the number for this approach but I am not putting it here for now because the results vary by a large enough margin. This is because the spawned thread wakes them up repeatedly and the number of tasks drained by the executor in tick varies significantly as it depends heavily on how many times the spawned thread pushed into the sync queue.

For the second approach for remote polling whose link is follows:
https://github.com/abh1nav10/compio/blob/benchmark-executor/compio-executor/benches/remote_with_many_receive.rs#L65-L88
I did not put the numbers for this as well but this is also variable because I guess this could not measure the impact of the pushing of tasks in the sync queue as it is overshadowed by the repeated sending and receiving in the channel.

Happy to learn if there is a better approach!

[George-Miao]

@abh1nav10 Interesting results! Can you also try to run compio's own bench? Maybe try the uds one? I'm not very certain if we should ditch piggyback (remote scheduling faireness in exchange for lower overhead), or if there's a better approach for this...

[abh1nav10]

I ran the benchmark. The results are very similar with either of them being slightly better than the other on different runs and yes I think in order to solve the problem of scheduling fairness, we would have to somehow make the executor periodically drain the batches regardless of whether they are full or not and in order to do that in this implementation, I dont think we can get around without having to use SeqCst to ensure total order at certain points which takes away the benefit. However the benefit of draining when the queue is empty is still there.