New row format that does not guarantee ordering of columns

[rluvaton]

Is your feature request related to a problem or challenge? Please describe what you are trying to do.
Yes, I'm using RowConverter and it start to become a bottleneck,
some of the use cases of row conversions do not need ordering
for example:

1. grouping - grouping by a lot of columns does not need ordering requirements
2. aggregation - using count(distinct <struct>) or array_agg with distinct, both of which do not need ordering requirements
3. shuffling

and having ordering requirements limit optimizations.

Bottlenecks that I found and how the ordering limit optimizations described below.

Describe the solution you'd like

Describe alternatives you've considered

Additional context

---

All my benchmarks and profiling were done on the most reliable machine I could get:

c5.metal

Env

[ec2-user@ip-172-31-21-167 build]$ ./fastfetch -c ../presets/all.jsonc
                      ec2-user@ip-
                      -------------------------
  ,     #_            OS: Amazon Linux 2023.9.20251208 x86_64
  ~\_  ####_          Host: c5.metal (00001)
 ~~  \_#####\         BIOS (Legacy): 1.0 (4.15)
 ~~     \###|         Chassis: Rack Mount Chassis
 ~~       \#/ ___     Kernel: Linux 6.1.158-180.294.amzn2023.x86_64
  ~~       V~' '->    Init System: systemd 252.23-10.amzn2023
   ~~~         /      Uptime: 3 hours, 52 mins
     ~~._.   _/       Loadavg: 0.04, 0.08, 0.05
        _/ _/         Processes: 825
      _/m/'           Shell: bash 5.2.15
                      LM: sshd 8.7p1 (TTY)
                      Terminal: /dev/pts/0
                      Terminal Size: 160 columns x 57 rows (3200px x 2508px)
                      Terminal Theme: #ACB2BE (FG) - #21252A (BG) [Dark]
                      CPU: 2 x Intel(R) Xeon(R) Platinum 8275CL (96) @ 3.90 GHz
                      CPU Cache (L1): 48x32.00 KiB (D), 48x32.00 KiB (I)
                      CPU Cache (L2): 48x1.00 MiB (U)
                      CPU Cache (L3): 2x35.75 MiB (U)
                      CPU Usage: 0%
                      Memory: 2.00 GiB / 188.52 GiB (1%)
                      Disk (/): 15.36 GiB / 255.93 GiB (6%) - xfs
                      Date & Time: 2026-01-01 11:53:52
                      Locale: C.UTF-8
                      Network IO (enp125s0): 1.75 KiB/s (IN) - 4.69 KiB/s (OUT)
                      Disk IO (Amazon Elastic Block Store): 0 B/s (R) - 4.00 KiB/s (W)
                      Physical Disk (Amazon Elastic Block Store): 256.00 GiB [SSD, Fixed]
                      Version: fastfetch 2.56.1-16 (x86_64)

$ ./cpufetch --verbose

 Name:                Intel Xeon Platinum 8275CL
 Microarchitecture:   Cascade Lake
 Technology:          14nm
 Max Frequency:       3.900 GHz
 Sockets:             2
 Cores:               24 cores (48 threads)
 Cores (Total):       48 cores (96 threads)
 AVX:                 AVX,AVX2,AVX512
 FMA:                 FMA3
 L1i Size:            32KB (1.5MB Total)
 L1d Size:            32KB (1.5MB Total)
 L2 Size:             1MB (48MB Total)
 L3 Size:             35.75MB (71.5MB Total)
 Peak Performance:    11.98 TFLOP/s

---

When I tried to improve performance of row conversion I first started with having the easiest case but with multiple columns

also all benchmarks run with:

.cargo/config:

[build]
rustflags = ["-C", "force-frame-pointers=yes"]

[rluvaton]

Bottleneck 1: Store bound for 50 columns of non-null u64 array

Note: using u64 as it doesn't have some sign that we need to deal with
and no nulls to focus on a specific code path (fixed::encode_not_null)

Benchmark code:

fn do_bench(c: &mut Criterion, name: &str, cols: Vec<ArrayRef>) {
  let fields: Vec<_> = cols
    .iter()
    .map(|x| SortField::new(x.data_type().clone()))
    .collect();
  let mut group = c.benchmark_group("row_format");
  group.throughput(criterion::Throughput::Elements(cols.len() as u64));

  group.bench_function(&format!("convert_columns {name}"), |b| {
    b.iter(|| {
      let converter = RowConverter::new(fields.clone()).unwrap();
      hint::black_box(converter.convert_columns(&cols).unwrap())
    });
  });
}

fn run_bench_on_multi_column_with_same_fixed_size_data_type_with_no_nulls<T>(
  c: &mut Criterion,
  num_cols: usize,
  batch_size: usize,
) where
  T: ArrowPrimitiveType,
  StandardUniform: Distribution<T::Native>,
{
  let mut seed = 0;

  let mut cols: Vec<ArrayRef> = vec![];

  for _ in 0..num_cols {
    seed += 1;
    cols.push(
      Arc::new(create_primitive_array_with_seed::<T>(batch_size, 0.0, seed)) as ArrayRef,
    );
  }

  do_bench(
    c,
    format!(
      "{} with {} columns at size {batch_size}",
      T::DATA_TYPE,
      num_cols
    )
      .as_str(),
    cols,
  );
}

fn row_bench(c: &mut Criterion) {
  run_bench_on_multi_column_with_same_fixed_size_data_type_with_no_nulls::<UInt64Type>(
    c, 50, 8192,
  );
}

criterion_group! {
    name = benches;
    config = Criterion::default().measurement_time(Duration::from_secs(10));
    targets = row_bench
}

Results on main:

$ cargo bench --features=test_utils --bench row_format --profile=profiling -- --save-baseline=main

    Finished `profiling` profile [optimized + debuginfo] target(s) in 0.15s
     Running benches/row_format.rs (target/profiling/deps/row_format-7489cf224545c7d6)
