65.9K
CodeProject 正在变化。 阅读更多。
Home

C# 中数组的高效 Map 操作

Christopher Diggins
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.92/5 (28投票s)

2012 年 9 月 2 日

CPOL

8分钟阅读

viewsIcon

72327

downloadIcon

501

对 C# 中数组的 map 高阶函数实现技术进行的非正式调查。

介绍  

本文比较了实现用于转换数组的 map 函数的各种技术的性能，并介绍了一种使用表达式树重写的新颖高性能 map 实现。

一个map 操作从另一个列表中构造一个序列或列表，其中新列表中的每个元素都是将函数应用于原始列表中每个对应元素的结果。对于 C# 程序员来说，最著名的 map 操作示例是系统库中的IEnumerable.Select()函数。   

map 操作因其常见且易于并行而成为优化的有趣研究对象。高性能的 map 操作是高效集合库的基石。  

观察结果 

实验的主要观察结果是：  

  • 当数组较小时（< 10,000 个元素），最简单的非并行实现远远优于并行实现。  
  • 使用带有范围分区的Parallel.ForEach()始终优于AsParallel().AsOrdered().Select().ToArray()。 
  • 通过将 lambda 作为表达式树传递并重写它，我们可以提高带有范围分区的Parallel.ForEach()的性能。 

方法论   

这些测试是在一台 2.3 Ghz 的 Intel i7 四核机器上运行的。   

为了比较 map 的不同实现，我创建了一个测试套件，比较了 6 种不同的 map 实现。我针对 9 种不同的函数参数和长度从 100 到 10,000,000 个整数不等的输入数组尝试了每种实现。

在每个数组大小上，测试函数会重复运行，并在不同的实现技术之间交替进行，直到总经过时间达到 1 秒。  

实现数组 Map 操作的技术

在我的实验中，我研究了以下数组 map 操作的实现。

简单的顺序 Map

这是一个简单的 map 实现，使用了 for 循环。

U[] Map<T, U>(T[] xs, Func<T, U> f)  {   
  var r = new U[xs.Length];
  for (int i=0; i < xs.Length; ++i) r[i] = f(xs[i]);
  return r;
}

对于小型数组（<= 1000），这始终是最有效的实现。

使用 IEnumerable.Select 实现 Map   

最简单的 map 实现使用IEnumerable.Select()  操作，然后调用ToArray()。 

U[] Map<T, U>(T[] xs, Func<T, U> f)  {   
  return xs.Select(f).ToArray();
}
根据我的测量，这通常是最慢的 map 实现方法，特别是对于大小为 10,000 及以上的数组。这比手动编写的版本效率低是合乎情理的，因为它使用了枚举器，使得编译器难以利用有关底层数据类型的优化知识。

使用 Parallel.For 的并行 Map 操作 

使用Parallel.For()可以轻松地将手动编写的 map 操作转换为并行操作，如下所示：   

static U[] SimpleParallelMap<T, U>(T[] xs, Func<T, U> f) {
  var r = new U[xs.Length];
  Parallel.For(0, xs.Length, i => r[i] = f(xs[i]));
  return r;
}

令人惊讶的是，即使对于大型数组，甚至在某些情况下表现不佳，这种实现也从未显著优于非并行版本。

使用 IEnumerable.AsParallel() 的并行 Map   

另一种并行实现 map 的方法是使用IEnumerable.AsParallel()。 

U[] Map<T, U>(T[] xs, Func<T, U> f)  {   
  return xs.Select(f).AsParallel().AsOrdered().ToArray();
}

这种技术的性能与Parallel.For()方法相当，有时更好，有时更差。出于某种原因，对于正好是 1,000,000 个元素的数组，其性能一直比 Parallel.For() 技术差（有时长达 2 倍或更多）。

使用范围分区器的并行 Map 

通过使用Parallel.ForEeach() ，分区器可以通过创建更少的操作子范围数组的任务来减轻任务调度程序的负担。

static U[] PartitionedParallelMap<T, U>(T[] xs, Func<T, U> f)
{
  var r = new U[xs.Length];
  Parallel.ForEach(Partitioner.Create(0, xs.Length), 
    range => { for (int i = range.Item1; i < range.Item2; ++i) 
      r[i] = f(xs[i]); });
  return r;
}

对于大型数组，此方法的性能是迄今为止最好的，但与大多数并行方法一样，只有当数组大小达到 10,000 个元素时，它才开始优于简单的手动编写的顺序 map 实现。  

使用范围分区器和表达式树重写的并行 Map

