Proposal: XQueue

Problem

Queues in Linux are currently implemented as a doubly-linked list. Elements are typically added to the end of the list and removed from the beginning.

Advantages:

• Implementation is simple and shared with other list manipulation.
• Objects can be removed from the queue in any order.
• Objects can be placed on any queue.

Disadvantages:

• Removing an element from the queue results in dirtying three cachelines; one in the element that is being removed, one in the element before it in the list and one in the element that is after it in the list.
• Two pointers is 16 bytes on 64-bit systems which is a relatively high price to pay per element in the list. It's reasonable for some objects, and not for others.
• Placing an object on multiple queues simultaneously requires embedding multiple list_heads in the object.

Solution

Define a new data structure based on the xarray, called the xqueue. Adding an object to the tail of the xqueue returns an index for that object. Removing an object from the head returns the object. Objects can also be removed by index. If your use case does not require removing objects by index, the index returned from xq_add() can be thrown away.

The xarray as-is does not satisfy the memory requirements. Once the indices get large, it will waste a lot of memory just to describe which index. The enhancements I intend are:

1. Add an 'unsigned int xa_base' to the xa_node (there is a 4-byte gap between 'exceptional' and 'parent' on 64-bit). When walking down the tree to create a new ID, accumulate the xa_base at each level (wrapping around 0). When removing by ID, subtract the xa_base at each level from the ID (again wrapping around 0). When removing from the head, just remove the leftmost present entry.
2. When removing the

   Comparison:

   • Removing an element from the queue results in dirtying one cacheline.
   • If