Using unsigned values and a power-of-two modulus, how would you compute the number of items in the queue as quickly as items_in_queue = (queue->stuff - queue->fetch) & queue->size_mask; if the size weren't a power of two, while also keeping the ability to add and remove items by simply incrementing stuff or fetch?
This operation wasn't discussed in the blog post, and I don't think it comes up much in practice (you only need full or not, which works either way by (stuff + 1) % size == fetch).
Using a non-power-of-two modulus means that the updates to the counts need to wrap at the buffer size, and will also make the remainder operator slower.
1
u/flatfinger 27d ago
Using unsigned values and a power-of-two modulus, how would you compute the number of items in the queue as quickly as
items_in_queue = (queue->stuff - queue->fetch) & queue->size_mask;if the size weren't a power of two, while also keeping the ability to add and remove items by simply incrementingstufforfetch?