arXiv CSopen access

FastPair: GPU-Optimized String Decoding

Unknown · arxiv_cs

arXiv CS · Papers · License: Open Access

cloud distributedcomputing parallelcomputing

distributed computing, parallel computing, cloud

FastPair: GPU-Optimized String Decoding Joseph Isaacs1* , Francesco Gargiulo1,2* , Peter Boncz3 , Robert Kruszewski1 , Nicholas Gates1 , Rossano Venturini2 , Will Manning1 , Martin Prammer1† 3 CWI, Netherlands

Loghub Windows

ClickBench URL

233

985

171

923

849

1202

1063

Zstd (3)

1144

FSST-12

Zstd (-10)

436

500

OnPair-12

DE (best)

116

1000

OnPair-16

650

1620

1500

1529

Modern data systems compress data at rest and decompress it only when needed to preserve interconnect bandwidth. This design is often inefficient on GPU-based compute platforms because many conventional compression techniques exhibit serial data dependencies that limit GPU parallelism, leaving resources idle. Recent NVIDIA GPUs address this decoding deficiency through the Decompression Engine (DE), an on-die, fixed-function decompression accelerator for general-purpose compression formats such as Deflate, LZ4, and Snappy. Recent work has proposed string codecs that replace frequent substrings with fixed-width codes from a small, trained dictionary, making each code’s lookup independent. While these lookups can run in parallel, the resulting scattered reads and short output writes still do not align well with GPU hardware, which handles contiguous memory accesses more efficiently. We present FastPair, a GPU decoder that optimizes the existing dictionary decoding process by reorganizing lookups and assembling decoded substrings for contiguous output writes. On a B300, FastPair decodes ten real-world columns 2.4 to 4.2× faster than the DE, reaching up to 1.6 TB/s.

decode throughput (GB/s)

arXiv:2609.15034v1 [cs.DB] 14 Sep 2026

Abstract

151

2 University of Pisa, Italy

1405

1 Spiral, USA

Wikipedia

Figure 1. Decode throughput on a B300 for the three codecs FastPair decodes, the Decompression Engine (DE) at its best codec and chunk size per column, and software nvCOMPZstd at compression levels −10 and 3 (default frame size). The DE operates independently of the streaming multiprocessors (SMs). In this work, we investigate a software alternative that leverages a new class of compression techniques that expose enough independent work to use the SMs efficiently. Recent data management research has begun investigating alternatives to black-box compression techniques, such as those the DE can decode. These works have proposed cascading several data-specific lightweight compression techniques [2, 15, 21, 27, 41, 47]. These lightweight encodings preserve efficient access to individual values, allowing a query to retrieve a few values without decompressing an entire block [1, 4, 7, 14]. Together, these encodings can be applied iteratively, yielding compression ratios comparable to those of existing black-box techniques. Crucially, finegrained accesses also enable parallel decoding. We focus on FSST [7] and OnPair [14], which compress strings by replacing frequent substrings with fixed-width codes. Each code indexes a trained dictionary of short byte strings, called tokens; decoding retrieves these tokens and concatenates them. These lookups can be performed in parallel because each lookup depends only on its code and the trained dictionary. The main differences among these FSST-family codecs stem from their dictionaries. For example, longer tokens can improve compression because a single code replaces more input bytes. However, storing longer tokens may require larger dictionaries. OnPair tokens can be up to 16 bytes, while FSST tokens can be up to 8 bytes. Although their encoders differ, these codecs share the same dictionary-lookup

Introduction

Data is typically stored in compressed form when not in use [11, 16, 38]. When a data analytic query requires it, data must travel to the compute unit and be decompressed along the way. Decompressing at any point during the transfer sends the larger, decompressed form over one or more interconnects. Thus, decompressing on the device that performs the compute is often ideal. However, decompressing on the computing device helps only if the decoder runs efficiently on that device. Widely used compression techniques were designed for CPUs with out-of-order, superscalar cores and often contain serial decoding dependencies. In contrast, GPUs rely on many independent threads to keep their execution units busy. Thus, serial decoding dependencies may leave a ported decoder with too little parallel work to use the device efficiently [31, 35, 40]. The decoder’s output rate then limits downstream operators that consume those bytes [17, 23, 33, 46]. NVIDIA’s Blackwell datacenter GPUs address this problem with the Decompression Engine (DE), a fixed-function hardware accelerator for Deflate, LZ4, and Snappy [20, 24, 25, 28]. * Joseph Isaacs and Francesco Gargiulo contributed equally to this work.

†Martin Prammer is the corresponding author ([email protected]). 1

Isaacs, Gargiulo, et al.

Table 1. The five GPUs used throughout this work. All five devices carry a 65 536-register file per SM. GPU

Architecture

Mem.

B300 H100-SXM 80 GB A100-SXM 40 GB RTX PRO 6000-SE L40S

Blackwell Ultra Hopper Ampere Blackwell Ada Lovelace

10.3 9.0 8.0 12.0 8.9

HBM3e HBM3 HBM2 GDDR7 GDDR6

Peak Mem. BW

SMs

Max Warps/SM

SRAM/SM

Max Shared Mem./SM

8.0 TB/s 3.35 TB/s 1.56 TB/s 1.60 TB/s 0.86 TB/s

148 132 108 188 142

64 64 64 48 48

256 KiB 256 KiB 192 KiB 128 KiB 128 KiB

228 KiB 228 KiB 164 KiB 100 KiB 100 KiB

decoding process. Overall, dictionary lookups expose parallelism opportunities within and across strings, reducing serial dependencies that limit conventional GPU decoding. Thus, this family of compression codecs offers an opportunity to design an optimized GPU decoder. However, this optimized decoder must still address several remaining challenges, such as organizing those lookups and their output for the GPU’s memory system. Consecutive codes can refer to unrelated dictionary entries, while variable token lengths make output positions depend on all preceding token lengths. These scattered reads and short output writes fit poorly with hardware that most efficiently serves contiguous accesses from neighboring threads. In this work, we present FastPair, a GPU decoder that optimizes dictionary decoding by reorganizing dictionary lookups and assembling decoded tokens for contiguous output writes. FastPair’s design is based on the following three considerations: First, OnPair’s CPU decoder locates a token by reading its offset from a table and then fetching the token at that offset. Although lookups for different codes are independent, each lookup still requires two dependent reads. FastPair prepares fixed-size dictionary entries so that a thread can compute the token’s address directly from the code, eliminating this dependency. Furthermore, the sixteen-byte entries needed for OnPair do not always need to be read in full, as many tokens contain eight bytes or fewer. FastPair splits the dictionary into low- and high-byte planes; this split read optimization allows FastPair to read eight bytes per token, fetching the remaining bytes only for longer tokens (Section 3). Next, writing these tokens in parallel requires knowing their output positions, which depend on the lengths of preceding tokens. FastPair precomputes output positions when the column is compressed, so that decoding does not have to recover them from the start of the code stream. It stores one position for each fixed-size group of codes, which we call a batch. Threads assigned to a batch start at its stored position and sum token lengths in parallel to determine their individual destinations. This additional metadata, the sidecar, adds about 1% of data overhead to the stored column (Section 3.1). Finally, while knowing the output positions makes writes independent, it does not necessarily make them efficient, as each thread performs a small write. FastPair first assembles the tokens in a shared-memory buffer on the SM, then uses

