|
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
|
|
|
|
|
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
|
|
|
|
|
Just use the framework properly to avoid the resize problem!
|
|
|
|
|
Mike Lang wrote: Just use the framework properly to avoid the resize problem
Hey, grouchy, take your overzealous opinions somewhere else. The .Net Framework cannot solve everything for you. Specifically, setting the initial capacity of List is not always an option that will produce viable results. Say you are even off by 2x. The List will still use 3x the memory and SlimList will only use 2x.
Now please change your vote to something more appropriate. You know, based on the merits of article, not on some unfounded opinion.
Visual Studio is an excellent GUIIDE.
|
|
|
|
|
So what if you are off by 2x. So the list would have to grow once, big deal. Maybe you should just increase your assumed size by 2x. My opinion is well founded with plenty of experience writing real applications and testing performance.
Where are your performance tests that show how much memory or system performance you are saving. Your whole point of the article is that is is better than the framework. So prove it. I'm not going to do the work for you. If you update your post with performance tests that show an improvement I will reconsider my vote score. The tests should be included as code that can be downloaded and verified by others.
|
|
|
|
|
Mike Lang wrote: So the list would have to grow once, big deal
It's not much, but it will change the maximum amount of memory the list uses throughout the program, which may be the difference between a working program and a crashing program on a low memory system. Also, are you even remotely familiar with exponential growth? For one, that "only once" growth will be the biggest of all the other growth. And it will also be as big as the rest of the growths combined. For example:
1 + 2 + 4 + 8 = 15 (the next iteration would have been 16, which is one greater than 15, the sum of every iteration before 16)
Mike Lang wrote: Maybe you should just increase your assumed size by 2x
And if you're off by 3x? And who knows how much you're off by? What about lists that resize based on user interaction (such as a list of enemies in a video game)? Sure, you could use the maximum list size you expect for every programming object you make, but that would hardly be efficient or recommended, especially in systems where different algorithms can take up different amounts of memory at different times. You hardly want each algorithm taking up it's maximum amount of memory the whole time programs are running.
Why would I need performance tests to show the blindingly obvious fact that the peek memory consumption of SlimList will be only 2x while the peek memory consumption of List will be 3x? I've explained that fact in the article and a graph or chart would not add any significant information to the discussion. I could bloody well draw a graph in my head because the behavior of both lists is so predictable. If the memory useage over time were mapped (time is independent variable, memory usage is dependent variable), it would look like discrete steps the doubled each time they increased. And, for List, these steps would each have a thin lip that have a height of 3 times the previous step before returning (very quickly) to a height of 2 times the previous step. Paint a clear enough picture for you?
The "verification" can be done logically by reviewing my article. If a specific area does not make sense, they can post comments at the bottom of my article and I can clarify any confusion they may be having. Not every concept requires a bloody chart to describe.
Visual Studio is an excellent GUIIDE.
|
|
|
|
|
My vote was not meant to say that SlimList does not live up to what you say it does. I really don't know because I don't see any tests that prove how it compares to List. All I see is theory and a demonstration of how it works. That's all nice and good. It seems to make sense from what I have read.
My concern is more that some will hear that this is "faster than List", and interpret that to mean that they should add this to some generic utility component that they reference in every project and then always use in place of List. If they are in a scenario where the SlimList does not give them a direct benefit then they actually hurt the memory of their application because they now have a larger component that uses more memory.
The reality is that in most applications, setting the Capacity and adding your items is likely to be more efficient. However, If you can show that assumption is also wrong via a performance test, then more kudos to you.
A counter balance in your article about performance testing and the inclusion of tests when it works well and when it does not would get a 5 vote from me.
|
|
|
|
|
Mike Lang wrote: My concern is more that some will hear that this is "faster than List"
Article: SlimList uses less memory than List, but it is also slower than List.
If they skip of the first sentence of the conclusion section of the article, that is their fault.
Mike Lang wrote: they now have a larger component that uses more memory
SlimList will use less memory in most cases. I will leave it to the application developers to decide if the few kilobytes that SlimList compiles to is too much. That is not really my concern. Really, though, the article exists to present a concept in a clear and concise manner. The specific code I attach to the article is only of ancillary importance.
Mike Lang wrote: setting the Capacity and adding your items is likely to be more efficient
How about a counter example? Bob starts up a game on his Alienware. He plays with max settings and trounces enemies with his mad skillz, because he is a l337 hax0r. Now Jill starts up that same game on her eMachine. She uses lower settings. Given that her computer has very little memory, she does not fire at enemies as rapidly as Bob, because it slows her computer down to have a bunch of bullets on the screen at once. It turns out that using a bunch of bullets makes the list structures used in the program grow so large that she starts to use virtual memory. Luckily, however, the programmer was kind enough to use data structures that grow based on the need of the user. So, while Jill is not going to get as high of a score as Bob, at least she can still play the game, so long as she fires her weapon less often. If the programmer had decided to set the capacity of the data structures involved to the amount expected to be reached by Bob (effectively using a constant and higher amount of memory), then the game might not even be playable by Jill. I made some simplifications in this example, but you get the idea. Dynamic data structures are useful. Different users have different demands.
Counter example 2. Bob is working on a spreadsheet. It is probably the most massive spreadsheet you have ever seen. It has millions of rows in it. Bob is very efficient at his job because he has enough RAM to support such a spreadsheet. Jill, on the other hand, does not have very much RAM. Luckily, she also does not work with very large spreadsheets. Also good for her is that the programmer used a dynamically growing list data structure to store the rows in her spreadsheet. As she adds rows, that list grows larger and larger. If the list had been designed such that the capacity of the list was set to millions of rows to suit Bob's needs, Jill would have been left in the cold using virtual memory, making her spreadsheet application virtually unusable. Here again, you see that list sizes cannot always be predicted and that growing them dynamically is of use. As far as showing this via a "performance test", I am not going to do that. That dynamic data structures are useful is a basic programming concept that most programmers understand. This is not an article for beginners (I marked it intermediate/advanced), so I'm not going to cover such basic concepts.
Mike Lang wrote: A counter balance in your article about performance testing and the inclusion of tests when it works well and when it does not would get a 5 vote from me.
I feel my article discusses both the pros and the cons of using SlimList very well. It doesn't happen to show performance testing because they are not necessary to convey the concepts, which is the only purpose of the article... not to prove that I'm a excellent programmer who has release a shining product to the world. Performance tests should be done by programmers if they are having performance issues with their applications. I included some graphics to illustrate the concepts presented in the article and adding charts would just be another visualization technique to present those concepts. That would be redundant and I'm not going to do it because some guy has a fetish for charts.
Mike Lang wrote: would get a 5 vote from me
Think about that. By including a few charts or graphs or whatever, you'd change the vote from 1 to 5? Do you really think my article deserves a 1, or are you just voting that to attempt to strong-arm me into making the changes you think should be done to the article? That is not a proper use of the voting system. You should vote what you think the article deserves; you should not vote an article to get your way.
Visual Studio is an excellent GUIIDE.
|
|
|
|
|
aspdotnetdev wrote: Dynamic data structures are useful
Sure they are, just not this one in its current form. This is exactly why List also grows dynamically. List starts relatively small to meet the needs of the average programmer, then it grows if it must. For advanced programmers they can set an initial size to prevent the resize.
aspdotnetdev wrote: Do you really think my article deserves a 1, or are you just voting that to attempt to strong-arm me into making the changes you think should be done to the article
No my 1 vote is because that is all the writing is worth when it doesn't explain how well it compares to the alternative(s). Especially now that I ran a performance test (see other comment), it definitely is not worth a 5. I only expected a minor 10% drop in performance based on your article, which would have been acceptable in some scenarios for the memory gain.
aspdotnetdev wrote: Given that her computer has very little memory, she does not fire at enemies as rapidly as Bob, because it slows her computer down to have a bunch of bullets on the screen at once
With SlimList she may not run out of memory, but her frame rate would be so slow due to the performance issues that she would be too frustrated to even make the game worth playing.
Memory and performance go hand in hand. you can chase one without consideration for the other. It is fine to trade off one for the other given your situation, but both need to remain in a tolerable range.
If you rewrite this to solve the performance issue to within a tolerable range, I'd be happy to review the project again.
|
|
|
|
|