Сравнение двух байтовых массивов в .NET

Как я могу сделать это быстро?

Конечно, я могу сделать это:

static bool ByteArrayCompare(byte[] a1, byte[] a2)
{
    if (a1.Length != a2.Length)
        return false;

    for (int i=0; i<a1.Length; i++)
        if (a1[i]!=a2[i])
            return false;

    return true;
}

Но я ищу либо функцию BCL, либо какой-нибудь высоко оптимизированный проверенный способ сделать это.

java.util.Arrays.equals((sbyte[])(Array)a1, (sbyte[])(Array)a2);

работает хорошо, но не похоже, что это будет работать для x64.

Обратите внимание на мой сверхбыстрый ответ здесь .

4.09.2008 07:33:25
«Это своего рода рассчитывает на то, что массивы начинаются с выравнивания qword». Это большое, если. Вы должны исправить код, чтобы отразить это.
Joe Chung 9.08.2009 20:45:24
return a1.Length == a2.Length &&! a1.Where ((t, i) => t! = a2 [i]). Any ();
alerya 31.08.2012 12:10:35
Мне понравился ответ @OhadSchneider оIStructuralEquatable
LCJ 1.03.2013 07:01:03
27 ОТВЕТОВ

Я бы использовал небезопасный код и запускал forцикл, сравнивающий указатели Int32.

Может быть, вам следует также рассмотреть проверку массивов, чтобы быть ненулевым.

6
28.06.2015 23:42:32

Извините, если вы ищете управляемый способ, вы уже делаете это правильно, и, насколько мне известно, в BCL нет встроенного метода для этого.

Вы должны добавить несколько начальных нулевых проверок, а затем просто повторно использовать их, как если бы они находились в BCL.

0
4.09.2008 07:45:49
Вы были правы, когда писали, что, однако в 2010 году (.NET 4.0) появился метод BCL, см. Ответ Охада Шнайдера. Во время вопроса .NET 3.5 имел Linq (см. Ответ aku).
Jeppe Stig Nielsen 13.07.2016 09:04:45

Если вы не против этого, вы можете импортировать сборку J # "vjslib.dll" и использовать ее метод Arrays.equals (byte [], byte []) ...

Не вините меня, если кто-то смеется над вами, хотя ...


РЕДАКТИРОВАТЬ: Для чего мало, я использовал Reflector, чтобы разобрать код для этого, и вот как это выглядит:

public static bool equals(sbyte[] a1, sbyte[] a2)
{
  if (a1 == a2)
  {
    return true;
  }
  if ((a1 != null) && (a2 != null))
  {
    if (a1.Length != a2.Length)
    {
      return false;
    }
    for (int i = 0; i < a1.Length; i++)
    {
      if (a1[i] != a2[i])
      {
        return false;
      }
    }
    return true;
  }
  return false;
}
29
4.09.2008 08:03:45

Вы можете использовать метод Enumerable.SequenceEqual .

using System;
using System.Linq;
...
var a1 = new int[] { 1, 2, 3};
var a2 = new int[] { 1, 2, 3};
var a3 = new int[] { 1, 2, 4};
var x = a1.SequenceEqual(a2); // true
var y = a1.SequenceEqual(a3); // false

Если по какой-то причине вы не можете использовать .NET 3.5, ваш метод в порядке.
Среда компилятора \ среды выполнения оптимизирует ваш цикл, поэтому вам не нужно беспокоиться о производительности.

606
4.09.2008 08:08:31
Но разве SequenceEqual не займет больше времени, чем небезопасное сравнение? Особенно, когда вы делаете тысячи сравнений?
tcables 20.01.2011 18:18:33
Да, это работает примерно в 50 раз медленнее, чем небезопасное сравнение.
Hafthor 3.02.2011 02:53:31
Это действительно воскрешает здесь мертвых, но медленное - это действительно плохое слово для использования здесь. В 50 раз медленнее звучит плохо, но вы не часто сравниваете достаточно данных для того, чтобы это что-то изменило, и если вам это нужно, вам действительно нужно сравнить это с вашим собственным делом по множеству причин. Например, обратите внимание, что создатель небезопасного ответа отмечает разницу в 7 раз медленнее, а не в 50 раз медленнее (скорость небезопасного метода также зависит от выравнивания данных). В тех редких случаях, когда эти цифры имеют значение, P / Invoke работает даже быстрее.
Selali Adobor 17.09.2014 22:47:03
Таким образом, более медленная реализация получает более 300 лайков? Я бы предложил подключить msvcrt.dll, так как это был бы самый быстрый способ выполнить работу.
TGarrett 14.05.2015 13:49:38
Быстрее не самая важная вещь для бизнеса. Ремонтопригодность гораздо «быстрее», чем экономия на этом коде в 99% случаев. Я использую SequenceEqual, и весь мой код <1 мс. Те мкс, которые вы сохраняете, никогда не добавят 5 минут отсутствия читаемости P / Invoke.
PRMan 25.09.2015 23:54:48

.NET 3.5 и новее имеют новый открытый тип, System.Data.Linq.Binaryкоторый инкапсулирует byte[]. Он реализует, IEquatable<Binary>что (по сути) сравнивает два байтовых массива. Обратите внимание, что System.Data.Linq.Binaryтакже есть оператор неявного преобразования из byte[].

Документация MSDN: System.Data.Linq.Binary

Отражатель декомпилируется методом Equals:

private bool EqualsTo(Binary binary)
{
    if (this != binary)
    {
        if (binary == null)
        {
            return false;
        }
        if (this.bytes.Length != binary.bytes.Length)
        {
            return false;
        }
        if (this.hashCode != binary.hashCode)
        {
            return false;
        }
        int index = 0;
        int length = this.bytes.Length;
        while (index < length)
        {
            if (this.bytes[index] != binary.bytes[index])
            {
                return false;
            }
            index++;
        }
    }
    return true;
}

Интересным моментом является то, что они переходят к байтовому циклу сравнения, только если хэши двух двоичных объектов совпадают. Это, однако, происходит за счет вычисления хэша в конструкторе Binaryобъектов (путем обхода массива с помощью forцикла :-)).

Вышеприведенная реализация означает, что в худшем случае вам, возможно, придется обходить массивы три раза: сначала для вычисления хеш-функции array1, затем для вычисления хеш-функции array2 и, наконец, (поскольку это наихудший сценарий, равны длины и хэши) для сравнения. байты в массиве 1 с байтами в массиве 2.

В целом, несмотря на то, что System.Data.Linq.Binaryон встроен в BCL, я не думаю, что это самый быстрый способ сравнения двухбайтовых массивов: - |.

25
1.05.2009 13:14:40

