토요일 하루 만에 O(N²) 알고리즘 일곱 개 교체하기

여러분의 AI는 작동하는 코드를 쓸 수 있다. 그것을 확장되는 코드로 만드는 것이야말로 공간 런타임이 이기고 지는 지점이다 — 그리고 그것이 정확히 RakuAI가 그 위에 지어진 규율이다.

에이전트는 작동하는 코드를 쓰는 데 능숙하다. 확장되는 코드를 쓰는 데는 가끔 서투르다. 이것은 내가 인식하고 예산에 넣게 된 패턴이다. 이슈 틀 잡기가 X를 하는 함수를 요청하면, 에이전트는 작은 입력에서는 올바르게 X를 하지만 실제 크기의 입력에서는 무너지는 함수를 쓴다.

이번 토요일 나는 일부러 그런 함수들을 찾아 나섰다. 일곱 개가 돌아왔다. 토요일이 끝날 무렵, 일곱 개 모두 에이전트가 원래 착지시켰던 무차별 대입 플레이스홀더 대신 실제 프로덕션 알고리즘을 실행하고 있었다.

이 글은 각각이 무엇이었는지, 왜 중요했는지, 그리고 각각에 대해 에이전트가 무엇을 잘못했는지에 관한 것이다.

패턴

패턴은 이렇게 나타난다. 이슈가 등록된다. “오브젝트 A와 B 사이의 충돌 감지를 구현하라. 오브젝트가 겹칠 때 감지해야 함. 수락 기준: 겹치면 true를, 그렇지 않으면 false를 반환하는 bool 함수.”

에이전트는 함수를 작성한다. 함수는 작동한다. 함수는 O(N²) 무차별 대입이다. 오브젝트 두 개에는 괜찮다. 오브젝트 이백 개에도 괜찮다. 오브젝트 이천 개에는, 프레임률이 사라진다.

에이전트의 프롬프트는 점근적 복잡도를 명시하지 않았다. 에이전트는 프롬프트를 만족시켰다. 프롬프트는 엔진을 만족시키지 못했다.

이것은 에이전트 쪽의 문제가 아니라 내 쪽의 규율 문제다. 수정은 프롬프트 안에서 복잡도 목표에 대해 구체적이 되는 것, 중요할 때 알고리즘 클래스를 명시적으로 지정하는 것, 그리고 이런 종류의 무차별 대입 폴백을 정기적인 주기로 감사하는 것이다. 이번 토요일이 그 감사 주기였다.

일곱 가지 구체적인 교체

각각에 대해 구체적으로 말하고 싶다. 패턴이 동일하고 교훈이 쌓이기 때문이다.

하나. 2D 물리 광역 단계 충돌 감지. 원래 구현은 모든 오브젝트 쌍에 대한 이중 중첩 루프였다. 프레임당 O(N²). 스윕 앤 프룬(Baraff, 1992)으로 교체했다. 축 정렬 경계 상자를 최소 X 좌표로 정렬한 다음, 한 번 스캔한다. 한 상자의 최대 X가 다른 상자의 최소 X보다 클 때만 X축에서 쌍이 겹친다. 정렬은 O(N log N)이고, 스캔은 O(N + K)이며 K는 실제로 겹치는 쌍의 개수다. 일반적인 씬에서 K는 N²보다 훨씬 작은데, 그것이 핵심이다.

둘. 에이전트-군집 서브시스템을 위한 공간 충돌 감지. 같은 패턴, 다른 표면. 원래 구현은 모든 에이전트를 다른 모든 에이전트와 확인하는 이중 중첩 루프였다. 공간 해시 그리드로 교체했다. 각 에이전트는 경계 셀 좌표로 해시되며, 충돌은 같은 셀이나 인접 셀에 있는 에이전트 사이에서만 확인된다. 셀 크기는 대략 평균 에이전트 반경의 두 배로 선택된다. 예상 복잡도는 O(N), 최악의 경우(모두가 같은 셀에 있을 때, 일반적인 플레이에서는 일어나지 않음)는 O(N²)다. 해시 함수는 FNV 스타일 3D 좌표 해싱이다. 쌍 중복 제거는 (min(a,b), max(a,b)) 쌍의 정렬된 uint64_t 집합을 통해 이루어진다.

