19

概括

在处理大型文本文件时,我遇到了以下(意外)我无法解释的性能下降。我对这个问题的目标是:

  • 了解导致下述减速的原因
  • 了解如何快速初始化大型非原始数组

问题

  • 数组包含非原始参考项
    • 不是int[]MyComplexType[]
    • MyComplexType是一个类,而不是一个结构
    • MyComplexType包含一些string属性
  • 数组是预分配的
  • 数组很大
  • 如果在没有分配给数组的情况下创建和使用项目,则程序很快
  • 如果创建了一个项目,然后将其分配给一个数组项目,则程序会显着减慢。
    • 我希望数组项分配是一个简单的引用分配,但根据我在下面的测试程序的结果,情况似乎并非如此

测试程序

考虑以下C#程序:

namespace Test
{
    public static class Program
    {
        // Simple data structure
        private sealed class Item
        {
            public Item(int i)
            {
                this.Name = "Hello " + i;
                //this.Name = "Hello";
                //this.Name = null;
            }
            public readonly string Name;
        }

        // Test program
        public static void Main()
        {
            const int length = 1000000;
            var items = new Item[length];

            // Create one million items but don't assign to array
            var w = System.Diagnostics.Stopwatch.StartNew();
            for (var i = 0; i < length; i++)
            {
                var item = new Item(i);
                if (!string.IsNullOrEmpty(item.Name)) // reference the item and its Name property
                {
                    items[i] = null; // do not remember the item
                }
            }
            System.Console.Error.WriteLine("Without assignment: " + w.Elapsed);

            // Create one million items and assign to array
            w.Restart();
            for (var i = 0; i < length; i++)
            {
                var item = new Item(i);
                if (!string.IsNullOrEmpty(item.Name)) // reference the item and its Name property
                {
                    items[i] = item; // remember the item
                }
            }
            System.Console.Error.WriteLine("   With assignment: " + w.Elapsed);
        }
    }
}

它包含两个几乎相同的循环。每个循环创建一百万个Item类实例。第一个循环使用创建的项目,然后丢弃引用(不将其保留在items数组中)。第二个循环使用创建的项目,然后将引用存储在items数组中。数组项分配是循环之间的唯一区别。

我的结果

  • 当我Release在我的机器上运行构建(打开优化)时,我得到以下结果:

    Without assignment: 00:00:00.2193348
       With assignment: 00:00:00.8819170
    

    有数组赋值的循环比没有赋值的循环要慢得多(慢约 4 倍)。

  • 如果我更改Item构造函数以将常量字符串分配给Name属性:

    public Item(int i)
    {
        //this.Name = "Hello " + i;
        this.Name = "Hello";
        //this.Name = null;
    }
    

    我得到以下结果:

    Without assignment: 00:00:00.0228067
       With assignment: 00:00:00.0718317
    

    有分配的循环仍然比没有分配的循环慢约 3 倍

  • 最后,如果我分配null给该Name属性:

    public Item(int i)
    {
        //this.Name = "Hello " + i;
        //this.Name = "Hello";
        this.Name = null;
    }
    

    我得到以下结果:

    Without assignment: 00:00:00.0146696
       With assignment: 00:00:00.0105369
    

    一旦没有分配字符串,没有分配的版本最终会稍微慢一些(我假设因为所有这些实例都被释放以进行垃圾收集)

问题

  • 为什么数组项分配会大大减慢测试程序的速度?

  • 是否有可以加快分配速度的属性/语言结构/等?

PS:我尝试使用 dotTrace 调查减速,但没有定论。我看到的一件事是,在有赋值的循环中,字符串复制和垃圾收集的开销比在没有赋值的循环中要多得多(尽管我预计会反过来)。

4

6 回答 6

26

I suspect most of the timing issues are related to memory allocation.

When you assign the items into the array, they are never becoming eligible for garbage collection. When you have a string as a property that isn't a constant (interned) or null, this is going to cause your memory allocation requirements to go up.

