You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "andygrove (via GitHub)" <gi...@apache.org> on 2024/06/14 20:31:32 UTC
[PR] Implement more efficient version of xxhash64 [datafusion-comet]
andygrove opened a new pull request, #575:
URL: https://github.com/apache/datafusion-comet/pull/575
## Which issue does this PR close?
<!--
We generally require a GitHub issue to be filed for all bug fixes and enhancements and this helps us generate change logs for our releases. You can link an issue to this PR using the GitHub syntax. For example `Closes #123` indicates that this PR will close issue #123.
-->
Closes https://github.com/apache/datafusion-comet/issues/547
## Rationale for this change
<!--
Why are you proposing this change? If this is already explained clearly in the issue then this section is not needed.
Explaining clearly why changes are proposed helps reviewers understand your changes and offer better suggestions for fixes.
-->
## What changes are included in this PR?
<!--
There is no need to duplicate the description in the issue here but it is sometimes worth providing a summary of the individual changes in this PR.
-->
## How are these changes tested?
<!--
We typically require tests for all PRs in order to:
1. Prevent the code from being accidentally broken by subsequent changes
2. Serve as another way to document the expected behavior of the code
If tests are not included in your PR, please explain why (for example, are they covered by existing tests)?
-->
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Implement more efficient version of xxhash64 [datafusion-comet]
Posted by "andygrove (via GitHub)" <gi...@apache.org>.
andygrove commented on code in PR #575:
URL: https://github.com/apache/datafusion-comet/pull/575#discussion_r1650079025
##########
core/src/execution/datafusion/expressions/xxhash64.rs:
##########
@@ -0,0 +1,186 @@
+// 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.
+
+//! xxhash64 implementation
+
+const CHUNK_SIZE: usize = 32;
+
+const PRIME_1: u64 = 11_400_714_785_074_694_791;
Review Comment:
:man_shrugging: I copied this directly from xxhash64. I think either style works in this case
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Implement more efficient version of xxhash64 [datafusion-comet]
Posted by "parthchandra (via GitHub)" <gi...@apache.org>.
parthchandra commented on code in PR #575:
URL: https://github.com/apache/datafusion-comet/pull/575#discussion_r1649411618
##########
core/src/execution/datafusion/expressions/xxhash64.rs:
##########
@@ -0,0 +1,186 @@
+// 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.
+
+//! xxhash64 implementation
+
+const CHUNK_SIZE: usize = 32;
+
+const PRIME_1: u64 = 11_400_714_785_074_694_791;
+const PRIME_2: u64 = 14_029_467_366_897_019_727;
+const PRIME_3: u64 = 1_609_587_929_392_839_161;
+const PRIME_4: u64 = 9_650_029_242_287_828_579;
+const PRIME_5: u64 = 2_870_177_450_012_600_261;
+
+/// Custom implementation of xxhash64 based on code from https://github.com/shepmaster/twox-hash
+/// but optimized for our use case by removing any intermediate buffering, which is
+/// not required because we are operating on data that is already in memory.
+#[inline]
+pub(crate) fn spark_compatible_xxhash64<T: AsRef<[u8]>>(data: T, seed: u64) -> u64 {
+ let data: &[u8] = data.as_ref();
+ let length_bytes = data.len();
+
+ let mut v1 = seed.wrapping_add(PRIME_1).wrapping_add(PRIME_2);
+ let mut v2 = seed.wrapping_add(PRIME_2);
+ let mut v3 = seed;
+ let mut v4 = seed.wrapping_sub(PRIME_1);
+
+ // process chunks of 32 bytes
+ let mut offset_u64_4 = 0;
+ let ptr_u64 = data.as_ptr() as *const u64;
+ unsafe {
+ while offset_u64_4 * CHUNK_SIZE + CHUNK_SIZE <= length_bytes {
+ v1 = ingest_one_number(v1, ptr_u64.add(offset_u64_4 * 4).read_unaligned().to_le());
Review Comment:
Does this produce the right result? The [original implementation of XXHash64 ](https://github.com/Cyan4973/xxHash/blob/805c00b68fa754200ada0c207ffeaa7a4409377c/xxhash.h#L3517)processes 64 bits at a time.
##########
core/src/execution/datafusion/expressions/xxhash64.rs:
##########
@@ -0,0 +1,186 @@
+// 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.
+
+//! xxhash64 implementation
+
+const CHUNK_SIZE: usize = 32;
+
+const PRIME_1: u64 = 11_400_714_785_074_694_791;
+const PRIME_2: u64 = 14_029_467_366_897_019_727;
+const PRIME_3: u64 = 1_609_587_929_392_839_161;
+const PRIME_4: u64 = 9_650_029_242_287_828_579;
+const PRIME_5: u64 = 2_870_177_450_012_600_261;
+
+/// Custom implementation of xxhash64 based on code from https://github.com/shepmaster/twox-hash
+/// but optimized for our use case by removing any intermediate buffering, which is
+/// not required because we are operating on data that is already in memory.
+#[inline]
+pub(crate) fn spark_compatible_xxhash64<T: AsRef<[u8]>>(data: T, seed: u64) -> u64 {
+ let data: &[u8] = data.as_ref();
+ let length_bytes = data.len();
+
+ let mut v1 = seed.wrapping_add(PRIME_1).wrapping_add(PRIME_2);
+ let mut v2 = seed.wrapping_add(PRIME_2);
+ let mut v3 = seed;
+ let mut v4 = seed.wrapping_sub(PRIME_1);
+
+ // process chunks of 32 bytes
+ let mut offset_u64_4 = 0;
+ let ptr_u64 = data.as_ptr() as *const u64;
+ unsafe {
+ while offset_u64_4 * CHUNK_SIZE + CHUNK_SIZE <= length_bytes {
+ v1 = ingest_one_number(v1, ptr_u64.add(offset_u64_4 * 4).read_unaligned().to_le());
+ v2 = ingest_one_number(
+ v2,
+ ptr_u64.add(offset_u64_4 * 4 + 1).read_unaligned().to_le(),
+ );
+ v3 = ingest_one_number(
+ v3,
+ ptr_u64.add(offset_u64_4 * 4 + 2).read_unaligned().to_le(),
+ );
+ v4 = ingest_one_number(
+ v4,
+ ptr_u64.add(offset_u64_4 * 4 + 3).read_unaligned().to_le(),
+ );
+ offset_u64_4 += 1;
+ }
+ }
+
+ let mut hash = if length_bytes >= CHUNK_SIZE {
+ // We have processed at least one full chunk
+ let mut hash = v1.rotate_left(1);
+ hash = hash.wrapping_add(v2.rotate_left(7));
+ hash = hash.wrapping_add(v3.rotate_left(12));
+ hash = hash.wrapping_add(v4.rotate_left(18));
+
+ hash = mix_one(hash, v1);
+ hash = mix_one(hash, v2);
+ hash = mix_one(hash, v3);
+ hash = mix_one(hash, v4);
+
+ hash
+ } else {
+ seed.wrapping_add(PRIME_5)
+ };
+
+ hash = hash.wrapping_add(length_bytes as u64);
+
+ // process u64s
+ let mut offset_u64 = offset_u64_4 * 4;
+ while offset_u64 * 8 + 8 <= length_bytes {
+ let mut k1 = unsafe {
+ ptr_u64
+ .add(offset_u64)
+ .read_unaligned()
+ .to_le()
+ .wrapping_mul(PRIME_2)
+ };
+ k1 = k1.rotate_left(31);
+ k1 = k1.wrapping_mul(PRIME_1);
+ hash ^= k1;
+ hash = hash.rotate_left(27);
+ hash = hash.wrapping_mul(PRIME_1);
+ hash = hash.wrapping_add(PRIME_4);
+ offset_u64 += 1;
+ }
+
+ // process u32s
+ let data = &data[offset_u64 * 8..];
+ let ptr_u32 = data.as_ptr() as *const u32;
+ let length_bytes = length_bytes - offset_u64 * 8;
+ let mut offset_u32 = 0;
+ while offset_u32 * 4 + 4 <= length_bytes {
+ let k1 = unsafe {
+ u64::from(ptr_u32.add(offset_u32).read_unaligned().to_le()).wrapping_mul(PRIME_1)
+ };
+ hash ^= k1;
+ hash = hash.rotate_left(23);
+ hash = hash.wrapping_mul(PRIME_2);
+ hash = hash.wrapping_add(PRIME_3);
+ offset_u32 += 1;
+ }
+
+ // process u8s
+ let data = &data[offset_u32 * 4..];
+ let length_bytes = length_bytes - offset_u32 * 4;
+ let mut offset_u8 = 0;
+ while offset_u8 < length_bytes {
+ let k1 = u64::from(data[offset_u8]).wrapping_mul(PRIME_5);
+ hash ^= k1;
+ hash = hash.rotate_left(11);
+ hash = hash.wrapping_mul(PRIME_1);
+ offset_u8 += 1;
+ }
+
+ // The final intermixing
+ hash ^= hash >> 33;
+ hash = hash.wrapping_mul(PRIME_2);
+ hash ^= hash >> 29;
+ hash = hash.wrapping_mul(PRIME_3);
+ hash ^= hash >> 32;
+
+ hash
+}
+
+#[inline(always)]
+fn ingest_one_number(mut current_value: u64, mut value: u64) -> u64 {
+ value = value.wrapping_mul(PRIME_2);
Review Comment:
Should this be `current_value = value.wrapping_mul(PRIME_2)` ?
##########
core/src/execution/datafusion/expressions/xxhash64.rs:
##########
@@ -0,0 +1,186 @@
+// 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.
+
+//! xxhash64 implementation
+
+const CHUNK_SIZE: usize = 32;
+
+const PRIME_1: u64 = 11_400_714_785_074_694_791;
+const PRIME_2: u64 = 14_029_467_366_897_019_727;
+const PRIME_3: u64 = 1_609_587_929_392_839_161;
+const PRIME_4: u64 = 9_650_029_242_287_828_579;
+const PRIME_5: u64 = 2_870_177_450_012_600_261;
+
+/// Custom implementation of xxhash64 based on code from https://github.com/shepmaster/twox-hash
+/// but optimized for our use case by removing any intermediate buffering, which is
+/// not required because we are operating on data that is already in memory.
+#[inline]
+pub(crate) fn spark_compatible_xxhash64<T: AsRef<[u8]>>(data: T, seed: u64) -> u64 {
+ let data: &[u8] = data.as_ref();
+ let length_bytes = data.len();
+
+ let mut v1 = seed.wrapping_add(PRIME_1).wrapping_add(PRIME_2);
+ let mut v2 = seed.wrapping_add(PRIME_2);
+ let mut v3 = seed;
+ let mut v4 = seed.wrapping_sub(PRIME_1);
+
+ // process chunks of 32 bytes
+ let mut offset_u64_4 = 0;
+ let ptr_u64 = data.as_ptr() as *const u64;
+ unsafe {
+ while offset_u64_4 * CHUNK_SIZE + CHUNK_SIZE <= length_bytes {
+ v1 = ingest_one_number(v1, ptr_u64.add(offset_u64_4 * 4).read_unaligned().to_le());
+ v2 = ingest_one_number(
+ v2,
+ ptr_u64.add(offset_u64_4 * 4 + 1).read_unaligned().to_le(),
+ );
+ v3 = ingest_one_number(
+ v3,
+ ptr_u64.add(offset_u64_4 * 4 + 2).read_unaligned().to_le(),
+ );
+ v4 = ingest_one_number(
+ v4,
+ ptr_u64.add(offset_u64_4 * 4 + 3).read_unaligned().to_le(),
+ );
+ offset_u64_4 += 1;
+ }
+ }
+
+ let mut hash = if length_bytes >= CHUNK_SIZE {
+ // We have processed at least one full chunk
+ let mut hash = v1.rotate_left(1);
+ hash = hash.wrapping_add(v2.rotate_left(7));
+ hash = hash.wrapping_add(v3.rotate_left(12));
+ hash = hash.wrapping_add(v4.rotate_left(18));
+
+ hash = mix_one(hash, v1);
+ hash = mix_one(hash, v2);
+ hash = mix_one(hash, v3);
+ hash = mix_one(hash, v4);
+
+ hash
+ } else {
+ seed.wrapping_add(PRIME_5)
+ };
+
+ hash = hash.wrapping_add(length_bytes as u64);
+
+ // process u64s
+ let mut offset_u64 = offset_u64_4 * 4;
+ while offset_u64 * 8 + 8 <= length_bytes {
+ let mut k1 = unsafe {
+ ptr_u64
+ .add(offset_u64)
+ .read_unaligned()
+ .to_le()
+ .wrapping_mul(PRIME_2)
+ };
+ k1 = k1.rotate_left(31);
+ k1 = k1.wrapping_mul(PRIME_1);
+ hash ^= k1;
+ hash = hash.rotate_left(27);
+ hash = hash.wrapping_mul(PRIME_1);
+ hash = hash.wrapping_add(PRIME_4);
+ offset_u64 += 1;
+ }
+
+ // process u32s
+ let data = &data[offset_u64 * 8..];
+ let ptr_u32 = data.as_ptr() as *const u32;
+ let length_bytes = length_bytes - offset_u64 * 8;
+ let mut offset_u32 = 0;
+ while offset_u32 * 4 + 4 <= length_bytes {
+ let k1 = unsafe {
+ u64::from(ptr_u32.add(offset_u32).read_unaligned().to_le()).wrapping_mul(PRIME_1)
+ };
+ hash ^= k1;
+ hash = hash.rotate_left(23);
+ hash = hash.wrapping_mul(PRIME_2);
+ hash = hash.wrapping_add(PRIME_3);
+ offset_u32 += 1;
+ }
+
+ // process u8s
+ let data = &data[offset_u32 * 4..];
+ let length_bytes = length_bytes - offset_u32 * 4;
+ let mut offset_u8 = 0;
+ while offset_u8 < length_bytes {
+ let k1 = u64::from(data[offset_u8]).wrapping_mul(PRIME_5);
+ hash ^= k1;
+ hash = hash.rotate_left(11);
+ hash = hash.wrapping_mul(PRIME_1);
+ offset_u8 += 1;
+ }
+
+ // The final intermixing
+ hash ^= hash >> 33;
+ hash = hash.wrapping_mul(PRIME_2);
+ hash ^= hash >> 29;
+ hash = hash.wrapping_mul(PRIME_3);
+ hash ^= hash >> 32;
+
+ hash
+}
+
+#[inline(always)]
+fn ingest_one_number(mut current_value: u64, mut value: u64) -> u64 {
+ value = value.wrapping_mul(PRIME_2);
+ current_value = current_value.wrapping_add(value);
+ current_value = current_value.rotate_left(31);
+ current_value.wrapping_mul(PRIME_1)
+}
+
+#[inline(always)]
+fn mix_one(mut hash: u64, mut value: u64) -> u64 {
Review Comment:
I know this is based on `twox-hash` which also does what you're doing here. However, this looks like this is the [XXH64_mergeRound](https://github.com/Cyan4973/xxHash/blob/805c00b68fa754200ada0c207ffeaa7a4409377c/xxhash.h#L3422) function which calls [XXH64_Round](https://github.com/Cyan4973/xxHash/blob/805c00b68fa754200ada0c207ffeaa7a4409377c/xxhash.h#L3397) which is slightly different.
XXH64_Round seems to be `ingest_one_number`
##########
core/src/execution/datafusion/expressions/xxhash64.rs:
##########
@@ -0,0 +1,186 @@
+// 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.
+
+//! xxhash64 implementation
+
+const CHUNK_SIZE: usize = 32;
+
+const PRIME_1: u64 = 11_400_714_785_074_694_791;
Review Comment:
Just curious, is this the preferred way to write these or would hex be preferred (one is just as unreadable as the other).
##########
core/src/execution/datafusion/expressions/xxhash64.rs:
##########
@@ -0,0 +1,186 @@
+// 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.
+
+//! xxhash64 implementation
+
+const CHUNK_SIZE: usize = 32;
+
+const PRIME_1: u64 = 11_400_714_785_074_694_791;
+const PRIME_2: u64 = 14_029_467_366_897_019_727;
+const PRIME_3: u64 = 1_609_587_929_392_839_161;
+const PRIME_4: u64 = 9_650_029_242_287_828_579;
+const PRIME_5: u64 = 2_870_177_450_012_600_261;
+
+/// Custom implementation of xxhash64 based on code from https://github.com/shepmaster/twox-hash
+/// but optimized for our use case by removing any intermediate buffering, which is
+/// not required because we are operating on data that is already in memory.
+#[inline]
+pub(crate) fn spark_compatible_xxhash64<T: AsRef<[u8]>>(data: T, seed: u64) -> u64 {
+ let data: &[u8] = data.as_ref();
+ let length_bytes = data.len();
+
+ let mut v1 = seed.wrapping_add(PRIME_1).wrapping_add(PRIME_2);
+ let mut v2 = seed.wrapping_add(PRIME_2);
+ let mut v3 = seed;
+ let mut v4 = seed.wrapping_sub(PRIME_1);
+
+ // process chunks of 32 bytes
+ let mut offset_u64_4 = 0;
+ let ptr_u64 = data.as_ptr() as *const u64;
+ unsafe {
+ while offset_u64_4 * CHUNK_SIZE + CHUNK_SIZE <= length_bytes {
+ v1 = ingest_one_number(v1, ptr_u64.add(offset_u64_4 * 4).read_unaligned().to_le());
+ v2 = ingest_one_number(
+ v2,
+ ptr_u64.add(offset_u64_4 * 4 + 1).read_unaligned().to_le(),
+ );
+ v3 = ingest_one_number(
+ v3,
+ ptr_u64.add(offset_u64_4 * 4 + 2).read_unaligned().to_le(),
+ );
+ v4 = ingest_one_number(
+ v4,
+ ptr_u64.add(offset_u64_4 * 4 + 3).read_unaligned().to_le(),
+ );
+ offset_u64_4 += 1;
+ }
+ }
+
+ let mut hash = if length_bytes >= CHUNK_SIZE {
+ // We have processed at least one full chunk
+ let mut hash = v1.rotate_left(1);
+ hash = hash.wrapping_add(v2.rotate_left(7));
+ hash = hash.wrapping_add(v3.rotate_left(12));
+ hash = hash.wrapping_add(v4.rotate_left(18));
+
+ hash = mix_one(hash, v1);
+ hash = mix_one(hash, v2);
+ hash = mix_one(hash, v3);
+ hash = mix_one(hash, v4);
+
+ hash
+ } else {
+ seed.wrapping_add(PRIME_5)
+ };
+
+ hash = hash.wrapping_add(length_bytes as u64);
+
+ // process u64s
+ let mut offset_u64 = offset_u64_4 * 4;
+ while offset_u64 * 8 + 8 <= length_bytes {
+ let mut k1 = unsafe {
+ ptr_u64
+ .add(offset_u64)
+ .read_unaligned()
+ .to_le()
+ .wrapping_mul(PRIME_2)
+ };
+ k1 = k1.rotate_left(31);
+ k1 = k1.wrapping_mul(PRIME_1);
+ hash ^= k1;
+ hash = hash.rotate_left(27);
+ hash = hash.wrapping_mul(PRIME_1);
+ hash = hash.wrapping_add(PRIME_4);
+ offset_u64 += 1;
+ }
+
+ // process u32s
+ let data = &data[offset_u64 * 8..];
+ let ptr_u32 = data.as_ptr() as *const u32;
+ let length_bytes = length_bytes - offset_u64 * 8;
+ let mut offset_u32 = 0;
+ while offset_u32 * 4 + 4 <= length_bytes {
+ let k1 = unsafe {
+ u64::from(ptr_u32.add(offset_u32).read_unaligned().to_le()).wrapping_mul(PRIME_1)
+ };
+ hash ^= k1;
+ hash = hash.rotate_left(23);
+ hash = hash.wrapping_mul(PRIME_2);
+ hash = hash.wrapping_add(PRIME_3);
+ offset_u32 += 1;
+ }
+
+ // process u8s
+ let data = &data[offset_u32 * 4..];
+ let length_bytes = length_bytes - offset_u32 * 4;
+ let mut offset_u8 = 0;
+ while offset_u8 < length_bytes {
+ let k1 = u64::from(data[offset_u8]).wrapping_mul(PRIME_5);
+ hash ^= k1;
+ hash = hash.rotate_left(11);
+ hash = hash.wrapping_mul(PRIME_1);
+ offset_u8 += 1;
+ }
+
+ // The final intermixing
+ hash ^= hash >> 33;
+ hash = hash.wrapping_mul(PRIME_2);
+ hash ^= hash >> 29;
+ hash = hash.wrapping_mul(PRIME_3);
+ hash ^= hash >> 32;
+
+ hash
+}
+
+#[inline(always)]
+fn ingest_one_number(mut current_value: u64, mut value: u64) -> u64 {
+ value = value.wrapping_mul(PRIME_2);
Review Comment:
Oh, nvm. I was reading this wrong.
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Implement more efficient version of xxhash64 [datafusion-comet]
Posted by "andygrove (via GitHub)" <gi...@apache.org>.
andygrove commented on PR #575:
URL: https://github.com/apache/datafusion-comet/pull/575#issuecomment-2176565540
@parthchandra @advancedxy This is ready for review now
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org