为什么复制对字符串的引用比复制int要慢得多（但反之亦然，对于Array.Copy（））？(Why is copying references to strings much slower than copying ints (but vice versa for Array.Copy())?)

 假设我想将数组的一部分向右移动1.我可以使用Array.Copy或者只是Array.Copy复制元素： 
 
private static void BuiltInCopy<T>(T[] arg, int start) {
    int length = arg.Length - start - 1;
    Array.Copy(arg, start, arg, start + 1, length);
}

private static void ElementByElement<T>(T[] arg, int start) {
    for (int i = arg.Length - 1; i > start; i--) {
        arg[i] = arg[i - 1];
    }
}

private static void ElementByElement2<T>(T[] arg, int start) {
    int i = arg.Length - 1;
    while (i > start)
        arg[i] = arg[--i];
}
 
 （ ElementByElement2由Matt Howells建议。） 
 
 我使用Minibench测试了它，结果让我感到非常惊讶。 
 
internal class Program {
    private static int smallArraySize = 32;

    public static void Main(string[] args) {
        BenchArrayCopy();
    }

    private static void BenchArrayCopy() {
        var smallArrayInt = new int[smallArraySize];
        for (int i = 0; i < smallArraySize; i++)
            smallArrayInt[i] = i;

        var smallArrayString = new string[smallArraySize];
        for (int i = 0; i < smallArraySize; i++)
            smallArrayString[i] = i.ToString();

        var smallArrayDateTime = new DateTime[smallArraySize];
        for (int i = 0; i < smallArraySize; i++)
            smallArrayDateTime[i] = DateTime.Now;

        var moveInt = new TestSuite<int[], int>("Move part of array right by 1: int")
            .Plus(BuiltInCopy, "Array.Copy()")
            .Plus(ElementByElement, "Element by element (for)")
            .Plus(ElementByElement2, "Element by element (while)")
            .RunTests(smallArrayInt, 0);

        var moveString = new TestSuite<string[], string>("Move part of array right by 1: string")
            .Plus(BuiltInCopy, "Array.Copy()")
            .Plus(ElementByElement, "Element by element (for)")
            .Plus(ElementByElement2, "Element by element (while)")
            .RunTests(smallArrayString, "0");

        moveInt.Display(ResultColumns.All, moveInt.FindBest());
        moveString.Display(ResultColumns.All, moveInt.FindBest());
    }

    private static T ElementByElement<T>(T[] arg) {
        ElementByElement(arg, 1);
        return arg[0];
    }

    private static T ElementByElement2<T>(T[] arg) {
        ElementByElement2(arg, 1);
        return arg[0];
    }

    private static T BuiltInCopy<T>(T[] arg) {
        BuiltInCopy(arg, 1);
        return arg[0];
    }

    private static void BuiltInCopy<T>(T[] arg, int start) {
        int length = arg.Length - start - 1;
        Array.Copy(arg, start, arg, start + 1, length);
    }

    private static void ElementByElement<T>(T[] arg, int start) {
        for (int i = arg.Length - 1; i > start; i--) {
            arg[i] = arg[i - 1];
        }
    }

    private static void ElementByElement2<T>(T[] arg, int start) {
        int i = arg.Length - 1;
        while (i > start)
            arg[i] = arg[--i];
    }
}
 
 请注意，这里没有测量分配。 所有方法都只是复制数组元素。 由于我在32位操作系统上，因此int和string引用在堆栈上占用相同的空间量。 
 
 这是我期望看到的： 
 
 
 
 BuiltInCopy应该是最快的，原因有两个：1）它可以做内存复制; 2） List<T>.Insert使用Array.Copy 。 另一方面，它是非泛型的，当数组有不同的类型时它可以做很多额外的工作，所以也许它没有充分利用1）。 
 
 
 对于int和string ElementByElement应该同样快。 
 
 
 对于int和string ， BuiltInCopy要么同样快，要么对int要慢一些（如果它必须做一些拳击）。 
 
 
 但是，所有这些假设都是错误的（至少在我的.NET 3.5 SP1机器上）！ 
 
 
 
 对于32个元素的数组， BuiltInCopy<int>明显慢于BuiltInCopy<int> 。 当大小增加时， BuiltInCopy<int>变得更快。 
 
 
 ElementByElement<string>比ElementByElement<int>慢4倍 。 
 
 
 BuiltInCopy<int>比BuiltInCopy<string>更快。 
 
 
 任何人都可以解释这些结果吗？ 
 
 更新：从CLR代码生成团队博客文章中关于数组边界检查消除 ： 
 
 
 
 建议4：当您复制中型到大型数组时，请使用Array.Copy，而不是显式复制循环。 首先，所有范围检查将被“提升”到循环外的单个检查。 如果数组包含对象引用，您还将有效地“提升”与存储到对象类型数组相关的两个额外费用：与数组协方差相关的每个元素“存储检查”通常可以通过检查动态来消除数组的类型和与垃圾收集相关的写屏障将被聚合并变得更加有效。 最后，我们将能够使用更高效的“memcpy”式复制循环。 （在即将到来的多核世界中，如果阵列足够大，甚至可能采用并行性！） 
 
 
 最后一列是得分（以刻度/迭代次数表示的总持续时间，由最佳结果标准化）。 
 
 两次运行在smallArraySize = 32 ： 
 