neighboring threads to copy contiguous parts of the completed batch to device memory. This optimization lets the hardware combine, or coalesce, these contiguous writes into fewer memory accesses (Section 3). Across the ten real-world data columns we explore, FastPair decodes at 2.4 to 4.2× the DE’s rate on a B300. It reaches 1.6 TB/s when decoding Loghub Windows with OnPair-16, 2.5× the DE’s rate (Figure 1). We perform two studies to better understand FastPair’s decoding performance: First, we conduct a sensitivity study to understand how FastPair’s design choices interact with the input data and the GPU’s on-chip resources (Section 4). Per-thread overheads can be better amortized by assigning each thread more codes to process; however, this optimization requires more registers and shared memory, which can limit parallelism. The token-length distribution also matters: split reads help when short tokens are common, whereas reading the full entry at once avoids a second read for long tokens. Then, we use hardware counters to examine how dictionary reads and decoded output assembly use the GPU’s memory system. While FastPair coalesces writes to device memory, assembling the output still requires many short shared-memory writes. Together with the scattered dictionary reads, these writes can saturate the L1 cache’s access pipeline while device-memory bandwidth remains available (Section 5.2). Consistent with this on-chip limit, decoding on the three GPUs with high-bandwidth memory (HBM) scales nearly linearly with SM clock speed across the evaluated columns while memory clocks remain fixed (Section 5.3). The work is structured as follows: Section 2 describes the codecs and GPU mechanisms FastPair uses. Then, Section 3 presents the FastPair decoder. We explore and measure FastPair’s design choices in Section 4. Section 5 evaluates FastPair and examines how FastPair uses GPU resources. Section 6 discusses prior work. Finally, we conclude and discuss future work in Section 7.

Background

In this section, we discuss the string codecs FastPair decodes, including how their dictionaries are built (Section 2.1) and OnPair’s original CPU-optimized decoder (Section 2.2). Then, we discuss the architectural components that enable highperformance parallel decoders on GPUs (Section 2.3). 2

FastPair: GPU-Optimized String Decoding

Table 2. Dictionary statistics and compression ratios, per column and codec. |𝐶𝑜𝑑𝑒𝑠 | is the number of distinct codes that appear in the encoded column. 𝐿𝑒𝑛 is the mean decoded bytes per code. ≤8B is the share of decoded codes whose token is eight bytes or fewer. CR is the compression ratio; for baselines, CR 𝑓 is the CR of the fastest-decoding (B300) configuration, while CR↑ is the best CR found. Real-world columns appear above the divider while synthetically generated columns are below. OnPair-16

OnPair-12

FSST-12

Zstd

gANS

(Dataset) Column

|𝐶𝑜𝑑𝑒𝑠 | 𝐿𝑒𝑛 ≤8B CR

|𝐶𝑜𝑑𝑒𝑠 | 𝐿𝑒𝑛 CR

CR 𝑓 CR↑

FineWeb2 Mandarin Wikipedia CodeParrot Loghub Android ClickBench URL ClickBench Title Loghub HDFS Loghub Thunderbird Loghub Spark Loghub Windows

65 426 4.9 65 428 5.6 65 231 6.1 61 629 9.3 64 428 8.6 64 802 10.1 63 932 9.0 59 823 11.0 62 485 11.2 37 853 12.1

TPC-H c_address TPC-H l_comment TPC-H o_clerk TPC-H l_shipinstruct TPC-H ps_comment

65 180 2.2 100% 1.1 64 971 10.4 33% 5.2 45 000 15.0 0% 7.5 5 9.6 40% 25.2 65 049 12.7 16% 6.3

2.1

89% 82% 77% 43% 51% 37% 48% 23% 21% 18%

2.5 2.8 3.0 4.6 4.3 5.0 4.5 5.5 5.5 6.0

4 045 3.0 100% 4 047 3.2 98% 4 059 3.5 93% 3 930 4.2 86% 4 012 4.7 81% 4 026 5.7 79% 3 617 6.7 63% 3 541 7.6 55% 3 640 8.3 42% 3 551 10.1 37%

2.0 2.1 2.3 2.8 3.1 3.8 4.4 5.0 5.5 6.7

4 030 3 771 3 917 3 686 3 678 2 660 1 413 2 225 2 037 1 793

2.4 2.7 2.9 3.0 3.2 3.0 3.9 3.5 4.0 4.5

1.6 1.8 1.9 2.0 2.1 2.0 2.8 2.4 2.9 3.3

1.3 2.0 1.6 2.7 4.4 4.4 8.2 8.2 6.5 6.5 6.0 6.0 10.9 11.0 19.0 19.0 15.4 15.5 9.9 18.3

1.1 2.6 1.4 3.3 2.2 5.3 3.2 15.2 6.0 9.1 6.3 9.7 9.7 13.6 5.1 26.5 15.4 19.8 18.7 137.7

1.3 1.6 1.7 1.5 1.4 1.7 1.6 1.5 1.6 1.6

3 904 1.9 100% 1.3 3 862 7.7 58% 5.1 3 837 7.7 48% 5.1 5 9.6 40% 25.2 3 865 10.3 32% 6.8

3 904 1 044 783 8 936

1.9 1.3 4.0 3.1 3.8 3.0 6.0 15.8 4.9 3.9

1.0 1.3 4.6 4.6 2.8 5.3 25.0 25.2 5.8 5.8

0.9 1.2 1.9 4.2 6.7 6.8 24.3 28.1 4.7 6.4

1.3 1.9 2.2 2.1 1.9

1.3 1.9 2.3 2.1 1.9

Dictionary-Compressed Strings

Table 2 lists the columns from each dataset we explore in this work. Their compression-related statistics follow from three differences in dictionary construction: a codec’s training procedure, code width, and maximum token length. FSST and OnPair use different dictionary training methods. FSST trains over several passes on a sample, concatenating frequent adjacent code pairs into longer tokens and keeping those that cover the most sample bytes, a process that fills small dictionaries well. OnPair instead merges frequent adjacent substrings in a single sequential pass, following byte-pair encoding [13] and its relative Re-Pair [22], but merging as it scans rather than tracking where each pair occurs. Because a merge joins two entries already in the dictionary, tokens lengthen as training proceeds. FSST-family encoding techniques use fixed-width codes, so the code width (or maximum dictionary cardinality) determines how many entries a dictionary can address. The maximum token length sets an upper bound on how many bytes a single code may expand to. In this work, we evaluate OnPair-16, OnPair-12, and FSST-12, where the suffix indicates the code width: -16 and -12 address up to 65 536 and 4 096 entries, respectively. FSST-12 caps the maximum token length at 8 bytes, while OnPair-16 and OnPair-12 cap it at 16 bytes. These differences are visible in Table 2: At the same code width, OnPair-12’s mean token length is longer than FSST-12’s in every column except c_address, whose values are random characters. Notably, none of these three techniques requires escape codes: markers for literals the dictionary cannot represent. Both FSST-12 and OnPair-16/-12 place all one-byte literals in

Dictionary encodings and their use for compression are long established [36]. Their re-emergence is part of a broader trend in data management research exploring lightweight compression techniques and their interactions with data analysis tasks [4, 5, 8, 18, 19, 21, 40, 41, 47]. These techniques enable random access to compressed data, eliminating the need to decompress large blocks to extract scattered values. Random access to values also enables highly parallel decoding, which generally aligns with heterogeneous data management platforms such as GPU-based data analytic engines [6, 17, 46]. In this work, we focus on lightweight string codecs. Older formats derive the dictionary from the text itself: LZW extends it while scanning [42], and LZ77 replaces repeated segments with back-references to earlier positions [49]. Thus, both techniques require decoding a block from its start to recover any value. In contrast, the two lightweight string codecs we explore in this work, FSST [7] and OnPair [14], train a dictionary whose entries remain fixed during decoding. These FSST-family techniques rewrite each row as dictionary codes, where each code indexes a stored bytestring token; given this dictionary, each dictionary code can be looked up without decoding the preceding text. Cascaded encoding techniques apply a sequence of lightweight encodings [2, 15, 21, 27, 41, 47]. FSST-family encodings particularly benefit from these optimizations, as they encode string data into an integer form that can then benefit from a variety of numeric-specific lightweight encodings [1, 3, 4, 18, 34, 44]. 3

Isaacs, Gargiulo, et al.

2.2

Listing 1. OnPair’s CPU decoding loop.

In this section, we examine OnPair’s CPU decoder (Listing 1). OnPair’s decoder uses a four-way-unrolled loop. It reads a code and its packed offset and length, copies sixteen bytes, and advances the output cursor by the true token length. Fetching the token requires two dependent reads: the table entry supplies the address for the token load. Note that this loop is already optimized for CPUs: copying a constant sixteen bytes and advancing by the true length is branch-free. Further, this sequence lowers to one unaligned 128-bit store on x86-64 and AArch64. Finally, because tokens are written in stream order, the next write overwrites the excess bytes from the previous copy.

