How Go’s Runtime Uses Treap for Efficient Goroutine Scheduling

Treap overview

Treap is a binary tree that simultaneously satisfies the binary‑search‑tree (BST) order on the key and the heap order on a random priority. Each node stores a key (X) and a priority (Y). The BST property guarantees that all keys in the left subtree are ≤ X and all keys in the right subtree are ≥ X; the heap property (max‑heap in the Go implementation) guarantees Y ≤ Y₀ for every child. Randomly assigning distinct priorities yields an expected balanced tree, giving search, insert and delete an expected O(log N) cost. Compared with red‑black or AVL trees, a treap needs only two rotation primitives, simplifying implementation.

Purpose in the Go runtime

In the Go runtime source file sema.go, the struct semaRoot contains a field treap *sudog. This treap holds the waiting goroutine nodes ( sudog) for a sync.Mutex. Each sudog has a unique address ( s.elem) that serves as the treap key, and a random ticket that serves as the priority.

type semaRoot struct {
    lock  mutex
    treap *sudog // root of a balanced tree of waiting goroutines
    nwait atomic.Uint32 // number of waiting goroutines
}

type sudog struct {
    g           *g
    next        *sudog
    prev        *sudog
    elem        unsafe.Pointer // address of the mutex field
    acquiretime int64
    releasetime int64
    ticket      uint32 // random priority
    isSelect    bool
    success     bool
    waiters     uint16
    parent      *sudog // binary‑tree parent
    waitlink    *sudog // linked list of goroutines waiting on the same address
    waittail    *sudog
    c           *hchan // channel, if any
}

When a goroutine attempts to lock a sync.Mutex that is already held, it is blocked and inserted into this treap. Goroutines blocked on the same mutex share the same address (the address of Mutex.sema) and therefore belong to the same treap node’s wait‑list.

Enqueue – adding a waiting goroutine

The method (root *semaRoot) queue(addr *uint32, s *sudog, lifo bool) inserts a sudog into the treap. The algorithm proceeds as follows:

Initialize the new sudog (set g, elem, clear links, zero waiters).

Traverse the treap from the root using a standard BST search on addr (the key). If a node with the same address already exists, either replace it (when lifo is true) or append s to the node’s wait‑list.

If the address is not present, remember the last visited node as last and continue the descent until a nil child is reached.

Assign a random priority: s.ticket = cheaprand() | 1. The lowest bit is forced to 1 so the priority never equals zero.

Link the new node as the appropriate child of last and set s.parent = last.

While the parent’s priority is larger than the child’s, rotate the child upward to preserve the heap property. A right rotation is used when the child is the left child; otherwise a left rotation.

func (root *semaRoot) queue(addr *uint32, s *sudog, lifo bool) {
    s.g = getg()
    s.elem = unsafe.Pointer(addr)
    s.next = nil
    s.prev = nil
    s.waiters = 0
    var last *sudog
    pt := &root.treap
    for t := *pt; t != nil; t = *pt { // BST walk (①)
        if t.elem == unsafe.Pointer(addr) { // address already present
            if lifo {
                *pt = s
                s.ticket = t.ticket
                // copy other fields from t to s …
            } else {
                if t.waittail == nil {
                    t.waitlink = s
                } else {
                    t.waittail.waitlink = s
                }
                t.waittail = s
                s.waitlink = nil
                if t.waiters+1 != 0 {
                    t.waiters++
                }
            }
            return
        }
        last = t
        if uintptr(unsafe.Pointer(addr)) < uintptr(t.elem) { // go left (②)
            pt = &t.prev
        } else {
            pt = &t.next
        }
    }
    s.ticket = cheaprand() | 1 // random priority (③)
    s.parent = last
    *pt = s
    for s.parent != nil && s.parent.ticket > s.ticket { // rotate up (④)
        if s.parent.prev == s {
            root.rotateRight(s.parent) // right rotation (⑤)
        } else {
            if s.parent.next != s {
                panic("semaRoot queue")
            }
            root.rotateLeft(s.parent) // left rotation (⑥)
        }
    }
}

Dequeue – removing a waiting goroutine

The method

(root *semaRoot) dequeue(addr *uint32) (found *sudog, now, tailtime int64)