Я думал о методах ускорения передачи блоков, встроенных во многие видеокарты. Но тогда вам придется копировать все данные побайтно, так что это вам мало поможет, если вы не хотите реализовывать всю часть своей логики в неуправляемом и аппаратно-зависимом коде ...

Другой способ оптимизации, подобный подходу, показанному выше, состоит в том, чтобы хранить как можно больше ваших данных в long [], а не byte [] с самого начала, например, если вы последовательно читаете их из двоичного файла, или если вы используете отображенный в память файл, считывайте данные как длинные [] или одиночные длинные значения. Тогда вашему циклу сравнения потребуется только 1/8 от количества итераций, которые он должен выполнить для байта [], содержащего такое же количество данных. Речь идет о том, когда и как часто вам нужно сравнивать и когда и как часто вам нужно обращаться к данным побайтово, например, использовать их в вызове API в качестве параметра в методе, который ожидает байт []. В конце концов, вы можете только сказать, действительно ли вы знаете вариант использования ...

1
7.08.2009 11:09:32
Принятый ответ преобразует буфер байтов в длинный буфер и сравнивает его, как вы описываете.
Hafthor 18.12.2012 17:18:29

Если вы посмотрите, как .NET выполняет string.Equals, вы увидите, что он использует закрытый метод EqualsHelper, который имеет «небезопасную» реализацию указателя. .NET Reflector - ваш друг, чтобы увидеть, как все происходит внутри.

Это можно использовать в качестве шаблона для сравнения байтового массива, о котором я рассказывал в блоге. Быстрое сравнение байтового массива в C # . Я также сделал несколько элементарных тестов, чтобы увидеть, когда безопасная реализация быстрее небезопасной.

Тем не менее, если вам действительно не нужна убийственная производительность, я бы пошел на простое сравнение цикла fr.

5
28.06.2015 23:43:37

Для сравнения коротких байтовых массивов интересным является следующее:

if(myByteArray1.Length != myByteArray2.Length) return false;
if(myByteArray1.Length == 8)
   return BitConverter.ToInt64(myByteArray1, 0) == BitConverter.ToInt64(myByteArray2, 0); 
else if(myByteArray.Length == 4)
   return BitConverter.ToInt32(myByteArray2, 0) == BitConverter.ToInt32(myByteArray2, 0); 

Тогда я бы наверняка выпал на решение, указанное в вопросе.

Было бы интересно сделать анализ производительности этого кода.

2
18.09.2009 15:29:25
int i = 0; for (; i <a1.Length-7; i + = 8) if (BitConverter.ToInt64 (a1, i)! = BitConverter.ToInt64 (a2, i)) вернуть false; for (; i <a1.Length; i ++) if (a1 [i]! = a2 [i]) возвращает false; вернуть истину; // немного медленнее простого цикла for.
Hafthor 21.12.2012 05:49:23

P / Invoke полномочия активируются!

[DllImport("msvcrt.dll", CallingConvention=CallingConvention.Cdecl)]
static extern int memcmp(byte[] b1, byte[] b2, long count);

static bool ByteArrayCompare(byte[] b1, byte[] b2)
{
    // Validate buffers are the same length.
    // This also ensures that the count does not exceed the length of either buffer.  
    return b1.Length == b2.Length && memcmp(b1, b2, b1.Length) == 0;
}
234
28.06.2015 23:45:14
P / Invoke yaay - это оказалось самым быстрым, по крайней мере, для растровых изображений, по крайней мере: stackoverflow.com/questions/2031217/…
Erik Forbes 10.01.2010 20:48:49
В этом случае закрепление не требуется. Маршаллер выполняет автоматическое закрепление при вызове собственного кода с помощью PInvoke. Ссылка: stackoverflow.com/questions/2218444/…
Mark Glasgow 16.03.2010 08:55:44
P / Invoke может вызывать уныние, но это, безусловно, самое быстрое из всех представленных решений, включая реализацию, которую я придумал, которая использует небезопасные сравнения с размером указателя. Есть несколько оптимизаций, которые вы можете сделать, прежде чем обращаться к собственному коду, включая равенство ссылок и сравнение первого и последнего элементов.
Josh 1.09.2011 19:44:21
Почему бу? Плакат хотел быструю реализацию, а сравнение на оптимизированном ассемблере не сравнится. Я не знаю, как получить «REPE CMPSD» из .NET без P / INVOKE.
Jason Goemaat 2.10.2011 06:55:36
Nitpick: MSVCR.dll не должен использоваться кодом пользователя. Чтобы использовать MSVCR, вам придется распространять среду выполнения, используя версию, которую вы распространяете. ( msdn.microsoft.com/en-us/library/… и blogs.msdn.com/b/oldnewthing/archive/2014/04/11/10516280.aspx )
Mitch 12.12.2014 04:55:18
 using System.Linq; //SequenceEqual

 byte[] ByteArray1 = null;
 byte[] ByteArray2 = null;

 ByteArray1 = MyFunct1();
 ByteArray2 = MyFunct2();

 if (ByteArray1.SequenceEqual<byte>(ByteArray2) == true)
 {
    MessageBox.Show("Match");
 }
 else
 {
   MessageBox.Show("Don't match");
 }
10
6.01.2011 16:22:03
Это то, что я использовал. Но это ... звучит как последовательное сравнение, которое вы иначе делали бы, используя простой цикл, следовательно, не очень быстрый. Было бы неплохо отразить это и посмотреть, что на самом деле происходит. Судя по названию, ничего особенного.
Sergey Akopov 6.01.2011 20:33:15
Да, но уже упоминается в принятом ответе. Кстати, вы можете удалить спецификацию типа там.
nawfal 2.06.2013 15:19:31

Для этого в .NET 4 есть новое встроенное решение - IStructuralEquatable

static bool ByteArrayCompare(byte[] a1, byte[] a2) 
{
    return StructuralComparisons.StructuralEqualityComparer.Equals(a1, a2);
}
159
25.03.2014 11:36:36
Согласно этому сообщению в блоге, это на самом деле очень медленно.
Matt Johnson-Pint 17.12.2012 23:23:55
Сумасшедший медленный Примерно в 180 раз медленнее, чем простой цикл.
Hafthor 21.12.2012 05:47:04
Это работает, но я не понимаю почему. Байт [] - это примитивный тип, который не реализует IStructuralEquatable, так почему вы можете его приводить - и при этом неявное приведение! И тогда метод интерфейса «Равно» волшебным образом становится доступным ... откуда берется реализация этого метода? Может кто-нибудь подсказать мне?
Josh 3.10.2013 15:20:39
Почему не просто StructuralComparisons.StructuralEqualityComparer.Equals(a1, a2). Нет NullReferenceExceptionздесь.
ta.speot.is 24.03.2014 23:51:20
@ ta.speot.is Спасибо, не могу спорить с одним вкладышем! Предыдущее решение было несколько более эффективным, поскольку оно сохранило приведение к IStructuralEquatable (статически известно, что массив IStructuralEquatable), но действительно ваши предложения заставляют метод работать и для нулевых аргументов.
Ohad Schneider 25.03.2014 11:39:10
РЕШЕНИЕ

