10

I'm running AQTime on this piece of code, I found that .IndexOf takes 16% of the time vs close to 80% for the other piece... They appear to use the same IsEqual and other routines. Called 116,000 times inserting 30,000 items. None of the List<> objects gets over 200 elements. (I may be using AQTime incorrectly, I'm looking into this)

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();
    }
}
4

3 回答 3

10

我做了以下假设：

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

IndexOf您可以通过实现IEquatable<T>接口来加快速度：

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将比较两个PointD元素使用ValueType.Equals(object other)这涉及昂贵的装箱操作。

接口的文档IEquatable<T>状态：

该IEquatable<T>接口由通用集合对象（例如Dictionary<TKey, TValue>,和 ）使用List<T>，并且在测试诸如、、和LinkedList<T>等方法中的相等性时使用。应该为可能存储在通用集合中的任何对象实现它。ContainsIndexOfLastIndexOfRemove

这是我的完整基准代码：

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 版本上，我得到以下时间（大约）：

索引：00:00:04.8096623
循环：00:00:00.0014203

当PointD变成a时class，时间改变为

索引：00:00:01.0703627
循环：00:00:00.0014190

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

索引：00:00:00.3904615
循环：00:00:00.0015218
于 2010-09-07T22:37:53.423 回答
4

通常，在您访问数组元素之前，它会检查以确保索引 >= 0 并且 < 长度 - 这样您就不会读取或覆盖不属于您的内存。除其他外，它消除了一系列称为缓冲区溢出的严重安全漏洞。

不用说，如果您的循环中的代码很少，这会影响性能。为了减轻这个问题，JIT 编译器优化了这种形式的 for 循环for (i = 0; i < array.Length; i++) { array[i]; }——也就是说，任何访问从 0 到长度 - 1 的数组的所有索引的任何循环。它省略了这种情况下的边界检查。（如果您访问诸如数组 [i + 1] 之类的内容，优化将失败，因为您可能会越界。）

不幸的是，这只适用于数组，不适用于 List<>s。所以你后面的代码不会被优化。

但是由于 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 查找和各种健全性检查。因此，在这种情况下，当您不使用分析器运行 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;
}
于 2010-09-07T22:25:52.273 回答
0

What's the type of _pCoord3Points? If the element type is a value type which only overrides Equals(object) then it's possible that IndexOf is repeatedly boxing values to check for equality. That might explain it. It's really just guesswork at this point though... if you could provide a short but complete program which demonstrates the problem, that would make it a lot easier to help you.

于 2010-09-07T21:50:54.323 回答