removes the first goroutine blocked on addr. The process is:

Search the treap for the node whose elem matches addr. If not found, return nil.

When the node is found, jump to the Found label.

If the node’s waitlink points to another waiting goroutine, replace the current node with that link.

Otherwise rotate the node down to a leaf using right‑or‑left rotations based on child priorities.

Delete the leaf and return the removed sudog together with timing information.

func (root *semaRoot) dequeue(addr *uint32) (found *sudog, now, tailtime int64) {
    ps := &root.treap
    s := *ps
    for ; s != nil; s = *ps { // BST search (①)
        if s.elem == unsafe.Pointer(addr) { // (②)
            goto Found
        }
        if uintptr(unsafe.Pointer(addr)) < uintptr(s.elem) {
            ps = &s.prev
        } else {
            ps = &s.next
        }
    }
    return nil, 0, 0
Found:
    if t := s.waitlink; t != nil { // multiple waiters (③)
        *ps = t
        // … copy fields as needed …
    } else { // rotate to leaf then delete (④‑⑤)
        for s.next != nil || s.prev != nil {
            if s.next == nil || s.prev != nil && s.prev.ticket < s.next.ticket {
                root.rotateRight(s)
            } else {
                root.rotateLeft(s)
            }
        }
        if s.parent != nil {
            if s.parent.prev == s {
                s.parent.prev = nil
            } else {
                s.parent.next = nil
            }
        } else {
            root.treap = nil
        }
        tailtime = s.acquiretime
    }
    // clean up s …
    return s, now, tailtime
}

rotateLeft

rotateLeft

makes the right child y of x the new subtree root, preserving BST order while swapping heap priorities. The transformation is from (x a (y b c)) to (y (x a b) c).

func (root *semaRoot) rotateLeft(x *sudog) {
    // p -> (x a (y b c))
    p := x.parent
    y := x.next
    b := y.prev

    y.prev = x          // (①) y becomes x's left child
    x.parent = y        // (②) x becomes y's parent
    x.next = b          // (③) attach b as x's right child
    if b != nil {
        b.parent = x    // (④) update b's parent
    }

    y.parent = p        // (⑤) re‑link y with original parent
    if p == nil {
        root.treap = y // (⑥) y becomes new root
    } else if p.prev == x {
        p.prev = y      // (⑦) x was left child
    } else {
        if p.next != x {
            throw("semaRoot rotateLeft")
        }
        p.next = y      // (⑦) x was right child
    }
}

rotateRight

rotateRight

is the symmetric operation: it makes the left child x of y the new root, converting (y (x a b) c) into (x a (y b c)).

func (root *semaRoot) rotateRight(y *sudog) {
    // p -> (y (x a b) c)
    p := y.parent
    x := y.prev
    b := x.next

    x.next = y          // (①) x becomes y's right child
    y.parent = x        // (②) y becomes x's child
    y.prev = b          // (③) attach b as y's left child
    if b != nil {
        b.parent = y    // (④) update b's parent
    }

    x.parent = p        // (⑤) re‑link x with original parent
    if p == nil {
        root.treap = x // (⑥) x becomes new root
    } else if p.prev == y {
        p.prev = x      // (⑦) y was left child
    } else {
        if p.next != y {
            throw("semaRoot rotateRight")
        }
        p.next = x      // (⑦) y was right child
    }
}

Analysis

The treap used by the Go runtime is a compact balanced tree that requires only left and right rotations. This keeps the implementation smaller than red‑black or AVL trees while still delivering logarithmic performance for mutex wait‑queue operations. The enqueue code rotates a newly inserted node upward until the heap property holds; the dequeue code rotates the target node downward to a leaf before removal, which explains the symmetric use of the rotation primitives.

References

Wikipedia: https://en.wikipedia.org/wiki/Treap

Medium visual introduction: https://medium.com/carpanese/a-visual-introduction-to-treap-data-structure-part-1-6196d6cc12ee

CP‑Algorithms treap article: https://cp-algorithms.com/data_structures/treap.html

Go source sema.go (semaRoot definition): https://github.com/golang/go/blob/master/src/runtime/sema.go#L40