Пользователь gil предложил небезопасный код, который породил это решение:

// Copyright (c) 2008-2013 Hafthor Stefansson
// Distributed under the MIT/X11 software license
// Ref: http://www.opensource.org/licenses/mit-license.php.
static unsafe bool UnsafeCompare(byte[] a1, byte[] a2) {
  if(a1==a2) return true;
  if(a1==null || a2==null || a1.Length!=a2.Length)
    return false;
  fixed (byte* p1=a1, p2=a2) {
    byte* x1=p1, x2=p2;
    int l = a1.Length;
    for (int i=0; i < l/8; i++, x1+=8, x2+=8)
      if (*((long*)x1) != *((long*)x2)) return false;
    if ((l & 4)!=0) { if (*((int*)x1)!=*((int*)x2)) return false; x1+=4; x2+=4; }
    if ((l & 2)!=0) { if (*((short*)x1)!=*((short*)x2)) return false; x1+=2; x2+=2; }
    if ((l & 1)!=0) if (*((byte*)x1) != *((byte*)x2)) return false;
    return true;
  }
}

который выполняет 64-битное сравнение для максимально возможного массива. Этот вид рассчитывает на то, что массивы начинаются с выравнивания qword. Это сработает, если не выровнять qword, но не так быстро, как если бы это было.

Он работает примерно на семь таймеров быстрее, чем простой forцикл. Использование библиотеки J # выполняется аналогично оригинальному forциклу. Использование .SequenceEqual работает в семь раз медленнее; Я думаю только потому, что он использует IEnumerator.MoveNext. Я думаю, что решения на основе LINQ, по крайней мере, такие медленные или хуже.

76
17.04.2017 11:09:30
Хорошее решение. Но один (маленький) совет: сравнение, если ссылки a1 и a2 равны, может ускорить процесс, если дать один и тот же массив для a1 и b1.
mmmmmmmm 20.12.2012 13:34:43
Новые тестовые данные в выпуске .NET 4 x64: IStructualEquatable.equals ~ в 180 раз медленнее, SequenceEqual в 15 раз медленнее, хэш SHA1 сравнивает в 11 раз медленнее, битконвертер ~ такой же, небезопасный в 7 раз быстрее, пинвоукс в 11 раз быстрее. Довольно круто, что небезопасно только немного медленнее, чем P / Invoke на memcmp.
Hafthor 21.12.2012 05:46:18
Эта ссылка дает подробные сведения о том, почему выравнивание памяти имеет значение ibm.com/developerworks/library/pa-dalign - поэтому можно было бы оптимизировать проверку выравнивания, и если оба массива не выровнены на одну и ту же величину, выполняйте байтовые сравнения до тех пор, пока они оба не станут одинаковыми. на границе слов.
Hafthor 10.01.2013 16:28:46
разве это не даст ложь, когда a1 и a2 равны нулю?
nawfal 14.04.2013 10:26:17
@CristiDiaconescu Я зациклился на ответе Кевина Дриджера. Вероятно, я должен сделать тестовый набор и мои результаты доступными на github и дать ссылку на него в своем ответе.
Hafthor 27.06.2013 17:06:34

Если вы ищете очень быстрый компаратор равенства байтовых массивов, я предлагаю вам взглянуть на эту статью STSdb ​​Labs: Компаратор сравнения байтовых массивов. В нем представлены некоторые из самых быстрых реализаций для сравнения равенства массива byte [], которые представлены, протестированы и обобщены на производительность.

Вы также можете сосредоточиться на этих реализациях:

BigEndianByteArrayComparer - быстрый байт [] массив Comparer слева направо (BigEndian) BigEndianByteArrayEqualityComparer - - быстрый байт [] равенство Comparer слева направо (BigEndian) LittleEndianByteArrayComparer - быстрый байт [] массив Comparer справа налево (LittleEndian) LittleEndianByteArrayEqualityComparer - быстрый байт [] равенство равенства справа налево (LittleEndian)

-2
2.07.2014 11:07:46

Используйте SequenceEqualsдля этого для сравнения.

-1
23.04.2015 20:19:09

Краткий ответ таков:

    public bool Compare(byte[] b1, byte[] b2)
    {
        return Encoding.ASCII.GetString(b1) == Encoding.ASCII.GetString(b2);
    }

Таким образом, вы можете использовать оптимизированное сравнение строк .NET для сравнения байтового массива без необходимости писать небезопасный код. Вот как это делается в фоновом режиме :

private unsafe static bool EqualsHelper(String strA, String strB)
{
    Contract.Requires(strA != null);
    Contract.Requires(strB != null);
    Contract.Requires(strA.Length == strB.Length);

    int length = strA.Length;

    fixed (char* ap = &strA.m_firstChar) fixed (char* bp = &strB.m_firstChar)
    {
        char* a = ap;
        char* b = bp;

        // Unroll the loop

        #if AMD64
            // For the AMD64 bit platform we unroll by 12 and
            // check three qwords at a time. This is less code
            // than the 32 bit case and is shorter
            // pathlength.

            while (length >= 12)
            {
                if (*(long*)a     != *(long*)b)     return false;
                if (*(long*)(a+4) != *(long*)(b+4)) return false;
                if (*(long*)(a+8) != *(long*)(b+8)) return false;
                a += 12; b += 12; length -= 12;
            }
       #else
           while (length >= 10)
           {
               if (*(int*)a != *(int*)b) return false;
               if (*(int*)(a+2) != *(int*)(b+2)) return false;
               if (*(int*)(a+4) != *(int*)(b+4)) return false;
               if (*(int*)(a+6) != *(int*)(b+6)) return false;
               if (*(int*)(a+8) != *(int*)(b+8)) return false;
               a += 10; b += 10; length -= 10;
           }
       #endif

        // This depends on the fact that the String objects are
        // always zero terminated and that the terminating zero is not included
        // in the length. For odd string sizes, the last compare will include
        // the zero terminator.
        while (length > 0)
        {
            if (*(int*)a != *(int*)b) break;
            a += 2; b += 2; length -= 2;
        }

        return (length <= 0);
    }
}
-2
4.07.2015 17:48:24
В моих тестах преобразование в строку уничтожает преимущество более быстрого сравнения. Это было примерно в 2,5 раза медленнее, чем простой цикл for.
Doug Clutter 15.07.2015 15:06:35
Когда я делал то же самое, простой был примерно в 8 раз медленнее. Вы можете написать свой код здесь?
Alon 16.07.2015 15:55:15
Будет ли это прерываться, если байт содержит нулевое (0) значение?
Joseph Lennox 22.09.2015 16:52:15
-1 Помимо того, что он медленный из-за преобразования в строку, как указано @DougClutter, это не удастся, если байтовый массив содержит данные не ASCII. Чтобы получить правильный результат, нужно использовать iso-8859-1.
Joe 19.01.2017 10:33:34
Compare(new byte[]{128}, new byte[]{ 255 }) == trueсовсем не
CodesInChaos 3.02.2018 15:57:04