셋. 모델 로더 버텍스 캐시 최적화. 원래 구현은 애셋 작성자가 지정한 순서로 렌더러에 버텍스와 삼각형을 로드했다. 대부분의 저작 도구는 GPU의 버텍스 캐시에 맞춰 최적화하지 않으며, 이는 렌더러가 이미 가지고 있던 버텍스를 다시 가져오느라 많은 사이클을 낭비한다는 뜻이다. Tom Forsyth의 2006년 버텍스 캐시 최적화로 교체했다. 크기 32의 LRU 캐시 모델로, 각 후보 삼각형을 캐시 내 위치 감쇠 함수와 결합가 보너스(다른 미처리 삼각형들과 버텍스를 많이 공유하는 삼각형이 더 높은 점수를 받음)로 점수 매긴다. 결과는 전형적인 메시 위상에 대해 거의 최적에 가까운 상각 캐시 미스율이다. 구현은 T가 삼각형 개수일 때 O(T)로 실행된다.

넷. 비전 특징 서술자 매칭. 런타임의 컴퓨터 비전 파이프라인은 모든 프레임에서 특징 감지를 수행하고 추적을 위해 연속된 프레임 사이의 특징을 매칭한다. 원래 구현은 입력 서술자의 고정된 비율을 “매칭됨”으로 반환하는 플레이스홀더였다. 그 플레이스홀더는 무차별 대입조차 아니었다. 의도적인 스텁이었다. 교체는 Lowe의 비율 검정(2004)을 사용한 진짜 무차별 대입 서술자 매칭이다. ORB 서술자(이진)의 경우, 거리 척도는 XOR과 커니핸 비트 카운트를 통한 해밍 거리다. SIFT와 부동소수점 서술자의 경우, 거리는 L²다. 비율 검정은 최선과 차선 후보가 거리상 너무 가까운 모호한 매치를 거부한다. 비율 검정의 임계값은 문헌 기본값인 0.75다. 복잡도는 O(N₁ × N₂ × D)이며 D는 서술자 차원으로, ORB의 경우 32바이트다. 이것은 문자 그대로의 의미에서 무차별 대입이지만, 우리가 다루는 서술자 길이와 특징 개수에서는 충분히 빠르며 문헌이 비교하는 대상이기도 하다. 더 똑똑한 근사(FLANN, 계층적 k-평균)는 다음 주말을 위한 큐에 올라 있다.

다섯. 천 물리 제약 해결기. 원래 구현은 고정된 순서로, 낮은 반복 횟수로 제약을 반복했으며, 이는 수렴하지 않는 흔들리는 천을 만들어냈다. 반복 사이에 적절한 제약 셔플링을 갖춘 위치 기반 동역학 해결기로 교체했다. 셔플링이 중요한 이유는, 항상 같은 순서로 제약을 처리하는 제약 해결기는 편향되기 때문이다. 천은 예측 가능하게 한 방향으로만 늘어나게 된다. 각 반복마다 셔플링하면 그 편향이 제거된다. 반복 횟수는 프로덕션 품질을 위해 4에서 12로 올렸고, 저사양 디바이스를 위한 4회 반복 빠른 경로도 있다.

여섯. 군중 서브시스템을 위한 AI 에이전트 경로 계획. 원래 구현은 매 스텝마다 무작위 유효 이웃을 고르는 플레이스홀더였다. 에이전트는 무작위 방향으로 배회했고 가끔 운으로 목적지에 도착했다. 내비게이션 메시 위에서 적절한 A* 경로 계획으로 교체했다. 휴리스틱은 유클리드 거리이며, 비용 함수는 지형 경사와 표면 종류로 가중된다. 구현은 오픈 셋에 이진 힙을, 클로즈드 셋에 해시 셋을 사용하며, 이는 스텝당 비용을 힙에서 O(log N), 해시 셋에서 O(1)로 만든다.

