Fast string to integer#

문제#

보통의 경우 10진수 또는 16진수의 string을 integer로 변환하기 위하여 strtoul( ) 를 사용합니다.
하지만, strtoul( )를 매우 많이 반복하는 경우 처리 속도가 느립니다.
다음 코드는 strtoul( )을 300,000,000회 반복하였으며, 약 5초가 소요되었습니다.

#include <iostream>
#include <chrono>

int main()
{
	const char* hexString = "19AF";   // 0x19AF = 6575

	auto start = std::chrono::high_resolution_clock::now();

	for (int i = 0; i < 300000000; i++)
	{
		int value = strtoul(hexString, NULL, 16);
	}

	auto end = std::chrono::high_resolution_clock::now();
	std::chrono::duration<double, std::milli> elapsed = end - start;
	std::cout << "time: " << elapsed.count() << " ms" << std::endl;

    return 0;
}

개선#

LUT(LookUp Table)를 사용하면 strtoul( ) 보다 빠르게 처리할 수 있습니다.
10진수, 16진수의 string에 포함되는 문자는 다음과 같습니다.

‘0’~‘9’
‘a’~‘f’
‘A’~‘F’

따라서, 이에 대한 integer값을 가지는 LUT를 다음 코드의 initLut( ) 안에 미리 만들어 놓습니다.
그리고 각 자릿수에 LUT 적용하여 문자에 해당하는 정수값을 확보하고, Shift 연산자를 사용하여 string을 integer로 변환하면 속도가 빨라집니다.
다음 코드는 약 0.7초가 소요 되었습니다.

strtoul( )

#include <iostream>
#include <chrono>

char LUT['f'+1];   // 'f'=102

void initLut()
{
    LUT['0'] = 0x0;
    LUT['1'] = 0x1;
    LUT['2'] = 0x2;
    LUT['3'] = 0x3;
    LUT['4'] = 0x4;
    LUT['5'] = 0x5;
    LUT['6'] = 0x6;
    LUT['7'] = 0x7;
    LUT['8'] = 0x8;
    LUT['9'] = 0x9;

    LUT['a'] = 0xa;
    LUT['b'] = 0xb;
    LUT['c'] = 0xc;
    LUT['d'] = 0xd;
    LUT['e'] = 0xe;
    LUT['f'] = 0xf;

    LUT['A'] = 0xa;
    LUT['B'] = 0xb;
    LUT['C'] = 0xc;
    LUT['D'] = 0xd;
    LUT['E'] = 0xe;
    LUT['F'] = 0xf;
}

int main()
{
    initLut();

    const char* hexString = "19AF";   // 0x19AF = 6575

    auto start = std::chrono::high_resolution_clock::now();

    for (int i = 0; i < 300000000; i++)
    {
        int value = 
            (LUT[hexString[0]] << 12) | 
            (LUT[hexString[1]] << 8) | 
            (LUT[hexString[2]] << 4) | 
            LUT[hexString[3]];
    }

    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> elapsed = end - start;
    std::cout << "time: " << elapsed.count() << " ms" << std::endl;

    return 0;
}

strtoul( )은 5초, LUT를 사용하는 경우 0.7초이므로, 약 1/7수준으로 처리 시간이 단축 되었습니다.