sleep

Documentation

Overview

Package sleep allows goroutines to efficiently sleep on multiple sources of notifications (wakers). It offers O(1) complexity, which is different from multi-channel selects which have O(n) complexity (where n is the number of channels) and a considerable constant factor.

It is similar to edge-triggered epoll waits, where the user registers each object of interest once, and then can repeatedly wait on all of them.

A Waker object is used to wake a sleeping goroutine (G) up, or prevent it from going to sleep next. A Sleeper object is used to receive notifications from wakers, and if no notifications are available, to optionally sleep until one becomes available.

A Waker can be associated with at most one Sleeper, but a Sleeper can be associated with multiple Wakers. A Sleeper has a list of asserted (ready) wakers; when Fetch() is called repeatedly, elements from this list are returned until the list becomes empty in which case the goroutine goes to sleep. When Assert() is called on a Waker, it adds itself to the Sleeper's asserted list and wakes the G up from its sleep if needed.

Sleeper objects are expected to be used as follows, with just one goroutine executing this code:

// One time set-up.
s := sleep.Sleeper{}
s.AddWaker(&w1, constant1)
s.AddWaker(&w2, constant2)

// Called repeatedly.
for {
	switch id, _ := s.Fetch(true); id {
	case constant1:
		// Do work triggered by w1 being asserted.
	case constant2:
		// Do work triggered by w2 being asserted.
	}
}

And Waker objects are expected to call w.Assert() when they want the sleeper to wake up and perform work.

The notifications are edge-triggered, which means that if a Waker calls Assert() several times before the sleeper has the chance to wake up, it will only be notified once and should perform all pending work (alternatively, it can also call Assert() on the waker, to ensure that it will wake up again).

The "unsafeness" here is in the casts to/from unsafe.Pointer, which is safe when only one type is used for each unsafe.Pointer (which is the case here), we should just make sure that this remains the case in the future. The usage of unsafe package could be confined to sharedWaker and sharedSleeper types that would hold pointers in atomic.Pointers, but the go compiler currently can't optimize these as well (it won't inline their method calls), which reduces performance.

Index

• type Sleeper
  • func (s *Sleeper) AddWaker(w *Waker, id int)
  • func (s *Sleeper) Done()
  • func (s *Sleeper) Fetch(block bool) (id int, ok bool)
• type Waker
  • func (w *Waker) Assert()
  • func (w *Waker) Clear() bool
  • func (w *Waker) IsAsserted() bool

Types

type Sleeper

type Sleeper struct {
	// contains filtered or unexported fields
}

Sleeper allows a goroutine to sleep and receive wake up notifications from Wakers in an efficient way.

This is similar to edge-triggered epoll in that wakers are added to the sleeper once and the sleeper can then repeatedly sleep in O(1) time while waiting on all wakers.

None of the methods in a Sleeper can be called concurrently. Wakers that have been added to a sleeper A can only be added to another sleeper after A.Done() returns. These restrictions allow this to be implemented lock-free.

This struct is thread-compatible.

func (*Sleeper) AddWaker

func (s *Sleeper) AddWaker(w *Waker, id int)

AddWaker associates the given waker to the sleeper. id is the value to be returned when the sleeper is woken by the given waker.

func (*Sleeper) Done

func (s *Sleeper) Done()

Done is used to indicate that the caller won't use this Sleeper anymore. It removes the association with all wakers so that they can be safely reused by another sleeper after Done() returns.

func (*Sleeper) Fetch

func (s *Sleeper) Fetch(block bool) (id int, ok bool)

Fetch fetches the next wake-up notification. If a notification is immediately available, it is returned right away. Otherwise, the behavior depends on the value of 'block': if true, the current goroutine blocks until a notification arrives, then returns it; if false, returns 'ok' as false.

When 'ok' is true, the value of 'id' corresponds to the id associated with the waker; when 'ok' is false, 'id' is undefined.

N.B. This method is *not* thread-safe. Only one goroutine at a time is

allowed to call this method.

type Waker

type Waker struct {
	// contains filtered or unexported fields
}

Waker represents a source of wake-up notifications to be sent to sleepers. A waker can be associated with at most one sleeper at a time, and at any given time is either in asserted or non-asserted state.

Once asserted, the waker remains so until it is manually cleared or a sleeper consumes its assertion (i.e., a sleeper wakes up or is prevented from going to sleep due to the waker).

This struct is thread-safe, that is, its methods can be called concurrently by multiple goroutines.

func (*Waker) Assert

func (w *Waker) Assert()

Assert moves the waker to an asserted state, if it isn't asserted yet. When asserted, the waker will cause its matching sleeper to wake up.

func (*Waker) Clear

func (w *Waker) Clear() bool

Clear moves the waker to then non-asserted state and returns whether it was asserted before being cleared.

N.B. The waker isn't removed from the "ready" list of a sleeper (if it happens to be in one), but the sleeper will notice that it is not asserted anymore and won't return it to the caller.

func (*Waker) IsAsserted

func (w *Waker) IsAsserted() bool

IsAsserted returns whether the waker is currently asserted (i.e., if it's currently in a state that would cause its matching sleeper to wake up).