let c = *codes_ptr.add(i + k) as usize; let entry = *table_ptr.add(c); // u64 = (off<<16)|len let off = (entry >> 16) as usize; let len = (entry & 0xffff) as usize; std::ptr::copy_nonoverlapping( dict_ptr.add(off), cursor, crate::MAX_TOKEN_SIZE, // always 16 ); cursor = cursor.add(len); // advance by true len

Table 3. Terms used throughout this paper. Some definitions conflict across vendors; we use NVIDIA terminology.

2.3 Term

Definition

Streaming multiprocessor: an execution unit with its own registers, scratchpad, and L1. Per-thread storage allocated from each SM. The unit that executes the kernel body. A group of threads assigned to the same SM. Scratchpad on each SM, shared within a block. The split of an SM’s single SRAM array between shared memory and L1, requested by the kernel.

warp lane resident blocks launch bounds

device memory global memory sector wavefront

CPU-based String Decoding

GPU Architecture

Because GPU terminology is often vendor-specific, we define the terms used throughout this work in Table 3. Table 1 identifies the capabilities of the devices used in this work. A GPU delivers data to its streaming multiprocessors (SMs) via device memory, a GPU-wide L2 cache, and per-SM SRAM, which serves as the L1 cache and shared memory (a scratchpad). A kernel can request that SRAM be allocated as shared memory rather than L1, known as the carveout. Unallocated SRAM is used for the L1 cache [29]. Larger shared-memory allocations reduce the L1 space available for dictionary reads. An SM hides memory latency by keeping several warps resident and switching between them. The resident warp count relative to the hardware maximum is known as its occupancy. Warps are assigned to an SM in groups called thread blocks (blocks). Each block reserves registers and shared memory; thus, larger allocations can leave room for fewer blocks and, consequently, fewer resident warps. However, raising occupancy is not always beneficial. For example, coarsening, the process of assigning additional work to each thread, can improve performance [39]. While coarsening gives each thread more work and uses more per-thread resources (such as registers), lowering occupancy, it better amortizes per-thread overheads. While keeping more work in flight helps hide memory latency, memory-access throughput is limited by how quickly the L1 pipe can process requests. A warp’s global-memory instruction produces a single request containing the addresses requested by all participating lanes. The hardware divides this request into wavefronts, where a pipeline stage processes one wavefront per cycle. Requests requiring several wavefronts consume more of the L1 pipe’s processing capacity, even if all their data is cached. Shared-memory reads and writes also consume the L1 pipe’s processing capacity [26]. We distinguish the L1 pipe’s access rate, measured in wavefronts per cycle, from the cache’s byte bandwidth, measured in bytes per cycle. When the 32 lanes of a warp read contiguous, aligned addresses, GPU hardware can merge the lanes’ reads into a few wide accesses. When those same lanes read

A group of 32 threads executing common instructions (i.e., single-instruction, multiple-thread). A thread’s position within its warp. Blocks an SM holds at once. Compile-time parameters: threads per block (𝑇 ) and requested blocks per SM (𝐵). Together, they bound a kernel’s register allocation. GPU DRAM. The address space every thread can reach. An aligned 32-byte portion of a cache line. A 128-byte L1 cache line contains four sectors. The unit of work the L1 pipe processes in one cycle. One warp’s memory instruction becomes one or more wavefronts [26].

their dictionaries, eliminating the need for such codes. FSST8 and its 255-entry dictionary cannot include all one-byte literals; instead, any missing byte is stored immediately after the reserved escape code. A decoder starting at an arbitrary input position must therefore determine whether the starting byte is a dictionary code or a literal following an escape. Without escapes, threads can begin dictionary lookups at any fixed-width code boundary without inspecting preceding input. This allows the input to be divided into fixed-size groups of codes for parallel processing. However, fixed-size groups of codes can expand to different numbers of bytes. Thus, writing their output into a single packed buffer requires knowing the total decoded length of the preceding groups. 4

FastPair: GPU-Optimized String Decoding

Table 4. Definitions of warp primitives used in Algorithm 1.

Algorithm 1 The FastPair Decoding Algorithm Require: lane ℓ ∈ [0, 32), 32 ·𝐾 codes, output out at cursor Require: dictionary planes dict lo , dict hi ; token lengths lens Require: 𝐾, tokens per thread Require: 𝑊 , token bytes in dict lo Require: 𝐻 , rounds of queued reads held across the emit Require: |𝑐 |, |len|, |off |, |lo| = 𝐾; |hi| = 𝐻 per lane 1: for 𝑘 ← 0 . . . 𝐾 − 1 do 2: 𝑐 𝑘 ← codes[ℓ + 32𝑘] 3: len𝑘 ← lens[𝑐 𝑘 ] 4: lo𝑘 ← dict lo [𝑐 𝑘 ]

Returns a 32-bit mask whose bit ℓ is set when lane ℓ’s predicate 𝑝 is true. Counts the set bits in mask 𝑚. Counts the set bits in 𝑚 below bit ℓ, giving that lane’s position in the queue. Returns exclusive byte offsets for all 32𝐾 tokens in stream order, ℓ + 32𝑘, and their total decoded length. Waits for all 32 lanes and orders their memory accesses so prior shared-memory writes are visible to subsequent reads.

SyncWarp

⊲ scan

7: 𝑛 ← 0 ⊲ queue 8: for 𝑘 ← 0 . . . 𝐾 − 1 do 9: 𝑚 ← Ballot(len𝑘 > 𝑊 ) 10: if len𝑘 > 𝑊 then 11: queue[𝑛 + Rank(𝑚, ℓ)] ← (𝑐𝑘 , off 𝑘 +𝑊 , len𝑘 −𝑊 )

These scattered accesses can exhaust the cache’s access rate while its byte bandwidth remains available. To output decoded values, the threads must also recover the positions the CPU decoder obtains by advancing its cursor. A warp’s parallel prefix sum computes these positions by summing token lengths across lanes, using a handful of warp shuffles rather than a serial pass over the tokens (Section 3.2).

𝑛 ← 𝑛 + PopCount(𝑚) 13: SyncWarp 12:

⊲ hoist

⊲ dict hi reads

17: for 𝑘 ← 0 . . . 𝐾 − 1, 𝑗 ← 0 . . .𝑊 − 1 do 18: if 𝑗 < min(len𝑘 ,𝑊 ) then 19: scratch[shift + off 𝑘 + 𝑗] ← lo𝑘 [ 𝑗]

⊲ emit

𝑞 ← queue[ℓ + 32𝑟 ] 𝑣 ← hi𝑟 if 𝑟 < 𝐻 else dict hi [𝑞.𝑐] for 𝑗 ← 0 . . . 𝑞.len − 1 do scratch[shift + 𝑞.off + 𝑗] ← 𝑣 [ 𝑗] ⊲ drain

26: SyncWarp 27: head ← min((16 − shift) mod 16, total) 28: body ← ⌊(total − head)/16⌋ 29: 𝑡 ← head + 16 body 30: if ℓ < head then 31: out [cursor + ℓ] ← scratch[shift + ℓ]

⊲ head

32: for 𝑘 ← ℓ to body − 1 step 32 do ⊲ aligned body 33: out [cursor+head +16𝑘] ← scratch[shift +head +16𝑘] 34: if ℓ < total − 𝑡 then 35: out [cursor + 𝑡 + ℓ] ← scratch[shift + 𝑡 + ℓ]

Design

Algorithm 1 presents the FastPair decoder and its stages, which use warp primitives from Table 4. Decoding a dictionary-compressed string requires reading a code, looking up its token, and appending the token’s bytes to the output. This process has multiple properties that make parallel decoding difficult. First, output placement depends on all previous tokens because tokens are concatenated without padding. Second, locating a token requires two dependent reads: the offset table must be read before the token’s bytes. Third, each token is written to the output in a short, unaligned copy. To address these challenging properties, FastPair uses precomputed offsets and a parallel prefix sum to resolve output placement. Further, its fixed-stride dictionary layout makes each token directly addressable from its code, while staging coalesces writes to device memory. However, these optimizations consume other contested resources, creating trade-offs that we explore in Section 3.3.

