Grab me a Bag

A transmit window stores a sequential series of packets of which any can be requested to be re-transmitted. So taking the engineering approach to answer the question: what is the best container? We test each container available in the glib toolkit for two performance properties: first sequentially adding items to the window, and second randomly accessing items in the window. From this we can draw some pretty graphs

A time penalty occurs for the first block allocations, this is when page faults occur and pages are assigned to the applications process space. Post allocation the time period for allocating remains constant.

Now we have three different allocators for the data in the container, first regular malloc, second a glib slice allocator, and third a pre-populated trash stack. Note that we are running all the tests in one application so only the first run suffers from the page fault penalty. The trash stack usage shows a clear performance advantage, whilst minimal difference between malloc and the slice allocator.

The graph gets rather busy, the y-axis deliberately culled to 0.5μs as the byte array times are 1000% worse. What we can tell is that singly linked lists are fractionally faster the doubly linked, but similar to queues and pointer arrays. Hash tables and byte arrays easily fair the worst.

These tests are all in basic_container.