Я опубликовал аналогичный вопрос о проверке, заполнен ли ноль byte []. (SIMD-код был взломан, поэтому я удалил его из этого ответа.) Вот самый быстрый код из моих сравнений:

static unsafe bool EqualBytesLongUnrolled (byte[] data1, byte[] data2)
{
    if (data1 == data2)
        return true;
    if (data1.Length != data2.Length)
        return false;

    fixed (byte* bytes1 = data1, bytes2 = data2) {
        int len = data1.Length;
        int rem = len % (sizeof(long) * 16);
        long* b1 = (long*)bytes1;
        long* b2 = (long*)bytes2;
        long* e1 = (long*)(bytes1 + len - rem);

        while (b1 < e1) {
            if (*(b1) != *(b2) || *(b1 + 1) != *(b2 + 1) || 
                *(b1 + 2) != *(b2 + 2) || *(b1 + 3) != *(b2 + 3) ||
                *(b1 + 4) != *(b2 + 4) || *(b1 + 5) != *(b2 + 5) || 
                *(b1 + 6) != *(b2 + 6) || *(b1 + 7) != *(b2 + 7) ||
                *(b1 + 8) != *(b2 + 8) || *(b1 + 9) != *(b2 + 9) || 
                *(b1 + 10) != *(b2 + 10) || *(b1 + 11) != *(b2 + 11) ||
                *(b1 + 12) != *(b2 + 12) || *(b1 + 13) != *(b2 + 13) || 
                *(b1 + 14) != *(b2 + 14) || *(b1 + 15) != *(b2 + 15))
                return false;
            b1 += 16;
            b2 += 16;
        }

        for (int i = 0; i < rem; i++)
            if (data1 [len - 1 - i] != data2 [len - 1 - i])
                return false;

        return true;
    }
}

Измеряется на двух 256 МБ байтовых массивах:

UnsafeCompare                           : 86,8784 ms
EqualBytesSimd                          : 71,5125 ms
EqualBytesSimdUnrolled                  : 73,1917 ms
EqualBytesLongUnrolled                  : 39,8623 ms
20
24.10.2015 15:40:44
Я подтверждаю. Я также провел тесты. Это быстрее, чем ответ, использующий небезопасный вызов memcmp.
ujeenator 19.11.2015 17:31:53
@AmberdeBlack Вы уверены? Вы тестировали с крошечными массивами?
Zar Shardan 31.03.2016 11:49:36
@ArekBulski Вы уверены, что это быстрее чем memcmp, потому что мое тестирование показывает иначе?
Zar Shardan 3.04.2016 00:39:58
Я получил практически идентичную производительность между этим и memcmp, поэтому +1 за полностью управляемое решение.
Mike Marynowski 26.10.2018 13:46:07

Не смог найти решения, которым я полностью доволен (разумная производительность, но небезопасный код / ​​пинвоук), поэтому я придумал это, ничего оригинального, но работает:

    /// <summary>
    /// 
    /// </summary>
    /// <param name="array1"></param>
    /// <param name="array2"></param>
    /// <param name="bytesToCompare"> 0 means compare entire arrays</param>
    /// <returns></returns>
    public static bool ArraysEqual(byte[] array1, byte[] array2, int bytesToCompare = 0)
    {
        if (array1.Length != array2.Length) return false;

        var length = (bytesToCompare == 0) ? array1.Length : bytesToCompare;
        var tailIdx = length - length % sizeof(Int64);

        //check in 8 byte chunks
        for (var i = 0; i < tailIdx; i += sizeof(Int64))
        {
            if (BitConverter.ToInt64(array1, i) != BitConverter.ToInt64(array2, i)) return false;
        }

        //check the remainder of the array, always shorter than 8 bytes
        for (var i = tailIdx; i < length; i++)
        {
            if (array1[i] != array2[i]) return false;
        }

        return true;
    }

Производительность по сравнению с некоторыми другими решениями на этой странице:

Простой цикл: 19837 тиков, 1,00

* BitConverter: 4886 тиков, 4.06

UnsafeCompare: 1636 тиков, 12.12

EqualBytesLongUnrolled: 637 тиков, 31.09

P / Invoke memcmp: 369 тиков, 53,67

Протестировано в linqpad, 1000000 байтов идентичных массивов (в худшем случае), 500 итераций каждый.

3
31.03.2016 11:37:54
да, я заметил, что в комментарии stackoverflow.com/a/1445280/4489, что мое тестирование показывает, что это на самом деле немного медленнее, чем простой цикл for, который я имел в первоначальном вопросе.
Hafthor 30.03.2016 23:25:02
вы уверены? В моем тестировании это в 4 раза быстрее? Ничто не может сравниться со старым добрым нативным кодом, даже с маршалингом.
Zar Shardan 31.03.2016 11:43:20

Я разработал метод, который слегка бьет memcmp()(ответ плинтуса) и очень мало бьет EqualBytesLongUnrolled()(ответ Арека Бульски ) на моем ПК. По сути, он разворачивает цикл на 4 вместо 8.

Обновление 30 марта 2019 года :

Начиная с .NET core 3.0, у нас есть поддержка SIMD!

Это решение является самым быстрым с большим отрывом на моем ПК:

#if NETCOREAPP3_0
using System.Runtime.Intrinsics.X86;
#endif


