|
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 ![Smile | :)](https://www.codeproject.com/script/Forums/Images/smiley_smile.gif)
|
|
|
|
|
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 />
}
|
|
|
|
|
![Go to Parent](https://www.codeproject.com/App_Themes/CodeProject/Img/arrow-up24.png) 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.
|
|
|
|
|
![Go to Parent](https://www.codeproject.com/App_Themes/CodeProject/Img/arrow-up24.png) 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
|
|
|
|
|
roman.wagner wrote: one thing i remember was the problem with removing elements
Yeah, didn't feel like implementing that feature, as my primary objective was to explain how the growing is optimized.
roman.wagner wrote: to avoid unwanted references
Also a good spot. Another thing I didn't feel like implementing.
I will add both ideas to the bottom of my article if/when I update it. And you just reminded me that I didn't mention that SlimList can't have a capacity set to an arbitrary value (will always be rounded up to 2^x). Just writing that down here as a note to myself for later when I update the article.
By the way, you mention that this is an old idea. While I'm sure it's been thought of before, I could not find it implemented anywhere. Although part of the problem was probably that I couldn't really find the right terms to search for it. If you can find it implemented anywhere else or described anywhere else, I would gladly add links to my article so that readers could get an alternative perspective on the same data structure. Thanks for your comments!
Visual Studio is an excellent GUIIDE.
|
|
|
|
|
have you read the documentation on the List Capacity property? To avoid the array resize problem, set your anticipated capacity after initialization, then add your items. If loading the items from a database you should know the count before adding the items. If you are adding items dynamically as a user utilizes your application you can code an educated guess based on your use cases.
http://msdn.microsoft.com/en-us/library/y52x03h2.aspx[^]
|
|
|
|
|
Mike Lang wrote: have you read the documentation on the List Capacity property
Yes.
Mike Lang wrote: If you are adding items dynamically as a user utilizes your application you can code an educated guess based on your use cases
One does not always know the exact size of the list. Much of the time, one does not even know the approximate size of the list. You get more than 2x off on your guess, and the SlimList suddenly becomes useful. Your vote of one is narrow minded and based on incorrect assumptions, just as you would have me believe the premise of my article is.
Visual Studio is an excellent GUIIDE.
|
|
|
|
|
When I was reading through the article I also had the feeling that in most cases the memory consumption and specifically the new allocation @ double size can be prevented as you have a pretty good idea of what data to expect and as such set the capacity.
On the other hand I recognize the fact that this is not always the case and as we all know, even though memory is cheap, it is easy to consume huge amounts using a default list implementation in your code.
Though I will not start using this implementation as "my default" I'll sure keep it in mind when I have to (refactor?) create some thing that possibly takes huge amounts of records but may often be used for small quantities.
It's a same the .Net Micro framework doesn't support generics, this would fit in these systems rather nicely.
Cheers,
AT
Cogito ergo sum
|
|
|
|
|