已开启
build_multi_array_is_equal_from_arrays #11
吴磊创建于  5月21日
吴磊
吴磊成员
5月21日 创建

描述(Description)

函数 build_multi_array_is_equal_from_arrays 是多列数组相等比较的核心入口,被 join、dedup、group-by 等算子频繁调用。旧版实现存在三个性能瓶颈和一个正确性缺陷:

  1. 每列使用 Box<dyn Fn> 闭包,每次比较都要经过 trait object 的 vtable 间接查找;
  2. 全量 clone PrimitiveArray 而非零拷贝引用,早期版本甚至使用 .to_vec() 导致 build 时间从 ~0.9ms 退化到 ~2ms;
  3. validity 判断和 value 比较分在两层函数中,增加间接调用层数;
  4. NullArray 的 null 处理不完整,单侧为 Null 时行为不正确。

本次优化将架构从闭包链重构为 MultiColumnComparator 结构体,采用 enum 静态分发和零拷贝缓冲区引用,消除了上述问题。

复现(Reproduction)

Minimal reproduction example

use arrow::array::{ArrayRef, PrimitiveArray, Float64Array};
use arrow::datatypes::Float64Type;

let left: Vec<ArrayRef> = vec![
    Arc::new(Float64Array::from(vec![1.0, f64::NAN, 3.0, f64::NAN])) as ArrayRef,
];
let right: Vec<ArrayRef> = vec![
    Arc::new(Float64Array::from(vec![1.0, 2.0, f64::NAN, f64::NAN])) as ArrayRef,
];
let nulls_equal = vec![true];
let nans_equal = vec![true];

let cmp = build_multi_array_is_equal_from_arrays(&left, &right, &nulls_equal, &nans_equal)?;

// 旧版问题:
// 1. 每次 cmp(0, 0) 调用都经过 Box<dyn Fn> vtable
// 2. NullArray 场景下 is_valid() 始终返回 true
// 3. 构建 comparator 时对每个 float array 做全量 clone

说明:
● 性能问题可通过 perf 火焰图观察到 vtable lookup_rjem_malloc 热点
● 正确性问题在单侧为 NullArray 时可复现(旧版 is_valid() 返回 true,不应进入 value 比较)

期望结果(Expected behavior)
修改后预期行为:
● 构建时间从 ~0.9-2ms 下降到零拷贝级别(仅 Arc 原子递增)
● 每次比较走 enum 静态分发,无 vtable 间接查找
● NullArray 正确处理:左右两侧 null 信息独立存储,显式标记 NullArray
● 公共 API 签名不变,下游零改动

测试环境(Environment)

列出环境信息:
● 操作系统及架构:Linux / ARM64 & x86_64
● daft 版本:待确认
● python 版本:待确认
● rust 版本:2021 edition

修复建议(Suggested Fix)

已完成修复,核心改动如下:

  1. 架构重构:从四个嵌套函数收敛为一个 MultiColumnComparator 结构体,包含 value_comparators: Vec<ValueComparator>(enum 分发)和 validity_info: Vec<ColumnValidityInfo>(预提取 null 信息)

  2. Enum 静态分发

    enum ValueComparator {
        Null,
        F32 { left_values: ScalarBuffer<f32>, right_values: ScalarBuffer<f32>, nan_equal: bool },
        F64 { left_values: ScalarBuffer<f64>, right_values: ScalarBuffer<f64>, nan_equal: bool },
        Generic { comparator: Box<dyn Fn(usize, usize) -> bool + Send + Sync> },
    }
    
  3. 零拷贝缓冲区:通过 left_arr.values().clone() 获取 ScalarBuffer<T> 的 Arc 引用,仅原子递增计数器,不分配堆内存

  4. Null 处理修复:新增 ColumnValidityInfo 分别存储左右两侧的 null 信息,显式标记 left_is_null_array / right_is_null_array

  5. 比较循环合并:validity 判断和 value 比较在同一个 for 循环中完成,消除中间闭包调用层数

严重程度(Severity)

● 性能影响:热路径函数,每次行比较均被调用。旧版 vtable 查找和内存分配在大数据量下放大为显著性能瓶颈,改用enum静态分发和零拷贝引用后,消除了热路径上的间接调用和堆分配开销
● 正确性影响:无

likedislike
吴磊吴磊成员
5月21日 修改了issue 的描述
吴磊吴磊成员
5月21日 修改了issue 的描述
吴磊吴磊成员
5月21日 修改了issue 的描述
吴磊吴磊成员
5月21日 修改标题为 “build_multi_array_is_equal_from_arrays”,原标题为“1”
junlai-coder成员
5月22日 评论:

鲲鹏 920B(ARM)上因分支预测较弱 —— 不应该体现硬件内部分析的细节

likedislike
吴磊吴磊成员
5月22日 修改了issue 的描述