20: for 𝑟 ← 0 . . . 𝐾 − 1 do 21: if ℓ + 32𝑟 < 𝑛 then

36: cursor ← cursor + total

Ballot(𝑝)

WarpPrefixSum(len)

⊲ 𝑊 bytes

5: off , total ← WarpPrefixSum(len) 6: shift ← cursor mod 16

22: 23: 24: 25:

Definition

PopCount(𝑚) Rank(𝑚, ℓ)

⊲ input, gather

14: for 𝑟 ← 0 . . . 𝐻 − 1 do 15: if ℓ + 32𝑟 < 𝑛 then 16: hi𝑟 ← dict hi [queue[ℓ + 32𝑟 ].𝑐]

Primitive

⊲ tail

3.1

Design Overview

FastPair distributes decoding across many GPU threads, each handling a small portion of the code stream. Within a warp, threads cooperate on a batch of consecutive codes. Each thread processes 𝐾 codes, resulting in each warp processing 32 · 𝐾 codes per batch. Each warp reads its batch’s output position (cursor) from the sidecar before decoding. The sidecar stores each batch’s starting location. By recording this information at compression time, each warp can start without waiting for earlier

⊲ next batch

32 unrelated addresses, their reads may span 32 different sectors, even though each lane needs only a few bytes. Depending on the addresses and access width, serving the same number of sectors may require one wavefront or several [26]. 5

Isaacs, Gargiulo, et al.

batches. Including the sidecar in the compression output adds about 1% of storage overhead. We observe that, for the columns explored in this work, regenerating the sidecar at decode time instead results in about 20% slower decoding, and up to 35% on short-token columns. The decoding penalty tends to be larger for columns with shorter tokens because regeneration processes more codes per decoded byte. Within a batch, threads fetch and decode their tokens independently, using a parallel prefix sum of token lengths to determine each token’s local output position. Each thread writes its decoded output to a shared-memory buffer, enabling neighboring threads to copy contiguous segments to device memory via coalesced writes. 3.2

aligned 16-byte chunks, so most of the output uses coalesced stores. To align these copies, the first token is placed at a scratch-buffer offset of cursor modulo 16, aligning the buffer with the destination. Any unaligned head and trailing bytes are copied individually, so no write extends into another batch. 3.3

Performance Modeling

FastPair’s batch size determines how much work each warp performs before draining its output. Larger batches amortize the scan and drain overheads, but also require more registers and shared memory. Hoisting introduces a similar trade-off: keeping more reads in flight requires registers to hold their results. In this section, we model these resource requirements to understand how 𝐾 and 𝐻 affect the number of blocks that can reside on each SM (Table 1). First, each SM has a fixed number of warp slots, 𝑁 𝑤 . A block of 𝑇 threads occupies 𝑇 /32 of them, one per warp, so at most ⌊𝑁 𝑤 /(𝑇 /32)⌋ blocks are ever resident. The three HBM-based devices in our evaluation set 𝑁 𝑤 = 64, while the GDDR ones set 𝑁 𝑤 = 48 (Table 1). Next, each SM has a fixed-size register file: 𝑅 = 65 536, with 32-bit registers, for every GPU we evaluate. Each SMresident thread draws from this shared pool. The launchbound parameter 𝐵 asks the compiler to budget registers for at least 𝐵 blocks of 𝑇 threads per SM [29]. This gives a perthread register limit of approximately 𝑅/(𝑇 · 𝐵); increasing 𝐵 leaves fewer registers for each thread. Note that this compiler target does not guarantee that 𝐵 blocks fit under the other resource constraints. Further, coarsening and hoisting both require register space. Each of a thread’s 𝐾 codes requires registers for the code itself, the token’s length, the output offset, and its lowplane bytes. Each hoisted round retains one high-plane value per lane. Using 𝐿 for the maximum token length supported by the kernel and 𝑐 for the per-thread overhead state, an approximate register-limit condition for a pair (𝐾, 𝐻 ) is: 𝑊 𝐿 −𝑊 𝑅 𝐾 3+ +𝐻 +𝑐 ≤ 4 4 𝑇 ·𝐵

Decode Stages

In this section, we walk through the FastPair decoder stages step by step. These stages are labeled in Algorithm 1. The first stage is the input stage, where lanes read consecutive codes in 𝐾 rounds, keeping input accesses coalesced. This input feeds the gather stage, where each thread reads the length and the first 𝑊 bytes of each of its 𝐾 tokens. Because each token is directly addressable from its code (an index into a fixed-stride dictionary), FastPair does not require a dictionary offset table. The dictionary is stored as two planes: a low plane holding 𝑊 bytes per entry, read for every token, and a high plane holding the remaining bytes (also at a fixed stride), read only for tokens longer than 𝑊 . For OnPair, 𝑊 = 8 induces split reads, while 𝑊 = 16 fetches the full dictionary entry at once. Token lengths are packed into nibbles in a separate table, storing each token’s length minus one. As the length read and the token read depend only on the original code, they can proceed independently. After the gather-stage reads finish, a warp scan resolves the batch-local offsets for each token by summing the lengths of preceding codes. Adding these offsets to cursor gives the final output positions. If any tokens longer than 𝑊 bytes are present, an additional lookup is queued for the remaining bytes, allowing the warp to redistribute this extra work across its lanes. Within each input round, a warp Ballot identifies the lanes holding long tokens; a prefix count assigns their requests to consecutive queue slots. The warp processes the completed queue in rounds of up to 32 requests, one per lane. Before outputting the batch, the warp hoists the first 𝐻 rounds of queued reads, so those loads are in flight before the emit begins. Then, each thread emits the first 𝑊 bytes of each token to a shared-memory staging buffer (scratch), or the entire token if it is shorter. The scanned offsets assign each token a disjoint range, so these writes can proceed in parallel without the overlapping copies used by the CPU decoder. Threads handling queued reads fill the remaining bytes of long tokens. Once the batch is fully staged, the warp drains the buffer to global memory. Neighboring lanes copy consecutive,

This construction allocates one register each for a code, its token length, and its offset. An additional 𝑊 /4 registers store low-plane dictionary bytes, and (𝐿−𝑊 )/4 store hoisted high-plane bytes. Note that at 𝑊 = 𝐿, every token fits in the low plane, so there are no high-plane bytes or a request queue, eliminating the impact of 𝐻 . Finally, each block reserves shared memory for its warps’ staging buffers and request queues. Increasing 𝐾 requires more output space and queue slots, increasing the per-block allocation 𝑀 (including overheads). If 𝐴 bytes of shared memory are available per SM, at most ⌊𝐴/𝑀⌋ such blocks fit. Each of the established constraints may limit how many blocks an SM holds at once (given 𝑟 registers per thread and 𝑁 𝑤 warp slots per SM): 6

B=1

2000

B=4

B=8 18

1500 1000

500

blocks/SM

decode throughput (GB/s)

FastPair: GPU-Optimized String Decoding

0 1

4 6 K (tokens per thread)

decode throughput T=64

T=128

blocks/SM T=256

T=64

T=128

T=256

Figure 2. Decode throughput and blocks/SM when varying 𝐾, across multiple combinations of launch bounds (𝑇 = {64, 128, 256}, 𝐵 = {1, 4, 8}). B300, Loghub Windows, OnPair-12 (𝑊 = 8, 𝐻 = 1).

min

Q4 Would staging the dictionary in shared memory result in faster decoding? (Section 4.4) Q5 How does mean token length affect decode rate? Does this depend on whether the dictionary fits in the L1 cache? (Section 4.5)

𝐴 𝑅 𝑁𝑤 , , 𝑀 𝑇 ·𝑟 𝑇 /32

