▲

GN⁺: 1brc merykitty의 마법 SWAR: 3천 단어로 설명된 8줄 코드

 (questdb.io)
2P by neo 6달전 | favorite | 댓글 1개

1BRC 대회 소개

  • 1BRC 대회에서는 "보통의 용의자들"을 처리한 후, CSV 파일에서 온도를 파싱하는 것이 병목 현상이 될 것이라는 예측이 있었음.
  • 온도는 -XX.X, -X.X, X.X, XX.X의 네 가지 형태로 나타날 수 있으며, 초기에는 Double.parseDouble() 라이브러리 호출을 사용했음.
  • 그러나 곧 맞춤형 솔루션이 등장했고, 이 중 하나는 루프 없이 두 개의 분기만을 가진 최적화된 방법으로 보였음.
  • 그러다가 Quân Anh Mai(@merykitty)가 제시한 솔루션으로 인해 트위터의 #1BRC 해시태그가 불타올랐음. 이 솔루션은 if 문 없이 단 하나의 파일 읽기만을 사용했음.

merykitty의 마법 같은 SWAR 분석

  • merykitty의 코드는 18개의 ALU 연산으로만 구성되어 있으며, numberOfTrailingZeros()라는 단일 저수준 함수 호출을 포함함.
  • 입력된 long 숫자에는 CSV에서 8바이트가 들어가고, 정수 형태의 온도(실제 온도의 10배)가 출력됨.
  • 이 기술은 "SIMD Within A Register"(SWAR)라고 불리며, 표준 CPU 레지스터와 명령어를 사용함.
  • 코드는 숫자가 음수인지 감지, 부호 문자를 제거, 소수점 위치 찾기, 내용을 템플릿에 맞춰 정렬, ASCII 문자를 숫자 값으로 변환, 각 숫자에 가중치를 곱하고 모두 더하기, 부호 적용 등의 단계를 거침.
  • 이러한 단계들은 ALU 연산만을 사용하여 수행됨.

결론

  • merykitty가 단독으로 몇 일 만에 이 모든 것을 어떻게 해낼 수 있었는지는 블로그 포스트로 설명할 수 없는 진짜 미스터리임.
  • QuestDB는 오픈 소스이며, 아파치 2.0 라이선스 하에 빠른 데이터 삽입과 SQL 분석 기능을 제공함.

GN⁺의 의견

  • 이 기사는 단순한 온도 파싱 문제를 해결하기 위해 고안된 SWAR 기술의 복잡성과 창의성을 보여줌. 이는 프로그래밍에서 비트 연산의 강력함과 최적화의 중요성을 강조함.
  • 이러한 접근 방식은 특히 시스템 프로그래밍이나 성능에 민감한 애플리케이션 개발에 관심이 있는 초급 소프트웨어 엔지니어에게 흥미로운 사례가 될 수 있음.
  • 비트 연산과 최적화에 대한 이해를 높이기 위해 관련된 주제나 문제를 다루는 온라인 코딩 대회나 튜토리얼을 찾아보는 것이 도움이 될 것임.
  • 이 기술이 실제 산업 환경에서 어떻게 적용될 수 있는지, 그리고 이와 유사한 최적화 기법을 사용하는 다른 데이터베이스나 시스템이 있는지에 대한 추가적인 연구가 필요함.
  • QuestDB와 같은 시스템을 도입할 때는 성능 향상뿐만 아니라 유지보수성, 코드의 가독성, 그리고 장기적인 기술 지원과 같은 다른 요소들도 고려해야 함.
▲
neo 6달전  [-]
Hacker News 의견

  • simdjson 논문과 관련된 해커뉴스 댓글 요약:

    • simdjson 논문: 이와 유사한 기술을 사용하며, 매우 잘 쓰여졌고 훌륭한 예시를 포함함.

  • 코드 컨텍스트에 대한 해석: 제시된 해결책이 뛰어나지만, 데이터가 잘 구성되었다는 가정이 필요함. 효율적인 오류 검사와 복구 기능은 경험이 많은 파서에서 큰 가치를 지님.

  • 숫자 파싱 기술: 숫자 비트필드를 각각의 10의 거듭제곱으로 곱하고 MUL을 통해 shift/더하는 것은 알려진 기술임. Lemire의 블로그 참조.

  • SWAR(SIMD Within A Register)에 대한 설명: 자바/스칼라에서 바이트 배열 뷰 var 핸들을 사용하여 효율적인 SWAR 루틴을 구현하는 예시들이 많음.

  • SWAR에 대한 간단한 정의: "SIMD Within A Register"는 하나의 레지스터 내에서 SIMD 연산을 수행함.

  • BRC(Branchless Ray Casting)의 I/O 병목 현상에 대한 질문: CPU가 병목이라는 것이 이해되지 않음.

  • 68000에서의 SWAR 사용 경험: 4바이트를 한 번에 병렬로 처리하는 것이 가능했지만, 오버플로우 처리가 까다로웠음. 해당 기사를 매우 좋아함.

  • 상태 공간과 슈퍼 옵티마이저: 상태 공간이 작기 때문에 유사한 결과를 내놓는 슈퍼 옵티마이저가 존재하는지에 대한 질문.

  • AVX 명령어와 자바의 SIMD 지원: 이 알고리즘은 AVX 명령어를 사용하여 32배 병렬로 수행될 수 있지만, 자바는 특정 경우를 제외하고는 SIMD CPU 사용을 제대로 지원하지 않아 아쉬움.

  • 비트 조작에 대한 이해: 이 기사는 그 이전의 어떤 것보다 비트 조작을 더 잘 이해할 수 있게 해주었으며, 1BRC 챌린지에 대한 자바 솔루션을 제시한 저자에게 감사함.

답변달기