f:\MyProgramming\TimSort\Benchmarks\bin\Release>Benchmarks.exe
============ Move part of array right by 1: int ============
Array.Copy()               468791028 0:30.350 1,46
Element by element (for)   637091585 0:29.895 1,06
Element by element (while) 667595468 0:29.549 1,00

============ Move part of array right by 1: string ============
Array.Copy()               432459039 0:30.929 1,62
Element by element (for)   165344842 0:30.407 4,15
Element by element (while) 150996286 0:28.399 4,25


f:\MyProgramming\TimSort\Benchmarks\bin\Release>Benchmarks.exe
============ Move part of array right by 1: int ============
Array.Copy()               459040445 0:29.262 1,38
Element by element (for)   645863535 0:30.929 1,04
Element by element (while) 651068500 0:30.064 1,00

============ Move part of array right by 1: string ============
Array.Copy()               403684808 0:30.191 1,62
Element by element (for)   162646202 0:30.051 4,00
Element by element (while) 160947492 0:30.945 4,16
 
 两次运行在smallArraySize = 256 ： 
 
f:\MyProgramming\TimSort\Benchmarks\bin\Release>Benchmarks.exe
============ Move part of array right by 1: int ============
Array.Copy()               172632756 0:30.128 1,00
Element by element (for)    91403951 0:30.253 1,90
Element by element (while)  65352624 0:29.141 2,56

============ Move part of array right by 1: string ============
Array.Copy()               153426720 0:28.964 1,08
Element by element (for)    19518483 0:30.353 8,91
Element by element (while)  19399180 0:29.793 8,80


f:\MyProgramming\TimSort\Benchmarks\bin\Release>Benchmarks.exe
============ Move part of array right by 1: int ============
Array.Copy()               184710866 0:30.456 1,00
Element by element (for)    92878947 0:29.959 1,96
Element by element (while)  73588500 0:30.331 2,50

============ Move part of array right by 1: string ============
Array.Copy()               157998697 0:30.336 1,16
Element by element (for)    19905046 0:29.995 9,14
Element by element (while)  18838572 0:29.382 9,46

Let's say I want to move a part of an array right by 1. I can either use Array.Copy or just make a loop copying elements one by one:
 
private static void BuiltInCopy<T>(T[] arg, int start) {
    int length = arg.Length - start - 1;
    Array.Copy(arg, start, arg, start + 1, length);
}

private static void ElementByElement<T>(T[] arg, int start) {
    for (int i = arg.Length - 1; i > start; i--) {
        arg[i] = arg[i - 1];
    }
}

private static void ElementByElement2<T>(T[] arg, int start) {
    int i = arg.Length - 1;
    while (i > start)
        arg[i] = arg[--i];
}
 
(ElementByElement2 was suggested by Matt Howells.)
 
I tested it using Minibench, and results surprised me quite a lot.
 
internal class Program {
    private static int smallArraySize = 32;

    public static void Main(string[] args) {
        BenchArrayCopy();
    }

    private static void BenchArrayCopy() {
        var smallArrayInt = new int[smallArraySize];
        for (int i = 0; i < smallArraySize; i++)
            smallArrayInt[i] = i;

        var smallArrayString = new string[smallArraySize];
        for (int i = 0; i < smallArraySize; i++)
            smallArrayString[i] = i.ToString();

        var smallArrayDateTime = new DateTime[smallArraySize];
        for (int i = 0; i < smallArraySize; i++)
            smallArrayDateTime[i] = DateTime.Now;

        var moveInt = new TestSuite<int[], int>("Move part of array right by 1: int")
            .Plus(BuiltInCopy, "Array.Copy()")
            .Plus(ElementByElement, "Element by element (for)")
            .Plus(ElementByElement2, "Element by element (while)")
            .RunTests(smallArrayInt, 0);

        var moveString = new TestSuite<string[], string>("Move part of array right by 1: string")
            .Plus(BuiltInCopy, "Array.Copy()")
            .Plus(ElementByElement, "Element by element (for)")
            .Plus(ElementByElement2, "Element by element (while)")
            .RunTests(smallArrayString, "0");

        moveInt.Display(ResultColumns.All, moveInt.FindBest());
        moveString.Display(ResultColumns.All, moveInt.FindBest());
    }

    private static T ElementByElement<T>(T[] arg) {
        ElementByElement(arg, 1);
        return arg[0];
    }

