是否可以仅使用一次分配来连接字符串列表？
Is it possible to concatenate a list of strings using only a single allocation?
进行一些分析后，我们发现我们的应用程序连接字符串的当前方式会导致大量内存流失和 CPU 时间。
我们正在构建一个 List<string> 字符串来连接，其长度约为 50 万个元素，引用了数百兆字节的字符串。我们正在尝试优化我们应用程序的这一小部分，因为它似乎占了不成比例的 CPU 和内存使用量。
我们做了很多文本处理:)
理论上，我们应该能够在一次分配和 N 个副本中执行连接 - 我们可以知道我们的字符串中总共有多少个字符可用，所以它应该就像总结字符串的长度一样简单组件字符串并分配足够的底层内存来保存结果。
假设我们从预填充的 List<string> 开始，是否可以使用一次分配连接该列表中的所有字符串？
目前，我们正在使用 StringBuilder class，但这存储了它自己的所有字符的中间缓冲区 - 所以我们有一个不断增长的块数组，每个块存储一个我们给它的字符的副本。远非理想。块数组的分配并不可怕，但最糟糕的是它分配了中间字符数组，这意味着 N 次分配和复制。
我们现在能做的最好的事情是调用 List<string>.ToArray() - 它执行一个 500k 元素数组的副本 - 并将结果 string[] 传递给 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>？
编辑 1
我想总结一下到目前为止讨论的各种方法，以及为什么它们仍然不是最佳方法。我还想更具体地设置情况的参数，因为我收到了很多试图回避中心问题的问题。
...
首先，我正在使用的代码结构。一共有三层：
- 第一层是一组生成我的内容的方法。这些方法 return 小型字符串对象，我称之为 'component' 字符串。这些字符串对象最终将连接成一个字符串。我没有能力修改这些方法；我不得不面对他们 return 字符串对象并继续前进的现实。
- 第二层是我调用这些内容生产者并组装输出的代码，是这个问题的主题。我必须调用内容生成器方法，收集它们 return 的字符串，并最终将 returned 字符串连接成一个字符串（实际情况稍微复杂一些；returned 字符串是根据它们的输出路由方式进行分区，因此我有几组大型字符串集合）。
- 第三层是一组接受单个大字符串以进行进一步处理的方法。更改该代码的界面超出了我的控制范围。
谈论一些数字：一个典型的批次 运行 将从内容制作者那里收集大约 500000 个字符串，代表大约 200-500 MB 的内存。我需要最有效的方法将这 500k 个字符串连接成一个字符串。
...
现在我想检查一下到目前为止讨论的方法。为了数字，假设我们是 运行ning 64 位，假设我们正在收集 500000 个字符串对象，并假设字符串对象的总大小总计 200 兆字节的字符数据。此外，假设原始字符串对象的内存不计入以下分析中任何方法的总内存。我做这个假设是因为它对任何和所有方法都是通用的，因为这是一个假设我们不能改变内容制作者的界面——他们 return 500k 相对较小的完全形成的字符串对象，然后我必须接受和以某种方式连接。如上所述，我无法更改此界面。
方法 #1
内容生产者---->StringBuilder---->string
从概念上讲，这将调用内容生产者，并将他们 return 的字符串直接写入 StringBuilder，然后调用 StringBuilder.ToString() 以获得连接的字符串。
通过分析 StringBuilder 的实现，我们可以看出其成本归结为 400 MB 的分配和复制：
- 在我们从内容制作者收集输出的阶段，我们将 200 MB 的数据写入
StringBuilder。我们将执行一个 200 MB 的分配来预分配 StringBuilder，然后在我们复制和丢弃从内容生产者 编辑的字符串时执行 200 MB 的副本
- 在我们收集了内容制作者的所有输出并形成完整的
StringBuilder 之后，我们需要调用 StringBuilder.ToString()。这只执行一次分配（string.FastAllocateString()），然后将字符串数据从其内部缓冲区复制到字符串对象的内部内存中。
总成本：大约 400 MB 的分配和副本
方法 #2
内容制作者--->预分配char[]--->string
这个策略相当简单。假设我们大致知道我们将从生产者那里收集多少字符数据，我们可以预先分配一个 200 MB 的 char[]。然后，正如我们所说的内容生产者，我们将他们 return 的字符串复制到我们的 char[] 中。这占 200 MB 的分配和副本。将其转换为字符串对象的最后一步是将其传递给 new string(char[]) 构造函数。然而，由于字符串是不可变的而数组不是，构造函数将复制整个数组，导致它分配和复制另外 200 MB 的字符数据。
总成本：大约 400 MB 的分配和副本
方法 #3：
内容制作者---> List<string> ----> string[] ----> string.Concat(string[])
- 预分配一个
List<string> 大约 500k 个元素 - 大约 4 MB 的 List 底层数组分配（500k * 每个指针 8 个字节 == 4 MB 内存）。
- 召集所有的内容制作者收集他们的字符串。大约 4 MB 的副本，因为我们将指向 returned 字符串的指针复制到 List 的底层数组中。
- 调用
List<string>.ToArray()获得string[]。大约 4 MB 的分配和复制（同样，我们实际上只是复制指针）。
- 致电
string.Concat(string[])：
- Concat 会在执行任何实际工作之前复制提供给它的数组。大约 4 MB 的分配和副本。
- Concat 然后将使用内部
string.FastAllocateString() 特殊方法分配单个 'destination' 字符串对象。大约 200 MB 的分配。
- Concat 然后将字符串从提供的数组的内部副本直接复制到目标中。大约 200 MB 的副本。
总成本：大约 212 MB 的分配和副本
None 这些方法是理想的，但是方法 #3 非常接近。我们假设需要分配和复制的内存的绝对最小值是 200 MB（对于目标字符串），这里我们非常接近 - 212 MB。
如果有一个 string.Concat 重载 1) 接受了一个 IList<string> 并且 2) 在使用它之前没有复制那个 IList，那么问题就解决了。 .Net 没有提供这样的方法，因此是这个问题的主题。
编辑 2
解决方案取得进展。
我用一些被黑的 IL 做了一些测试，发现直接调用 string.FastAllocateString(n)（通常不可调用...）与调用 new string('[=46=]', n) 一样快，而且两者都是似乎 分配了与预期一样多的内存。
从那里，似乎可以使用 unsafe 和 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( '[=11=]', concatLength );
unsafe
{
fixed( char* ptr = newString )
{
...
}
}
return newString;
}
下一个最大的障碍是实施或找到一种有效的块复制方法，ala Buffer.BlockCopy，除了接受 char* 类型的方法。
如果您可以在尝试执行操作之前确定串联的长度，则 char 数组在某些用例中可以击败字符串生成器。操作数组中的字符可防止多次分配。
更新
请查看 .NET String.Join 的内部实现 - 它使用带有指针的不安全代码来避免多次分配。除非我遗漏了什么，否则您似乎可以使用您的列表重写它来完成您想要的：
[System.Security.SecuritySafeCritical] // auto-generated
public unsafe static String Join(String separator, String[] value, int startIndex, int count) {
//Range check the array
if (value == null)
throw new ArgumentNullException("value");
if (startIndex < 0)
throw new ArgumentOutOfRangeException("startIndex", Environment.GetResourceString("ArgumentOutOfRange_StartIndex"));
if (count < 0)
throw new ArgumentOutOfRangeException("count", Environment.GetResourceString("ArgumentOutOfRange_NegativeCount"));
if (startIndex > value.Length - count)
throw new ArgumentOutOfRangeException("startIndex", Environment.GetResourceString("ArgumentOutOfRange_IndexCountBuffer"));
Contract.EndContractBlock();
//Treat null as empty string.
if (separator == null) {
separator = String.Empty;
}
//If count is 0, that skews a whole bunch of the calculations below, so just special case that.
if (count == 0) {
return String.Empty;
}
int jointLength = 0;
//Figure out the total length of the strings in value
int endIndex = startIndex + count - 1;
for (int stringToJoinIndex = startIndex; stringToJoinIndex <= endIndex; stringToJoinIndex++) {
if (value[stringToJoinIndex] != null) {
jointLength += value[stringToJoinIndex].Length;
}
}
//Add enough room for the separator.
jointLength += (count - 1) * separator.Length;
// Note that we may not catch all overflows with this check (since we could have wrapped around the 4gb range any number of times
// and landed back in the positive range.) The input array might be modifed from other threads,
// so we have to do an overflow check before each append below anyway. Those overflows will get caught down there.
if ((jointLength < 0) || ((jointLength + 1) < 0) ) {
throw new OutOfMemoryException();
}
//If this is an empty string, just return.
if (jointLength == 0) {
return String.Empty;
}
string jointString = FastAllocateString( jointLength );
fixed (char * pointerToJointString = &jointString.m_firstChar) {
UnSafeCharBuffer charBuffer = new UnSafeCharBuffer( pointerToJointString, jointLength);
// Append the first string first and then append each following string prefixed by the separator.
charBuffer.AppendString( value[startIndex] );
for (int stringToJoinIndex = startIndex + 1; stringToJoinIndex <= endIndex; stringToJoinIndex++) {
charBuffer.AppendString( separator );
charBuffer.AppendString( value[stringToJoinIndex] );
}
Contract.Assert(*(pointerToJointString + charBuffer.Length) == '[=10=]', "String must be null-terminated!");
}
return jointString;
}
更新 2
关于快速分配的要点。根据一个旧的 SO post，你可以使用反射来包装 FastAllocate（当然假设你会缓存 fastAllocate 方法引用，所以你每次都调用 Invoke。也许调用的权衡比你现在在做什么。
var fastAllocate = typeof (string).GetMethods(BindingFlags.NonPublic | BindingFlags.Static)
.First(x => x.Name == "FastAllocateString");
var newString = (string)fastAllocate.Invoke(null, new object[] {20});
Console.WriteLine(newString.Length); // 20
也许另一种方法是使用不安全代码将您的分配复制到 char* 数组中，然后将其传递给字符串构造函数。带有 char* 的字符串构造函数是传递给底层 C++ 实现的 extern。我还没有找到该代码的可靠来源来确认，但也许这对您来说会更快。非产品就绪代码（不检查潜在溢出，添加固定以锁定来自垃圾收集的字符串等）将以：
开头
public unsafe string MyConcat(List<string> values)
{
int index = 0;
int totalLength = values.Sum(m => m.Length);
char* concat = stackalloc char[totalLength + 1]; // Add additional char for null term
foreach (var value in values)
{
foreach (var c in value)
{
concat[index] = c;
index++;
}
}
concat[index] = '[=12=]';
return new string(concat);
}
现在我对此一无所知 :) 也许有人可以在这里找到一种方法，通过编组来避免不安全的代码。由于引入不安全代码需要将不安全标志添加到编译中，因此请考虑将此部分添加为单独的 dll，以便在您走这条路时将应用的安全风险降至最低。
我的前两个答案现在已经包含在问题中了。这是我高度依赖的情况，但很有用 -
第三个答案
如果在所有这些 MB 的字符串中你得到很多相同的字符串，那么更聪明的方法是使用两个字典，一个是 Dictionary<int, int> 来存储 position 和 "Id" 在该位置的字符串，而另一个将是 Dictionary<int, int> 以存储 "Id" 和原始字符串中实际字符串的索引 [].
对我来说巧合的是，我正在尝试做的事情已经在 C# 中实现了。有点像这样...
如果确实有很多相同的字符串，String Interning 是不是很少见？如果大量匹配字符串来自内容制作者，您肯定会节省大量 200 MB 目标。
什么是String.Intern？
When you use strings in C#, the CLR does something clever called
string interning. It's a way of storing one copy of any string. If you
end up having a hundred—or, worse, a million—strings with the same
value, it's a waste to take up all of that memory storing the same
string over and over again. String interning is a way around that.
The CLR maintains a table called the intern pool that contains a
single, unique reference to every literal string that's either
declared or created programmatically while your program's running. And
the .NET Framework gives you two useful methods for interacting with
the intern pool: String.Intern() and String.IsInterned().
The way String.Intern() works is pretty straightforward. You pass it a
single string as an argument. If that string is already in the intern
pool, it returns a reference to that string. If it's not already in
the intern pool, it adds it and returns the same reference you passed
into it.
link 中解释了使用 String Interning 的方法。为了这个答案的完整性，我可以在此处添加代码，但前提是您认为这些解决方案有用。
StringBuilder 旨在有效地连接字符串。它没有其他用途。
使用设置初始容量的构造函数：
int totalLength = CalcTotalLength();
// sufficient capacity
StringBuilder sb = new StringBuilder(totalLength);
但是你说连StringBuilder都分配中间内存，你想做得更好...
这些是不寻常的要求，因此您需要编写一个适合您情况的函数（创建一个适当大小的 char[]，然后填充它）。我相信你有能力。
除非字符串的平均长度非常小，否则最有效的方法，给定 List<String>，将使用 ToArray() 将其复制到新的 String[]，并将其传递给连接或连接方法。如果串联或连接方法想要在开始之前复制其数组，那么这样做可能会导致引用数组的浪费分配，但这只会为每个字符串分配一个引用，只有一个分配来保存字符数据, 并且它的大小会正确地容纳整个字符串。
如果您自己构建数据结构，您可以通过将 String[] 初始化为估计的所需大小、自行填充并根据需要扩展它来提高效率。这将节省一份 String[] 的数据分配。
另一种方法是分配一个 String[8192][]，然后为每个字符串数组分配一个 String[8192]。完成所有操作后，您将确切知道需要传递给 Concat 方法的 String[] 大小，以便您可以创建具有该确切大小的数组。这种方法需要更多的分配，但只有最后的 String[] 和 String 本身需要在大对象堆上进行。
很遗憾你给自己施加的限制。它的结构非常块状，很难让任何流程继续进行。例如，如果您不期望 IList 而只期望 IEnumerable，您可以使您的内容的 生产者 更容易。不仅如此，您还可以通过仅在需要时使用字符串 - 并且仅在生成它们时使用这些字符串来使您的处理受益。
这让你走上了一些不错的异步之路。
在另一端，他们让您一次发送所有内容。太难了。
但话说回来，既然你要 运行 一遍又一遍，等等......我想知道你是否无法创建你的字符串缓冲区或字节缓冲区或 StringBuilder 或无论如何 - 并在执行之间重用它 - 一次分配最大怪物（或根据需要逐步重新分配它） - 不要让 gc 拥有它。字符串构造函数将一遍又一遍地复制它——但这是每个周期的一次分配。如果您 运行 如此频繁地使用它会使机器变热，那么它可能值得一试。在不久的过去，我已经做出了准确的权衡（但我没有 5gb 可以窒息）。一开始感觉很脏 - 但哇哦 - 吞吐量很大声！
此外，虽然您的原生 API 需要一个字符串，但您可以对它撒谎 - 让它认为您正在给它一个字符串。您很可能在末尾传递带有空字符的缓冲区 - 或者长度 - 取决于 API 的细节。我想有一两个评论者谈到了这个。在这种情况下，您可能需要在调用 big ol' 字符串的本机使用者期间固定缓冲区。
如果是这种情况，您只能一次性分配缓冲区，重复复制到其中，仅此而已。在您提出的最佳情况下，它可能会成功。
我已经实现了一种将 List 连接成单个字符串的方法，该字符串只执行一次分配。
以下代码在 .Net 4.6 下编译 - Block.MemoryCopy 直到 4.6 才添加到 .Net。
"unsafe" 实现：
public static unsafe class FastConcat
{
public static string Concat( IList<string> list )
{
string destinationString;
int destLengthChars = 0;
for( int i = 0; i < list.Count; i++ )
{
destLengthChars += list[i].Length;
}
destinationString = new string( '[=10=]', destLengthChars );
unsafe
{
fixed( char* origDestPtr = destinationString )
{
char* destPtr = origDestPtr; // a pointer we can modify.
string source;
for( int i = 0; i < list.Count; i++ )
{
source = list[i];
fixed( char* sourcePtr = source )
{
Buffer.MemoryCopy(
sourcePtr,
destPtr,
long.MaxValue,
source.Length * sizeof( char )
);
}
destPtr += source.Length;
}
}
}
return destinationString;
}
}
竞争实施是以下 "safe" 实施：
public static string Concat( IList<string> list )
{
return string.Concat( list.ToArray() )
}
内存消耗
- "unsafe" 实现恰好执行一次分配和零次临时分配。
List<string> 直接串联成一个新分配的 string 对象。
- "safe" 实现需要列表的两份副本 - 一份，当我调用
ToArray() 将其传递给 string.Concat 时，另一份当 string.Concat 执行它自己的数组的内部副本。
连接 500k 元素列表时，"safe" string.Concat 方法在 64 位进程中分配了恰好 8 MB 的额外内存，我已通过 运行 确认在内存监视器中测试驱动程序。这是我们对安全实现执行的数组副本的期望。
CPU 表现
对于小型工作集，不安全实施似乎胜出约 25%。
测试驱动程序通过 64 位编译、通过 NGEN 将程序安装到本机图像缓存中以及从卸载工作站上的调试器外部 运行 进行测试。
来自我的带有小型工作集的测试驱动程序（500k 个字符串，每个 2-10 个字符长）：
Unsafe Time: 17.266 ms
Unsafe Time: 18.419 ms
Unsafe Time: 16.876 ms
Safe Time: 21.265 ms
Safe Time: 21.890 ms
Safe Time: 24.492 ms
不安全平均值：17.520 毫秒。安全平均值：22.549 毫秒。 safe 比 unsafe 花费大约 25% 的时间。这可能是由于安全实施必须完成的额外工作，即分配临时数组。
...
来自我的具有大型工作集（500k 字符串，每个 500-800 个字符长）的测试驱动程序：
Unsafe Time: 498.122 ms
Unsafe Time: 513.725 ms
Unsafe Time: 515.016 ms
Safe Time: 487.456 ms
Safe Time: 499.508 ms
Safe Time: 512.390 ms
如您所见，大字符串的性能差异大致为零，可能是因为时间由原始副本支配。
结论
如果您不关心数组副本，安全实现实现起来非常简单，并且大致与不安全实现一样快。如果你想绝对完美地使用内存，请使用不安全的实现。
我附上了用于测试工具的代码：
class PerfTestHarness
{
private List<string> corpus;
public PerfTestHarness( List<string> corpus )
{
this.corpus = corpus;
// Warm up the JIT
// Note that `result` is discarded. We reference it via 'result[0]' as an
// unused paramater to my prints to be absolutely sure it doesn't get
// optimized out. Cheap hack, but it works.
string result;
result = FastConcat.Concat( this.corpus );
Console.WriteLine( "Fast warmup done", result[0] );
result = string.Concat( this.corpus.ToArray() );
Console.WriteLine( "Safe warmup done", result[0] );
GC.Collect();
GC.WaitForPendingFinalizers();
}
public void PerfTestSafe()
{
Stopwatch watch = new Stopwatch();
string result;
GC.Collect();
GC.WaitForPendingFinalizers();
watch.Start();
result = string.Concat( this.corpus.ToArray() );
watch.Stop();
Console.WriteLine( "Safe Time: {0:0.000} ms", watch.Elapsed.TotalMilliseconds, result[0] );
Console.WriteLine( "Memory usage: {0:0.000} MB", Environment.WorkingSet / 1000000.0 );
Console.WriteLine();
}
public void PerfTestUnsafe()
{
Stopwatch watch = new Stopwatch();
string result;
GC.Collect();
GC.WaitForPendingFinalizers();
watch.Start();
result = FastConcat.Concat( this.corpus );
watch.Stop();
Console.WriteLine( "Unsafe Time: {0:0.000} ms", watch.Elapsed.TotalMilliseconds, result[0] );
Console.WriteLine( "Memory usage: {0:0.000} MB", Environment.WorkingSet / 1000000.0 );
Console.WriteLine();
}
}
进行一些分析后，我们发现我们的应用程序连接字符串的当前方式会导致大量内存流失和 CPU 时间。
我们正在构建一个 List<string> 字符串来连接，其长度约为 50 万个元素，引用了数百兆字节的字符串。我们正在尝试优化我们应用程序的这一小部分，因为它似乎占了不成比例的 CPU 和内存使用量。
我们做了很多文本处理:)
理论上，我们应该能够在一次分配和 N 个副本中执行连接 - 我们可以知道我们的字符串中总共有多少个字符可用，所以它应该就像总结字符串的长度一样简单组件字符串并分配足够的底层内存来保存结果。
假设我们从预填充的 List<string> 开始，是否可以使用一次分配连接该列表中的所有字符串？
目前，我们正在使用 StringBuilder class，但这存储了它自己的所有字符的中间缓冲区 - 所以我们有一个不断增长的块数组，每个块存储一个我们给它的字符的副本。远非理想。块数组的分配并不可怕，但最糟糕的是它分配了中间字符数组，这意味着 N 次分配和复制。
我们现在能做的最好的事情是调用 List<string>.ToArray() - 它执行一个 500k 元素数组的副本 - 并将结果 string[] 传递给 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>？
编辑 1
我想总结一下到目前为止讨论的各种方法，以及为什么它们仍然不是最佳方法。我还想更具体地设置情况的参数，因为我收到了很多试图回避中心问题的问题。
...
首先，我正在使用的代码结构。一共有三层：
- 第一层是一组生成我的内容的方法。这些方法 return 小型字符串对象，我称之为 'component' 字符串。这些字符串对象最终将连接成一个字符串。我没有能力修改这些方法；我不得不面对他们 return 字符串对象并继续前进的现实。
- 第二层是我调用这些内容生产者并组装输出的代码，是这个问题的主题。我必须调用内容生成器方法，收集它们 return 的字符串，并最终将 returned 字符串连接成一个字符串（实际情况稍微复杂一些；returned 字符串是根据它们的输出路由方式进行分区，因此我有几组大型字符串集合）。
- 第三层是一组接受单个大字符串以进行进一步处理的方法。更改该代码的界面超出了我的控制范围。
谈论一些数字：一个典型的批次 运行 将从内容制作者那里收集大约 500000 个字符串，代表大约 200-500 MB 的内存。我需要最有效的方法将这 500k 个字符串连接成一个字符串。
...
现在我想检查一下到目前为止讨论的方法。为了数字，假设我们是 运行ning 64 位，假设我们正在收集 500000 个字符串对象，并假设字符串对象的总大小总计 200 兆字节的字符数据。此外，假设原始字符串对象的内存不计入以下分析中任何方法的总内存。我做这个假设是因为它对任何和所有方法都是通用的，因为这是一个假设我们不能改变内容制作者的界面——他们 return 500k 相对较小的完全形成的字符串对象，然后我必须接受和以某种方式连接。如上所述，我无法更改此界面。
方法 #1
内容生产者---->StringBuilder---->string
从概念上讲，这将调用内容生产者，并将他们 return 的字符串直接写入 StringBuilder，然后调用 StringBuilder.ToString() 以获得连接的字符串。
通过分析 StringBuilder 的实现，我们可以看出其成本归结为 400 MB 的分配和复制：
- 在我们从内容制作者收集输出的阶段，我们将 200 MB 的数据写入
StringBuilder。我们将执行一个 200 MB 的分配来预分配StringBuilder，然后在我们复制和丢弃从内容生产者 编辑的字符串时执行 200 MB 的副本
- 在我们收集了内容制作者的所有输出并形成完整的
StringBuilder之后，我们需要调用StringBuilder.ToString()。这只执行一次分配（string.FastAllocateString()），然后将字符串数据从其内部缓冲区复制到字符串对象的内部内存中。
总成本：大约 400 MB 的分配和副本
方法 #2
内容制作者--->预分配char[]--->string
这个策略相当简单。假设我们大致知道我们将从生产者那里收集多少字符数据，我们可以预先分配一个 200 MB 的 char[]。然后，正如我们所说的内容生产者，我们将他们 return 的字符串复制到我们的 char[] 中。这占 200 MB 的分配和副本。将其转换为字符串对象的最后一步是将其传递给 new string(char[]) 构造函数。然而，由于字符串是不可变的而数组不是，构造函数将复制整个数组，导致它分配和复制另外 200 MB 的字符数据。
总成本：大约 400 MB 的分配和副本
方法 #3：
内容制作者---> List<string> ----> string[] ----> string.Concat(string[])
- 预分配一个
List<string>大约 500k 个元素 - 大约 4 MB 的 List 底层数组分配（500k * 每个指针 8 个字节 == 4 MB 内存）。 - 召集所有的内容制作者收集他们的字符串。大约 4 MB 的副本，因为我们将指向 returned 字符串的指针复制到 List 的底层数组中。
- 调用
List<string>.ToArray()获得string[]。大约 4 MB 的分配和复制（同样，我们实际上只是复制指针）。 - 致电
string.Concat(string[])：- Concat 会在执行任何实际工作之前复制提供给它的数组。大约 4 MB 的分配和副本。
- Concat 然后将使用内部
string.FastAllocateString()特殊方法分配单个 'destination' 字符串对象。大约 200 MB 的分配。 - Concat 然后将字符串从提供的数组的内部副本直接复制到目标中。大约 200 MB 的副本。
总成本：大约 212 MB 的分配和副本
None 这些方法是理想的，但是方法 #3 非常接近。我们假设需要分配和复制的内存的绝对最小值是 200 MB（对于目标字符串），这里我们非常接近 - 212 MB。
如果有一个 string.Concat 重载 1) 接受了一个 IList<string> 并且 2) 在使用它之前没有复制那个 IList，那么问题就解决了。 .Net 没有提供这样的方法，因此是这个问题的主题。
编辑 2
解决方案取得进展。
我用一些被黑的 IL 做了一些测试，发现直接调用 string.FastAllocateString(n)（通常不可调用...）与调用 new string('[=46=]', n) 一样快，而且两者都是似乎 分配了与预期一样多的内存。
从那里，似乎可以使用 unsafe 和 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( '[=11=]', concatLength );
unsafe
{
fixed( char* ptr = newString )
{
...
}
}
return newString;
}
下一个最大的障碍是实施或找到一种有效的块复制方法，ala Buffer.BlockCopy，除了接受 char* 类型的方法。
如果您可以在尝试执行操作之前确定串联的长度，则 char 数组在某些用例中可以击败字符串生成器。操作数组中的字符可防止多次分配。
更新
请查看 .NET String.Join 的内部实现 - 它使用带有指针的不安全代码来避免多次分配。除非我遗漏了什么，否则您似乎可以使用您的列表重写它来完成您想要的：
[System.Security.SecuritySafeCritical] // auto-generated
public unsafe static String Join(String separator, String[] value, int startIndex, int count) {
//Range check the array
if (value == null)
throw new ArgumentNullException("value");
if (startIndex < 0)
throw new ArgumentOutOfRangeException("startIndex", Environment.GetResourceString("ArgumentOutOfRange_StartIndex"));
if (count < 0)
throw new ArgumentOutOfRangeException("count", Environment.GetResourceString("ArgumentOutOfRange_NegativeCount"));
if (startIndex > value.Length - count)
throw new ArgumentOutOfRangeException("startIndex", Environment.GetResourceString("ArgumentOutOfRange_IndexCountBuffer"));
Contract.EndContractBlock();
//Treat null as empty string.
if (separator == null) {
separator = String.Empty;
}
//If count is 0, that skews a whole bunch of the calculations below, so just special case that.
if (count == 0) {
return String.Empty;
}
int jointLength = 0;
//Figure out the total length of the strings in value
int endIndex = startIndex + count - 1;
for (int stringToJoinIndex = startIndex; stringToJoinIndex <= endIndex; stringToJoinIndex++) {
if (value[stringToJoinIndex] != null) {
jointLength += value[stringToJoinIndex].Length;
}
}
//Add enough room for the separator.
jointLength += (count - 1) * separator.Length;
// Note that we may not catch all overflows with this check (since we could have wrapped around the 4gb range any number of times
// and landed back in the positive range.) The input array might be modifed from other threads,
// so we have to do an overflow check before each append below anyway. Those overflows will get caught down there.
if ((jointLength < 0) || ((jointLength + 1) < 0) ) {
throw new OutOfMemoryException();
}
//If this is an empty string, just return.
if (jointLength == 0) {
return String.Empty;
}
string jointString = FastAllocateString( jointLength );
fixed (char * pointerToJointString = &jointString.m_firstChar) {
UnSafeCharBuffer charBuffer = new UnSafeCharBuffer( pointerToJointString, jointLength);
// Append the first string first and then append each following string prefixed by the separator.
charBuffer.AppendString( value[startIndex] );
for (int stringToJoinIndex = startIndex + 1; stringToJoinIndex <= endIndex; stringToJoinIndex++) {
charBuffer.AppendString( separator );
charBuffer.AppendString( value[stringToJoinIndex] );
}
Contract.Assert(*(pointerToJointString + charBuffer.Length) == '[=10=]', "String must be null-terminated!");
}
return jointString;
}
更新 2
关于快速分配的要点。根据一个旧的 SO post，你可以使用反射来包装 FastAllocate（当然假设你会缓存 fastAllocate 方法引用，所以你每次都调用 Invoke。也许调用的权衡比你现在在做什么。
var fastAllocate = typeof (string).GetMethods(BindingFlags.NonPublic | BindingFlags.Static)
.First(x => x.Name == "FastAllocateString");
var newString = (string)fastAllocate.Invoke(null, new object[] {20});
Console.WriteLine(newString.Length); // 20
也许另一种方法是使用不安全代码将您的分配复制到 char* 数组中，然后将其传递给字符串构造函数。带有 char* 的字符串构造函数是传递给底层 C++ 实现的 extern。我还没有找到该代码的可靠来源来确认，但也许这对您来说会更快。非产品就绪代码（不检查潜在溢出，添加固定以锁定来自垃圾收集的字符串等）将以：
public unsafe string MyConcat(List<string> values)
{
int index = 0;
int totalLength = values.Sum(m => m.Length);
char* concat = stackalloc char[totalLength + 1]; // Add additional char for null term
foreach (var value in values)
{
foreach (var c in value)
{
concat[index] = c;
index++;
}
}
concat[index] = '[=12=]';
return new string(concat);
}
现在我对此一无所知 :) 也许有人可以在这里找到一种方法，通过编组来避免不安全的代码。由于引入不安全代码需要将不安全标志添加到编译中，因此请考虑将此部分添加为单独的 dll，以便在您走这条路时将应用的安全风险降至最低。
我的前两个答案现在已经包含在问题中了。这是我高度依赖的情况，但很有用 -
第三个答案
如果在所有这些 MB 的字符串中你得到很多相同的字符串，那么更聪明的方法是使用两个字典，一个是 Dictionary<int, int> 来存储 position 和 "Id" 在该位置的字符串，而另一个将是 Dictionary<int, int> 以存储 "Id" 和原始字符串中实际字符串的索引 [].
对我来说巧合的是，我正在尝试做的事情已经在 C# 中实现了。有点像这样...
如果确实有很多相同的字符串，String Interning 是不是很少见？如果大量匹配字符串来自内容制作者，您肯定会节省大量 200 MB 目标。
什么是String.Intern？
When you use strings in C#, the CLR does something clever called string interning. It's a way of storing one copy of any string. If you end up having a hundred—or, worse, a million—strings with the same value, it's a waste to take up all of that memory storing the same string over and over again. String interning is a way around that. The CLR maintains a table called the intern pool that contains a single, unique reference to every literal string that's either declared or created programmatically while your program's running. And the .NET Framework gives you two useful methods for interacting with the intern pool: String.Intern() and String.IsInterned().
The way String.Intern() works is pretty straightforward. You pass it a single string as an argument. If that string is already in the intern pool, it returns a reference to that string. If it's not already in the intern pool, it adds it and returns the same reference you passed into it.
link 中解释了使用 String Interning 的方法。为了这个答案的完整性，我可以在此处添加代码，但前提是您认为这些解决方案有用。
StringBuilder 旨在有效地连接字符串。它没有其他用途。
使用设置初始容量的构造函数：
int totalLength = CalcTotalLength();
// sufficient capacity
StringBuilder sb = new StringBuilder(totalLength);
但是你说连StringBuilder都分配中间内存，你想做得更好...
这些是不寻常的要求，因此您需要编写一个适合您情况的函数（创建一个适当大小的 char[]，然后填充它）。我相信你有能力。
除非字符串的平均长度非常小，否则最有效的方法，给定 List<String>，将使用 ToArray() 将其复制到新的 String[]，并将其传递给连接或连接方法。如果串联或连接方法想要在开始之前复制其数组，那么这样做可能会导致引用数组的浪费分配，但这只会为每个字符串分配一个引用，只有一个分配来保存字符数据, 并且它的大小会正确地容纳整个字符串。
如果您自己构建数据结构，您可以通过将 String[] 初始化为估计的所需大小、自行填充并根据需要扩展它来提高效率。这将节省一份 String[] 的数据分配。
另一种方法是分配一个 String[8192][]，然后为每个字符串数组分配一个 String[8192]。完成所有操作后，您将确切知道需要传递给 Concat 方法的 String[] 大小，以便您可以创建具有该确切大小的数组。这种方法需要更多的分配，但只有最后的 String[] 和 String 本身需要在大对象堆上进行。
很遗憾你给自己施加的限制。它的结构非常块状，很难让任何流程继续进行。例如，如果您不期望 IList 而只期望 IEnumerable，您可以使您的内容的 生产者 更容易。不仅如此，您还可以通过仅在需要时使用字符串 - 并且仅在生成它们时使用这些字符串来使您的处理受益。
这让你走上了一些不错的异步之路。
在另一端，他们让您一次发送所有内容。太难了。
但话说回来，既然你要 运行 一遍又一遍，等等......我想知道你是否无法创建你的字符串缓冲区或字节缓冲区或 StringBuilder 或无论如何 - 并在执行之间重用它 - 一次分配最大怪物（或根据需要逐步重新分配它） - 不要让 gc 拥有它。字符串构造函数将一遍又一遍地复制它——但这是每个周期的一次分配。如果您 运行 如此频繁地使用它会使机器变热，那么它可能值得一试。在不久的过去，我已经做出了准确的权衡（但我没有 5gb 可以窒息）。一开始感觉很脏 - 但哇哦 - 吞吐量很大声！
此外，虽然您的原生 API 需要一个字符串，但您可以对它撒谎 - 让它认为您正在给它一个字符串。您很可能在末尾传递带有空字符的缓冲区 - 或者长度 - 取决于 API 的细节。我想有一两个评论者谈到了这个。在这种情况下，您可能需要在调用 big ol' 字符串的本机使用者期间固定缓冲区。
如果是这种情况，您只能一次性分配缓冲区，重复复制到其中，仅此而已。在您提出的最佳情况下，它可能会成功。
我已经实现了一种将 List 连接成单个字符串的方法，该字符串只执行一次分配。
以下代码在 .Net 4.6 下编译 - Block.MemoryCopy 直到 4.6 才添加到 .Net。
"unsafe" 实现：
public static unsafe class FastConcat
{
public static string Concat( IList<string> list )
{
string destinationString;
int destLengthChars = 0;
for( int i = 0; i < list.Count; i++ )
{
destLengthChars += list[i].Length;
}
destinationString = new string( '[=10=]', destLengthChars );
unsafe
{
fixed( char* origDestPtr = destinationString )
{
char* destPtr = origDestPtr; // a pointer we can modify.
string source;
for( int i = 0; i < list.Count; i++ )
{
source = list[i];
fixed( char* sourcePtr = source )
{
Buffer.MemoryCopy(
sourcePtr,
destPtr,
long.MaxValue,
source.Length * sizeof( char )
);
}
destPtr += source.Length;
}
}
}
return destinationString;
}
}
竞争实施是以下 "safe" 实施：
public static string Concat( IList<string> list )
{
return string.Concat( list.ToArray() )
}
内存消耗
- "unsafe" 实现恰好执行一次分配和零次临时分配。
List<string>直接串联成一个新分配的string对象。 - "safe" 实现需要列表的两份副本 - 一份，当我调用
ToArray()将其传递给 string.Concat 时，另一份当 string.Concat 执行它自己的数组的内部副本。
连接 500k 元素列表时，"safe" string.Concat 方法在 64 位进程中分配了恰好 8 MB 的额外内存，我已通过 运行 确认在内存监视器中测试驱动程序。这是我们对安全实现执行的数组副本的期望。
CPU 表现
对于小型工作集，不安全实施似乎胜出约 25%。
测试驱动程序通过 64 位编译、通过 NGEN 将程序安装到本机图像缓存中以及从卸载工作站上的调试器外部 运行 进行测试。
来自我的带有小型工作集的测试驱动程序（500k 个字符串，每个 2-10 个字符长）：
Unsafe Time: 17.266 ms
Unsafe Time: 18.419 ms
Unsafe Time: 16.876 ms
Safe Time: 21.265 ms
Safe Time: 21.890 ms
Safe Time: 24.492 ms
不安全平均值：17.520 毫秒。安全平均值：22.549 毫秒。 safe 比 unsafe 花费大约 25% 的时间。这可能是由于安全实施必须完成的额外工作，即分配临时数组。
...
来自我的具有大型工作集（500k 字符串，每个 500-800 个字符长）的测试驱动程序：
Unsafe Time: 498.122 ms
Unsafe Time: 513.725 ms
Unsafe Time: 515.016 ms
Safe Time: 487.456 ms
Safe Time: 499.508 ms
Safe Time: 512.390 ms
如您所见，大字符串的性能差异大致为零，可能是因为时间由原始副本支配。
结论
如果您不关心数组副本，安全实现实现起来非常简单，并且大致与不安全实现一样快。如果你想绝对完美地使用内存，请使用不安全的实现。
我附上了用于测试工具的代码：
class PerfTestHarness
{
private List<string> corpus;
public PerfTestHarness( List<string> corpus )
{
this.corpus = corpus;
// Warm up the JIT
// Note that `result` is discarded. We reference it via 'result[0]' as an
// unused paramater to my prints to be absolutely sure it doesn't get
// optimized out. Cheap hack, but it works.
string result;
result = FastConcat.Concat( this.corpus );
Console.WriteLine( "Fast warmup done", result[0] );
result = string.Concat( this.corpus.ToArray() );
Console.WriteLine( "Safe warmup done", result[0] );
GC.Collect();
GC.WaitForPendingFinalizers();
}
public void PerfTestSafe()
{
Stopwatch watch = new Stopwatch();
string result;
GC.Collect();
GC.WaitForPendingFinalizers();
watch.Start();
result = string.Concat( this.corpus.ToArray() );
watch.Stop();
Console.WriteLine( "Safe Time: {0:0.000} ms", watch.Elapsed.TotalMilliseconds, result[0] );
Console.WriteLine( "Memory usage: {0:0.000} MB", Environment.WorkingSet / 1000000.0 );
Console.WriteLine();
}
public void PerfTestUnsafe()
{
Stopwatch watch = new Stopwatch();
string result;
GC.Collect();
GC.WaitForPendingFinalizers();
watch.Start();
result = FastConcat.Concat( this.corpus );
watch.Stop();
Console.WriteLine( "Unsafe Time: {0:0.000} ms", watch.Elapsed.TotalMilliseconds, result[0] );
Console.WriteLine( "Memory usage: {0:0.000} MB", Environment.WorkingSet / 1000000.0 );
Console.WriteLine();
}
}