Поскольку вы упомянули эффективность, вот несколько сильно оптимизированных кодов C # , которые я написал, которые используют собственную адресацию и максимальное чтение с выравниванием по ключевым словам, чтобы сократить число обращений к памяти в 8 раз. удивитесь, если есть более быстрый способ поиска байта в памяти в .NET .
Возвращает индекс первого вхождения байта 'v' в диапазоне памяти, начиная со смещения i (относительно адреса src) и продолжаясь в течение длины c. Возвращает -1 , если байт v не найден.
// fast IndexOf byte in memory. (To use this with managed byte[] array, see below)
public unsafe static int IndexOfByte(byte* src, byte v, int i, int c)
{
ulong t;
byte* p, pEnd;
for (p = src + i; ((long)p & 7) != 0; c--, p++)
if (c == 0)
return -1;
else if (*p == v)
return (int)(p - src);
ulong r = v; r |= r << 8; r |= r << 16; r |= r << 32;
for (pEnd = p + (c & ~7); p < pEnd; p += 8)
{
t = *(ulong*)p ^ r;
t = (t - 0x0101010101010101) & ~t & 0x8080808080808080;
if (t != 0)
{
t &= (ulong)-(long)t;
return (int)(p - src) + dbj8[t * 0x07EDD5E59A4E28C2 >> 58];
}
}
for (pEnd += c & 7; p < pEnd; p++)
if (*p == v)
return (int)(p - src);
return -1;
}
Не пугайтесь одного умножения, которое вы видите; он выполняется только один раз за вызов этой функции, чтобы выполнить окончательный поиск deBruijn . Используемая для этого справочная таблица только для чтения представляет собой простой общий список из 64-байтовых значений, который требует однократной только инициализации:
// elsewhere in the static class...
readonly static sbyte[] dbj8 =
{
7, -1, -1, -1, -1, 5, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, 6, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, 3, -1, -1, -1, -1, -1, -1, 1, -1, 2, 0, -1, -1,
};
К значениям -1 никогда не обращаются, и при желании их можно оставить равными нулю, как показано в следующей альтернативе предыдущему коду инициализации таблицы, если вы предпочитаете:
static MyStaticClass()
{
dbj8 = new sbyte[64]; // initialize the lookup table (alternative to the above)
dbj8[0x00] = 7;
dbj8[0x18] = 6;
dbj8[0x05] = 5;
dbj8[0x09] = 4;
dbj8[0x33] = 3;
dbj8[0x3C] = 2;
dbj8[0x3A] = 1;
/* dbj8[0x3D] = 0; */
}
readonly static sbyte[] dbj8, dbj16;
Для полноты рассмотрим, как использовать функцию с прототипом метода, предоставленным ФП в исходном вопросе.
/// Finds the first occurrence of a specific byte in a byte array.
/// If not found, returns -1.
public static unsafe int GetFirstOccurance(byte byteToFind, byte[] byteArray)
{
fixed (byte* p = byteArray)
return IndexOfByte(p, byteToFind, 0, byteArray.Length);
}
Обсуждение
Мой код немного сложен, поэтому подробное изучение оставлено в качестве упражнения для заинтересованного читателя. Вы можете изучить другой взгляд на общий подход к поиску по групповой памяти во внутреннем методе .NET Buffer.IndexOfByte , но этот код имеет существенные недостатки по сравнению с моим:
- Наиболее важно, что код .NET сканирует только 4 байта за раз вместо 8, как у меня.
- Это не публичный метод, поэтому вам нужно использовать рефлексию для его вызова.
- .NET-код имеет «утечку производительности», когда проверка
t1 != 0 дает ложное срабатывание , а четыре последующие проверки теряются. Обратите внимание на их «провальный» случай: из-за этого ложноположительного результата им требуется четыре заключительных проверки - таким образом, позволяющих провалиться - для поддержания правильности, а не только три.
- Ложно-положительный результат кода .NET вызван внутренне низкими побитовыми вычислениями, основанными на переполнении бита переноса из одного байта в следующий. Это приводит к асимметрии дополняющих два (о чем свидетельствует использование ими констант
0x7efefeff или 0x81010100) и случайному «левому выходу» (т. Е. Потере) информации, касающейся самого значимого байта, что является настоящей проблемой здесь. В отличие от этого, я использую вычисления underflow , которые сохраняют вычисления каждого байта независимо от его соседей '. Мой метод дает убедительный результат во всех случаях без ложноположительной или «сквозной» обработки.
- Мой код использует метод без ветвей для окончательного поиска. Обычно считается, что несколько неразветвленных логических операций (плюс в данном случае одно умножение) способствуют повышению производительности по сравнению с расширенными
if-else структурами, поскольку последние могут нарушить прогнозирующее кэширование ЦП . Эта проблема более важна для моего 8-байтового сканера, потому что без использования поиска у меня было бы вдвое больше if-else условий при окончательной проверке, чем у 4-байтового группового сканера.
Конечно, если вас не интересуют все эти мелочи, вы можете просто скопировать и использовать код; Я полностью протестировал его и проверил правильное поведение для всех правильно сформированных входных данных. Поэтому, пока базовая функциональность готова к использованию, вы, вероятно, захотите добавить проверку аргументов.
[править:]
<strong>String.IndexOf(String s, Char char, int ix_start, int count)</strong> ... <strong><em>fast!</em></strong>
Поскольку вышеописанный метод успешно работал в моих проектах, я расширил его, чтобы охватить 16-битный поиск. Вот тот же код, адаптированный для поиска 16-битного короткого, ushort или char примитива вместо byte. Этот адаптированный метод также был независимо проверен на соответствие его собственной соответствующей методологии модульных испытаний, адаптированной сверху.
static MyStaticClass()
{
dbj16 = new sbyte[64];
/* dbj16[0x3A] = 0; */
dbj16[0x33] = 1;
dbj16[0x05] = 2;
dbj16[0x00] = 3;
}
readonly static sbyte[] dbj16;
public static int IndexOf(ushort* src, ushort v, int i, int c)
{
ulong t;
ushort* p, pEnd;
for (p = src + i; ((long)p & 7) != 0; c--, p++)
if (c == 0)
return -1;
else if (*p == v)
return (int)(p - src);
ulong r = ((ulong)v << 16) | v;
r |= r << 32;
for (pEnd = p + (c & ~7); p < pEnd; p += 4)
{
t = *(ulong*)p ^ r;
t = (t - 0x0001000100010001) & ~t & 0x8000800080008000;
if (t != 0)
{
i = dbj16[(t & (ulong)-(long)t) * 0x07EDD5E59A4E28C2 >> 58];
return (int)(p - src) + i;
}
}
for (pEnd += c & 7; p < pEnd; p++)
if (*p == v)
return (int)(p - src);
return -1;
}
И ниже приведены различные перегрузки для доступа к этому для оставшихся 16-битных примитивов, плюс String (последний показанный):
public static int IndexOf(this char[] rg, char v) => IndexOf(rg, v, 0, rg.Length);
public static int IndexOf(this char[] rg, char v, int i, int c = -1)
{
if (rg != null && (c = c < 0 ? rg.Length - i : c) > 0)
fixed (char* p = rg)
return IndexOf((ushort*)p, v, i, c < 0 ? rg.Length - i : c);
return -1;
}
public static int IndexOf(this short[] rg, short v) => IndexOf(rg, v, 0, rg.Length);
public static int IndexOf(this short[] rg, short v, int i, int c = -1)
{
if (rg != null && (c = c < 0 ? rg.Length - i : c) > 0)
fixed (short* p = rg)
return IndexOf((ushort*)p, (ushort)v, i, c < 0 ? rg.Length - i : c);
return -1;
}
public static int IndexOf(this ushort[] rg, ushort v) => IndexOf(rg, v, 0, rg.Length);
public static int IndexOf(this ushort[] rg, ushort v, int i, int c = -1)
{
if (rg != null && (c = c < 0 ? rg.Length - i : c) > 0)
fixed (ushort* p = rg)
return IndexOf(p, v, i, c < 0 ? rg.Length - i : c);
return -1;
}
public static int IndexOf(String s, Char ch, int i = 0, int c = -1)
{
if (s != null && (c = c < 0 ? s.Length - i : c) > 0)
fixed (char* p = s)
return IndexOf((ushort*)p, ch, i, c);
return -1;
}
Обратите внимание, что перегрузка String не помечена как метод расширения, поскольку эта высокопроизводительная замещающая версия функции никогда не будет вызываться таким образом (встроенные методы с одинаковым именем всегда имеют приоритет над методами расширения). Чтобы использовать его как расширение для String экземпляров, вы можете изменить имя этого метода. Например, IndexOf__(this String s,...) может привести к появлению рядом с именем встроенного метода в списках Intellisense , что может быть полезным напоминанием о необходимости подписки. В противном случае, если вам не нужен синтаксис расширения, вы можете просто вызвать эту оптимизированную версию напрямую как статический метод своего собственного класса, когда хотите использовать ее вместо s.IndexOf(Char ch).