public static unsafe bool Compare(byte[] arr0, byte[] arr1)
{
    if (arr0 == arr1)
    {
        return true;
    }
    if (arr0 == null || arr1 == null)
    {
        return false;
    }
    if (arr0.Length != arr1.Length)
    {
        return false;
    }
    if (arr0.Length == 0)
    {
        return true;
    }
    fixed (byte* b0 = arr0, b1 = arr1)
    {
#if NETCOREAPP3_0
        if (Avx2.IsSupported)
        {
            return Compare256(b0, b1, arr0.Length);
        }
        else if (Sse2.IsSupported)
        {
            return Compare128(b0, b1, arr0.Length);
        }
        else
#endif
        {
            return Compare64(b0, b1, arr0.Length);
        }
    }
}
#if NETCOREAPP3_0
public static unsafe bool Compare256(byte* b0, byte* b1, int length)
{
    byte* lastAddr = b0 + length;
    byte* lastAddrMinus128 = lastAddr - 128;
    const int mask = -1;
    while (b0 < lastAddrMinus128) // unroll the loop so that we are comparing 128 bytes at a time.
    {
        if (Avx2.MoveMask(Avx2.CompareEqual(Avx.LoadVector256(b0), Avx.LoadVector256(b1))) != mask)
        {
            return false;
        }
        if (Avx2.MoveMask(Avx2.CompareEqual(Avx.LoadVector256(b0 + 32), Avx.LoadVector256(b1 + 32))) != mask)
        {
            return false;
        }
        if (Avx2.MoveMask(Avx2.CompareEqual(Avx.LoadVector256(b0 + 64), Avx.LoadVector256(b1 + 64))) != mask)
        {
            return false;
        }
        if (Avx2.MoveMask(Avx2.CompareEqual(Avx.LoadVector256(b0 + 96), Avx.LoadVector256(b1 + 96))) != mask)
        {
            return false;
        }
        b0 += 128;
        b1 += 128;
    }
    while (b0 < lastAddr)
    {
        if (*b0 != *b1) return false;
        b0++;
        b1++;
    }
    return true;
}
public static unsafe bool Compare128(byte* b0, byte* b1, int length)
{
    byte* lastAddr = b0 + length;
    byte* lastAddrMinus64 = lastAddr - 64;
    const int mask = 0xFFFF;
    while (b0 < lastAddrMinus64) // unroll the loop so that we are comparing 64 bytes at a time.
    {
        if (Sse2.MoveMask(Sse2.CompareEqual(Sse2.LoadVector128(b0), Sse2.LoadVector128(b1))) != mask)
        {
            return false;
        }
        if (Sse2.MoveMask(Sse2.CompareEqual(Sse2.LoadVector128(b0 + 16), Sse2.LoadVector128(b1 + 16))) != mask)
        {
            return false;
        }
        if (Sse2.MoveMask(Sse2.CompareEqual(Sse2.LoadVector128(b0 + 32), Sse2.LoadVector128(b1 + 32))) != mask)
        {
            return false;
        }
        if (Sse2.MoveMask(Sse2.CompareEqual(Sse2.LoadVector128(b0 + 48), Sse2.LoadVector128(b1 + 48))) != mask)
        {
            return false;
        }
        b0 += 64;
        b1 += 64;
    }
    while (b0 < lastAddr)
    {
        if (*b0 != *b1) return false;
        b0++;
        b1++;
    }
    return true;
}
#endif
public static unsafe bool Compare64(byte* b0, byte* b1, int length)
{
    byte* lastAddr = b0 + length;
    byte* lastAddrMinus32 = lastAddr - 32;
    while (b0 < lastAddrMinus32) // unroll the loop so that we are comparing 32 bytes at a time.
    {
        if (*(ulong*)b0 != *(ulong*)b1) return false;
        if (*(ulong*)(b0 + 8) != *(ulong*)(b1 + 8)) return false;
        if (*(ulong*)(b0 + 16) != *(ulong*)(b1 + 16)) return false;
        if (*(ulong*)(b0 + 24) != *(ulong*)(b1 + 24)) return false;
        b0 += 32;
        b1 += 32;
    }
    while (b0 < lastAddr)
    {
        if (*b0 != *b1) return false;
        b0++;
        b1++;
    }
    return true;
}
7
2.04.2019 15:51:50
Мои измерения отличаются .NET 462 может NETCORE:
Motlicek Petr 26.09.2016 10:55:04
Сбой кода при сравнении двух массивов нулевой длины, потому что закрепление возвращается null.
Glenn Slayden 17.04.2017 12:53:54
memcmp - это не просто средство сравнения. Он предоставляет информацию о том, какой объект больше или меньше. Можете ли вы принять свой алгоритм для этой цели и проверить производительность?
nicolay.anykienko 24.01.2018 11:48:16
Это быстрее чем Spanи memcpy?
silkfire 9.03.2020 15:20:07
@silkfire На .NET core 3 и современном процессоре это должно быть в 2-3 раза быстрее для больших массивов.
Mr Anderson 9.03.2020 15:44:05

Кажется, что EqualBytesLongUnrolled является лучшим из предложенного выше.

Пропущенные методы (Enumerable.SequenceEqual, StructuralComparisons.StructuralEqualityComparer.Equals) не были медленными для пациента. На 265 МБ массивах я измерил это:

Host Process Environment Information:
BenchmarkDotNet.Core=v0.9.9.0
OS=Microsoft Windows NT 6.2.9200.0
Processor=Intel(R) Core(TM) i7-3770 CPU 3.40GHz, ProcessorCount=8
Frequency=3323582 ticks, Resolution=300.8802 ns, Timer=TSC
CLR=MS.NET 4.0.30319.42000, Arch=64-bit RELEASE [RyuJIT]
GC=Concurrent Workstation
JitModules=clrjit-v4.6.1590.0

Type=CompareMemoriesBenchmarks  Mode=Throughput  

                 Method |      Median |    StdDev | Scaled | Scaled-SD |
----------------------- |------------ |---------- |------- |---------- |
             NewMemCopy |  30.0443 ms | 1.1880 ms |   1.00 |      0.00 |
 EqualBytesLongUnrolled |  29.9917 ms | 0.7480 ms |   0.99 |      0.04 |
          msvcrt_memcmp |  30.0930 ms | 0.2964 ms |   1.00 |      0.03 |
          UnsafeCompare |  31.0520 ms | 0.7072 ms |   1.03 |      0.04 |
       ByteArrayCompare | 212.9980 ms | 2.0776 ms |   7.06 |      0.25 |

OS=Windows
Processor=?, ProcessorCount=8
Frequency=3323582 ticks, Resolution=300.8802 ns, Timer=TSC
CLR=CORE, Arch=64-bit ? [RyuJIT]
GC=Concurrent Workstation
dotnet cli version: 1.0.0-preview2-003131

Type=CompareMemoriesBenchmarks  Mode=Throughput  

                 Method |      Median |    StdDev | Scaled | Scaled-SD |
----------------------- |------------ |---------- |------- |---------- |
             NewMemCopy |  30.1789 ms | 0.0437 ms |   1.00 |      0.00 |
 EqualBytesLongUnrolled |  30.1985 ms | 0.1782 ms |   1.00 |      0.01 |
          msvcrt_memcmp |  30.1084 ms | 0.0660 ms |   1.00 |      0.00 |
          UnsafeCompare |  31.1845 ms | 0.4051 ms |   1.03 |      0.01 |
       ByteArrayCompare | 212.0213 ms | 0.1694 ms |   7.03 |      0.01 |