Benchmarking row_format/convert_columns UInt64 with 50 columns at size 8192: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 10.0s. You may wish to increase target time to 10.6s, enable flat sampling, or reduce sample count to 60.
Benchmarking row_format/convert_columns UInt64 with 50 columns at size 8192: Collecting 100 samples in estimated 10.585 s (50
row_format/convert_columns UInt64 with 50 columns at size 8192
                        time:   [2.0778 ms 2.0787 ms 2.0799 ms]
                        thrpt:  [24.040 Kelem/s 24.054 Kelem/s 24.063 Kelem/s]
Found 16 outliers among 100 measurements (16.00%)
  6 (6.00%) high mild
  10 (10.00%) high severe

Note

TL;DR: the problem is that we are bottleneck by store, and there are a lot of store instructions that split across a cacheline boundary.

Allowing us to bitpack nulls from all columns at the start of the row and to reorder fields and add padding will allow us to improve the performance.

Step by step finding the problem:

Running Top-Down analysis - Level 1

$ ~/pmu-tools/toplev.py --core S0-C0 -l1 --single-thread -v --no-desc taskset -c 0 target/profiling/deps/row_format-7489cf224545c7d6 --bench --warm-up-time 1 --noplot
Benchmarking row_format/convert_columns UInt64 with 50 columns at size 8192: Warming up for 1.0000 s
Warning: Unable to complete 100 samples in 10.0s. You may wish to increase target time to 10.9s, enable flat sampling, or reduce sample count to 60.
Benchmarking row_format/convert_columns UInt64 with 50 columns at size 8192: Collecting 100 samples in estimated 10.932 s (50
row_format/convert_columns UInt64 with 50 columns at size 8192
                        time:   [2.1303 ms 2.1308 ms 2.1313 ms]
                        thrpt:  [23.459 Kelem/s 23.466 Kelem/s 23.471 Kelem/s]
Found 12 outliers among 100 measurements (12.00%)
  5 (5.00%) high mild
  7 (7.00%) high severe

# 5.01-full-perf on Intel(R) Xeon(R) Platinum 8275CL CPU @ 3.00GHz [clx/skylake]
FE               Frontend_Bound   % Slots                        0.3  <
BAD              Bad_Speculation  % Slots                        0.4  <
BE               Backend_Bound    % Slots                       80.3   <==
RET              Retiring         % Slots                       19.0  <
MUX                               %                            100.00
Run toplev --describe Backend_Bound^ to get more information on bottleneck
Add --run-sample to find locations
Add --nodes '!+Backend_Bound*/2,+MUX' for breakdown.

It looks like the problem is Backend_Bound.

Running Top-Down analysis - Level 2

$ ~/pmu-tools/toplev.py --core S0-C0 -l2 --single-thread -v --no-desc taskset -c 0 target/profiling/deps/row_format-7489cf224545c7d6 --bench --warm-up-time 1 --noplot
Benchmarking row_format/convert_columns UInt64 with 50 columns at size 8192: Warming up for 1.0000 s
Warning: Unable to complete 100 samples in 10.0s. You may wish to increase target time to 11.1s, enable flat sampling, or reduce sample count to 60.
Benchmarking row_format/convert_columns UInt64 with 50 columns at size 8192: Collecting 100 samples in estimated 11.130 s (50
row_format/convert_columns UInt64 with 50 columns at size 8192
                        time:   [2.1779 ms 2.1784 ms 2.1789 ms]
                        thrpt:  [22.947 Kelem/s 22.953 Kelem/s 22.958 Kelem/s]
                 change:
                        time:   [+2.0777% +2.2031% +2.3211%] (p = 0.00 < 0.05)
                        thrpt:  [−2.2684% −2.1556% −2.0354%]
                        Performance has regressed.
Found 3 outliers among 100 measurements (3.00%)
  2 (2.00%) high mild
  1 (1.00%) high severe

# 5.01-full-perf on Intel(R) Xeon(R) Platinum 8275CL CPU @ 3.00GHz [clx/skylake]
FE               Frontend_Bound                      % Slots                        0.5  < [14.0%]
BAD              Bad_Speculation                     % Slots                        0.5  < [14.0%]
BE               Backend_Bound                       % Slots                       78.9    [14.0%]<==
RET              Retiring                            % Slots                       19.9  < [14.0%]
FE               Frontend_Bound.Fetch_Latency        % Slots                        0.2  < [14.0%]
FE               Frontend_Bound.Fetch_Bandwidth      % Slots                        0.3  < [14.0%]
BAD              Bad_Speculation.Branch_Mispredicts  % Slots                        0.5  < [14.0%]
BAD              Bad_Speculation.Machine_Clears      % Slots                        0.0  < [14.0%]
BE/Mem           Backend_Bound.Memory_Bound          % Slots                       40.5    [14.0%]
BE/Core          Backend_Bound.Core_Bound            % Slots                       38.4    [14.0%]
RET              Retiring.Light_Operations           % Slots                       18.2  < [14.0%]
RET              Retiring.Heavy_Operations           % Slots                        1.7  < [14.0%]
MUX                                                  %                             14.00
Run toplev --describe Backend_Bound^ to get more information on bottleneck
Add --run-sample to find locations
Add --nodes '!+Backend_Bound*/2,+MUX' for breakdown.

Running Top-Down analysis - Level 3

$ ~/pmu-tools/toplev.py --core S0-C0 -l3 --single-thread -v --no-desc taskset -c 0 target/profiling/deps/row_format-7489cf224545c7d6 --bench --warm-up-time 1 --noplot
Benchmarking row_format/convert_columns UInt64 with 50 columns at size 8192: Warming up for 1.0000 s
Warning: Unable to complete 100 samples in 10.0s. You may wish to increase target time to 10.9s, enable flat sampling, or reduce sample count to 60.
row_format/convert_columns UInt64 with 50 columns at size 8192
                        time:   [2.1342 ms 2.1347 ms 2.1353 ms]
                        thrpt:  [23.416 Kelem/s 23.422 Kelem/s 23.428 Kelem/s]
                 change:
                        time:   [+0.5527% +0.6704% +0.7973%] (p = 0.00 < 0.05)
                        thrpt:  [−0.7910% −0.6659% −0.5497%]
                        Change within noise threshold.
Found 7 outliers among 100 measurements (7.00%)
  3 (3.00%) high mild
  4 (4.00%) high severe

# 5.01-full-perf on Intel(R) Xeon(R) Platinum 8275CL CPU @ 3.00GHz [clx/skylake]
FE               Frontend_Bound                                        % Slots                        0.6  < [ 3.0%]
BAD              Bad_Speculation.Branch_Mispredicts.Other_Mispredicts  % Slots                        0.0  < [ 3.0%]
BAD              Bad_Speculation.Machine_Clears.Other_Nukes            % Slots                        0.0  <
BE/Core          Backend_Bound.Core_Bound.Serializing_Operation        % Clocks                       0.0  < [ 3.0%]
BAD              Bad_Speculation                                       % Slots                        0.4  < [ 3.0%]
BE               Backend_Bound                                         % Slots                       77.8    [ 3.0%]<==
RET              Retiring                                              % Slots                       19.7  < [ 3.0%]
FE               Frontend_Bound.Fetch_Latency                          % Slots                        0.3  < [ 3.0%]
FE               Frontend_Bound.Fetch_Bandwidth                        % Slots                        0.3  < [ 3.0%]
BAD              Bad_Speculation.Branch_Mispredicts                    % Slots                        0.4  < [ 3.0%]
BAD              Bad_Speculation.Machine_Clears                        % Slots                        0.0    [ 3.0%]
BE/Mem           Backend_Bound.Memory_Bound                            % Slots                       39.9    [ 3.0%]
BE/Core          Backend_Bound.Core_Bound                              % Slots                       37.9    [ 3.0%]
RET              Retiring.Light_Operations                             % Slots                       18.0  < [ 3.0%]
RET              Retiring.Heavy_Operations                             % Slots                        1.7  < [ 3.0%]
FE               Frontend_Bound.Fetch_Latency.ICache_Misses            % Clocks                       0.1  < [ 3.0%]
FE               Frontend_Bound.Fetch_Latency.ITLB_Misses              % Clocks                       0.2  < [ 3.0%]
FE               Frontend_Bound.Fetch_Latency.Branch_Resteers          % Clocks                       0.2  < [ 3.0%]
FE               Frontend_Bound.Fetch_Latency.MS_Switches              % Clocks_est                   0.3    [ 3.0%]
FE               Frontend_Bound.Fetch_Latency.LCP                      % Clocks                       0.0  < [ 3.0%]
FE               Frontend_Bound.Fetch_Latency.DSB_Switches             % Clocks                       0.3  < [ 3.0%]
FE               Frontend_Bound.Fetch_Bandwidth.MITE                   % Slots_est                    0.5  < [ 3.0%]
FE               Frontend_Bound.Fetch_Bandwidth.DSB                    % Slots_est                    2.8  < [ 3.0%]
BE/Mem           Backend_Bound.Memory_Bound.L1_Bound                   % Stalls                      12.7    [ 3.0%]
BE/Mem           Backend_Bound.Memory_Bound.L2_Bound                   % Stalls                       0.1  < [ 3.0%]
BE/Mem           Backend_Bound.Memory_Bound.L3_Bound                   % Stalls                       0.4  < [ 3.0%]
BE/Mem           Backend_Bound.Memory_Bound.DRAM_Bound                 % Stalls                       0.5  < [ 3.0%]
BE/Mem           Backend_Bound.Memory_Bound.Store_Bound                % Stalls                      52.2    [ 3.0%]
BE/Core          Backend_Bound.Core_Bound.Divider                      % Clocks                       0.0  < [ 3.0%]
BE/Core          Backend_Bound.Core_Bound.Ports_Utilization            % Clocks                       9.2  < [ 3.0%]
RET              Retiring.Light_Operations.FP_Arith                    % Uops                         0.9  < [ 3.0%]
RET              Retiring.Light_Operations.Memory_Operations           % Slots                        5.5  < [ 3.0%]
RET              Retiring.Light_Operations.Fused_Instructions          % Slots                        4.5  < [ 3.0%]
RET              Retiring.Light_Operations.Non_Fused_Branches          % Slots                        0.1  < [ 3.0%]
RET              Retiring.Light_Operations.Other_Light_Ops             % Slots                        7.1  < [ 3.0%]
RET              Retiring.Heavy_Operations.Few_Uops_Instructions       % Slots                        1.5  < [ 3.0%]
RET              Retiring.Heavy_Operations.Microcode_Sequencer         % Slots                        0.3    [ 3.0%]
MUX                                                                    %                              3.00
Run toplev --describe Backend_Bound^ to get more information on bottleneck
Add --run-sample to find locations
Add --nodes '!+Backend_Bound*/2,+MUX' for breakdown.

Recording only store related events

$ perf record -e mem_inst_retired.all_stores:pp -g target/profiling/deps/row_format-7489cf224545c7d6 --bench --warm-up-time 1 --noplot
Benchmarking row_format/convert_columns UInt64 with 50 columns at size 8192: Warming up for 1.0000 s
Warning: Unable to complete 100 samples in 10.0s. You may wish to increase target time to 10.7s, enable flat sampling, or reduce sample count to 60.
row_format/convert_columns UInt64 with 50 columns at size 8192
                        time:   [2.1135 ms 2.1139 ms 2.1145 ms]
                        thrpt:  [23.647 Kelem/s 23.652 Kelem/s 23.658 Kelem/s]
                 change:
                        time:   [−2.3692% −2.2443% −2.1307%] (p = 0.00 < 0.05)
                        thrpt:  [+2.1770% +2.2958% +2.4266%]
                        Performance has improved.
Found 8 outliers among 100 measurements (8.00%)
  3 (3.00%) high mild
  5 (5.00%) high severe

[ perf record: Woken up 3 times to write data ]
[ perf record: Captured and wrote 0.676 MB perf.data (3924 samples) ]

then report:

perf report -g --percent-limit 0.01 --no-children

the most expensive function is fixed::encode_not_null (as this is the only function that is being used) with this info in the annotation:

annotated info

Percent│       add    $0xfffffffffffffff8,%r9                                                                                                                  ▒
       │     <core::slice::iter::Iter<T> as core::iter::traits::iterator::Iterator>::next:                                                                     ▒
       │     ↑ jne    30                                                                                                                                       ▒
       │     ↓ jmp    dc                                                                                                                                       ▒
       │     arrow_row::fixed::encode_not_null:                                                                                                                ▒
       │     let offset = &mut offsets[value_idx + 1];                                                                                                         ▒
       │ 7d:   cmp    $0x1,%rcx                                                                                                                                ▒
       │       mov    $0x1,%eax                                                                                                                                ▒
       │       mov    $0x1,%ebx                                                                                                                                ▒
       │       cmovb  %rcx,%rbx                                                                                                                                ▒
       │       sub    %rcx,%rbx                                                                                                                                ▒
       │     core::ptr::non_null::NonNull<T>::add:                                                                                                             ▒
       │       data16 data16 data16 data16 cs nopw 0x0(%rax,%rax,1)                                                                                            ▒
       │ a0:   lea    (%rbx,%rax,1),%r10                                                                                                                       ▒
       │     arrow_row::fixed::encode_not_null:                                                                                                                ▒
       │       cmp    $0x1,%r10                                                                                                                                ▒
       │     ↓ je     f7                                                                                                                                       ▒
       │     let end_offset = *offset + T::ENCODED_LEN;                                                                                                        ▒
       │       mov    (%rdx,%rax,8),%r11                                                                                                                       ▒
       │       lea    0x9(%r11),%r10                                                                                                                           ▒
       │     core::num::<impl usize>::checked_sub:                                                                                                             ▒
       │       cmp    $0xfffffffffffffff6,%r11                                                                                                                 ▒
       │     ↓ ja     e1                                                                                                                                       ▒
       │       cmp    %rsi,%r10                                                                                                                                ▒
       │     ↓ ja     e1                                                                                                                                       ▒
       │     arrow_row::fixed::encode_not_null:                                                                                                                ▒
       │     to_write[0] = 1;                                                                                                                                  ▒
 49.57 │       movb   $0x1,(%rdi,%r11,1)                                                                                                                       ▒
       │     let mut encoded = val.encode();                                                                                                                   ▒
       │       mov    -0x8(%r8,%rax,8),%r14                                                                                                                    ▒
       │     core::num::<impl u64>::swap_bytes:                                                                                                                ▒
       │       bswap  %r14                                                                                                                                     ▒
       │     core::ptr::copy_nonoverlapping:                                                                                                                   ▒
 49.22 │       mov    %r14,0x1(%rdi,%r11,1)                                                                                                                    ▒
       │     arrow_row::fixed::encode_not_null:                                                                                                                ▒
       │     *offset = end_offset;                                                                                                                             ▒
  1.22 │       mov    %r10,(%rdx,%rax,8)                                                                                                                       ▒
       │     <core::ptr::non_null::NonNull<T> as core::cmp::PartialEq>::eq:                                                                                    ▒
       │       inc    %rax                                                                                                                                     ▒
       │       add    $0xfffffffffffffff8,%r9                                                                                                                  ▒
       │     <core::slice::iter::Iter<T> as core::iter::traits::iterator::Iterator>::next:                                                                     ◆
       │     ↑ jne    a0                                                                                                                                       ▒
       │     arrow_row::fixed::encode_not_null:                                                                                                                ▒
       │     }                                                                                                                                                 ▒
       │     }                                                                                                                                                 ▒
       │ dc:   pop    %rbx                                                                                                                                     ▒
       │       pop    %r14                                                                                                                                     ▒
       │       pop    %rbp                                                                                                                                     ▒
       │     ← ret                                                                                                                                             ▒
       │ e1:   mov    %rsi,%rdx                                                                                                                                ▒
       │     <core::ops::range::Range<usize> as core::slice::index::SliceIndex<[T]>>::index_mut:                                                               ▒
       │       lea    anon.674ea2c4ec16cc99febf090ac1512894.22.llvm.1276781284273354020,%rcx                                                                   ▒
       │       mov    %r11,%rdi                                                                                                                                ▒
       │       mov    %r10,%rsi

we see that there are 2 expensive instructions, movb and mov, the first movb is writing to_write[0] = 1;
and the second mov is writing the encoded value.

So testing with mem_inst_retired.split_stores

recording:

$ perf record -e mem_inst_retired.split_stores:pp -g target/profiling/deps/row_format-7489cf224545c7d6 --bench --warm-up-time 1 --noplot
Benchmarking row_format/convert_columns UInt64 with 50 columns at size 8192: Warming up for 1.0000 s
Warning: Unable to complete 100 samples in 10.0s. You may wish to increase target time to 10.9s, enable flat sampling, or reduce sample count to 60.
row_format/convert_columns UInt64 with 50 columns at size 8192
                        time:   [2.1362 ms 2.1367 ms 2.1373 ms]
                        thrpt:  [23.394 Kelem/s 23.400 Kelem/s 23.406 Kelem/s]
                 change:
                        time:   [+0.9806% +1.0905% +1.2080%] (p = 0.00 < 0.05)
                        thrpt:  [−1.1936% −1.0787% −0.9711%]
                        Change within noise threshold.
Found 3 outliers among 100 measurements (3.00%)
  2 (2.00%) high mild
  1 (1.00%) high severe

[ perf record: Woken up 2 times to write data ]
[ perf record: Captured and wrote 0.460 MB perf.data (2612 samples) ]

Viewing the data:

perf report -g --percent-limit 0.01 --no-children

showed for the same hot function fixed::encode_not_null:

annotated info

Percent│ 7d:   cmp    $0x1,%rcx
       │       mov    $0x1,%eax
       │       mov    $0x1,%ebx
       │       cmovb  %rcx,%rbx
       │       sub    %rcx,%rbx
       │     core::ptr::non_null::NonNull<T>::add:
       │       data16 data16 data16 data16 cs nopw 0x0(%rax,%rax,1)
       │ a0:   lea    (%rbx,%rax,1),%r10
       │     arrow_row::fixed::encode_not_null:
       │       cmp    $0x1,%r10
       │     ↓ je     f7
       │     let end_offset = *offset + T::ENCODED_LEN;
       │       mov    (%rdx,%rax,8),%r11
       │       lea    0x9(%r11),%r10
       │     core::num::<impl usize>::checked_sub:
       │       cmp    $0xfffffffffffffff6,%r11
       │     ↓ ja     e1
       │       cmp    %rsi,%r10
       │     ↓ ja     e1
       │     arrow_row::fixed::encode_not_null:
       │     to_write[0] = 1;
       │       movb   $0x1,(%rdi,%r11,1)
       │     let mut encoded = val.encode();
       │       mov    -0x8(%r8,%rax,8),%r14
       │     core::num::<impl u64>::swap_bytes:
       │       bswap  %r14
       │     core::ptr::copy_nonoverlapping:
100.00 │       mov    %r14,0x1(%rdi,%r11,1)
       │     arrow_row::fixed::encode_not_null:
       │     *offset = end_offset;
       │       mov    %r10,(%rdx,%rax,8)
       │     <core::ptr::non_null::NonNull<T> as core::cmp::PartialEq>::eq:
       │       inc    %rax
       │       add    $0xfffffffffffffff8,%r9
       │     <core::slice::iter::Iter<T> as core::iter::traits::iterator::Iterator>::next:
       │     ↑ jne    a0
       │     arrow_row::fixed::encode_not_null:
       │     }
       │     }
       │ dc:   pop    %rbx
       │       pop    %r14
       │       pop    %rbp
       │     ← ret
       │ e1:   mov    %rsi,%rdx
       │     <core::ops::range::Range<usize> as core::slice::index::SliceIndex<[T]>>::index_mut:
       │       lea    anon.674ea2c4ec16cc99febf090ac1512894.22.llvm.1276781284273354020,%rcx
       │       mov    %r11,%rdi
       │       mov    %r10,%rsi
       │     → call   *0x31ec69(%rip)        # 52de90 <_DYNAMIC+0x4a8>
       │     arrow_row::fixed::encode_not_null:
       │     let offset = &mut offsets[value_idx + 1];
       │ f7:   lea    anon.674ea2c4ec16cc99febf090ac1512894.21.llvm.1276781284273354020,%rdx
       │       mov    %rax,%rdi
       │       mov    %rcx,%rsi

