개인적으로 간단한 spreadsheet 기능을 가진 lightsheet_rust(https://github.com/yiunsr/lightsheet_rust ) 라는 프로그램을 개발중이다. 이 프로그램을 csv 파일을 열어서 sqlite3 로 저장해서 기본적인 sort, 수정, 추가, 간단한 수식을 제공하려고 한다. 이 프로그램 시작이 csv 파일을 열어서 sqlite3 DB에 저장하는 것이라보니 오래전 부터 https://yiunsr.tistory.com/821 이런 식으로 sqlite3 를 빠르게 insert 하는 것을 찾았다. 그러다 보니 이제는 rust 를 사용한다. 해당 option 외에 더 빠르게 하는 sqlite3 옵션은 없는 것 같다. 이제는 csv 파일을 빠르게 파싱하는 방법을 찾고 있다. 그러다 보니 simd (https://ko.wikipedia.org/wiki/SIMD) 를 이용하는 방법을 찾고 있다.
우선 빠른 csv 파서를 만들기 위해 필요한 것은 빠르게 field_separate(일반적으로 콤마, tsv 일 경우 탭), row_separate( \n, \r, \r\n) 그리고 특수한 문자 double quotes (큰따옴표 ") 를 빠르게 찾는게 필요하다. (큰따옴표가 의미 있는 이유는 a11, "b,11", c11 이라는 csv 파일 내용이 있으면 2번째 항목은 b,11 이다. 큰따옴표가 column 중간에 들어가는 콤마를 seperator 가 아닌 문자로 인식하게 해준다.) 일반적으로 파싱을 구현할 때 Tokenizer 로 token 을 분리할 때 문자 하나하나를 검사해서 구현한다. 그러나 csv 의 경우 특별한 의미를 가지는 위의 3가지 문자에 대해서만 빠르게 찾아서 Tokenizer 를 구현하게 된다면 빠르게 구현할 수 있다. 글로 설명하다보니 이해하기 어려워서 코드로 설명하면
1) 문자하나하나 csv 를 파싱하는 방법
test_csv = "a1,b1,c1\na2,b2,c2"
for idx in range(len(test_csv)):
ch = test_csv[idx]
if ch == '"':
quote 일 때 해야할 일
elif ch == ",":
comma 일 때 해야할 일
elif ch == "\n":
line feed 일 때 해야할 일
else:
pass
# 아무 일도 안하고 위에서 많은 비교만 한다.
2) 특정 문자에 대해서 빠르게 이동 가능하다면
test_csv = "a1,b1,c1\na2,b2,c2"
for idx in find_3chars(test_csv, ",", '"',"\n"):
ch = test_csv[idx]
if ch == '"':
quote 일 때 해야할 일
elif ch == ",":
comma 일 때 해야할 일
elif ch == "\n":
line feed 일 때 해야할 일
else:
pass
# 여기가 불러질 일이 없다.find_3chars 는 test_csv 에서 csv 를 파싱하는데 의미가 있는 문자 3가지( ",", '"',"\n") 의 index (여기서는 3,6, 9 ...) 를 찾아주는 함수이다.
일반적으로 find_3chars 이런 함수는 일일이 문자를 찾는 것이라 2)가 1)과 같으면 같았지 더 빠를수가 없다. 그런데
intel simd 명령어중 avx2 에서만 동작하는 명령어를 사용하면 빠르게 find_3chars 를 구현 할 수 있다. simd 는 single instruction multiple data 의 약자다.
이 simd 명령어가 _mm256_cmpeq_epi8 (https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html#text=_mm256_cmpeq_epi8&ig_expand=909 ) 이다. 이 명령어는 두 개의 256bit(1byte 32개) 피 연산자를 인자로 받아서 각 byte별로 결과를 256bit(32byte) 로 저장한다.
a0 a1 a2 .... a31 (1byte 32개, 비교 대상으로 위에서의 a1,b1,c1\na2,b2,c2 )
b0 b1 b2 ... b31 (1byte 32개, ,,,,, 가 32 개 )
c0 c1 c2 ... c31 (1byte 32개)
aN 과 bN 을 비교해서 같으면 cN은 0, 다르면 cN은 1 로 설정된다. 이 32개의 비교 연산이 하나의 instruction 으로 동작한다. 이 비교 연산을 하기 위해서는 b0 b1 ... b31 가 같은 값으로 32번 들어가야 한다.
a0 a1 a2 ... a31 내 "," 문자를 찾는다고 가정하면 b0 b1 b2 .... b31 모두 동일한 "," 가 들어가야 한다. 이 값을 넣는 것도 하나의 simd 명령어로 처리 가능하다. _mm256_set1_epi8 라는 명렁어는 피연산자 one byte 를 받아서 32byte 에 동일하게 피연산자를 복사해서 넣는 처리를 해준다. 그리고 _mm256_cmpeq_epi8 를 통해 a0 ... a31 에 "," 문자가 있으면 c0 ... c31 중 해당하는 byte가 -1(0xFF)가 되고 아니면 0이 된다. 이 결과도 32byte가 아니라 결과를 bit 로 저장할 수 있다. _mm256_movemask_epi8 를 사용하면 32byte 의 결과를 다시 4byte(32bit) int 로 변경할 수 있다. ( _mm256_movemask_epi8 명령어는 msb(most significant bit) 가 있으면 1로 bit를 set 하고 없으면 0으로 bit 를 clear 한다. ). 이 결과를 대문자 C (32bit integer 이다. ) 라고 하자. 이렇게 하면 a0 .... a31 에서 콤마(,) 기호가 있으면 이 bit에 대응되는 C 에 bit가 1로 된다. 예를 들어 a1,b1,c12 => 2진수로 그 결과가 100100100 로 표시된다.
이렇게 \n 에 대해서도 찾고 '"' (큰따옴표)에 대해서도 찾아서 각각의 결과를 bitwise or 32byte 의 문자열에 대해 csv 파싱에 필요한 요소들의 위치를 한 번에 찾을 수 있다.
이렇게 찾은 방법이 simd 를 이용하기는 하지만 준비작업도 있고, 그 결과를 bit 로 된것을 분리해서 다시 확인하는 과정도 필요한다. 그래서 구현이 잘못되면 글자 하나하나를 비교하는 것보다 늦을 수도 있는데, 실제로 테스트 해보면 simd 를 이용한 방법이 확실히 더 빠르다. simd 를 이용한 방법이 뭔지 모르겠지만 메모리 cache 를 이용하면서 더 최적화되는 느낌이다.
내 경우 rust 를 이용해서 문자열에서 글자 3가지를 찾을 수 있는 라이브러리를 만들었다. https://github.com/yiunsr/bufchr 이다. 이 라이브러리는 https://github.com/BurntSushi/memchr 라는 라이브러리를
개선한 것이다. 기존의 memchr 이라는 라이브러리는 이미 계산된 32개의 결과를 모두 이용하지 않는다. 그냥 특정지점에서 부터 32byte 내에 매칭되는 문자가 있는지 확인하는 방식이다. 보통 찾는 곳은 haystack 이고 찾는 대상을 needle 이라고 표현한다. haystack 은 커다른 건초더미를 의미한다. 큰 건초더미에서 바늘을 찾는 것을 생각하면 된다. 기존 memchr 은 needle 이 적게 있을 때 빠른 속도를 낸다. 내가 만든 bufchr 은 바늘이 매우 많을 때 빠른 속도를 낸다. 특히 32byte 내에 needle 이 많으면 속도가 빠르게 된다. csv 의 경우 needle 이 32byte 내에 여러개 있을 가능성이 크기 때문에 내 라이브러리가 더 적합하다.
그리고 이 bufchr 를 이용해서 csv 파서를 만들고 있다. https://github.com/yiunsr/ss-csv 라는 rust 에서 csv 를 파서하는 라이브러리를 만들고 있다. 여기에는 cow string (clone on write 내용이 수정될 때에만 clone 됨)도 이용하고 있다. 따라서 기존https://github.com/BurntSushi/rust-csv 보다 더 빠른 속도를 보인다.
테스트 해 보니 기존 것 보다 3분의 1 시간만에 csv 파싱을 끝내고 있다. 물론 csv 마다 다를 수 있다. 그리고 제약사항이 좀더 많다.
https://gist.github.com/yiunsr/c0b0768d9e3938461214ec073f053b44 에서 테스트 코드를 확인 할 수 있다.