Think twice before to implement some idea – # 1
I’ve already written some posts that show some source code that can be rewritten in a different way and this way to achieve better performance. Now I will open a series with a topic of this post with a number and I’ll post different samples of implementations that I’ll run into and I’ll do some simple tests in order to find which is better. I’m not an expert of the performance improvement and for sure not all my conclusions are correct but let me share my opinion.
Sometime ago I had to improve the performance of a part of the source code in one of our applications and during this process I decided to cache in-memory some data frequently used during the operation that I was optimizing. I needed all the collected information in small arrays by parent id in a hash table. Initially, I used a list to prepare the array and after that each time to call List<T>.ToArray() in order to use the information (it is not important why it is a matter of other implementations in the application). Then I’ve decided to prepare the arrays at the beginning and to save time in their future use. I wrote a code similar to those below.
1: Dictionary<int, Item[]> dictionary = new Dictionary<int, Item[]>();
2: for (int i = 0; i < items.Length; i++)
3: {
4: Item item = items[i];
5: Item[] currentItems;
6: if (dictionary.TryGetValue(item.ParentId, out currentItems))
7: {
8: Item[] newCurrentItems = new Item[currentItems.Length + 1];
9: Array.Copy(currentItems, newCurrentItems, currentItems.Length);
10: newCurrentItems[newCurrentItems.Length - 1] = item;
11: dictionary[item.ParentId] = newCurrentItems;
12: }
13: else
14: {
15: dictionary.Add(item.ParentId, new Item[] { item });
16: }
17: }
Yesterday, a colleague of mine Saso Jordanoski ask me why I didn’t use a List<T> in order to prepare the arrays. We’ve started a conversation and I’ve explained why but the point of Saso was that I re-allocate so much memory creating a lot of unusual arrays and that it will be better to use a List<T>. Yes, in this case we think it is true but during the discussion we came up with an idea to just use the array of items with sorted by parent id array of items and to copy from it. And do you know? The result of my simple test shows that the last idea is much better, almost 8 times :). Think twice before to implement an idea! Below is the implementation of the last idea.
1: int count = 0;
2: for (int i = 0; i < items.Length; i += count)
3: {
4: Item item = items[i];
5: count = Count(items, i, item.ParentId);
6: Item[] currentItems = new Item[count];
7:
8: Array.Copy(items, i, currentItems, 0, count);
9: dictionary.Add(item.ParentId, currentItems);
10: }
It even looks simpler and easy to be understood. Below is the fool code of the test application.
1: using System;
2: using System.Collections.Generic;
3: using System.Linq;
4: using System.Text;
5: using System.Diagnostics;
6:
7: namespace CopyToTest
8: {
9: class Program
10: {
11: static void Main(string[] args)
12: {
13: Item[] items = new Item[100000];
14:
15: for (int i = 0; i < 20000; i++)
16: {
17: int startIndex = i * 5;
18: for (int j = startIndex; j < startIndex + 5; j++)
19: {
20: items[j] = new Item { ParentId = i, Value = string.Empty };
21: }
22: }
23:
24: Stopwatch sw = new Stopwatch();
25: sw.Start();
26: Dictionary<int, Item[]> dictionary = new Dictionary<int, Item[]>();
27: for (int i = 0; i < items.Length; i++)
28: {
29: Item item = items[i];
30: Item[] currentItems;
31: if (dictionary.TryGetValue(item.ParentId, out currentItems))
32: {
33: Item[] newCurrentItems = new Item[currentItems.Length + 1];
34: Array.Copy(currentItems, newCurrentItems, currentItems.Length);
35: newCurrentItems[newCurrentItems.Length - 1] = item;
36: dictionary[item.ParentId] = newCurrentItems;
37: }
38: else
39: {
40: dictionary.Add(item.ParentId, new Item[] { item });
41: }
42: }
43: sw.Stop();
44:
45: Console.WriteLine(sw.ElapsedMilliseconds);
46:
47: sw.Reset();
48: sw.Start();
49: dictionary = new Dictionary<int, Item[]>();
50: int count = 0;
51: for (int i = 0; i < items.Length; i += count)
52: {
53: Item item = items[i];
54: count = Count(items, i, item.ParentId);
55: Item[] currentItems = new Item[count];
56:
57: Array.Copy(items, i, currentItems, 0, count);
58: dictionary.Add(item.ParentId, currentItems);
59: }
60: sw.Stop();
61:
62: Console.WriteLine(sw.ElapsedMilliseconds);
63: Console.Read();
64: }
65:
66: private static int Count(Item[] array, int startindex, int parentId)
67: {
68: int count = 0;
69: for (int i = startindex; i < array.Length; i++)
70: {
71: if (array[i].ParentId == parentId)
72: {
73: count++;
74: }
75: else
76: {
77: break;
78: }
79: }
80: return count;
81: }
82: }
83:
84: public class Item
85: {
86: public int ParentId;
87: public string Value;
88: }
89: }
And you can see the results on my machine below.
Leave a Reply