Use a michael-scott MPMC queue for actor mailboxes #29

New Issue

john · 2025-06-07T21:46:44Z

john commented

2025-06-07 21:46:44 +00:00

Your actor mailboxes have one consumer (the actor) and many producers (any thread calling send_message). That’s exactly the profile of an MPSC (multiple‐producer, single‐consumer) queue. You can implement it lock-free with a single atomic pointer:

typedef struct letter_node {
letter data;
struct letter_node *next;
} letter_node_t;

_Atomic(letter_node_t *) mailbox_head = NULL;

// producer: push to head
void push_letter(letter_node_t node) {
node->next = atomic_load(&mailbox_head);
while (!atomic_compare_exchange_weak(
&mailbox_head, &node->next, node)) { / retry */ }
}

// consumer: grab the list, then reverse it
letter_node_t *grab_all_letters(void) {
letter_node_t *head = atomic_exchange(&mailbox_head, NULL);
// now reverse head → tail to restore FIFO order...
return reversed_list;
}
Pros:

Zero locks in send_message.
Actor just does one atomic swap once per turn, then drains its entire batch.
Cons:

You have to manage your own node pool or allocate per-message.
You need to reverse the list if you want strict FIFO.

Your actor mailboxes have one consumer (the actor) and many producers (any thread calling send_message). That’s exactly the profile of an MPSC (multiple‐producer, single‐consumer) queue. You can implement it lock-free with a single atomic pointer: typedef struct letter_node { letter data; struct letter_node *next; } letter_node_t; _Atomic(letter_node_t *) mailbox_head = NULL; // producer: push to head void push_letter(letter_node_t *node) { node->next = atomic_load(&mailbox_head); while (!atomic_compare_exchange_weak( &mailbox_head, &node->next, node)) { /* retry */ } } // consumer: grab the list, then reverse it letter_node_t *grab_all_letters(void) { letter_node_t *head = atomic_exchange(&mailbox_head, NULL); // now reverse head → tail to restore FIFO order... return reversed_list; } Pros: Zero locks in send_message. Actor just does one atomic swap once per turn, then drains its entire batch. Cons: You have to manage your own node pool or allocate per-message. You need to reverse the list if you want strict FIFO.

Sign in to join this conversation.

1 Participants

Notifications

Due Date

No due date set.

Dependencies

No dependencies set.

Reference: john/cell#29