logo标签列表

为什么这个List<>.IndexOf代码比List[i]和手动比较快这么多？

c#performanceindexof
10

我在这段代码上运行AQTime，发现.IndexOf占用了16%的时间，而其他部分接近80%... 它们似乎使用相同的IsEqual和其他例程。调用116,000次插入30,000个项目。没有List<>对象超过200个元素。(我可能在错误地使用AQTime，正在研究中)

class PointD : IEquatable<PointD>
{
    public double X, Y, Z;

    bool IEquatable<PointD>.Equals(PointD other)
    {
        return ((X == other.X) && (Y == other.Y) && (Z == other.Z));
    }
}

class PerfTest
{
    readonly List<PointD> _pCoord3Points = new List<PointD>();
    public int NewPoints;
    public int TotalPoints;

    public PerfTest()
    {
        NewPoints = 0;
        TotalPoints = 0;
    }
    public int CheckPointIndexOf(PointD pt)
    {
        int retIndex = _pCoord3Points.IndexOf(pt);
        if (retIndex < 0)
        {
            _pCoord3Points.Add(pt);
            NewPoints++;
        }
        TotalPoints++;
        return retIndex;    
    }

    public int CheckPointForBreak(PointD pt)
    {
        int retIndex = -1;
        for (int i = 0; i < _pCoord3Points.Count; i++)
        {
            PointD otherPt = _pCoord3Points[i];
            if ((pt.X == otherPt.X) &&
                (pt.Y == otherPt.Y) &&
                (pt.Z == otherPt.Z))
            {
                retIndex = i;
                break;
            }
        }
        if (retIndex == -1)
        {
            NewPoints++;
            _pCoord3Points.Add(pt);
        }
        TotalPoints++;
        return retIndex;
    }

    static void Main()
    {
        const int xmax = 300;
        const int ymax = 10;
        const int zmax = 10;
        const int imax = 4;

        var test = new PerfTest();
        //test.Init();
        Stopwatch sw = Stopwatch.StartNew();
        for (int i = 0; i < imax; i++)
        {
            for (int x = 0; x < xmax; x++)
            {
                for (int y = 0; y < ymax; y++)
                {
                    for (int z = 0; z < zmax; z++)
                    {
                        var pt = new PointD { X = x, Y = y, Z = z };
                        test.CheckPointIndexOf(pt);
                    }
                }
            }

        } 
        sw.Stop();
        string output = string.Format("Total: {0:0} New: {1:0} IndexOf: ", test.TotalPoints, test.NewPoints);
        Console.Write(output);
        Console.WriteLine(sw.Elapsed);

        test = new PerfTest();
        sw = Stopwatch.StartNew();
        for (int i = 0; i < imax; i++)
        {
            for (int x = 0; x < xmax; x++)
            {
                for (int y = 0; y < ymax; y++)
                {
                    for (int z = 0; z < zmax; z++)
                    {
                        var pt = new PointD { X = x, Y = y, Z = z };
                        test.CheckPointForBreak(pt);
                    }
                }
            }

        } 
        sw.Stop();
        output = string.Format("Total: {0:0} New: {1:0} PointD[] ", test.TotalPoints, test.NewPoints);
        Console.Write(output);
        Console.WriteLine(sw.Elapsed);
        Console.ReadLine();
    }
}
IndexOf 真的更快吗？当我尝试复制时，IndexOf 明显较慢，我认为 Jon 关于装箱的猜测是正确的。 - Dirk Vollmar
2
我得到了完全相反的结果，当PointD是一个结构体时，IndexOf的速度要慢20倍。结构体的Equals()方法并不便宜。请发布一个真正可验证的示例。 - Hans Passant
啊，如果IndexOf在你的机器上更快，但其他人的机器上不是，那可能是因为你的分析器。许多分析器不能平等地惩罚它们无法探测的代码。 - Rei Miyasaka
3个回答
11

我做了以下的假设：

  • PointD 是一个结构体
  • IndexOf 比手动迭代列表要慢

您可以通过实现 IEquatable<T> 接口来加速 IndexOf 的执行：

struct PointD : IEquatable<PointD>
{
    public int X;
    public int Y;
    public int Z;

    public bool Equals(PointD other)
    {
        return (this.X == other.X) &&
                (this.Y == other.Y) &&
                (this.Z == other.Z);
    }
}

如果不实现 IEquatable<T> 接口，IndexOf 将使用 ValueType.Equals(object other) 进行比较两个 PointD 元素，这涉及到昂贵的装箱操作。

IEquatable<T> 接口的文档说明如下：

IEquatable<T> 接口被泛型集合对象（例如Dictionary<TKey, TValue>、List<T>和LinkedList<T>）用于测试相等性，在Contains、IndexOf、LastIndexOf和Remove等方法中。对于任何可能存储在泛型集合中的对象都应该实现此接口。

这是我完整的基准测试代码：

using System;
using System.Collections.Generic;
using System.Diagnostics;

struct PointD 
{
    public int X;
    public int Y;
    public int Z;
}

class PerfTest
{
    List<PointD> _pCoord3Points = new List<PointD>();

    int checkPointIndexOf(PointD pt)
    {
        return _pCoord3Points.IndexOf(pt);  
    }

