|
One of the problems that this implementation faces is that as it creates "jagged" arrays in order to store new elements, they will probably reside in different and distant memory locations, resulting in poor memory performance.
On the contrary, doubling the capacity will occur a low amortized cost compared with the cost of the memory page faults. Superscalar cpus will probably benefit more from the standard List<t> implementation.
So perhaps one way is to suggest different increase factors to the existing implementation rather than implementing the suggested solution.
Good implementation though.
|
|
|
|
|
I agree with the general idea that there are performance issues to consider. However, I will address a few of your concerns below.
Member 8118454 wrote: One of the problems that this implementation faces is that as it creates "jagged" arrays in order to store new elements, they will probably reside in
different and distant memory locations, resulting in poor memory performance
In theory that could be problematic; however, the number of these arrays is minimal (for most collections, even large ones, you could count the number jagged arrays on your fingers and toes). There is a performance problem with calculating which of those jagged arrays to address, however, as it uses some math operations that are slow. On the other hand, I addressed this in the article and indicated a workaround for processors which support the BSR assembly command. In effect, the small number of jagged arrays means that processors can still load large sequential chunks of the arrays for boosted performance, and the BSR support would mean that the calculation to perform the lookup would be fast too. Another consideration is that some operations, such as iterators, could be implemented to be very nearly as performant as standard Lists (IIRC, I avoided doing that to keep the code simple and easy to understand, given that the value of this article is more academic than pragmatic).
Member 8118454 wrote: Superscalar cpus will probably benefit more from the standard List<T> implementation
Like I mention above, the fact that there are multiple jagged arrays is somewhat tempered by the fact that there are very few of them. Still, it is true that the standard List implementation will always be faster, though the difference does not have to be great. One would only really want to use a SlimList where memory is very, very limited.
Member 8118454 wrote: So perhaps one way is to suggest different increase factors to the existing implementation rather than implementing the suggested solution
I'm sure Code Project has plenty of room on their servers for new articles, should you think of something.
Member 8118454 wrote: Good implementation though
Thanks.
|
|
|
|
|
|
For no other reason than to counter T-luvs downvote.
|
|
|
|
|
Thanks for that, Marcus. However, I am somewhat conflicted about this, because I personally avoid countering votes (sometimes I too succumb to countering though). I see it as being an example of two wrongs not making a right, and voting my article a 5 for any reason other than it deserving a 5 seems in some ways right and in some ways wrong (hence my being conflicted rather than being categorically opposed to your 5-vote). I'm sure T-luv will get bored and stop voting my stuff down eventually, and I have a large enough reputation that his votes are about the same as a mosquito biting a rhino's behind. I do appreciate your support, but I think the best way you can provide it in the future is to vote on anything T-luv posts which you think is invalid and to respond to his claims with your elicidations. In fact, you have already done some of that and I thank you.
|
|
|
|
|
No worries. I just figured that my minuscule rep score should be just about enough to counter his 1s...
I wasn't, now I am, then I won't be anymore.
|
|
|
|
|
My vote of 1 for poor writing, subject matter is not relevant and SlimList has very poor performance.
T-luv
Put the lime in the coconut, then you feel better . . . Harry Nilsson
|
|
|
|
|
I know why you chose to come here and downvote this article. That is childish. You may disagree wholeheartedly on the authors comments on other articles, and like you, I disagree very much with the arrogance that his posts sometimes display. But I suggest you should be a big boy too and not downvote someone just because you're angry at something they have done elsewhere. It seriously jeopardizes the integrity of the site when people do this. I'm not saying this to flame you, I'm saying this because I don't want to see behavior like this propagate across the site.
Cheers.
I wasn't, now I am, then I won't be anymore.
|
|
|
|
|
I agree completely, and thank you for your support of Code Project. I too believe that votes should be cast to the content they are voting on (e.g., on the arrogant post rather than on the unrelated article).
|
|
|
|
|
Thank you very much for your nice comments
|
|
|
|
|
T-luv posted this same comment twice. For my response, see here.
|
|
|
|
|
My vote of 1 for poor writing, subject matter is not relevant and SllimList has very poor performance.
|
|
|
|
|
For those wondering why T-luv voted my article a 1, please read the comments at the bottom of "Understanding and Using .NET Partial Classes". (see the edit below for more info) As I'm sure T-luv would recommend, form your own opinions.
T-luv wrote: poor writing
In what way do you recommend I improve my writing? Did I make a bunch of typos, grammar errors, or should I use Old English in a different font?
T-luv wrote: subject matter is not relevant
Not relevant to what? To you? Then don't read the article.
T-luv wrote: SllimList has very poor performance
In what sense? The memory performance is as I state, better than List in most cases. The speed of the operations are slower than List, true, but being faster than List was not the point of this data structure. It could be implemented faster, I'll give you that, but it will never be faster than List without a change in CPU architecture. And like I said in the article, I do not intend to make every optimization to speed possible for this data structure, as that is not the point of it at all.
EDIT: The artile I linked to above but have since crossed out was deleted because it was plagiarised, so you can no longer see the messages at the bottom of it.
|
|
|
|
|
While reading about SWAR[^], I found the following algorithms for computing the base-2 log with integer math...
int CountOnes(uint32 x)
{
x -= ((x >> 1) & 0x55555555);
x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
x = (((x >> 4) + x) & 0x0f0f0f0f);
x += (x >> 8);
x += (x >> 16);
return (int)(x & 0x0000003f);
}
int Log2Floor(uint32 x)
{
x |= (x >> 1);
x |= (x >> 2);
x |= (x >> 4);
x |= (x >> 8);
x |= (x >> 16);
return (CountOnes(x) - 1);
}
|
|
|
|
|
If all you need is to avoid the peak 3x memory consumption, my RWList data structure does that:
VList data structures in C#[^]
My data structures also enjoy low overhead for small lists of 0, 1 or 2 items.
My implementation uses a linked list of arrays, and when the largest array is full, RWList (or WList, or VList, or RVList) continues to use the old arrays but allocates a new, larger, empty array. Like SlimList, the peak memory use is barely more than 2x. However, to better serve its "persistent list" use case, the maximum array size is currently hard-coded at 1024 elements. Consequently, performance slowly begins to decrease after you exceed about 3000 items.
|
|
|
|
|
You said: "Also, no time is wasted copying elements from the old array to the new array, because each new array only stores new values."
That implies a performance gain by not copying elements, or at least that your alternative is faster than copying the elements. I have to strongly disagree here, and now I see why you have refused to do a performance test. I know I said I wouldn't make one for you, but my curiosity overwhelmed me. So here is some performance test code. It is a console app referencing the code in your download. See my next reply for the results.
using System;<br />
using System.Collections.Generic;<br />
using System.Text;<br />
using Zigrem.Collections;<br />
using System.Diagnostics;<br />
<br />
namespace PerfTest<br />
{<br />
class Program<br />
{<br />
static void Main(string[] args)<br />
{<br />
Console.WriteLine("Starting Performance Tests - Comparing SlimList and List.");<br />
<br />
Console.WriteLine("");<br />
Console.WriteLine("");<br />
Console.WriteLine("Compare Adding items to each collection.");<br />
ListTestAdd(64, 64);<br />
ListTestAdd(64, 64);<br />
ListTestAdd(16777216, 262144);<br />
<br />
SlimListTestAdd(64, 64);<br />
SlimListTestAdd(64, 64);<br />
SlimListTestAdd(16777216, 262144);<br />
<br />
Console.WriteLine("");<br />
Console.WriteLine("");<br />
Console.WriteLine("Compare Inserting items in each collection.");<br />
ListTestInsert(64, 64);<br />
ListTestInsert(64, 64);<br />
ListTestInsert(262144, 4096);<br />
<br />
SlimListTestInsert(64, 64);<br />
SlimListTestInsert(64, 64);<br />
SlimListTestInsert(262144, 4096);<br />
}<br />
<br />
private static void SlimListTestAdd(int count, int reportInterval)<br />
{<br />
Console.WriteLine("");<br />
Console.WriteLine("");<br />
Console.WriteLine("");<br />
Console.WriteLine(string.Format("BEGIN test - SlimList Adding {0} items.", count));<br />
SlimList<int> lst = new SlimList<int>();<br />
Stopwatch w = new Stopwatch();<br />
<br />
w.Start();<br />
for (int i = 0; i < count; i++)<br />
{<br />
lst.Add(i);<br />
if (i % reportInterval == 0)<br />
{<br />
w.Stop();<br />
Console.WriteLine(string.Format("Items: {0}, Duration: {1}, {2}ms",<br />
i, w.Elapsed, w.ElapsedMilliseconds));<br />
<br />
w.Start();<br />
}<br />
}<br />
w.Stop();<br />
Console.WriteLine(string.Format("Items: {0}, Duration: {1}, {2}ms",<br />
count, w.Elapsed, w.ElapsedMilliseconds));<br />
}<br />
private static void SlimListTestInsert(int count, int reportInterval)<br />
{<br />
Console.WriteLine("");<br />
Console.WriteLine("");<br />
Console.WriteLine("");<br />
Console.WriteLine(string.Format("BEGIN test - SlimList Inserting {0} items.", count));<br />
SlimList<int> lst = new SlimList<int>();<br />
Stopwatch w = new Stopwatch();<br />
<br />
w.Start();<br />
lst.Add(0);<br />
for (int i = 1; i < count; i++)<br />
{<br />
lst.Insert(0, i);<br />
if (i % reportInterval == 0)<br />
{<br />
w.Stop();<br />
Console.WriteLine(string.Format("Items: {0}, Duration: {1}, {2}ms",<br />
i, w.Elapsed, w.ElapsedMilliseconds));<br />
<br />
w.Start();<br />
}<br />
}<br />
w.Stop();<br />
<br />
Console.WriteLine(string.Format(" Duration: {0} ({1}ms)",<br />
w.Elapsed, w.ElapsedMilliseconds));<br />
}<br />
<br />
private static void ListTestAdd(int count, int reportInterval)<br />
{<br />
Console.WriteLine("");<br />
Console.WriteLine("");<br />
Console.WriteLine("");<br />
Console.WriteLine(string.Format("BEGIN test - List Adding {0} items.", count));<br />
List<int> lst = new List<int>();<br />
Stopwatch w = new Stopwatch();<br />
<br />
w.Start();<br />
for (int i = 0; i < count; i++)<br />
{<br />
lst.Add(i);<br />
if (i % reportInterval == 0)<br />
{<br />
w.Stop();<br />
Console.WriteLine(string.Format("Items: {0}, Duration: {1}, {2}ms", <br />
i, w.Elapsed, w.ElapsedMilliseconds));<br />
<br />
w.Start();<br />
}<br />
}<br />
w.Stop();<br />
Console.WriteLine(string.Format("Items: {0}, Duration: {1}, {2}ms",<br />
count, w.Elapsed, w.ElapsedMilliseconds));<br />
}<br />
private static void ListTestInsert(int count, int reportInterval)<br />
{<br />
Console.WriteLine("");<br />
Console.WriteLine("");<br />
Console.WriteLine("");<br />
Console.WriteLine(string.Format("BEGIN test - List Inserting {0} items.", count));<br />
List<int> lst = new List<int>();<br />
Stopwatch w = new Stopwatch();<br />
<br />
w.Start();<br />
lst.Add(0);<br />
for (int i = 1; i < count; i++)<br />
{<br />
lst.Insert(0, i);<br />
if (i % reportInterval == 0)<br />
{<br />
w.Stop();<br />
Console.WriteLine(string.Format("Items: {0}, Duration: {1}, {2}ms",<br />
i, w.Elapsed, w.ElapsedMilliseconds));<br />
<br />
w.Start();<br />
}<br />
}<br />
w.Stop();<br />
Console.WriteLine(string.Format(" Duration: {0} ({1}ms)",<br />
w.Elapsed, w.ElapsedMilliseconds));<br />
}<br />
}<br />
}
|
|
|
|
|
here are the results from 1 run. I ran it other times with similar results, but I have not averaged them together. The results are so glaringly obvious. SlimList is about 10 times slower than List when adding items. The following is the test output:
Starting Performance Tests - Comparing SlimList and List.<br />
<br />
<br />
Compare Adding items to each collection.<br />
<br />
<br />
BEGIN test - List Adding 64 items.<br />
Items: 0, Duration: 00:00:00.0000027, 0ms<br />
Items: 64, Duration: 00:00:00.0000078, 0ms<br />
<br />
<br />
BEGIN test - List Adding 64 items.<br />
Items: 0, Duration: 00:00:00.0000022, 0ms<br />
Items: 64, Duration: 00:00:00.0000120, 0ms<br />
<br />
<br />
BEGIN test - List Adding 16777216 items.<br />
Items: 0, Duration: 00:00:00.0000016, 0ms<br />
Items: 262144, Duration: 00:00:00.0117065, 11ms<br />
Items: 524288, Duration: 00:00:00.0249682, 24ms<br />
Items: 786432, Duration: 00:00:00.0338601, 33ms<br />
Items: 1048576, Duration: 00:00:00.0494562, 49ms<br />
Items: 1310720, Duration: 00:00:00.0588287, 58ms<br />
Items: 1572864, Duration: 00:00:00.0677689, 67ms<br />
Items: 1835008, Duration: 00:00:00.0773168, 77ms<br />
Items: 2097152, Duration: 00:00:00.0974447, 97ms<br />
Items: 2359296, Duration: 00:00:00.1067171, 106ms<br />
Items: 2621440, Duration: 00:00:00.1156389, 115ms<br />
Items: 2883584, Duration: 00:00:00.1245459, 124ms<br />
Items: 3145728, Duration: 00:00:00.1337901, 133ms<br />
Items: 3407872, Duration: 00:00:00.1427332, 142ms<br />
Items: 3670016, Duration: 00:00:00.1519112, 151ms<br />
Items: 3932160, Duration: 00:00:00.1608335, 160ms<br />
Items: 4194304, Duration: 00:00:00.1916967, 191ms<br />
Items: 4456448, Duration: 00:00:00.2165018, 216ms<br />
Items: 4718592, Duration: 00:00:00.2260960, 226ms<br />
Items: 4980736, Duration: 00:00:00.2349974, 234ms<br />
Items: 5242880, Duration: 00:00:00.2442005, 244ms<br />
Items: 5505024, Duration: 00:00:00.2533492, 253ms<br />
Items: 5767168, Duration: 00:00:00.2622900, 262ms<br />
Items: 6029312, Duration: 00:00:00.2734931, 273ms<br />
Items: 6291456, Duration: 00:00:00.2823945, 282ms<br />
Items: 6553600, Duration: 00:00:00.2915697, 291ms<br />
Items: 6815744, Duration: 00:00:00.3007063, 300ms<br />
Items: 7077888, Duration: 00:00:00.3096332, 309ms<br />
Items: 7340032, Duration: 00:00:00.3188276, 318ms<br />
Items: 7602176, Duration: 00:00:00.3277313, 327ms<br />
Items: 7864320, Duration: 00:00:00.3374705, 337ms<br />
Items: 8126464, Duration: 00:00:00.3472337, 347ms<br />
Items: 8388608, Duration: 00:00:00.3979916, 397ms<br />
Items: 8650752, Duration: 00:00:00.4084236, 408ms<br />
Items: 8912896, Duration: 00:00:00.4173041, 417ms<br />
Items: 9175040, Duration: 00:00:00.4268254, 426ms<br />
Items: 9437184, Duration: 00:00:00.4357551, 435ms<br />
Items: 9699328, Duration: 00:00:00.4447738, 444ms<br />
Items: 9961472, Duration: 00:00:00.4537800, 453ms<br />
Items: 10223616, Duration: 00:00:00.4624702, 462ms<br />
Items: 10485760, Duration: 00:00:00.4735154, 473ms<br />
Items: 10747904, Duration: 00:00:00.4822056, 482ms<br />
Items: 11010048, Duration: 00:00:00.4912023, 491ms<br />
Items: 11272192, Duration: 00:00:00.5002180, 500ms<br />
Items: 11534336, Duration: 00:00:00.5089138, 508ms<br />
Items: 11796480, Duration: 00:00:00.5178674, 517ms<br />
Items: 12058624, Duration: 00:00:00.5265604, 526ms<br />
Items: 12320768, Duration: 00:00:00.5409880, 540ms<br />
Items: 12582912, Duration: 00:00:00.5499531, 549ms<br />
Items: 12845056, Duration: 00:00:00.5587506, 558ms<br />
Items: 13107200, Duration: 00:00:00.5678260, 567ms<br />
Items: 13369344, Duration: 00:00:00.5767923, 576ms<br />
Items: 13631488, Duration: 00:00:00.5854853, 585ms<br />
Items: 13893632, Duration: 00:00:00.5964403, 596ms<br />
Items: 14155776, Duration: 00:00:00.6054453, 605ms<br />
Items: 14417920, Duration: 00:00:00.6141328, 614ms<br />
Items: 14680064, Duration: 00:00:00.6231372, 623ms<br />
Items: 14942208, Duration: 00:00:00.6318247, 631ms<br />
Items: 15204352, Duration: 00:00:00.6407593, 640ms<br />
Items: 15466496, Duration: 00:00:00.6494493, 649ms<br />
Items: 15728640, Duration: 00:00:00.6601492, 660ms<br />
Items: 15990784, Duration: 00:00:00.6694468, 669ms<br />
Items: 16252928, Duration: 00:00:00.6781342, 678ms<br />
Items: 16515072, Duration: 00:00:00.6874099, 687ms<br />
Items: 16777216, Duration: 00:00:00.6963192, 696ms<br />
<br />
<br />
<br />
BEGIN test - SlimList Adding 64 items.<br />
Items: 0, Duration: 00:00:00.0023726, 2ms<br />
Items: 64, Duration: 00:00:00.0024422, 2ms<br />
<br />
<br />
<br />
BEGIN test - SlimList Adding 64 items.<br />
Items: 0, Duration: 00:00:00.0000022, 0ms<br />
Items: 64, Duration: 00:00:00.0000270, 0ms<br />
<br />
<br />
<br />
BEGIN test - SlimList Adding 16777216 items.<br />
Items: 0, Duration: 00:00:00.0000047, 0ms<br />
Items: 262144, Duration: 00:00:00.1015908, 101ms<br />
Items: 524288, Duration: 00:00:00.1950373, 195ms<br />
Items: 786432, Duration: 00:00:00.2861947, 286ms<br />
Items: 1048576, Duration: 00:00:00.3786970, 378ms<br />
Items: 1310720, Duration: 00:00:00.4721007, 472ms<br />
Items: 1572864, Duration: 00:00:00.5641216, 564ms<br />
Items: 1835008, Duration: 00:00:00.6563459, 656ms<br />
Items: 2097152, Duration: 00:00:00.7484258, 748ms<br />
Items: 2359296, Duration: 00:00:00.8444827, 844ms<br />
Items: 2621440, Duration: 00:00:00.9376747, 937ms<br />
Items: 2883584, Duration: 00:00:01.0332100, 1033ms<br />
Items: 3145728, Duration: 00:00:01.1249429, 1124ms<br />
Items: 3407872, Duration: 00:00:01.2181383, 1218ms<br />
Items: 3670016, Duration: 00:00:01.3116058, 1311ms<br />
Items: 3932160, Duration: 00:00:01.4024268, 1402ms<br />
Items: 4194304, Duration: 00:00:01.5150291, 1515ms<br />
Items: 4456448, Duration: 00:00:01.6202143, 1620ms<br />
Items: 4718592, Duration: 00:00:01.7327727, 1732ms<br />
Items: 4980736, Duration: 00:00:01.8533229, 1853ms<br />
Items: 5242880, Duration: 00:00:01.9856202, 1985ms<br />
Items: 5505024, Duration: 00:00:02.0833949, 2083ms<br />
Items: 5767168, Duration: 00:00:02.1751624, 2175ms<br />
Items: 6029312, Duration: 00:00:02.2737906, 2273ms<br />
Items: 6291456, Duration: 00:00:02.3693452, 2369ms<br />
Items: 6553600, Duration: 00:00:02.4626051, 2462ms<br />
Items: 6815744, Duration: 00:00:02.5551306, 2555ms<br />
Items: 7077888, Duration: 00:00:02.6467450, 2646ms<br />
Items: 7340032, Duration: 00:00:02.7382223, 2738ms<br />
Items: 7602176, Duration: 00:00:02.8330497, 2833ms<br />
Items: 7864320, Duration: 00:00:02.9223862, 2922ms<br />
Items: 8126464, Duration: 00:00:03.0138011, 3013ms<br />
Items: 8388608, Duration: 00:00:03.1051206, 3105ms<br />
Items: 8650752, Duration: 00:00:03.1962570, 3196ms<br />
Items: 8912896, Duration: 00:00:03.3039182, 3303ms<br />
Items: 9175040, Duration: 00:00:03.4299079, 3429ms<br />
Items: 9437184, Duration: 00:00:03.5520229, 3552ms<br />
Items: 9699328, Duration: 00:00:03.6442103, 3644ms<br />
Items: 9961472, Duration: 00:00:03.7333046, 3733ms<br />
Items: 10223616, Duration: 00:00:03.8346870, 3834ms<br />
Items: 10485760, Duration: 00:00:03.9269069, 3926ms<br />
Items: 10747904, Duration: 00:00:04.0183053, 4018ms<br />
Items: 11010048, Duration: 00:00:04.1103578, 4110ms<br />
Items: 11272192, Duration: 00:00:04.2041647, 4204ms<br />
Items: 11534336, Duration: 00:00:04.2952403, 4295ms<br />
Items: 11796480, Duration: 00:00:04.3858054, 4385ms<br />
Items: 12058624, Duration: 00:00:04.4770818, 4477ms<br />
Items: 12320768, Duration: 00:00:04.5692027, 4569ms<br />
Items: 12582912, Duration: 00:00:04.6601618, 4660ms<br />
Items: 12845056, Duration: 00:00:04.7490993, 4749ms<br />
Items: 13107200, Duration: 00:00:04.8464195, 4846ms<br />
Items: 13369344, Duration: 00:00:04.9380812, 4938ms<br />
Items: 13631488, Duration: 00:00:05.0304072, 5030ms<br />
Items: 13893632, Duration: 00:00:05.1203454, 5120ms<br />
Items: 14155776, Duration: 00:00:05.2111645, 5211ms<br />
Items: 14417920, Duration: 00:00:05.3004758, 5300ms<br />
Items: 14680064, Duration: 00:00:05.3935709, 5393ms<br />
Items: 14942208, Duration: 00:00:05.4827309, 5482ms<br />
Items: 15204352, Duration: 00:00:05.5731868, 5573ms<br />
Items: 15466496, Duration: 00:00:05.6643626, 5664ms<br />
Items: 15728640, Duration: 00:00:05.7566604, 5756ms<br />
Items: 15990784, Duration: 00:00:05.8525812, 5852ms<br />
Items: 16252928, Duration: 00:00:05.9458858, 5945ms<br />
Items: 16515072, Duration: 00:00:06.0371843, 6037ms<br />
Items: 16777216, Duration: 00:00:06.1287403, 6128ms
|
|
|
|
|
Mike Lang wrote: SlimList is about 10 times slower than List when adding items
As I said in the article, SlimList is slower than List by a constant factor. You have apparently disovered that constant to be about 10 on your computer. I made no promises that SlimList is faster than List, only that it uses less memory.
While the above message is very thorough, what you have provided is an irrelevant conclusion. While you have reached a perfectly valid conclusion -- that SlimList is slower than List -- it is irrelevant with respect to the article and anything I have stated in the article. In fact, your irrelevant conclusion is redundant, because I state the same conclusion in the article (under the section titled, guess what, "conclusion").
You'll also notice that I offer up a suggestion, near the end of the article, for improving the speed of SlimList (by using the BSR assembly instruction). Read the bottom of the article for a further discussion of why I chose not to implement this speedup.
Visual Studio is an excellent GUIIDE.
|
|
|
|
|
The insert test inserts a value in the first location until all items have been added. The framework List class performs well under high usage. The SlimList has difficulty moving the items around in the list to allow the first element to be inserted.
Is there something wrong with the test, or is SlimList poorly suited to insert items at the beginning?
Below is only a partial result output because the test is just taking waaaay too long to run. I don't have all week to wait for it to complete.
Compare Inserting items in each collection.<br />
<br />
<br />
<br />
BEGIN test - List Inserting 64 items.<br />
Duration: 00:00:00.0000139 (0ms)<br />
<br />
<br />
<br />
BEGIN test - List Inserting 64 items.<br />
Duration: 00:00:00.0000209 (0ms)<br />
<br />
<br />
<br />
BEGIN test - List Inserting 262144 items.<br />
Items: 4096, Duration: 00:00:00.0083326, 8ms<br />
Items: 8192, Duration: 00:00:00.0350100, 35ms<br />
Items: 12288, Duration: 00:00:00.0780236, 78ms<br />
Items: 16384, Duration: 00:00:00.1357692, 135ms<br />
Items: 20480, Duration: 00:00:00.2098691, 209ms<br />
Items: 24576, Duration: 00:00:00.2988606, 298ms<br />
Items: 28672, Duration: 00:00:00.4038401, 403ms<br />
Items: 32768, Duration: 00:00:00.5274511, 527ms<br />
Items: 36864, Duration: 00:00:00.6711713, 671ms<br />
Items: 40960, Duration: 00:00:00.8303418, 830ms<br />
Items: 45056, Duration: 00:00:01.0010962, 1001ms<br />
Items: 49152, Duration: 00:00:01.1892687, 1189ms<br />
Items: 53248, Duration: 00:00:01.3974038, 1397ms<br />
Items: 57344, Duration: 00:00:01.6156193, 1615ms<br />
Items: 61440, Duration: 00:00:01.8583169, 1858ms<br />
Items: 65536, Duration: 00:00:02.1178666, 2117ms<br />
Items: 69632, Duration: 00:00:02.3959531, 2395ms<br />
Items: 73728, Duration: 00:00:02.6967424, 2696ms<br />
Items: 77824, Duration: 00:00:03.0092612, 3009ms<br />
Items: 81920, Duration: 00:00:03.3547727, 3354ms<br />
Items: 86016, Duration: 00:00:03.7083137, 3708ms<br />
Items: 90112, Duration: 00:00:04.0696018, 4069ms<br />
Items: 94208, Duration: 00:00:04.4488430, 4448ms<br />
Items: 98304, Duration: 00:00:04.8464595, 4846ms<br />
Items: 102400, Duration: 00:00:05.2642819, 5264ms<br />
Items: 106496, Duration: 00:00:05.7004557, 5700ms<br />
Items: 110592, Duration: 00:00:06.1508119, 6150ms<br />
Items: 114688, Duration: 00:00:06.6156693, 6615ms<br />
Items: 118784, Duration: 00:00:07.0995936, 7099ms<br />
Items: 122880, Duration: 00:00:07.5992437, 7599ms<br />
Items: 126976, Duration: 00:00:08.1205586, 8120ms<br />
Items: 131072, Duration: 00:00:08.6553126, 8655ms<br />
Items: 135168, Duration: 00:00:09.2081462, 9208ms<br />
Items: 139264, Duration: 00:00:09.7796158, 9779ms<br />
Items: 143360, Duration: 00:00:10.3637453, 10363ms<br />
Items: 147456, Duration: 00:00:10.9662973, 10966ms<br />
Items: 151552, Duration: 00:00:11.5775563, 11577ms<br />
Items: 155648, Duration: 00:00:12.2185998, 12218ms<br />
Items: 159744, Duration: 00:00:12.8911386, 12891ms<br />
Items: 163840, Duration: 00:00:13.5627838, 13562ms<br />
Items: 167936, Duration: 00:00:14.2494669, 14249ms<br />
Items: 172032, Duration: 00:00:14.9568389, 14956ms<br />
Items: 176128, Duration: 00:00:15.6841053, 15684ms<br />
Items: 180224, Duration: 00:00:16.4204640, 16420ms<br />
Items: 184320, Duration: 00:00:17.1825438, 17182ms<br />
Items: 188416, Duration: 00:00:17.9651631, 17965ms<br />
Items: 192512, Duration: 00:00:18.7643228, 18764ms<br />
Items: 196608, Duration: 00:00:19.5764470, 19576ms<br />
Items: 200704, Duration: 00:00:20.4061236, 20406ms<br />
Items: 204800, Duration: 00:00:21.2472194, 21247ms<br />
Items: 208896, Duration: 00:00:22.1321712, 22132ms<br />
Items: 212992, Duration: 00:00:23.0139920, 23013ms<br />
Items: 217088, Duration: 00:00:23.9265702, 23926ms<br />
Items: 221184, Duration: 00:00:24.8496015, 24849ms<br />
Items: 225280, Duration: 00:00:25.7802296, 25780ms<br />
Items: 229376, Duration: 00:00:26.7488105, 26748ms<br />
Items: 233472, Duration: 00:00:27.7232254, 27723ms<br />
Items: 237568, Duration: 00:00:28.7236886, 28723ms<br />
Items: 241664, Duration: 00:00:29.7476397, 29747ms<br />
Items: 245760, Duration: 00:00:30.8131949, 30813ms<br />
Items: 249856, Duration: 00:00:31.9093136, 31909ms<br />
Items: 253952, Duration: 00:00:33.0407984, 33040ms<br />
Items: 258048, Duration: 00:00:34.2563230, 34256ms<br />
Duration: 00:00:35.6398581 (35639ms)<br />
<br />
<br />
<br />
BEGIN test - SlimList Inserting 64 items.<br />
Duration: 00:00:00.0030294 (3ms)<br />
<br />
<br />
<br />
BEGIN test - SlimList Inserting 64 items.<br />
Duration: 00:00:00.0011331 (1ms)<br />
<br />
<br />
<br />
BEGIN test - SlimList Inserting 262144 items.<br />
Items: 4096, Duration: 00:00:04.8155776, 4815ms<br />
Items: 8192, Duration: 00:00:19.4487749, 19448ms<br />
Items: 12288, Duration: 00:00:45.7870318, 45787ms<br />
Items: 16384, Duration: 00:01:25.1184220, 85118ms<br />
Items: 20480, Duration: 00:02:10.3661747, 130366ms<br />
Items: 24576, Duration: 00:03:05.2107527, 185210ms<br />
Items: 28672, Duration: 00:04:09.7475371, 249747ms<br />
Items: 32768, Duration: 00:05:29.1863499, 329186ms<br />
Items: 36864, Duration: 00:06:55.2910400, 415291ms<br />
Items: 40960, Duration: 00:08:36.3846636, 516384ms<br />
Items: 45056, Duration: 00:10:28.9503056, 628950ms<br />
Items: 49152, Duration: 00:12:28.5142150, 748514ms<br />
Items: 53248, Duration: 00:14:39.3812842, 879381ms<br />
Items: 57344, Duration: 00:17:01.8532271, 1021853ms<br />
Items: 61440, Duration: 00:19:33.9243702, 1173924ms
|
|
|
|
|
SlimList and List should have similar performance with regard to insertions. The only difference should be the factor. For each insert at the beginning of the list, both List and SlimList should have O(N) performance (i.e., the length of time it takes to insert an item should be proportional to the number of items in the list). The reason for this performance is that both data structures shift elements in order to perform insertions. That is, they move all the element that already exist in the list up one position.
From my calculations, SlimList appears to be about 630 times slower than List for inserts. That seems a bit odd to me, but since it is a constant number, it is not inconsistent with the conclusions I reach in my article. However, since that is a very large factor, I will investigate to see if I can speed things up a bit. My guess is that List uses low level memory optimizations for shifting array elements while SlimList just does the fastest thing I could code (performs a ton of unnecessary calculations), as I mention in my article:
Article: Many of the functions use clear, but slow code.
Anyway, I'll check out the code and I'll let you know what's causing the slowdown and I may submit a more optimized version.
Visual Studio is an excellent GUIIDE.
|
|
|
|
|
FYI, using Array.Copy seems to have done the trick. For large lists, inserts are roughly the same speed as with List. Still haven't uploaded the code yet... I'll let you know when I do.
|
|
|
|
|
If you could setup a memory profile of using both SlimList and List that would be great. At this point I am not going to bother. The minor memory reduction you may get from using this is never going to be worth the overhead of the apparent performance loss. If SlimList was only 10% slower with your claimed memory reduction it may be worth it in some scenarios, but this is just too much of a performance drain for any application type I can imagine.
|
|
|
|
|
Mike Lang wrote: The minor memory reduction you may get from using this is never going to be worth the overhead of the apparent performance loss
Article: 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.
As I mention in the article, the article is academic in nature. The purpose of the article is to demonstrate that SlimList uses less memory than List and that it does so with only a constant factor penalty to speed performance. And as both you and the article state, this data structure is not well suited to production applications in its current state, as the slowdown is probably never going to be worth the memory gained. This article should only be viewed to understand algorithms and may be used as a starting point for similar algorithms.
That being said, I do have several ideas for speeding up the performance of SlimList. I estimate the speed performance factor difference between List and SlimList can be reduced to about 3x (and almost 1x, or equal, for some operations). However, as this is still relatively poor performance, I'm not going to make that optimization. This article is academic in nature, and should not be viewed otherwise.
Visual Studio is an excellent GUIIDE.
|
|
|
|
|
That sentence only says that the operation of copying is avoided, not that overall SlimList performance is better than List. And I was completely correct in that statement, no copy operation is performed. You may be confusing the copy operation with the array allocation. When capacity increases, a new array is created. However, no elements are actually copied from the old arrays to the new array, as is done with List. Now give me a moment and I will reply to the rest of your posts.
Visual Studio is an excellent GUIIDE.
|
|
|
|
|
one thing i remember was the problem with removing elements.
when removing elements from SlimList the memoryusage does not decrease.
you should remove empty minor arrays.
to avoid permanent allocation of new arrays while doing something like
while(true) { list.Add(myObject); list.Remove(myObject); }
you should remove minor array "i" when minor array "i-1" has lessequal 2^i / 3 items
and to avoid unwanted references to the last element of the list you should
explicitly set
this[this.count-1] = default(T) before decreasing the count member
|
|
|
|
|