3
26.09.2016 12:08:20
Я обновил свой NewMemCmpответ, чтобы использовать AVX-2
Mr Anderson 2.04.2019 15:47:29

Давайте добавим еще один!

Недавно Microsoft выпустила специальный пакет NuGet, System.Runtime.CompilerServices.Unsafe . Он особенный, потому что он написан на IL , и предоставляет низкоуровневую функциональность, прямо недоступную в C #.

Один из его методов Unsafe.As<T>(object)позволяет приводить любой ссылочный тип к другому ссылочному типу, пропуская любые проверки безопасности. Обычно это очень плохая идея, но если оба типа имеют одинаковую структуру, это может сработать. Таким образом, мы можем использовать это, чтобы привести byte[]к long[]:

bool CompareWithUnsafeLibrary(byte[] a1, byte[] a2)
{
    if (a1.Length != a2.Length) return false;

    var longSize = (int)Math.Floor(a1.Length / 8.0);
    var long1 = Unsafe.As<long[]>(a1);
    var long2 = Unsafe.As<long[]>(a2);

    for (var i = 0; i < longSize; i++)
    {
        if (long1[i] != long2[i]) return false;
    }

    for (var i = longSize * 8; i < a1.Length; i++)
    {
        if (a1[i] != a2[i]) return false;
    }

    return true;
}

Обратите внимание, что long1.Lengthвсе равно будет возвращаться длина исходного массива, поскольку он хранится в поле в структуре памяти массива.

Этот метод не такой быстрый, как другие методы, продемонстрированные здесь, но он намного быстрее, чем простой метод, не использует небезопасный код, P / Invoke или закрепление, а реализация довольно проста (IMO). Вот некоторые результаты BenchmarkDotNet с моей машины:

BenchmarkDotNet=v0.10.3.0, OS=Microsoft Windows NT 6.2.9200.0
Processor=Intel(R) Core(TM) i7-4870HQ CPU 2.50GHz, ProcessorCount=8
Frequency=2435775 Hz, Resolution=410.5470 ns, Timer=TSC
  [Host]     : Clr 4.0.30319.42000, 64bit RyuJIT-v4.6.1637.0
  DefaultJob : Clr 4.0.30319.42000, 64bit RyuJIT-v4.6.1637.0

                 Method |          Mean |    StdDev |
----------------------- |-------------- |---------- |
          UnsafeLibrary |   125.8229 ns | 0.3588 ns |
          UnsafeCompare |    89.9036 ns | 0.8243 ns |
           JSharpEquals | 1,432.1717 ns | 1.3161 ns |
 EqualBytesLongUnrolled |    43.7863 ns | 0.8923 ns |
              NewMemCmp |    65.4108 ns | 0.2202 ns |
            ArraysEqual |   910.8372 ns | 2.6082 ns |
          PInvokeMemcmp |    52.7201 ns | 0.1105 ns |

Я также создал суть со всеми тестами .

10
3.07.2017 15:27:29
Он не использует ключевое слово unsafe, но в любом случае вызывает небезопасный код с помощью System.Runtime.CompilerServices.Unsafe
Paulo Zemek 3.07.2018 21:36:09
Я обновил свой NewMemCmpответ, чтобы использовать AVX-2
Mr Anderson 2.04.2019 15:51:11

Это почти наверняка намного медленнее, чем любая другая версия, приведенная здесь, но было весело писать.

static bool ByteArrayEquals(byte[] a1, byte[] a2) 
{
    return a1.Zip(a2, (l, r) => l == r).All(x => x);
}
1
27.09.2017 23:23:43

Я провел некоторые измерения, используя прилагаемую программу .net 4.7 Release build без отладчика. Я думаю, что люди использовали неправильную метрику, так как то, о чем вы говорите, если вы заботитесь о скорости, это то, сколько времени нужно, чтобы выяснить, равны ли два байтовых массива. т.е. пропускная способность в байтах.

StructuralComparison :              4.6 MiB/s
for                  :            274.5 MiB/s
ToUInt32             :            263.6 MiB/s
ToUInt64             :            474.9 MiB/s
memcmp               :           8500.8 MiB/s

Как видите, нет лучшего способа, чем memcmpон, и он на несколько порядков быстрее. Простой forцикл - второй лучший вариант. И это все еще поражает, почему Microsoft не может просто включить Buffer.Compareметод.

[Program.cs]:

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Runtime.InteropServices;
using System.Text;
using System.Threading.Tasks;

namespace memcmp
{
    class Program
    {
        static byte[] TestVector(int size)
        {
            var data = new byte[size];
            using (var rng = new System.Security.Cryptography.RNGCryptoServiceProvider())
            {
                rng.GetBytes(data);
            }
            return data;
        }

        static TimeSpan Measure(string testCase, TimeSpan offset, Action action, bool ignore = false)
        {
            var t = Stopwatch.StartNew();
            var n = 0L;
            while (t.Elapsed < TimeSpan.FromSeconds(10))
            {
                action();
                n++;
            }
            var elapsed = t.Elapsed - offset;
            if (!ignore)
            {
                Console.WriteLine($"{testCase,-16} : {n / elapsed.TotalSeconds,16:0.0} MiB/s");
            }
            return elapsed;
        }

        [DllImport("msvcrt.dll", CallingConvention = CallingConvention.Cdecl)]
        static extern int memcmp(byte[] b1, byte[] b2, long count);

        static void Main(string[] args)
        {
            // how quickly can we establish if two sequences of bytes are equal?

            // note that we are testing the speed of different comparsion methods

            var a = TestVector(1024 * 1024); // 1 MiB
            var b = (byte[])a.Clone();

            // was meant to offset the overhead of everything but copying but my attempt was a horrible mistake... should have reacted sooner due to the initially ridiculous throughput values...
            // Measure("offset", new TimeSpan(), () => { return; }, ignore: true);
            var offset = TimeZone.Zero

            Measure("StructuralComparison", offset, () =>
            {
                StructuralComparisons.StructuralEqualityComparer.Equals(a, b);
            });

            Measure("for", offset, () =>
            {
                for (int i = 0; i < a.Length; i++)
                {
                    if (a[i] != b[i]) break;
                }
            });

            Measure("ToUInt32", offset, () =>
            {
                for (int i = 0; i < a.Length; i += 4)
                {
                    if (BitConverter.ToUInt32(a, i) != BitConverter.ToUInt32(b, i)) break;
                }
            });

            Measure("ToUInt64", offset, () =>
            {
                for (int i = 0; i < a.Length; i += 8)
                {
                    if (BitConverter.ToUInt64(a, i) != BitConverter.ToUInt64(b, i)) break;
                }
            });

            Measure("memcmp", offset, () =>
            {
                memcmp(a, b, a.Length);
            });
        }
    }
}
3
24.03.2019 16:32:48

