[ 2017 年编辑:请参阅 本文末尾有关C# 7的重要评论]
经过多年努力解决这个确切的问题,我将总结我发现的一些技术和解决方案。抛开文体风格不谈,结构数组实际上是C#中可用的内存大容量存储方法。如果您的应用程序真正在高吞吐量条件下处理数百万个中型对象,则没有其他托管替代方案。
我同意@kaalus 的观点,即对象标头和 GC 压力可以快速增加;然而,当解析和/或生成冗长的自然语言句子时,我的 NLP 语法处理系统可以在不到一分钟的时间内处理 8-10 GB(或更多)的结构分析。提示合唱:“C# 不适用于此类问题……”、“切换到汇编语言……”、“对FPGA进行接线……”等。
好吧,让我们运行一些测试。首先,全面了解价值类型( struct
) 管理问题和class
权衡struct
取舍的最佳点是至关重要的。当然还有装箱、固定/不安全代码、固定缓冲区GCHandle,
IntPtr,
等等,但在我看来,最重要的是明智地使用托管指针(又称“内部指针”)。
您对这些主题的掌握还将包括以下事实:如果您碰巧在您的struct
一个或多个对托管类型的引用中包含了(而不仅仅是 blittable 原语),那么您访问struct
withunsafe
指针的选项将大大减少。对于我将在下面提到的托管指针方法,这不是问题。所以一般来说,包括对象引用是好的,并且关于这个讨论并没有太大变化。
哦,如果您确实需要保留您的unsafe
访问权限,您可以使用GCHandle
“正常”模式将对象引用无限期地存储在您的结构中。幸运的是,将GCHandle
放入您的结构不会触发不安全访问禁令。(注意它GCHandle
本身就是一个值类型,你甚至可以用
var gch = GCHandle.Alloc("spookee",GCHandleType.Normal);
GCHandle* p = &gch;
String s = (String)p->Target;
……等等。作为一种值类型,GCHandle 直接映射到您的结构中,但显然它存储的任何引用类型都不是。它们在堆中,不包含在阵列的物理布局中。最后,在 GCHandle 上,请注意它的复制语义,因为如果您最终不Free
分配每个 GCHandle,就会发生内存泄漏。
@Ani 提醒我们,有些人认为可变struct
实例是“邪恶的”,但问题在于它们容易发生事故。确实,OP的示例...
s[543].a = 3;
...准确地说明了我们想要实现的目标:就地访问我们的数据记录。(注意:引用类型 ' ' 实例数组的语法class
具有相同的外观,但在本文中,我们只专门讨论用户定义值类型的非锯齿数组。)对于我自己的程序,我通常如果我遇到一个过大的 blittable 结构(意外地)完全从其数组存储行中成像,则认为这是一个严重的错误:
记录 no_no = s[543]; // 不要这样做
no_no.a = 3 // 像这样
至于你struct
可以或应该有多大(宽),这无关紧要,因为你要小心不要让struct
做前面例子中刚刚展示的事情,也就是说,迁移到全部它的嵌入数组。事实上,这指向了整篇文章的一个基本前提:
规则:
对于 的数组,始终就地struct
访问各个字段;永远不要“提及”(在C#中)实例本身in-toto。struct
不幸的是,C#语言无法系统地标记或禁止违反此规则的代码,因此这里的成功通常取决于仔细的编程纪律。
由于我们的“巨型结构”永远不会从它们的数组中成像出来,它们实际上只是内存上的模板。换句话说,正确的想法是将struct
视为覆盖数组元素。我们总是认为每个都是空的“内存模板”,而不是可转移或便携的封装器或数据容器。对于数组绑定的“巨型”值类型,我们永远不想调用“ struct
”最存在的特征,即按值传递。
例子:
public struct rec
{
public int a, b, c, d, e, f;
}
在这里,我们覆盖 6int
秒,每个“记录”总共 24 个字节。您需要考虑并注意包装选项以获得易于对齐的尺寸。但是过多的填充可能会削减您的内存预算:因为更重要的考虑因素是非 LOH 对象的 85,000 字节限制。确保您的记录大小乘以预期的行数不超过此限制。
因此,对于此处给出的示例,最好建议您将rec
s 数组保持为每个不超过 3,000 行。希望您的应用程序可以围绕这个最佳点进行设计。当您记得——或者——每一行将是一个单独的垃圾收集对象,而不仅仅是一个数组时,这并不是那么限制。您已将对象增殖减少了三个数量级,这对一天的工作很有好处。因此,这里的 .NET 环境强烈地引导我们使用一个非常具体的约束:似乎如果您将应用程序的内存设计定位为 30-70 KB 范围内的整体分配,那么您真的可以摆脱很多很多,事实上,您反而会受到一系列更棘手的性能瓶颈(即硬件内存总线上的带宽)的限制。
因此,现在您在物理上连续的表格存储中拥有一个包含 3,000 个 6 元组的单个 .NET 引用类型(数组)。首先,我们必须非常小心,不要“拿起”其中一个结构。正如上面 Jon Skeet 所指出的,“大规模结构的性能通常比类差”,这是绝对正确的。没有更好的方法来瘫痪你的内存总线,而不是开始随意抛出丰满的值类型。
因此,让我们利用结构数组的一个不常提及的方面:整个数组的所有行的所有对象(以及这些对象或结构的字段)始终初始化为其默认值。您可以开始在数组中的任何行或列(字段)中的任何位置一次插入一个值。您可以将某些字段保留为默认值,或者替换相邻字段而不干扰中间字段。使用堆栈驻留(局部变量)结构所需的烦人的手动初始化已经一去不复返了。
有时很难保持逐个字段的方法,因为 .NET 总是试图让我们在整个new
'd-up 结构中爆炸——但对我来说,这种所谓的“初始化”只是违反了我们的禁忌(反对从数组中取出整个结构),以不同的形式。
现在我们进入问题的症结所在。显然,就地访问您的表格数据可以最大限度地减少数据混洗的繁忙工作。但通常这是一个不便的麻烦。由于边界检查,数组访问在 .NET 中可能很慢。那么如何维护一个指向数组内部的“工作”指针,以避免系统不断地重新计算索引偏移量。
评估
让我们评估在值类型数组存储行中操作各个字段的五种不同方法的性能。下面的测试旨在测量在不提取或重写整个结构(数组元素)的情况下,在原位(即“它们所在的位置”)集中访问位于某个数组索引处的结构的数据字段的效率。比较了五种不同的访问方法,所有其他因素都保持不变。
五种方法如下:
- 通过方括号和字段说明符点的正常、直接数组访问。请注意,在 .NET 中,数组是通用类型系统的一种特殊且独特的原语。正如@Ani 上面提到的,这种语法不能用于更改引用实例的单个字段,例如列表,即使它是使用值类型参数化的。
- 使用未记录的
__makeref
C# 语言关键字。
- 通过使用关键字的委托管理指针
ref
- “不安全”指针
- 与 #3 相同,但使用 C#函数而不是委托。
在我给出 C# 测试结果之前,这里是测试工具的实现。这些测试在 .NET 4.5 上运行,这是一个在 x64、Workstation gc 上运行的 AnyCPU 版本。(请注意,由于测试对分配和取消分配阵列本身的效率不感兴趣,因此上面提到的 LOH 考虑不适用。)
const int num_test = 100000;
static rec[] s1, s2, s3, s4, s5;
static long t_n, t_r, t_m, t_u, t_f;
static Stopwatch sw = Stopwatch.StartNew();
static Random rnd = new Random();
static void test2()
{
s1 = new rec[num_test];
s2 = new rec[num_test];
s3 = new rec[num_test];
s4 = new rec[num_test];
s5 = new rec[num_test];
for (int x, i = 0; i < 5000000; i++)
{
x = rnd.Next(num_test);
test_m(x); test_n(x); test_r(x); test_u(x); test_f(x);
x = rnd.Next(num_test);
test_n(x); test_r(x); test_u(x); test_f(x); test_m(x);
x = rnd.Next(num_test);
test_r(x); test_u(x); test_f(x); test_m(x); test_n(x);
x = rnd.Next(num_test);
test_u(x); test_f(x); test_m(x); test_n(x); test_r(x);
x = rnd.Next(num_test);
test_f(x); test_m(x); test_n(x); test_r(x); test_u(x);
x = rnd.Next(num_test);
}
Debug.Print("Normal (subscript+field): {0,18}", t_n);
Debug.Print("Typed-reference: {0,18}", t_r);
Debug.Print("C# Managed pointer: (ref delegate) {0,18}", t_m);
Debug.Print("C# Unsafe pointer: {0,18}", t_u);
Debug.Print("C# Managed pointer: (ref func): {0,18}", t_f);
}
因为为每个特定方法实现测试的代码片段很长,我先给出结果。时间是“滴答”;更低意味着更好。
Normal (subscript+field): 20,804,691
Typed-reference: 30,920,655
Managed pointer: (ref delegate) 18,777,666 // <- a close 2nd
Unsafe pointer: 22,395,806
Managed pointer: (ref func): 18,767,179 // <- winner
我很惊讶这些结果如此明确。TypedReferences
是最慢的,大概是因为它们与指针一起拖着类型信息。考虑到劳累的“普通”版本的 IL 代码的重要性,它的表现出奇的好。模式转换似乎会伤害不安全的代码,以至于您确实必须证明、计划和衡量您将要部署它的每个地方。
但是通过利用ref
函数参数传递中的关键字来指向数组的内部部分,可以实现最快的时间,从而消除了“按字段访问”数组索引计算。
也许我的测试设计偏爱这个,但测试场景代表了我的应用程序中的经验使用模式。让我对这些数字感到惊讶的是,保持在托管模式的优势——同时也有你的指针——并没有因为必须调用函数或通过委托调用而取消。
赢家
最快的一个:(也许也是最简单的?)
static void f(ref rec e)
{
e.a = 4;
e.e = e.a;
e.b = e.d;
e.f = e.d;
e.b = e.e;
e.a = e.c;
e.b = 5;
e.d = e.f;
e.c = e.b;
e.e = e.a;
e.b = e.d;
e.f = e.d;
e.c = 6;
e.b = e.e;
e.a = e.c;
e.d = e.f;
e.c = e.b;
e.e = e.a;
e.d = 7;
e.b = e.d;
e.f = e.d;
e.b = e.e;
e.a = e.c;
e.d = e.f;
e.e = 8;
e.c = e.b;
e.e = e.a;
e.b = e.d;
e.f = e.d;
e.b = e.e;
e.f = 9;
e.a = e.c;
e.d = e.f;
e.c = e.b;
e.e = e.a;
e.b = e.d;
e.a = 10;
e.f = e.d;
e.b = e.e;
e.a = e.c;
e.d = e.f;
e.c = e.b;
}
static void test_f(int ix)
{
long q = sw.ElapsedTicks;
f(ref s5[ix]);
t_f += sw.ElapsedTicks - q;
}
但它的缺点是您不能将相关逻辑放在程序中:函数的实现分为两个 C# 函数f和test_f。
我们只需牺牲一点性能就可以解决这个特殊问题。下一个与上述基本相同,但将其中一个函数作为 lambda 函数嵌入到另一个函数中......
紧接着
用内联委托替换前面示例中的静态函数需要使用ref
参数,这反过来又排除了Func<T>
lambda 语法的使用;相反,您必须使用旧式 .NET 中的显式委托。
通过添加此全局声明一次:
delegate void b(ref rec ee);
...我们可以在整个程序中使用它直接ref
进入数组rec[]的元素,内联访问它们:
static void test_m(int ix)
{
long q = sw.ElapsedTicks;
/// the element to manipulate "e", is selected at the bottom of this lambda block
((b)((ref rec e) =>
{
e.a = 4;
e.e = e.a;
e.b = e.d;
e.f = e.d;
e.b = e.e;
e.a = e.c;
e.b = 5;
e.d = e.f;
e.c = e.b;
e.e = e.a;
e.b = e.d;
e.f = e.d;
e.c = 6;
e.b = e.e;
e.a = e.c;
e.d = e.f;
e.c = e.b;
e.e = e.a;
e.d = 7;
e.b = e.d;
e.f = e.d;
e.b = e.e;
e.a = e.c;
e.d = e.f;
e.e = 8;
e.c = e.b;
e.e = e.a;
e.b = e.d;
e.f = e.d;
e.b = e.e;
e.f = 9;
e.a = e.c;
e.d = e.f;
e.c = e.b;
e.e = e.a;
e.b = e.d;
e.a = 10;
e.f = e.d;
e.b = e.e;
e.a = e.c;
e.d = e.f;
e.c = e.b;
}))(ref s3[ix]);
t_m += sw.ElapsedTicks - q;
}
此外,虽然看起来每次调用都会实例化一个新的 lambda 函数,但如果您小心,就不会发生这种情况:使用此方法时,请确保您没有“关闭”任何局部变量(即引用 lambda 函数之外的变量,从它的主体内),或者做任何其他事情,将阻止你的委托实例是静态的。如果一个局部变量恰好落入您的 lambda 并且因此 lambda 被提升为一个实例/类,您将“可能”注意到一个差异,因为它试图创建 500 万个委托。
只要你保持 lambda 函数没有这些副作用,就不会有多个实例;这里发生的情况是,每当 C# 确定 lambda 没有非显式依赖项时,它都会懒惰地创建(并缓存)一个静态单例。有点不幸的是,这种剧烈的性能变化在我们看来是一种无声的优化。总的来说,我喜欢这种方法。它快速且整洁——除了奇怪的括号,这里没有一个可以省略。
其余的
为了完整起见,以下是其余的测试:正常包围加点;类型参考;和不安全的指针。
static void test_n(int ix)
{
long q = sw.ElapsedTicks;
s1[ix].a = 4;
s1[ix].e = s1[ix].a;
s1[ix].b = s1[ix].d;
s1[ix].f = s1[ix].d;
s1[ix].b = s1[ix].e;
s1[ix].a = s1[ix].c;
s1[ix].b = 5;
s1[ix].d = s1[ix].f;
s1[ix].c = s1[ix].b;
s1[ix].e = s1[ix].a;
s1[ix].b = s1[ix].d;
s1[ix].f = s1[ix].d;
s1[ix].c = 6;
s1[ix].b = s1[ix].e;
s1[ix].a = s1[ix].c;
s1[ix].d = s1[ix].f;
s1[ix].c = s1[ix].b;
s1[ix].e = s1[ix].a;
s1[ix].d = 7;
s1[ix].b = s1[ix].d;
s1[ix].f = s1[ix].d;
s1[ix].b = s1[ix].e;
s1[ix].a = s1[ix].c;
s1[ix].d = s1[ix].f;
s1[ix].e = 8;
s1[ix].c = s1[ix].b;
s1[ix].e = s1[ix].a;
s1[ix].b = s1[ix].d;
s1[ix].f = s1[ix].d;
s1[ix].b = s1[ix].e;
s1[ix].f = 9;
s1[ix].a = s1[ix].c;
s1[ix].d = s1[ix].f;
s1[ix].c = s1[ix].b;
s1[ix].e = s1[ix].a;
s1[ix].b = s1[ix].d;
s1[ix].a = 10;
s1[ix].f = s1[ix].d;
s1[ix].b = s1[ix].e;
s1[ix].a = s1[ix].c;
s1[ix].d = s1[ix].f;
s1[ix].c = s1[ix].b;
t_n += sw.ElapsedTicks - q;
}
static void test_r(int ix)
{
long q = sw.ElapsedTicks;
var tr = __makeref(s2[ix]);
__refvalue(tr, rec).a = 4;
__refvalue(tr, rec).e = __refvalue( tr, rec).a;
__refvalue(tr, rec).b = __refvalue( tr, rec).d;
__refvalue(tr, rec).f = __refvalue( tr, rec).d;
__refvalue(tr, rec).b = __refvalue( tr, rec).e;
__refvalue(tr, rec).a = __refvalue( tr, rec).c;
__refvalue(tr, rec).b = 5;
__refvalue(tr, rec).d = __refvalue( tr, rec).f;
__refvalue(tr, rec).c = __refvalue( tr, rec).b;
__refvalue(tr, rec).e = __refvalue( tr, rec).a;
__refvalue(tr, rec).b = __refvalue( tr, rec).d;
__refvalue(tr, rec).f = __refvalue( tr, rec).d;
__refvalue(tr, rec).c = 6;
__refvalue(tr, rec).b = __refvalue( tr, rec).e;
__refvalue(tr, rec).a = __refvalue( tr, rec).c;
__refvalue(tr, rec).d = __refvalue( tr, rec).f;
__refvalue(tr, rec).c = __refvalue( tr, rec).b;
__refvalue(tr, rec).e = __refvalue( tr, rec).a;
__refvalue(tr, rec).d = 7;
__refvalue(tr, rec).b = __refvalue( tr, rec).d;
__refvalue(tr, rec).f = __refvalue( tr, rec).d;
__refvalue(tr, rec).b = __refvalue( tr, rec).e;
__refvalue(tr, rec).a = __refvalue( tr, rec).c;
__refvalue(tr, rec).d = __refvalue( tr, rec).f;
__refvalue(tr, rec).e = 8;
__refvalue(tr, rec).c = __refvalue( tr, rec).b;
__refvalue(tr, rec).e = __refvalue( tr, rec).a;
__refvalue(tr, rec).b = __refvalue( tr, rec).d;
__refvalue(tr, rec).f = __refvalue( tr, rec).d;
__refvalue(tr, rec).b = __refvalue( tr, rec).e;
__refvalue(tr, rec).f = 9;
__refvalue(tr, rec).a = __refvalue( tr, rec).c;
__refvalue(tr, rec).d = __refvalue( tr, rec).f;
__refvalue(tr, rec).c = __refvalue( tr, rec).b;
__refvalue(tr, rec).e = __refvalue( tr, rec).a;
__refvalue(tr, rec).b = __refvalue( tr, rec).d;
__refvalue(tr, rec).a = 10;
__refvalue(tr, rec).f = __refvalue( tr, rec).d;
__refvalue(tr, rec).b = __refvalue( tr, rec).e;
__refvalue(tr, rec).a = __refvalue( tr, rec).c;
__refvalue(tr, rec).d = __refvalue( tr, rec).f;
__refvalue(tr, rec).c = __refvalue( tr, rec).b;
t_r += sw.ElapsedTicks - q;
}
static void test_u(int ix)
{
long q = sw.ElapsedTicks;
fixed (rec* p = &s4[ix])
{
p->a = 4;
p->e = p->a;
p->b = p->d;
p->f = p->d;
p->b = p->e;
p->a = p->c;
p->b = 5;
p->d = p->f;
p->c = p->b;
p->e = p->a;
p->b = p->d;
p->f = p->d;
p->c = 6;
p->b = p->e;
p->a = p->c;
p->d = p->f;
p->c = p->b;
p->e = p->a;
p->d = 7;
p->b = p->d;
p->f = p->d;
p->b = p->e;
p->a = p->c;
p->d = p->f;
p->e = 8;
p->c = p->b;
p->e = p->a;
p->b = p->d;
p->f = p->d;
p->b = p->e;
p->f = 9;
p->a = p->c;
p->d = p->f;
p->c = p->b;
p->e = p->a;
p->b = p->d;
p->a = 10;
p->f = p->d;
p->b = p->e;
p->a = p->c;
p->d = p->f;
p->c = p->b;
}
t_u += sw.ElapsedTicks - q;
}
概括
对于大型 C# 应用程序中的内存密集型工作,使用托管指针直接就地访问值类型数组元素 的字段是可行的方法。
如果您真的很重视性能,这可能是使用C++/CLI
(或CIL
,就此而言)而不是C#
应用程序的相关部分的充分理由,因为这些语言允许您直接在函数体内声明托管指针。
在C#
中,创建托管指针的唯一方法是声明一个带有ref
orout
参数的函数,然后被调用者将观察托管指针。因此,要在 C# 中获得性能优势,您必须使用上面显示的(前两种)方法之一。 [参见下面的 C#7]
可悲的是,这些部署将函数拆分为多个部分只是为了访问数组元素。尽管比等效C++/CLI
代码要优雅得多,但测试表明,即使在 C# 中,对于高吞吐量应用程序,与幼稚的值类型数组访问相比,我们仍然可以获得很大的性能优势。
[ 2017 年编辑:虽然总体上可能对本文的劝告赋予了一定程度的先见之明,但C# 7的发布Visual Studio 2017
同时使上述特定方法……完全过时了。简而言之,该语言中新的ref locals功能允许您将自己的托管指针声明为局部变量,并使用它来合并单个数组取消引用操作。因此,例如上面的测试结构......
public struct rec { public int a, b, c, d, e, f; }
static rec[] s7 = new rec[100000];
...现在可以编写上面的相同测试函数的方式:
static void test_7(int ix)
{
ref rec e = ref s7[ix]; // <--- C#7 ref local
e.a = 4; e.e = e.a; e.b = e.d; e.f = e.d; e.b = e.e; e.a = e.c;
e.b = 5; e.d = e.f; e.c = e.b; e.e = e.a; e.b = e.d; e.f = e.d;
e.c = 6; e.b = e.e; e.a = e.c; e.d = e.f; e.c = e.b; e.e = e.a;
e.d = 7; e.b = e.d; e.f = e.d; e.b = e.e; e.a = e.c; e.d = e.f;
e.e = 8; e.c = e.b; e.e = e.a; e.b = e.d; e.f = e.d; e.b = e.e;
e.f = 9; e.a = e.c; e.d = e.f; e.c = e.b; e.e = e.a; e.b = e.d;
e.a = 10; e.f = e.d; e.b = e.e; e.a = e.c; e.d = e.f; e.c = e.b;
}
请注意,这如何完全消除了对我上面讨论的那些杂物的需求。托管指针的更流畅的使用避免了在“赢家”中使用的不必要的函数调用,这是我审查过的那些表现最好的方法。因此,新特征的性能只能优于上述方法的获胜者。
具有讽刺意味的是,C# 7 还添加了本地函数,这一特性将直接解决我为上述两个黑客提出的关于封装不良的抱怨。令人高兴的是,仅仅为了访问托管指针而增加专用函数的整个企业现在完全没有实际意义。