소개
이진 연산 확장 함수는 바이트 배열에 적용되어 기본 이진 연산자를 사용하는 쉽고 빠른 방법을 제공합니다. AND, OR, XOR, NOT, Shift Left, Shift Right 연산자가 제공됩니다.
제공된 함수는 System.Threading.Tasks.Parallel라이브러리 및 unsafe포인터가 바이트 배열의 요소에 순차적으로 액세스하는 데 사용되는 많은 영역 에 의존 합니다.
배경
처음 for에는 다음 명령문과 같이 배열의 모든 요소에 대해 동일한 이진 연산을 반복 하는 간단한 사이클을 사용했습니다 .

public static byte[] Bin_And_noParallel_noPointers(this byte[] ba, byte[] bt)
{
int longlen = Math.Max(ba.Length, bt.Length);
int shortlen = Math.Min(ba.Length, bt.Length);
byte[] result = new byte[longlen];
for (int i = 0; i < shortlen; i++)
{
result[i] = (byte)(ba[i] & bt[i]);
}
return result;
}
public static byte[] Bin_And(this byte[] ba, byte[] bt)
public static byte[] Bin_Or(this byte[] ba, byte[] bt)
public static byte[] Bin_Xor(this byte[] ba, byte[] bt)
public static byte[] Bin_Not(this byte[] ba)
public static byte[] Bin_ShiftLeft(this byte[] ba, int bits)
public static byte[] Bin_ShiftRight(this byte[] ba, int bits)

이러한 함수는 확장 된 메서드이며 두 바이트 배열간에 이진 ‘AND’연산이 실행되는 다음 예에서 설명하는 방식으로 사용됩니다.

byte[] MyFirstByteArray, MySecondByteArray;
// fill the arrays here, for example by loading them from files
// (System.IO.File.ReadAllBytes) or filling them manually or with random bytes
byte[] result = MyFirstByteArray.Bin_And(MySecondByteArray);

이러한 기능을 시도하려면 포인터가 usafe 영역에서 사용되므로 프로젝트-> 속성-> 빌드에서 ‘안전하지 않은 코드 허용’상자를 선택해야합니다.

나는 바이트 배열을 문학 텍스트 (예 : 1308 년과 1321 년경에 쓴 유명한 이탈리아 시인 Dante Alighieri의 ‘신곡’처럼)로 채워서 이러한 작업을 테스트했습니다. 따라서 저작권 문제가 없어야합니다. 500,000 바이트, 제대로 작동했습니다.

코드 설명
이전에 언급했듯이 간단한 이진 함수를 개선하기위한 여정 동안 더 빠르게 만들기 위해 세 가지 전략, 즉 바이트 대신 병렬 처리, 포인터 및 정수를 시도했습니다.

처음에는 간단한 방법을 사용해 보았는데 System.Threading.Tasks.Parallel.For실행 속도가 약간 증가했지만 그다지 많지는 않았습니다.

그런 다음 포인터 접근 방식을 시도했습니다. 인덱스 (예 : in MyArray[175]) 를 통해 배열에 액세스하는 것이 첫 번째 바이트에서 마지막 바이트로 순차적으로 이동하는 포인터를 통해 동일한 데이터에 액세스하는 것보다 느립니다. 이 두 번째 접근 방식은 병렬 접근 방식보다 빠르지는 않지만 유사한 좋은 결과를 제공했습니다.

그럼 .. 조합 해보는 건 어떨까요?

글쎄, Parallel.For전체 속도가 크게 떨어졌기 때문에를 사용하는 것은 나쁜 생각이었습니다.

최종 솔루션은 좀 더 복잡했지만 속도 증가 (특히 대형 배열)는 그만한 가치가 있습니다. ‘AND’이진 연산에 대한 샘플 코드는 다음과 같습니다.