In the first case, I suspect what's happening is that you're churning through the objects fast, so they stay in Gen0, and can be GCed quickly, and that memory segment can be reused. This means that you're never having to allocate more memory from the OS.

In the second case, you're creating strings within your objects, both of which are two allocations, then storing these so they aren't eligible for GC. At some point, you'll need to get more memory, so you'll get allocated memory.

As for your final check - when you set the Name to null, the if (!string.IsNullOrEmpty(item.Name)) check will prevent it from being added. As such, the two code paths, and therefore the timings, become (effectively) identical, though the first is marginally slower (most likely due to the JIT running the first time).

于 2013-11-05T20:21:15.353 回答
2

我的猜测是编译器非常聪明,并且在您没有分配 Item 的情况下,您不需要对 Item 做任何重要的事情。它可能只是在第一个循环中重用 Item 对象内存,因为它可以。在第二个循环中,需要分配堆位,因为它们都是独立的,稍后会被引用。

我想这与您所看到的与垃圾收集有关的内容一致。在第一个循环中创建一个项目与许多项目。

快速说明 - 第一个循环可能使用对象池作为优化。 这篇文章可能会提供见解。正如 Reed 很快指出的那样,这篇文章谈到了应用程序优化,但我想分配器本身有很多优化可以做类似的事情。

于 2013-11-05T20:18:07.063 回答
1

我不相信这与数组分配(真的)有任何关系。它与必须保留项目及其包含的对象的时间量有关,以防您以后可以引用它们。它与堆分配和垃圾收集生成有关。

首次分配时item,它的字符串将位于“第 0 代”。这通常是垃圾收集的,并且非常热,甚至可能是缓存的内存。很有可能在循环的接下来的几次迭代中,整个“第 0 代”将被 GC 处理,并且内存重新用于 newitems及其字符串。当我们将赋值添加到数组时,对象不能被垃圾回收,因为它仍然存在引用。这会导致内存消耗增加。

我相信您会在代码执行期间看到内存增加:我认为问题在于堆中的内存分配与缓存未命中相结合,因为它始终必须使用“新”内存并且无法从硬件内存缓存中受益。

于 2013-11-05T20:31:46.340 回答
0

尝试解决您的实际问题(尽管这是一个有趣的难题)。我会推荐几件事:

  1. 不要将连接的字符串存储在构造中。使用get访问器返回字符串值。在诊断数组分配时,这会将字符串连接排除在外。如果您想在第一次使用计算值时“缓存”get它,那应该没问题。
  2. 对您的实际程序运行 dotTrace以更好地了解时间花费在哪里。由于您无法加快阵列分配速度,因此您应该寻找可以更改的其他区域。
于 2013-11-05T21:27:31.240 回答
0

在我看来,你是分支预测的受害者。让我们详细看看你在做什么:

在“无分配”的情况下,您只需将null分配给数组items的所有元素;通过这样做,处理器会在 for 循环的一些迭代之后学习您正在为数组项分配相同的值(甚至是null );因此不再需要if语句:您的程序将运行得更快。

在“有赋值”的情况下,处理器不知道新生成项的进程:在for循环的每次迭代中调用if语句;这会导致程序运行速度变慢...

这种行为依赖于称为分支预测单元的处理器硬件的一部分(消耗芯片的很大一部分晶体管......)一个类似的主题在这里很好地说明了为什么处理排序数组比处理未排序数组更快?

于 2013-11-05T21:50:14.720 回答
-3

好的,我还在寻找,但 MSDN 建议您使用集合(大概List<T>HashTable<T>类似的东西)而不是数组。 从 MSDN 文档

类库设计者可能需要就何时使用数组以及何时返回集合做出艰难的决定。尽管这些类型具有相似的使用模型,但它们具有不同的性能特征。通常,当支持添加、删除或其他操作集合的方法时,您应该使用集合

也许 .NET 规范文档中有一些内容。

于 2013-11-05T20:22:45.630 回答