일곱. 여러 클립에 걸친 애니메이션 블렌딩. 원래 구현은 가장 최근에 요청된 클립만 재생하고 나머지는 무시하는 플레이스홀더였다. 적절한 가중 블렌드 트리로 교체했다. 각 출력 프레임은 기여하는 클립들의 본별 변환의 가중 합이며, 가중치는 애니메이션 작성자가 지정하는 블렌드 트리 위상에 의해 구동된다. 블렌드 계산은 본 계층 순서를 존중해 자식 본이 부모의 블렌드된 변환을 올바르게 상속받도록 한다.

무엇을 배웠나

세 가지, 돌이켜보면 어느 것도 놀랍지 않다.

이슈 안에 알고리즘을 명시하라. 사소하지 않은 입력 크기에서 작동하는 어떤 함수에 대해서든, 이슈 틀 잡기는 예상 복잡도를 명시해야 한다. “N개 오브젝트 사이의 충돌을 감지하라”만으로는 부족하다. “스윕 앤 프룬(Baraff 1992) 혹은 그와 동등한 것을 사용해 최악의 경우 O(N log N)으로 N개 오브젝트 사이의 충돌을 감지하라”면 충분하다. 인용이 곧 규율이다. 그것이 없으면, 에이전트는 가장 쉬운 올바른 것, 즉 무차별 대입을 작성한다.

감사 작업은 필수적이다. PR이 착지하는 대로 읽는 것만으로는 이것들을 잡아내지 못했을 것이다. 각 개별 PR은 통과하는 테스트와 함께 작동하는 함수였다. “런타임 안에서 O(N²) 이상인 모든 함수를 찾고 그래야 하는지 평가하라”는 감사 작업이 그것들을 드러낸다. 감사를 주기에 추가하라.

문헌이 치트 코드다. 이 교체들 각각은 수십 년 된 논문을 배경으로 한 발표된 알고리즘이다. Baraff 1992. Forsyth 2006. Lowe 2004. 위치 기반 동역학. A*. 이것들은 새로운 것이 아니다. 어떤 논문을 읽어야 하는지 알려주면 에이전트는 그중 무엇이든 문헌과 동등한 버전을 작성할 것이다.

파트너와 빌더가 여기서 얻어야 할 것

파트너십을 위해 엔진을 평가하고 있고 팀이 코드베이스에 대한 알고리즘 감사를 한 적이 없다면, 하나 해보라고 요청하라. 감사는 무언가를 드러낼 것이다. 팀이 그것에 대해 어떻게 반응하는지가 어떤 기능 목록보다 더 많은 것을 말해준다.

성능에 민감한 코드베이스에서 에이전트 기반 워크플로를 운영하고 있다면, 감사 작업은 선택 사항이 아니다. 에이전트는 작동하는 코드를 착지시킬 것이다. 그 작동하는 코드는 때때로 무차별 대입 버전일 것이다. 감사는 어느 쪽인지 알아내는 방법이다.

성능에 민감한 작업을 위한 코딩 에이전트를 만드는 AI 랩이라면, 내가 최적화하고 싶은 지표는 “에이전트가 이름이 확장성 문제를 암시하는 함수를 구현할 때 점근적 복잡도에 대해 묻는가”다. 대부분의 에이전트는 그러지 않는다. 그러는 에이전트가 더 나은 코드를 만들어낸다.

토요일 오후. 무차별 대입 알고리즘 일곱 개가 실제 프로덕션 버전으로 교체됐다. 엔진은 더 빨라졌다. 코드베이스는 더 정직해졌다.

다시 만드는 일로 돌아간다.