4

I am trying to optimize generic lists arithmetic operation. I have 3 lists of nullable double as defined below.

List<double?> list1 = new List<double?>();
List<double?> list2 = new List<double?>();
List<double?> listResult = new List<double?>();

int recordCount = list1.Count > list2.Count ? list2.Count : list1.Count;

for (int index = 0; index < recordCount; index++)
{
      double? result = list1[index] + list2[index];
      listResult.Add(result);
}

Is there any way to make this operation to run faster if I have huge lists?

Thanks for your input.

7
  • How are you populating the lists before you Add them together? If the data is from a database it would be faster to get the results summed from the dB. Oct 5, 2012 at 1:12
  • You know that this code will produce a ArrayOutOfBoundsException if the 2 lists have different sizes?
    – juergen d
    Oct 5, 2012 at 1:12
  • 1
    @juergend No, he is first finding which list is shorter -- line 5.
    – Jay
    Oct 5, 2012 at 1:13
  • @Juergend, this statement "int recordCount = list1.Count > list2.Count ? list2.Count : list1.Count;" will take care of the problem
    – Alan B
    Oct 5, 2012 at 1:14
  • @jeremy, those lists are populated from other operations and it's not reading from database
    – Alan B
    Oct 5, 2012 at 1:16

5 Answers 5

9

Is there any way to make this operation to run faster if I have huge lists?

You could move your list creation for the results until after your count:

List<double?> list1 = new List<double?>();
List<double?> list2 = new List<double?>();

int recordCount = list1.Count > list2.Count ? list2.Count : list1.Count;
List<double?> listResult = new List<double?>(recordCount);

This would let you specify the exact capacity necessary for the results, and avoid reallocations within the list itself. For "huge lists" this is likely one of the slowest portions, as the memory allocations and copies as the list gets large will be the slowest operation here.

Also, if the calculation is simple, you could potentially use multiple cores:

List<double?> list1 = new List<double?>();
List<double?> list2 = new List<double?>();

int recordCount = list1.Count > list2.Count ? list2.Count : list1.Count;

var results = new double?[recordCount]; // Use an array here

Parallel.For(0, recordCount, index => 
    {
        double? result = list1[index] + list2[index];
        results[index] = result;
    });

Given that the "work" is so simple here, you probably actually would need a custom partitioner to get the most out of parallelism (see How to: Speed Up Small Loop Bodies for details):

var results = new double?[recordCount]; // Use an array here
var rangePartitioner = Partitioner.Create(0, recordCount);

Parallel.ForEach(rangePartitioner, range => 
    {
        for (int index = range.Item1; index < range.Item2; index++)
        {
            results[index] = list1[index] + list2[index];
        }
    });

If this isn't a bottleneck, however, you could use LINQ to do this as a one-liner:

var results = list1.Zip(list2, (one, two) => one + two).ToList();

However, this will be (very slightly) less efficient than handling the looping yourself, if performance is really a bottleneck.

5
  • I'm pretty sure list realloc would use some type of growing/exponential/fibonnaci/other expanding growth system, so maybe not as bad as you think. But I agree that allocating only once is a good optimization, and easy.
    – mattypiper
    Oct 5, 2012 at 1:23
  • @mattypiper It does - it starts with 4 elements, and doubles each time. With a very large list, though, that can be expensive, as each realloc requires a copy of the existing list. Oct 5, 2012 at 1:24
  • Since the operation is so simple the parallel improvement is probably the most likely to result in an increase in performance assuming that you are running on a system with multiple cores, processors, or Hyperthreading. Oct 5, 2012 at 1:32
  • @CraigSuchanec Yeah - but being THIS simple, it probably requires a custom partitioner... going to edit Oct 5, 2012 at 1:33
  • @CraigSuchanec Done - that's actually going to be better if the work is really this simple. Oct 5, 2012 at 1:36
0

If you know the sizes of the lists ahead of time, simple arrays should run faster. Created like this:

double?[] Array1 = new double?[10];
0

The first thing you could do is specify the capacity of your result list

List<double?> listResult = new List<double?>(recordCount);

This will pre-allocate the space for the results saving time on each of the List.Add() calls.

If you're really worried performance you could break the lists into chunks and spark off multiple threads to do partial result sets and then merge the full set back together when they're done.

0
var result = from i in
            Enumerable.Range(0, Math.Min(list1.Count, list2.Count))
            select list1.ElementAtOrDefault(i) + list2.ElementAtOrDefault(i);
foreach (var item in result)
{
Debug.Write(item.Value);
}
0
0

If you have the ability to use raw arrays instead of lists, you can certainly make this faster - just how much depends on how low-level you want to go. Correcting a few bugs in your source, I wrote up three different versions. One goes the way your code does, by creating a new list for results (I took the liberty of using the constructor which takes a capacity, preventing a bunch of intermediate allocations).

I also wrote a version that sums two arrays into a third, with the view that stripping away List would increase efficiency.

Finally, I wrote a version that uses unsafe code to add the first array to the second using pointers.

The result of the comparison is below:

Timings: 500000 iterations of 10000-item lists
  Lists:           00:00:13.9184166
  Arrays (safe):   00:00:08.4868231
  Arrays (unsafe): 00:00:03.0901603

Press any key to continue...

The code I used can be found in this Github gist.

Unsafe code may be a little too much optimization, but it's pretty striking to see the difference between these three samples. For clarity's sake, I'd recommend sticking with safe code and use arrays.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.