FC27: SegmentedList<T>

Yet another list class to avoid LOH allocation

Author

Feng Yuan
August 18, 2023

In the last episode discussing the new MemoryCache implementation, we mentioned there are four lists in the trimming code which could land in large object heap. So how do you optimize that? There are two ways to do it, reuse the lists or switch to use segmented lists.

Segmented data structure is a very useful tool in reducing allocation, reducing memory usage, minimizing data copying, reducing garbage collection time. If you think about it, our memory is paged, our disk is divided into sections, our buildings are divided into stories. So why not turning out data structure into segmented?

Here is a simple implementation of SegmentedList:

Data in the segmented list is stored in array of arrays. Segment size is restricted to powers of two, so we can use shifting and masking to replace more expensive division and module operations.

Here is data access:

Resizing:

Enumerator implementation:

Quite simple. The key to notice is to keep common operations as small/fast as possible.

Performance tests:

Here we’re comparing the performance of three list usage scenarios:

  1. Growing List from empty, resizing into LOH.

  2. Growing SegmentedList from empty.

  3. Pre-allocate List with exact capacity, LOH.

Test results:

SegmentedList is using the least CPU by far, List(size) is allocating the least, but almost as expensive as growing list in CPU.

SegmentedList is only using 2.53% more memory than allocating List with known capacity.

Notice growing List from empty is using 209% more memory than allocating with capacity. The worst case is 300%.

So SegmentedList is a clear winner.

Here is another advantage of using segmented data structure we’re not taking advantage of yet: the arrays can be easily reused.