CRC 계산 속도 비교: 제조사 라이브러리보다 룩업 테이블이 더 빠를까?

아무리 잘 최적화된 비트와이즈 CRC 계산 알고리즘이라도, 룩업 테이블 방식의 처리 속도를 따라잡기는 쉽지 않다. 심지어 제조사의 어셈블리 기반 알고리즘도 초보자의 LUT 기반 코드보다 속도가 느리다. ATmega2560을 통해 실제 속도를 비교해 보았다.

CRC 연산의 속도가 중요한 이유

CRC(순환 중복 검사, Cyclic Redundancy Check)는 데이터 저장 및 전송 과정에서 발생하는 오류를 감지하는 대표적인 방법이다. 데이터를 0과 1로 이루어진 이진수 비트열로 보고, 미리 정해진 식을 이용해 계산한 결과인 CRC 값을 송신 측과 수신 측에서 비교해, 두 값이 동일하면 데이터가 정상적으로 이동했다고 판단한다.

문제는 CRC 연산 작업이 데이터를 이동하거나 확인하는 거의 모든 과정에 반복적으로 실행된다는 점이다. 만약 100회의 통신이 이루어진다면 송신과 수신을 합해 200회의 CRC 연산이 필요하며, 1회 연산에 필요한 연산 시간은 검증해야 하는 데이터의 양에 비례해 늘어나게 된다. 때문에 CRC 연산 속도는 전체 시스템의 동작 속도에 영향을 미치게 된다.

이러한 이유로 시스템이 허용하는 범위 안에서 CRC 연산에 소모되는 시간을 줄이는 것은 상당히 중요하다. 특히 처리해야 할 데이터가 많거나, 임베디드 환경처럼 성능이 제한된 환경에서 CRC를 계산해야 하는 경우라면 CRC 계산 속도가 시스템 전체 성능에 적지 않은 영향을 주게 된다.

비트 단위 연산과 룩업 테이블

CRC를 계산하는 방법은 크게 두 가지 방법으로 나눌 수 있다.

비트 단위 연산(Bitwise)

CRC의 원리를 그대로 구현해 입력 데이터를 비트 단위로 한 비트씩 이동시키면서 연산을 수행한다.

본 글에서는 비트와이즈 방식이라 부르겠다.

테이블 조회 방식(LUT, Lookup Table)

들어올 수 있는 모든 데이터에 대해 미리 CRC 연산을 한 표를 만들어 테이블에서 결과 값을 바로 꺼내와 사용한다.

본 글에서는 룩업 테이블 방식이라 부르겠다.

일반적으로 돈을 쓰면(즉, 메모리를 사용하면) 처리 속도는 증가하고, 돈을 아끼면(즉, 메모리를 사용하지 않으면) 처리 속도는 느려진다. 비트와이즈 방식과 룩업 테이블 방식중 룩업 테이블 방식의 연산 속도가 비트와이즈 방식보다 빠른 것은 쉽게 유추할 수 있다.

제조사의 최적화 라이브러리는 과연 더 빠를까?

그동안 몇 번에 걸친 실험을 통해, 메모리가 충분하다면 계산하는 것보다 읽어 오는 게 훨씬 낫다는 사실은 이미 알고 있었다. 그러던 와중, 마이크로칩 스튜디오(Microchip Studio)의 기본 제공 라이브러리를 살펴보다가 마이크로칩에서 공식 제공하는 CRC-16 계산 라이브러리가 있는 것을 보게되었다.

그 순간, 본 필자의 머릿속에 한 가지 의문과 호기심이 떠올랐다.

하드웨어를 가장 잘 아는 제조사가 직접 만든 라이브러리라면, 최적화 끝판왕이겠지?
내가 만든 허접한 룩업 테이블 방식보다 더 빠를 수도 있지 않을까?

백문이 불여일견, 궁금한 것은 직접 확인해 보면 된다. 실제 실험을 통해 다음의 세 가지 방식의 동작 속도를 비교해 보기로 했다.

1. 필자가 직접 작성한 허접한 룩업 테이블 방식의 CRC-16 계산기
2. 필자가 직접 작성한 허접한 비트와이즈 방식의 CRC-16 계산기
3. 마이크로칩 제공 CRC-16 계산 라이브러리

시험 준비

정확한 속도 비교를 위해 오실로스코프를 이용해 연산의 시작 타이밍과 종료 타이밍을 측정하기로 했다.

동일한 입력 문자열을 주고 ATmega2560 16MHz 환경에서 디지털 출력 포트 2개를 골라, 코드가 시작되는 순간에 High로 올리고, 종료되는 순간에 Low로 내려주면 연산에 걸린 실제 시간을 측정할 수 있을 것이다.

직접 만든 CRC-16 계산기

