질문의 역사
C++20 이전에는 두 정수 또는 포인터의 산술 평균을 계산하기 위해 일반적으로 수동 구현이 필요했으며, 일반적으로는 단순한 표현식 (a + b) / 2를 사용했습니다. 그러나 이 방법은 합이 해당 형식이 표현할 수 있는 최대 값을 초과할 때 정의되지 않은 동작을 유발합니다. std::midpoint는 C++20에서 <numeric> 헤더 내에 표준화되어 정수형과 포인터 형식의 전체 도메인에서 올바른 결과를 보장하는 이동 가능하고, constexpr이며, noexcept 솔루션을 제공합니다.
문제
부호 있는 정수 오버플로우는 C++에서 정의되지 않은 동작이며, C++20의 2의 보수 규정 준수에도 불구하고 그렇습니다. 두 개의 큰 양의 부호 있는 정수(예: INT_MAX 근처)를 평균화할 때, 그 합은 오버플로우가 발생합니다. 마찬가지로 두 개의 큰 음의 정수에 대해서도 합이 언더플로우될 수 있습니다. 포인터 산술 또한 오버플로우에서 정의되지 않은 동작을 가지지만, 동일한 배열의 두 포인터 간의 차이는 std::ptrdiff_t에 맞게 보장되어 정수 추가에서 존재하는 오버플로우 위험을 제거합니다. 문제는 덧셈에 내재된 오버플로우를 피하면서 정수에 대한 평균 계산 알고리즘을 구현하는 것입니다.
해결책
부호 있는 정수를 위해 std::midpoint는 피연산자를 뺄셈 전에 해당 부호 없는 대응값으로 변환하여 오버플로우를 피합니다. a > b인 경우 a - (unsigned_type(a) - b) / 2로 평균을 계산하거나, 그렇지 않을 경우 대칭적인 방식을 적용합니다. 이는 피연산자의 중간 값의 크기가 입력을 초과하지 않도록 하여 두 숫자 간의 반 거리를 계산하기 위해 부호 없는 타입의 잘 정의된 모듈로 산술을 활용합니다. 포인터의 경우, 구현은 first + (last - first) / 2를 쉽게 사용하며, (last - first)의 차이는 잘 정의되고 표현이 가능하므로 후속 덧셈이 배열의 유효 범위 내에 남도록 보장합니다.
문제 설명
고주파 거래 플랫폼에서는 Unix 에포크 이후 나노초로 표현된 두 주문 타임스탬프 간의 시간 중간점을 계산해야 했습니다. 시장 개장 근처의 스트레스 테스트 중에, 타임스탬프가 INT64_MAX에 근접할 때, 기존 계산 (t1 + t2) / 2가 부호 있는 정수 오버플로우로 인해 간헐적인 충돌을 유발하여 주문 매칭 엔진의 우선 순위 큐 로직이 손상되었습니다.
고려된 다양한 솔루션
솔루션 1: 내장된 확장 정밀도 타입 사용
팀은 중간 계산을 위해 __int128_t로 캐스팅하고 다시 캐스팅하는 것을 고려했습니다. 이 접근 방식은 지원되는 컴파일러(GCC, Clang, MSVC)에서 올바른 산술을 보장했습니다. 그러나 이는 엄격한 C++17 준수를 요구하는 내장 타겟에 대한 이동 가능성이 부족하며, 32비트 아키텍처에서 128비트 에뮬레이션의 비용으로 미세한 성능 저하를 초래했습니다.
솔루션 2: 부호 없는 산술 캐스팅 두 타임스탬프를 std::uint64_t로 변환하고 평균을 계산한 후 다시 변환하는 것을 제안했습니다. 이는 양수 값에 대해서는 오버플로우를 피할 수 있지만, 역사적 타임스탬프(부호가 있는 표현에서의 음수 값)에 대해서는 구현 정의된 결과를 생성하기 때문에 부정확한 평균을 초래할 수 있습니다.
솔루션 3: 오버플로우 체크가 있는 수동 분기
피연산자의 부호를 확인하고 조건부로 a + (b - a)/2 또는 비트 조작을 사용하는 사용자 정의 함수를 구현하는 것을 고려했습니다. 이는 정확성을 제공했지만 분기 오버헤드와 복잡성을 추가했습니다. 여러 수치 도메인(좌표, 가격, 타임스탬프)에 걸쳐 이 논리를 유지하는 것은 DRY 원칙을 위반하고 유지 관리 오류의 위험을 증가시켰습니다.
솔루션 4: C++20 std::midpoint 도입 도구 체인을 C++20으로 업그레이드하고 std::midpoint를 사용하여 모든 엣지 케이스를 올바르게 처리하는 제로 오버헤드 추상화를 제공했습니다.
선택된 솔루션 및 결과 팀은 솔루션 4를 선택하고 계산 계층을 C++20으로 마이그레이션했습니다. 이 변경으로 인해 프로덕션에서의 오버플로우 충돌이 제거되었으며, 안전한 수학 유틸리티를 200라인 줄이는 동시에 분기 논리를 제거하여 캐시 지역성을 향상시켰습니다. 회귀 테스트를 통해 x86-64에서 단순 접근 방식과 동일한 성능을 확인했으며, 컴파일 타임 상수에 대한 constexpr 평가의 추가 혜택이 있었습니다.
질문 1: 부호 있는 정수를 부호 없는 타입으로 변환하는 것이 일반적인 중간 계산에 불충분한 이유는 무엇인가?
답변 부호 없는 산술 연산은 2^N 모듈로에서 래핑하고 오버플로우를 피하지만, 음의 부호 있는 정수를 부호 없는 정수로 변환하면 큰 양의 값이 생성됩니다(예: -1은 UINT_MAX가 됩니다). 음수와 양수 타임스탬프를 부호 없는 산술로 평균화하면 부호 있는 평균이 아닌 부호 없는 범위의 중간에 가까운 결과가 나타납니다. std::midpoint는 부호를 보존하고 차이가 홀수일 때 첫 번째 인수 방향으로 올바르게 반올림하여 최종 결과에 대한 보조 래핑에 의존하지 않고 부호 비트를 올바르게 처리합니다.
질문 2: std::midpoint가 포인터에 대해 정의되지 않은 동작을 유발하는 특정 객체 모델 제약 조건은 무엇인가?
답변
std::midpoint는 두 포인터가 동일한 배열 객체의 요소를 가리켜야 합니다(또는 마지막 요소 뒤를 넘어). 포인터가 서로 다른 배열이나 관련 없는 메모리를 참조하는 경우, 내부적으로 사용되는 last - first 표현이 동일한 배열의 포인터에 대해서만 정의되기 때문에 동작은 정의되지 않습니다. 이는 정수 중간값과의 미세한 차이이며, 지원자들은 종종 이것이 단순한 수치 평균처럼 작동한다고 가정하고 포인터 산술에 대한 엄격한 별칭 및 객체 모델 요구 사항을 간과합니다.
질문 3: std::midpoint는 부동 소수점 타입에 대해 정수와 어떻게 다르게 작동하며, 특히 NaN 값에 대해서는 어떤가?
답변
부동 소수점 타입에 대해 std::midpoint는 합산에서 오버플로우 및 언더플로우를 방지하여 (이는 잘못된 무한대 또는 0을 생성할 수 있습니다) 구현 정의된 전략을 사용하며, 종종 a/2 + b/2와 동등합니다. 특히, 만약 어느 한 인수가 NaN이면 std::midpoint는 NaN을 반환합니다. 한 인수가 양의 무한대이고 다른 인수가 음의 무한대인 경우 NaN(불확정)을 반환하며, 반면 정수 중간값은 단순히 오버플로우되거나 래핑됩니다. 지원자들은 종종 간단한 산술이 수행된다고 가정하여 IEEE 754 특수 값 전파 규칙을 고려하지 않습니다.