For example, at 𝑇 = 256, 𝐵 = 4, 𝐾 = 6, and 𝑊 = 8, the per-thread register limit is 64 registers. A block occupies 31.25 KiB, so four resident blocks require 125 KiB. The three HBM GPUs make between 164 and 228 KiB available, which is enough for all four blocks, while the two GDDR devices make only 100 KiB available, which fits only three blocks. Increasing the tokens decoded per thread (𝐾) increases the required shared memory, which in turn can reduce the L1 cache available for the dictionary. At OnPair-12, the low plane is 32 KiB for split reads (𝑊 = 8); at OnPair-16, it is 512 KiB at the same width, larger than any evaluated GPU’s total per-SM SRAM. The compiler can also add to this cache pressure, as registers it cannot keep spill to local memory, perthread device-memory storage cached like any other access; these spilled-register reads then compete with dictionary reads [29]. In the next section, we explore the impact of these parameters through multiple sensitivity studies.

Unless stated otherwise, rates are reported in GB/s using the minimum time from at least 100 decodes on a B300, at its boost clock. 4.1

Kernel Launch Parameters

To better understand decoder parallelism limits, we examine the effects of 𝐾 (tokens per thread) and the launch bounds 𝑇 (threads per block) and 𝐵 (resident blocks requested). We sweep these parameters by decoding the Loghub Windows column on a B300 using OnPair-12 (𝑊 = 8, 𝐻 = 1). The results of this study are shown in Figure 2. As 𝐾 increases, each thread performs more work and requires more registers. We observe similar behavior at 𝐵 = 1 and 𝐵 = 4, whereas 𝐵 = 8 behaves differently. At 𝑇 = 256, increasing 𝐵 from 4 to 8 halves the register limit to 32 per thread. For these parameters, after 𝐾 = 5, the kernel spills registers to local memory and reduces residency from eight blocks to five. These spills add L1 accesses that compete with dictionary reads; thus, even though more blocks can reside than at 𝐵 = 4, this kernel decodes more slowly. Based on these experiments, we recommend 𝑇 = 256, 𝐵 = 4, and 𝐾 = 6 as the default launch configuration on the B300, as it achieves the highest decode rate in the sweep and provides capacity for four blocks per SM without spilling.

Microbenchmarks

This section addresses the following questions through a set of targeted experiments: Q1 How do the 𝐾 (tokens per thread), 𝑇 (threads per block), and 𝐵 (resident blocks requested) parameters impact FastPair’s decode rate? (Section 4.1) Q2 Does issuing the long-token reads early (the hoist stage) make decoding faster? (Section 4.2) Q3 Does unconditionally fetching only part of each dictionary entry result in a faster decoder? Is this benefit data-dependent? (Section 4.3)

4.2

Hoisted Reads

To evaluate the impact of hoisting reads, we perform a sensitivity study by decoding the Loghub Windows column using OnPair-12 (𝑊 = 8) on a B300, varying 𝐾 (tokens per thread) 7

H (held rounds)

B=1

B=4

B=8

1477 1476 1519 1479 1421

1462 1380 1515 1477 1414

1211 1060 925

934

905

1375 1464 1474 1507 1463 1412

1375 1466 1477 1506 1455 1422

1457 1225 1045 940

846

925

1253 1377 1458 1373 1515 1467 1413

1183 1379 1459 1466 1525 1454 1426

1403 1448 1294 1085 921

879

924

832 1155 1362 1483 1473 1423 1470 1418

833 1217 1370 1481 1474 1510 1460 1428

1223 1411 1458 1375 1134 754

877

962

782 1162 1383 1472 1464 1435 1383 1424

781 1163 1382 1482 1473 1520 1471 1417

1197 1410 1465 1376 1014 1023 900

976

2 4 6 K (tokens per thread)

1500 1250 1000 750

decode throughput (GB/s)

Isaacs, Gargiulo, et al.

Figure 3. Decode throughput when varying (𝐾, 𝐻 ). (𝑇 = 256, 𝐵 = {1, 4, 8}). B300, Loghub Windows, OnPair-12 (𝑊 = 8). 4.3

and 𝐻 (held rounds of hoisted reads) across launch configurations (𝑇 = 256, 𝐵 = {1, 4, 8}). The results of this experiment are shown in Figure 3. The hoist does not improve the highest-performing configuration (𝑇 = 256, 𝐵 = 4, 𝐾 = 6): at 𝐾 = 6 the coarsened loop already has enough independent loads in flight to hide their latency (Section 4.1). The hoist matters at (𝐵 = {1, 4}, 𝐾 = 1), where too few loads are outstanding to hide the latency of any one of them. Issuing the high-plane reads before the emit stage leaves fewer warps stalled on an outstanding load.1 We use 𝐻 = 1 by default, which holds one round, and drop to 𝐻 = 0 only when the compiler reports a register spill. Register utilization also explains why hoisting degrades performance under the tighter register limit at 𝐵 = 8, where, at 𝐾 = 4, increasing 𝐻 to two triggers spilling and reduces performance. Here, the additional register pressure causes registers to spill to local memory. Because local memory traffic is cached in L1, spilled registers compete with the dictionary.

Splitting decoding dictionaries into a low plane and high plane lets a single indexed load serve every token of at most 𝑊 bytes, while longer tokens require a second (high-plane) lookup. This optimization enables narrower reads, which may require fewer L1 wavefronts even when the same number of sectors are accessed (Section 2.3). The benefit of this split therefore depends on the data: specifically, the portion of a column’s tokens the low plane can serve on its own. We show the results of exploring 𝑊 in Figure 4. The narrow read (𝑊 = 8) is slower than the full read (𝑊 = 16) when long tokens are common. An extreme example is the o_clerk column decoded by OnPair-16, where no token is eight bytes or fewer, and the narrow read is 23% slower. The narrow read begins to outperform the full read once the low plane serves more than about 40% of a column’s tokens. The most beneficial columns for the narrow read, using OnPair-12, are c_address and the FineWeb2 Mandarin columns, which decode 1.38× and 1.35× faster, respectively. This behavior supports automatic kernel selection, since the encoder already holds the token-length histogram when it writes the dictionary. We recommend defaulting to split reads (𝑊 = 8) and disabling them (𝑊 = 16) when over 60% of a column’s tokens exceed eight bytes.

1 At (𝑇 = 256, 𝐵 = 1, 𝐾 = 1), where 𝐻 = 1 improves on 𝐻 = 0 by 6.4%, the

share of warp cycles stalled on an outstanding L1 load falls from 39.4% to 33.2%, while the shared-memory and memory-queue stalls rise.

OnPair-16 OnPair-12

1.2

4.4

1.0 0.8 0.0

0.2 0.4 0.6 0.8 fraction of tokens 8 bytes

≤

Shared-Memory-Resident Dictionaries

Prior GPU-based FSST-decoding work stages the dictionary in shared memory, eliminating the global-memory gather [40]. While this approach works well for FSST’s small dictionary, larger dictionaries pose two challenges: First, they may not fit in shared memory. Second, staging a dictionary in each thread block consumes shared memory, potentially limiting the number of resident blocks. We therefore measure the impact of staging the decoding dictionaries in shared memory when decoding the Loghub Windows column using a B300. OnPair-16’s low plane alone is 512 KiB, so it cannot fit in the B300’s shared-memory carveout (228 KiB; Table 1).

decode throughput = 8 / = 16

1.4

Gather Width

1.0

Figure 4. Ratio of the best decode throughputs found for 𝑊 = 8 and 𝑊 = 16, per column. Columns are organized by their fraction of tokens ≤ 8 bytes. B300, OnPair-16 and -12. 8

decode throughput (GB/s)

FastPair: GPU-Optimized String Decoding

Where staging does fit, it is slower: by 26% at OnPair12 (1131 GB/s against 1527 GB/s) and by 54% at FSST-12 (643 GB/s against 1409 GB/s). We investigate performance counters to better understand the impact of staging the dictionary in shared memory, profiling the best staging kernel variant against the non-staging kernel for this column. At OnPair-12, staging cuts global load sectors from 209 million to 7.6 million per launch, and the sectors each request touches from 17.4 to 1.9, indicating that the global-memory gather is gone. However, shared-memory bank conflicts rise from 61 million to 91 million, occupancy falls from 52% to 24%, and the L1 pipe falls from 99% to 76% of its access-rate limit rather than being freed. Staging replaces global-memory dictionary reads with shared-memory reads, which still compete with output writes for the L1 pipe’s access rate (Section 5.2). We therefore leave larger dictionaries to the GPU’s existing cache structures.