通过观察传递给ForEach的函数主要由调用 lambda 函数参数的成本决定，可以提高PartitionedParallelMap()函数的性能。总的来说，调用 lambda 函数具有显着的性能成本。  

如果 lambda 函数作为表达式树传递，则可以将其内联到动态创建的函数中，并传递给Parallel.ForEach()函数。    

这是伪代码中的通用方法：  

static U[] OptimizedPartitionedParallelMap<T, U>(T[] xs, Expresion<Func<T, U>> fexpr)
{
  var r = new U[xs.Length];
  Expression<Action<T[], U[], int, int>> fexpr2 = RewriteExpressionTree(fexpr);
  Action<T[], U[], int, int> f = fexpr.Compile();
  Parallel.ForEach(Partitioner.Create(0, xs.Length), range => 
   { f(xs, r, range.Item1, range.Item2); });
  return r;
}

重写代码创建了一个新的表达式树，并使用ExpressionVisitor类将函数参数（fexpr）的主体内联到其中，从而消除了循环中昂贵的 lambda 调用。  

public class FunctionInliner <t,> : ExpressionVisitor
{
  Expression argument;
  ParameterExpression parameter;

  public FunctionInliner(Expression<func<t,>> function, Expression argument){
     parameter = function.Parameters[0];
     this.argument = argument;
  }

  public Expression Modify(Expression expression) {
    return Visit(expression);
  }

  protected override Expression VisitParameter(ParameterExpression node){ 
    return node = parameter ? argument : node;
  }
}

public static class FunctionInliner
{
  public static Expression InlineFunctionCall<t,>(Expression<func<t,>> function, Expression arg) {
     var fi = new FunctionInliner<t,>(function, arg);
     return fi.Modify(function.Body);
  }
}

这个 map 实现只有在Expression.Compile()被记忆化（即缓存）的情况下才有合理的性能，如下所示： 

private static Dictionary<Expression, object> memoizedFastMaps = new Dictionary<Expression, object>();

public static U[] FastMap<T, U>(this T[] self, Expression<Func<T, U>> fexpr) {
  Action<T[], U[], int, int> f;
  lock (memoizedFastMaps)
  {
    if (!memoizedFastMaps.ContainsKey(fexpr))
       memoizedFastMaps[fexpr] = ComputeFastMap(fexpr);
    f = (Action<T[], U[], int, int>)memoizedFastMaps[fexpr];
  }
  var r = new U[self.Length];
  Parallel.ForEach(Partitioner.Create(0, self.Length), 
  range => f(self, r, range.Item1, range.Item2));
  return r;
}

该技术的性能通常比简单地使用范围分区器略好。 

结果    

此表包含不同 map 测试的结果。它也可以作为彩色编码的 Excel 表格在 zip 包中找到。每个值代表每个测试花费的总毫秒数。每列代表不同大小的数组。