본 필자가 CRC에 대해 공부하며 작성한 기본적인 비트와이즈 방식의 계산기이다. 손으로 한 비트씩 이동해 가며 계산하는 방법을 그대로 코드화 시킨 것으로, 루프 안에서 매 비트마다 조건문 검사, 시프트 연산, XOR 연산을 진행한다.

uint16_t CRC16_Compute(uint8_t *datastream, uint16_t numberofbyte, uint16_t poly, uint16_t initval)
{
	for (uint16_t i=0; i<numberofbyte+2; i++)
	{
		for (uint8_t j=8; j>0; j--)
		{
			if (initval & 0x8000)
			{
				initval = initval << 1;
				initval = (((i>=numberofbyte) ? 0 : datastream[i]) & (1<<(j-1))) ? (initval | 1) : initval;
				initval = initval ^ poly;
			}
			else
			{
				initval = initval << 1;
				initval = (((i>=numberofbyte) ? 0 : datastream[i]) & (1<<(j-1))) ? (initval | 1) : initval;
			}
		}
	}
	return initval;
}

마이크로칩 제공 CRC-16 라이브러리

마이크로칩 스튜디오(AVR 툴체인) 에 포함된 라이브러리 코드이다. C언어가 아닌 인라인 어셈블리로 작성되어 있어, 레지스터를 직접 건드리는 8비트 MCU 아키텍처 최적화의 끝을 보여주는 형태다. (2002년부터 얼마나 많은 개선이 있었을까!)

Copyright (c) 2002, 2003, 2004  Marek Michalkiewicz
Copyright (c) 2005, 2007 Joerg Wunsch
Copyright (c) 2013 Dave Hylands
Copyright (c) 2013 Frederic Nadeau
All rights reserved.
_crc_xmodem_update(uint16_t __crc, uint8_t __data)
{
    uint16_t __ret;             /* %B0:%A0 (alias for __crc) */
    uint8_t __tmp1;             /* %1 */
    uint8_t __tmp2;             /* %2 */
                                /* %3  __data */

    __asm__ __volatile__ (
        "eor    %B0,%3"          "\n\t" /* crc.hi ^ data */
        "mov    __tmp_reg__,%B0" "\n\t"
        "swap   __tmp_reg__"     "\n\t" /* swap(crc.hi ^ data) */

        /* Calculate the ret.lo of the CRC. */
        "mov    %1,__tmp_reg__"  "\n\t"
        "andi   %1,0x0f"         "\n\t"
        "eor    %1,%B0"          "\n\t"
        "mov    %2,%B0"          "\n\t"
        "eor    %2,__tmp_reg__"  "\n\t"
        "lsl    %2"              "\n\t"
        "andi   %2,0xe0"         "\n\t"
        "eor    %1,%2"           "\n\t" /* __tmp1 is now ret.lo. */

        /* Calculate the ret.hi of the CRC. */
        "mov    %2,__tmp_reg__"  "\n\t"
        "eor    %2,%B0"          "\n\t"
        "andi   %2,0xf0"         "\n\t"
        "lsr    %2"              "\n\t"
        "mov    __tmp_reg__,%B0" "\n\t"
        "lsl    __tmp_reg__"     "\n\t"
        "rol    %2"              "\n\t"
        "lsr    %B0"             "\n\t"
        "lsr    %B0"             "\n\t"
        "lsr    %B0"             "\n\t"
        "andi   %B0,0x1f"        "\n\t"
        "eor    %B0,%2"          "\n\t"
        "eor    %B0,%A0"         "\n\t" /* ret.hi is now ready. */
        "mov    %A0,%1"          "\n\t" /* ret.lo is now ready. */
        : "=d" (__ret), "=d" (__tmp1), "=d" (__tmp2)
        : "r" (__data), "0" (__crc)
        : "r0"
    );
    return __ret;
}

직접 만든 테이블 기반 CRC-16 계산기

본 필자가 만든 룩업 테이블 방식의 계산기로, 복잡한 비트 연산 없이 입력된 바이트 데이터를 인덱스 삼아 배열에서 미리 계산된 값을 즉시 꺼내오는 구조이다.

uint16_t CRC16_get(uint8_t *datastream, uint16_t numberofbyte, uint16_t *crctbl)
{
	uint16_t rtn=0;
	for (uint16_t i=0; i<numberofbyte; i++)
		rtn = ((rtn << 8) ^ crctbl[ ((rtn>>8) ^ (0xff & datastream[i])) ]);
	return rtn;
}

시험 결과

{0x10, 0x20, 0x30, 0x40, 0x50}이라는 동일한 5바이트 데이터를 입력으로 사용한 뒤, CRC-16 계산을 완료하는 데 걸리는 시간을 오실로스코프로 측정했다.

결론

가장 놀란 것은, 필자가 직접 만든 허접한 룩업 테이블 방식이 어셈블리어까지 동원된 제조사 라이브러리보다 더 빠르게 동작한 것이었다.