    int checkPointForBreak(PointD pt)
    {
        int retIndex = -1;
        for (int i = 0; i < _pCoord3Points.Count; i++)
        {
            PointD otherPt = _pCoord3Points[i];
            if ((pt.X == otherPt.X) &&
                (pt.Y == otherPt.Y) &&
                (pt.Z == otherPt.Z))
                retIndex = i;
            break;
        }
        return retIndex;
    }

    void init()
    {
        for (int x = 0; x < 100; x++)
        {
            for (int y = 0; y < 10; y++)
            {
                for (int z = 0; z < 10; z++)
                {
                    PointD pt = new PointD() { X = x, Y = y, Z = z };
                    _pCoord3Points.Add(pt);
                }
            }
        }
    }

    static void Main(string[] args)
    {
        PerfTest test = new PerfTest();
        test.init();
        Stopwatch sw = Stopwatch.StartNew();
        for (int x = 0; x < 100; x++)
        {
            for (int y = 0; y < 10; y++)
            {
                for (int z = 0; z < 10; z++)
                {
                    PointD pt = new PointD() { X = x, Y = y, Z = z };
                    test.checkPointIndexOf(pt);
                }
            }
        }
        sw.Stop();
        Console.WriteLine(sw.Elapsed);
        sw = Stopwatch.StartNew();
        for (int x = 0; x < 100; x++)
        {
            for (int y = 0; y < 10; y++)
            {
                for (int z = 0; z < 10; z++)
                {
                    PointD pt = new PointD() { X = x, Y = y, Z = z };
                    test.checkPointForBreak(pt);
                }
            }
        }
        sw.Stop();
        Console.WriteLine(sw.Elapsed);
    }
}

在 Windows 7 x64 上，使用 .NET 4.0 x64 构建，我得到了以下时间（大约）：

IndexOf: 00:00:04.8096623
For Loop: 00:00:00.0014203

当将PointD转换为一个class时，时间会改变：

IndexOf: 00:00:01.0703627
For Loop: 00:00:00.0014190

当使用实现IEquatable<PointD>的struct PointD时，我得到更为“相似”的结果，但IndexOf仍然比较慢（使用class时没有显着差异）：

IndexOf: 00:00:00.3904615
For Loop: 00:00:00.0015218
@0xA3：在启动秒表之前，您能否调用List<PointD>.IndexOf一次以消除JIT成本+一次初始化（EqualityComparer<PointD>的静态构造函数来确定正确的比较器等）在幕后发生的情况？虽然我们看到数量级的差异，但我认为这并不重要。 - Ani
@Ani：是的，你说得对，基准测试在JIT开销方面并不准确。但我决定忽略这种影响。实际上，如果你先预热一下，你会发现for循环的JIT开销更为显著，这似乎是合理的，因为List<T>.IndexOf包含在mscorlib.dll的本机映像中。 - Dirk Vollmar
它以IndexOf 8.08...和[] 10.018...结束，这就是我的问题所在，为什么？感谢您对当前答案的所有工作。 - Roger
当我从结构体（struct）更改为类（class）时，那就改变了它。明白了。再次感谢。 - Roger
4
通常，在访问数组元素之前，它会检查索引是否>= 0且< length——这样您就不会读取或覆盖不属于您的内存。除其他外，它消除了一堆严重的安全漏洞，称为缓冲区溢出。
不用说，如果您的循环中有很少的代码，那么这会阻碍性能。为了减轻这个问题，JIT编译器会对形式为for（i = 0; i < array.Length; i ++）{array [i];} 的for循环进行优化-即，任何访问从0到length-1的所有数组索引的循环。它省略了此情况下的边界检查。（如果您访问诸如array [i + 1]之类的内容，则优化失败，因为您可能越过边界。）
不幸的是，这仅适用于数组，而不适用于List<>。因此，您的后面的代码将无法进行优化。
但是，由于List<>在内部包含一个数组，并且List.IndexOf（）使用循环直接访问数组中的每个值，因此可以进行优化。
顺便提一下，最好使用for (int i = 0; i < array.Length; i++) { }而不是int length = array.Length; for(int i = 0; i < length; i++) { } -- 因为不能确定length是否真的是数组的长度。
编辑：查看使用Reflector的IndexOf代码，循环确实会进行优化，但正如其他人在这里提到的那样，它调用Equals() -- 这需要vtable lookup和各种检查。 所以在这种情况下，如果没有使用分析器运行它，IndexOf可能实际上会更慢。
反汇编代码：
internal virtual int IndexOf(T[] array, T value, int startIndex, int count)
{
    int num = startIndex + count;
    for (int i = startIndex; i < num; i++)
    {
        if (this.Equals(array[i], value))
        {
            return i;
        }
    }
    return -1;
}
.NET 的疯狂随机知识！ - Chris Marisic
0

_pCoord3Points 是什么类型？如果元素类型是值类型，只重写了 Equals(object) 方法，那么 IndexOf 可能会反复装箱以检查相等性。这可能是一个解释。但现在只是猜测... 如果您可以提供一个简短但完整的程序来演示问题，那将更容易帮助您。

1
但是如果 IndexOf 涉及装箱，那么它应该会更慢，而不是像 OP 所声称的那样更快，对吗？ - Dirk Vollmar
确实，Jon，你似乎是对的。我进行了测量，IndexOf 对于值类型来说明显较慢（在我的测量中约为 1000 倍），对于引用类型仍然比较慢（约为 100 倍）。 - Dirk Vollmar
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接