This is an automated email from the ASF dual-hosted git repository.
HappenLee pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/doris.git
The following commit(s) were added to refs/heads/master by this push:
new 45d1598da2f [improvement](be) Accelerate phmap control scans with ARM
NEON (#69688)
45d1598da2f is described below
commit 45d1598da2f85d90ded9c8bcd19982f5b2d93e17
Author: HappenLee <[email protected]>
AuthorDate: Fri Oct 30 16:56:52 2026 +0800
[improvement](be) Accelerate phmap control scans with ARM NEON (#69688)
AArch64 currently uses portable scalar phmap control-byte scans. The
subtraction-based H2 mask can include adjacent false-positive
candidates: control bytes `0x12, 0x13` can both be returned when looking
for `0x12`. Key comparison preserves correctness, but the extra
candidates cost work.
Add exact NEON control comparisons on little-endian AArch64 while
keeping eight-byte groups, the portable fallback and the existing ARM
dump/load layout. x86 keeps its existing SSE implementation.
`PHMAP_HAVE_ARM_NEON=0` disables the new implementation at compile time.
The normal third-party downloader applies this patch alongside the
existing AArch64 int128 hash-mixer patch, with separate markers and a
subshell that restores the caller's working directory. The NEON patch
now includes context so a replay cannot silently insert the same code
again. The downloader checks the actual source with a direction-locked
reverse dry-run, recovers a missing marker when all hunks are already
applied, and preflights every hunk before a fresh application. Partial
or duplicated sources fail without further edits and do not retain a
success marker. The standalone tests cover control masks, unaligned
reads, special slots, conversion bounds, map operations, rehash and
dump/load. The standalone C++ benchmark can be compiled directly. For an
incremental comparison, retain the existing int128 patch in both the
baseline and optimized dependency sources, adding NEON only to the
optimized copy.
### Supplied ARM measurements
The following measurements come from the supplied report on original
Doris baseline `70f7dcbe11c8e142b81536c1dfaaf505ec05437b`, not a new ARM
run of this rebased PR. That baseline predates master's AArch64 int128
patch. These numbers therefore do **not** establish the incremental
gains of the final combined patch stack; a new ARM run with the combined
patch stack is still needed.
Environment: Neoverse-N2, 16 cores, nominal 3 GHz; Clang 20.1.8; C++17,
`-O3 -DNDEBUG -march=armv8-a+crc -pthread`; one process pinned to CPU
15. Nine alternating baseline/NEON rounds, each measurement at least 0.2
seconds of thread CPU time. Values are median thread CPU ns/op. Reported
intervals use 10,000 paired bootstrap resamples.
Positive time reduction means faster; negative means slower.
| Scenario | Baseline ns/op | NEON ns/op | Time reduction | Reported 95%
interval |
|---|---:|---:|---:|---:|
| Hit lookup, 4,096 keys | 4.0773 | 3.8350 | +5.94% | [+5.84%, +6.11%] |
| Hit lookup, 100,000 keys | 10.6120 | 9.6412 | +9.15% | [+8.99%,
+12.44%] |
| Hit lookup, 114,000 keys | 11.4606 | 10.5508 | +7.94% | [+7.73%,
+11.42%] |
| Hit lookup, 1,000,000 keys | 16.3554 | 14.4228 | +11.82% | [+10.20%,
+12.74%] |
| Miss lookup, 4,096 keys | 3.4818 | 3.3069 | +5.02% | [+4.81%, +5.08%]
|
| Miss lookup, 100,000 keys | 9.7027 | 9.9144 | -2.18% | [-2.91%,
-1.27%] |
| Miss lookup, 114,000 keys | 16.8860 | 17.5147 | -3.72% | [-3.93%,
-2.89%] |
| Miss lookup, 1,000,000 keys | 8.6927 | 8.1035 | +6.78% | [+4.93%,
+9.01%] |
| Insert, 100,000 keys, including allocation/destruction | 9.8116 |
9.2758 | +5.46% | [+3.94%, +6.25%] |
| Erase/reinsert, 20,000 operations per iteration | 16.3032 | 16.3810 |
-0.48% | [-1.19%, +0.97%] |
| Synthetic adjacent-H2 scan, 32,768 groups | 2.7578 | 1.7641 | +36.03%
| [+35.75%, +36.09%] |
Load factors differ: approximately 50.0%, 76.3%, 87.0% and 47.7% at the
four lookup sizes. Two miss-lookup workloads regress reproducibly. The
erase/reinsert interval crosses zero. The adjacent-H2 case measures
group scans and candidate-key comparisons, not complete table lookups.
These are library microbenchmarks, not end-to-end SQL gains.
### Validation
**Reported in the supplied ARM bundle:** randomized scalar-oracle
checks, baseline/NEON/forced-portable paths, bidirectional dump/load and
ASAN/UBSAN passed. The archive contains the patch and report; these ARM
executions were not repeated during this submission.
**Executed locally after rebasing onto master
`3d2d9aac54148056529c13ef4b9fbdbcb65fab77` (x86_64, Clang 16.0.6):**
- Standalone correctness tests passed for baseline, patched and
explicitly NEON-disabled builds; x86 selected the existing 16-byte SSE
groups in all three. Tests also exercise the portable group
implementation directly.
- Baseline-to-patched and patched-to-baseline dump/load passed; patched
ASAN/UBSAN passed.
- Benchmark source compiled with `-Wall -Wextra -Werror`; all 11
scenarios passed a short checksum smoke run. No x86 performance
conclusion is drawn from it.
- Standard third-party download/patch script passed twice with `OLDPWD`
unset. The standard downloader produces byte-identical headers to those
used by the standalone tests.
- clang-format 16, repository clang-tidy entry point for both standalone
C++ files, shell syntax and `git diff --check` passed.
**Downloader recovery follow-up:** `bash
thirdparty/test/parallel-hashmap-patch-test.sh` passed using the pinned
cached archive and the real downloader; no dependency downloads were
needed. It covers fresh extraction, normal reruns, an applied patch with
a missing marker, a stale marker over pristine sources, partially
applied sources with/without a marker, and duplicate NEON definitions.
Successful reruns compare both complete headers; failing cases verify
unchanged source and absence of the success marker. The same test
detects the original replay bug. The regenerated patch inserts exactly
the same 67 C++ lines, and its applied header bytes match the original
optimized source. Bash syntax and shell whitespace checks passed;
generated patch context preserves the pinned dependency's existing
whitespace.
Full Doris BE compilation, SQL regression/performance tests and new ARM
measurements against the combined int128+NEON patch stack have not been
run.
The C++ test and benchmark have no Python dependency and can be compiled
directly:
```bash
bash thirdparty/download-thirdparty.sh parallel_hashmap
clang++ -std=c++17 -O2 -pthread -Wall -Wextra -Werror \
-isystem thirdparty/src/parallel-hashmap-1.3.8 \
thirdparty/tests/parallel_hashmap_neon_test.cpp -o /tmp/phmap-neon-test
/tmp/phmap-neon-test
clang++ -std=c++17 -O3 -DNDEBUG -pthread -Wall -Wextra -Werror \
-isystem thirdparty/src/parallel-hashmap-1.3.8 \
thirdparty/benchmarks/parallel_hashmap_bench.cpp -o /tmp/phmap-neon-bench
taskset -c 15 /tmp/phmap-neon-bench 0.2
```
Select an available isolated CPU instead of CPU 15 when necessary. For
the reported ARM compiler settings, add `-march=armv8-a+crc`. The
benchmark emits one JSON line per scenario with CPU/wall timings and
checksums. To compare against baseline on current master, extract the
verified source archive into another directory, apply only
`parallel-hashmap-1.3.8-aarch64-int128.patch`, compile the same C++
benchmark against that directory with identical flags, and alternate
baseline/optimized execution order.
### Release note
Accelerate phmap control-byte scanning on little-endian AArch64 while
preserving eight-byte ARM groups and the portable fallback.
---
thirdparty/benchmarks/parallel_hashmap_bench.cpp | 200 +++++++++++++++
thirdparty/download-thirdparty.sh | 33 ++-
.../patches/parallel-hashmap-1.3.8-arm-neon.patch | 104 ++++++++
thirdparty/test/parallel-hashmap-patch-test.sh | 143 +++++++++++
thirdparty/tests/parallel_hashmap_neon_test.cpp | 272 +++++++++++++++++++++
5 files changed, 743 insertions(+), 9 deletions(-)
diff --git a/thirdparty/benchmarks/parallel_hashmap_bench.cpp
b/thirdparty/benchmarks/parallel_hashmap_bench.cpp
new file mode 100644
index 00000000000..fe10d044740
--- /dev/null
+++ b/thirdparty/benchmarks/parallel_hashmap_bench.cpp
@@ -0,0 +1,200 @@
+// 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.
+
+#include <parallel_hashmap/phmap.h>
+
+#include <algorithm>
+#include <array>
+#include <chrono>
+#include <cstdint>
+#include <ctime>
+#include <iomanip>
+#include <iostream>
+#include <random>
+#include <stdexcept>
+#include <string>
+#include <type_traits>
+#include <vector>
+
+namespace {
+
+using Map = phmap::flat_hash_map<uint64_t, uint64_t>;
+using Group = phmap::priv::Group;
+
+uint64_t mix(uint64_t value) {
+ value += 0x9e3779b97f4a7c15ULL;
+ value = (value ^ (value >> 30)) * 0xbf58476d1ce4e5b9ULL;
+ value = (value ^ (value >> 27)) * 0x94d049bb133111ebULL;
+ return value ^ (value >> 31);
+}
+
+double cpu_seconds() {
+ timespec value {};
+ if (::clock_gettime(CLOCK_THREAD_CPUTIME_ID, &value) != 0) {
+ throw std::runtime_error("clock_gettime failed");
+ }
+ return value.tv_sec + value.tv_nsec * 1e-9;
+}
+
+template <typename Work>
+void measure(const std::string& name, uint64_t operations, size_t size, size_t
capacity,
+ double seconds, Work work) {
+ uint64_t expected = work();
+ uint64_t checksum = 0;
+ uint64_t iterations = 1;
+ double cpu_elapsed = 0;
+ double wall_elapsed = 0;
+ for (;;) {
+ checksum = 0;
+ auto wall_start = std::chrono::steady_clock::now();
+ double cpu_start = cpu_seconds();
+ for (uint64_t iteration = 0; iteration < iterations; ++iteration) {
+ // Force each iteration to read the table again, including under
LTO.
+ asm volatile("" ::: "memory");
+ checksum += work();
+ asm volatile("" : "+r"(checksum) : : "memory");
+ }
+ cpu_elapsed = cpu_seconds() - cpu_start;
+ wall_elapsed =
std::chrono::duration<double>(std::chrono::steady_clock::now() - wall_start)
+ .count();
+ if (cpu_elapsed >= seconds) {
+ break;
+ }
+ iterations *= 2;
+ }
+ if (checksum != expected * iterations) {
+ throw std::runtime_error("benchmark result changed between
iterations");
+ }
+ auto count = static_cast<double>(operations) * iterations;
+ std::cout << std::setprecision(12) << R"({"name":")" << name <<
R"(","size":)" << size
+ << R"(,"capacity":)" << capacity << R"(,"group_width":)" <<
Group::kWidth
+ << R"(,"portable":)"
+ << std::is_same_v<Group, phmap::priv::GroupPortableImpl> <<
R"(,"iterations":)"
+ << iterations << R"(,"operations":)" << operations <<
R"(,"cpu_ns_per_op":)"
+ << cpu_elapsed * 1e9 / count << R"(,"wall_ns_per_op":)" <<
wall_elapsed * 1e9 / count
+ << R"(,"checksum_per_iteration":)" << expected <<
R"(,"checksum":)" << checksum << "}"
+ << std::endl;
+}
+
+std::vector<uint64_t> make_keys(size_t size, size_t start = 0) {
+ std::vector<uint64_t> keys;
+ keys.reserve(size);
+ for (size_t i = 0; i < size; ++i) {
+ keys.push_back(mix(i + start));
+ }
+ std::mt19937_64 random(81384);
+ std::shuffle(keys.begin(), keys.end(), random);
+ return keys;
+}
+
+void lookup_benchmarks(size_t size, double seconds) {
+ auto keys = make_keys(size);
+ auto misses = make_keys(size, size);
+ Map map;
+ map.reserve(size);
+ for (auto key : keys) {
+ map.emplace(key, key + 1);
+ }
+ measure("find_hit/" + std::to_string(size), size, size, map.capacity(),
seconds, [&] {
+ uint64_t checksum = 0;
+ for (auto key : keys) {
+ auto found = map.find(key);
+ checksum += found->second;
+ }
+ return checksum;
+ });
+ measure("find_miss/" + std::to_string(size), size, size, map.capacity(),
seconds, [&] {
+ uint64_t checksum = 0;
+ for (auto key : misses) {
+ checksum += map.find(key) != map.end();
+ }
+ return checksum;
+ });
+}
+
+void mutation_benchmarks(double seconds) {
+ constexpr size_t size = 100000;
+ auto keys = make_keys(size);
+ measure("insert_reserved/100000", size, size, 0, seconds, [&] {
+ Map map;
+ map.reserve(size);
+ for (auto key : keys) {
+ map.emplace(key, key + 1);
+ }
+ asm volatile("" : : "g"(&map) : "memory");
+ return map.size();
+ });
+ Map map;
+ map.reserve(size);
+ for (auto key : keys) {
+ map.emplace(key, key + 1);
+ }
+ constexpr size_t changes = 10000;
+ measure("erase_insert/10000", changes * 2, size, map.capacity(), seconds,
[&] {
+ for (size_t i = 0; i < changes; ++i) {
+ map.erase(keys[i]);
+ }
+ for (size_t i = 0; i < changes; ++i) {
+ map.emplace(keys[i], keys[i] + 1);
+ }
+ return map.size();
+ });
+}
+
+void adjacent_h2_benchmark(double seconds) {
+ struct Probe {
+ std::array<phmap::priv::ctrl_t, Group::kWidth> ctrl;
+ std::array<uint64_t, Group::kWidth> keys;
+ uint64_t needle;
+ };
+ std::vector<Probe> probes(32768);
+ for (size_t i = 0; i < probes.size(); ++i) {
+ auto& probe = probes[i];
+ probe.ctrl.fill(phmap::priv::kEmpty);
+ probe.ctrl[2] = 0x12;
+ probe.ctrl[3] = 0x13;
+ for (size_t j = 0; j < probe.keys.size(); ++j) {
+ probe.keys[j] = mix(i * Group::kWidth + j);
+ }
+ probe.needle = probe.keys[2];
+ }
+ measure("group_adjacent_h2/32768", probes.size(), probes.size(), 0,
seconds, [&] {
+ uint64_t checksum = 0;
+ for (const auto& probe : probes) {
+ for (auto position : Group(probe.ctrl.data()).Match(0x12)) {
+ checksum += probe.keys[position] == probe.needle;
+ }
+ }
+ return checksum;
+ });
+}
+
+} // namespace
+
+int main(int argc, char** argv) {
+ double seconds = argc == 2 ? std::stod(argv[1]) : 0.2;
+ if (seconds <= 0 || seconds > 10) {
+ std::cerr << "minimum CPU seconds must be in (0, 10]\n";
+ return 1;
+ }
+ for (size_t size : {size_t {4096}, size_t {100000}, size_t {114000},
size_t {1000000}}) {
+ lookup_benchmarks(size, seconds);
+ }
+ mutation_benchmarks(seconds);
+ adjacent_h2_benchmark(seconds);
+ return 0;
+}
diff --git a/thirdparty/download-thirdparty.sh
b/thirdparty/download-thirdparty.sh
index 5af6d4a96fa..c3183010b12 100755
--- a/thirdparty/download-thirdparty.sh
+++ b/thirdparty/download-thirdparty.sh
@@ -800,16 +800,31 @@ if [[ " ${TP_ARCHIVES[*]} " =~ " BOOST " ]]; then
echo "Finished patching ${BOOST_SOURCE}"
fi
-# Clang on AArch64 supports __int128. Enable phmap's multiply-based hash mixer
-# instead of falling back to the longer shift/xor implementation.
+# Clang on AArch64 supports __int128. Keep the existing hash mixer patch and
+# accelerate ARM control scans without changing the eight-byte group layout.
if [[ " ${TP_ARCHIVES[*]} " =~ " PARALLEL_HASHMAP " ]]; then
- cd "${TP_SOURCE_DIR}/${PARALLEL_HASHMAP_SOURCE}"
- if [[ ! -f "${PATCHED_MARK}_aarch64_int128" ]]; then
- patch -p1
<"${TP_PATCH_DIR}/parallel-hashmap-1.3.8-aarch64-int128.patch"
- touch "${PATCHED_MARK}_aarch64_int128"
- fi
- cd -
- echo "Finished patching ${PARALLEL_HASHMAP_SOURCE} for AArch64 int128"
+ (
+ cd "${TP_SOURCE_DIR}/${PARALLEL_HASHMAP_SOURCE}"
+ if [[ ! -f "${PATCHED_MARK}_aarch64_int128" ]]; then
+ patch -p1
<"${TP_PATCH_DIR}/parallel-hashmap-1.3.8-aarch64-int128.patch"
+ touch "${PATCHED_MARK}_aarch64_int128"
+ fi
+ neon_patch="${TP_PATCH_DIR}/parallel-hashmap-1.3.8-arm-neon.patch"
+ # A run can stop after patching but before writing the marker. Check
the
+ # source even when the marker exists: the old insertion-only patch
could
+ # be applied twice and still leave a marker claiming success.
+ # --forward prevents either dry-run probe from automatically changing
direction.
+ if ! patch --dry-run --batch --forward --reverse --fuzz=0 -p1 \
+ <"${neon_patch}" >/dev/null 2>&1; then
+ rm -f "${PATCHED_MARK}_arm_neon"
+ # Check every hunk before modifying any file; partial or
incompatible
+ # sources must fail without accepting or further applying the
patch.
+ patch --dry-run --batch --forward --fuzz=0 -p1 <"${neon_patch}"
+ patch --batch --forward --fuzz=0 -p1 <"${neon_patch}"
+ fi
+ touch "${PATCHED_MARK}_arm_neon"
+ )
+ echo "Finished patching ${PARALLEL_HASHMAP_SOURCE} (AArch64 int128 and ARM
NEON)"
fi
# vim: ts=4 sw=4 ts=4 tw=100:
diff --git a/thirdparty/patches/parallel-hashmap-1.3.8-arm-neon.patch
b/thirdparty/patches/parallel-hashmap-1.3.8-arm-neon.patch
new file mode 100644
index 00000000000..53eac662c72
--- /dev/null
+++ b/thirdparty/patches/parallel-hashmap-1.3.8-arm-neon.patch
@@ -0,0 +1,104 @@
+--- a/parallel_hashmap/phmap.h
++++ b/parallel_hashmap/phmap.h
+@@ -462,10 +462,59 @@
+ #pragma warning(pop)
+ #endif
+
+ #endif // PHMAP_HAVE_SSE2
+
++#if PHMAP_HAVE_ARM_NEON && defined(PHMAP_IS_LITTLE_ENDIAN)
++
++struct GroupAArch64Impl {
++ enum { kWidth = 8 };
++
++ explicit GroupAArch64Impl(const ctrl_t* pos) { ctrl =
vld1_u8(reinterpret_cast<const uint8_t*>(pos)); }
++
++ BitMask<uint64_t, kWidth, 3> Match(h2_t hash) const {
++ uint8x8_t dup = vdup_n_u8(hash);
++ auto mask = vceq_u8(ctrl, dup);
++ constexpr uint64_t msbs = 0x8080808080808080ULL;
++ return BitMask<uint64_t, kWidth,
3>(vget_lane_u64(vreinterpret_u64_u8(mask), 0) & msbs);
++ }
++
++ BitMask<uint64_t, kWidth, 3> MatchEmpty() const {
++ auto mask = vceq_s8(vdup_n_s8(static_cast<ctrl_t>(kEmpty)),
vreinterpret_s8_u8(ctrl));
++ constexpr uint64_t msbs = 0x8080808080808080ULL;
++ return BitMask<uint64_t, kWidth,
3>(vget_lane_u64(vreinterpret_u64_u8(mask), 0) & msbs);
++ }
++
++ BitMask<uint64_t, kWidth, 3> MatchEmptyOrDeleted() const {
++ auto mask = vcgt_s8(vdup_n_s8(static_cast<ctrl_t>(kSentinel)),
vreinterpret_s8_u8(ctrl));
++ constexpr uint64_t msbs = 0x8080808080808080ULL;
++ return BitMask<uint64_t, kWidth,
3>(vget_lane_u64(vreinterpret_u64_u8(mask), 0) & msbs);
++ }
++
++ uint32_t CountLeadingEmptyOrDeleted() const {
++ uint64_t mask = vget_lane_u64(vreinterpret_u64_u8(ctrl), 0);
++ // ctrl | ~(ctrl >> 7) has the lowest bit of each byte set to 0 for
kEmpty (-128)
++ // and kDeleted (-2), and 1 for kSentinel (-1) and full slots
(0..127).
++ constexpr uint64_t bits = 0x0101010101010101ULL;
++ uint64_t x = (mask | ~(mask >> 7)) & bits;
++ return static_cast<uint32_t>((x == 0 ? 64 : TrailingZeros(x)) >> 3);
++ }
++
++ void ConvertSpecialToEmptyAndFullToDeleted(ctrl_t* dst) const {
++ uint64_t mask = vget_lane_u64(vreinterpret_u64_u8(ctrl), 0);
++ constexpr uint64_t msbs = 0x8080808080808080ULL;
++ constexpr uint64_t lsbs = 0x0101010101010101ULL;
++ auto x = mask & msbs;
++ auto res = (~x + (x >> 7)) & ~lsbs;
++ little_endian::Store64(dst, res);
++ }
++
++ uint8x8_t ctrl;
++};
++
++#endif // PHMAP_HAVE_ARM_NEON && defined(PHMAP_IS_LITTLE_ENDIAN)
++
+ // --------------------------------------------------------------------------
+ // --------------------------------------------------------------------------
+ struct GroupPortableImpl
+ {
+ enum { kWidth = 8 };
+@@ -519,10 +568,15 @@
+ uint64_t ctrl;
+ };
+
+ #if PHMAP_HAVE_SSE2
+ using Group = GroupSse2Impl;
++#elif PHMAP_HAVE_ARM_NEON && defined(PHMAP_IS_LITTLE_ENDIAN)
++ using Group = GroupAArch64Impl;
++ static_assert(static_cast<size_t>(Group::kWidth) ==
++ static_cast<size_t>(GroupPortableImpl::kWidth),
++ "ARM NEON must preserve the portable phmap dump/load
layout");
+ #else
+ using Group = GroupPortableImpl;
+ #endif
+
+ // The number of cloned control bytes that we copy from the beginning to the
+--- a/parallel_hashmap/phmap_config.h
++++ b/parallel_hashmap/phmap_config.h
+@@ -660,10 +660,23 @@
+
+ #if PHMAP_HAVE_SSE2
+ #include <emmintrin.h>
+ #endif
+
++// ARM NEON comparisons use the same eight control bytes as the portable
group.
++#ifndef PHMAP_HAVE_ARM_NEON
++ #if defined(__ARM_NEON) && defined(__aarch64__) &&
defined(PHMAP_IS_LITTLE_ENDIAN)
++ #define PHMAP_HAVE_ARM_NEON 1
++ #else
++ #define PHMAP_HAVE_ARM_NEON 0
++ #endif
++#endif
++
++#if PHMAP_HAVE_ARM_NEON
++ #include <arm_neon.h>
++#endif
++
+ #if PHMAP_HAVE_SSSE3
+ #include <tmmintrin.h>
+ #endif
+
+
diff --git a/thirdparty/test/parallel-hashmap-patch-test.sh
b/thirdparty/test/parallel-hashmap-patch-test.sh
new file mode 100755
index 00000000000..893a586cd09
--- /dev/null
+++ b/thirdparty/test/parallel-hashmap-patch-test.sh
@@ -0,0 +1,143 @@
+#!/usr/bin/env bash
+# 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.
+
+set -euo pipefail
+
+ROOT="$(cd "$(dirname "${BASH_SOURCE[0]}")/.." &>/dev/null && pwd)"
+ARCHIVE_DIR="${1:-${ROOT}/src}"
+ARCHIVE_DIR="$(cd "${ARCHIVE_DIR}" && pwd)"
+TP_DIR="${ROOT}"
+source "${ROOT}/vars.sh"
+[[ -f "${ARCHIVE_DIR}/${PARALLEL_HASHMAP_NAME}" ]] || {
+ echo "FAIL: provide the directory containing ${PARALLEL_HASHMAP_NAME}" >&2
+ exit 1
+}
+
+mkdir -p "${ROOT}/src"
+tmpdir="$(mktemp -d "${ROOT}/src/phmap-patch-test.XXXXXX")"
+trap 'rm -rf "${tmpdir}"' EXIT
+
+fail() {
+ echo "FAIL: $*" >&2
+ exit 1
+}
+
+prepare() {
+ local dest="$1"
+ mkdir -p "${dest}/src"
+ cp "${ROOT}/vars.sh" "${dest}/vars.sh"
+ ln -s "${ROOT}/patches" "${dest}/patches"
+ cp "${ARCHIVE_DIR}/${PARALLEL_HASHMAP_NAME}" "${dest}/src/"
+}
+
+run_download() {
+ TP_DIR="$1" DORIS_HOME="${tmpdir}" bash "${ROOT}/download-thirdparty.sh"
parallel_hashmap
+}
+
+check_sources() {
+ local source="$1/src/${PARALLEL_HASHMAP_SOURCE}"
+ [[ -f "${source}/patched_mark_aarch64_int128" ]] || fail "missing int128
marker"
+ [[ -f "${source}/patched_mark_arm_neon" ]] || fail "missing NEON marker"
+ [[ "$(grep -c '^struct GroupAArch64Impl {'
"${source}/parallel_hashmap/phmap.h")" == 1 ]] \
+ || fail "NEON group must appear exactly once"
+ cmp "${tmpdir}/expected/phmap.h" "${source}/parallel_hashmap/phmap.h"
+ cmp "${tmpdir}/expected/phmap_config.h"
"${source}/parallel_hashmap/phmap_config.h"
+}
+
+snapshot() {
+ local source="$1/src/${PARALLEL_HASHMAP_SOURCE}/parallel_hashmap"
+ cp "${source}/phmap.h" "${tmpdir}/before-phmap.h"
+ cp "${source}/phmap_config.h" "${tmpdir}/before-phmap_config.h"
+}
+
+expect_failure() {
+ local dest="$1"
+ if run_download "${dest}" >"${dest}/failure.log" 2>&1; then
+ fail "incompatible or partial patch unexpectedly succeeded"
+ fi
+ local source="${dest}/src/${PARALLEL_HASHMAP_SOURCE}"
+ [[ ! -f "${source}/patched_mark_arm_neon" ]] || fail "failed patch
retained its marker"
+ cmp "${tmpdir}/before-phmap.h" "${source}/parallel_hashmap/phmap.h"
+ cmp "${tmpdir}/before-phmap_config.h"
"${source}/parallel_hashmap/phmap_config.h"
+}
+
+prepare "${tmpdir}/fresh"
+run_download "${tmpdir}/fresh"
+source_dir="${tmpdir}/fresh/src/${PARALLEL_HASHMAP_SOURCE}"
+mkdir "${tmpdir}/expected"
+cp "${source_dir}/parallel_hashmap/phmap.h" "${tmpdir}/expected/"
+cp "${source_dir}/parallel_hashmap/phmap_config.h" "${tmpdir}/expected/"
+check_sources "${tmpdir}/fresh"
+touch "${source_dir}/cache_reuse_sentinel"
+run_download "${tmpdir}/fresh"
+check_sources "${tmpdir}/fresh"
+[[ -f "${source_dir}/cache_reuse_sentinel" ]] || fail "rerun replaced cached
sources"
+echo "PASS: fresh sources and normal rerun"
+
+# Model a process stopping between the completed patch and the marker write.
+rm "${source_dir}/patched_mark_arm_neon"
+run_download "${tmpdir}/fresh"
+check_sources "${tmpdir}/fresh"
+run_download "${tmpdir}/fresh"
+check_sources "${tmpdir}/fresh"
+echo "PASS: completed patch without a marker recovers without reapplying"
+
+# A stale marker must not suppress applying the patch to pristine sources.
+prepare "${tmpdir}/stale"
+tar xzf "${ARCHIVE_DIR}/${PARALLEL_HASHMAP_NAME}" -C "${tmpdir}/stale/src"
+touch "${tmpdir}/stale/src/${PARALLEL_HASHMAP_SOURCE}/patched_mark_arm_neon"
+run_download "${tmpdir}/stale"
+check_sources "${tmpdir}/stale"
+echo "PASS: stale marker on pristine sources"
+
+# One patched file and one unpatched file must be rejected before either
changes.
+# Keep the real int128 patch applied, as it precedes NEON in the downloader.
+for marker in missing present; do
+ prepare "${tmpdir}/partial-${marker}"
+ tar xzf "${ARCHIVE_DIR}/${PARALLEL_HASHMAP_NAME}" -C
"${tmpdir}/partial-${marker}/src"
+ partial_source="${tmpdir}/partial-${marker}/src/${PARALLEL_HASHMAP_SOURCE}"
+ (
+ cd "${partial_source}"
+ patch --batch --forward --fuzz=0 -p1 \
+ <"${ROOT}/patches/parallel-hashmap-1.3.8-aarch64-int128.patch"
+ touch patched_mark_aarch64_int128
+ )
+ cp "${tmpdir}/expected/phmap.h"
"${partial_source}/parallel_hashmap/phmap.h"
+ if [[ "${marker}" == present ]]; then
+ touch "${partial_source}/patched_mark_arm_neon"
+ fi
+ snapshot "${tmpdir}/partial-${marker}"
+ expect_failure "${tmpdir}/partial-${marker}"
+done
+echo "PASS: partial sources fail without further edits or a success marker"
+
+# Duplicate definitions reproduce the old insertion-only patch's replay result.
+prepare "${tmpdir}/duplicate"
+run_download "${tmpdir}/duplicate"
+duplicate_source="${tmpdir}/duplicate/src/${PARALLEL_HASHMAP_SOURCE}"
+awk '
+ /^#if PHMAP_HAVE_ARM_NEON && defined\(PHMAP_IS_LITTLE_ENDIAN\)/ && !found
{ copying = 1 }
+ copying { block = block $0 "\n" }
+ copying && /^#endif/ { copying = 0; found = 1 }
+ { print }
+ found && !inserted { printf "%s", block; inserted = 1 }
+' "${duplicate_source}/parallel_hashmap/phmap.h" >"${tmpdir}/duplicate-phmap.h"
+mv "${tmpdir}/duplicate-phmap.h" "${duplicate_source}/parallel_hashmap/phmap.h"
+snapshot "${tmpdir}/duplicate"
+expect_failure "${tmpdir}/duplicate"
+echo "PASS: duplicate NEON definitions are rejected despite an existing marker"
diff --git a/thirdparty/tests/parallel_hashmap_neon_test.cpp
b/thirdparty/tests/parallel_hashmap_neon_test.cpp
new file mode 100644
index 00000000000..535819c54c9
--- /dev/null
+++ b/thirdparty/tests/parallel_hashmap_neon_test.cpp
@@ -0,0 +1,272 @@
+// 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.
+
+#include <parallel_hashmap/phmap.h>
+#include <parallel_hashmap/phmap_dump.h>
+
+#include <algorithm>
+#include <array>
+#include <cstdint>
+#include <fstream>
+#include <iostream>
+#include <random>
+#include <sstream>
+#include <stdexcept>
+#include <string>
+#include <type_traits>
+#include <unordered_map>
+#include <vector>
+
+namespace {
+
+using phmap::priv::ctrl_t;
+using phmap::priv::Group;
+using phmap::priv::GroupPortableImpl;
+using phmap::priv::h2_t;
+using phmap::priv::kDeleted;
+using phmap::priv::kEmpty;
+using phmap::priv::kSentinel;
+
+void require(bool condition, const char* message) {
+ if (!condition) {
+ throw std::runtime_error(message);
+ }
+}
+
+template <typename Mask>
+std::vector<uint32_t> positions(Mask mask) {
+ std::vector<uint32_t> result;
+ for (uint32_t position : mask) {
+ result.push_back(position);
+ }
+ require(static_cast<bool>(mask) == !result.empty(), "mask bool");
+ if (!result.empty()) {
+ require(mask.TrailingZeros() == result.front(), "trailing zeros");
+ }
+ return result;
+}
+
+template <typename Impl>
+void check_group(const ctrl_t* bytes, h2_t hash) {
+ constexpr int width = Impl::kWidth;
+ Impl group(bytes);
+ std::vector<uint32_t> matches;
+ std::vector<uint32_t> empty;
+ std::vector<uint32_t> available;
+ for (int i = 0; i < width; ++i) {
+ if (bytes[i] == static_cast<ctrl_t>(hash)) {
+ matches.push_back(i);
+ }
+ if (bytes[i] == kEmpty) {
+ empty.push_back(i);
+ }
+ if (bytes[i] == kEmpty || bytes[i] == kDeleted) {
+ available.push_back(i);
+ }
+ }
+ auto actual = positions(group.Match(hash));
+ if constexpr (std::is_same_v<Impl, GroupPortableImpl>) {
+ // The scalar subtraction can borrow into an adjacent byte: 0x12,0x13
+ // can both match 0x12. Only full slots may be false positives.
+ require(matches.empty() == actual.empty(), "portable match emptiness");
+ for (auto expected : matches) {
+ require(std::find(actual.begin(), actual.end(), expected) !=
actual.end(),
+ "portable missed an exact match");
+ }
+ for (auto position : actual) {
+ require(position < width && bytes[position] >= 0, "portable
matched special slot");
+ }
+ } else {
+ require(actual == matches, "SIMD match differs from scalar oracle");
+ }
+ require(positions(group.MatchEmpty()) == empty, "empty mask");
+ require(positions(group.MatchEmptyOrDeleted()) == available,
"empty/deleted mask");
+ if (!actual.empty()) {
+ require(group.Match(hash).LeadingZeros() == width - 1 - actual.back(),
"leading zeros");
+ }
+ uint32_t leading = 0;
+ while (leading < width && (bytes[leading] == kEmpty || bytes[leading] ==
kDeleted)) {
+ ++leading;
+ }
+ require(group.CountLeadingEmptyOrDeleted() == leading, "leading
empty/deleted count");
+
+ std::array<ctrl_t, width + 16> converted;
+ converted.fill(42);
+ group.ConvertSpecialToEmptyAndFullToDeleted(converted.data() + 7);
+ for (int i = 0; i < width; ++i) {
+ require(converted[i + 7] == (bytes[i] < 0 ? kEmpty : kDeleted),
"special conversion");
+ }
+ for (int i = 0; i < 7; ++i) {
+ require(converted[i] == 42, "conversion underrun");
+ }
+ for (size_t i = width + 7; i < converted.size(); ++i) {
+ require(converted[i] == 42, "conversion overrun");
+ }
+}
+
+void check_groups() {
+ std::mt19937 random(81384);
+ std::array<ctrl_t, 32> bytes;
+ constexpr std::array<ctrl_t, 3> special_values {kEmpty, kDeleted,
kSentinel};
+ for (int iteration = 0; iteration < 100000; ++iteration) {
+ bytes.fill(kEmpty);
+ auto* data = bytes.data() + (iteration & 7);
+ for (int i = 0; i < Group::kWidth; ++i) {
+ uint32_t value = random() % 131;
+ data[i] = value < 128 ? static_cast<ctrl_t>(value) :
special_values[value - 128];
+ }
+ h2_t hash = random() % 128;
+ check_group<Group>(data, hash);
+ check_group<GroupPortableImpl>(data, hash);
+ }
+ for (int offset = 0; offset < 8; ++offset) {
+ for (auto special : {kEmpty, kDeleted, kSentinel}) {
+ bytes.fill(special);
+ check_group<Group>(bytes.data() + offset, 0);
+ check_group<GroupPortableImpl>(bytes.data() + offset, 0);
+ }
+ for (int lane = 0; lane < Group::kWidth; ++lane) {
+ for (int value = 0; value < 128; ++value) {
+ bytes.fill(kEmpty);
+ bytes[offset + lane] = static_cast<ctrl_t>(value);
+ check_group<Group>(bytes.data() + offset, value);
+ }
+ }
+ }
+ bytes.fill(kEmpty);
+ bytes[2] = 0x12;
+ bytes[3] = 0x13;
+ check_group<Group>(bytes.data(), 0x12);
+ require(positions(GroupPortableImpl(bytes.data()).Match(0x12)) ==
std::vector<uint32_t>({2, 3}),
+ "adjacent-H2 scalar baseline");
+}
+
+template <typename Map>
+void check_map() {
+ Map map;
+ std::unordered_map<uint64_t, uint64_t> reference;
+ std::mt19937_64 random(81384);
+ map.reserve(65536);
+ for (int i = 0; i < 200000; ++i) {
+ uint64_t key = random() % 60000;
+ uint64_t value = random();
+ switch (i % 4) {
+ case 0:
+ case 1:
+ map[key] = value;
+ reference[key] = value;
+ break;
+ case 2:
+ require(map.erase(key) == reference.erase(key), "erase result");
+ break;
+ default: {
+ auto found = map.find(key);
+ auto expected = reference.find(key);
+ require((found == map.end()) == (expected == reference.end()),
"find result");
+ if (found != map.end()) {
+ require(found->second == expected->second, "find value");
+ }
+ }
+ }
+ if (i % 16384 == 0) {
+ map.rehash(map.size() * 2);
+ }
+ }
+ require(map.size() == reference.size(), "map size");
+ for (const auto& [key, value] : reference) {
+ auto found = map.find(key);
+ require(found != map.end() && found->second == value, "map final
content");
+ }
+}
+
+struct Archive {
+ std::iostream& stream;
+ void saveBinary(const void* data, size_t bytes) {
+ stream.write(static_cast<const char*>(data), bytes);
+ require(static_cast<bool>(stream), "dump write");
+ }
+ void loadBinary(void* data, size_t bytes) {
+ stream.read(static_cast<char*>(data), bytes);
+ require(static_cast<bool>(stream), "dump read");
+ }
+};
+
+using DumpMap = phmap::flat_hash_map<uint64_t, uint64_t>;
+
+DumpMap dump_fixture() {
+ DumpMap map;
+ for (uint64_t i = 0; i < 10000; ++i) {
+ map[i * 7 + 3] = i * 11 + 5;
+ }
+ for (uint64_t i = 0; i < 10000; i += 3) {
+ map.erase(i * 7 + 3);
+ }
+ return map;
+}
+
+void check_loaded(const DumpMap& map) {
+ auto expected = dump_fixture();
+ require(map.size() == expected.size(), "dump/load size");
+ for (const auto& [key, value] : expected) {
+ auto found = map.find(key);
+ require(found != map.end() && found->second == value, "dump/load
content");
+ }
+}
+
+} // namespace
+
+int main(int argc, char** argv) {
+ try {
+ if (argc == 3) {
+ const bool dumping = std::string(argv[1]) == "--dump";
+ auto mode = std::ios::in | std::ios::out | std::ios::binary;
+ if (dumping) {
+ mode |= std::ios::trunc;
+ }
+ std::fstream stream(argv[2], mode);
+ require(static_cast<bool>(stream), "open archive");
+ Archive archive {stream};
+ if (dumping) {
+ auto map = dump_fixture();
+ require(map.phmap_dump(archive), "dump");
+ } else {
+ require(std::string(argv[1]) == "--load", "unknown archive
operation");
+ DumpMap map;
+ require(map.phmap_load(archive), "load");
+ check_loaded(map);
+ }
+ } else {
+ require(argc == 1, "unexpected arguments");
+ check_groups();
+ check_map<phmap::flat_hash_map<uint64_t, uint64_t>>();
+ check_map<phmap::parallel_flat_hash_map<uint64_t, uint64_t>>();
+ std::stringstream stream;
+ Archive archive {stream};
+ auto source = dump_fixture();
+ require(source.phmap_dump(archive), "roundtrip dump");
+ DumpMap loaded;
+ require(loaded.phmap_load(archive), "roundtrip load");
+ check_loaded(loaded);
+ }
+ std::cout << "PASS group_width=" << Group::kWidth
+ << " portable=" << std::is_same_v<Group, GroupPortableImpl>
<< '\n';
+ return 0;
+ } catch (const std::exception& error) {
+ std::cerr << "FAIL: " << error.what() << '\n';
+ return 1;
+ }
+}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