public static byte[] Bin_And(this byte[] ba, byte[] bt)
{
int lenbig = Math.Max(ba.Length, bt.Length);
int lensmall = Math.Min(ba.Length, bt.Length);
byte[] result = new byte[lenbig];
int ipar = 0;
object o = new object();
System.Action paction = delegate()
{
int actidx;
lock (o)
{
actidx = ipar++;
}
unsafe
{
fixed (byte* ptres = result, ptba = ba, ptbt = bt)
{
byte* pr = (byte*)ptres;
byte* pa = (byte*)ptba;
byte* pt = (byte*)ptbt;
pr += actidx; pa += actidx; pt += actidx;
while (pr < ptres + lensmall)
{
*pr = (byte)(*pt & *pa);
pr += paralleldegree; pa += paralleldegree; pt += paralleldegree;
}
}
}
};

System.Action[] actions = new Action[paralleldegree];
for (int i = 0; i < paralleldegree; i++)
{
actions[i] = paction;
}
Parallel.Invoke(actions);
return result;
}

이 함수에서 대리자 (AND 연산을 실행하는 코드 포함)가 선언 된 다음 동일한 대리자가 paralleldegree변수 (정적 생성자 내부에 할당 된 클래스 수준 변수) 와 동일한 횟수만큼 호출됩니다 ( 기사 끝에있는 전체 클래스 코드 참조) 현재 시스템에서 사용할 수있는 프로세서 수를 포함합니다. 물론 대리자의 다양한 인스턴스는 병렬 방식으로 호출됩니다.

대리자 내부에서 포인터는 입력 및 출력 바이트 배열에 선언 된 다음 while주기 내 에서 각주기의 다음 요소로 이동합니다. 함수의 핵심은 *pr = (*pt & *pa);입력 값 ( *pt 및 *pa) 사이에서 AND 이진 연산이 실행되어 결과를 출력 ( *pr) 에 넣는 간단한 라인 입니다.

이제 paralleldegree1 이면 (즉, 병렬 처리 없음)이 대리자는 이해하기 매우 쉽습니다.

그러나 예를 들어 paralleldegree4 라고 가정 해 보겠습니다 . 그러면 대리자의 네 인스턴스가 정확히 동일한 코드를 네 번 실행하여 실행 시간이 매우 느려진다는 문제가 발생합니다. 따라서이 아이디어 paralleldegree는 4 (또는 1보다 큰 숫자) 일 때 각 대리자가 입력 바이트 배열의 다른 바이트에서 시작 while하도록 한 다음주기 내 에서 모든주기에서 다음 4 바이트로 점프하는 것입니다. , 따라서 병렬로 실행되는 다른 대리자와 충돌없이 결과를 계산합니다.

이 경우 첫 번째 대리자는 바이트 0, 4, 8, 12 등을 계산합니다. 두 번째 대리자는 바이트 1, 5, 9, 13 등, 세 번째 2, 6, 10, 14 …, 네 번째 3, 7, 11, 15 …를 lock계산합니다. ipar각 호출에서 증가 되는 변수 (기능 수준) (4 인 경우 4 배 paralleldegree)와 actidx한 번만 할당되는 변수 (대리자 수준) 덕분에 델리게이트가 순차적 인 지점에서 시작하도록하는 목적 ( 모든 델리게이트에 대해) 그리고 모든 델리게이트에 대해 포인터의 ‘초기 오프셋’과 같은 역할을합니다 (줄에서 볼 수 있음 pr += actidx; pa += actidx; pt += actidx;).