that the mov instruction that writes the encoded value is now taking 100% of the samples in this function for writing across boundries.

the 100% is relative to this function, but when pressing p it toggle percent type to global
and then the percent is 92.99%, so very expensive.

I tried multiple things that keep the ordering gurrentees but still improving the performance.
one of them was to use 2 bytes for null info instead of 1 byte.

this improved performance by 18%:

    Finished `profiling` profile [optimized + debuginfo] target(s) in 0.15s
     Running benches/row_format.rs (target/profiling/deps/row_format-7489cf224545c7d6)
row_format/convert_columns UInt64 with 50 columns at size 8192
                        time:   [1.6916 ms 1.6919 ms 1.6922 ms]
                        thrpt:  [29.546 Kelem/s 29.553 Kelem/s 29.558 Kelem/s]
                 change:
                        time:   [−18.727% −18.626% −18.535%] (p = 0.00 < 0.05)
                        thrpt:  [+22.752% +22.890% +23.042%]
                        Performance has improved.

The problem, however, is that it doesn't really solve the problem, it just delay it, with the right combination of columns we can get to that problem again.
and also doing perf and report shows that even for the 50 columns of u64 with 2 bytes for null the is still high (and even higher than before):

Changing the code to not add the null byte made the code 37% faster:

    Finished `profiling` profile [optimized + debuginfo] target(s) in 4.74s
     Running benches/row_format.rs (target/profiling/deps/row_format-7489cf224545c7d6)
