jhorstmann commented on code in PR #9250:
URL: https://github.com/apache/arrow-rs/pull/9250#discussion_r2720736440
##########
arrow-array/src/array/byte_view_array.rs:
##########
@@ -795,83 +795,17 @@ impl<T: ByteViewType + ?Sized> GenericByteViewArray<T> {
/// ```
/// # Inlining and Endianness
///
- /// - We start by calling `.to_le_bytes()` on the `raw` `u128`, because
Rust’s native in‑memory
- /// representation is little‑endian on x86/ARM.
- /// - We extract the low 32 bits numerically (`raw as u32`)—this step is
endianness‑free.
- /// - We copy the 12 bytes of inline data (original order) into
`buf[0..12]`.
- /// - We serialize `length` as big‑endian into `buf[12..16]`.
- /// - Finally, `u128::from_be_bytes(buf)` treats `buf[0]` as the most
significant byte
- /// and `buf[15]` as the least significant, producing a `u128` whose
integer value
- /// directly encodes “inline data then length” in big‑endian form.
- ///
- /// This ensures that a simple `u128` comparison is equivalent to the
desired
- /// lexicographical comparison of the inline bytes followed by length.
+ /// This function uses target-endian independent bitwise operations to
construct a 128-bit key:
+ /// - `raw.to_be() << 32` effectively clears the length bits and shifts
the 12-byte inline data
+ /// into the high 96 bits in Big-Endian order. This ensures the first
byte of the string
+ /// is the most significant byte of the resulting `u128`.
+ /// - `raw.to_le() as u32` extracts the length as a native-endian integer,
which is then
+ /// placed in the low 32 bits.
+ /// - The combination ensures that a single `u128` comparison correctly
orders by inline data
+ /// first (lexicographically), then by length (numerically).
#[inline(always)]
pub fn inline_key_fast(raw: u128) -> u128 {
- // 1. Decompose `raw` into little‑endian bytes:
- // - raw_bytes[0..4] = length in LE
- // - raw_bytes[4..16] = inline string data
- let raw_bytes = raw.to_le_bytes();
-
- // 2. Numerically truncate to get the low 32‑bit length
(endianness‑free).
- let length = raw as u32;
-
- // 3. Build a 16‑byte buffer in big‑endian order:
- // - buf[0..12] = inline string bytes (in original order)
- // - buf[12..16] = length.to_be_bytes() (BE)
- let mut buf = [0u8; 16];
- buf[0..12].copy_from_slice(&raw_bytes[4..16]); // inline data
-
- // Why convert length to big-endian for comparison?
- //
- // Rust (on most platforms) stores integers in little-endian format,
- // meaning the least significant byte is at the lowest memory address.
- // For example, an u32 value like 0x22345677 is stored in memory as:
- //
- // [0x77, 0x56, 0x34, 0x22] // little-endian layout
- // ^ ^ ^ ^
- // LSB ↑↑↑ MSB
- //
- // This layout is efficient for arithmetic but *not* suitable for
- // lexicographic (dictionary-style) comparison of byte arrays.
- //
- // To compare values by byte order—e.g., for sorted keys or binary
trees—
- // we must convert them to **big-endian**, where:
- //
- // - The most significant byte (MSB) comes first (index 0)
- // - The least significant byte (LSB) comes last (index N-1)
- //
- // In big-endian, the same u32 = 0x22345677 would be represented as:
- //
- // [0x22, 0x34, 0x56, 0x77]
- //
- // This ordering aligns with natural string/byte sorting, so calling
- // `.to_be_bytes()` allows us to construct
- // keys where standard numeric comparison (e.g., `<`, `>`) behaves
- // like lexicographic byte comparison.
- buf[12..16].copy_from_slice(&length.to_be_bytes()); // length in BE
-
- // 4. Deserialize the buffer as a big‑endian u128:
- // buf[0] is MSB, buf[15] is LSB.
- // Details:
- // Note on endianness and layout:
- //
- // Although `buf[0]` is stored at the lowest memory address,
- // calling `u128::from_be_bytes(buf)` interprets it as the **most
significant byte (MSB)**,
- // and `buf[15]` as the **least significant byte (LSB)**.
- //
- // This is the core principle of **big-endian decoding**:
- // - Byte at index 0 maps to bits 127..120 (highest)
- // - Byte at index 1 maps to bits 119..112
- // - ...
- // - Byte at index 15 maps to bits 7..0 (lowest)
- //
- // So even though memory layout goes from low to high (left to right),
- // big-endian treats the **first byte** as highest in value.
- //
- // This guarantees that comparing two `u128` keys is equivalent to
lexicographically
- // comparing the original inline bytes, followed by length.
- u128::from_be_bytes(buf)
+ (raw.to_be() << 32) | (raw.to_le() as u32 as u128)
Review Comment:
Test coverage for this method looks good, and I agree this is much easier.
I just learned it is possible to run code under miri while targeting a
big-endian platform:
```
$ cargo +nightly miri test --target s390x-unknown-linux-gnu --
test_inline_key_fast_various_lengths_and_lexical
```
I extracted that test into a separate project, to avoid dealing with
dependencies, and I think the code needs a small adjustment.
```suggestion
(raw.swap_bytes() << 32) | (raw as u32 as u128)
```
Since the inline key is always created with `from_le_bytes` and comparing
integers is endian-independent, I think the swapping needs to happen
independent of endian-ness.
Test code in details:
<details>
```
pub fn make_inlined_view(data: &[u8]) -> u128 {
let len = data.len();
assert!(len <= 12);
let mut view_buffer = [0; 16];
view_buffer[0..4].copy_from_slice(&(len as u32).to_le_bytes());
view_buffer[4..4 + len].copy_from_slice(&data[..len]);
u128::from_le_bytes(view_buffer)
}
pub fn inline_key_fast(raw: u128) -> u128 {
(raw.swap_bytes() << 32) | (raw as u32 as u128)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_inline_key_fast_various_lengths_and_lexical() {
/// Helper to create a raw u128 value representing an inline
ByteView:
/// - `length`: number of meaningful bytes (must be ≤ 12)
/// - `data`: the actual inline data bytes
///
/// The first 4 bytes encode length in little-endian,
/// the following 12 bytes contain the inline string data (unpadded).
fn make_raw_inline(length: u32, data: &[u8]) -> u128 {
assert!(length as usize <= 12, "Inline length must be ≤ 12");
assert!(
data.len() == length as usize,
"Data length must match `length`"
);
let mut raw_bytes = [0u8; 16];
raw_bytes[0..4].copy_from_slice(&length.to_le_bytes()); //
length stored little-endian
raw_bytes[4..(4 + data.len())].copy_from_slice(data); // inline
data
u128::from_le_bytes(raw_bytes)
}
dbg!(inline_key_fast(make_raw_inline(3, b"foo")).to_be_bytes());
// Test inputs: various lengths and lexical orders,
// plus special cases for byte order and length tie-breaking
let test_inputs: Vec<&[u8]> = vec![
b"a",
b"aa",
b"aaa",
b"aab",
b"abcd",
b"abcde",
b"abcdef",
b"abcdefg",
b"abcdefgh",
b"abcdefghi",
b"abcdefghij",
b"abcdefghijk",
b"abcdefghijkl",
// Tests for byte-order reversal bug:
// Without the fix, "backend one" would compare as "eno dnekcab",
// causing incorrect sort order relative to "backend two".
b"backend one",
b"backend two",
// Tests length-tiebreaker logic:
// "bar" (3 bytes) and "bar\0" (4 bytes) have identical inline
data,
// so only the length differentiates their ordering.
b"bar",
b"bar\0",
// Additional lexical and length tie-breaking cases with same
prefix, in correct lex order:
b"than12Byt",
b"than12Bytes",
b"than12Bytes\0",
b"than12Bytesx",
b"than12Bytex",
b"than12Bytez",
// Additional lexical tests
b"xyy",
b"xyz",
b"xza",
];
for i in 0..test_inputs.len() - 1 {
let v1 = test_inputs[i];
let v2 = test_inputs[i + 1];
// Assert the array's natural lexical ordering is correct
assert!(v1 < v2, "Array compare failed: {v1:?} !< {v2:?}");
// Assert the keys produced by inline_key_fast reflect the same
ordering
let key1 = inline_key_fast(make_inlined_view(v1));
let key2 = inline_key_fast(make_inlined_view(v2));
assert!(
key1 < key2,
"Key compare failed: key({v1:?})=0x{key1:032x} !<
key({v2:?})=0x{key2:032x}",
);
}
}
}
```
</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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