100 1000 10,000 100,000 1,000,000 10,000,000
x * 2 
IEnumerable.Select   47.0013 177.8057 328.9458 360.1104 354.0814 645.1824
SimpleMap            7.5816 34.7406 69.7591 94.4403 92.0408 189.9622
Parallel.For         356.2646 250.5682 145.9923 234.1428 103.7589 214.9254
ParallelQuery        154.392 230.0595 288.8722 237.1865 385.0914 131.25
Partitioned ForEach  209.446 154.7732 107.0929 44.0619 25.6843 52.4506
Expression-tree map  202.83 138.4812 55.6059 29.6556 70.3177 47.7849
x % 3 
IEnumerable.Select   50.9754 187.2522 326.9465 351.2355 404.2332 546.7806
SimpleMap            11.0956 53.0866 96.3511 120.8589 136.8649 205.0038
Parallel.For         335.2865 221.5865 138.5964 213.4733 121.2471 159.3329
ParallelQuery        158.7274 228.8488 277.0174 219.9876 260.9124 125.8866
Partitioned ForEach  217.3006 152.4565 89.5992 56.3834 41.3112 57.5527
Expression-tree map  203.2819 144.2859 68.2051 40.7922 97.9225 56.9034
x % 10 == 0 
IEnumerable.Select   44.749 154.2371 269.2269 299.4427 375.8133 486.5356
SimpleMap            11.0698 54.2887 97.424 135.1354 181.7922 213.2659
Parallel.For         327.3782 233.9054 144.3949 134.1175 147.8055 192.6815
ParallelQuery        159.6129 233.3072 275.8584 331.0025 185.0597 143.3002
Partitioned ForEach  227.4341 157.5438 128.4379 55.6181 53.5953 59.0363
Expression-tree map  207.7087 153.7541 81.5905 47.0574 62.8087 61.7823
x * y 
IEnumerable.Select   47.5342 176.2845 330.5266 417.78 389.5859 641.2155
SimpleMap            6.6616 29.933 60.012 82.1904 86.6731 164.2725
Parallel.For         335.883 239.2442 151.766 151.0844 109.0079 208.9425
ParallelQuery        156.0036 229.0513 307.9049 260.6253 319.6288 114.221
Partitioned ForEach  219.3628 156.26 81.5716 41.7017 34.5045 54.1712
Expression-tree map  211.8914 155.145 65.0756 45.8949 80.9438 57.4718
Math.Sqrt(x)
IEnumerable.Select   52.052 178.1152 325.6915 337.2131 314.3897 594.8534
SimpleMap            11.5972 60.8885 108.1417 150.2933 142.9398 226.6415
Parallel.For         332.5255 214.7269 155.6848 115.8106 107.1056 206.2448
ParallelQuery        151.1703 236.2765 262.9026 221.0244 333.1709 108.9785
Partitioned ForEach  218.4954 153.5197 70.759 133.0735 53.0308 116.2612
Expression-tree map  212.4254 146.074 74.6249 46.6229 51.6872 84.8528
1.0 / x 
IEnumerable.Select   57.7009 192.1225 351.9372 342.5118 342.8452 422.6756
SimpleMap            13.6616 61.0858 113.1279 215.0919 149.2644 159.6373
Parallel.For         327.4285 211.7903 168.9644 123.7927 123.0176 130.4033
ParallelQuery        156.755 233.4242 211.9213 156.8925 305.5861 379.4584
Partitioned ForEach  222.793 151.4817 73.8911 51.0748 56.9122 86.312
Expression-tree map  200.7036 139.8924 77.7088 115.2319 54.257 59.8788
F(x) 
IEnumerable.Select    48.3564 172.7315 328.2192 339.3331 401.4378 685.65
SimpleMap             9.3622 53.5944 119.9011 134.9806 153.9984 271.0598
Parallel.For          317.6485 199.1581 138.0239 188.8737 127.2151 202.1605
ParallelQuery         148.9416 201.4768 241.8003 197.0903 154.3222 141.0791
Partitioned ForEach   215.59 172.11 64.8258 47.5668 45.3556 65.6707
Expression-tree map  239.0486 190.5578 103.7636 92.9645 160.6785 143.9428
xs[x % xs.Length] 
IEnumerable.Select   53.4851 194.6166 326.2611 371.1026 431.2638 568.9713
SimpleMap            11.1547 52.3415 92.1421 123.3329 142.5564 203.5745
Parallel.For         321.7491 215.2261 135.3974 225.5697 129.4563 188.0756
ParallelQuery        161.9284 219.4217 290.0379 169.8483 139.5091 118.6672
Partitioned ForEach  219.876 157.8085 73.0295 58.3842 42.7669 59.3939
Expression-tree map  210.0777 148.9512 80.0346 53.4993 121.5434 70.5305
x.ToString() 
IEnumerable.Select   174.3339 318.9216 322.7798 263.6981 263.9824 2986.9454
SimpleMap            123.489 255.0868 285.1731 247.5723 297.4845 2781.8611
Parallel.For         198.1301 109.1844 115.8489 147.2986 174.429 1952.4264
ParallelQuery        145.9428 112.4906 96.8155 125.436 183.3579 2024.5259
Partitioned ForEach  182.2398 96.6949 89.1915 129.1918 226.7504 1928.2476
Expression-tree map  165.3074 104.9725 89.9368 121.4181 178.6953 1835.5693

结语

本次调查是非正式的，不够严谨。理想情况下，应该添加更多测试，并探索更多输入数组类型（不仅仅是 int 数组）。最后，需要测试更多的 CPU 配置。  

尽管如此，这些结果确实为数组大小对最有效技术产生了巨大影响这一事实提供了一些有趣的见解，并展示了范围分区在数组并行 map 操作中的有效性。 

虽然表达式树重写技术很有趣，但性能提升不如预期，而且不稳定。目前，由于复杂性，我不建议使用它，但我希望其他人能够找到提高其性能的方法。  

当然，欢迎所有评论，但我尤其希望听到其他机器上的结果以及建议的替代实现。 

历史        

2012年9月2日 - 第一个版本

© . All rights reserved.