Before I start, let me just say this article is not for everyone. If you are looking for a list to use in a production application, move along to a more useful article. If, however, you are interested in data structures, please read on. This article is targeted toward those who would like to deepen their understanding of data structures and algorithms.
Also, please do not tell me that the tester form is coded sloppy (that is unimportant) or that optimizations could be made to specific
SlimList functions (I am aware of those too). The purpose of this article is to present a new data structure, not to optimize it to the extreme or to build a full application. That being said, please feel free to make comments about specific optimizations I could make, and I'll happily add them to the bottom of this article so that others may benefit from your idea.
SlimList is my attempt to improve upon the .NET
List by reducing the amount of memory it consumes. At worst,
List consumes 3x the amount of memory actually stored in the
SlimList reduces this maximum amount to only 2x the amount of memory actually stored in the list. Since
IList, it has most of the features that
List does. That being the case, you can use
SlimList pretty much exactly how you would a
List Uses 3x Memory
List data structure, an array of elements is stored to hold all the elements. When the capacity of the
List is exceeded, a second array that is twice the size of the first one is created. The old array is then copied to the new array and the old array is discarded. So, the array doubles each time the capacity is exceeded. The Reflector screenshots below confirm this is how
List performs size increases (
EnsureCapacity doubles the length and
Capacity performs the copy operation). One might think that only half the memory is being wasted on capacity (i.e., that 2x of the memory is being used). While this is true after the copy operation, it is not true during the copy operation, because both the old array and the new array exist during that time period. Since the new array is twice the size of the old array, a total of 3x the amount of required memory exists during the copy operation.
SlimList remedies this.
SlimList Uses 2x Memory
SlimList uses a different structure than
List to store elements. Rather than an array,
SlimList uses an array of arrays to store elements (sample structure shown in image below). The first array (which I will refer to as the "major" array) is about 32 items long, and each sub-array (which I will refer to as the "minor" arrays) is initialized to
null. After enough elements have been added, the first two elements in the major array are each arrays of size 2 (the first and second columns in the image below). The third is of size 4 (third column below), and the fourth is of size 8 (fourth column below). Each subsequent array is twice the size of the previous. The screenshot above and to the right shows this data structure (as viewed from the Visual Studio debugger). These arrays of exponentially increasing size are the ones that hold the actual data elements.
List creates a new array twice the size of the existing array when capacity is exceeded. A
SlimList, however, creates a new array the same size of the existing elements when capacity is exceeded. Also, no time is wasted copying elements from the old array to the new array, because each new array only stores new values. That is, the existing values stay in their existing arrays, so no copy operation is performed.
Adding to a SlimList
SlimList is created, an array is created, like the one shown below:
private T items = new T;
T is a templated type. So, if you were to specify the type as
int, the array would look something like this:
private int items = new int;
That is a jagged array. The "major" array has 31 "minor" arrays. Each minor array can be a different size. Initially, the minor arrays are all
null. When the first item is added to the
SlimList, the first minor array is initialized to size 2. This would look something like this (also shown as the first column in the above image):
items = new int;
When the second item is added, it is just assigned as the second element in that minor array. When the third item is added, a second minor array needs to be created, which looks like this:
items = new int;
That second minor array happens to be the same size as the first, but all subsequent minor arrays are twice as large as the previous one. So, to manually assign the third element in the
SlimList, the code would look something like this:
items = value;
Whenever the last element of the last minor array gets filled, the next minor array is created. Each minor array gets created with a size equal to the number of elements already in the
SlimList. This means the
SlimList doubles each time the capacity is exceeded. The key advantage it has over
List is that no copy operation must be performed when capacity increases, so less memory is consumed.
SlimList uses less memory than
List, it also uses more processor power, but indexing is still an O(1) operation. In order to access an item at a given index, two indexing operations must be performed. One to index the major array, and one to index the minor array. On top of that, the index of the major array first needs to be calculated. This is done with a base 2 logarithm (since the minor arrays double in size). That calculation looks like the following:
int firstIndex = (index == 0 ? 0 : (int)Math.Truncate(Math.Log(index, 2)));
The second index is calculated as the offset into the minor array.
Qualitative Comparison of SlimList and List
It is not really worthwhile for me to do a quantitative analysis of the
SlimList performance, as this article is purely theoretical. However, here are a few qualitative observations about this data structure:
List uses a peak of 3x the required memory.
SlimList uses only 2x.
SlimList avoids the copy operation that
List performs, which means it will save time in this area.
SlimList requires more calculations to index an item, so
List is faster in this area.
SlimList is more complicated than
List to implement, and it is harder to describe.
SlimList operations have the same big-O notation, although the factor might be different. For example,
SlimList both have an index performance of O(1), but
SlimList would probably be more like 5 * O(1).
These are optimizations which could be done on
SlimList, but that I didn't bother to implement, as they were not required to get
SlimList up and running:
SlimList currently uses
Math.Log to calculate the base 2 log. However, there is an assembly instruction called
BSR (bit scan reverse) which might be used to do this calculation much faster. By counting the number of binary zeroes to the left of a number, you can figure out the base 2 log. Problem is, the instruction is not on all processors, so I decided not to use it. I'm no assembly expert, but the calculation would be performed something like this:
MOV EAX, i BSR EAX, EAX MOV i, EAX
Many of the functions use clear, but slow code. For example, to search through the list, I could have iterated through each minor array in succession. However, I decided just to accept the penalty of performing the index calculations for each item because the code was cleaner (and faster to write).
SlimList has a fairly large overhead (an array of about 32 elements). This could be fixed with a hybrid of
SlimList, but that is an exercise for the reader.
SlimList uses less memory than
List, but it is also slower than
List. If memory is very tight or copy operations are expensive (such as on a hard drive), a
SlimList might be the way to go. Download the code and give it a try if you want. The test application will appear very slow, but that is just because of my poor use of threading. That should not be used as an indicator of actual
SlimList performance. The only purpose of the tester form is to verify that the
SlimList works as advertised. If you have any suggestions or ideas, feel free to leave them below. If you vote low, please give me the courtesy of explaining why you did so and how I might improve this article for a higher vote.
- October 17th, 2009 - Article creation.