Я не видел много решений linq здесь.

Я не уверен в последствиях для производительности, однако, как правило, придерживаюсь практического linqправила, а затем оптимизирую его позже, если это необходимо.

public bool CompareTwoArrays(byte[] array1, byte[] array2)
 {
   return !array1.Where((t, i) => t != array2[i]).Any();
 }

Обратите внимание, что это работает, только если они имеют одинаковый размер массива. расширение может выглядеть так

public bool CompareTwoArrays(byte[] array1, byte[] array2)
 {
   if (array1.Length != array2.Length) return false;
   return !array1.Where((t, i) => t != array2[i]).Any();
 }
3
2.02.2018 06:53:46
Весь смысл вопроса заключается в более быстром решении, чем функция, размещенная в вопросе.
CodesInChaos 3.02.2018 15:57:41

Span<T> предлагает чрезвычайно конкурентоспособную альтернативу без необходимости вводить запутанный и / или непереносимый пух в базу кода вашего собственного приложения:

// byte[] is implicitly convertible to ReadOnlySpan<byte>
static bool ByteArrayCompare(ReadOnlySpan<byte> a1, ReadOnlySpan<byte> a2)
{
    return a1.SequenceEqual(a2);
}

Реализация (внутренности) .NET Core 3.1.0 может быть найдена здесь .

Я пересмотрел суть @ EliArbel, добавив этот метод так SpansEqual, чтобы отбрасывать большинство менее интересных исполнителей в тестах других, запускать его с различными размерами массива, выводить графики и отмечать SpansEqualв качестве базового уровня, чтобы он сообщал, как разные методы сравниваются с SpansEqual,

Приведенные ниже цифры взяты из результатов, слегка отредактированных для удаления столбца «Ошибка».

|        Method |  ByteCount |               Mean |            StdDev | Ratio |
|-------------- |----------- |-------------------:|------------------:|------:|
|    SpansEqual |         15 |           3.562 ns |         0.0035 ns |  1.00 |
|  LongPointers |         15 |           4.611 ns |         0.0028 ns |  1.29 |
|      Unrolled |         15 |          18.035 ns |         0.0195 ns |  5.06 |
| PInvokeMemcmp |         15 |          11.210 ns |         0.0353 ns |  3.15 |
|               |            |                    |                   |       |
|    SpansEqual |       1026 |          20.048 ns |         0.0286 ns |  1.00 |
|  LongPointers |       1026 |          63.347 ns |         0.1062 ns |  3.16 |
|      Unrolled |       1026 |          39.175 ns |         0.0304 ns |  1.95 |
| PInvokeMemcmp |       1026 |          40.830 ns |         0.0350 ns |  2.04 |
|               |            |                    |                   |       |
|    SpansEqual |    1048585 |      44,070.526 ns |        35.3348 ns |  1.00 |
|  LongPointers |    1048585 |      59,973.407 ns |        80.4145 ns |  1.36 |
|      Unrolled |    1048585 |      55,032.945 ns |        24.4745 ns |  1.25 |
| PInvokeMemcmp |    1048585 |      55,593.719 ns |        22.4301 ns |  1.26 |
|               |            |                    |                   |       |
|    SpansEqual | 2147483591 | 253,648,180.000 ns | 1,112,524.3074 ns |  1.00 |
|  LongPointers | 2147483591 | 249,412,064.286 ns | 1,079,409.5670 ns |  0.98 |
|      Unrolled | 2147483591 | 246,329,091.667 ns |   852,021.7992 ns |  0.97 |
| PInvokeMemcmp | 2147483591 | 247,795,940.000 ns | 3,390,676.3644 ns |  0.98 |

Я был удивлен, увидев, SpansEqualчто методы max-array-size не вышли на первое место, но разница настолько мала, что я не думаю, что это когда-либо будет иметь значение.

Информация о моей системе:

BenchmarkDotNet=v0.12.0, OS=Windows 10.0.18362
Intel Core i7-6850K CPU 3.60GHz (Skylake), 1 CPU, 12 logical and 6 physical cores
.NET Core SDK=3.1.100
  [Host]     : .NET Core 3.1.0 (CoreCLR 4.700.19.56402, CoreFX 4.700.19.56404), X64 RyuJIT
  DefaultJob : .NET Core 3.1.0 (CoreCLR 4.700.19.56402, CoreFX 4.700.19.56404), X64 RyuJIT
69
14.12.2019 14:34:39
Я никогда не думал, что буду использовать Span <T> или что-то похожее во всем, что я делаю. Благодаря вам я могу теперь похвастаться этим перед моими сотрудниками.
jokab 20.02.2018 03:14:36
Специально ли реализован SequenceEqual как метод Span? Думал, что это был только один из методов расширения IEnumerable.
Zastai 6.04.2018 09:26:28
@ Zastai да, {ReadOnly,}Span<T>имеет свою собственную версию SequenceEqual(то же имя, потому что у него тот же контракт, что и у соответствующего IEnumerable<T>метода расширения, он просто быстрее). Обратите внимание, что {ReadOnly,}Span<T>нельзя использовать IEnumerable<T>методы расширения из-за ограничений на ref structтипы.
Joe Amenta 6.04.2018 10:33:36
@Sentinel пакет System.Memory имеет «портативные» / «медленные» Span<T>реализации для netstandard1.1и выше (поэтому поиграйтесь с этой интерактивной диаграммой, чтобы увидеть, что это такое). «Быстрый» Span<T>доступен в настоящее время только в .NET Core 2.1, но учтите, что в SequenceEqual<T>частности, между «быстрым» и «медленным» / «переносимым» должно быть очень мало различий (хотя netstandard2.0цели должны видеть небольшое улучшение, потому что они иметь векторизованный путь кода).
Joe Amenta 26.06.2018 10:14:53
install-package system.memory
Chris Moschini 16.10.2018 14:15:57

Поскольку многие из вышеперечисленных причудливых решений не работают с UWP и потому что я люблю Linq и функциональные подходы, я представляю вам свою версию этой проблемы. Чтобы избежать сравнения при возникновении первого различия, я выбрал .FirstOrDefault ()

public static bool CompareByteArrays(byte[] ba0, byte[] ba1) =>
    !(ba0.Length != ba1.Length || Enumerable.Range(1,ba0.Length)
        .FirstOrDefault(n => ba0[n] != ba1[n]) > 0);
