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