4.5

4 6 8 10 12 mean token length (bytes per code) FSST-12 OnPair-16 OnPair-12 r = +0.997 r = +0.982 r = +0.976

Figure 5. Decode throughput against mean token length on a B300, with least-squares fits and correlation coefficients.

We emphasize that the compression ratios reported throughout this work refer to data organized as a variablelength string array, where the string data is stored bytepacked and is accompanied by an array of fixed-width offsets. For each technique, we compress the string data using the technique under evaluation. Because decompressing the row offsets array is not necessary for bulk decompression, we do not include it in the compression ratio. Thus, for generalpurpose compression techniques, the compression ratio is the ratio of uncompressed to compressed bytes, while for FSST-family codecs we report uncompressed bytes against the sum of cascade-compressed bytes, batch offsets (sidecar), and dictionary data. Broadly, we recommend configuring FastPair with 𝐾 = 6 (tokens per thread), 𝐻 = 1 (held rounds of hoisted reads), and split reads enabled based on the column’s token-length distribution. For the B300, we also recommend launch bounds 𝑇 = 256 (threads per block) and 𝐵 = 4 (resident blocks requested). However, unless stated otherwise, the results in this section report each technique, both ours and each baseline, at the best configuration we found for each column. Where configurations trade compression ratio for decoding speed, such as Zstd frame-size tuning, we show an envelope of the best configurations found.

Token Length and Decode Rate

Across the real-world data columns, the decode rate rises nearly linearly with mean token length (Figure 5). The number of bytes decoded per second equals the mean token length multiplied by the number of codes decoded per second. The compression ratio equals the mean token length divided by the mean bytes per code (ignoring the dictionary, sidecar, and further cascaded compression). At a fixed code decoding rate and code width, increasing the mean token length therefore improves both decode throughput and the compression ratio. FSST-family tokens are decoded independently, regardless of length. A higher mean token length means fewer codes for the same text, improving both compression ratio and decoding throughput [14]. Further, this decoding relationship does not require the dictionary to be L1-resident. OnPair-16’s low-plane dictionary at 𝑊 = 8 is 512 KiB, at least twice as large as any explored GPU’s maximum per-SM SRAM capacity, so it cannot be L1-resident on any of those GPUs. OnPair-16 remains the fastest decoding technique on five of the ten real columns.

1600 1400 1200 1000 800

Evaluation 5.1

We evaluate FastPair on the five GPUs listed in Table 1, over the first 1 GB of each column in Table 2 [9, 10, 32, 37, 43, 48]. We compute decode rates from the minimum decoding time across at least 100 runs, with clock boosting enabled, unless specified otherwise. We prepare all relevant data and move it to device memory before decoding begins. In particular, we widen the stored, bit-packed codes and repack the dictionary into fixed-stride entries. We also decompress the offset sidecar and de-cascade the FSST-family encodings to their base form.

Performance Evaluation

On the B300, FastPair decodes the 10 real-data columns at 952–1529 GB/s using OnPair-12 and 814–1620 GB/s using OnPair-16. The fastest column is Loghub Windows at 1620 GB/s using OnPair-16, against 650 GB/s for the DE’s best codec and chunk size on that same column; an H100 decodes it at 1413 GB/s, above the B300’s Decompression Engine. Among the real-world columns, no baseline configuration we measured reaches those rates at an equal or better compression ratio. These results are shown in Figure 6. 9

decode throughput (GB/s)

Isaacs, Gargiulo, et al.

Real-world columns

2000

Generated columns

1500 1000 500 0

1.5 2

3 5 7 10 20 30 1 compression ratio (log) OnPair-12 FSST-12 DE Deflate (5) Zstd (3) Zstd (19) Bitcomp-default

OnPair-16 Zstd (-10)

1.5 2

3 5 7 10 compression ratio (log) DE Deflate (0) DE LZ4 Bitcomp-sparse gANS

DE Snappy GSST (A100)

Figure 6. Decode throughput against compression ratio on a B300, for both real-world and generated data columns. We show a baseline envelope: at each compression ratio, the fastest rate any baseline technique reaches at that ratio or better. We also include GSST’s A100-based result for reference. Zstd, at each compression level, is drawn as a best-found envelope. The only technique that shows comparable decoding performance on real-world data is the nvCOMP Bitcomp kernel using the Sparse compression mode; however, this kernel targets scientific data (floating-point) and barely compresses the evaluated string-data columns. Among the baselines that compress these columns by at least 2×, the DE decodes fastest on every real-world column; every baseline that reaches this minimum compression ratio uses a back-reference-based codec, the kind the DE accelerates. Further, neither OnPair-12 nor OnPair-16 is strictly better than the other. OnPair-16 is faster on four of the five log columns and slower on the text corpora, by as much as 47% across the devices we measure. Thus, the choice between OnPair-12 and -16 is largely data-dependent; if a given

throughput (% of peak)

100

column can use the larger dictionary and regularly forms tokens longer than eight bytes, such as the aforementioned log columns with repeated structural components, then OnPair16 may outperform OnPair-12.

5.2

To identify the factors that limit FastPair’s decoding throughput, we use device performance counters to measure unit utilization. We express each unit’s throughput relative to its peak sustained rate and derive the breakdown of the L1 pipe’s wavefront activity, which we show in Figure 7. On the B300, H100, and A100, the per-SM L1 pipe reaches about 99% of its access-rate limit when decoding the Loghub Windows column using OnPair-12, while device-memory bandwidth utilization ranges from 24% to 60% of peak. This contrasts with the RTX PRO 6000-SE and L40S, which reach 63% and 35% of that limit, respectively, while using about 90% of device-memory bandwidth. On the three HBM devices, the L1 pipe is nearly saturated while device-memory bandwidth remains available. Shared writes account for roughly 56% of the L1 pipe’s wavefronts on the HBM devices and 47% on the GDDR devices. These writes include output assembly in the emit stage and request-queue writes in split-read kernels. Global reads, including dictionary lookups in the gather stage, form the second-largest component. The remainder is other shared-memory traffic, including the warp shuffles used by the scan. The two largest consumers of the L1 pipe are bandwidth-inefficient: scattered dictionary reads and short shared-memory writes consume access capacity while transferring little data. In contrast, the drain stage combines neighboring threads’ accesses into more efficient coalesced transfers, reading from shared memory to write to global memory.

80 60

60 20 0

Performance Analysis

35 24

B300 H100 A100 RTX PRO L40S L1 – shared write L1 – other L1 – shared read L2 L1 – global write Device memory L1 – global read SM (compute)

Figure 7. Unit throughput as a fraction of its peak sustained rate (boost enabled) [26]. Loghub Windows. OnPair-12. 10

decode throughput (GB/s)

FastPair: GPU-Optimized String Decoding

2000 1500 1000 500 0

t t t s s k k e d S Titl HDF erbir Spar ndow ddres men _cler struc men o ip in c om nd Wi c_a l_com h p s_ Thu l_s RTX PRO 6000-SE (GDDR7) DE Deflate (5) DE Snappy boost L40S (GDDR6) DE Deflate (0) max DE LZ4 75%

t a eb2 ipedi Parro droid W e e An Fin Wik Cod

B300 (HBM) H100 (HBM) A100 (HBM)

L UR

55% 40%

Figure 8. Decode throughput of OnPair-12 on five GPUs across five SM clock frequencies: unlocked (boost), locked at max, and locked at 75, 55, and 40% of its maximum. The horizontal lines are the fastest configurations of the four B300 DE settings. 5.3

Cross-Architecture Evaluation

codes enables FastPair to construct batches without changing the code sequence. Further, its larger dictionaries preclude GSST’s approach of always storing the entire dictionary in shared memory. Finally, FastPair distributes a batch’s codes across a warp for decoding. DPF [30] decodes FSST records in parallel, using a prefix sum for output placement and shared-memory staging for coalesced writes. Fang et al. [12] position variable-length decoded output with a parallel prefix sum and stage small dictionaries in shared memory. CODAG [31] uses warp-level decoding and coalesced I/O for RLE and Deflate. Its lanes repeat the same serial decoding work to avoid broadcasting decoder state, whereas FastPair assigns independent dictionary lookups to lanes. ZipFlow [45] generates GPU kernels for string-dictionary expansion, including a word dictionary cascaded with bit-packing and ANS.

