alamb commented on code in PR #23766: URL: https://github.com/apache/datafusion/pull/23766#discussion_r3627046948
########## datafusion/common/src/utils/hex.rs: ########## @@ -0,0 +1,329 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +//! Hex encoding of bytes and integers. +//! +//! [`encode_bytes`] and [`encode_bytes_into`] encode a byte slice into an +//! owned `String` or an appended `Vec<u8>`, respectively; [`encode_bytes_to_slice`] +//! writes into a caller-provided, pre-sized buffer. [`encode_u64`] encodes an +//! integer, trimming leading zeros. All four take a [`HexCase`] to choose +//! between lowercase and uppercase digits. + +/// Case of the emitted hex digits. +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub enum HexCase { + /// Digits `0123456789abcdef`. + Lower, + /// Digits `0123456789ABCDEF`. + Upper, +} + +const LOWER_DIGITS: &[u8; 16] = b"0123456789abcdef"; +const UPPER_DIGITS: &[u8; 16] = b"0123456789ABCDEF"; + +/// Maps a full byte to its two hex digits, so encoding advances a whole byte +/// per iteration instead of a nibble. +const LOOKUP_LOWER: [[u8; 2]; 256] = build_lookup(LOWER_DIGITS); +const LOOKUP_UPPER: [[u8; 2]; 256] = build_lookup(UPPER_DIGITS); + +const fn build_lookup(digits: &[u8; 16]) -> [[u8; 2]; 256] { + let mut table = [[0u8; 2]; 256]; + let mut i = 0; + while i < 256 { + table[i][0] = digits[i >> 4]; + table[i][1] = digits[i & 0xF]; + i += 1; + } + table +} + +impl HexCase { + #[inline] + const fn lookup(self) -> &'static [[u8; 2]; 256] { + match self { + HexCase::Lower => &LOOKUP_LOWER, + HexCase::Upper => &LOOKUP_UPPER, + } + } + + #[inline] + const fn digits(self) -> &'static [u8; 16] { + match self { + HexCase::Lower => LOWER_DIGITS, + HexCase::Upper => UPPER_DIGITS, + } + } +} + +/// Appends the hex encoding of `bytes` to `out`. +/// +/// Allocates only through `out`'s own growth. Callers that must bound or guard +/// that growth should reserve capacity in `out` before calling. +#[inline(always)] +pub fn encode_bytes_into(bytes: &[u8], case: HexCase, out: &mut Vec<u8>) { + let lookup = case.lookup(); + for &byte in bytes { + out.extend_from_slice(&lookup[byte as usize]); + } +} + +/// Writes the hex encoding of `bytes` into `out`. +/// +/// `out` must be exactly `2 * bytes.len()` bytes long. This is for callers +/// that already own a pre-sized buffer (for example a slice of a larger, +/// pre-allocated output array) and want to write directly into it rather +/// than appending to a `Vec`. +/// +/// The length requirement is only checked in debug builds, via Review Comment: Why not just check it and return an internal error? It seems better than a silent failure in release builds ########## datafusion/functions/src/crypto/md5.rs: ########## @@ -122,13 +107,15 @@ fn md5(args: &[ColumnarValue]) -> Result<ColumnarValue> { Ok(match value { ColumnarValue::Array(array) => { let binary_array = as_binary_array(&array)?; - let string_array: StringViewArray = - binary_array.iter().map(|opt| opt.map(hex_encode)).collect(); + let string_array: StringViewArray = binary_array + .iter() + .map(|opt| opt.map(|b| encode_bytes(b, HexCase::Lower))) Review Comment: This is unfortunate (as it makes a bunch of allocated strings and then copies them again into theStringViewArray -- using a temporary buffer ald a stringViewBuilder could avoid the intermediate allocation This can be done as a follow on PR (or never) -- the old version dod this too ########## datafusion/functions/src/string/to_hex.rs: ########## @@ -79,101 +76,50 @@ where #[inline] fn to_hex_scalar<T: ToHex>(value: T) -> String { let mut hex_buffer = [0u8; 16]; - let hex_len = value.write_hex_to_buffer(&mut hex_buffer); - // SAFETY: hex_buffer is ASCII hex digits - unsafe { std::str::from_utf8_unchecked(&hex_buffer[16 - hex_len..]).to_string() } + let hex = value.write_hex(&mut hex_buffer); + // SAFETY: hex holds only ASCII hex digits. + unsafe { std::str::from_utf8_unchecked(hex).to_string() } } /// Trait for converting integer types to hexadecimal in a buffer Review Comment: I wonder if we should move this code into the common library crate as well ########## datafusion/common/src/utils/hex.rs: ########## @@ -0,0 +1,329 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +//! Hex encoding of bytes and integers. +//! +//! [`encode_bytes`] and [`encode_bytes_into`] encode a byte slice into an +//! owned `String` or an appended `Vec<u8>`, respectively; [`encode_bytes_to_slice`] +//! writes into a caller-provided, pre-sized buffer. [`encode_u64`] encodes an +//! integer, trimming leading zeros. All four take a [`HexCase`] to choose +//! between lowercase and uppercase digits. + +/// Case of the emitted hex digits. +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub enum HexCase { + /// Digits `0123456789abcdef`. + Lower, + /// Digits `0123456789ABCDEF`. + Upper, +} + +const LOWER_DIGITS: &[u8; 16] = b"0123456789abcdef"; +const UPPER_DIGITS: &[u8; 16] = b"0123456789ABCDEF"; + +/// Maps a full byte to its two hex digits, so encoding advances a whole byte +/// per iteration instead of a nibble. +const LOOKUP_LOWER: [[u8; 2]; 256] = build_lookup(LOWER_DIGITS); +const LOOKUP_UPPER: [[u8; 2]; 256] = build_lookup(UPPER_DIGITS); + +const fn build_lookup(digits: &[u8; 16]) -> [[u8; 2]; 256] { + let mut table = [[0u8; 2]; 256]; + let mut i = 0; + while i < 256 { + table[i][0] = digits[i >> 4]; + table[i][1] = digits[i & 0xF]; + i += 1; + } + table +} + +impl HexCase { + #[inline] + const fn lookup(self) -> &'static [[u8; 2]; 256] { + match self { + HexCase::Lower => &LOOKUP_LOWER, + HexCase::Upper => &LOOKUP_UPPER, + } + } + + #[inline] + const fn digits(self) -> &'static [u8; 16] { + match self { + HexCase::Lower => LOWER_DIGITS, + HexCase::Upper => UPPER_DIGITS, + } + } +} + +/// Appends the hex encoding of `bytes` to `out`. +/// +/// Allocates only through `out`'s own growth. Callers that must bound or guard +/// that growth should reserve capacity in `out` before calling. +#[inline(always)] +pub fn encode_bytes_into(bytes: &[u8], case: HexCase, out: &mut Vec<u8>) { + let lookup = case.lookup(); + for &byte in bytes { + out.extend_from_slice(&lookup[byte as usize]); + } +} + +/// Writes the hex encoding of `bytes` into `out`. +/// +/// `out` must be exactly `2 * bytes.len()` bytes long. This is for callers +/// that already own a pre-sized buffer (for example a slice of a larger, +/// pre-allocated output array) and want to write directly into it rather +/// than appending to a `Vec`. +/// +/// The length requirement is only checked in debug builds, via +/// `debug_assert_eq!`. In release builds a mismatched `out` length is not +/// an error: only `min(bytes.len(), out.len() / 2)` bytes are encoded, so +/// an `out` that is too short silently drops the remaining input, and an +/// `out` that is too long is left with unwritten, stale bytes at the end. +/// Callers are responsible for sizing `out` correctly. +/// +/// # Example +/// +/// ``` +/// use datafusion_common::utils::hex::{HexCase, encode_bytes_to_slice}; +/// +/// let mut out = [0u8; 8]; +/// encode_bytes_to_slice(&[0xde, 0xad, 0xbe, 0xef], HexCase::Lower, &mut out); +/// assert_eq!(&out, b"deadbeef"); +/// ``` +#[inline(always)] +pub fn encode_bytes_to_slice(bytes: &[u8], case: HexCase, out: &mut [u8]) { + debug_assert_eq!(out.len(), bytes.len() * 2); + let lookup = case.lookup(); + for (&b, chunk) in bytes.iter().zip(out.chunks_exact_mut(2)) { + chunk.copy_from_slice(&lookup[b as usize]); Review Comment: this is probably going to be quite fast ########## datafusion/common/src/utils/hex.rs: ########## @@ -0,0 +1,329 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +//! Hex encoding of bytes and integers. +//! +//! [`encode_bytes`] and [`encode_bytes_into`] encode a byte slice into an +//! owned `String` or an appended `Vec<u8>`, respectively; [`encode_bytes_to_slice`] +//! writes into a caller-provided, pre-sized buffer. [`encode_u64`] encodes an +//! integer, trimming leading zeros. All four take a [`HexCase`] to choose +//! between lowercase and uppercase digits. + +/// Case of the emitted hex digits. +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub enum HexCase { + /// Digits `0123456789abcdef`. + Lower, + /// Digits `0123456789ABCDEF`. + Upper, +} + +const LOWER_DIGITS: &[u8; 16] = b"0123456789abcdef"; +const UPPER_DIGITS: &[u8; 16] = b"0123456789ABCDEF"; + +/// Maps a full byte to its two hex digits, so encoding advances a whole byte +/// per iteration instead of a nibble. +const LOOKUP_LOWER: [[u8; 2]; 256] = build_lookup(LOWER_DIGITS); +const LOOKUP_UPPER: [[u8; 2]; 256] = build_lookup(UPPER_DIGITS); + +const fn build_lookup(digits: &[u8; 16]) -> [[u8; 2]; 256] { + let mut table = [[0u8; 2]; 256]; + let mut i = 0; + while i < 256 { + table[i][0] = digits[i >> 4]; + table[i][1] = digits[i & 0xF]; + i += 1; + } + table +} + +impl HexCase { + #[inline] + const fn lookup(self) -> &'static [[u8; 2]; 256] { + match self { + HexCase::Lower => &LOOKUP_LOWER, + HexCase::Upper => &LOOKUP_UPPER, + } + } + + #[inline] + const fn digits(self) -> &'static [u8; 16] { + match self { + HexCase::Lower => LOWER_DIGITS, + HexCase::Upper => UPPER_DIGITS, + } + } +} + +/// Appends the hex encoding of `bytes` to `out`. +/// +/// Allocates only through `out`'s own growth. Callers that must bound or guard +/// that growth should reserve capacity in `out` before calling. +#[inline(always)] +pub fn encode_bytes_into(bytes: &[u8], case: HexCase, out: &mut Vec<u8>) { + let lookup = case.lookup(); + for &byte in bytes { + out.extend_from_slice(&lookup[byte as usize]); + } +} + +/// Writes the hex encoding of `bytes` into `out`. +/// +/// `out` must be exactly `2 * bytes.len()` bytes long. This is for callers +/// that already own a pre-sized buffer (for example a slice of a larger, +/// pre-allocated output array) and want to write directly into it rather +/// than appending to a `Vec`. +/// +/// The length requirement is only checked in debug builds, via +/// `debug_assert_eq!`. In release builds a mismatched `out` length is not +/// an error: only `min(bytes.len(), out.len() / 2)` bytes are encoded, so +/// an `out` that is too short silently drops the remaining input, and an +/// `out` that is too long is left with unwritten, stale bytes at the end. +/// Callers are responsible for sizing `out` correctly. +/// +/// # Example +/// +/// ``` +/// use datafusion_common::utils::hex::{HexCase, encode_bytes_to_slice}; +/// +/// let mut out = [0u8; 8]; +/// encode_bytes_to_slice(&[0xde, 0xad, 0xbe, 0xef], HexCase::Lower, &mut out); +/// assert_eq!(&out, b"deadbeef"); +/// ``` +#[inline(always)] +pub fn encode_bytes_to_slice(bytes: &[u8], case: HexCase, out: &mut [u8]) { + debug_assert_eq!(out.len(), bytes.len() * 2); + let lookup = case.lookup(); + for (&b, chunk) in bytes.iter().zip(out.chunks_exact_mut(2)) { + chunk.copy_from_slice(&lookup[b as usize]); + } +} + +/// Returns the hex encoding of `bytes` as an owned `String`. +/// +/// # Example +/// +/// ``` +/// use datafusion_common::utils::hex::{HexCase, encode_bytes}; +/// +/// assert_eq!(encode_bytes(&[0xde, 0xad, 0xbe, 0xef], HexCase::Lower), "deadbeef"); +/// assert_eq!(encode_bytes(&[0xde, 0xad, 0xbe, 0xef], HexCase::Upper), "DEADBEEF"); +/// ``` +#[inline] +pub fn encode_bytes(bytes: &[u8], case: HexCase) -> String { Review Comment: I think this function will perform poorly as it allocates -- it might be a good idea as a follow on PR to remove. this function and rewrite any uses of it so they don't allocate a bunch of strings ########## datafusion/functions/src/string/to_hex.rs: ########## @@ -24,16 +24,14 @@ use arrow::datatypes::{ Int64Type, UInt8Type, UInt16Type, UInt32Type, UInt64Type, }; use datafusion_common::cast::as_primitive_array; +use datafusion_common::utils::hex::{HexCase, encode_u64}; use datafusion_common::{Result, ScalarValue, exec_err, internal_err}; use datafusion_expr::{ Coercion, ColumnarValue, Documentation, ScalarFunctionArgs, ScalarUDFImpl, Signature, TypeSignatureClass, Volatility, }; use datafusion_macros::user_doc; -/// Hex lookup table for fast conversion -const HEX_CHARS: &[u8; 16] = b"0123456789abcdef"; - /// Converts the number to its equivalent hexadecimal representation. /// to_hex(2147483647) = '7fffffff' fn to_hex_array<T: ArrowPrimitiveType>(array: &ArrayRef) -> Result<ArrayRef> Review Comment: here is an good example of creating StringArrays directly with hex ########## datafusion/common/src/utils/hex.rs: ########## @@ -0,0 +1,329 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +//! Hex encoding of bytes and integers. +//! +//! [`encode_bytes`] and [`encode_bytes_into`] encode a byte slice into an +//! owned `String` or an appended `Vec<u8>`, respectively; [`encode_bytes_to_slice`] +//! writes into a caller-provided, pre-sized buffer. [`encode_u64`] encodes an +//! integer, trimming leading zeros. All four take a [`HexCase`] to choose +//! between lowercase and uppercase digits. + +/// Case of the emitted hex digits. +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub enum HexCase { + /// Digits `0123456789abcdef`. + Lower, + /// Digits `0123456789ABCDEF`. + Upper, +} + +const LOWER_DIGITS: &[u8; 16] = b"0123456789abcdef"; +const UPPER_DIGITS: &[u8; 16] = b"0123456789ABCDEF"; + +/// Maps a full byte to its two hex digits, so encoding advances a whole byte +/// per iteration instead of a nibble. +const LOOKUP_LOWER: [[u8; 2]; 256] = build_lookup(LOWER_DIGITS); +const LOOKUP_UPPER: [[u8; 2]; 256] = build_lookup(UPPER_DIGITS); + +const fn build_lookup(digits: &[u8; 16]) -> [[u8; 2]; 256] { + let mut table = [[0u8; 2]; 256]; + let mut i = 0; + while i < 256 { + table[i][0] = digits[i >> 4]; + table[i][1] = digits[i & 0xF]; + i += 1; + } + table +} + +impl HexCase { + #[inline] + const fn lookup(self) -> &'static [[u8; 2]; 256] { + match self { + HexCase::Lower => &LOOKUP_LOWER, + HexCase::Upper => &LOOKUP_UPPER, + } + } + + #[inline] + const fn digits(self) -> &'static [u8; 16] { + match self { + HexCase::Lower => LOWER_DIGITS, + HexCase::Upper => UPPER_DIGITS, + } + } +} + +/// Appends the hex encoding of `bytes` to `out`. +/// +/// Allocates only through `out`'s own growth. Callers that must bound or guard +/// that growth should reserve capacity in `out` before calling. +#[inline(always)] +pub fn encode_bytes_into(bytes: &[u8], case: HexCase, out: &mut Vec<u8>) { + let lookup = case.lookup(); + for &byte in bytes { + out.extend_from_slice(&lookup[byte as usize]); + } +} + +/// Writes the hex encoding of `bytes` into `out`. +/// +/// `out` must be exactly `2 * bytes.len()` bytes long. This is for callers +/// that already own a pre-sized buffer (for example a slice of a larger, +/// pre-allocated output array) and want to write directly into it rather +/// than appending to a `Vec`. +/// +/// The length requirement is only checked in debug builds, via +/// `debug_assert_eq!`. In release builds a mismatched `out` length is not +/// an error: only `min(bytes.len(), out.len() / 2)` bytes are encoded, so +/// an `out` that is too short silently drops the remaining input, and an +/// `out` that is too long is left with unwritten, stale bytes at the end. +/// Callers are responsible for sizing `out` correctly. +/// +/// # Example +/// +/// ``` +/// use datafusion_common::utils::hex::{HexCase, encode_bytes_to_slice}; +/// +/// let mut out = [0u8; 8]; +/// encode_bytes_to_slice(&[0xde, 0xad, 0xbe, 0xef], HexCase::Lower, &mut out); +/// assert_eq!(&out, b"deadbeef"); +/// ``` +#[inline(always)] +pub fn encode_bytes_to_slice(bytes: &[u8], case: HexCase, out: &mut [u8]) { + debug_assert_eq!(out.len(), bytes.len() * 2); + let lookup = case.lookup(); + for (&b, chunk) in bytes.iter().zip(out.chunks_exact_mut(2)) { + chunk.copy_from_slice(&lookup[b as usize]); + } +} + +/// Returns the hex encoding of `bytes` as an owned `String`. +/// +/// # Example +/// +/// ``` +/// use datafusion_common::utils::hex::{HexCase, encode_bytes}; +/// +/// assert_eq!(encode_bytes(&[0xde, 0xad, 0xbe, 0xef], HexCase::Lower), "deadbeef"); +/// assert_eq!(encode_bytes(&[0xde, 0xad, 0xbe, 0xef], HexCase::Upper), "DEADBEEF"); +/// ``` +#[inline] +pub fn encode_bytes(bytes: &[u8], case: HexCase) -> String { + let mut out = Vec::with_capacity(bytes.len() * 2); + encode_bytes_into(bytes, case, &mut out); + // SAFETY: `out` holds only ASCII hex digits, which are valid UTF-8. + unsafe { String::from_utf8_unchecked(out) } +} + +/// Writes `v` as hex into `buf` and returns the written subslice. +/// +/// Digits are written right-aligned with leading zeros trimmed, so the result +/// borrows the tail of `buf`. Zero encodes as `"0"`. +/// +/// Signed values should be cast with `as u64`, which yields the two's +/// complement representation that both `to_hex` and Spark's `hex` produce for +/// negative input. +/// +/// # Example +/// +/// The caller owns the buffer and can reuse it across calls; each call +/// returns a fresh subslice of it, borrowed for as long as `buf` is: +/// +/// ``` +/// use datafusion_common::utils::hex::{HexCase, encode_u64}; +/// +/// let mut buf = [0u8; 16]; +/// assert_eq!(encode_u64(0xAB, HexCase::Lower, &mut buf), b"ab"); +/// assert_eq!(encode_u64(0, HexCase::Lower, &mut buf), b"0"); +/// ``` +#[inline(always)] +pub fn encode_u64(v: u64, case: HexCase, buf: &mut [u8; 16]) -> &[u8] { + let start = write_digits(v, case, buf); + &buf[start..] +} + +/// Writes the digits of `v` right-aligned in `buf`, returning the index of the +/// first digit. +/// +/// Split out from [`encode_u64`] so the mutable borrow of `buf` ends before the +/// returned slice reborrows it. The `v == 0` case returns early; if that early +/// return instead reborrowed `buf` as `&buf[..]` inline in [`encode_u64`], the +/// borrow checker would extend that reborrow over the rest of the function +/// body, conflicting with the mutable writes on the non-zero path below. Review Comment: I think it would be enough here to describe the borrow checker and not try to summarize the implementation detail too ```suggestion /// returned slice reborrows it. ``` -- 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] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
