You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "rluvaton (via GitHub)" <gi...@apache.org> on 2026/01/01 14:46:42 UTC
[I] Row format that does not guarantee ordering of columns [arrow-rs]
rluvaton opened a new issue, #9083:
URL: https://github.com/apache/arrow-rs/issues/9083
**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**
<!--
A clear and concise description of what you want to happen.
-->
**Describe alternatives you've considered**
<!--
A clear and concise description of any alternative solutions or features you've considered.
-->
**Additional context**
<!--
Add any other context or screenshots about the feature request here.
-->
-----------
All my benchmarks and profiling were done on the most reliable machine I could get:
```
c5.metal
```
<details><summary>Env</summary>
<p>
```bash
[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)
```
```bash
$ ./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
```
</p>
</details>
------
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`:
```toml
[build]
rustflags = ["-C", "force-frame-pointers=yes"]
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] New row format that does not guarantee ordering of columns [arrow-rs]
Posted by "rluvaton (via GitHub)" <gi...@apache.org>.
rluvaton commented on issue #9083:
URL: https://github.com/apache/arrow-rs/issues/9083#issuecomment-3819117741
I'm already implementing it in my own project but I thought it would be beneficial for others as shuffle is a common operation
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] New row format that does not guarantee ordering of columns [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #9083:
URL: https://github.com/apache/arrow-rs/issues/9083#issuecomment-3710188287
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
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] New row format that does not guarantee ordering of columns [arrow-rs]
Posted by "rluvaton (via GitHub)" <gi...@apache.org>.
rluvaton commented on issue #9083:
URL: https://github.com/apache/arrow-rs/issues/9083#issuecomment-3756262948
The POC PR looks good in term of performance (and contains a lot of commented code and playing around) that I want to start a discussion.
POC PR:
- #9164
**I first laying out how I plan to integrate this the easiest way for reviewers and what optimizations I done in that PR in each step here**
### How I plan to add those in a way that is easy to review and understand
If we plan to process, I will create these chains of PRs for better review and make it easy to understand, each one will focus on one thing and everything except the first PR will be small.
#### 1. Just copy the code and little tweaks
1. Copy the entire RowConverter and all the conversion code to a new directory named `unordered_row`
2. Rename to `Unordered*`
3. Remove the Ord trait - as we will no longer guarantee it (even though at this step we just copied the code)
4. update tests
5. Change the API to get `Fields` instead of `SortField` - this is needed so I won't introduce a breaking change later
This will be the largest PR but it is just made to have a baseline and make it easy to review, especially for people that are familiar with RowConverter.
#### 2. Add benchmarks
just run all row format benchmarks on the unordered row format as well
So next Pull request can have a baseline
#### 3. Remove all sort and order related code
because the first PR is just a copy to make it easier to review.
#### 4. Implement Optimization for field reordering
Because we no longer guarantee ordering, we can reorder fields so that:
1. fields with the same type can be grouped together so later optimization on encoding multiple columns at once is possible
2. optimize for cache lines (so we won't write u64, u8, u64 and instead write u64, u64, u8 so it will be mostly aligned - and later we can add padding if we want)
3. encoding fields with same type right after another improve code locality
This will also help with the store bottleneck as described here:
- https://github.com/apache/arrow-rs/issues/9083#issuecomment-3703789536
#### 5. Encode nulls at the beginning of a row and make it bit packed + metadata bit
currently we encode a null in a full byte which is wasteful, so we will bit pack all nullability
this is done to save space.
there will be an optional metadata bit/byte depending on the number of columns to encode that tells if all columns are valid or unknown to fast skip rows
will have detailed explanation of the code in the matching PR
#### 6. Don't encode nulls for non nullable fields
Skip null encoding for non nullable fields to save computation
This will also help with the store bottleneck as described here:
- https://github.com/apache/arrow-rs/issues/9083#issuecomment-3703789536
#### 7. Implement encoding 4 same type primitive columns at a time.
because we can change the ordering of the encoded data, we will group together columns with the same types and also group by nullability.
so we can implement encoding of 4 columns at a time to really take advantage of all the CPU units and to also reduce the amount of jumps we do in memory if we need to come back every time
#### 8. Implement custom boolean encoding that save space
Instead of encoding 1 bit and 1 byte for the null and boolean respectively, we will encode both in a single byte (we can encode a boolean in a single byte if we decide not to encode the nulls in the same byte. or bit pack them like nulls.)
#### 9. Change how we encode binary based data to be simpler and reduce branches + logic:
will encode the length and then will encode the bytes (just copy the bytes as is).
to avoid small strings (like 1-8 bytes) have the encoded length larger than the actual byte we will use a dynamic type to encode the length.
if the length is in the range of `u8` we will encode it as u8, and if in the range of u16 will encode it as u16 and so on.
this means that if most string are below `65,536` we will only use 2 bytes to encode the length.
and if I want to encode a string with length `65,535` with this impl it will only use `65,535 + 2` (+ ctrl byte) compared to ~`67,500` bytes in the current implementation due to marker byte between each block of 32 bytes.
This also will reduce the amount of branch as we do not copy in blocks and have an iterator of blocks, and the branch of what type should use for the length has pretty wide range so much less probability for mispredicting the length.
BTW branch misprediction here was one of the main bottlenecks as described in detail here:
- https://github.com/apache/arrow-rs/issues/9083#issuecomment-3703789605
##### 10. Improve list encoding
Encode the number of items first, then the lengths and then copy the child rows as is. this will allow for large continues data copy.
##### 11. Improve list encoding even further
Instead of encoding the lengths as 32 bit or 64 bit, we will encode them all in the same type that will be the smallest type that is needed to encode the worst case scenario so we can reduce space.
--------
The row convertor will guarantee as little as possible to allow for further optimizations to be made.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] New row format that does not guarantee ordering of columns [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #9083:
URL: https://github.com/apache/arrow-rs/issues/9083#issuecomment-3710183483
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
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] New row format that does not guarantee ordering of columns [arrow-rs]
Posted by "rluvaton (via GitHub)" <gi...@apache.org>.
rluvaton commented on issue #9083:
URL: https://github.com/apache/arrow-rs/issues/9083#issuecomment-3801346219
For 227 columns, these are the timing:
| Benchmark | Time (mean) | Time Range |
|-----------|-------------|------------|
| shuffle/optimized_row_format_approach | 5.3059 s | [5.2993 s - 5.3122 s] |
| shuffle/optimized_row_format_approach going partition wise | 5.3291 s | [5.3150 s - 5.3455 s] |
| shuffle/row_format_approach | 6.1024 s | [6.0741 s - 6.1393 s] |
| shuffle/row_format_approach going partition wise | 6.1486 s | [6.1340 s - 6.1644 s] |
| shuffle/interleave_column_wise_approach | 7.3626 s | [7.3108 s - 7.4122 s] |
| shuffle/interleave_approach | 7.5366 s | [7.4260 s - 7.6677 s] |
| shuffle/take_to_builders_column_wise_approach | 9.8153 s | [9.0891 s - 10.499 s] |
| shuffle/take_to_builders_approach | 16.362 s | [12.556 s - 21.725 s] |
| shuffle/take_approach | 24.967 s | [23.513 s - 26.464 s] |
| shuffle/take_column_wise_approach | 26.216 s | [25.264 s - 27.461 s] |
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] New row format that does not guarantee ordering of columns [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #9083:
URL: https://github.com/apache/arrow-rs/issues/9083#issuecomment-3759332347
> @alamb I'm talking about the shuffling/partitioning operation - Consider you have a 10 batches with 50 columns, and you want to split to 3 partitions based on a round robin or hash, so each row will be needed to copy to a different place.
If I were implementing this operation I would:
1. Compute the input indices to send to each partition
2. Call the [take](https://docs.rs/arrow/latest/arrow/compute/kernels/take/fn.take_record_batch.html) kernel to create the relevant output arrays
This would result in exactly one data copy (to the output array)
> you might say that but encoding to rows is the same thing and even worse as you copy twice.
Indeed, In my mind, any use of a Row Format would result in at least 2 copies (into the Row Format, and back to the output Arrays)
> you are right but in my tests I saw that it is faster to (1) encode to this format (2) partition and (3) decode back rather than to encode it using specialized implementation per type
What tests are you referring to? Maybe I would understand better if you could describe what your test was doing
> @alamb in the case when we already need to convert to rows (in the fallback implementation) the ordering doesn't matter and we can use this new row format which will make it faster.
Right -- I am saying this proposal would make the fallback faster. I was suggesting avoiding the fallback entirely (with specialized implementation)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] New row format that does not guarantee ordering of columns [arrow-rs]
Posted by "rluvaton (via GitHub)" <gi...@apache.org>.
rluvaton commented on issue #9083:
URL: https://github.com/apache/arrow-rs/issues/9083#issuecomment-3764140243
> > @alamb I'm talking about the shuffling/partitioning operation - Consider you have a 10 batches with 50 columns, and you want to split to 3 partitions based on a round robin or hash, so each row will be needed to copy to a different place.
>
> If I were implementing this operation I would:
> 1. Compute the input indices to send to each partition
> 2. Call the [take](https://docs.rs/arrow/latest/arrow/compute/kernels/take/fn.take_record_batch.html) kernel to create the relevant output arrays
>
> This would result in exactly one data copy (to the output array)
But what if you need to partition to 1500 partitions?
If batch size is 8192 you will have for each partition ~6 elements.
So for each partition I will do take on 6 elements and it will output an array of 6 elements per partition.
And every item will be a cache miss if the data is evenly distributed and you don't take advantage of the data already in the cache
And if you have 30 columns (or even 500 like I saw sometimes) then you will have 1500 * 30 cache misses per batch
And if want the partition to output batches with the configured batch size 8192 I will to concat again so another copy.
And if you say, ok, so if you had the feature for take to builders (like some open issue about that)
Then I will say that you still have the cache misses.
But you will say, you have cache misses between elements as well
yes but I have 1 source and 1 dest so it is more predictable and one of the optimization is to encode multiple columns at a time.
But then you say, ok so instead don't use take and go over that array and for each index copy it to the destination builder for that partition.
And this was my current approach before this. But you are doing small data copies for each row. And with row format you doing larger data copies (entire row)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] New row format that does not guarantee ordering of columns [arrow-rs]
Posted by "rluvaton (via GitHub)" <gi...@apache.org>.
rluvaton commented on issue #9083:
URL: https://github.com/apache/arrow-rs/issues/9083#issuecomment-3764170446
> > you are right but in my tests I saw that it is faster to (1) encode to this format (2) partition and (3) decode back rather than to encode it using specialized implementation per type
>
> What tests are you referring to? Maybe I would understand better if you could describe what your test was doing
>
Some spark workload of a client
> > @alamb in the case when we already need to convert to rows (in the fallback implementation) the ordering doesn't matter and we can use this new row format which will make it faster.
>
> Right -- I am saying this proposal would make the fallback faster. I was suggesting avoiding the fallback entirely (with specialized implementation)
Sometimes you either can't or don't wanna bother in implementing a specialized implementation, for example struct of lists of structs
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] New row format that does not guarantee ordering of columns [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #9083:
URL: https://github.com/apache/arrow-rs/issues/9083#issuecomment-3818852658
Thanks @rluvaton -- I realistically am not going to have time to review this proposal in any level of detail. I think I am struggling to maintain the existing code we have, and I am not sure we have bandwidth to maintain a major new feature.
Is there some way to implement it downstream for a while and then we can potentially upstream it once it is more mature / shows its value?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] New row format that does not guarantee ordering of columns [arrow-rs]
Posted by "rluvaton (via GitHub)" <gi...@apache.org>.
rluvaton commented on issue #9083:
URL: https://github.com/apache/arrow-rs/issues/9083#issuecomment-3756386372
> > row format is also useful when you need to copy a lot of columns around, for example when shuffling
>
> I don't understand why row format would be used here -- Arrow already has a format that is optimzied for copying values around (the IPC format)
I'm talking about the shuffling/partitioning operation - Consider you have a 10 batches with 50 columns, and you want to split to 3 partitions based on a round robin or hash, so each row will be needed to copy to a different place.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] New row format that does not guarantee ordering of columns [arrow-rs]
Posted by "rluvaton (via GitHub)" <gi...@apache.org>.
rluvaton commented on issue #9083:
URL: https://github.com/apache/arrow-rs/issues/9083#issuecomment-3756252103
The results of the benchmarks are promising:
- https://github.com/apache/arrow-rs/pull/9164#issuecomment-3752998682
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] New row format that does not guarantee ordering of columns [arrow-rs]
Posted by "rluvaton (via GitHub)" <gi...@apache.org>.
rluvaton commented on issue #9083:
URL: https://github.com/apache/arrow-rs/issues/9083#issuecomment-3756253686
row format is also useful when you need to copy a lot of columns around, for example when shuffling
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] New row format that does not guarantee ordering of columns [arrow-rs]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on issue #9083:
URL: https://github.com/apache/arrow-rs/issues/9083#issuecomment-3765363076
Can you maybe produce / show a usecase / benchmark showing a row format to be faster for the "wide table" case?
I think I see your point that producing the data might be faster (as you can colocate the row-values), but at some point you would also need to decode them into multiple `RecordBatches` paying the same price?
I also wondered sometimes earlier if in some cases we want to have/support more control over how multiple record batches are allocated and colocate arrays from different batches or different columns, perhaps nullifying the need of creating a new format altogether and avoid many new code paths (as all code understands `RecordBatch` / `Array`)?
Colocate different batches:
```
[allocated region col1 ]
col1: [1, 2, 3, 4, 5, 6] [1, 2, 3, 4, 5, 6] [1, 2, 3, 4, 5, 6] [1, 2, 3, 4, 5, 6] [1, 2, 3, 4, 5, 6]
[allocated region col2 ]
col2: ["a", "b", "c"] ["a", "b", "c"] ["a", "b", "c"] ["a", "b", "c"] ["a", "b", "c"] ["a", "b", "c"]
```
or colocating per column:
```
[allocated region col1/col2 ]
col1: [1, 2, 3, 4, 5, 6] ["a", "b", "c", "d", "e"]
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] New row format that does not guarantee ordering of columns [arrow-rs]
Posted by "rluvaton (via GitHub)" <gi...@apache.org>.
rluvaton commented on issue #9083:
URL: https://github.com/apache/arrow-rs/issues/9083#issuecomment-3756265538
@Dandandan @alamb I would like your opinion on your thoughts and whether I should proceed with making the PRs
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] New row format that does not guarantee ordering of columns [arrow-rs]
Posted by "rluvaton (via GitHub)" <gi...@apache.org>.
rluvaton commented on issue #9083:
URL: https://github.com/apache/arrow-rs/issues/9083#issuecomment-3805279426
There is another implementation that I call splitter that have specialized implementation per type and work on all partitions at the same time which is faster than take into builders when there are a lot of partitions, but when there are a lot of columns than the optimised row format is faster.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] Row format that does not guarantee ordering of columns [arrow-rs]
Posted by "rluvaton (via GitHub)" <gi...@apache.org>.
rluvaton commented on issue #9083:
URL: https://github.com/apache/arrow-rs/issues/9083#issuecomment-3703789605
## 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
<details><summary>Benchmark code:</summary>
<p>
```rust
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
}
```
</p>
</details>
Results on main:
```bash
$ 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)
<details><summary>Step by step finding the problem (<code>Branch_Mispredicts</code>):</summary>
<details><summary>Running Top-Down analysis - Level 1</summary>
<p>
```bash
$ ~/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.
```
</p>
</details>
It looks like the problem is `Bad_Speculation`.
<details><summary>Running Top-Down analysis - Level 2</summary>
<p>
```bash
$ ~/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.
```
</p>
</details>
it is `Branch_Mispredicts`
<details><summary>Running Top-Down analysis - Level 3</summary>
<p>
```bash
$ ~/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.
```
</p>
</details>
<details><summary>Recording using perf the misprediction and all branches</summary>
<p>
Running perf record to see where most mispredictions while showing (mispredictions, `all_branches`)
```bash
$ 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:
```bash
$ perf report -g --group --percent-limit 0.01 --no-children
```
</p>
</details>
the most expensive in term of misprediction is `arrow_row::variable::encode_one`:
```bash
+ 67.00% 43.93% row_format-7489 row_format-7489cf224545c7d6 [.] arrow_row::variable::encode_one
```
<details><summary>annotated info</summary>
<p>
```asm
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) ▒
```
</p>
</details>
</details>
we see that the misprediction is on the iterator of the blocks in `variable::encode_blocks` function
```rust
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:
<details><summary>updated code:</summary>
<p>
```rust
/// 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
}
```
</p>
</details>
We will have 33% time improvement.
```bash
$ 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).
<details><summary>Running Top-Down analysis again on the updated code:</summary>
<p>
and if we run top level again for level 1:
```bash
$ ~/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:
```bash
$ ~/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:
```bash
$ ~/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:
```bash
$ 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:
```bash
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:
```bash
$ 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):
```bash
$ 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:
```bash
$ 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:
```bash
$ 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:
```bash
$ 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.
</p>
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] New row format that does not guarantee ordering of columns [arrow-rs]
Posted by "rluvaton (via GitHub)" <gi...@apache.org>.
rluvaton commented on issue #9083:
URL: https://github.com/apache/arrow-rs/issues/9083#issuecomment-3756423048
>
> > grouping - grouping by a lot of columns does not need ordering requirements
>
> How about implementing a specialization for Structs, the way we have for other types: [apache/datafusion@`main`/datafusion/physical-plan/src/aggregates/group_values/multi_group_by](https://github.com/apache/datafusion/tree/main/datafusion/physical-plan/src/aggregates/group_values/multi_group_by)
>
> That would likely be a lot faster than having to copy all the data once which a new row format would do
@alamb in the case when we already need to convert to rows (in the fallback implementation) the ordering doesn't matter and we can use this new row format which will make it faster.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] New row format that does not guarantee ordering of columns [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #9083:
URL: https://github.com/apache/arrow-rs/issues/9083#issuecomment-3756356776
My thoughts from the
1. https://github.com/apache/arrow-rs/issues/9083#issuecomment-3710183483
2. https://github.com/apache/arrow-rs/issues/9083#issuecomment-3710188287
Basically, my personal opinion is that a parallel RowFormat for equality comparisons is likely going to be a lot of code to maintain and I think that for whatever usecase you have in mind, you would likely better off using a different approach.
> row format is also useful when you need to copy a lot of columns around, for example when shuffling
I don't understand why row format would be used here -- Arrow already has a format that is optimzied for copying values around (the IPC format)
> grouping - grouping by a lot of columns does not need ordering requirements
How about implementing a specialization for Structs, the way we have for other types: https://github.com/apache/datafusion/tree/main/datafusion/physical-plan/src/aggregates/group_values/multi_group_by
That would likely be a lot faster than having to copy all the data once which a new row format would do
- aggregation - using count(distinct <struct>) or array_agg with distinct, both of which do not need ordering requirement
shuffling
Similarly, I think if you implemented a specialized accumulator for structs you would be better off than using a RowFormat, right?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] New row format that does not guarantee ordering of columns [arrow-rs]
Posted by "rluvaton (via GitHub)" <gi...@apache.org>.
rluvaton commented on issue #9083:
URL: https://github.com/apache/arrow-rs/issues/9083#issuecomment-3800851661
@Dandandan @alamb created an run a benchmark, link for the code in the end.
----
I created a benchmark with different implementations that all achieve the same goal, shuffle to partitions.
the implementations are:
1. take into builders - I implemented `take` that accept a sink to save the take data into to avoid reallocation or `concat`
2. take and concat - using the existing take and then doing concat on each column
3. interleave
4. existing row format
5. optimized row format
For each implementation that is no row based I implemented 2 benchmarks one when we go for all batches of column1 than all batches of column2 and so on (ones that named _column wise_) and another implementation that goes per batch, run the `take`/`interleave` on each column in that batch and than go to the next batch.
each benchmark get an input laid out so no pre processing on the input is needed before running (so `interleave` for example will already get the `Vec<(batch_index, row_index)>`).
The benchmark is to shuffle 128 batches of size 8192 rows into 1500 partitions. so shuffling ~1M rows. this also mean that each partition will only have ~700 rows in it.
I excluded the logic for splitting into batches from the benchmark since all of it are running in
I also preallocate for the take into builders and both row format enough data so no need to copy.
these are the results (sorted from fastest to slowest) running on my local MacBook M3 run:
Benchmark | Time (mean) | Time Range
-- | -- | --
shuffle/optimized_row_format_approach going partition wise | 2.6734 s | [2.6685 s - 2.6790 s]
shuffle/optimized_row_format_approach | 2.6930 s | [2.6899 s - 2.6958 s]
shuffle/row_format_approach going partition wise | 3.0178 s | [3.0075 s - 3.0283 s]
shuffle/row_format_approach | 3.0346 s | [3.0230 s - 3.0486 s]
shuffle/interleave_column_wise_approach | 3.4028 s | [3.3219 s - 3.4863 s]
shuffle/interleave_approach | 3.5126 s | [3.4128 s - 3.6161 s]
shuffle/take_to_builders_column_wise_approach | 4.2012 s | [4.1025 s - 4.3140 s]
shuffle/take_to_builders_approach | 4.2263 s | [4.0417 s - 4.4349 s]
shuffle/take_approach | 7.0364 s | [6.8709 s - 7.2323 s]
shuffle/take_column_wise_approach | 8.0610 s | [8.0290 s - 8.0964 s]
<details>
<summary>Raw results</summary>
```
Running benches/shuffle.rs (target/release/deps/shuffle-b6a3c1bf993fb91d)
Gnuplot not found, using plotters backend
Benchmarking shuffle/take_to_builders_approach: Warming up for 3.0000 s
Warning: Unable to complete 10 samples in 5.0s. You may wish to increase target time to 40.8s.
shuffle/take_to_builders_approach
time: [4.0417 s 4.2263 s 4.4349 s]
Benchmarking shuffle/take_to_builders_column_wise_approach: Warming up for 3.0000 s
Warning: Unable to complete 10 samples in 5.0s. You may wish to increase target time to 44.6s.
shuffle/take_to_builders_column_wise_approach
time: [4.1025 s 4.2012 s 4.3140 s]
Found 3 outliers among 10 measurements (30.00%)
1 (10.00%) low mild
1 (10.00%) high mild
1 (10.00%) high severe
Benchmarking shuffle/take_approach: Warming up for 3.0000 s
Warning: Unable to complete 10 samples in 5.0s. You may wish to increase target time to 107.1s.
shuffle/take_approach time: [6.8709 s 7.0364 s 7.2323 s]
Found 2 outliers among 10 measurements (20.00%)
2 (20.00%) high mild
Benchmarking shuffle/take_column_wise_approach: Warming up for 3.0000 s
Warning: Unable to complete 10 samples in 5.0s. You may wish to increase target time to 80.8s.
shuffle/take_column_wise_approach
time: [8.0290 s 8.0610 s 8.0964 s]
Benchmarking shuffle/interleave_approach: Warming up for 3.0000 s
Warning: Unable to complete 10 samples in 5.0s. You may wish to increase target time to 40.0s.
shuffle/interleave_approach
time: [3.4128 s 3.5126 s 3.6161 s]
Benchmarking shuffle/interleave_column_wise_approach: Warming up for 3.0000 s
Warning: Unable to complete 10 samples in 5.0s. You may wish to increase target time to 34.8s.
shuffle/interleave_column_wise_approach
time: [3.3219 s 3.4028 s 3.4863 s]
Benchmarking shuffle/row_format_approach: Warming up for 3.0000 s
Warning: Unable to complete 10 samples in 5.0s. You may wish to increase target time to 32.3s.
shuffle/row_format_approach
time: [3.0230 s 3.0346 s 3.0486 s]
Found 1 outliers among 10 measurements (10.00%)
1 (10.00%) high mild
Benchmarking shuffle/row_format_approach going partition wise: Warming up for 3.0000 s
Warning: Unable to complete 10 samples in 5.0s. You may wish to increase target time to 30.3s.
shuffle/row_format_approach going partition wise
time: [3.0075 s 3.0178 s 3.0283 s]
Benchmarking shuffle/optimized_row_format_approach: Warming up for 3.0000 s
Warning: Unable to complete 10 samples in 5.0s. You may wish to increase target time to 27.0s.
shuffle/optimized_row_format_approach
time: [2.6899 s 2.6930 s 2.6958 s]
Benchmarking shuffle/optimized_row_format_approach going partition wise: Warming up for 3.0000 s
Warning: Unable to complete 10 samples in 5.0s. You may wish to increase target time to 26.7s.
shuffle/optimized_row_format_approach going partition wise
time: [2.6685 s 2.6734 s 2.6790 s]
```
</details>
[**Benchmark implementation:**](https://github.com/rluvaton/bench_arrow_shuffle_implementation)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] Row format that does not guarantee ordering of columns [arrow-rs]
Posted by "rluvaton (via GitHub)" <gi...@apache.org>.
rluvaton commented on issue #9083:
URL: https://github.com/apache/arrow-rs/issues/9083#issuecomment-3703789536
## 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`)
<details><summary>Benchmark code:</summary>
<p>
```rust
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
}
```
</p>
</details>
Results on main:
```bash
$ 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.
<details><summary>Step by step finding the problem:</summary>
<details><summary>Running Top-Down analysis - Level 1</summary>
<p>
```bash
$ ~/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.
```
</p>
</details>
It looks like the problem is `Backend_Bound`.
<details><summary>Running Top-Down analysis - Level 2</summary>
<p>
```bash
$ ~/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.
```
</p>
</details>
<details><summary>Running Top-Down analysis - Level 3</summary>
<p>
```bash
$ ~/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.
```
</p>
</details>
<details><summary>Recording only store related events</summary>
<p>
```bash
$ 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:
```bash
perf report -g --percent-limit 0.01 --no-children
```
</p>
</details>
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:
<details><summary>annotated info</summary>
<p>
```asm
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
```
</p>
</details>
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`
<details><summary>recording:</summary>
<p>
```bash
$ 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:
```bash
perf report -g --percent-limit 0.01 --no-children
```
</p>
</details>
showed for the same hot function `fixed::encode_not_null`:
<details><summary>annotated info</summary>
<p>
```asm
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
```
</p>
</details>
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.
</details>
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%:
```bash
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:
```bash
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.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] New row format that does not guarantee ordering of columns [arrow-rs]
Posted by "rluvaton (via GitHub)" <gi...@apache.org>.
rluvaton commented on issue #9083:
URL: https://github.com/apache/arrow-rs/issues/9083#issuecomment-3818705904
Pinging again in cased you missed it:
@Dandandan @alamb
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org