Playing Around Less Slow Coding Practices for C++, CUDA, and Assembly Code

이 저장소의 벤치마크는 모든 주제를 완전히 다루는 것을 목표로 하지는 않지만, 성능 지향적인 소프트웨어 설계를 위한 사고방식과 직관을 형성하는 데 도움을 줍니다.
또한 C++에서 STL은 아니지만 사실상의 표준(de facto standard)인 라이브러리들을 CMake를 통해 가져오고 소스에서 컴파일하여 사용하는 예시를 제공합니다.
더 높은 수준의 추상화와 언어를 원하신다면 less_slow.rs 및 less_slow.py를 확인해 보세요.
저는 저 자신의 코딩 습관을 재고하기 위해 이러한 측정값들이 많이 필요했지만, 다른 분들에게도 도움이 되기를 바랍니다.
대부분의 코드는 매우 길고, 순서가 있으며, 중첩된 #pragma 섹션으로 구성되어 있습니다. 반드시 모든 사람에게 선호되는 형태는 아닙니다.

현대 코드의 상당 부분은 흔한 함정들 — 버그, 보안 취약점, 그리고 성능 병목 현상 (performance bottlenecks) — 으로 인해 어려움을 겪습니다.
대학 커리큘럼과 코딩 부트캠프는 전통적인 코딩 스타일과 표준 기능에 머무르는 경향이 있으며, 더 재미있고, 특이하며, 잠재적으로 효율적인 설계 기회들을 노출하는 경우는 드뭅니다.
이 저장소는 바로 그 점을 탐구합니다.

코드는 C++20 및 CUDA 기능을 활용하며, 다른 플랫폼에서도 작동할 수 있지만 주로 Linux 환경의 GCC, Clang, NVCC 컴파일러를 위해 설계되었습니다.
주제는 몇 나노초(nanoseconds) 내에 실행되는 기본적인 마이크로 커널(micro-kernels)부터 병렬 알고리즘 (parallel algorithms), 코루틴 (coroutines), 다형성 (polymorphism)을 포함하는 더 복잡한 구조에 이르기까지 다양합니다.
주요 하이라이트는 다음과 같습니다:

• 100배 더 저렴한 랜덤 입력?! 입력 생성 비용이 때로는 알고리즘 자체보다 더 많이 드는 이유를 알아보세요.

• 1/40의 비용으로 삼각함수 오차 1% 구현: std::sin과 같은 STL 함수를 단 3줄의 코드로 근사화하는 방법.

• 커스텀 std::ranges 및 반복자 (iterators)를 통한 4배 빠른 지연 로직 (lazy-logic)!

• -O3를 넘어서는 컴파일러 최적화 (Compiler optimizations): 추가적인 2배 속도 향상을 위한 덜 알려진 플래그와 기술들을 배워보세요.

• 행렬 곱셈 (Multiplying matrices)? 3x3x3 GEMM이 연산 횟수가 60% 더 적음에도 불구하고 왜 4x4x4보다 70% 더 느릴 수 있는지 확인해보세요.

• AI 스케일링 (Scaling AI)? 이론적인 ALU 처리량과 사용 중인 BLAS 사이의 격차를 측정해보세요.

• if 조건문은 몇 개부터 너무 많은 것일까? 단 10줄의 코드로 CPU의 분기 예측기 (branch predictor)를 테스트해보세요.

• 반복 (iteration)보다 재귀 (recursion)를 선호하시나요? 알고리즘이 SEGFAULT를 일으킬 깊이를 측정해보세요.

• 예외 (exceptions)를 피해야 하는 이유는? std::error_code나 std::variant와 같은 ADT (대수적 데이터 타입)를 사용하시겠습니까?

• 다중 코어로 확장하기 (Scaling to many cores)? OpenMP, Intel의 oneTBB, 또는 커스텀 스레드 풀 (thread pool)을 사용하는 방법을 배워보세요.

• 메모리 할당을 피하며 JSON을 처리하는 방법은? C++ 20을 사용하는 것이 쉬울까요, 아니면 전통적인 C 99 도구를 사용하는 것이 쉬울까요?

• 커스텀 키와 투명한 비교자 (transparent comparators)를 사용하여 STL의 연관 컨테이너 (associative containers)를 올바르게 사용하는 방법은?

• consteval 정규 표현식 (RegEx) 엔진으로 직접 작성한 파서 (parser)를 이기는 방법은?

• 포인터 크기가 정말 64비트일까 그리고 포인터 태깅 (pointer-tagging)을 활용하는 방법은?

• __UDP가 얼마나 많은 패킷을 드롭(dropping)하고 있는가__와 사용자 공간(user-space)에서 io_uring을 통해 웹 요청을 처리하는 방법은?

• 50% 더 빠른 벡터화된 불연속 메모리 연산(vectorized disjoint memory operations)을 위한 Scatter and Gather.

• Intel의 oneAPI vs Nvidia의 CCCL? <thrust>와 <cub>에는 무엇이 특별하게 들어있는가?