Using the B300’s Decompression Engine as the baseline, we compare FastPair’s OnPair-12 decoding performance across the five GPUs. We also vary each GPU’s SM clock, while keeping the memory clock fixed, across five states: unlocked (boost), locked at max, and locked at 75, 55, and 40% of its maximum. These results are shown in Figure 8. On the B300, FastPair decodes every column we explore faster than the DE. Older or less provisioned GPUs also exceed it on most columns: the H100, A100, and RTX PRO 6000-SE decode faster than the DE on all ten real columns, while the GDDR6 L40S does so on only five, falling short on all five Loghub columns. FastPair’s decoding performance on the B300, H100, and A100 scales nearly linearly with the SM clock. On these devices, columns with longer tokens decode faster and show larger absolute throughput gains as the clock increases. The RTX PRO 6000-SE levels off near the top of its clock range, particularly on long-token log columns. On the L40S, while longer tokens also improve decoding throughput, they reduce the impact of higher SM clocks.

Conclusion and Future Work

FastPair decodes FSST-family compressed strings efficiently on GPUs by reorganizing dictionary lookups and output writes. Across ten real-world columns on a B300, its best per-column configuration achieves 2.4 to 4.2× the decoding rate of the fixed-function Decompression Engine. Our architectural study shows that dictionary reads and the short shared-memory writes used to assemble output can reach the L1 pipe’s access-rate limit. Decoding throughput therefore depends on the memory accesses required per decoded byte, as well as on the parallelism exposed by the codec. FastPair contributes to a broader body of work built around cascading lightweight encodings to compress data. In future work, we aim to explore other lightweight encodings and extend our techniques to other compute platforms.

Related Work

GSST [40] is the closest prior GPU decoder for FSST-family strings. At compression time, GSST divides input into blocks with separate FSST-8 dictionaries, then subdivides each block into independently decodable splits. Splits are constructed to share either a compressed or uncompressed size; GSST stores the other size and recovers starting offsets with a prefix sum. GSST decodes the data by assigning each split to a thread. Both GSST and FastPair use a staged-then-aligned drain [40] and both give each thread many tokens rather than one [39]. In contrast to GSST, decoding escape-free 11

Isaacs, Gargiulo, et al.

Acknowledgments

[15] Mateusz Gienieczko, Maximilian Kuschewski, Thomas Neumann, Viktor Leis, and Jana Giceva. 2025. AnyBlox: A Framework for SelfDecoding Datasets. Proc. VLDB Endow. 18, 11 (2025), 4017–4031. https://doi.org/10.14778/3749646.3749672 [16] Anurag Gupta, Deepak Agarwal, Derek Tan, Jakub Kulesza, Rahul Pathak, Stefano Stefani, and Vidhya Srinivasan. 2015. Amazon Redshift and the Case for Simpler Data Warehouses. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 1917–1923. https://doi.org/10.1145/2723372.2742795 [17] HeavyAI, Inc. 2024. HeavyDB: An Open-Source SQL-Based, Columnar GPU Database. https://github.com/heavyai/heavydb [18] Sven Hepkema, Azim Afroozeh, Charlotte Felius, Peter Boncz, and Stefan Manegold. 2025. G-ALP: Rethinking Light-weight Encodings for GPUs. In Proceedings of the 21st International Workshop on Data Management on New Hardware (DaMoN ’25). 1–10. https://doi.org/10. 1145/3736227.3736242 [19] Zezhou Huang, Krystian Sakowski, Hans Lehnert, Wei Cui, Carlo Curino, Matteo Interlandi, Marius Dumitru, and Rathijit Sen. 2025. GPU Acceleration of SQL Analytics on Compressed Data. Proc. VLDB Endow. 19, 3 (2025), 320–333. https://doi.org/10.14778/3778092.3778095 [20] Aaron Jarmusch and Sunita Chandrasekaran. 2026. Microbenchmarking NVIDIA’s Blackwell Architecture: An In-Depth Architectural Analysis. In Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS ’26). 1026–1036. https: //doi.org/10.1109/IPDPS65963.2026.00087 [21] Maximilian Kuschewski, David Sauerwein, Adnan Alhomssi, and Viktor Leis. 2023. BtrBlocks: Efficient Columnar Compression for Data Lakes. Proc. ACM Manag. Data 1, 2 (2023), 1–26. https: //doi.org/10.1145/3589263 [22] N. Jesper Larsson and Alistair Moffat. 2000. Off-Line DictionaryBased Compression. Proc. IEEE 88, 11 (2000), 1722–1732. https: //doi.org/10.1109/5.892708 [23] NVIDIA Corporation. 2024. cuDF: GPU DataFrame Library. https: //github.com/NVIDIA/cudf [24] NVIDIA Corporation. 2024. nvCOMP: High-Performance Compression on NVIDIA GPUs. https://developer.nvidia.com/nvcomp [25] NVIDIA Corporation. 2024. NVIDIA Blackwell Architecture Technical Overview. https://resources.nvidia.com/en-us-blackwell-architecture [26] NVIDIA Corporation. 2025. Nsight Compute Kernel Profiling Guide. https://docs.nvidia.com/nsight-compute/ProfilingGuide/ [27] NVIDIA Corporation. 2025. nvCOMP: Cascaded Compression. https: //docs.nvidia.com/cuda/nvcomp/cascaded.html [28] NVIDIA Corporation. 2025. nvCOMP: Decompression Engine. https: //docs.nvidia.com/cuda/nvcomp/decompression_engine_faq.html [29] NVIDIA Corporation. 2026. CUDA C++ Programming Guide and Architecture Tuning Guides. https://docs.nvidia.com/cuda/ [30] Tsuyoshi Ozawa and Kazuo Goda. 2026. Data Path Fusion in GPU for Analytical Query Processing. arXiv:2605.10511 [cs.DB] [31] Jeongmin Park, Zaid Qureshi, Vikram Sharma Mailthody, Andrew Gacek, Shunfan Shao, Mohammad AlMasri, Isaac Gelado, Jinjun Xiong, Chris Newburn, I-hsin Chung, Michael Garland, Nikolay Sakharnykh, and Wen-mei Hwu. 2023. CODAG: Characterizing and Optimizing Decompression Algorithms for GPUs. arXiv:2307.03760 [cs.DC] [32] Guilherme Penedo, Hynek Kydlíček, Vinko Sabolčec, Bettina Messmer, Negar Foroutan, Amir Hossein Kargaran, Colin Raffel, Martin Jaggi, Leandro Von Werra, and Thomas Wolf. 2025. FineWeb2: One Pipeline to Scale Them All – Adapting Pre-Training Data Processing to Every Language. arXiv:2506.20920 [cs.CL] [33] Anil Shanbhag, Samuel Madden, and Xiangyao Yu. 2020. A Study of the Fundamental Performance Characteristics of GPUs and CPUs for Database Analytics. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 1617–1632. https://doi.org/10. 1145/3318464.3380595

Generative AI assisted with the development and evaluation of FastPair and the preparation of this manuscript. The authors directed all use of AI and stand by this work.

