Fast List Multiplication in C#

Some background, I'm trying to do a large scale building simulation.

The issue is I have a list of the the custom type Point3D that I want to do fast array multiplication on it. So, at different time step, I would have to times a double value with the Point3D ( I've overloaded the multiplication and division operation of Point3D) for each and every Point3D, the result will then be stored in a Dictionary<double,List<Point3D>>. The key of this dictionary is the different time step, and the value is the corresponding displacement.

Since I have a lot of DOF, and a lot of time step, it seems that the above operation is very slow. Is there anyway to optimiz开发者_如何学运维e the whole operation?

This is my current code, and it's extremely slow. So I need some ideas to optimize it.

public static Dictionary<double, List<Point3D>> ComputeTimeSeries(Dictionary<double, double> timeStep, List<Point3D> dofs)
{
   var timeSeries = new Dictionary<double, List<Point3D>>();
   foreach(var keyValue in timeStep)
   {
      // the point3d*double operation is already being overloaded.
      timeSeries.Add(keyValue.Key, dofs.Select(pt=>pt*keyValue.Value).ToList());  
   }
   return timeSeries;
}

Note: I'm currently still stuck at .Net 3.5. So probably PLINQ and TPL won't help

---

I would try something like this:

public static Dictionary<double, Point3D[]> ComputeTimeSeries(Dictionary<double,    double> timeStep, Point3D[] dofs)
{
   var timeSeries = new Dictionary<double, Point3D[]>();
   foreach(var keyValue in timeStep)
   {
      var tempArray = new Point3D[dofs.Length];
      for (int index=0; index < dofs.Length; index++)
          tempArray[index] = dofs[index] * keyValue.Value;
      timeSeries.Add(keyValue.Key, tempArray);  
   }
   return timeSeries;
}

Using Select/ToList is more readable, but the extra interface calls are very expensive compared to a simple multiplication.

---

For starters, you can eliminate some re-allocation and copying by using a Capacity parameter when creating the new Dictionary:

 var timeSeries = new Dictionary<double, List<Point3D>>(timeStep.Count);

And the code in the foreach loop looks independent of each other, this means you could run it in parallel. In .NET4 this is as easy as replacing :

 foreach(var keyValue in timeStep) { ... }

with

Parallel.Foreach(timestep, key, (key) => ...);

---

Profiler will give you some ideas. Also, try to escape from linq

public static Dictionary<double, List<Point3D>> ComputeTimeSeries(Dictionary<double, double> timeStep, List<Point3D> dofs)
{
   var timeSeries = new Dictionary<double, List<Point3D>>();
   foreach(var keyValue in timeStep)
   {
      List<double> lst = new List<double>();
      foreach (Point3D point in dofs)
         lst.Add(point* keyValue.Value);

      timeSeries.Add(keyValue.Key, lst);  // the point3d*double operation is already being overloaded.
   }
   return timeSeries;
}

---

I'm not a C# expert, but maybe the

dofs.Select(pt=>pt*keyValue.Value).ToList()

part could benefit from parallelization. Using SIMD instructions and/or threads, you could perform dofs[0] *= keyValue.Value and dofs[1] *= keyValue.Value etc. in parallel.

This code looks much like the first example given in the Optimize Managed Code For Multi-Core Machines article. So maybe you could rewrite the above to something like

Parallel.For(0, dofs.Length, delegate(int i) {
  dofs[i] *= keyValue.Value;
});

---

If you could change the return value from Dictionary<double, List<Point3D>> to Dictionary<double, IEnumerable<Point3D>> you could postpone the actual calculation until it was needed.

You could remove the .ToList() and end up with the following:

public static Dictionary<double, IEnumerable<Point3D>> ComputeTimeSeries(Dictionary<double, double> timeStep, List<Point3D> dofs)
{
   var timeSeries = new Dictionary<double, List<Point3D>>();  
   foreach(var keyValue in timeStep)    
   {
      // the point3d*double operation is already being overloaded.
      timeSeries.Add(keyValue.Key, dofs.Select(pt=>pt*keyValue.Value));  
   } 
   return timeSeries; 
}

Now the calculations would be performed when you started to enumerate the values instead of inside the ComputeTimeSeries method. This would not make the compuations faster, but you would probably spread them out in time, possibly even across many threads.