Util

Active contributors: Antoine Pitrou, Sutou Kouhei, William Ayd, Rossi Sun

cpp/src/arrow/util/ is the kitchen sink of the Arrow C++ library — bit utilities, hashing, compression, the async runtime, threading, telemetry, decimal arithmetic, RLE encoding, UTF-8 handling, and more. Almost every other subsystem depends on at least a few headers here.

Major topic areas

Bitmaps

Validity bitmaps appear everywhere; performance hinges on these helpers.

• bit_util.h — bit-level helpers (SetBit, ClearBit, GetBit, popcount, leading/trailing zeros).
• bitmap.h, bitmap_ops.cc — bitwise AND/OR/XOR/NOT on bitmaps; bit-counting; copying with offset; the recently added OptionalBitmapAnd short-circuits when one bitmap is fully valid.
• bitmap_reader.h, bitmap_writer.h — byte-aligned readers and writers.
• bitmap_visit.h, bitmap_generate.h — iteration helpers.
• bit_block_counter.h — counts set bits in 64-bit blocks for branch-free null counting.
• bit_run_reader.h — yields runs of set/unset bits for filter optimizations.

Bit packing (RLE / Parquet)

Bit packing is its own subdiscipline — Parquet's RLE/dictionary encoding leans on high-throughput pack/unpack kernels.

• bpacking.cc, bpacking_internal.h — public unpacking entry points.
• bpacking_scalar*.{cc,h} — scalar fallbacks. bpacking_scalar_codegen.py generates bpacking_scalar_generated_internal.h (~5,900 lines).
• bpacking_simd_*.{cc,h} — SIMD variants for SSE4.2/AVX2/AVX-512/NEON. Generated by bpacking_simd_codegen.py and producing bpacking_simd512_generated_internal.h (~11,000 lines).
• byte_stream_split_internal.{h,cc} (with AVX2 variant) — Parquet's BYTE_STREAM_SPLIT encoding.
• rle_encoding_internal.h (~57 KB) — Parquet's RLE encoding/decoding.

Compression

compression.h defines arrow::util::Codec, the compression interface used by IPC, Parquet, and the dataset writer.

Codec	File
LZ4 (raw + frame)	compression_lz4.cc
ZSTD	compression_zstd.cc
Snappy	compression_snappy.cc
Brotli	compression_brotli.cc
Zlib (gzip + raw deflate)	compression_zlib.cc
BZ2	compression_bz2.cc

Async runtime

The async machinery is one of the more sophisticated parts of the library.

• future.h (~32 KB) — arrow::Future<T> with continuations (Then, AddCallback).
• async_generator.h (~78 KB — the largest header in util/) — pull-based async iteration. Defines composable operators: map, filter, transform, merge, flatten, queue, take.
• async_util.h, async_util.cc — task tracking, async completion barriers.
• thread_pool.h, thread_pool.cc — ThreadPool with capacity control. GetCpuThreadPool() returns the default singleton.
• task_group.h, task_group.cc — gathered concurrent execution.
• cancel.h, cancel.cc — StopToken for cooperative cancellation.
• counting_semaphore.cc, mutex.cc, concurrent_map.h, queue.h — primitive synchronization.

Decimal arithmetic

basic_decimal.h, basic_decimal.cc (46 KB) — fixed-precision decimal value types. decimal.h, decimal.cc (52 KB) — arithmetic, formatting, parsing. decimal_internal.h — internal helpers for cross-precision conversions.

UTF-8 / String

utf8.h, utf8.cc, utf8_internal.h (18 KB) — UTF-8 validation, code-point iteration, transformations. value_parsing.h, value_parsing.cc (30 KB) — string-to-typed-value parsing for CSV and JSON converters. formatting.h (~22 KB) — string formatting for value_to_string and pretty-print. string.h, string_util.h.

Hashing

hashing.h (34 KB) — open-addressing hash tables for unique value tracking and dictionary encoding. hash_util.h — hash function helpers. crc32.h, crc32.cc (64 KB — heavily templated) — CRC-32C used by IPC and the dataset writer.

CPU dispatch

cpu_info.h, cpu_info.cc — runtime CPU feature detection (CPUID on x86, /proc/cpuinfo on ARM, sysctl on macOS). dispatch_internal.h — generates a runtime function pointer based on CPU features. simd.h — SIMD intrinsic abstractions.

Logging and telemetry

logging.h, logging.cc — ARROW_LOG(level) macros. logger.h, logger.cc — pluggable logger interface for structured logging. tracing.h, tracing_internal.h, tracing_internal.cc — OpenTelemetry integration. Spans are emitted by Acero, Flight, and the dataset scanner.

Other helpers

File	Purpose
align_util.h	Pointer alignment helpers.
aligned_storage.h	Aligned std::aligned_storage_t workalike.
atfork_internal.{h,cc}	Hooks for pthread_atfork (used to recover thread pools after fork).
base64.h	Base64 encode/decode.
cache_internal.h	Per-CPU caches, MRU caches.
chrono_internal.h	Time-based helpers.
endian.h	Big/little-endian byte swaps.
float16.h	IEEE 754 half-precision.
formatting.h	Pretty-print helpers used by IPC, Parquet, CSV.
iterator.h	arrow::Iterator<T> (synchronous).
key_value_metadata.h	The canonical metadata container.
secure_string.h	Memory-zeroing string for secrets.
small_vector.h	Stack-allocated small-buffer vector.
tdigest.h	The t-digest streaming quantile sketch.
trie.h	Bytewise trie for token matching.
uri.h	URI parsing.
range.h, iterator.h	Range/iterator helpers.
ree_util.h	Run-end-encoded helpers.
byte_size.h	Total memory usage of arrays/tables.

Vendored

cpp/src/arrow/vendored/ (sibling directory, often grouped with util) holds tiny third-party libraries vendored into Arrow:

• xxhash/ — xxHash hashing.
• datetime/ — Howard Hinnant's date library.
• fast_float/ — fast float parsing.
• double-conversion/ — Google's double-to-string converter.
• pcg/ — random number generators.
• base64/, random/, ...

Each subdirectory has its own LICENSE.

How util is consumed

Almost every subsystem in the C++ library uses something from util/:

• Compute kernels use bit_util.h, bitmap_ops.cc, dispatch_internal.h.
• Acero uses future.h, async_generator.h, thread_pool.h, task_group.h.
• Parquet uses bpacking_*, compression*, crc32.h.
• Datasets use the async runtime + the filesystem helpers in io_util.h.
• Flight uses tracing_internal.h, cancel.h, future.h, secure_string.h.

This is why the directory is so large — it is a shared infrastructure layer.

Entry points for modification

• Adding a new compression codec: implement arrow::util::Codec and add a compression_<name>.cc. Register in compression.cc.
• Adding async helpers: extend async_generator.h for new operator semantics. Note that the file is huge — most additions should be small composable operators.
• Tuning bit-level operations: each bit_* header has a sibling bit_*_test.cc and bit_*_benchmark.cc. Run benchmarks before/after.