References [1] Azim Afroozeh and Peter Boncz. 2023. The FastLanes Compression Layout: Decoding >100 Billion Integers per Second with Scalar Code. Proc. VLDB Endow. 16, 9 (2023), 2132–2144. https://doi.org/10.14778/ 3598581.3598587 [2] Azim Afroozeh and Peter Boncz. 2025. The FastLanes File Format. Proc. VLDB Endow. 18, 11 (2025), 4629–4643. https://doi.org/10.14778/ 3749646.3749718 [3] Azim Afroozeh, Lotte Felius, and Peter Boncz. 2024. Accelerating GPU Data Processing using FastLanes Compression. In Proceedings of the 20th International Workshop on Data Management on New Hardware (DaMoN ’24). 1–11. https://doi.org/10.1145/3662010.3663450 [4] Azim Afroozeh, Leonardo X. Kuffo, and Peter Boncz. 2023. ALP: Adaptive Lossless Floating-Point Compression. Proc. ACM Manag. Data 1, 4 (2023), 1–26. https://doi.org/10.1145/3626717 [5] Tim Anema, Joost Hoozemans, Zaid Al-Ars, and H. Peter Hofstee. 2025. High Throughput GPU-Accelerated FSST String Compression. In Proceedings of the 16th International Workshop on Accelerating Analytics and Data Management Systems Using Modern Processor and Storage Architectures (ADMS ’25). https://www.vldb.org/2025/Workshops/ VLDB-Workshops-2025/ADMS/ADMS25-01.pdf [6] Felipe Aramburú, William Malpica, Kaouther Abrougui, Amin Aramoon, Romulo Auccapuclla, Claude Brisson, Matthijs Brobbel, Colby Farrell, Pradeep Garigipati, Joost Hoozemans, Supun Kamburugamuve, Akhil Nair, Alexander Ocsa, Johan Peltenburg, Rubén Quesada López, Deepak Sihag, Ahmet Uyar, Dhruv Vats, Michael Wendt, Jignesh M. Patel, and Rodrigo Aramburú. 2025. Theseus: A Distributed and Scalable GPU-Accelerated Query Processing Platform Optimized for Efficient Data Movement. arXiv:2508.05029 [cs.DC] [7] Peter Boncz, Thomas Neumann, and Viktor Leis. 2020. FSST: Fast Random Access String Compression. Proc. VLDB Endow. 13, 11 (2020), 2649–2661. https://doi.org/10.14778/3407790.3407851 [8] Hedi Chehaidar, Mihail Stoian, Moritz Stargalla, and Andreas Kipf. 2026. OptFSST: Optimized FSST String Compression. In Proceedings of the 17th International Workshop on Accelerating Analytics and Data Management Systems Using Modern Processor and Storage Architectures (ADMS ’26). https://arxiv.org/abs/2607.11271 [9] ClickHouse, Inc. 2023. ClickBench: A Benchmark for Analytical Databases. https://github.com/ClickHouse/ClickBench [10] CodeParrot. 2022. CodeParrot codeparrot-clean Dataset. https: //huggingface.co/datasets/codeparrot/codeparrot-clean [11] Benoit Dageville, Thierry Cruanes, Marcin Zukowski, Vadim Antonov, Artin Avanes, Jon Bock, Jonathan Claybaugh, Daniel Engovatov, Martin Hentschel, Jiansheng Huang, Allison W. Lee, Ashish Motivala, Abdul Q. Munir, Steven Pelley, Peter Povinec, Greg Rahn, Spyridon Triantafyllis, and Philipp Unterbrunner. 2016. The Snowflake Elastic Data Warehouse. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 215–226. https://doi.org/10.1145/ 2882903.2903741 [12] Wenbin Fang, Bingsheng He, and Qiong Luo. 2010. Database Compression on Graphics Processors. Proc. VLDB Endow. 3, 1–2 (2010), 670–680. https://doi.org/10.14778/1920841.1920927 [13] Philip Gage. 1994. A New Algorithm for Data Compression. The C Users Journal 12, 2 (1994), 23–38. [14] Francesco Gargiulo and Rossano Venturini. 2025. OnPair: Short Strings Compression for Fast Random Access. arXiv:2508.02280 [cs.DB] 12

FastPair: GPU-Optimized String Decoding

1984.1659158 [43] Wikimedia Foundation. 2023. Wikipedia (Hugging Face dataset wikimedia/wikipedia, 20231101 dumps). https://huggingface.co/ datasets/wikimedia/wikipedia [44] Youyang Xia, Feng Zhang, Junda Pan, Yihao Liu, Jiawei Guan, Huanchen Zhang, and Xiaoyong Du. 2026. L3: A GPU-Native CoDesigned Data Format for Learned Lossless Lightweight Compression. Proc. ACM Manag. Data 4, 3 (2026), 1–27. https://doi.org/10.1145/ 3802078 [45] Gwangoo Yeo, Zhiyang Shen, Wei Cui, Matteo Interlandi, Rathijit Sen, Bailu Ding, Qi Chen, and Minsoo Rhu. 2026. ZipFlow: A CompilerBased Framework to Unleash Compressed Data Movement for Modern GPUs. arXiv:2602.08190 [cs.DB] [46] Bobbi Yogatama, Yifei Yang, Kevin Kristensen, Devesh Sarda, Abigale Kim, Adrian Cockcroft, Yu Teng, Joshua Patterson, Gregory Kimball, Wes McKinney, Weiwei Gong, and Xiangyao Yu. 2026. Rethinking Analytical Processing in the GPU Era. In Proceedings of the 16th Conference on Innovative Data Systems Research (CIDR ’26). https://vldb.org/cidrdb/papers/2026/p12-yogatama.pdf [47] Xinyu Zeng, Ruijun Meng, Martin Prammer, Wes McKinney, Jignesh M. Patel, Andrew Pavlo, and Huanchen Zhang. 2025. F3: The Open-Source Data File Format for the Future. Proc. ACM Manag. Data 3, 4 (2025), 1–27. https://doi.org/10.1145/3749163 [48] Jieming Zhu, Shilin He, Pinjia He, Jinyang Liu, and Michael R. Lyu. 2023. Loghub: A Large Collection of System Log Datasets for AIDriven Log Analytics. In Proceedings of the 34th IEEE International Symposium on Software Reliability Engineering (ISSRE ’23). 355–366. https://doi.org/10.1109/ISSRE59848.2023.00071 [49] Jacob Ziv and Abraham Lempel. 1977. A Universal Algorithm for Sequential Data Compression. IEEE Transactions on Information Theory 23, 3 (1977), 337–343. https://doi.org/10.1109/TIT.1977.1055714

[34] Anil Shanbhag, Bobbi W. Yogatama, Xiangyao Yu, and Samuel Madden. 2022. Tile-Based Lightweight Integer Compression in GPU. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 1390–1403. https://doi.org/10.1145/3514221.3526132 [35] Evangelia Sitaridi, Rene Mueller, Tim Kaldewey, Guy Lohman, and Kenneth A. Ross. 2016. Massively-Parallel Lossless Data Decompression. In Proceedings of the 45th International Conference on Parallel Processing (ICPP ’16). 242–247. https://doi.org/10.1109/ICPP.2016.35 [36] James A. Storer and Thomas G. Szymanski. 1982. Data Compression via Textual Substitution. Journal of the ACM 29, 4 (1982), 928–951. https://doi.org/10.1145/322344.322346 [37] Transaction Processing Performance Council. 2022. TPC Benchmark H (Decision Support) Standard Specification, Revision 3.0.1. https: //www.tpc.org/tpch/ [38] Alexandre Verbitski, Anurag Gupta, Debanjan Saha, Murali Brahmadesam, Kamal Gupta, Raman Mittal, Sailesh Krishnamurthy, Sandor Maurice, Tengiz Kharatishvili, and Xiaofeng Bao. 2017. Amazon Aurora: Design Considerations for High Throughput CloudNative Relational Databases. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 1041–1052. https: //doi.org/10.1145/3035918.3056101 [39] Vasily Volkov. 2010. Better Performance at Lower Occupancy. GPU Technology Conference (GTC). https://www.nvidia.com/content/gtc2010/pdfs/2238_gtc2010.pdf [40] Robin Vonk, Joost Hoozemans, and Zaid Al-Ars. 2025. GSST: Parallel String Decompression at 191 GB/s on GPU. In Proceedings of the 5th Workshop on Challenges and Opportunities of Efficient and Performant Storage Systems (CHEOPS ’25). 8–14. https://doi.org/10.1145/3719330. 3721228 [41] Vortex Authors. 2025. Vortex: A Next-Generation Columnar File Format and Toolkit. https://github.com/vortex-data/vortex [42] Terry A. Welch. 1984. A Technique for High-Performance Data Compression. Computer 17, 6 (1984), 8–19. https://doi.org/10.1109/MC.

Record · ID 919348 · SHA-256 41dbcab4310ca56c
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.