经过一些分析后,我们发现我们的应用程序连接字符串的当前方式会导致大量的内存流失和 CPU 时间。
我们正在建设一个List<string>
要连接的字符串长度约为 50 万个元素,引用了数百兆字节的字符串。我们正在尝试优化应用程序的这一小部分,因为它似乎占用了不成比例的 CPU 和内存使用量。
我们做了很多文本处理:)
理论上,我们应该能够在一次分配和 N 个副本中执行串联 - 我们可以知道字符串中总共有多少个可用字符,因此它应该像总结组成字符串的长度并分配足够的字符一样简单底层内存来保存结果。
假设我们从预填充开始List<string>
,是否可以使用单个分配连接该列表中的所有字符串?
目前,我们正在使用StringBuilder
类,但这存储了它自己的所有字符的中间缓冲区 - 所以我们有一个不断增长的块数组,每个块存储我们给它的字符的副本。远非理想。块数组的分配并不可怕,但最糟糕的是它分配中间字符数组,这意味着 N 次分配和副本。
我们现在能做的最好的事情就是打电话List<string>.ToArray()
- 执行 500k 元素数组的一份副本 - 并传递结果string[]
to string.Concat(params string[])
. string.Concat()
然后执行两次分配,一次将输入数组复制到内部数组,另一次分配目标字符串的内存。
来自referencesource.microsoft.com:
public static String Concat(params String[] values) {
if (values == null)
throw new ArgumentNullException("values");
Contract.Ensures(Contract.Result<String>() != null);
// Spec#: Consider a postcondition saying the length of this string == the sum of each string in array
Contract.EndContractBlock();
int totalLength=0;
// -----------> Allocation #1 <---------
String[] internalValues = new String[values.Length];
for (int i=0; i<values.Length; i++) {
string value = values[i];
internalValues[i] = ((value==null)?(String.Empty):(value));
totalLength += internalValues[i].Length;
// check for overflow
if (totalLength < 0) {
throw new OutOfMemoryException();
}
}
return ConcatArray(internalValues, totalLength);
}
private static String ConcatArray(String[] values, int totalLength) {
// -----------------> Allocation #2 <---------------------
String result = FastAllocateString(totalLength);
int currPos=0;
for (int i=0; i<values.Length; i++) {
Contract.Assert((currPos <= totalLength - values[i].Length),
"[String.ConcatArray](currPos <= totalLength - values[i].Length)");
FillStringChecked(result, currPos, values[i]);
currPos+=values[i].Length;
}
return result;
}
因此,在最好的情况下,我们有三个分配,两个用于引用组件字符串的数组,一个用于目标连接字符串。
我们可以对此进行改进吗?是否可以连接一个List<string>
使用单个分配和单个字符副本循环?
Edit 1
我想总结一下迄今为止讨论的各种方法,以及为什么它们仍然不是最佳的。我还想更具体地设置情况参数,因为我收到了很多试图回避核心问题的问题。
...
首先,我正在使用的代码的结构。共有三层:
- 第一层是一组生成我的内容的方法。这些方法返回小型字符串对象,我将其称为“组件”字符串。这些字符串对象最终将连接成一个字符串。我没有能力修改这些方法;我必须面对现实,他们返回字符串对象并继续前进。
- 第二层是我的代码,它调用这些内容生成器并组装输出,这是这个问题的主题。我必须调用内容生成器方法,收集它们返回的字符串,并最终将返回的字符串连接成一个字符串(实际情况稍微复杂一些;返回的字符串根据它们的输出路由方式进行分区,所以我有几组大型字符串集合)。
- 第三层是一组接受单个大字符串以进行进一步处理的方法。更改该代码的界面超出了我的控制范围。
谈论一些数字:典型的批处理运行将从内容生产者收集约 500000 个字符串,相当于约 200-500 MB 的内存。我需要最有效的方法将这 500k 字符串连接成一个字符串。
...
现在我想检查一下迄今为止讨论的方法。就数字而言,假设我们运行 64 位,假设我们正在收集 500000 个字符串对象,并假设字符串对象的总大小相当于 200 MB 的字符数据。另外,假设原始字符串对象的内存是没有计算在内以下分析中任何方法的总和。我做出这个假设是因为它对于任何和所有方法来说都是常见的,因为它是一个假设,即我们无法更改内容生成器的接口 - 它们返回 500k 相对较小的完全形成的字符串对象,然后我必须接受这些对象并以某种方式连接。如上所述,我无法更改此界面。
方法#1
内容制作者---->StringBuilder
---->string
从概念上讲,这将调用内容生成器,并直接将它们返回的字符串写入StringBuilder
,然后稍后调用StringBuilder.ToString()
以获得连接的字符串。
通过分析StringBuilder
的实现,我们可以看到其成本归结为 400 MB 的分配和复制:
- 在我们从内容制作者收集输出的阶段,我们将 200 MB 的数据写入
StringBuilder
。我们将执行一次 200 MB 分配来预分配StringBuilder
,然后当我们复制并丢弃从内容生产者返回的字符串时,会产生 200 MB 的副本
- 在我们收集了内容制作者的所有输出并形成了完整的
StringBuilder
,然后我们需要调用StringBuilder.ToString()
。这恰好执行一次分配(string.FastAllocateString()
),然后将字符串数据从其内部缓冲区复制到字符串对象的内部存储器。
总成本:大约 400 MB 的分配和副本
方法#2
内容生产者--->预分配char[]
--->string
这个策略相当简单。假设我们大致知道将从生产者那里收集多少角色数据,我们可以预先分配char[]
大小为 200 MB。然后,正如我们所说的内容生产者,我们将他们返回的字符串复制到我们的char[]
。这占了 200 MB 的分配和副本。将其转换为字符串对象的最后一步是将其传递给new string(char[])
构造函数。但是,由于字符串是不可变的,而数组则不然,构造函数将复制整个数组,从而使其分配并复制另外 200 MB 的字符数据。
总成本:大约 400 MB 的分配和副本
方法#3:
内容制作者 --->List<string>
---->string[]
---->string.Concat(string[])
- 预先分配一个
List<string>
大约 500k 元素 - List 底层数组的大约 4 MB 分配(500k * 每个指针 8 字节 == 4 MB 内存)。
- 致电所有内容制作者来收集他们的字符串。当我们将返回字符串的指针复制到 List 的底层数组中时,大约需要 4 MB 的副本。
- Call
List<string>.ToArray()
获得一个string[]
。大约 4 MB 的分配和复制(同样,我们实际上只是复制指针)。
- Call
string.Concat(string[])
:
- Concat 将在执行任何实际工作之前复制提供给它的数组。同样,大约 4 MB 的分配和副本。
- 然后,Concat 将使用内部分配单个“目标”字符串对象
string.FastAllocateString()
特殊方法。大约 200 MB 的分配量。
- 然后,Concat 会将字符串从提供的数组的内部副本直接复制到目标中。大约 200 MB 的副本。
总成本:大约 212 MB 的分配和副本
这些方法都不是理想的,但方法 3 非常接近。我们假设需要分配和复制的绝对最小内存为 200 MB(对于目标字符串),而这里我们非常接近 - 212 MB。
如果有一个string.Concat
过载 1) 接受IList<string>
2)在使用之前没有复制该IList,那么问题就解决了。 .Net 没有提供这样的方法,因此是这个问题的主题。
Edit 2
解决方案的进展.
我用一些被黑的 IL 做了一些测试,发现直接调用string.FastAllocateString(n)
(通常不可调用...)与调用一样快new string('\0', n)
,并且两者都seem分配与预期一样多的内存。
从那里,似乎可以使用以下命令获取指向新分配的字符串的指针:unsafe
and fixed
声明。
于是,一个粗略的解决方案开始出现:
private static string Concat( List<string> list )
{
int concatLength = 0;
for( int i = 0; i < list.Count; i++ )
{
concatLength += list[i].Length;
}
string newString = new string( '\0', concatLength );
unsafe
{
fixed( char* ptr = newString )
{
...
}
}
return newString;
}
下一个最大的障碍是实现或找到一种有效的块复制方法,ala Buffer.BlockCopy,除了接受的方法char*
types.