• CUDA C++, PTX 중간 표현(Intermediate Representations), 그리고 SASS, 그리고 이것들이 CPU 코드와 어떻게 다른가?

• 성능이 중요한 코드(performance-critical code)를 위해 인트린직(intrinsics), 인라인 asm, 그리고 별도의 .S 파일 중 무엇을 선택해야 하는가?

• CPU와 Volta, Ampere, Hopper, Blackwell GPU 간의 텐서 코어(Tensor Cores) 및 메모리(Memory) 차이점!

• FPGA 코딩이 GPU와 어떻게 다른가 그리고 고수준 합성(High-Level Synthesis), Verilog, VHDL이란 무엇인가? 🔜 #36

• 암호화된 엔클레이브(Encrypted Enclaves)란 무엇인가 그리고 Intel SGX, AMD SEV, ARM Realm의 지연 시간(latency)은 어느 정도인가? 🔜 #31

읽어보려면, less_slow.cpp 소스 파일로 이동하여 코드 스니펫(code snippets)과 주석을 읽어보세요.
대부분의 현대적인 IDE에는 #pragma region 섹션 사이를 탐색하고 이동하는 데 도움이 되는 내비게이션 바가 있다는 점을 기억하세요.
아래 지침을 따라 귀하의 환경에서 코드를 실행하고, 소스 코드를 읽으면서 주석과 비교해 보세요.

벤치마크 실행하기

이 프로젝트는 Linux, MacOS, Windows에서 GCC, Clang, MSVC 컴파일러와 호환되는 것을 목표로 합니다.
그럼에도 불구하고, 가장 폭넓은 기능을 다루기 위해서는 Linux에서 GCC를 사용하는 것을 권장합니다:

• Windows를 사용 중이라면, WSL을 사용하여 Linux 환경을 구축하는 것을 권장합니다.
• MacOS를 사용 중이라면, Homebrew 또는 MacPorts를 통해 제공되는 Clang의 비네이티브(non-native) 배포판 사용을 고려해 보세요.
• Linux를 사용 중이라면, C++20 기능을 지원할 수 있도록 CMake와 최신 버전의 GCC 또는 Clang 컴파일러를 반드시 설치하세요.

C++에 익숙하며 읽으면서 코드와 측정값을 직접 검토하고 싶다면, 저장소(repository)를 클론(clone)하고 다음 명령어를 실행하면 됩니다.

git clone https://github.com/ashvardanian/less_slow.cpp.git # 저장소 클론
cd less_slow.cpp                                            # 디렉토리 이동

...

빌드 과정에서 소스(source)로부터 여러 서드파티 의존성(third-party dependencies)을 가져와 컴파일합니다:

• 프로파일링(profiling)을 위해 Google의 Benchmark를 사용합니다.
• 병렬 STL (Parallel STL) 백엔드로 Intel의 oneTBB를 사용합니다.
• Senders & executors를 위해 Meta의 libunifex를 사용합니다.
• std::ranges를 대체하기 위해 Eric Niebler의 range-v3를 사용합니다.
• std::format을 대체하기 위해 Victor Zverovich의 fmt를 사용합니다.
• std::string을 대체하기 위해 Ash Vardanian의 StringZilla를 사용합니다.
• std::regex를 대체하기 위해 Hana Dusíková의 CTRE를 사용합니다.
• JSON 역직렬화(deserialization)를 위해 Niels Lohmann의 json을 사용합니다.
• 더 빠른 JSON 처리를 위해 Yaoyuan Guo의 yyjson을 사용합니다.
• STL의 연관 컨테이너(associative containers)를 대체하기 위해 Google의 Abseil을 사용합니다.
• C++20 코루틴(coroutines)을 구현하기 위해 Lewis Baker의 cppcoro를 사용합니다.
• Linux 커널 바이패스(kernel-bypass)를 단순화하기 위해 Jens Axboe의 liburing을 사용합니다.
• 네트워킹 TS 확장 기능으로서 Chris Kohlhoff의 ASIO를 사용합니다.
• GPU 가속 알고리즘을 위해 Nvidia의 CCCL을 사용합니다.
• GPU 가속 선형 대수(Linear Algebra)를 위해 Nvidia의 CUTLASS를 사용합니다.

Parallel STL, Intel TBB, BLAS 및 CUDA 없이 빌드하려면:

cmake -B build_release -D CMAKE_BUILD_TYPE=Release -D USE_INTEL_TBB=OFF -D USE_NVIDIA_CCCL=OFF -D USE_BLAS=OFF
cmake --build build_release --config Release

Homebrew에서 주요 의존성을 가져와 MacOS에서 빌드하려면:

brew install openblas
cmake -B build_release \
      -D CMAKE_BUILD_TYPE=Release \
...

출력을 제어하거나 특정 벤치마크 (benchmark)를 실행하려면 다음 플래그 (flags)를 사용하세요:

build_release/less_slow --benchmark_format=json             # JSON 형식으로 출력
build_release/less_slow --benchmark_out=results.json        # 결과를 `stdout` 대신 파일로 저장
build_release/less_slow --benchmark_filter=std_sort         # 이름에 `std_sort`가 포함된 벤치마크만 실행

안정성과 재현성 (reproducibility)을 높이려면, CPU의 동시 다중 스레딩 (Simultaneous Multi-Threading, SMT)을 비활성화하고 --benchmark_enable_random_interleaving=true 플래그를 사용하세요. 이 플래그는 여기에 설명된 대로 벤치마크를 섞고 교차 배치 (interleave) 합니다.

build_release/less_slow --benchmark_enable_random_interleaving=true

Google Benchmark는 libpmf를 통해 사용자 요청 성능 카운터 (User-Requested Performance Counters)를 지원합니다.
이러한 데이터를 수집하려면 sudo 권한이 필요할 수 있음에 유의하세요.

sudo build_release/less_slow --benchmark_enable_random_interleaving=true --benchmark_format=json --benchmark_perf_counters="CYCLES,INSTRUCTIONS"

또는, 성능 카운터 수집을 위해 Linux의 perf 도구를 사용하세요:

sudo perf stat taskset 0xEFFFEFFFEFFFEFFFEFFFEFFFEFFFEFFF build_release/less_slow --benchmark_enable_random_interleaving=true --benchmark_filter=super_sort

프로젝트 구조 (Project Structure)

이 저장소의 주요 파일은 CPU 측 코드가 포함된 less_slow.cpp C++ 파일입니다.
다양한 하드웨어별 최적화를 위한 여러 다른 파일들이 생성됩니다:

$ tree .
.
├── CMakeLists.txt          # 모든 파일에 대한 빌드 및 어셈블리(assembly) 지침
...

밈(Memes)과 레퍼런스(References)

밈(memes) 없는 교육용 콘텐츠라고?!
설마!

<table> <tr> <td><img src="https://github.com/ashvardanian/ashvardanian/blob/master/memes/ieee764-vs-gnu-compiler.jpg?raw=true" alt="IEEE 754 vs GNU Compiler"></td> <td><img src="https://github.com/ashvardanian/ashvardanian/blob/master/memes/no-easter-bunny-no-free-abstractions.jpg?raw=true" alt="No Easter Bunny, No Free Abstractions"></td> </tr> </table>

Google Benchmark 기능

이 벤치마크 스위트(benchmark suite)는 Google Benchmark에서 제공하는 대부분의 기능을 사용합니다.
많은 벤치마크를 작성하면서 전체 사용자 가이드(User Guide)를 일일이 확인하는 것을 피하고 싶다면, 가장 유용한 기능들을 요약한 목록은 다음과 같습니다:

• ->Args({x, y}) - 매개변수화된 벤치마크(parameterized benchmarks)에 여러 인자를 전달

• BENCHMARK() - 기본적인 벤치마크 함수를 등록

• BENCHMARK_CAPTURE() - 캡처된 서로 다른 값들을 사용하여 벤치마크의 변형(variants)을 생성

• Counter::kAvgThreads - 스레드 평균 카운터(thread-averaged counters) 지정

• DoNotOptimize() - 컴파일러가 연산을 최적화하여 제거하는 것을 방지

• ClobberMemory() - 메모리 동기화(memory synchronization) 강제

• ->Complexity(oNLogN) - 알고리즘 복잡도(algorithmic complexity)를 지정하고 검증

• ->SetComplexityN(n) - 복잡도 계산을 위한 입력 크기(input size) 설정

• ->ComputeStatistics("max", ...) - 실행 전반에 걸쳐 사용자 정의 통계(custom statistics) 계산

• ->Iterations(n) - 정확한 반복 횟수(iterations) 제어

• ->MinTime(n) - 최소 벤치마크 지속 시간 설정

• ->MinWarmUpTime(n) - 데이터 캐시(data caches)를 워밍업(warm up)하기 위함

• ->Name("...") - 사용자 정의 벤치마크 이름 할당

• ->Range(start, end) - 입력 크기 범위에 대해 프로파일링(profile)

• ->RangeMultiplier(n) - 범위 값 사이의 승수(multiplier) 설정

• ->ReportAggregatesOnly() - 집계된 통계(aggregated statistics)만 표시

• state.counters["name"] - 사용자 정의 성능 카운터(performance counters) 생성

• state.PauseTiming(), ResumeTiming() - 타이밍 측정(timing measurement) 제어

• state.SetBytesProcessed(n) - 처리된 바이트 수(number of bytes processed) 기록

• state.SkipWithError() - 에러 메시지와 함께 벤치마크(benchmark) 건너뛰기

• ->Threads(n) - 지정된 스레드(threads) 수로 벤치마크 실행

• ->Unit(kMicrosecond) - 보고를 위한 시간 단위(time unit) 설정

• ->UseRealTime() - CPU 시간(CPU time) 대신 실제 시간(real time) 측정

• ->UseManualTime() - GPU 및 IO 벤치마크를 위해 사용자 정의 타이밍(custom timings)을 제공하기 위함