흑백과 디지털

   개인적으로 간단한 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   에서 테스트 코드를 확인 할 수 있다. 

Rust 에서 nightly version 에서는 benchmark 를 기본으로 제공한다. 이게 언제 stable version 에 추가 될지는 모르겠지만 rust stable 버전에서는 다음 2가지 library 가 cargo bench 명령어를 지원한다.

https://github.com/bheisler/criterion.rs

와 
https://github.com/bluss/bencher

를 이용한 방법이 있다.

외부적으로 구현하는 방법은 매우 유사해 보인다. 

criterion.rs 는 다양한 기능을 제공하는데 비해 좀 무거워보인다. 간단히 속도 측정만을 하기에는 bencher 가 간단해 보인다. 어차피 둘다 [dev-dependencies] 에 추가하면 되기 때문에 실제 프로그램 release 시에는 해당 라이브러리를 포함하지 않는다. 

  현재 bufchr(https://github.com/yiunsr/bufchr) 이라는 rust 라이브러리를 만들고 있다. 이 라이브러리에서 benchmark 를 적용하려고 bencher 를 사용하고 있다. toml 은 다음과 같이 구성한다.

=====  https://github.com/yiunsr/bufchr/blob/0b8b02ba4a5b95b0fcdf8796e8cbcfdb18ba367a/Cargo.toml ====
[package]
name = "bufchr"
version = "0.1.0"
edition = "2018"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
[lib]
name = "bufchr"
path = "src/lib.rs"

[[bin]]
name = "bufchrbin"
path = "src/bin.rs"

[[bench]]
name = "bufchrbench"
harness = false
path = "benches/bench.rs"

[dev-dependencies]
bencher = "0.1.5"

==================
[[bench]] 의 path는 실제 benchmark 코드가 들어있는 위치이다. 이 코드는 각자 상황에 맞게 수정이 필요하다. 
( 디렉토리 구성은 https://github.com/yiunsr/bufchr/tree/0b8b02ba4a5b95b0fcdf8796e8cbcfdb18ba367a 을 참고하기 바란다. )

실제 benchmark 하는 코드는 아래와 같다. 
======= benches/bench.rs =======
#[macro_use]
extern crate bencher;

use bencher::Bencher;

use bufchr;

static CSV_HAYSTACK: &'static [u8] = include_bytes!("../data/gdp.csv");

fn read_gdp_csv(bench: &mut Bencher) {
    bench.iter(|| {
        let needle = b',';
        let mut bf = bufchr::Bufchr::new(CSV_HAYSTACK, needle);
        loop {
            let n = bf.next();
            if n == None{break;}
        }
    });
}

fn read_gdp_csv2(bench: &mut Bencher) {
    bench.iter(|| {
        let n1 = b',';
        let n2 = b'"';
        let mut bf = bufchr::Bufchr2::new(CSV_HAYSTACK, n1, n2);
        loop {
            let n = bf.next();
            if n == None{break;}
        }
    });
}

fn read_gdp_csv3(bench: &mut Bencher) {
    bench.iter(|| {
        let n1 = b',';
        let n2 = b'"';
        let n3 = b'\n';
        let mut bf = bufchr::Bufchr3::new(CSV_HAYSTACK, n1, n2, n3);
        loop {
            let n = bf.next();
            if n == None{break;}
        }
    });
}



benchmark_group!(benches, read_gdp_csv, read_gdp_csv2, read_gdp_csv3);
benchmark_main!(benches);
========================================

cargo bench --benches   를 통해 벤치마크를 실행할 수 있다.
실행시 아래와 같은 결과를 보여준다.
========
...................
running 3 tests
test read_gdp_csv  ... bench:       6,416 ns/iter (+/- 1,404)
test read_gdp_csv2 ... bench:      15,679 ns/iter (+/- 3,932)
test read_gdp_csv3 ... bench:      18,024 ns/iter (+/- 4,459)

test result: ok. 0 passed; 0 failed; 0 ignored; 3 measured
=============
6,416 ns/iter  이런 것의 의미는 함수 실행시간이 6416 나노 초 => 6.416 밀리 초 => 0.00614초 동안 실행했다는 의미이다. 

회사에서 외주 퍼블리시 한 HTML 코드를 보다보니, 화가 났다. 내 기준에으로 코드가 너무 엉망이었다. 수정이 쉽도록 CSS 를 통해서 grid 를 사용할 수 있도록 해주어야 하는데, 그렇게 되어 있지 않았다. (처음부터 이것을 분명히 짚고 넘어갔지만 가격때문에 강하게 주장할 수 없었다. 사실 이런 것을 원하면 전문 업체에게 요청하는게 맞다. )
 CSS를 잘 이용하면 javascript 없이 구현 가능한 코드인데 이 코드를 js 로 구현했다. checkbox 와 radio 형식의 버튼을 자바스크립트 onclick 이벤트시 class 를 추가하는 방식으로 구현하고 있었다. 이 코드는 아무리봐도 css checkbox 를 이용하면 될 것 같아서 구현해 보았다. 

https://jsfiddle.net/nahanmil/bkqj7x4c/11/

IE 11 에서도 정상적으로 동작한다.