-2
7.02.2018 14:43:39
-1 потому что этот код не работает и явно не проверен. Это бросает IndexOutOfRangeExceptionпри сравнении непустых массивов , потому что вы к элементам 1через , ba0.Lengthкогда он должен быть 0через ba0.Length - 1. Если вы исправите это, Enumerable.Range(0, ba0.Length)он по-прежнему некорректно возвращает trueмассивы равной длины, в которых отличаются только первые элементы, потому что вы не можете различить удовлетворяющие первые элементы predicateи не удовлетворяющие элементы predicate; FirstOrDefault<int>()возвращается 0в обоих случаях.
BACON 27.04.2018 00:19:26
Урок здесь, дети: не приносите нож в перестрелку
Richard Hauer 8.03.2019 14:04:48

Я остановился на решении, основанном на методе EqualBytesLongUnrolled, опубликованном ArekBulski, с дополнительной оптимизацией. В моем случае различия массивов в массивах, как правило, находятся рядом с хвостом массивов. В ходе тестирования я обнаружил, что в случае больших массивов возможность сравнивать элементы массива в обратном порядке дает этому решению огромный выигрыш в производительности по сравнению с решением на основе memcmp. Вот это решение:

public enum CompareDirection { Forward, Backward }

private static unsafe bool UnsafeEquals(byte[] a, byte[] b, CompareDirection direction = CompareDirection.Forward)
{
    // returns when a and b are same array or both null
    if (a == b) return true;

    // if either is null or different lengths, can't be equal
    if (a == null || b == null || a.Length != b.Length)
        return false;

    const int UNROLLED = 16;                // count of longs 'unrolled' in optimization
    int size = sizeof(long) * UNROLLED;     // 128 bytes (min size for 'unrolled' optimization)
    int len = a.Length;
    int n = len / size;         // count of full 128 byte segments
    int r = len % size;         // count of remaining 'unoptimized' bytes

    // pin the arrays and access them via pointers
    fixed (byte* pb_a = a, pb_b = b)
    {
        if (r > 0 && direction == CompareDirection.Backward)
        {
            byte* pa = pb_a + len - 1;
            byte* pb = pb_b + len - 1;
            byte* phead = pb_a + len - r;
            while(pa >= phead)
            {
                if (*pa != *pb) return false;
                pa--;
                pb--;
            }
        }

        if (n > 0)
        {
            int nOffset = n * size;
            if (direction == CompareDirection.Forward)
            {
                long* pa = (long*)pb_a;
                long* pb = (long*)pb_b;
                long* ptail = (long*)(pb_a + nOffset);
                while (pa < ptail)
                {
                    if (*(pa + 0) != *(pb + 0) || *(pa + 1) != *(pb + 1) ||
                        *(pa + 2) != *(pb + 2) || *(pa + 3) != *(pb + 3) ||
                        *(pa + 4) != *(pb + 4) || *(pa + 5) != *(pb + 5) ||
                        *(pa + 6) != *(pb + 6) || *(pa + 7) != *(pb + 7) ||
                        *(pa + 8) != *(pb + 8) || *(pa + 9) != *(pb + 9) ||
                        *(pa + 10) != *(pb + 10) || *(pa + 11) != *(pb + 11) ||
                        *(pa + 12) != *(pb + 12) || *(pa + 13) != *(pb + 13) ||
                        *(pa + 14) != *(pb + 14) || *(pa + 15) != *(pb + 15)
                    )
                    {
                        return false;
                    }
                    pa += UNROLLED;
                    pb += UNROLLED;
                }
            }
            else
            {
                long* pa = (long*)(pb_a + nOffset);
                long* pb = (long*)(pb_b + nOffset);
                long* phead = (long*)pb_a;
                while (phead < pa)
                {
                    if (*(pa - 1) != *(pb - 1) || *(pa - 2) != *(pb - 2) ||
                        *(pa - 3) != *(pb - 3) || *(pa - 4) != *(pb - 4) ||
                        *(pa - 5) != *(pb - 5) || *(pa - 6) != *(pb - 6) ||
                        *(pa - 7) != *(pb - 7) || *(pa - 8) != *(pb - 8) ||
                        *(pa - 9) != *(pb - 9) || *(pa - 10) != *(pb - 10) ||
                        *(pa - 11) != *(pb - 11) || *(pa - 12) != *(pb - 12) ||
                        *(pa - 13) != *(pb - 13) || *(pa - 14) != *(pb - 14) ||
                        *(pa - 15) != *(pb - 15) || *(pa - 16) != *(pb - 16)
                    )
                    {
                        return false;
                    }
                    pa -= UNROLLED;
                    pb -= UNROLLED;
                }
            }
        }

        if (r > 0 && direction == CompareDirection.Forward)
        {
            byte* pa = pb_a + len - r;
            byte* pb = pb_b + len - r;
            byte* ptail = pb_a + len;
            while(pa < ptail)
            {
                if (*pa != *pb) return false;
                pa++;
                pb++;
            }
        }
    }

    return true;
}
1
26.02.2018 14:07:04

Для тех из вас, кто заботится о порядке (т. Е. Хочет, чтобы вы memcmpвозвращали « intкак надо» вместо «ничего»), .NET Core 3.0 (и, по-видимому, .NET Standard 2.1 или .NET 5.0) будет включать в себя Span.SequenceCompareTo(...)метод расширения (плюс a Span.SequenceEqualTo), который может использоваться для сравнения двух ReadOnlySpan<T>экземпляров ( where T: IComparable<T>).

В первоначальном предложении GitHub обсуждение включало в себя сравнение подходов с вычислениями таблицы переходов, чтение byte[]as long[], использование SIMD и p / invoke для реализации CLR memcmp.

В дальнейшем это должен быть метод перехода для сравнения массивов байтов или диапазонов байтов (как следует использовать Span<byte>вместо byte[]API-интерфейсов .NET Standard 2.1), и он достаточно быстр, чтобы вам больше не нужно было его оптимизировать (и нет, несмотря на сходство в названии, оно не так ужасно, как ужасно Enumerable.SequenceEqual).

#if NETCOREAPP3_0
// Using the platform-native Span<T>.SequenceEqual<T>(..)
public static int Compare(byte[] range1, int offset1, byte[] range2, int offset2, int count)
{
    var span1 = range1.AsSpan(offset1, count);
    var span2 = range2.AsSpan(offset2, count);

    return span1.SequenceCompareTo(span2);
    // or, if you don't care about ordering
    // return span1.SequenceEqual(span2);
}
#else
// The most basic implementation, in platform-agnostic, safe C#
public static bool Compare(byte[] range1, int offset1, byte[] range2, int offset2, int count)
{
    // Working backwards lets the compiler optimize away bound checking after the first loop
    for (int i = count - 1; i >= 0; --i)
    {
        if (range1[offset1 + i] != range2[offset2 + i])
        {
            return false;
        }
    }

    return true;
}
#endif
2
24.10.2019 09:16:55