问题背景
我读到了这个问题，即如何尽可能快地反转字符串。 我发现其中一个答案是比较不同的方法。 在其中的一个中，他们只是从位置i运行一个循环交换元素，位置是string.Length-1-i但他们通过XOR使用已知的棘手交换。 我想知道使用通过XOR交换的字符串反转速度与使用经典交换通过时间变量的相同方法相比有多快。 令人惊讶的是，我比XOR获得了近50％的提升。
问题
编译器在幕后做了些神奇的事情，为什么我会得到这个结果？
修改后的代码与基准
using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; using System.Text; using System.Threading.Tasks; namespace ContestLibrary { public class Problem { delegate string StringDelegate(string s); static void Benchmark(string description, StringDelegate d, int times, string text) { Stopwatch sw = new Stopwatch(); sw.Start(); for (int j = 0; j < times; j++) { d(text); } sw.Stop(); Console.WriteLine("{0} Ticks {1} : called {2} times.", sw.ElapsedTicks, description, times); } public static string ReverseXor(string s) { char[] charArray = s.ToCharArray(); int len = s.Length - 1; for (int i = 0; i < len; i++, len--) { charArray[i] ^= charArray[len]; charArray[len] ^= charArray[i]; charArray[i] ^= charArray[len]; } return new string(charArray); } public static string ReverseClassic(string s) { char[] charArray = s.ToCharArray(); int len = s.Length-1; for (int i = 0; i < len; i++, len--) { char temp = charArray[len]; charArray[len] = charArray[i]; charArray[i] = temp; } return new string(charArray); } public static string StringOfLength(int length) { Random random = new Random(); StringBuilder sb = new StringBuilder(); for (int i = 0; i < length; i++) { sb.Append(Convert.ToChar(Convert.ToInt32(Math.Floor(26 * random.NextDouble() + 65)))); } return sb.ToString(); } static void Main(string[] args) { int[] lengths = new int[] {1,10,100,1000, 10000, 100000}; foreach (int l in lengths) { int iterations = 10000; string text = StringOfLength(l); Benchmark(String.Format("Classic (Length: {0})", l), ReverseClassic, iterations, text); Benchmark(String.Format("Xor (Length: {0})", l), ReverseXor, iterations, text); Console.WriteLine(); } Console.Read(); } } }Question Background
I read this question that is about how to reverse a string as fast as possible. I found that one of the answers was comparing different methods. In one of them, they just run a loop swapping elements from position i with the one at position string.Length-1-i but they use the known tricky swap via XOR. I was wondering how faster is reversing the string using the swap via XOR in comparison with the same method using the classic swap via a temporal variable. Surprisingly I'm getting almost a 50% improvement over the XOR one.
The Question
Is the compiler doing something magic behind the scenes, why I'm I getting this result?
The modified code with the Benchmarks
using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; using System.Text; using System.Threading.Tasks; namespace ContestLibrary { public class Problem { delegate string StringDelegate(string s); static void Benchmark(string description, StringDelegate d, int times, string text) { Stopwatch sw = new Stopwatch(); sw.Start(); for (int j = 0; j < times; j++) { d(text); } sw.Stop(); Console.WriteLine("{0} Ticks {1} : called {2} times.", sw.ElapsedTicks, description, times); } public static string ReverseXor(string s) { char[] charArray = s.ToCharArray(); int len = s.Length - 1; for (int i = 0; i < len; i++, len--) { charArray[i] ^= charArray[len]; charArray[len] ^= charArray[i]; charArray[i] ^= charArray[len]; } return new string(charArray); } public static string ReverseClassic(string s) { char[] charArray = s.ToCharArray(); int len = s.Length-1; for (int i = 0; i < len; i++, len--) { char temp = charArray[len]; charArray[len] = charArray[i]; charArray[i] = temp; } return new string(charArray); } public static string StringOfLength(int length) { Random random = new Random(); StringBuilder sb = new StringBuilder(); for (int i = 0; i < length; i++) { sb.Append(Convert.ToChar(Convert.ToInt32(Math.Floor(26 * random.NextDouble() + 65)))); } return sb.ToString(); } static void Main(string[] args) { int[] lengths = new int[] {1,10,100,1000, 10000, 100000}; foreach (int l in lengths) { int iterations = 10000; string text = StringOfLength(l); Benchmark(String.Format("Classic (Length: {0})", l), ReverseClassic, iterations, text); Benchmark(String.Format("Xor (Length: {0})", l), ReverseXor, iterations, text); Console.WriteLine(); } Console.Read(); } } }最满意答案
原因很简单，我们来检查每个函数在IL代码中有多少操作。 但首先，让我们看看两个功能的真正时间差异。 你说XOR函数比另一个慢了50％，当我在Debug模式下运行代码时，我得到了这个结果，但是你必须在Release模式下运行代码才能完全允许优化器完成它的工作:)。 在释放模式下，XOR功能几乎慢了3倍。
图片包含for循环内部分的IL代码，这是唯一改变的部分。
第一张图是带有temp变量的函数
第二张图是具有XOR的功能
正如您所看到的，指令数量的差异是巨大的，14对34。时间差异的3倍来自一些像conv.u2这样有点贵的操作。
The reason is very simple, lets check how many operations in IL code each function has. But first, lets see the real difference in time of both functions. You said that the XOR function is almost 50% slower than the other, when I run the code in Debug mode I have that results, but you must run the code in Release mode to fully allow the optimizer do its job :). In release mode the XOR functions is almost 3x slower.
The pictures have the IL code of the part inside the for loop, that is the only piece that changes.
The first picture is the function with the temp variable
The second picture is the function with the XOR
As you can see the difference in the number of instructions is huge, 14 against 34. The 3x difference in time come from some operations like conv.u2 that are a little expensive.
更多推荐
发布评论