SHA-1 충돌 감지, SIMD로 두 배 빠르게
Solving for faster SHA-1 collision detection
git 서버에서 pack 파일 검증 시 SHA-1 충돌 감지가 전체 시간의 84%를 차지할 만큼 느리다. 기존 sha1-checked 크레이트는 일반 SHA-1 속도의 28~29%에 불과했다. sam reis는 하드웨어 가속을 도입하고, 충돌 감지 필터를 SIMD에 맞게 재구성하는 솔버 기반 코드 생성기로 sha1dc를 새로 만들었다. 그 결과 일반 SHA-1의 68~81% 속도를 달성해 git pack 검증을 두 배 빠르게 할 수 있게 됐다.
일반 데이터에서는 약 95%의 블록이 필터를 통과할 때 빈 마스크를 남기므로 재계산은 거의 실행되지 않는다. 필터가 없다면 해싱은 약 40 MiB/s로 기어갈 것이고, 필터 자체가 충돌 감지 SHA-1이 일반 SHA-1보다 더 많은 시간을 소비하는 부분이다.