병렬 처리를 포인터와 함께 사용하면 실행 속도가 매우 빨라졌습니다 (waw에 의해 실행 속도를 분석하기 위해 테스트 할 함수를 루프 안에 넣고 100 또는 1000 번 실행하여 System.Diagnostics.Stopwatch수업 시간 ; 그러나 바이트 포인터 ( byte*)를 uint포인터 ( uint*) 로 대체하면 더 개선 할 수 있습니다 . uint는보다 4 배 더 크므 byte로 모든주기가 4 배 짧아집니다. 음, 속도가 다시 증가했습니다. 네 번이 아니라 ‘단지’두 번. 그래서,이 마지막 개선은 제 생각에 그만한 가치가있었습니다.

using System;
using System.Threading.Tasks;

namespace MySpace
{
public static class BinOps
{
private const int bitsinbyte = 8;
private static readonly int paralleldegree;
private static readonly int uintsize;
private static readonly int bitsinuint;
static BinOps()
{
paralleldegree = Environment.ProcessorCount;
uintsize = sizeof(uint) / sizeof(byte); // really paranoid, uh ?
bitsinuint = uintsize * bitsinbyte;
}

public static byte[] Bin_And(this byte[] ba, byte[] bt)
{
int lenbig = Math.Max(ba.Length, bt.Length);
int lensmall = Math.Min(ba.Length, bt.Length);
byte[] result = new byte[lenbig];
int ipar = 0;
object o = new object();
System.Action paction = delegate()
{
int actidx;
lock (o)
{
actidx = ipar++;
}
unsafe
{
fixed (byte* ptres = result, ptba = ba, ptbt = bt)
{
uint* pr = (uint*)ptres;
uint* pa = (uint*)ptba;
uint* pt = (uint*)ptbt;
pr += actidx; pa += actidx; pt += actidx;
while (pr < ptres + lensmall)
{
*pr = (*pt & *pa);
pr += paralleldegree; pa += paralleldegree; pt += paralleldegree;
}
}
}
};
System.Action[] actions = new Action[paralleldegree];
for (int i = 0; i < paralleldegree; i++)
{
actions[i] = paction;
}
Parallel.Invoke(actions);
return result;
}

public static byte[] Bin_Or(this byte[] ba, byte[] bt)
{
int lenbig = Math.Max(ba.Length, bt.Length);
int lensmall = Math.Min(ba.Length, bt.Length);
byte[] result = new byte[lenbig];
int ipar = 0;
object o = new object();
System.Action paction = delegate()
{
int actidx;
lock (o)
{
actidx = ipar++;
}
unsafe
{
fixed (byte* ptres = result, ptba = ba, ptbt = bt)
{
uint* pr = (uint*)ptres;
uint* pa = (uint*)ptba;
uint* pt = (uint*)ptbt;
pr += actidx; pa += actidx; pt += actidx;
while (pr < ptres + lensmall)
{
*pr = (*pt | *pa);
pr += paralleldegree; pa += paralleldegree; pt += paralleldegree;
}
uint* pl = ba.Length > bt.Length ? pa : pt;
while (pr < ptres + lenbig)
{
*pr = *pl;
pr += paralleldegree; pl += paralleldegree;
}
}
}
};
System.Action[] actions = new Action[paralleldegree];
for (int i = 0; i < paralleldegree; i++)
{
actions[i] = paction;
}
Parallel.Invoke(actions);

return result;
}

public static byte[] Bin_Xor(this byte[] ba, byte[] bt)
{
int lenbig = Math.Max(ba.Length, bt.Length);
int lensmall = Math.Min(ba.Length, bt.Length);
byte[] result = new byte[lenbig];
int ipar = 0;
object o = new object();
System.Action paction = delegate()
{
int actidx;
lock (o)
{
actidx = ipar++;
}
unsafe
{
fixed (byte* ptres = result, ptba = ba, ptbt = bt)
{
uint* pr = ((uint*)ptres) + actidx;
uint* pa = ((uint*)ptba) + actidx;
uint* pt = ((uint*)ptbt) + actidx;
while (pr < ptres + lensmall)
{
*pr = (*pt ^ *pa);
pr += paralleldegree; pa += paralleldegree; pt += paralleldegree;
}
uint* pl = ba.Length > bt.Length ? pa : pt;
while (pr < ptres + lenbig)
{
*pr = *pl;
pr += paralleldegree; pl += paralleldegree;
}
}
}
};
System.Action[] actions = new Action[paralleldegree];
for (int i = 0; i < paralleldegree; i++)
{
actions[i] = paction;
}
Parallel.Invoke(actions);

return result;
}

public static byte[] Bin_Not(this byte[] ba)
{
int len = ba.Length;
byte[] result = new byte[len];

int ipar = 0;
object o = new object();
System.Action paction = delegate()
{
int actidx;
lock (o)
{
actidx = ipar++;
}
unsafe
{
fixed (byte* ptres = result, ptba = ba)
{
uint* pr = (uint*)ptres;
uint* pa = (uint*)ptba;
pr += actidx; pa += actidx;
while (pr < ptres + len)
{
*pr = ~(*pa);
pr += paralleldegree; pa += paralleldegree;
}
}
}
};
System.Action[] actions = new Action[paralleldegree];
for (int i = 0; i < paralleldegree; i++)
{
actions[i] = paction;
}
Parallel.Invoke(actions);
return result;
}

public static byte[] Bin_ShiftLeft(this byte[] ba, int bits)
{
int ipar = 0;
object o = new object();

int len = ba.Length;
if (bits >= len * bitsinbyte) return new byte[len];
int shiftbits = bits % bitsinuint;
int shiftuints = bits / bitsinuint;
byte[] result = new byte[len];

if (len > 1)
{
// first uint is shifted without carry from previous byte (previous byte does not exist)
unsafe
{
fixed (byte* fpba = ba, fpres = result)
{
uint* pres = (uint*)fpres + shiftuints;
uint* pba = (uint*)fpba;
*pres = *pba << shiftbits;
}
}
System.Action paction = delegate()
{
int actidx;
lock (o)
{
actidx = ipar++;
}
unsafe
{
fixed (byte* fpba = ba, fpres = result)
{
// pointer to results; shift the bytes in the result
// (i.e. move left the pointer to the result)
uint* pres = (uint*)fpres + shiftuints + actidx + 1;
// pointer to original data, second byte
uint* pba1 = (uint*)fpba + actidx + 1;
if (shiftbits == 0)
{
while (pres < fpres + len)
{
*pres = *pba1;
pres += paralleldegree; pba1 += paralleldegree;
}
}
else
{
// pointer to original data, first byte
uint* pba2 = (uint*)fpba + actidx;
while (pres < fpres + len)
{
*pres = *pba2 >> (bitsinuint - shiftbits) | *pba1 << shiftbits;
pres += paralleldegree; pba1 += paralleldegree; pba2 += paralleldegree;
}
}
}
};

};
System.Action[] actions = new Action[paralleldegree];
for (int i = 0; i < paralleldegree; i++)
{
actions[i] = paction;
}
Parallel.Invoke(actions);
}

return result;
}

public static byte[] Bin_ShiftRight(this byte[] ba, int bits)
{
int ipar = 0;
object o = new object();
int len = ba.Length;
if (bits >= len * bitsinbyte) return new byte[len];
int ulen = len / uintsize + 1 - (uintsize - (len % uintsize)) / uintsize;
int shiftbits = bits % bitsinuint;
int shiftuints = bits / bitsinuint;
byte[] result = new byte[len];

if (len > 1)
{
unsafe
{
fixed (byte* fpba = ba, fpres = result)
{
uint* pres = (uint*)fpres + ulen - shiftuints - 1;
uint* pba = (uint*)fpba + ulen - 1;
*pres = *pba >> shiftbits;
}
}
System.Action paction = delegate()
{
int actidx;
lock (o)
{
actidx = ipar++;
}
unsafe
{
fixed (byte* fpba = ba, fpres = result)
{
// pointer to results; shift the bytes in the result
// (i.e. move left the pointer to the result)
uint* pres = (uint*)fpres + actidx;
// pointer to original data, first useful byte
uint* pba1 = (uint*)fpba + shiftuints + actidx;
if (shiftbits == 0)
{
while (pres < ((uint*)fpres) + ulen - shiftuints - 1)
{
*pres = *pba1;
// increment pointers to next position
pres += paralleldegree; pba1 += paralleldegree;
}
}
else
{
// pointer to original data, second useful byte
uint* pba2 = (uint*)fpba + shiftuints + actidx + 1;
while (pres < ((uint*)fpres) + ulen - shiftuints - 1)
{
// Core shift operation
*pres = (*pba1 >> shiftbits | *pba2 << (bitsinuint - shiftbits));
// increment pointers to next position
pres += paralleldegree; pba1 += paralleldegree; pba2 += paralleldegree;
}
}
}
};
};
System.Action[] actions = new Action[paralleldegree];
for (int i = 0; i < paralleldegree; i++)
{
actions[i] = paction;
}
Parallel.Invoke(actions);
}
return result;
}
}
}