Optimisations to the pdu queues
authorMark Hills <mark.hills@framestore.com>
Tue, 7 Jan 2014 10:23:46 +0000 (10:23 +0000)
committerRonnie Sahlberg <ronniesahlberg@gmail.com>
Fri, 4 Apr 2014 00:51:04 +0000 (17:51 -0700)
commitaec45c6274bffc92fc1595a95d043e8aae292451
treeda977f771674cb2f4a627ef88043ba3eb8da7abe
parent2c0f57fa33371a55b798a9cca14a3d58e6b3cb26
Optimisations to the pdu queues

When making many concurrent requests (as is likely in any performance
criticial application), the use of SLIST_REMOVE and SLIST_ADD_END are
a severe bottleneck because of their linear search.

I considered using a double-linked list but it was unnecessary to
allocate the additional memory for each list entry.

Instead, continue to use a single-linked list but retain:

* a pointer to the end of the list; and
* a pointer to the previous entry during a linear search.

The former would makes append operations O(1) time, and the latter
does the same for removal. We can do this because removal only happens
within the linear search, and there is no random access to the queue.
include/libnfs-private.h
lib/init.c
lib/pdu.c
lib/socket.c