How to efficiently resize an array of values, without boxing, used within a Dictionary

Question

In the code below, Pages is defined as

 public SortedDictionary<DateTime, float[]> Pages { get; set; }

I am trying to dynamically increase the size of this array. Can anyone tell how to increase the sized of the innermost float[]?

 var tt = currentContainer.Pages[dateTime];
 Array.Resize<float>(ref tt, currentContainer.Pages.Count + 1);

Fail 1

I tried the following code and get index out of range exception

    SortedDictionary<DateTime, float[]> Pages = new SortedDictionary<DateTime,float[]>();
    float[] xx = new float[1];
    xx[0] = 1;
    DateTime tempTime = DateTime.UtcNow;
    Pages.Add(tempTime, xx);
    var tt = Pages[tempTime];
    Array.Resize<float>(ref tt, Pages.Count + 1);
    Pages[tempTime][1] = 2;

Fail 2

The following gives a compile time error (property, index, or dynamic member can't be used as a ref value)

    SortedDictionary<DateTime, float[]> Pages = new SortedDictionary<DateTime,float[]>();
    float[] xx = new float[1];
    xx[0] = 1;
    DateTime tempTime = DateTime.UtcNow;
    Pages.Add(tempTime, xx);
    var tt = Pages[tempTime];
    // The line below is different from Fail 1 above ... compile time error
    Array.Resize<float>(ref Pages[tempTime], Pages.Count + 1);
    Pages[tempTime][1] = 2;

Question

What is the most performant answer to resize this array?

Would the answer change if it's likely that the final size will be 100-200 floats or 700-900 floats?

What if I change my allocation size from +1 to +128? .. or larger?

Is there a reason that you don't just use `SortedDictionary>` instead? You wouldn't need to resize anything. Just call Add() on the list. ??? — Brian Genisio, Jan 18 '11 at 02:27
Does List, or Linked list guarantee the order of the floats? That is very important to me. — makerofthings7, Jan 18 '11 at 02:30
List will cause a lot of boxing/unboxing for my float value type. Probably not the best choice — makerofthings7, Jan 18 '11 at 02:35
Using generic collections won't cause boxing/unboxing to occur. When you specify List the underlying array type of List is actually of type float. Using a non-generic, weak typed collection such as ArrayList would cause an inordinate amount of boxing/unboxing. Your best bet here really is to go with a List. — Wes P, Jan 18 '11 at 02:42
If you declare the List to take type float it won't cause boxing — Rob, Jan 18 '11 at 02:43
I don't understand what MSDN is saying re: List vs ArrayList ... something about the 500th element: http://msdn.microsoft.com/en-us/library/6sh2ey19.aspx — makerofthings7, Jan 18 '11 at 02:45
The List implementation takes up memory space with its additional methods and functionality. When the list reaches around 500 elements, the memory saved by _not_ boxing/unboxing overtakes the implementation size. In short, a List with 500+ elements takes less memory to store than an ArrayList with the same number of elements, _as_ _well_ as the saved time from not having to box/unbox. — Rob, Jan 18 '11 at 02:50
Is it true to say that, in short, an ArrayList is more efficient for less than 500 objects of a value type? — makerofthings7, Jan 18 '11 at 02:57

KV Prajapati · Accepted Answer · 2011-01-18T02:44:24.493

7

Use List<T>,

Example,

SortedDictionary<DateTime, List<float>> data;

data = new SortedDictionary<DateTime, List<float>>();

data.Add(DateTime.Now, new List<float>() { 11.4f, 322.3f, 33.5f });

EDIT:

How to get/set values from the list?

List<float> a = new List<float>()
{
  10.2f,20.3f
};

float v1 = a[0];
float v2 = a[1];

Console.WriteLine("{0} {1}", v1, v2);

a[0] = 90.40f;
Console.WriteLine("{0} {1}", a[0],a[1]);

edited Jan 18 '11 at 02:44

answered Jan 18 '11 at 02:28

KV Prajapati

93,659
19
148
186

Does List, or Linked list guarantee the order of the floats? That is very important to me.. – makerofthings7 Jan 18 '11 at 02:29
+1 using List. Both List and LinkedList preserve order (unlike Dictionary and HashSet). List is more like array... – Alexei Levenkov Jan 18 '11 at 02:31
+1 Brian. @makerofthings7 : It represents a strongly typed list of objects that can be accessed by index. – KV Prajapati Jan 18 '11 at 02:32
1

List will cause a lot of boxing/unboxing for my float value type. Probably not the best choice. – makerofthings7 Jan 18 '11 at 02:35
@makerofthings7 - I think you misunderstood the usage of List. – KV Prajapati Jan 18 '11 at 02:43
See this for more explanation http://stackoverflow.com/questions/4403055/boxing-unboxing-and-generics – Divi Jan 18 '11 at 02:49
Thanks Divi, reading now. See the link I posted under the question regarding MSDN and the 500 object mention. That is throwing me off. – makerofthings7 Jan 18 '11 at 02:52
@Divi- It is all aobut usage of (memory)stack/heap. – KV Prajapati Jan 18 '11 at 02:59
So would I be a nitpick if I went with ArrayList if I average less than 300 objects? Is the benefit on MSDN's link focused on memory usage, or performance? – makerofthings7 Jan 18 '11 at 03:04
1

If you go to ArrayList, you start to box/unbox. Stick with `List`. This level of optimization is only necesecary if you know for sure that the code is a bottleneck. `List` is your friend. – Brian Genisio Jan 18 '11 at 10:57

David Yaw · Answer 2 · 2011-01-18T02:52:47.267

3

First, do consider using a Dictionary<DateTime, List<Float>>, instead of the array. Since your code examples all involved expanding the array size by 1, that implies to me that you're going to resize the arrays many times to get to their final size. If that's the case, then choosing a container that can expand on its own, and can do so efficiently, is going to be better.

Second, all your examples are using array lengths one greater than the number of items in the dictionary. That's an unusual relationship, are you sure that a Dictionary<DateTime, (some group of floats)> is the proper container?

That said, here's how to resize the array inside a Dictionary.

SortedDictionary<DateTime, float[]> Pages = new SortedDictionary<DateTime,float[]>();
DateTime date = DateTime.UtcNow;

float[] arr = Pages[date];
Array.Resize<float>(ref arr, arr.Length + 1);
Pages[date] = arr; // [] overwrites the old value, unlike Add().

edited Jan 18 '11 at 02:52

answered Jan 18 '11 at 02:32

David Yaw

27,383
4
60
93

Will frequent resize operations put pressure on the stack or the heap in this case? – makerofthings7 Jan 18 '11 at 02:39
On the heap. Or more specifically, you're making extra work for the garbage collector. – David Yaw Jan 18 '11 at 02:52
Based on what I'm seeing & reading, I'm comparing ArrayList, List, and this method. I'll be doing some analysis to see if I have more than 500 items in an Array to justify the List – makerofthings7 Jan 18 '11 at 03:00
To answer your question, yes, I think that is the right choice container for my implementation. I am collecting data at a specific point in time. Each datapoint is a float. The position of the float in the array gives it meaning. – makerofthings7 Jan 18 '11 at 03:14
After testing, this seems to be the most performant solution compared to List if I increase my allocation size from +1 to +10 and keep the objects less than 300. – makerofthings7 Jan 18 '11 at 03:29
If you are collecting data at a specific point in time, why isn't `Dictionary` appropriate? If you have sensors, wouldn't the array length be a constant , not changing? (I don't mean to harp on this, it's just a rather unusual data structure.) – David Yaw Jan 18 '11 at 03:39

score 1 · Answer 3 · answered Jan 18 '11 at 02:30

1

Array.Resize(ref tt, Pages.Count + 1); Pages[tempTime] = tt;

answered Jan 18 '11 at 02:30

Alexei Levenkov

98,904
14
127
179

Will frequent resize operations put pressure on the stack or the heap in this case? – makerofthings7 Jan 18 '11 at 02:38
List will do much better work in resizng in relation to heap/CPU. If you call Array.Resize often (especially if you grow it by 1 as in your sample) it will put serious pressure on memory allocation and CPU for copying a lot of data. – Alexei Levenkov Jan 18 '11 at 17:57

Divi · Answer 4 · 2011-01-18T02:35:48.627

1

Instead of

public SortedDictionary< DateTime, float[]> Pages { get; set; },

you could use

public SortedDictionary< DateTime, List< float>> Pages { get; set; },

so you won't have to resize and if you still want to access it as an array, you can always use the ToArray() of the List class.

Hope this helps

edited Jan 18 '11 at 02:35

answered Jan 18 '11 at 02:30

Divi

7,621
13
47
63

List will cause a lot of boxing/unboxing for my float value type. Probably not the best choice. – makerofthings7 Jan 18 '11 at 02:39
When it comes to collections, generics make it possible to avoid boxing by utilizing actual T[] arrays. List for example uses T[] array to store its contents. http://stackoverflow.com/questions/4403055/boxing-unboxing-and-generics The array, of course, is a reference type and is therefore (in the current version of the CLR, yada yada) stored on the heap. But since it's a T[] and not an object[], the array's elements can be stored "directly": that is, they're still on the heap, but they're on the heap in the array instead of being boxed and having the array contain references to the boxes. – Divi Jan 18 '11 at 02:47
+1 for your links and comments on this post as a whole... Thanks! – makerofthings7 Jan 18 '11 at 03:01

score 1 · Answer 5 · answered Jan 18 '11 at 02:45

I would use a List as suggested in the other answers. The reason you can't change the array with Array.Resize() is that it copies the array into a new array, for which it returns the reference for (Reflector output below) - so unless you re-assign the new value to Pages[tempTime] you are out of luck.

[ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
public static void Resize<T>(ref T[] array, int newSize)
{
    if (newSize < 0)
    {
        throw new ArgumentOutOfRangeException("newSize", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
    }
    T[] sourceArray = array;
    if (sourceArray == null)
    {
        array = new T[newSize];
    }
    else if (sourceArray.Length != newSize)
    {
        T[] destinationArray = new T[newSize];
        Copy(sourceArray, 0, destinationArray, 0, (sourceArray.Length > newSize) ? newSize : sourceArray.Length);
        array = destinationArray;
    }
}

How to efficiently resize an array of values, without boxing, used within a Dictionary

5 Answers5