row_format/convert_columns UInt64 with 50 columns at size 8192
                        time:   [1.3429 ms 1.3433 ms 1.3436 ms]
                        thrpt:  [37.213 Kelem/s 37.223 Kelem/s 37.232 Kelem/s]
                 change:
                        time:   [−37.193% −37.114% −37.040%] (p = 0.00 < 0.05)
                        thrpt:  [+58.832% +59.018% +59.218%]
                        Performance has improved.
Found 13 outliers among 100 measurements (13.00%)
  5 (5.00%) high mild
  8 (8.00%) high severe

Important

I did not add the null info byte back so this remove a single instruction from the hot path. but if we move it to the start of the row and bitpack it with other columns and then use padding we could have that performance improvement.

[rluvaton]

Bottleneck 2: Branch misprediction for 50 columns non-nullable string arrays with string length between 1..=31

Note: Using non-empty string to avoid the empty string case and giving the branch predictor the optimal case
less than 32 bytes so it will be less than block size so it will go to the mini block path
and no nulls to focus on a specific code path

Benchmark code:

fn do_bench(c: &mut Criterion, name: &str, cols: Vec<ArrayRef>) {
  let fields: Vec<_> = cols
    .iter()
    .map(|x| SortField::new(x.data_type().clone()))
    .collect();
  let mut group = c.benchmark_group("row_format");
  group.throughput(criterion::Throughput::Elements(cols.len() as u64));

  group.bench_function(&format!("convert_columns {name}"), |b| {
    b.iter(|| {
      let converter = RowConverter::new(fields.clone()).unwrap();
      hint::black_box(converter.convert_columns(&cols).unwrap())
    });
  });
}


struct BinaryGenOptions {
  num_cols: usize,
  batch_size: usize,
  min_len: usize,
  max_len: usize,
}

fn run_bench_on_multi_column_with_same_string_data_type_with_no_nulls(
  c: &mut Criterion,
  opts: BinaryGenOptions
) {
  let mut seed = 0;

  let mut cols: Vec<ArrayRef> = vec![];

  for _ in 0..opts.num_cols {
    seed += 1;
    cols.push(
      Arc::new(create_string_array_with_len_range_and_prefix_and_seed::<i32>(
        opts.batch_size, 0.0, opts.min_len, opts.max_len, "", seed,
      )) as ArrayRef,
    );
  }

  do_bench(
    c,
    format!(
      "{} columns of StringArray str range: {}..={} batch_size: {} with no nulls",
      opts.num_cols,
      opts.min_len,
      opts.max_len,
      opts.batch_size
    )
      .as_str(),
    cols,
  );
}

fn row_bench(c: &mut Criterion) {
  run_bench_on_multi_column_with_same_string_data_type_with_no_nulls(
    c,
    BinaryGenOptions {
      batch_size: 8192,
      num_cols: 50,
      min_len: 1,
      max_len: 31,
    },
  );
}


criterion_group! {
    name = benches;
    config = Criterion::default().measurement_time(Duration::from_secs(10));
    targets = row_bench
}

Results on main:

$ cargo bench --features=test_utils --bench row_format --profile=profiling -- --save-baseline=main
    Finished `profiling` profile [optimized + debuginfo] target(s) in 4.74s
     Running benches/row_format.rs (target/profiling/deps/row_format-7489cf224545c7d6)
Benchmarking row_format/convert_columns 50 columns of StringArray str range: 1..=31 batch_size: 8192 with no null...: Collecting 100 samples in estimated 10.012
row_format/convert_columns 50 columns of StringArray str range: 1..=31 batch_size: 8192 with no null...
                        time:   [8.3129 ms 8.3163 ms 8.3200 ms]
                        thrpt:  [6.0096 Kelem/s 6.0123 Kelem/s 6.0148 Kelem/s]
Found 8 outliers among 100 measurements (8.00%)
  5 (5.00%) high mild
  3 (3.00%) high severe

Note

TL;DR: the problem here is the CPU branch miss prediction that it fail to predict the number of mini blocks in each value as it is uniformly randomized

Allowing us to avoid mini-blocks that was done as a way to reduce space amplification for small string
by encoding each non-empty string in <len><slice> where the length is the smallest possible type that can represent the string length (explained more below)

Step by step finding the problem (Branch_Mispredicts):

Running Top-Down analysis - Level 1

$ ~/pmu-tools/toplev.py --core S0-C0 -l1 --single-thread -v --no-desc taskset -c 0 target/profiling/deps/row_format-7489cf224545c7d6 --bench --warm-up-time 1 --noplot
Benchmarking row_format/convert_columns 50 columns of StringArray str range: 1..=31 batch_size: 8192 with no null...: Collecting 100 samples in estimated 10.073
row_format/convert_columns 50 columns of StringArray str range: 1..=31 batch_size: 8192 with no null...
                        time:   [8.3223 ms 8.3255 ms 8.3288 ms]
                        thrpt:  [6.0033 Kelem/s 6.0057 Kelem/s 6.0079 Kelem/s]
Found 8 outliers among 100 measurements (8.00%)
  7 (7.00%) high mild
  1 (1.00%) high severe

