regex에 대하여

regex는 아주 자주 사용된다

regex, 정규 표현식은 개발을 하다보면 흔히 사용되는 것들이다. 복잡한 파싱 로직을 작성하지 않고도 쉽게 텍스트 관련 로직을 처리할 수 있다. 물론 우리는 다들 복잡한 정규식을 이해하거나, 작성할 일은 자주 없겠지만 그래도 단순한 형식의 정규식은 매우 유용하다. 내가 본 몇가지 케이스는,, 특정 문자열을 포함하고 있는지 확인하는 contains도 있었고, 특정 prefix, suffix가 있는 문자열을 찾는 것도 있었다. 혹은 전화번호, 카드번호로 의심되는 문자열을 찾는 것도 있었는데, 정규식이 엄청나게 느리다는걸 알게된 계기였다.

정규색 객체의 생성 비용은 비교적 비싼 편이다. 나는 처음에 단순한 문자열을 담고있는 객체라고 생각했었지만, 실제로는 그렇지 않다는걸 프로파일러를 통해 알 수 있었다. 정규식을 함수가 호출할때 매번 생성하는 것은 매우 비효율적이다. 종종 이러한 서비스의 코드를 보고 수정하거나 알려드리곤 했었다. 하지만 실제로 왜 이렇게 복잡하고, 느리고, 객체 생성 자체가 비싼지 생각해보지는 않았었다. 그리고 그게 나에게 엄청 중요한 문제는 아니었다.

정규식의 속도는 문제가 된다. 적어도 나에게는 문제가 되었다. 개인정보로 의심되는 문자열이 있는지 확인해야하는 프로그램을 작성해야하는 일이 주어졌는데, 병목지점의 대부분이 regex 매칭을 처리하는 부분이었다. 수~수십 GB정도 되는 크기의 가변길이로 인코딩된 lz4 압축 파일이 6개정도 있었는데 이 파일을 전체 처리하는데 엄청난 시간이 걸렸다. 파일 갯수만큼 스레드를 만들어서 처리하더라도 regex는 CPU를 아주 많이 사용해서 스레드들이 전부 CPU 100%로 열심히 일하고 있었다.

6core를 전부 사용하면서 수십기가 정도 파일을 몇십분동안 처리하는게 나로서는 이해되지 않았다. 프로파일링을 해보아도, russ cox가 작성한 re2로 바꾸어도 그렇게까지 성능 개선이 없었다. 실험적, 경험적인 최적화는 이제 거의 한계였다. 스레드를 더 늘리면 해소야 되겠지만, 결국 성능을 결정짓는 함수의 계수와 기울기는 바뀌지 않는다. 이제 이론적으로 이 문제를 개선할 시간이다.

(잡설을 조금 적자면, 나는 scale 문제에서 기울기가 매우 중요하다고 생각한다. keyvalue와 bitmap은 둘다 1차 함수로 linear하게 증가하지만 계수가 다르다.)

regex와 Finite Automata

re2의 방식이 왜 실패했는지, 기존 regex는 어떻게 동작하고 re2는 어떻게 다를지를 보아야했다. 그래서 처음 시작은 (내가 아주 좋아하는 개발자인) russ cox의 블로그 글을 읽는 것으로 시작했다.

regex가 무엇인지 아주 간단하게 설명하고 시작하는데, 동일하게 인용하면서 시작해보자.

Regular expressions are a notation for describing sets of character strings. When a particular string is in the set described by a regular expression, we often say that the regular expression matches the string.

정규 표현식은 문자열 집합을 설명하는 표기법입니다. 특정 문자열이 정규 표현식이 나타내는 문자열 집합에 속하는 경우 우리는 그 문자열이 matching된다고 합니다.

문자열 집합을 설명하는 다른 방법은 FSM(Finite Automata, State Machine)이 있다. 다들 알고있을 이 방식으로 문자열 집합을 설명할 수 있다. 간단한 예시는 다음과 같다.

예시의 정규식을 간단한 FSM으로 만들어보겠다. “(l?s)|(won?o)”