📌 本文概要

FastLanes是一个面向数据并行硬件（SIMD / GPU）的下一代大数据文件格式，宣称比 Parquet 压缩率高 40%、解码快 40 倍。本文带你深入G-ALP（GPU 编码）模块：它是为 GPU 重设计的轻量压缩实现，通过"无分支、数据并行"的异常值回填技巧，让浮点列在 GPU 上的解码与查询性能大幅提升。无论你是数据工程师、GPU 开发新手，还是好奇文件格式如何演进的读者，都能从中获得清晰的理解。

一、为什么需要为 GPU 重新设计编码？

传统列式格式（如 Parquet）大量使用 Snappy、ZSTD 这类通用压缩算法。它们的特点是：

• 压缩算法内部充满分支与串行依赖（查找表、游程判断等）
• 在 CPU 单核上表现不错，但在 GPU 成千上万个线程并发执行时，线程会频繁"分叉"，效率急剧下降

FastLanes 的思路恰恰相反：放弃通用压缩，改用完全数据并行的"轻量编码"（Light-weight Encodings），比如 BP（BitPacking）、FFOR、ALP 等。这些编码的每一步都可以被编译器/GPU 自动向量化，没有任何显式 SIMD 指令。

💡 G-ALP 正是这一理念在 GPU 上的落地：论文标题就叫"G-ALP: Rethinking Light-weight Encodings for GPUs"（DaMoN '25），信息见 README.md，实现代码位于 galp/ 目录。

编码家族一览

这套类型与内核定义可以在 enums.cuh 中一眼看全：数据支持U32 / U64 / F32 / F64，内核分Decompress（解压）、Query（压缩态查询）、QueryMultiColumn（多列协同查询）三种。

二、ALP 核心原理：把浮点数"拆"开

ALP 编码的关键是把一个浮点值拆成三部分：

1. base + factor × fraction：用整数近似还原浮点
2. bit-packed 主数据：绝大多数值能被上述公式精确还原
3. exceptions（异常值）：极少数无法精确还原的值，单独存"值 + 位置"

浮点值 ≈ (packed + base) × factor + fraction → 绝大多数值 exceptions: { (位置, 原始值), ... } → 少数补洞

GPU 解压时，主数据是纯粹的并行读取 + 算术运算，非常快。真正的性能瓶颈出现在最后一步——patch（回填异常值）：要把稀疏的异常值"插"回正确位置。如果逐个写，就是典型的随机写 + 分支，GPU 最忌讳这种模式。

三、关键创新：数据并行的 Patch 算子

G-ALP 的杀手锏就是重写了 patch 算子，把"逐个散射写入"改成了3 步全数据并行流程：

1. Count：每个 lane 数自己负责几个异常值（一次取模 + 自增）
2. Prefix：对计数做前缀和，算出每条 lane 的起始偏移
3. Scatter：再遍历一遍异常，每条 lane 顺序写入自己的连续区段

整个过程零分支发散，所有线程步调一致。对比实现见 CPU 微基准 bench_data_parallelize_patch.cpp：new_data_parallelizer（新实现）对比old_data_parallelizer（旧的逐元素散射）。

GPU 端的对应结构定义在 structs.cuh，其中ALPColumn与ALPExtendedColumn分别对应两种设备端列布局；解码 functor 的核心一行算术见 alp.cuh——就是一次加法、一次乘法、一次小数叠加，对 GPU 极为友好。

📊 实测：新旧 Patch 性能对比

基准脚本对 0~20 个异常值场景分别测量了新旧实现的周期数（cycles per tuple），原始数据在 patch.csv，绘图脚本为 plot.py。核心结果：

解读图表：

• 🟢绿色曲线（new）平缓近似线性——异常越多开销增长越慢
• 🔴红色曲线（old）快速抬升——传统散射写入随异常增多明显恶化
• 结论：异常值越密集，G-ALP 新算子的优势越大（最高约 2.5 倍）

四、工程实现：如何组织 GPU 代码？

1. Warp-Lane 映射，消除分支

G-ALP 将每个向量（1024 个值）按 warp 内的 lane 切分：每个 lane 固定负责一组值，解压循环里用寄存器暂存、批量写回全局内存，核心内核见 kernels.cuh。

2. 变体矩阵 + 代码生成器

为了找到最优的 Unpacker / Patcher 组合（枚举多达十余种变体，见 enums.cuh），团队没有手写海量模板实例，而是用 Python代码生成器批量产出内核绑定：

• 生成器：generate-kernel-bindings.py，覆盖 4 种数据 × 4 种编码 × 多类 Unpacker
• 产物：galp/benchmark/generated-bindings/ 下 24 个.cu绑定文件

3. 与业界 GPU 压缩器正面对比

基准测试不仅测自身新旧版本，还与 NVIDIA 生态的压缩器做了横评（Bitcomp、LZ4、ZSTD、GDeflate、Snappy 等），驱动代码见 compressors-benchmarks.cu。不同 GPU 的编译配置可在 toolchains/ 中找到（T4、g4dn、gtx1080 等）。

五、上手体验与总结

🚀 快速上手（Python 三步）

import pyfastlanes conn = pyfastlanes.connect() conn.inline_footer().read_csv("path/to/csv_dir").to_fls("data.fls") conn.read_fls("data.fls").to_csv("decoded.csv")

G-ALP 属于 FastLanes 的 GPU 解压路径（CUDA reader 标注为Coming Soon，见 README.md），当前 CPU 侧完整功能已可用。

✅ 核心要点回顾

🎯一句话总结：G-ALP 证明了"为硬件重新思考编码"的价值——不是把 CPU 算法照搬上 GPU，而是围绕 GPU 的并行执行模型，把压缩格式的每一步都做成线程齐步走的无分支操作。这正是 FastLanes 作为"下一代大数据文件格式"的核心竞争力所在。

📚 延伸阅读

• 类型系统设计：docs/typing_system.md
• G-ALP 模块说明：galp/README.md
• 文件格式论文信息：README.md
• 基准结果原始数据：benchmark/result/galp/patch.csv