물론 직접 만든 비트와이즈 방식은 예상대로 가장 느렸다. 동일한 5바이트 데이터를 처리하는 데 193.122μs가 걸렸고, 바이트당 처리 시간은 약 38.6μs였다. 반면 테이블 기반 방식은 전체 계산에 11.623μs, 바이트당 약 2.3μs만 소요되었다. 단순 비교하면 약 16배 이상의 차이가 난다.

마이크로칩의 CRC-16 라이브러리는 비트 단위 연산을 수행하면서도 바이트당 약 3.1μs라는 빠른 속도를 보여주었다. 직접 만든 비트와이즈 방식과 비교하면 압도적으로 빠른 결과이다. 또한 직접 연산임에도 불구하고 룩업 테이블 방식과 근소한 차이밖에 나지 않는다. 역시 웬만한 기능은, 잘 뒤져서 나보다 더 똑똑한 사람들이 잘 만들어 놓은 라이브러리를 가져다 쓰는 게 최선의 방법일 것이다.

하지만 최종 승자는 결국 룩업 테이블 방식이었다. 테이블 기반 방식은 마이크로칩 라이브러리보다도 더 짧은 시간 안에 계산을 끝냈다. 하드웨어를 가장 잘 아는 제조사가 어셈블리어로 다듬어 만든 최적화 코드조차, 미리 계산해 둔 값을 메모리에서 바로 읽어 오는 방식의 허접한 코드의 연산 속도를 넘어서지는 못한 것이다.

알고리즘을 잘 짜놨다고 해도, 메모리를 써 가며 미리 계산한 값들을 참조해 가며 계산하는게 더 빠르다. 장착된 메모리는 최대한 사용해 주는 것이 성능 향상에 유리하다. 한 번이라도 연산을 줄이면 고스란히 동작속도로 돌아오게 된다. 메모리의 여유가 없다면 어쩔 수 없겠지만, 있으면 최대한 써먹어 줘야 한다.

CRC 계산을 사용하는 시리얼 통신을 구현한다고 가정했을 때, 짧은 길이의 데이터를 처리한다면 별 차이가 없게 느껴질 수 있다. 하지만 데이터 길이가 수백 바이트, 수천 바이트로 늘어나면 이야기가 달라진다. 바이트당 몇 마이크로초의 차이는 전체 처리 시간에서 상당히 큰 차이로 누적된다.

실제로 본 필자가 만들었던 방송신호 자동절체 제어기는 상태를 한 번 확인하는 데만 8000Byte 정도가 필요했다. 바이트당 20μs 차이라면 무려 0.16초라는 엄청난 시간이다!

좋은 라이브러리라는 것은 연산을 최소화 하고, 같은 연산을 하더라도 걸리는 시간을 최소화 하는 것이다. 결국 수학적 능력이 필요하다. 식을 간소화 해서 정리하는 방법을 아는것은 좋은 알고리즘을 만드는데에 필수적이다. 결국, 이놈의 수학은 끝까지 내 발목을 잡아댄다.

FAQ

제조사 라이브러리보다 직접 만든 룩업 테이블 방식이 빠를 수 있나?

그렇다. 제조사 라이브러리는 특정 MCU 아키텍처에 맞춰 잘 최적화되어 있을 수 있지만, 룩업 테이블 방식은 애초에 반복 연산 자체를 줄이는 방식이다. 따라서 메모리 접근 속도가 충분히 빠르고 테이블을 저장할 공간이 있다면, 직접 만든 룩업 테이블 방식이 제조사 라이브러리보다 빠르게 동작할 수도 있다.

비트와이즈 방식과 룩업 테이블 방식의 차이는?

비트와이즈 방식은 입력 데이터를 한 비트씩 이동시키며 CRC 계산식을 직접 수행하는 방식이다. 반면 룩업 테이블 방식은 미리 계산해 둔 중간 CRC 값을 표에서 읽어 와 계산량을 줄이는 방식이다. 일반적으로 룩업 테이블 방식이 더 많은 메모리를 사용하지만 계산 속도는 더 빠르다.

CRC-16 룩업 테이블의 메모리 용량은?

일반적인 CRC-16 룩업 테이블은 256개의 16비트 값을 저장하는 방식으로 구성되는 경우가 많다. 이 경우 약 512바이트 정도의 메모리가 필요하다.

0.16초는 짧은 시간 아닌가?

16MHz로 동작하는 ATmega2560를 기준으로 0.16초는 약 256만 클럭에 해당하고, 이는 if문을 128만 번 실행할 수 있는 시간이다. 사람이 느끼기에는 0.16초가 매우 짧은 시간이지만, 임베디드 시스템에서는 결코 무시할 수 있는 시간이 아니다.