ChunkedList
A new type of collection is available in a new library: ChunkedList<T>. It was created as a result of searching for processes that could be optimized, and the realization of how poorly a LinkedList<T> performs on modern computers. At the same time, the List<T> structure, while often outperforming LinkedList<T> in many cases, is not desireable. The conclusion was to create a new type of collection that supports both the benefits of using a LinkedList<T>, with the performance of the List<T>, or, as shown below, outperforming both.
ChunkedList Performance
The ChunkedList<T> is a generic data structure that is optimized for performance. It combines features from the LinkedList<T> structure, with features of the List<T> structure.
The LinkedList<T> structure generates nodes for each element, and arranges them in a linked list. It is very straightforward to add and remove elements. But the structure requires a lot of memory overhead, especially if storing small elements. It is also inefficient to process, as elements are not stored closely together, not allowing processor caches to be utilized efficiently.
The List<T> structure on the other hand, stores all elements in a single array internally. This makes access much faster. But adding elements can require the internal buffer to be resized, which can be a costly operation. To avoid this, the size of the increase grows as elements are added (i.e. size is doubled).
The ChunkedList<T> combines the two structures. Instead of attempting to have a single internal array, which requires resizing, the list creates chunks, and links the chunks together in a linked list of chunks. This allows for elements within a chunk to be stored closely together, while avoiding the need to resize the internal buffer, avoiding the necessary copying of data each time that happens.
Following are some performance benchmarks done, comparing the performance of the ChunkedList<T> structure, with the LinkedList<T> and List<T> structures. The ChunkedList<T> structure has comparable interfaces, allowing it to fit in code that uses either of the LinkedList<T> or List<T> structures. You can find the code of the ChunkedList<T> structure in the IoTGateway repository. The same repository also contains unit tests and the following benchmarking tests. You can also use the collection via its nuget.
The following benchmarks were done on a Windows 11 Intel i9 laptop machine, in Release mode. Different performance results may occur on different types of machines, and in different build modes, and for different processors. The benchmarks tests are done first on a small number of elements, to test how the structure works for small number of elements, and then does the same thing for a larger set of elements. The times are then compared to compute a relative performance (in percent) between the ChunkedList<T> and the LinkedList<T> and List<T> structures.
For all graphs, the x-axis represents the number of elements, and the y-axis represents the relative performance, in percent. An additional black line parallel to the x-axis marks the 100% level, where the lists perform equally. If the colored graph lies above this line, the ChunkedList<T> structure performs better than the structure represented by the graph. If the colored graph lies below the line, the ChunkedList<T> structure performs worse. The hidden implementations explain the variations of the curves, as memory exceed internal caches, or buffers have to be resized. The graphs are colored as follows:
Adding elements (last)
Simple addition of elements (last in the list):
Enumerating elements using an enumerator
Enumerating elements in a list sequentially:
Enumerating elements using ForEach
Enumerating elements in a list sequentially using ForEach() (not available in LinkedList, so enumeration is performed using an enumerator):
Enumerating elements using ForEachChunk
Enumerating elements in a list sequentially using ForEachChunk(), giving the ChunkedList<T> an edge. (Not available in LinkedList, so enumeration is performed using an enumerator, or List, where enumeration is done using ForEach()):
Enumerating elements using nodes
The LinkedList<T> and ChunkedList<T> permit the enumeration of content using a linked list of node objects that point to each individual element (LinkedList<T>) or each chunk (ChunkedList<T>). This iteration is compared to the ForEach() method of List<T>:
Checking if list contains en element
The Contains() method is used to check if a list contains an element:
Removing elements randomly
Removing elements randomly using the Remove() method:
Removing first elements
Removing first elements using the RemoveFirst() method (or RemoveAt() for List):
Note: The ChunkedList<T> structure outperforms the LinkedList<T> structure, even for this type of linked-list operation.
Note 2: The List<T> structure quickly diverges in performance for this operation. It is not suitable for implementing a FIFO queue, for instance.
Removing last elements
Removing last elements using the RemoveLast() method (or RemoveAt() for List):
Note: The ChunkedList<T> structure outperforms the LinkedList<T> structure, even for this type of linked-list operation.
Adding elements (first)
Simple addition of elements first in the list (or using Insert() for List):
Note: The ChunkedList<T> structure outperforms the LinkedList<T> structure, even for this type of linked-list operation.
Note 2: The List<T> structure quickly diverges in performance for this operation. It is not suitable for implementing queues or priority queues, for instance, where you process items from either end of the list.
Index operations (get/set)
Index operations using this[Index] is not available in the LinkedList<T> structure, so the benchmark comparison is only done between the ChunkedList<T> and List<T> structures:
Finding elements
Finding elements uses the IndexOf method for for ChunkedList<T> and List<T>, and the Find method for LinkedList<T>:
Finding last elements
Finding last elements uses the LastIndexOf method for for ChunkedList<T> and List<T>, and the FindLast method for LinkedList<T>:
Removing items by index
Removing items from their indices (RemoveAt() method) is not available in LinkedList<T>:
Inserting items by index
Inserting items by index (Insert() method) is not available in LinkedList<T>:
Adding a range of items
Adding a range of items (AddRange() method) is not available in LinkedList<T>. Both List<T> and ChunkedList<T> structures are optimized for adding ranges originating from arrays. A benchmark of this operation follows first:
A second benchmark is performed when the range is an enumeration not based on an array:
Copying elements to an array
Copying elements to an array using the CopyTo() method:
Creating an array of elements
Creating an array containing the elements of a list, using the ToArray() method (CopyTo method for LinkedList):
