상수 나눗셈 floor division, 새 알고리즘이 ARM에서 10~20% 더 빠름

기법 자체는 워낙 단순해서 누가 진작 했을 줄 알았는데, 찾아봐도 문서가 안 나오더라. 나 같은 사람이 하나 있었나 보지.

계산 일부가 미리 정해져 있으면 나눗셈을 곱셈과 시프트로 바꿀 수 있는데, 중첩 루프에서 이걸 미리 계산해두면 체감 속도가 꽤 달라짐.

표준 정수 나눗셈 쪽은 이미 많이 알려진 얘기고, 새건 range-splitting으로 음수 입력의 floor division을 처리하는 부분임. 약수 60%는 부호 선택 방식, 나머지 20%/20%는 음수/양수 bump로 처리함.

Robison 나눗셈이 더 나은 경우도 많음. 약수가 컴파일 상수가 아니라 작은 집합에서 오면 상수 테이블만 만들어두고 같은 코드를 쓰면 됨.

여러 약수로 나눗셈을 많이 해야 하는 경우를 보면, 이미지 코딩의 양자화 행렬 같은 걸 떠올리면 됨. Robison은 SIMD로 만들기 쉬운데 약수마다 코드 경로가 달라지는 알고리즘은 훨씬 힘듦.

멀티미디어 처리하는 입장에서 x86과 ARM의 곱셈 명령어 집합은 좀 한심할 정도로 제한적임. VideoCore 최적화하던 동료가 곱셈 명령어가 80개나 된다고 놀랐는데, 1~2년 만에 거의 다 썼다고 하더라.

이런 알고리즘 최적화 연구하는 사람들한테는 그냥 존경심이 생김.