    private static T ElementByElement2<T>(T[] arg) {
        ElementByElement2(arg, 1);
        return arg[0];
    }

    private static T BuiltInCopy<T>(T[] arg) {
        BuiltInCopy(arg, 1);
        return arg[0];
    }

    private static void BuiltInCopy<T>(T[] arg, int start) {
        int length = arg.Length - start - 1;
        Array.Copy(arg, start, arg, start + 1, length);
    }

    private static void ElementByElement<T>(T[] arg, int start) {
        for (int i = arg.Length - 1; i > start; i--) {
            arg[i] = arg[i - 1];
        }
    }

    private static void ElementByElement2<T>(T[] arg, int start) {
        int i = arg.Length - 1;
        while (i > start)
            arg[i] = arg[--i];
    }
}
 
Note that allocations are not being measured here. All methods just copy array elements. Since I am on 32-bit OS, an int and a string reference take up the same amount of space on stack. 
 
This is what I expected to see:
 
 
 
BuiltInCopy should be the fastest for two reasons: 1) it can do memory copy; 2) List<T>.Insert uses Array.Copy. On the other hand, it's non-generic, and it can do a lot of extra work when arrays have different types, so perhaps it didn't take full advantage of 1). 
 
 
ElementByElement should be equally fast for int and string. 
 
 
BuiltInCopy should either be equally fast for int and string, or slower for int (in case it has to do some boxing). 
 
 
However, all of these suppositions were wrong (at least, on my machine with .NET 3.5 SP1)! 
 
 
 
BuiltInCopy<int> is significantly slower than ElementByElement<int> for 32-element arrays. When size is increased, BuiltInCopy<int> becomes faster.
 
 
ElementByElement<string> is over 4 times slower than ElementByElement<int>. 
 
 
BuiltInCopy<int> is faster than BuiltInCopy<string>. 
 
 
Can anybody explain these results?
 
UPDATE: From a CLR Code Generation Team blog post on array bounds check elimination:
 
 
 
Advice 4: when you’re copying medium-to-large arrays, use Array.Copy, rather than explicit copy loops. First, all your range checks will be “hoisted” to a single check outside the loop. If the arrays contain object references, you will also get efficient “hoisting” of two more expenses related to storing into arrays of object types: the per-element “store checks” related to array covariance can often be eliminated by a check on the dynamic types of the arrays, and garbage-collection-related write barriers will be aggregated and become much more efficient. Finally, we will able to use more efficient “memcpy”-style copy loops. (And in the coming multicore world, perhaps even employ parallelism if the arrays are big enough!)
 
 
The last column is the score (total duration in ticks/number of iterations, normalized by the best result).
 
Two runs at smallArraySize = 32:
 
f:\MyProgramming\TimSort\Benchmarks\bin\Release>Benchmarks.exe
============ Move part of array right by 1: int ============
Array.Copy()               468791028 0:30.350 1,46
Element by element (for)   637091585 0:29.895 1,06
Element by element (while) 667595468 0:29.549 1,00

============ Move part of array right by 1: string ============
Array.Copy()               432459039 0:30.929 1,62
Element by element (for)   165344842 0:30.407 4,15
Element by element (while) 150996286 0:28.399 4,25


f:\MyProgramming\TimSort\Benchmarks\bin\Release>Benchmarks.exe
============ Move part of array right by 1: int ============
Array.Copy()               459040445 0:29.262 1,38
Element by element (for)   645863535 0:30.929 1,04
Element by element (while) 651068500 0:30.064 1,00

============ Move part of array right by 1: string ============
Array.Copy()               403684808 0:30.191 1,62
Element by element (for)   162646202 0:30.051 4,00
Element by element (while) 160947492 0:30.945 4,16
 
Two runs at smallArraySize = 256:
 
f:\MyProgramming\TimSort\Benchmarks\bin\Release>Benchmarks.exe
============ Move part of array right by 1: int ============
Array.Copy()               172632756 0:30.128 1,00
Element by element (for)    91403951 0:30.253 1,90
Element by element (while)  65352624 0:29.141 2,56

============ Move part of array right by 1: string ============
Array.Copy()               153426720 0:28.964 1,08
Element by element (for)    19518483 0:30.353 8,91
Element by element (while)  19399180 0:29.793 8,80


f:\MyProgramming\TimSort\Benchmarks\bin\Release>Benchmarks.exe
============ Move part of array right by 1: int ============
Array.Copy()               184710866 0:30.456 1,00
Element by element (for)    92878947 0:29.959 1,96
Element by element (while)  73588500 0:30.331 2,50

============ Move part of array right by 1: string ============
Array.Copy()               157998697 0:30.336 1,16
Element by element (for)    19905046 0:29.995 9,14
Element by element (while)  18838572 0:29.382 9,46

原文：https://stackoverflow.com/questions/1279407