ripgrep의 가속 방식은 Rust의 regex crate를 활용한 AVX2 (generic) 접근법이라는 설명. 예를 들어, \w+\s+Sherlock\s+\w+ 같은 정규표현식도 Sherlock만 따로 뽑아서 빠르게 검색 가능함을 강조. 실제 구현은 여기에서 확인 가능. 이 글의 알고리즘과의 주요 차이점은 needle의 첫/마지막 바이트 대신, 배경 분포를 이용해 덜 자주 나오는 2바이트로 검색을 최적화하는 휴리스틱 사용임을 언급. 단순 Two-Way 방식이나 GNU libc의 memmem보다 훨씬 빠른 성능임을 벤치마크 결과로 제시. prebuilt 벤치마크에서는 memmem류 루틴이 needle이 고정될 때마다 상태를 반복적으로 재구축해야 하기 때문에 효율이 떨어진다는 API 한계점도 강조
바이트의 배경 분포를 어떻게 알 수 있는지, haystack에서 그 분포를 일일이 스캔한다면 오히려 성능에 악영향이 있지 않겠냐는 지적
Wasm/WASI libc의 SIMD 최적화를 시도하면서 이런 문자열 검색 알고리즘을 구현한 경험 공유. haystack의 길이가 정해져 있고, needle이 충분히 크면 Quick Search와 조합하는 것이 유용하다는 의견과 함께 관련 코드와 알고리즘 설명 링크 제시
C#에서도 IndexOf에 SIMD가 적용됨을 공유하며, 자세한 내용은 여기에서 확인 가능
나 역시 SMID 방식을 써서 문자열 검색과 split을 위한 다양한 알고리즘을 직접 구현해봤다는 경험 소개. tamgu의 conversion.cxx 소스 공개. 본문에서 언급한 방식과는 또 다른 알고리즘을 썼음을 밝힘
본인 알고리즘에 대해 간단히 요약해달라는 요청. 예시로, 원문 1번 알고리즘은 첫/마지막 문자를, 2번 알고리즘은 앞 4글자를 동시에 비교하며 여러 후보 위치 확인하는 방식이라는 설명 첨부
몇 년 전 Zig의 generic SIMD를 사용해서 LZ77 window search용으로 수정한 버전을 구현해보려 했던 경험 공유. 관련 내용은 여기에서 확인 가능
빠른 HTTP 파싱을 위해 SIMD 알고리즘을 사용하는 hparse 프로젝트를 떠올린다는 의견
swar 알고리즘은 1바이트 정렬 데이터를 8바이트 단위로 캐스팅해 UB(정의되지 않은 동작)이 발생함을 언급. Unaligned load 때문에 성능 이슈가 있을 수도 있다는 지적
본인은 이런 코드는 종종 이상적인 알고리즘 혹은 가독성을 위한 의사코드로 받아들여왔다는 의견. mempcy를 사용하지 않고, 경계 검사도 부정확함을 지적. haystack 길이가 8의 배수라고 가정하거나, needle이 비어있으면 unsigned integer overflow로 out-of-bounds가 나는 등 UB가 3개나 존재. 실제로 SIMD 데모 코드에선 흥미로운 벡터 활용 방식만 보여주고, 경계 조건은 생략되는 경우가 많았던 경험 공유
libc의 strstr이 느리다는 건 이미 알려진 사실이지만, musl은 빠르고 최신 알고리즘이라는 점 강조. 이제 이름만 정하면 smart shootout에 추가 가능. 최고의 SIMD 알고리즘과 비교하면 어떨지 궁금증
참고 벤치마크로 musl의 Two-Way와 본인이 공유한 SIMD 최적화 libc 알고리즘의 비교 결과 소개. 벤치마크 방법은 관련 코드 기반. SIMD 활용 개선분은 이 표에서 확인 가능. 뛰어나다기보다는 꽤 괜찮은 수준의 개선임을 솔직히 평가. musl은 길이 고정 문자열(memmem)에 특화되고, 본인은 Wasm 환경에서 unknown length 문자열(strstr)에는 여러 최적화를 자유롭게 시도할 수 있었음을 언급. NUL 종료 문자열 때문에 여러 좋은 알고리즘이 곤란을 겪음
smart에 더 많은 SIMD 알고리즘이 포함되면 좋겠고, 시간 나면 직접 실험해보고 싶다는 개인적 의지 공유
문자열 검색 SIMD 비교에서 2018 버전이 빠진 것 아니냐는 질문
문자열 크기에 따라 SIMD 방식이 실제로 효율적인 경계가 궁금하다는 질문. 일반적으로 작은 문자열에선 SIMD 설정 오버헤드(정렬, 길이 계산 등) 때문에 오히려 단순 byte 기반 검색보다 느릴 수 있다는 점을 강조. 하드웨어 아키텍처에 따라 크게 달라질 수 있음을 감안
본인 경험상 오히려 반대임을 언급. 이런 알고리즘들은 쓸데없는 설정 없이 거의 brute force 방식이라, 길고 반복적인 needle엔 시간 복잡도가 나빠짐. 이에 반해 quadratic(제곱 근) 문제를 방지하거나 sublinear(부분 선형) 수행을 하는 고급 문자열 검색 알고리즘들은 needle 구조를 더 깊이 탐색하는 고비용 세팅이 필요하다는 점 강조
Python에서 타 언어 호출 없이 직접 SIMD를 쓸 수 있으면 좋겠다는 바람
Austin의 블로그와 모음글(story on vowels detection 링크)을 언급하며, "별도 언어 호출 없이 SIMD 직접 사용"이란 어떤 의미인지 구체적으로 질문. 기본적으로 Assembly도 ‘다른 언어’이긴 하니…라는 농담 섞인 언급. Python과 SIMD 관련 생태계는 PeachPy(x86 어셈을 Python에서 작성), Mojo(새 Python스타일 언어), CPython 바인딩이 얇은 SIMD 라이브러리 등으로 매우 다양한 스펙트럼이 있음을 안내. 구체적으로 어떤 방식 원하는지 묻고, ASCII 대상이라면 StringZilla의 find_first_of (코드) 함수도 추천
왜 굳이 Python에서 직접 하려고 하는지 의문. 성능 한계로 고민 중이라면 언어 자체를 바꾸는 것만으로 20~50배 이상 성능 향상이 가능하다는 조언
Hacker News 의견
ripgrep의 가속 방식은 Rust의
regexcrate를 활용한 AVX2 (generic) 접근법이라는 설명. 예를 들어,\w+\s+Sherlock\s+\w+같은 정규표현식도Sherlock만 따로 뽑아서 빠르게 검색 가능함을 강조. 실제 구현은 여기에서 확인 가능. 이 글의 알고리즘과의 주요 차이점은 needle의 첫/마지막 바이트 대신, 배경 분포를 이용해 덜 자주 나오는 2바이트로 검색을 최적화하는 휴리스틱 사용임을 언급. 단순 Two-Way 방식이나 GNU libc의memmem보다 훨씬 빠른 성능임을 벤치마크 결과로 제시.prebuilt벤치마크에서는memmem류 루틴이 needle이 고정될 때마다 상태를 반복적으로 재구축해야 하기 때문에 효율이 떨어진다는 API 한계점도 강조Wasm/WASI libc의 SIMD 최적화를 시도하면서 이런 문자열 검색 알고리즘을 구현한 경험 공유. haystack의 길이가 정해져 있고, needle이 충분히 크면 Quick Search와 조합하는 것이 유용하다는 의견과 함께 관련 코드와 알고리즘 설명 링크 제시
C#에서도 IndexOf에 SIMD가 적용됨을 공유하며, 자세한 내용은 여기에서 확인 가능
나 역시 SMID 방식을 써서 문자열 검색과 split을 위한 다양한 알고리즘을 직접 구현해봤다는 경험 소개. tamgu의 conversion.cxx 소스 공개. 본문에서 언급한 방식과는 또 다른 알고리즘을 썼음을 밝힘
본인 알고리즘에 대해 간단히 요약해달라는 요청. 예시로, 원문 1번 알고리즘은 첫/마지막 문자를, 2번 알고리즘은 앞 4글자를 동시에 비교하며 여러 후보 위치 확인하는 방식이라는 설명 첨부
몇 년 전 Zig의 generic SIMD를 사용해서 LZ77 window search용으로 수정한 버전을 구현해보려 했던 경험 공유. 관련 내용은 여기에서 확인 가능
빠른 HTTP 파싱을 위해 SIMD 알고리즘을 사용하는 hparse 프로젝트를 떠올린다는 의견
swar 알고리즘은 1바이트 정렬 데이터를 8바이트 단위로 캐스팅해 UB(정의되지 않은 동작)이 발생함을 언급. Unaligned load 때문에 성능 이슈가 있을 수도 있다는 지적
libc의 strstr이 느리다는 건 이미 알려진 사실이지만, musl은 빠르고 최신 알고리즘이라는 점 강조. 이제 이름만 정하면 smart shootout에 추가 가능. 최고의 SIMD 알고리즘과 비교하면 어떨지 궁금증
참고 벤치마크로 musl의 Two-Way와 본인이 공유한 SIMD 최적화 libc 알고리즘의 비교 결과 소개. 벤치마크 방법은 관련 코드 기반. SIMD 활용 개선분은 이 표에서 확인 가능. 뛰어나다기보다는 꽤 괜찮은 수준의 개선임을 솔직히 평가. musl은 길이 고정 문자열(memmem)에 특화되고, 본인은 Wasm 환경에서 unknown length 문자열(strstr)에는 여러 최적화를 자유롭게 시도할 수 있었음을 언급. NUL 종료 문자열 때문에 여러 좋은 알고리즘이 곤란을 겪음
smart에 더 많은 SIMD 알고리즘이 포함되면 좋겠고, 시간 나면 직접 실험해보고 싶다는 개인적 의지 공유
문자열 검색 SIMD 비교에서 2018 버전이 빠진 것 아니냐는 질문
문자열 크기에 따라 SIMD 방식이 실제로 효율적인 경계가 궁금하다는 질문. 일반적으로 작은 문자열에선 SIMD 설정 오버헤드(정렬, 길이 계산 등) 때문에 오히려 단순 byte 기반 검색보다 느릴 수 있다는 점을 강조. 하드웨어 아키텍처에 따라 크게 달라질 수 있음을 감안
Python에서 타 언어 호출 없이 직접 SIMD를 쓸 수 있으면 좋겠다는 바람
Austin의 블로그와 모음글(story on vowels detection 링크)을 언급하며, "별도 언어 호출 없이 SIMD 직접 사용"이란 어떤 의미인지 구체적으로 질문. 기본적으로 Assembly도 ‘다른 언어’이긴 하니…라는 농담 섞인 언급. Python과 SIMD 관련 생태계는 PeachPy(x86 어셈을 Python에서 작성), Mojo(새 Python스타일 언어), CPython 바인딩이 얇은 SIMD 라이브러리 등으로 매우 다양한 스펙트럼이 있음을 안내. 구체적으로 어떤 방식 원하는지 묻고, ASCII 대상이라면 StringZilla의
find_first_of(코드) 함수도 추천왜 굳이 Python에서 직접 하려고 하는지 의문. 성능 한계로 고민 중이라면 언어 자체를 바꾸는 것만으로 20~50배 이상 성능 향상이 가능하다는 조언