# 5.01-full-perf on Intel(R) Xeon(R) Platinum 8275CL CPU @ 3.00GHz [clx/skylake]
FE               Frontend_Bound   % Slots                       23.4
BAD              Bad_Speculation  % Slots                       26.5   <==
BE               Backend_Bound    % Slots                       11.8  <
RET              Retiring         % Slots                       38.3  <
MUX                               %                            100.00
Run toplev --describe Bad_Speculation^ to get more information on bottleneck
Add --run-sample to find locations
Add --nodes '!+Bad_Speculation*/2,+MUX' for breakdown.

It looks like the problem is Bad_Speculation.

Running Top-Down analysis - Level 2

$ ~/pmu-tools/toplev.py --core S0-C0 -l2 --single-thread -v --no-desc taskset -c 0 target/profiling/deps/row_format-7489cf224545c7d6 --bench --warm-up-time 1 --noplot
Benchmarking row_format/convert_columns 50 columns of StringArray str range: 1..=31 batch_size: 8192 with no null...: Collecting 100 samples in estimated 10.133
row_format/convert_columns 50 columns of StringArray str range: 1..=31 batch_size: 8192 with no null...
                        time:   [8.3452 ms 8.3481 ms 8.3513 ms]
                        thrpt:  [5.9871 Kelem/s 5.9894 Kelem/s 5.9914 Kelem/s]
                 change:
                        time:   [+0.2160% +0.2718% +0.3277%] (p = 0.00 < 0.05)
                        thrpt:  [−0.3267% −0.2710% −0.2156%]
                        Change within noise threshold.
Found 8 outliers among 100 measurements (8.00%)
  4 (4.00%) high mild
  4 (4.00%) high severe

# 5.01-full-perf on Intel(R) Xeon(R) Platinum 8275CL CPU @ 3.00GHz [clx/skylake]
FE               Frontend_Bound                      % Slots                       23.0    [14.0%]
BAD              Bad_Speculation                     % Slots                       25.9    [14.0%]
BE               Backend_Bound                       % Slots                       12.0  < [14.0%]
RET              Retiring                            % Slots                       39.1  < [14.0%]
FE               Frontend_Bound.Fetch_Latency        % Slots                        9.2  < [14.0%]
FE               Frontend_Bound.Fetch_Bandwidth      % Slots                       13.8  < [14.0%]
BAD              Bad_Speculation.Branch_Mispredicts  % Slots                       25.9    [14.0%]<==
BAD              Bad_Speculation.Machine_Clears      % Slots                        0.0  < [14.0%]
BE/Mem           Backend_Bound.Memory_Bound          % Slots                        4.0  < [14.0%]
BE/Core          Backend_Bound.Core_Bound            % Slots                        8.1  < [14.0%]
RET              Retiring.Light_Operations           % Slots                       36.9  < [14.0%]
RET              Retiring.Heavy_Operations           % Slots                        2.2  < [14.0%]
MUX                                                  %                             14.00
Run toplev --describe Branch_Mispredicts^ to get more information on bottleneck
Add --run-sample to find locations
Add --nodes '!+Branch_Mispredicts*/3,+MUX' for breakdown.

it is Branch_Mispredicts

Running Top-Down analysis - Level 3

$ ~/pmu-tools/toplev.py --core S0-C0 -l3 --single-thread -v --no-desc taskset -c 0 target/profiling/deps/row_format-7489cf224545c7d6 --bench --warm-up-time 1 --noplot
Benchmarking row_format/convert_columns 50 columns of StringArray str range: 1..=31 batch_size: 8192 with no null...: Collecting 100 samples in estimated 10.123
row_format/convert_columns 50 columns of StringArray str range: 1..=31 batch_size: 8192 with no null...
                        time:   [8.3599 ms 8.3622 ms 8.3647 ms]
                        thrpt:  [5.9775 Kelem/s 5.9793 Kelem/s 5.9809 Kelem/s]
                 change:
                        time:   [+0.1217% +0.1692% +0.2131%] (p = 0.00 < 0.05)
                        thrpt:  [−0.2126% −0.1689% −0.1215%]
                        Change within noise threshold.
Found 7 outliers among 100 measurements (7.00%)
  7 (7.00%) high mild

# 5.01-full-perf on Intel(R) Xeon(R) Platinum 8275CL CPU @ 3.00GHz [clx/skylake]
FE               Frontend_Bound                                        % Slots                       23.0    [ 3.0%]
BAD              Bad_Speculation.Branch_Mispredicts.Other_Mispredicts  % Slots                        0.3  < [ 3.0%]
BAD              Bad_Speculation.Machine_Clears.Other_Nukes            % Slots                        0.0  <
BE/Core          Backend_Bound.Core_Bound.Serializing_Operation        % Clocks                       0.0  < [ 3.0%]
BAD              Bad_Speculation                                       % Slots                       26.0    [ 3.0%]
BE               Backend_Bound                                         % Slots                       12.1  < [ 3.0%]
RET              Retiring                                              % Slots                       38.8  < [ 3.0%]
FE               Frontend_Bound.Fetch_Latency                          % Slots                        9.1  < [ 3.0%]
FE               Frontend_Bound.Fetch_Bandwidth                        % Slots                       13.8  < [ 3.0%]
BAD              Bad_Speculation.Branch_Mispredicts                    % Slots                       26.0    [ 3.0%]<==
BAD              Bad_Speculation.Machine_Clears                        % Slots                        0.0  < [ 3.0%]
BE/Mem           Backend_Bound.Memory_Bound                            % Slots                        4.0  < [ 3.0%]
BE/Core          Backend_Bound.Core_Bound                              % Slots                        8.1  < [ 3.0%]
RET              Retiring.Light_Operations                             % Slots                       36.6  < [ 3.0%]
RET              Retiring.Heavy_Operations                             % Slots                        2.3  < [ 3.0%]
FE               Frontend_Bound.Fetch_Latency.ICache_Misses            % Clocks                       0.1  < [ 3.0%]
FE               Frontend_Bound.Fetch_Latency.ITLB_Misses              % Clocks                       0.0  < [ 3.0%]
FE               Frontend_Bound.Fetch_Latency.Branch_Resteers          % Clocks                       6.4  < [ 3.0%]
FE               Frontend_Bound.Fetch_Latency.MS_Switches              % Clocks_est                   0.3  < [ 3.0%]
FE               Frontend_Bound.Fetch_Latency.LCP                      % Clocks                       0.0  < [ 3.0%]
FE               Frontend_Bound.Fetch_Latency.DSB_Switches             % Clocks                       8.3  < [ 3.0%]
FE               Frontend_Bound.Fetch_Bandwidth.MITE                   % Slots_est                    9.3  < [ 3.0%]
FE               Frontend_Bound.Fetch_Bandwidth.DSB                    % Slots_est                    6.9  < [ 3.0%]
BE/Mem           Backend_Bound.Memory_Bound.L1_Bound                   % Stalls                       9.1  < [ 3.0%]
BE/Mem           Backend_Bound.Memory_Bound.L2_Bound                   % Stalls                       0.4  < [ 3.0%]
BE/Mem           Backend_Bound.Memory_Bound.L3_Bound                   % Stalls                       1.3  < [ 3.0%]
BE/Mem           Backend_Bound.Memory_Bound.DRAM_Bound                 % Stalls                       0.7  < [ 3.0%]
BE/Mem           Backend_Bound.Memory_Bound.Store_Bound                % Stalls                       4.0  < [ 3.0%]
BE/Core          Backend_Bound.Core_Bound.Divider                      % Clocks                       0.0  < [ 3.0%]
BE/Core          Backend_Bound.Core_Bound.Ports_Utilization            % Clocks                      15.6  < [ 3.0%]
RET              Retiring.Light_Operations.FP_Arith                    % Uops                         0.5  < [ 3.0%]
RET              Retiring.Light_Operations.Memory_Operations           % Slots                       13.9  < [ 3.0%]
RET              Retiring.Light_Operations.Fused_Instructions          % Slots                        5.9  < [ 3.0%]
RET              Retiring.Light_Operations.Non_Fused_Branches          % Slots                        1.8  < [ 3.0%]
RET              Retiring.Light_Operations.Other_Light_Ops             % Slots                       14.5  < [ 3.0%]
RET              Retiring.Heavy_Operations.Few_Uops_Instructions       % Slots                        2.1  < [ 3.0%]
RET              Retiring.Heavy_Operations.Microcode_Sequencer         % Slots                        0.1  < [ 3.0%]
MUX                                                                    %                              3.00
Run toplev --describe Branch_Mispredicts^ to get more information on bottleneck
Add --run-sample to find locations
Add --nodes '!+Branch_Mispredicts*/3,+MUX' for breakdown.

