원문 캡처 · ap29600.github.io
원문 캡처 · ap29600.github.io

배열 언어 APL의 불리언 스캔(boolean scan)은 진리표의 대칭성을 이용해 여러 연산을 몇 가지 핵심 연산으로 구현할 수 있다. 안드레아 피세리(Andrea Piseri)는 논리 부정과 입력·출력 변환으로 스캔 연산 사이의 관계를 정리하고, 이를 통해 구현 작업과 실행 파일 크기를 줄이는 방법을 설명한다.

스캔과 불리언 연산의 대칭성

접기(fold)는 순서가 있는 자료를 차례로 처리하며 누산값을 갱신하고, 스캔(scan)은 최종 누산값 대신 중간 결과를 모두 반환한다. APL에서는 각각 /와 \\ 연산자로 표현한다. 예를 들어 +/ 1 2 3 4는 합계 10을, +\\ 1 2 3 4는 누적 합 1 3 6 10을 돌려준다.

스캔과 접기는 배열 곳곳에 정보를 전달하는 일반적인 방법이다. APL에서는 명시적으로 배열을 반복 처리하는 방식이 느릴 수 있어 특히 유용하다. 예를 들어 문자열에서 따옴표 안에 있는 위치를 찾을 때, 따옴표 문자인지 비교한 결과를 불리언 배열로 만든 뒤 배타적 논리합(XOR) 스캔을 적용하면 따옴표 안팎의 상태를 얻을 수 있다.

APL에는 AND, OR, XOR, NAND, NOR와 비교 연산자를 포함해 10개의 비자명한 이진 불리언 연산이 있다. 각 연산을 따로 빠르게 구현하면 개발 작업과 실행 파일 크기가 커진다. 특히 APL은 불리언 배열을 비트 단위로 압축해 저장하므로, 최적화된 구현은 CPU 사이클당 여러 원소를 처리할 수 있다. 피세리는 간단한 구현은 대략 사이클당 0.6개 원소를 처리할 수 있다고 언급한다.

피세리는 입력을 먼저 부정하거나 스캔 결과를 부정하는 변환을 적용하면 연산 사이에 다음과 같은 관계가 생긴다고 정리한다.

  • 스캔 입력을 부정하면 같은 스캔 결과를 내는 다른 불리언 연산으로 바꿀 수 있다.
  • 스캔 결과를 부정할 때는 누산값에도 대응하는 변환을 적용해 스캔의 상태 갱신을 유지한다.
  • 입력과 결과를 함께 변환하는 경우도 같은 방식으로 다른 연산과 연결된다.

이 변환을 10개 연산의 진리표에 적용하면 ∧, <, ≠가 모든 연산을 대표하는 집합이 된다. 따라서 이 세 연산을 빠르게 구현하면 나머지 연산은 대칭 변환을 적용해 구현할 수 있다. 글은 이 방식이 성능을 완전히 희생하지 않으면서 구현 시간과 실행 파일 크기를 줄인다고 설명한다.

이 아이디어가 완전히 새로운 것은 아니다. K 언어에서는 내장된 부등호 연산자가 없어 ≠ 스캔을 = 스캔과 부정 입력으로 바꾸는 방식이 알려져 있다. CBQN 인터프리터도 덜 흔한 조합에 이런 단축 방식을 활용한다. CBQN 스캔 구현

효율적인 비트 스캔 구현

부록에서는 XOR, AND, 미만 연산자의 스캔을 64비트 단어 단위로 구현하는 방법도 다룬다. XOR 스캔은 접두부를 두 배씩 늘리는 기법을 사용하며, 이전 단어에서 넘어오는 비트의 의존성을 늦추는 방식으로 개선할 수 있다고 설명한다. 글에 따르면 이 방식은 최대 사이클당 10.5비트를 처리한다. 측정값은 메모리가 캐시에 적중하는 조건에서 제시됐다.

AND 스캔은 단어 안의 첫 연속된 1 비트 구간을 계산하는 간단한 식으로 처리할 수 있다. 배열 전체에서는 실제 스캔이 필요한 단어가 최대 하나이고, 그 앞뒤는 각각 모두 1 또는 0으로 처리할 수 있다는 관찰을 이용한다. 피세리는 첫 번째 루프가 사이클당 62비트를 처리할 수 있다고 설명한다.

미만 연산자 스캔은 연속된 1 비트 구간에서 홀수 위치의 비트를 끄는 방식으로 설명한다. 제시한 구현은 사이클당 8.8비트를 처리한다. 이 방법은 simdjson의 JSON 이스케이프 문자 탐지 코드에서 가져왔다고 밝힌다. XOR 스캔의 구현 방식과 관련해서는 Bit Twiddling Hacks와 BQN 구현 노트도 참고 자료로 연결한다.

글에서 설명하는 스캔 의미는 왼쪽에서 오른쪽으로 처리하고 초기값을 명시하는 가상의 APL 방언을 기준으로 한다. 피세리는 실제 APL의 스캔이 이 방식과 일치하는 것은 함수가 결합법칙을 만족할 때뿐이라고 덧붙인다. 또 간단한 스칼라 구현에는 데이터 간 의존성 때문에 사이클당 원소 하나라는 상한이 있을 수 있다고 설명한다.