rluvaton commented on code in PR #11524:
URL: https://github.com/apache/arrow-rs/pull/11524#discussion_r4248148207
##########
parquet/src/arrow/arrow_writer/byte_array.rs:
##########
@@ -301,46 +301,234 @@ impl FallbackEncoder {
}
}
-/// [`Storage`] for the [`Interner`] used by [`DictEncoder`]
+/// Maximum size of a value that can be inlined in the hash table
+const SHORT_VALUE_LEN: usize = size_of::<u64>() - 1;
+
+/// Entry in the hash table
+#[derive(Debug, PartialEq, Eq, Hash, Clone, Copy)]
+struct Entry {
+ /// hash of the value (stored to avoid recomputing it in hash table check)
+ hash: u64,
+ /// if len =< [`SHORT_VALUE_LEN`]: the data inlined
+ /// if len > [`SHORT_VALUE_LEN`], the offset of where the data starts
+ offset_or_inline: OffsetOrInlineView,
+ /// value stored by the entry
+ index_in_dict: u64,
+}
+
+/// Either offset to the dictionary page bytes or inline bytes when the bytes
are short enough
+/// to avoid doing the indirection
+///
+/// For inlined view:
+/// +------------+---------------+------------------------------+
+/// | 1 bit set | len {7 bits} | value {56 bits} |
+/// +------------+---------------+------------------------------+
+///
+/// For non-inlined view:
+/// +--------------+--------------------------------------------+
+/// | 1 bit unset | offset in dict {63 bits} |
+/// +--------------+--------------------------------------------+
+///
+/// the inline view contain it's length to avoid having another field for
length in the entry
+/// since if the hashes are the same, most probably the length will be the
same, so we can do the indirection check
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
+struct OffsetOrInlineView(u64);
+
+impl OffsetOrInlineView {
+ const INLINE_FLAG: u64 = 1 << 63;
+ const LEN_SHIFT: u32 = 56;
+
+ #[inline]
+ fn is_non_inlined(&self) -> bool {
+ (self.0 & Self::INLINE_FLAG) == 0
+ }
+
+ #[inline]
+ fn is_inlined(&self) -> bool {
+ !self.is_non_inlined()
+ }
+
+ #[inline]
+ fn new_inlined(value: &[u8]) -> Self {
+ debug_assert!(value.len() <= 7);
+
+ // Value bytes occupy the low 56 bits, byte 0 in the least significant
position
+ let mut buf = [0u8; 8];
+ buf[..value.len()].copy_from_slice(value);
+ let packed = u64::from_le_bytes(buf);
+
+ Self(Self::INLINE_FLAG | ((value.len() as u64) << Self::LEN_SHIFT) |
packed)
+ }
+
+ #[inline]
+ fn new_non_inlined(offset: u64) -> Self {
+ assert_eq!(
+ offset & Self::INLINE_FLAG,
+ 0,
+ "offset must not have the inlined flag set, we don't support this
large of a byte array"
+ );
Review Comment:
We are now not allowing byte arrays values that will reach to `2^64` but I
think this is fine
--
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]
