天天看点

C# 字节数组 byte[] 快速比较算法

注:代码原创转载或使用请标明出处。

目前C#最高版本net6 preview 7,我没有找到快速比较两个字节数组 byte[]的api,如若谁知道请在下方留言,谢谢。

在没有使用某些cpu特有的比较指令实现的纯C#的快速比较byte[]的思路:

把byte[]转成byte*,然后利用64位cpu一次可比较64位数据的特点把byte强制转换成long进行比较理论上速度可以快一倍。

原本32位程序应该使用int比较,但经测试发现在64系统上32位程序使用long会比使用int*快一点。

代码如下:

//需要在项目属性的“生成”勾上“允许不安全代码”
//public static class ArrayExt ...
public unsafe static bool EqualsAll(this byte[] arr1, byte[]? arr2)	//如果代码不是nullable就去掉"?"
{
	if (Object.ReferenceEquals(arr1, arr2)) return true;

	int length = arr1.Length;
	if (arr2 == null || length != arr2.Length)
		return false;

	if (length < 4)
	{
		for (int i = 0; i < arr1.Length; i++)
		{
			if (arr1[i] != arr2[i])
				return false;
		}
		return true;
	}
	else
	{
		fixed (void* voidby1 = arr1)
		{
			fixed (void* voidby2 = arr2)
			{
				const int cOneCompareSize = 8;

				var blkCount = length / cOneCompareSize;
				var less = length % cOneCompareSize;

				byte* by1, by2;

				long* lby1 = (long*)voidby1;
				long* lby2 = (long*)voidby2;
				while (blkCount > 0)
				{
					if (*lby1 != *lby2)
						return false;
					lby1++; lby2++;
					blkCount--;
				}

				if (less >= 4) //此if和true的代码可以不要,性能差异不大
				{
					if (*((int*)lby1) != *((int*)lby2))
						return false;

					by1 = ((byte*)lby1 + 4);
					by2 = ((byte*)lby2 + 4);

					less = less - 4;
				}
				else
				{
					by1 = (byte*)lby1;
					by2 = (byte*)lby2;
				}

				while (less-- > 0)
				{
					if (*by1 != *by2)
						return false;
					by1++; by2++;
				}
				return true;
			}
		}
	}
}
           
测试数据:

测试环境:win7 x64, net5,100MB的byte[]

注:由于是64位系统,所以以下的64位和Any CPU基本上是一样的

---参考数据---
64位debug直接byte比较
335.0191
335.0192
64位release直接byte比较
63.0036	//release 有优化
64.0036
--
64位release使用EqualsAll比较
13.0007
13.0007
---参考数据结束---

32位debug使用long比较
55.0031
56.0032

32位debug使用int比较
74.0042
76.0044

64位debug使用long比较 与“32位使用int比较”时间少(75 - 41)/75≈45%
41.0024
39.0022
           

以上是多次测试取合适的一组的结果,不同电脑测试结果会不同,但结论是差不多的,包括release也是。

最终结果:

在64位系统Any CPU,100MB数据量下,

debug 模式下,使用EqualsAll和直接byte[]比较,快335/((41 + 39)/2) - 1≈ 7倍

release 模式下,使用EqualsAll和直接byte[]比较,快(63+64)/2/(13) - 1 ≈4倍

上面差异比较大,实际上EqualsAll没有快多少,是因为一般比较少出现100MB数据比较的情况,

附部分测试代码:

byte[] arr1, arr2;
arr1 = new byte[100 * 1024 * 1024];	//100MB
for (int i = 0; i < arr1.Length; i++)
	arr1[i] = (byte)i;
arr2 = new byte[arr1.Length];
Buffer.BlockCopy(arr1, 0, arr2, 0, arr1.Length);
DateTime now = DateTime.Now;
Assert.IsTrue(ArrayExt.EqualsAll(arr1, arr2));  //如果不是测试环境去掉Assert.IsTrue
Trace.WriteLine((DateTime.Now - now).TotalMilliseconds);
arr2[arr2.Length - 1] = (byte)(arr2[arr2.Length - 1] + 1);
now = DateTime.Now;
Assert.IsTrue(!ArrayExt.EqualsAll(arr1, arr2));
Trace.WriteLine((DateTime.Now - now).TotalMilliseconds);
           

继续阅读