Recording using perf the misprediction and all branches

Running perf record to see where most mispredictions while showing (mispredictions, all_branches)

$ perf record -e '{br_misp_retired.all_branches,br_inst_retired.all_branches}:pp' -g target/profiling/deps/row_format-7489cf224545c7d6 --bench --warm-up-time 1 --noplot

looking at the report:

$ perf report -g --group --percent-limit 0.01 --no-children

the most expensive in term of misprediction is arrow_row::variable::encode_one:

+   67.00%  43.93%  row_format-7489  row_format-7489cf224545c7d6  [.] arrow_row::variable::encode_one

annotated info

Percent       │     arrow_row::variable::encode_blocks:                                                                                                        ▒
              │       mov     %ecx,%r14d                                                                                                                       ▒
              │       and     $0x7,%r14d                                                                                                                       ▒
              │     <core::slice::iter::ChunksExact<T> as core::iter::traits::iterator::Iterator>::size_hint:                                                  ▒
              │       mov     %rcx,%rax                                                                                                                        ▒
              │       shr     $0x3,%rax                                                                                                                        ▒
              │     core::cmp::Ord::min:                                                                                                                       ▒
              │       cmp     %rax,%r9                                                                                                                         ▒
              │       cmovb   %r9,%rax                                                                                                                         ▒
              │     <core::iter::adapters::zip::Zip<A,B> as core::iter::adapters::zip::ZipImpl<A,B>>::next:                                                    ◆
  3.08   3.11 │       test    %rax,%rax                                                                                                                        ▒
 26.75   0.78 │     ↓ je      aa                                                                                                                               ▒
              │     arrow_row::variable::encode_blocks:                                                                                                        ▒
              │     let remainder = chunks.remainder();                                                                                                        ▒
              │     for (input, output) in chunks.clone().zip(to_write.chunks_exact_mut(SIZE + 1)) {                                                           ▒
              │     let input: &[u8; SIZE] = input.try_into().unwrap();                                                                                        ▒
              │     let out_block: &mut [u8; SIZE] = (&mut output[..SIZE]).try_into().unwrap();                                                                ▒
              │                                                                                                                                                ▒
              │     *out_block = *input;                                                                                                                       ▒
              │       mov     (%rdx),%r9                                                                                                                       ▒
              │       mov     %r9,0x1(%rdi)                                                                                                                    ▒
              │                                                                                                                                                ▒
              │     // Indicate that there are further blocks to follow                                                                                        ▒
              │     output[SIZE] = BLOCK_CONTINUATION;                                                                                                         ▒
              │       movb    $0xff,0x9(%rdi)                                                                                                                  ▒
              │     <core::iter::adapters::zip::Zip<A,B> as core::iter::adapters::zip::ZipImpl<A,B>>::next:                                                    ▒
  6.92   5.40 │    ┌──cmp     $0x1,%rax                                                                                                                        ▒
 26.92   2.92 │    ├──je      aa                                                                                                                               ▒
              │    │arrow_row::variable::encode_blocks:                                                                                                        ▒
              │    │*out_block = *input;                                                                                                                       ▒
              │    │  mov     0x8(%rdx),%r9                                                                                                                    ▒
              │    │  mov     %r9,0xa(%rdi)                                                                                                                    ▒
              │    │output[SIZE] = BLOCK_CONTINUATION;                                                                                                         ▒
              │    │  movb    $0xff,0x12(%rdi)                                                                                                                 ▒
              │    │<core::iter::adapters::zip::Zip<A,B> as core::iter::adapters::zip::ZipImpl<A,B>>::next:                                                    ▒
 13.33   3.66 │    │  cmp     $0x2,%rax                                                                                                                        ▒
 16.83   3.57 │    │↓ je      aa                                                                                                                               ▒
              │    │arrow_row::variable::encode_blocks:                                                                                                        ▒
              │    │*out_block = *input;                                                                                                                       ▒
              │    │  mov     0x10(%rdx),%r9                                                                                                                   ▒
              │    │  mov     %r9,0x13(%rdi)                                                                                                                   ▒
              │    │output[SIZE] = BLOCK_CONTINUATION;                                                                                                         ▒
              │    │  movb    $0xff,0x1b(%rdi)                                                                                                                 ▒
              │    │<core::iter::adapters::zip::Zip<A,B> as core::iter::adapters::zip::ZipImpl<A,B>>::next:                                                    ▒
              │    │  cmp     $0x3,%rax                                                                                                                        ▒
  0.00   5.24 │    │↓ je      aa                                                                                                                               ▒
              │    │arrow_row::variable::encode_blocks:                                                                                                        ▒
              │    │*out_block = *input;                                                                                                                       ▒
              │    │  mov     0x18(%rdx),%rax                                                                                                                  ▒
              │    │  mov     %rax,0x1c(%rdi)                                                                                                                  ▒
              │    │output[SIZE] = BLOCK_CONTINUATION;                                                                                                         ▒
              │    │  movb    $0xff,0x24(%rdi)                                                                                                                 ▒
              │    │arrow_row::variable::encode_one:                                                                                                           ▒
              │    │1 + encode_blocks::<MINI_BLOCK_SIZE>(&mut out[1..], val)                                                                                   ▒

we see that the misprediction is on the iterator of the blocks in variable::encode_blocks function

for (input, output) in chunks.clone().zip(to_write.chunks_exact_mut(SIZE + 1)) {

changing the code to avoid the blocks entirely
(as they are a way to have a slice of unsized bytes without prefix length so sorting will work on different lengths bytes)

by encoding the length at the start (in the smallest type possible to avoid a lot of space for small string)
and then having the slice as is:

updated code:

/// Faster encode_blocks that first copy all the data and then iterate over it and
#[inline]
fn fast_encode_bytes(out: &mut [u8], val: &[u8], opts: SortOptions) -> usize {
    // Write `2_u8` to demarcate as non-empty, non-null string
    out[0] = NON_EMPTY_SENTINEL;

    // TODO - in desc should do max minus the length so the order will be different (longer strings sort before shorter ones)
    let start_data_offset = {
        let len = val.len();

        match get_number_of_bits_needed_to_encode(len) {
            0 => {
                out[0] = EMPTY_SENTINEL;
                return 1;
            }
            1 => {
                out[0] |= LENGTH_TYPE_U8;

                // encode length
                let start_data_offset = 1 + size_of::<u8>();
                unsafe { out.get_unchecked_mut(1..start_data_offset) }.copy_from_slice(&(len as u8).to_be_bytes());

                start_data_offset
            }
            2 => {
                out[0] |= LENGTH_TYPE_U16;

                // encode length
                let start_data_offset = 1 + size_of::<u16>();
                unsafe { out.get_unchecked_mut(1..start_data_offset) }.copy_from_slice(&(len as u16).to_be_bytes());

                start_data_offset
            }
            4 => {
                out[0] |= LENGTH_TYPE_U32;

                // encode length
                let start_data_offset = 1 + size_of::<u32>();
                unsafe { out.get_unchecked_mut(1..start_data_offset) }.copy_from_slice(&(len as u32).to_be_bytes());

                start_data_offset
            }
            8 => {
                out[0] |= LENGTH_TYPE_U64;

                // encode length
                let start_data_offset = 1 + size_of::<u64>();
                unsafe { out.get_unchecked_mut(1..start_data_offset) }.copy_from_slice(&(len as u64).to_be_bytes());

                start_data_offset
            }
            bits_required => {
                unreachable!("invalid length type {len}. numbr of bits required {bits_required}");
            }
        }
    };

    let len = start_data_offset + val.len();
    out[start_data_offset..len].copy_from_slice(val);

    len
}

We will have 33% time improvement.

$ cargo bench --features=test_utils --bench row_format --profile=profiling -- --baseline=main
    Finished `profiling` profile [optimized + debuginfo] target(s) in 4.69s
     Running benches/row_format.rs (target/profiling/deps/row_format-7489cf224545c7d6)
Benchmarking row_format/convert_columns 50 columns of StringArray str range: 1..=31 batch_size: 8192 with no null...: Collecting 100 samples in estimated 10.059
row_format/convert_columns 50 columns of StringArray str range: 1..=31 batch_size: 8192 with no null...
                        time:   [5.5475 ms 5.5514 ms 5.5556 ms]
                        thrpt:  [9.0000 Kelem/s 9.0067 Kelem/s 9.0131 Kelem/s]
                 change:
                        time:   [−33.301% −33.246% −33.187%] (p = 0.00 < 0.05)
                        thrpt:  [+49.672% +49.804% +49.926%]
                        Performance has improved.

the type of the slice can be put at the metadata at the beginning of the rows if performance is better (I don't think so).

Running Top-Down analysis again on the updated code:

and if we run top level again for level 1:

$ ~/pmu-tools/toplev.py --core S0-C0 -l1 --single-thread -v --no-desc taskset -c 0 target/profiling/deps/row_format-7489cf224545c7d6 --bench --warm-up-time 1 --noplot
Benchmarking row_format/convert_columns 50 columns of StringArray str range: 1..=31 batch_size: 8192 with no null...: Collecting 100 samples in estimated 10.018
row_format/convert_columns 50 columns of StringArray str range: 1..=31 batch_size: 8192 with no null...
                        time:   [5.5393 ms 5.5431 ms 5.5469 ms]
                        thrpt:  [9.0140 Kelem/s 9.0203 Kelem/s 9.0264 Kelem/s]
                 change:
                        time:   [−34.268% −34.217% −34.168%] (p = 0.00 < 0.05)
                        thrpt:  [+51.901% +52.016% +52.134%]
                        Performance has improved.

# 5.01-full-perf on Intel(R) Xeon(R) Platinum 8275CL CPU @ 3.00GHz [clx/skylake]
FE               Frontend_Bound   % Slots                       20.7
BAD              Bad_Speculation  % Slots                       21.5   <==
BE               Backend_Bound    % Slots                       14.6  <
RET              Retiring         % Slots                       43.3  <
MUX                               %                            100.00
Run toplev --describe Bad_Speculation^ to get more information on bottleneck
Add --run-sample to find locations
Add --nodes '!+Bad_Speculation*/2,+MUX' for breakdown.

and level 2:

$ ~/pmu-tools/toplev.py --core S0-C0 -l2 --single-thread -v --no-desc taskset -c 0 target/profiling/deps/row_format-7489cf224545c7d6 --bench --warm-up-time 1 --noplot
Benchmarking row_format/convert_columns 50 columns of StringArray str range: 1..=31 batch_size: 8192 with no null...: Collecting 100 samples in estimated 10.082
row_format/convert_columns 50 columns of StringArray str range: 1..=31 batch_size: 8192 with no null...
                        time:   [5.5274 ms 5.5308 ms 5.5344 ms]
                        thrpt:  [9.0344 Kelem/s 9.0403 Kelem/s 9.0459 Kelem/s]
                 change:
                        time:   [−0.3163% −0.2212% −0.1278%] (p = 0.00 < 0.05)
                        thrpt:  [+0.1280% +0.2217% +0.3173%]
                        Change within noise threshold.
Found 18 outliers among 100 measurements (18.00%)
  18 (18.00%) high mild

# 5.01-full-perf on Intel(R) Xeon(R) Platinum 8275CL CPU @ 3.00GHz [clx/skylake]
FE               Frontend_Bound                      % Slots                       20.7    [14.0%]
BAD              Bad_Speculation                     % Slots                       21.5    [14.0%]
BE               Backend_Bound                       % Slots                       14.5  < [14.0%]
RET              Retiring                            % Slots                       43.3  < [14.0%]
FE               Frontend_Bound.Fetch_Latency        % Slots                       10.6    [14.0%]
FE               Frontend_Bound.Fetch_Bandwidth      % Slots                       10.1  < [14.0%]
BAD              Bad_Speculation.Branch_Mispredicts  % Slots                       21.5    [14.0%]<==
BAD              Bad_Speculation.Machine_Clears      % Slots                        0.0  < [14.0%]
BE/Mem           Backend_Bound.Memory_Bound          % Slots                        5.6  < [14.0%]
BE/Core          Backend_Bound.Core_Bound            % Slots                        8.9  < [14.0%]
RET              Retiring.Light_Operations           % Slots                       39.9  < [14.0%]
RET              Retiring.Heavy_Operations           % Slots                        3.4  < [14.0%]
MUX                                                  %                             14.00
Run toplev --describe Branch_Mispredicts^ to get more information on bottleneck
Add --run-sample to find locations
Add --nodes '!+Branch_Mispredicts*/3,+MUX' for breakdown.

and level 3:

$ ~/pmu-tools/toplev.py --core S0-C0 -l3 --single-thread -v --no-desc taskset -c 0 target/profiling/deps/row_format-7489cf224545c7d6 --bench --warm-up-time 1 --noplot
Benchmarking row_format/convert_columns 50 columns of StringArray str range: 1..=31 batch_size: 8192 with no null...: Collecting 100 samples in estimated 10.003
row_format/convert_columns 50 columns of StringArray str range: 1..=31 batch_size: 8192 with no null...
                        time:   [5.5268 ms 5.5302 ms 5.5337 ms]
                        thrpt:  [9.0355 Kelem/s 9.0413 Kelem/s 9.0468 Kelem/s]
                 change:
                        time:   [−0.1050% −0.0117% +0.0828%] (p = 0.80 > 0.05)
                        thrpt:  [−0.0827% +0.0117% +0.1051%]
                        No change in performance detected.
Found 15 outliers among 100 measurements (15.00%)
  15 (15.00%) high mild

# 5.01-full-perf on Intel(R) Xeon(R) Platinum 8275CL CPU @ 3.00GHz [clx/skylake]
FE               Frontend_Bound                                        % Slots                       20.8    [ 3.0%]
BAD              Bad_Speculation.Branch_Mispredicts.Other_Mispredicts  % Slots                        0.0  < [ 3.0%]
BAD              Bad_Speculation.Machine_Clears.Other_Nukes            % Slots                        0.0  <
BE/Core          Backend_Bound.Core_Bound.Serializing_Operation        % Clocks                       0.0  < [ 3.0%]
BAD              Bad_Speculation                                       % Slots                       21.6    [ 3.0%]
BE               Backend_Bound                                         % Slots                       14.7  < [ 3.0%]
RET              Retiring                                              % Slots                       43.0  < [ 3.0%]
FE               Frontend_Bound.Fetch_Latency                          % Slots                       10.6    [ 3.0%]
FE               Frontend_Bound.Fetch_Bandwidth                        % Slots                       10.3    [ 3.0%]
BAD              Bad_Speculation.Branch_Mispredicts                    % Slots                       21.6    [ 3.0%]<==
BAD              Bad_Speculation.Machine_Clears                        % Slots                        0.0  < [ 3.0%]
BE/Mem           Backend_Bound.Memory_Bound                            % Slots                        5.7  < [ 3.0%]
BE/Core          Backend_Bound.Core_Bound                              % Slots                        9.0  < [ 3.0%]
RET              Retiring.Light_Operations                             % Slots                       39.6  < [ 3.0%]
RET              Retiring.Heavy_Operations                             % Slots                        3.4  < [ 3.0%]
FE               Frontend_Bound.Fetch_Latency.ICache_Misses            % Clocks                       0.1  < [ 3.0%]
FE               Frontend_Bound.Fetch_Latency.ITLB_Misses              % Clocks                       0.0  < [ 3.0%]
FE               Frontend_Bound.Fetch_Latency.Branch_Resteers          % Clocks                       5.4    [ 3.0%]
FE               Frontend_Bound.Fetch_Latency.MS_Switches              % Clocks_est                   0.3  < [ 3.0%]
FE               Frontend_Bound.Fetch_Latency.LCP                      % Clocks                       0.0    [ 3.0%]
FE               Frontend_Bound.Fetch_Latency.DSB_Switches             % Clocks                       6.2    [ 3.0%]
FE               Frontend_Bound.Fetch_Bandwidth.MITE                   % Slots_est                    7.7  < [ 3.0%]
FE               Frontend_Bound.Fetch_Bandwidth.DSB                    % Slots_est                    4.1  < [ 3.0%]
BE/Mem           Backend_Bound.Memory_Bound.L1_Bound                   % Stalls                      12.9  < [ 3.0%]
BE/Mem           Backend_Bound.Memory_Bound.L2_Bound                   % Stalls                       0.5  < [ 3.0%]
BE/Mem           Backend_Bound.Memory_Bound.L3_Bound                   % Stalls                       1.4  < [ 3.0%]
BE/Mem           Backend_Bound.Memory_Bound.DRAM_Bound                 % Stalls                       0.5  < [ 3.0%]
BE/Mem           Backend_Bound.Memory_Bound.Store_Bound                % Stalls                       4.8  < [ 3.0%]
BE/Core          Backend_Bound.Core_Bound.Divider                      % Clocks                       0.0  < [ 3.0%]
BE/Core          Backend_Bound.Core_Bound.Ports_Utilization            % Clocks                      22.1  < [ 3.0%]
RET              Retiring.Light_Operations.FP_Arith                    % Uops                         0.4  < [ 3.0%]
RET              Retiring.Light_Operations.Memory_Operations           % Slots                       15.6  < [ 3.0%]
RET              Retiring.Light_Operations.Fused_Instructions          % Slots                        5.1  < [ 3.0%]
RET              Retiring.Light_Operations.Non_Fused_Branches          % Slots                        3.0  < [ 3.0%]
RET              Retiring.Light_Operations.Other_Light_Ops             % Slots                       15.4  < [ 3.0%]
RET              Retiring.Heavy_Operations.Few_Uops_Instructions       % Slots                        3.3  < [ 3.0%]
RET              Retiring.Heavy_Operations.Microcode_Sequencer         % Slots                        0.1  < [ 3.0%]
MUX                                                                    %                              3.00
Run toplev --describe Branch_Mispredicts^ to get more information on bottleneck
Add --run-sample to find locations
Add --nodes '!+Branch_Mispredicts*/3,+MUX' for breakdown.

We are still branch misprediction bounded but much less.

Lets see what was mispredicted:

$ perf record -e '{br_misp_retired.all_branches,br_inst_retired.all_branches}:pp' -g target/profiling/deps/row_format-7489cf224545c7d6 --bench --warm-up-time 1 --noplot
$ perf report -g --group --percent-limit 0.01 --no-children

we are now seeing this:

Samples: 43K of events 'anon group { br_misp_retired.all_branches, br_inst_retired.all_branches }', Event count (approx.): 17292789079
          Overhead  Command          Shared Object                Symbol
+   97.68%  23.41%  row_format-7489  libc.so.6                    [.] __memmove_evex_unaligned_erms
+    1.80%   0.71%  row_format-7489  row_format-7489cf224545c7d6  [.] core::slice::sort::shared::smallsort::small_sort_network
+    0.21%  33.24%  row_format-7489  row_format-7489cf224545c7d6  [.] arrow_row::variable::fast_encode_bytes
+    0.11%   0.41%  row_format-7489  row_format-7489cf224545c7d6  [.] core::slice::sort::unstable::quicksort::quicksort
+    0.11%   0.26%  row_format-7489  row_format-7489cf224545c7d6  [.] <alloc::string::String as core::iter::traits::collect::Extend<char>>::extend
+    0.05%  24.94%  row_format-7489  row_format-7489cf224545c7d6  [.] arrow_row::row_lengths
+    0.05%   0.30%  row_format-7489  row_format-7489cf224545c7d6  [.] criterion::stats::univariate::mixed::bootstrap

Running stats:

$ perf stat  -e br_misp_retired.all_branches,int_misc.recovery_cycles,cycles target/profiling/deps/row_format-7489cf224545c7d6 --bench --warm-up-time 1 --noplot
Benchmarking row_format/convert_columns 50 columns of StringArray str range: 1..=31 batch_size: 8192 with no null...: Collecting 100 samples in estimated 10.108
row_format/convert_columns 50 columns of StringArray str range: 1..=31 batch_size: 8192 with no null...
                        time:   [5.5396 ms 5.5437 ms 5.5480 ms]
                        thrpt:  [9.0123 Kelem/s 9.0192 Kelem/s 9.0259 Kelem/s]
                 change:
                        time:   [−1.2486% −1.1486% −1.0503%] (p = 0.00 < 0.05)
                        thrpt:  [+1.0615% +1.1620% +1.2644%]
                        Performance has improved.


 Performance counter stats for 'target/profiling/deps/row_format-7489cf224545c7d6 --bench --warm-up-time 1 --noplot':

         757542529      br_misp_retired.all_branches
        4241897496      int_misc.recovery_cycles
       46949042964      cycles

      12.065393734 seconds time elapsed

      12.043439000 seconds user
       0.020005000 seconds sys

which is slower than before in terms of cycles, but because we are running more iterations now.

if we run without any iterations (no --bench so it should only run once):

$ perf stat  -e br_misp_retired.all_branches,int_misc.recovery_cycles,cycles target/profiling/deps/row_format-7489cf224545c7d6 --noplot
Testing row_format/convert_columns 50 columns of StringArray str range: 1..=31 batch_size: 8192 with no null...
Success


 Performance counter stats for 'target/profiling/deps/row_format-7489cf224545c7d6 --noplot':

           1364986      br_misp_retired.all_branches
           8496676      int_misc.recovery_cycles
         229098727      cycles

       0.060764710 seconds time elapsed

       0.050737000 seconds user
       0.010107000 seconds sys

and for main:

$ perf stat  -e br_misp_retired.all_branches,int_misc.recovery_cycles,cycles target/profiling/deps/row_format-7489cf224545c7d6 --noplot
Testing row_format/convert_columns 50 columns of StringArray str range: 1..=31 batch_size: 8192 with no null...
Success


 Performance counter stats for 'target/profiling/deps/row_format-7489cf224545c7d6 --noplot':

           1576148      br_misp_retired.all_branches
           9737113      int_misc.recovery_cycles
         248169052      cycles

       0.066125641 seconds time elapsed

       0.066172000 seconds user
       0.000000000 seconds sys

we use fewer cycles. you can verify that it actually run our function by using perf record

if we run default stats:

for main:

$ perf stat target/profiling/deps/row_format-7489cf224545c7d6 --noplot
Testing row_format/convert_columns 50 columns of StringArray str range: 1..=31 batch_size: 8192 with no null...
Success


 Performance counter stats for 'target/profiling/deps/row_format-7489cf224545c7d6 --noplot':

             68.63 msec task-clock                       #    0.985 CPUs utilized
                 1      context-switches                 #   14.571 /sec
                 0      cpu-migrations                   #    0.000 /sec
              4575      page-faults                      #   66.664 K/sec
         246976894      cycles                           #    3.599 GHz
         561019003      instructions                     #    2.27  insn per cycle
          92611997      branches                         #    1.349 G/sec
           1584553      branch-misses                    #    1.71% of all branches

       0.069667346 seconds time elapsed

       0.059826000 seconds user
       0.009944000 seconds sys

with this improvement:

$ perf stat target/profiling/deps/row_format-7489cf224545c7d6 --noplot
Testing row_format/convert_columns 50 columns of StringArray str range: 1..=31 batch_size: 8192 with no null...
Success


 Performance counter stats for 'target/profiling/deps/row_format-7489cf224545c7d6 --noplot':

             63.59 msec task-clock                       #    0.983 CPUs utilized
                 1      context-switches                 #   15.726 /sec
                 0      cpu-migrations                   #    0.000 /sec
              4069      page-faults                      #   63.987 K/sec
         228843878      cycles                           #    3.599 GHz
         542384326      instructions                     #    2.37  insn per cycle
          88943721      branches                         #    1.399 G/sec
           1366042      branch-misses                    #    1.54% of all branches

       0.064687865 seconds time elapsed

       0.064722000 seconds user
       0.000000000 seconds sys

less branch misses and more instructions per cycle.

so this is a win.
and the more time and cycles were due to more iterations.

more reason to avoid sort guarantees.

[alamb]

If the basic idea is to create a row format that is targeted for equality (rather than comparison) that seems reasonable to me

The engineering challenge will be, in my mind, how to avoid re-implementing a bunch of code that is very similar but not quite the same as the existing row converter

[alamb]

BTW I think we have often found that implementing specialized versions of the code for different arrow types (rather than using the generic row format) results in better performance, though it is not as general as the RowFormat

In other words, what seems to have worked well in the past is:

1. Type specializations for the important usecases
2. Use the Row Format for the general case / fallback