Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How are golang select statements implemented?

In particular, I have some blocking queues in C++, and I want to wait until any one of them has some item I can pop.

The only mechanism I can think of is to spawn a separate thread for each queue that pops from its input queue and feeds into a master queue that the original thread can wait on.

It seems kind of resource heavy to spawn N new threads and then kill them all every time I want to pop from a group of queues.

Does Golang implement some more elegant mechanism that I might be able to implement in my own C++ code?

like image 308
math4tots Avatar asked May 04 '16 07:05

math4tots


1 Answers

I wouldn't necessarily say that Go's select implementation is elegant, but I think it's beautiful in its own way and it's fairly optimized.

  • it special-handles selects with a single non-default case
  • it permutes the order in which cases are evaluated in order to avoid deterministic starvation
  • it does an optimistic first pass over the cases looking for one that's already satisfied
  • it enqueues on the internal sender/receiver queues of each channel using many internal, known only to the runtime mechanisms
    • it uses sudogs which are like lightweight goroutine references (there can be many sudogs for the same goroutine) that allow quick jumping into the goroutine stack
    • it uses the scheduler's gopark mechanism to block itself which allows efficient unparking on signal
    • when signalled and unparked, it immediately goes into the triggered case handler function by manipulating the select goroutine's program counter

There's no single overarching groundbreaking idea in the implementation, but you would really appreciate how each step was carefully tinkered with so that it's fast, efficient and well integrated with concept of channels. Because of that, it's not very easy to reimplement Go's select statement in another language, unless you at least have the chan construct first.

You can take a look at the reimplementations available in other languages, where the idea was redone with various degrees of similarity and effectiveness. If I had to reimplement select from scratch in another language, I would probably first try a single shared semaphore and, in case that didn't work, switch to a cruder, sleep-a-little-then-check-in-random-order strategy.

like image 182
Dimitar Dimitrov Avatar answered Oct 17 '22 22:10

Dimitar Dimitrov