You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@doris.apache.org by GitBox <gi...@apache.org> on 2022/07/17 07:39:19 UTC
[GitHub] [doris] mrhhsg opened a new pull request, #10937: [improvement][agg]Use sub hashmap to speed up aggregation with string key
mrhhsg opened a new pull request, #10937:
URL: https://github.com/apache/doris/pull/10937
# Proposed changes
Issue Number: close #xxx
## Problem Summary:
Test on ssb-flat(100g) with SQL:
```sql
select c_address,count() from lineorder_flat group by c_address order by c_address limit 20;
```
Execution time was reduced by 5%
## Checklist(Required)
1. Does it affect the original behavior: (Yes/No/I Don't know)
2. Has unit tests been added: (Yes/No/No Need)
3. Has document been added or modified: (Yes/No/No Need)
4. Does it need to update dependencies: (Yes/No)
5. Are there any changes that cannot be rolled back: (Yes/No)
## Further comments
If this is a relatively large or complex change, kick off the discussion at [dev@doris.apache.org](mailto:dev@doris.apache.org) by explaining why you chose the solution you did and what alternatives you considered, etc...
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
[GitHub] [doris] mrhhsg commented on a diff in pull request #10937: [improvement][agg]Import sub hash map
Posted by GitBox <gi...@apache.org>.
mrhhsg commented on code in PR #10937:
URL: https://github.com/apache/doris/pull/10937#discussion_r922840232
##########
be/src/vec/common/hash_table/string_hash_table.h:
##########
@@ -0,0 +1,612 @@
+// 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.
+// This file is copied from
+// https://github.com/ClickHouse/ClickHouse/blob/master/src/Common/HashTable/StringHashTable.h
+// and modified by Doris
+
+#pragma once
+
+#include <new>
+#include <variant>
+
+#include "vec/common/hash_table/hash.h"
+
+using StringKey8 = doris::vectorized::UInt64;
+using StringKey16 = doris::vectorized::UInt128;
+struct StringKey24 {
+ doris::vectorized::UInt64 a;
+ doris::vectorized::UInt64 b;
+ doris::vectorized::UInt64 c;
+
+ bool operator==(const StringKey24 rhs) const { return a == rhs.a && b == rhs.b && c == rhs.c; }
+};
+
+inline StringRef ALWAYS_INLINE to_string_ref(const StringKey8& n) {
+ assert(n != 0);
+ return {reinterpret_cast<const char*>(&n), 8ul - (__builtin_clzll(n) >> 3)};
+}
+inline StringRef ALWAYS_INLINE to_string_ref(const StringKey16& n) {
+ assert(n.high != 0);
+ return {reinterpret_cast<const char*>(&n), 16ul - (__builtin_clzll(n.high) >> 3)};
+}
+inline StringRef ALWAYS_INLINE to_string_ref(const StringKey24& n) {
+ assert(n.c != 0);
+ return {reinterpret_cast<const char*>(&n), 24ul - (__builtin_clzll(n.c) >> 3)};
+}
+
+struct StringHashTableHash {
+#if defined(__SSE4_2__)
+ size_t ALWAYS_INLINE operator()(StringKey8 key) const {
+ size_t res = -1ULL;
+ res = _mm_crc32_u64(res, key);
+ return res;
+ }
+ size_t ALWAYS_INLINE operator()(StringKey16 key) const {
+ size_t res = -1ULL;
+ res = _mm_crc32_u64(res, key.low);
+ res = _mm_crc32_u64(res, key.high);
+ return res;
+ }
+ size_t ALWAYS_INLINE operator()(StringKey24 key) const {
+ size_t res = -1ULL;
+ res = _mm_crc32_u64(res, key.a);
+ res = _mm_crc32_u64(res, key.b);
+ res = _mm_crc32_u64(res, key.c);
+ return res;
+ }
+#else
+ size_t ALWAYS_INLINE operator()(StringKey8 key) const {
+ return util_hash::CityHash64(reinterpret_cast<const char*>(&key), 8);
+ }
+ size_t ALWAYS_INLINE operator()(StringKey16 key) const {
+ return util_hash::CityHash64(reinterpret_cast<const char*>(&key), 16);
+ }
+ size_t ALWAYS_INLINE operator()(StringKey24 key) const {
+ return util_hash::CityHash64(reinterpret_cast<const char*>(&key), 24);
+ }
+#endif
+ size_t ALWAYS_INLINE operator()(StringRef key) const { return StringRefHash()(key); }
+};
+
+template <typename Cell>
+struct StringHashTableEmpty //-V730
+{
+ using Self = StringHashTableEmpty;
+
+ bool _has_zero = false;
+ std::aligned_storage_t<sizeof(Cell), alignof(Cell)>
+ zero_value_storage; /// Storage of element with zero key.
+
+public:
+ bool has_zero() const { return _has_zero; }
+
+ void set_has_zero() {
+ _has_zero = true;
+ new (zero_value()) Cell();
+ }
+
+ void set_has_zero(const Cell& other) {
+ _has_zero = true;
+ new (zero_value()) Cell(other);
+ }
+
+ void clear_has_zero() {
+ _has_zero = false;
+ if (!std::is_trivially_destructible_v<Cell>) zero_value()->~Cell();
+ }
+
+ Cell* zero_value() { return std::launder(reinterpret_cast<Cell*>(&zero_value_storage)); }
+ const Cell* zero_value() const {
+ return std::launder(reinterpret_cast<const Cell*>(&zero_value_storage));
+ }
+
+ using LookupResult = Cell*;
+ using ConstLookupResult = const Cell*;
+
+ template <typename KeyHolder>
+ void ALWAYS_INLINE emplace(KeyHolder&&, LookupResult& it, bool& inserted, size_t = 0) {
+ if (!has_zero()) {
+ set_has_zero();
+ inserted = true;
+ } else
+ inserted = false;
+ it = zero_value();
+ }
+
+ template <typename Key>
+ LookupResult ALWAYS_INLINE find(const Key&, size_t = 0) {
+ return has_zero() ? zero_value() : nullptr;
+ }
+
+ template <typename Key>
+ ConstLookupResult ALWAYS_INLINE find(const Key&, size_t = 0) const {
+ return has_zero() ? zero_value() : nullptr;
+ }
+
+ size_t size() const { return has_zero() ? 1 : 0; }
+ bool empty() const { return !has_zero(); }
+ size_t get_buffer_size_in_bytes() const { return sizeof(Cell); }
+};
+
+template <size_t initial_size_degree = 8>
+struct StringHashTableGrower : public HashTableGrowerWithPrecalculation<initial_size_degree> {
+ // Smooth growing for string maps
+ void increase_size() { this->increase_size_degree(1); }
+};
+
+template <typename Mapped>
+struct StringHashTableLookupResult {
+ Mapped* mapped_ptr;
+ StringHashTableLookupResult() : mapped_ptr(nullptr) {} /// NOLINT
+ StringHashTableLookupResult(Mapped* mapped_ptr_) : mapped_ptr(mapped_ptr_) {} /// NOLINT
+ StringHashTableLookupResult(std::nullptr_t) {} /// NOLINT
+ const VoidKey getKey() const { return {}; } /// NOLINT
+ auto& get_mapped() { return *mapped_ptr; }
+ auto& operator*() { return *this; }
+ auto& operator*() const { return *this; }
+ auto* operator->() { return this; }
+ auto* operator->() const { return this; }
+ explicit operator bool() const { return mapped_ptr; }
+ friend bool operator==(const StringHashTableLookupResult& a, const std::nullptr_t&) {
+ return !a.mapped_ptr;
+ }
+ friend bool operator==(const std::nullptr_t&, const StringHashTableLookupResult& b) {
+ return !b.mapped_ptr;
+ }
+ friend bool operator!=(const StringHashTableLookupResult& a, const std::nullptr_t&) {
+ return a.mapped_ptr;
+ }
+ friend bool operator!=(const std::nullptr_t&, const StringHashTableLookupResult& b) {
+ return b.mapped_ptr;
+ }
+};
+
+template <typename Mapped>
+ALWAYS_INLINE inline auto lookup_result_get_mapped(StringHashTableLookupResult<Mapped*> cell) {
+ return &cell.get_mapped();
+}
+
+template <typename SubMaps>
+class StringHashTable : private boost::noncopyable {
+protected:
+ static constexpr size_t NUM_MAPS = 5;
+ // Map for storing empty string
+ using T0 = typename SubMaps::T0;
+
+ // Short strings are stored as numbers
+ using T1 = typename SubMaps::T1;
+ using T2 = typename SubMaps::T2;
+ using T3 = typename SubMaps::T3;
+
+ // Long strings are stored as StringRef along with saved hash
+ using Ts = typename SubMaps::Ts;
+ using Self = StringHashTable;
+
+ template <typename, typename, size_t>
+ friend class TwoLevelStringHashTable;
+
+ T0 m0;
+ T1 m1;
+ T2 m2;
+ T3 m3;
+ Ts ms;
+
+ using Cell = typename Ts::cell_type;
+
+ friend class const_iterator;
+ friend class iterator;
+
+ template <typename Derived, bool is_const>
+ class iterator_base {
+ using Container = std::conditional_t<is_const, const Self, Self>;
+
+ Container* container;
+ int sub_table_index;
+ typename T1::iterator iterator1;
+ typename T2::iterator iterator2;
+ typename T3::iterator iterator3;
+ typename Ts::iterator iterator4;
+
+ typename Ts::cell_type cell;
+
+ friend class StringHashTable;
+
+ public:
+ iterator_base() {}
+ iterator_base(Container* container_, bool end = false) : container(container_) {
+ if (end) {
+ sub_table_index = 4;
+ iterator4 = container->ms.end();
+ } else {
+ sub_table_index = 0;
+ if (container->m0.size() == 0)
+ sub_table_index++;
+ else
+ return;
+
+ iterator1 = container->m1.begin();
+ if (iterator1 == container->m1.end())
+ sub_table_index++;
+ else
+ return;
+
+ iterator2 = container->m2.begin();
+ if (iterator2 == container->m2.end())
+ sub_table_index++;
+ else
+ return;
+
+ iterator3 = container->m3.begin();
+ if (iterator3 == container->m3.end())
+ sub_table_index++;
+ else
+ return;
+
+ iterator4 = container->ms.begin();
+ }
+ }
+
+ bool operator==(const iterator_base& rhs) const {
+ if (sub_table_index != rhs.sub_table_index) return false;
+ switch (sub_table_index) {
+ case 0: {
+ return true;
+ }
+ case 1: {
+ return iterator1 == rhs.iterator1;
+ }
+ case 2: {
+ return iterator2 == rhs.iterator2;
+ }
+ case 3: {
+ return iterator3 == rhs.iterator3;
+ }
+ case 4: {
+ return iterator4 == rhs.iterator4;
+ }
+ }
+ __builtin_unreachable();
+ }
+
+ bool operator!=(const iterator_base& rhs) const { return !(*this == rhs); }
+
+ Derived& operator++() {
+ bool need_switch_to_next = false;
+ switch (sub_table_index) {
+ case 0: {
+ need_switch_to_next = true;
+ break;
+ }
+ case 1: {
+ iterator1.template operator++();
+ if (iterator1 == container->m1.end()) {
+ need_switch_to_next = true;
+ }
+ break;
+ }
+ case 2: {
+ iterator2.template operator++();
+ if (iterator2 == container->m2.end()) {
+ need_switch_to_next = true;
+ }
+ break;
+ }
+ case 3: {
+ iterator3.template operator++();
+ if (iterator3 == container->m3.end()) {
+ need_switch_to_next = true;
+ }
+ break;
+ }
+ case 4: {
+ iterator4.template operator++();
+ break;
+ }
+ }
+
+ while (need_switch_to_next) {
+ sub_table_index++;
+ need_switch_to_next = false;
+ switch (sub_table_index) {
+ case 1: {
+ iterator1 = container->m1.begin();
+ if (iterator1 == container->m1.end()) {
+ need_switch_to_next = true;
+ }
+ break;
+ }
+ case 2: {
+ iterator2 = container->m2.begin();
+ if (iterator2 == container->m2.end()) {
+ need_switch_to_next = true;
+ }
+ break;
+ }
+ case 3: {
+ iterator3 = container->m3.begin();
+ if (iterator3 == container->m3.end()) {
+ need_switch_to_next = true;
+ }
+ break;
+ }
+ case 4: {
+ iterator4 = container->ms.begin();
+ break;
+ }
+ }
+ }
+ while (need_switch_to_next)
+ ;
+
+ return static_cast<Derived&>(*this);
+ }
+
+ auto& operator*() const {
+ switch (sub_table_index) {
+ case 0: {
+ const_cast<iterator_base*>(this)->cell = *(container->m0.zero_value());
+ break;
+ }
+ case 1: {
+ const_cast<iterator_base*>(this)->cell = *iterator1;
+ break;
+ }
+ case 2: {
+ const_cast<iterator_base*>(this)->cell = *iterator2;
+ break;
+ }
+ case 3: {
+ const_cast<iterator_base*>(this)->cell = *iterator3;
+ break;
+ }
+ case 4: {
+ const_cast<iterator_base*>(this)->cell = *iterator4;
+ break;
+ }
+ }
+ return cell;
+ }
+ auto* operator->() const { return &(this->operator*()); }
+
+ auto get_ptr() const { return &(this->operator*()); }
+
+ size_t get_hash() const {
+ switch (sub_table_index) {
+ case 0: {
+ return container->m0.zero_value()->get_hash(container->m0);
+ }
+ case 1: {
+ return iterator1->get_hash(container->m1);
+ }
+ case 2: {
+ return iterator2->get_hash(container->m2);
+ }
+ case 3: {
+ return iterator3->get_hash(container->m3);
+ }
+ case 4: {
+ return iterator4->get_hash(container->ms);
+ }
+ }
+ }
+
+ size_t get_collision_chain_length() const { return 0; }
+
+ /**
+ * A hack for HashedDictionary.
+ *
+ * The problem: std-like find() returns an iterator, which has to be
+ * compared to end(). On the other hand, HashMap::find() returns
+ * LookupResult, which is compared to nullptr. HashedDictionary has to
+ * support both hash maps with the same code, hence the need for this
+ * hack.
+ *
+ * The proper way would be to remove iterator interface from our
+ * HashMap completely, change all its users to the existing internal
+ * iteration interface, and redefine end() to return LookupResult for
+ * compatibility with std find(). Unfortunately, now is not the time to
+ * do this.
+ */
+ operator Cell*() const { return nullptr; }
+ };
+
+public:
+ using Key = StringRef;
+ using key_type = Key;
+ using mapped_type = typename Ts::mapped_type;
+ using value_type = typename Ts::value_type;
+ using cell_type = typename Ts::cell_type;
+
+ using LookupResult = StringHashTableLookupResult<typename cell_type::mapped_type>;
+ using ConstLookupResult = StringHashTableLookupResult<const typename cell_type::mapped_type>;
+
+ StringHashTable() = default;
+
+ explicit StringHashTable(size_t reserve_for_num_elements)
+ : m1 {reserve_for_num_elements / 4},
+ m2 {reserve_for_num_elements / 4},
+ m3 {reserve_for_num_elements / 4},
+ ms {reserve_for_num_elements / 4} {}
+
+ StringHashTable(StringHashTable&& rhs) noexcept
+ : m1(std::move(rhs.m1)),
+ m2(std::move(rhs.m2)),
+ m3(std::move(rhs.m3)),
+ ms(std::move(rhs.ms)) {}
+
+ ~StringHashTable() = default;
+
+ // Dispatch is written in a way that maximizes the performance:
+ // 1. Always memcpy 8 times bytes
+ // 2. Use switch case extension to generate fast dispatching table
+ // 3. Funcs are named callables that can be force_inlined
+ //
+ // NOTE: It relies on Little Endianness
+ //
+ // NOTE: It requires padded to 8 bytes keys (IOW you cannot pass
+ // std::string here, but you can pass i.e. ColumnString::getDataAt()),
+ // since it copies 8 bytes at a time.
+ template <typename Self, typename KeyHolder, typename Func>
+ static auto ALWAYS_INLINE dispatch(Self& self, KeyHolder&& key_holder, Func&& func) {
+ StringHashTableHash hash;
+ const StringRef& x = key_holder_get_key(key_holder);
+ const size_t sz = x.size;
+ if (sz == 0) {
+ key_holder_get_key(key_holder);
Review Comment:
It's for empty string(length is 0)
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
[GitHub] [doris] Gabriel39 commented on a diff in pull request #10937: [improvement][agg]Import sub hash map
Posted by GitBox <gi...@apache.org>.
Gabriel39 commented on code in PR #10937:
URL: https://github.com/apache/doris/pull/10937#discussion_r922794738
##########
be/src/vec/common/hash_table/string_hash_table.h:
##########
@@ -0,0 +1,612 @@
+// 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.
+// This file is copied from
+// https://github.com/ClickHouse/ClickHouse/blob/master/src/Common/HashTable/StringHashTable.h
+// and modified by Doris
+
+#pragma once
+
+#include <new>
+#include <variant>
+
+#include "vec/common/hash_table/hash.h"
+
+using StringKey8 = doris::vectorized::UInt64;
+using StringKey16 = doris::vectorized::UInt128;
+struct StringKey24 {
+ doris::vectorized::UInt64 a;
+ doris::vectorized::UInt64 b;
+ doris::vectorized::UInt64 c;
+
+ bool operator==(const StringKey24 rhs) const { return a == rhs.a && b == rhs.b && c == rhs.c; }
+};
+
+inline StringRef ALWAYS_INLINE to_string_ref(const StringKey8& n) {
+ assert(n != 0);
+ return {reinterpret_cast<const char*>(&n), 8ul - (__builtin_clzll(n) >> 3)};
+}
+inline StringRef ALWAYS_INLINE to_string_ref(const StringKey16& n) {
+ assert(n.high != 0);
+ return {reinterpret_cast<const char*>(&n), 16ul - (__builtin_clzll(n.high) >> 3)};
+}
+inline StringRef ALWAYS_INLINE to_string_ref(const StringKey24& n) {
+ assert(n.c != 0);
+ return {reinterpret_cast<const char*>(&n), 24ul - (__builtin_clzll(n.c) >> 3)};
+}
+
+struct StringHashTableHash {
+#if defined(__SSE4_2__)
+ size_t ALWAYS_INLINE operator()(StringKey8 key) const {
+ size_t res = -1ULL;
+ res = _mm_crc32_u64(res, key);
+ return res;
+ }
+ size_t ALWAYS_INLINE operator()(StringKey16 key) const {
+ size_t res = -1ULL;
+ res = _mm_crc32_u64(res, key.low);
+ res = _mm_crc32_u64(res, key.high);
+ return res;
+ }
+ size_t ALWAYS_INLINE operator()(StringKey24 key) const {
+ size_t res = -1ULL;
+ res = _mm_crc32_u64(res, key.a);
+ res = _mm_crc32_u64(res, key.b);
+ res = _mm_crc32_u64(res, key.c);
+ return res;
+ }
+#else
+ size_t ALWAYS_INLINE operator()(StringKey8 key) const {
+ return util_hash::CityHash64(reinterpret_cast<const char*>(&key), 8);
+ }
+ size_t ALWAYS_INLINE operator()(StringKey16 key) const {
+ return util_hash::CityHash64(reinterpret_cast<const char*>(&key), 16);
+ }
+ size_t ALWAYS_INLINE operator()(StringKey24 key) const {
+ return util_hash::CityHash64(reinterpret_cast<const char*>(&key), 24);
+ }
+#endif
+ size_t ALWAYS_INLINE operator()(StringRef key) const { return StringRefHash()(key); }
+};
+
+template <typename Cell>
+struct StringHashTableEmpty //-V730
+{
+ using Self = StringHashTableEmpty;
+
+ bool _has_zero = false;
+ std::aligned_storage_t<sizeof(Cell), alignof(Cell)>
+ zero_value_storage; /// Storage of element with zero key.
+
+public:
+ bool has_zero() const { return _has_zero; }
+
+ void set_has_zero() {
+ _has_zero = true;
+ new (zero_value()) Cell();
+ }
+
+ void set_has_zero(const Cell& other) {
+ _has_zero = true;
+ new (zero_value()) Cell(other);
+ }
+
+ void clear_has_zero() {
+ _has_zero = false;
+ if (!std::is_trivially_destructible_v<Cell>) zero_value()->~Cell();
+ }
+
+ Cell* zero_value() { return std::launder(reinterpret_cast<Cell*>(&zero_value_storage)); }
+ const Cell* zero_value() const {
+ return std::launder(reinterpret_cast<const Cell*>(&zero_value_storage));
+ }
+
+ using LookupResult = Cell*;
+ using ConstLookupResult = const Cell*;
+
+ template <typename KeyHolder>
+ void ALWAYS_INLINE emplace(KeyHolder&&, LookupResult& it, bool& inserted, size_t = 0) {
+ if (!has_zero()) {
+ set_has_zero();
+ inserted = true;
+ } else
+ inserted = false;
+ it = zero_value();
+ }
+
+ template <typename Key>
+ LookupResult ALWAYS_INLINE find(const Key&, size_t = 0) {
+ return has_zero() ? zero_value() : nullptr;
+ }
+
+ template <typename Key>
+ ConstLookupResult ALWAYS_INLINE find(const Key&, size_t = 0) const {
+ return has_zero() ? zero_value() : nullptr;
+ }
+
+ size_t size() const { return has_zero() ? 1 : 0; }
+ bool empty() const { return !has_zero(); }
+ size_t get_buffer_size_in_bytes() const { return sizeof(Cell); }
+};
+
+template <size_t initial_size_degree = 8>
+struct StringHashTableGrower : public HashTableGrowerWithPrecalculation<initial_size_degree> {
+ // Smooth growing for string maps
+ void increase_size() { this->increase_size_degree(1); }
+};
+
+template <typename Mapped>
+struct StringHashTableLookupResult {
+ Mapped* mapped_ptr;
+ StringHashTableLookupResult() : mapped_ptr(nullptr) {} /// NOLINT
+ StringHashTableLookupResult(Mapped* mapped_ptr_) : mapped_ptr(mapped_ptr_) {} /// NOLINT
+ StringHashTableLookupResult(std::nullptr_t) {} /// NOLINT
+ const VoidKey getKey() const { return {}; } /// NOLINT
+ auto& get_mapped() { return *mapped_ptr; }
+ auto& operator*() { return *this; }
+ auto& operator*() const { return *this; }
+ auto* operator->() { return this; }
+ auto* operator->() const { return this; }
+ explicit operator bool() const { return mapped_ptr; }
+ friend bool operator==(const StringHashTableLookupResult& a, const std::nullptr_t&) {
+ return !a.mapped_ptr;
+ }
+ friend bool operator==(const std::nullptr_t&, const StringHashTableLookupResult& b) {
+ return !b.mapped_ptr;
+ }
+ friend bool operator!=(const StringHashTableLookupResult& a, const std::nullptr_t&) {
+ return a.mapped_ptr;
+ }
+ friend bool operator!=(const std::nullptr_t&, const StringHashTableLookupResult& b) {
+ return b.mapped_ptr;
+ }
+};
+
+template <typename Mapped>
+ALWAYS_INLINE inline auto lookup_result_get_mapped(StringHashTableLookupResult<Mapped*> cell) {
+ return &cell.get_mapped();
+}
+
+template <typename SubMaps>
+class StringHashTable : private boost::noncopyable {
+protected:
+ static constexpr size_t NUM_MAPS = 5;
+ // Map for storing empty string
+ using T0 = typename SubMaps::T0;
+
+ // Short strings are stored as numbers
+ using T1 = typename SubMaps::T1;
+ using T2 = typename SubMaps::T2;
+ using T3 = typename SubMaps::T3;
+
+ // Long strings are stored as StringRef along with saved hash
+ using Ts = typename SubMaps::Ts;
+ using Self = StringHashTable;
+
+ template <typename, typename, size_t>
+ friend class TwoLevelStringHashTable;
+
+ T0 m0;
+ T1 m1;
+ T2 m2;
+ T3 m3;
+ Ts ms;
+
+ using Cell = typename Ts::cell_type;
+
+ friend class const_iterator;
+ friend class iterator;
+
+ template <typename Derived, bool is_const>
+ class iterator_base {
+ using Container = std::conditional_t<is_const, const Self, Self>;
+
+ Container* container;
+ int sub_table_index;
+ typename T1::iterator iterator1;
+ typename T2::iterator iterator2;
+ typename T3::iterator iterator3;
+ typename Ts::iterator iterator4;
+
+ typename Ts::cell_type cell;
+
+ friend class StringHashTable;
+
+ public:
+ iterator_base() {}
+ iterator_base(Container* container_, bool end = false) : container(container_) {
+ if (end) {
+ sub_table_index = 4;
+ iterator4 = container->ms.end();
+ } else {
+ sub_table_index = 0;
+ if (container->m0.size() == 0)
+ sub_table_index++;
+ else
+ return;
+
+ iterator1 = container->m1.begin();
+ if (iterator1 == container->m1.end())
+ sub_table_index++;
+ else
+ return;
+
+ iterator2 = container->m2.begin();
+ if (iterator2 == container->m2.end())
+ sub_table_index++;
+ else
+ return;
+
+ iterator3 = container->m3.begin();
+ if (iterator3 == container->m3.end())
+ sub_table_index++;
+ else
+ return;
+
+ iterator4 = container->ms.begin();
+ }
+ }
+
+ bool operator==(const iterator_base& rhs) const {
+ if (sub_table_index != rhs.sub_table_index) return false;
+ switch (sub_table_index) {
+ case 0: {
+ return true;
+ }
+ case 1: {
+ return iterator1 == rhs.iterator1;
+ }
+ case 2: {
+ return iterator2 == rhs.iterator2;
+ }
+ case 3: {
+ return iterator3 == rhs.iterator3;
+ }
+ case 4: {
+ return iterator4 == rhs.iterator4;
+ }
+ }
+ __builtin_unreachable();
+ }
+
+ bool operator!=(const iterator_base& rhs) const { return !(*this == rhs); }
+
+ Derived& operator++() {
+ bool need_switch_to_next = false;
+ switch (sub_table_index) {
+ case 0: {
+ need_switch_to_next = true;
+ break;
+ }
+ case 1: {
+ iterator1.template operator++();
+ if (iterator1 == container->m1.end()) {
+ need_switch_to_next = true;
+ }
+ break;
+ }
+ case 2: {
+ iterator2.template operator++();
+ if (iterator2 == container->m2.end()) {
+ need_switch_to_next = true;
+ }
+ break;
+ }
+ case 3: {
+ iterator3.template operator++();
+ if (iterator3 == container->m3.end()) {
+ need_switch_to_next = true;
+ }
+ break;
+ }
+ case 4: {
+ iterator4.template operator++();
+ break;
+ }
+ }
+
+ while (need_switch_to_next) {
+ sub_table_index++;
+ need_switch_to_next = false;
+ switch (sub_table_index) {
+ case 1: {
+ iterator1 = container->m1.begin();
+ if (iterator1 == container->m1.end()) {
+ need_switch_to_next = true;
+ }
+ break;
+ }
+ case 2: {
+ iterator2 = container->m2.begin();
+ if (iterator2 == container->m2.end()) {
+ need_switch_to_next = true;
+ }
+ break;
+ }
+ case 3: {
+ iterator3 = container->m3.begin();
+ if (iterator3 == container->m3.end()) {
+ need_switch_to_next = true;
+ }
+ break;
+ }
+ case 4: {
+ iterator4 = container->ms.begin();
+ break;
+ }
+ }
+ }
+ while (need_switch_to_next)
+ ;
+
+ return static_cast<Derived&>(*this);
+ }
+
+ auto& operator*() const {
+ switch (sub_table_index) {
+ case 0: {
+ const_cast<iterator_base*>(this)->cell = *(container->m0.zero_value());
+ break;
+ }
+ case 1: {
+ const_cast<iterator_base*>(this)->cell = *iterator1;
+ break;
+ }
+ case 2: {
+ const_cast<iterator_base*>(this)->cell = *iterator2;
+ break;
+ }
+ case 3: {
+ const_cast<iterator_base*>(this)->cell = *iterator3;
+ break;
+ }
+ case 4: {
+ const_cast<iterator_base*>(this)->cell = *iterator4;
+ break;
+ }
+ }
+ return cell;
+ }
+ auto* operator->() const { return &(this->operator*()); }
+
+ auto get_ptr() const { return &(this->operator*()); }
+
+ size_t get_hash() const {
+ switch (sub_table_index) {
+ case 0: {
+ return container->m0.zero_value()->get_hash(container->m0);
+ }
+ case 1: {
+ return iterator1->get_hash(container->m1);
+ }
+ case 2: {
+ return iterator2->get_hash(container->m2);
+ }
+ case 3: {
+ return iterator3->get_hash(container->m3);
+ }
+ case 4: {
+ return iterator4->get_hash(container->ms);
+ }
+ }
+ }
+
+ size_t get_collision_chain_length() const { return 0; }
+
+ /**
+ * A hack for HashedDictionary.
+ *
+ * The problem: std-like find() returns an iterator, which has to be
+ * compared to end(). On the other hand, HashMap::find() returns
+ * LookupResult, which is compared to nullptr. HashedDictionary has to
+ * support both hash maps with the same code, hence the need for this
+ * hack.
+ *
+ * The proper way would be to remove iterator interface from our
+ * HashMap completely, change all its users to the existing internal
+ * iteration interface, and redefine end() to return LookupResult for
+ * compatibility with std find(). Unfortunately, now is not the time to
+ * do this.
+ */
+ operator Cell*() const { return nullptr; }
+ };
+
+public:
+ using Key = StringRef;
+ using key_type = Key;
+ using mapped_type = typename Ts::mapped_type;
+ using value_type = typename Ts::value_type;
+ using cell_type = typename Ts::cell_type;
+
+ using LookupResult = StringHashTableLookupResult<typename cell_type::mapped_type>;
+ using ConstLookupResult = StringHashTableLookupResult<const typename cell_type::mapped_type>;
+
+ StringHashTable() = default;
+
+ explicit StringHashTable(size_t reserve_for_num_elements)
+ : m1 {reserve_for_num_elements / 4},
+ m2 {reserve_for_num_elements / 4},
+ m3 {reserve_for_num_elements / 4},
+ ms {reserve_for_num_elements / 4} {}
+
+ StringHashTable(StringHashTable&& rhs) noexcept
+ : m1(std::move(rhs.m1)),
+ m2(std::move(rhs.m2)),
+ m3(std::move(rhs.m3)),
+ ms(std::move(rhs.ms)) {}
+
+ ~StringHashTable() = default;
+
+ // Dispatch is written in a way that maximizes the performance:
+ // 1. Always memcpy 8 times bytes
+ // 2. Use switch case extension to generate fast dispatching table
+ // 3. Funcs are named callables that can be force_inlined
+ //
+ // NOTE: It relies on Little Endianness
+ //
+ // NOTE: It requires padded to 8 bytes keys (IOW you cannot pass
+ // std::string here, but you can pass i.e. ColumnString::getDataAt()),
+ // since it copies 8 bytes at a time.
+ template <typename Self, typename KeyHolder, typename Func>
+ static auto ALWAYS_INLINE dispatch(Self& self, KeyHolder&& key_holder, Func&& func) {
+ StringHashTableHash hash;
+ const StringRef& x = key_holder_get_key(key_holder);
+ const size_t sz = x.size;
+ if (sz == 0) {
+ key_holder_get_key(key_holder);
Review Comment:
Does this line have no impact?
##########
be/src/vec/common/hash_table/string_hash_table.h:
##########
@@ -0,0 +1,612 @@
+// 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.
+// This file is copied from
+// https://github.com/ClickHouse/ClickHouse/blob/master/src/Common/HashTable/StringHashTable.h
+// and modified by Doris
+
+#pragma once
+
+#include <new>
+#include <variant>
+
+#include "vec/common/hash_table/hash.h"
+
+using StringKey8 = doris::vectorized::UInt64;
+using StringKey16 = doris::vectorized::UInt128;
+struct StringKey24 {
+ doris::vectorized::UInt64 a;
+ doris::vectorized::UInt64 b;
+ doris::vectorized::UInt64 c;
+
+ bool operator==(const StringKey24 rhs) const { return a == rhs.a && b == rhs.b && c == rhs.c; }
+};
+
+inline StringRef ALWAYS_INLINE to_string_ref(const StringKey8& n) {
+ assert(n != 0);
+ return {reinterpret_cast<const char*>(&n), 8ul - (__builtin_clzll(n) >> 3)};
+}
+inline StringRef ALWAYS_INLINE to_string_ref(const StringKey16& n) {
+ assert(n.high != 0);
+ return {reinterpret_cast<const char*>(&n), 16ul - (__builtin_clzll(n.high) >> 3)};
+}
+inline StringRef ALWAYS_INLINE to_string_ref(const StringKey24& n) {
+ assert(n.c != 0);
+ return {reinterpret_cast<const char*>(&n), 24ul - (__builtin_clzll(n.c) >> 3)};
+}
+
+struct StringHashTableHash {
+#if defined(__SSE4_2__)
+ size_t ALWAYS_INLINE operator()(StringKey8 key) const {
+ size_t res = -1ULL;
+ res = _mm_crc32_u64(res, key);
+ return res;
+ }
+ size_t ALWAYS_INLINE operator()(StringKey16 key) const {
+ size_t res = -1ULL;
+ res = _mm_crc32_u64(res, key.low);
+ res = _mm_crc32_u64(res, key.high);
+ return res;
+ }
+ size_t ALWAYS_INLINE operator()(StringKey24 key) const {
+ size_t res = -1ULL;
+ res = _mm_crc32_u64(res, key.a);
+ res = _mm_crc32_u64(res, key.b);
+ res = _mm_crc32_u64(res, key.c);
+ return res;
+ }
+#else
+ size_t ALWAYS_INLINE operator()(StringKey8 key) const {
+ return util_hash::CityHash64(reinterpret_cast<const char*>(&key), 8);
+ }
+ size_t ALWAYS_INLINE operator()(StringKey16 key) const {
+ return util_hash::CityHash64(reinterpret_cast<const char*>(&key), 16);
+ }
+ size_t ALWAYS_INLINE operator()(StringKey24 key) const {
+ return util_hash::CityHash64(reinterpret_cast<const char*>(&key), 24);
+ }
+#endif
+ size_t ALWAYS_INLINE operator()(StringRef key) const { return StringRefHash()(key); }
+};
+
+template <typename Cell>
+struct StringHashTableEmpty //-V730
+{
+ using Self = StringHashTableEmpty;
+
+ bool _has_zero = false;
+ std::aligned_storage_t<sizeof(Cell), alignof(Cell)>
+ zero_value_storage; /// Storage of element with zero key.
+
+public:
+ bool has_zero() const { return _has_zero; }
+
+ void set_has_zero() {
+ _has_zero = true;
+ new (zero_value()) Cell();
+ }
+
+ void set_has_zero(const Cell& other) {
+ _has_zero = true;
+ new (zero_value()) Cell(other);
+ }
+
+ void clear_has_zero() {
+ _has_zero = false;
+ if (!std::is_trivially_destructible_v<Cell>) zero_value()->~Cell();
+ }
+
+ Cell* zero_value() { return std::launder(reinterpret_cast<Cell*>(&zero_value_storage)); }
+ const Cell* zero_value() const {
+ return std::launder(reinterpret_cast<const Cell*>(&zero_value_storage));
+ }
+
+ using LookupResult = Cell*;
+ using ConstLookupResult = const Cell*;
+
+ template <typename KeyHolder>
+ void ALWAYS_INLINE emplace(KeyHolder&&, LookupResult& it, bool& inserted, size_t = 0) {
+ if (!has_zero()) {
+ set_has_zero();
+ inserted = true;
+ } else
+ inserted = false;
+ it = zero_value();
+ }
+
+ template <typename Key>
+ LookupResult ALWAYS_INLINE find(const Key&, size_t = 0) {
+ return has_zero() ? zero_value() : nullptr;
+ }
+
+ template <typename Key>
+ ConstLookupResult ALWAYS_INLINE find(const Key&, size_t = 0) const {
+ return has_zero() ? zero_value() : nullptr;
+ }
+
+ size_t size() const { return has_zero() ? 1 : 0; }
+ bool empty() const { return !has_zero(); }
+ size_t get_buffer_size_in_bytes() const { return sizeof(Cell); }
+};
+
+template <size_t initial_size_degree = 8>
+struct StringHashTableGrower : public HashTableGrowerWithPrecalculation<initial_size_degree> {
+ // Smooth growing for string maps
+ void increase_size() { this->increase_size_degree(1); }
+};
+
+template <typename Mapped>
+struct StringHashTableLookupResult {
+ Mapped* mapped_ptr;
+ StringHashTableLookupResult() : mapped_ptr(nullptr) {} /// NOLINT
+ StringHashTableLookupResult(Mapped* mapped_ptr_) : mapped_ptr(mapped_ptr_) {} /// NOLINT
+ StringHashTableLookupResult(std::nullptr_t) {} /// NOLINT
+ const VoidKey getKey() const { return {}; } /// NOLINT
+ auto& get_mapped() { return *mapped_ptr; }
+ auto& operator*() { return *this; }
+ auto& operator*() const { return *this; }
+ auto* operator->() { return this; }
+ auto* operator->() const { return this; }
+ explicit operator bool() const { return mapped_ptr; }
+ friend bool operator==(const StringHashTableLookupResult& a, const std::nullptr_t&) {
+ return !a.mapped_ptr;
+ }
+ friend bool operator==(const std::nullptr_t&, const StringHashTableLookupResult& b) {
+ return !b.mapped_ptr;
+ }
+ friend bool operator!=(const StringHashTableLookupResult& a, const std::nullptr_t&) {
+ return a.mapped_ptr;
+ }
+ friend bool operator!=(const std::nullptr_t&, const StringHashTableLookupResult& b) {
+ return b.mapped_ptr;
+ }
+};
+
+template <typename Mapped>
+ALWAYS_INLINE inline auto lookup_result_get_mapped(StringHashTableLookupResult<Mapped*> cell) {
+ return &cell.get_mapped();
+}
+
+template <typename SubMaps>
+class StringHashTable : private boost::noncopyable {
+protected:
+ static constexpr size_t NUM_MAPS = 5;
+ // Map for storing empty string
+ using T0 = typename SubMaps::T0;
+
+ // Short strings are stored as numbers
+ using T1 = typename SubMaps::T1;
+ using T2 = typename SubMaps::T2;
+ using T3 = typename SubMaps::T3;
+
+ // Long strings are stored as StringRef along with saved hash
+ using Ts = typename SubMaps::Ts;
+ using Self = StringHashTable;
+
+ template <typename, typename, size_t>
+ friend class TwoLevelStringHashTable;
+
+ T0 m0;
+ T1 m1;
+ T2 m2;
+ T3 m3;
+ Ts ms;
+
+ using Cell = typename Ts::cell_type;
+
+ friend class const_iterator;
+ friend class iterator;
+
+ template <typename Derived, bool is_const>
+ class iterator_base {
+ using Container = std::conditional_t<is_const, const Self, Self>;
+
+ Container* container;
+ int sub_table_index;
+ typename T1::iterator iterator1;
+ typename T2::iterator iterator2;
+ typename T3::iterator iterator3;
+ typename Ts::iterator iterator4;
+
+ typename Ts::cell_type cell;
+
+ friend class StringHashTable;
+
+ public:
+ iterator_base() {}
+ iterator_base(Container* container_, bool end = false) : container(container_) {
+ if (end) {
+ sub_table_index = 4;
+ iterator4 = container->ms.end();
+ } else {
+ sub_table_index = 0;
+ if (container->m0.size() == 0)
+ sub_table_index++;
+ else
+ return;
+
+ iterator1 = container->m1.begin();
+ if (iterator1 == container->m1.end())
+ sub_table_index++;
+ else
+ return;
+
+ iterator2 = container->m2.begin();
+ if (iterator2 == container->m2.end())
+ sub_table_index++;
+ else
+ return;
+
+ iterator3 = container->m3.begin();
+ if (iterator3 == container->m3.end())
+ sub_table_index++;
+ else
+ return;
+
+ iterator4 = container->ms.begin();
+ }
+ }
+
+ bool operator==(const iterator_base& rhs) const {
+ if (sub_table_index != rhs.sub_table_index) return false;
+ switch (sub_table_index) {
+ case 0: {
+ return true;
+ }
+ case 1: {
+ return iterator1 == rhs.iterator1;
+ }
+ case 2: {
+ return iterator2 == rhs.iterator2;
+ }
+ case 3: {
+ return iterator3 == rhs.iterator3;
+ }
+ case 4: {
+ return iterator4 == rhs.iterator4;
+ }
+ }
+ __builtin_unreachable();
+ }
+
+ bool operator!=(const iterator_base& rhs) const { return !(*this == rhs); }
+
+ Derived& operator++() {
+ bool need_switch_to_next = false;
+ switch (sub_table_index) {
+ case 0: {
+ need_switch_to_next = true;
+ break;
+ }
+ case 1: {
+ iterator1.template operator++();
+ if (iterator1 == container->m1.end()) {
+ need_switch_to_next = true;
+ }
+ break;
+ }
+ case 2: {
+ iterator2.template operator++();
+ if (iterator2 == container->m2.end()) {
+ need_switch_to_next = true;
+ }
+ break;
+ }
+ case 3: {
+ iterator3.template operator++();
+ if (iterator3 == container->m3.end()) {
+ need_switch_to_next = true;
+ }
+ break;
+ }
+ case 4: {
+ iterator4.template operator++();
+ break;
+ }
+ }
+
+ while (need_switch_to_next) {
+ sub_table_index++;
+ need_switch_to_next = false;
+ switch (sub_table_index) {
+ case 1: {
+ iterator1 = container->m1.begin();
+ if (iterator1 == container->m1.end()) {
+ need_switch_to_next = true;
+ }
+ break;
+ }
+ case 2: {
+ iterator2 = container->m2.begin();
+ if (iterator2 == container->m2.end()) {
+ need_switch_to_next = true;
+ }
+ break;
+ }
+ case 3: {
+ iterator3 = container->m3.begin();
+ if (iterator3 == container->m3.end()) {
+ need_switch_to_next = true;
+ }
+ break;
+ }
+ case 4: {
+ iterator4 = container->ms.begin();
+ break;
+ }
+ }
+ }
+ while (need_switch_to_next)
+ ;
+
+ return static_cast<Derived&>(*this);
+ }
+
+ auto& operator*() const {
+ switch (sub_table_index) {
+ case 0: {
+ const_cast<iterator_base*>(this)->cell = *(container->m0.zero_value());
+ break;
+ }
+ case 1: {
+ const_cast<iterator_base*>(this)->cell = *iterator1;
+ break;
+ }
+ case 2: {
+ const_cast<iterator_base*>(this)->cell = *iterator2;
+ break;
+ }
+ case 3: {
+ const_cast<iterator_base*>(this)->cell = *iterator3;
+ break;
+ }
+ case 4: {
+ const_cast<iterator_base*>(this)->cell = *iterator4;
+ break;
+ }
+ }
+ return cell;
+ }
+ auto* operator->() const { return &(this->operator*()); }
+
+ auto get_ptr() const { return &(this->operator*()); }
+
+ size_t get_hash() const {
+ switch (sub_table_index) {
+ case 0: {
+ return container->m0.zero_value()->get_hash(container->m0);
+ }
+ case 1: {
+ return iterator1->get_hash(container->m1);
+ }
+ case 2: {
+ return iterator2->get_hash(container->m2);
+ }
+ case 3: {
+ return iterator3->get_hash(container->m3);
+ }
+ case 4: {
+ return iterator4->get_hash(container->ms);
+ }
+ }
+ }
+
+ size_t get_collision_chain_length() const { return 0; }
+
+ /**
+ * A hack for HashedDictionary.
+ *
+ * The problem: std-like find() returns an iterator, which has to be
+ * compared to end(). On the other hand, HashMap::find() returns
+ * LookupResult, which is compared to nullptr. HashedDictionary has to
+ * support both hash maps with the same code, hence the need for this
+ * hack.
+ *
+ * The proper way would be to remove iterator interface from our
+ * HashMap completely, change all its users to the existing internal
+ * iteration interface, and redefine end() to return LookupResult for
+ * compatibility with std find(). Unfortunately, now is not the time to
+ * do this.
+ */
+ operator Cell*() const { return nullptr; }
+ };
+
+public:
+ using Key = StringRef;
+ using key_type = Key;
+ using mapped_type = typename Ts::mapped_type;
+ using value_type = typename Ts::value_type;
+ using cell_type = typename Ts::cell_type;
+
+ using LookupResult = StringHashTableLookupResult<typename cell_type::mapped_type>;
+ using ConstLookupResult = StringHashTableLookupResult<const typename cell_type::mapped_type>;
+
+ StringHashTable() = default;
+
+ explicit StringHashTable(size_t reserve_for_num_elements)
+ : m1 {reserve_for_num_elements / 4},
+ m2 {reserve_for_num_elements / 4},
+ m3 {reserve_for_num_elements / 4},
+ ms {reserve_for_num_elements / 4} {}
+
+ StringHashTable(StringHashTable&& rhs) noexcept
+ : m1(std::move(rhs.m1)),
+ m2(std::move(rhs.m2)),
+ m3(std::move(rhs.m3)),
+ ms(std::move(rhs.ms)) {}
+
+ ~StringHashTable() = default;
+
+ // Dispatch is written in a way that maximizes the performance:
+ // 1. Always memcpy 8 times bytes
+ // 2. Use switch case extension to generate fast dispatching table
+ // 3. Funcs are named callables that can be force_inlined
+ //
+ // NOTE: It relies on Little Endianness
+ //
+ // NOTE: It requires padded to 8 bytes keys (IOW you cannot pass
+ // std::string here, but you can pass i.e. ColumnString::getDataAt()),
+ // since it copies 8 bytes at a time.
+ template <typename Self, typename KeyHolder, typename Func>
+ static auto ALWAYS_INLINE dispatch(Self& self, KeyHolder&& key_holder, Func&& func) {
+ StringHashTableHash hash;
+ const StringRef& x = key_holder_get_key(key_holder);
+ const size_t sz = x.size;
+ if (sz == 0) {
+ key_holder_get_key(key_holder);
+ return func(self.m0, VoidKey {}, 0);
+ }
+
+ if (x.data[sz - 1] == 0) {
+ // Strings with trailing zeros are not representable as fixed-size
+ // string keys. Put them to the generic table.
+ return func(self.ms, std::forward<KeyHolder>(key_holder), hash(x));
Review Comment:
Why strings with trailing zeros are not applicable for this optimization?
##########
be/src/vec/common/hash_table/string_hash_table.h:
##########
@@ -0,0 +1,612 @@
+// 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.
+// This file is copied from
+// https://github.com/ClickHouse/ClickHouse/blob/master/src/Common/HashTable/StringHashTable.h
+// and modified by Doris
+
+#pragma once
+
+#include <new>
+#include <variant>
+
+#include "vec/common/hash_table/hash.h"
+
+using StringKey8 = doris::vectorized::UInt64;
+using StringKey16 = doris::vectorized::UInt128;
+struct StringKey24 {
+ doris::vectorized::UInt64 a;
+ doris::vectorized::UInt64 b;
+ doris::vectorized::UInt64 c;
+
+ bool operator==(const StringKey24 rhs) const { return a == rhs.a && b == rhs.b && c == rhs.c; }
+};
+
+inline StringRef ALWAYS_INLINE to_string_ref(const StringKey8& n) {
+ assert(n != 0);
+ return {reinterpret_cast<const char*>(&n), 8ul - (__builtin_clzll(n) >> 3)};
+}
+inline StringRef ALWAYS_INLINE to_string_ref(const StringKey16& n) {
+ assert(n.high != 0);
+ return {reinterpret_cast<const char*>(&n), 16ul - (__builtin_clzll(n.high) >> 3)};
+}
+inline StringRef ALWAYS_INLINE to_string_ref(const StringKey24& n) {
+ assert(n.c != 0);
+ return {reinterpret_cast<const char*>(&n), 24ul - (__builtin_clzll(n.c) >> 3)};
+}
+
+struct StringHashTableHash {
+#if defined(__SSE4_2__)
+ size_t ALWAYS_INLINE operator()(StringKey8 key) const {
+ size_t res = -1ULL;
+ res = _mm_crc32_u64(res, key);
+ return res;
+ }
+ size_t ALWAYS_INLINE operator()(StringKey16 key) const {
+ size_t res = -1ULL;
+ res = _mm_crc32_u64(res, key.low);
+ res = _mm_crc32_u64(res, key.high);
+ return res;
+ }
+ size_t ALWAYS_INLINE operator()(StringKey24 key) const {
+ size_t res = -1ULL;
+ res = _mm_crc32_u64(res, key.a);
+ res = _mm_crc32_u64(res, key.b);
+ res = _mm_crc32_u64(res, key.c);
+ return res;
+ }
+#else
+ size_t ALWAYS_INLINE operator()(StringKey8 key) const {
+ return util_hash::CityHash64(reinterpret_cast<const char*>(&key), 8);
+ }
+ size_t ALWAYS_INLINE operator()(StringKey16 key) const {
+ return util_hash::CityHash64(reinterpret_cast<const char*>(&key), 16);
+ }
+ size_t ALWAYS_INLINE operator()(StringKey24 key) const {
+ return util_hash::CityHash64(reinterpret_cast<const char*>(&key), 24);
+ }
+#endif
+ size_t ALWAYS_INLINE operator()(StringRef key) const { return StringRefHash()(key); }
+};
+
+template <typename Cell>
+struct StringHashTableEmpty //-V730
+{
+ using Self = StringHashTableEmpty;
+
+ bool _has_zero = false;
+ std::aligned_storage_t<sizeof(Cell), alignof(Cell)>
+ zero_value_storage; /// Storage of element with zero key.
+
+public:
+ bool has_zero() const { return _has_zero; }
+
+ void set_has_zero() {
+ _has_zero = true;
+ new (zero_value()) Cell();
+ }
+
+ void set_has_zero(const Cell& other) {
+ _has_zero = true;
+ new (zero_value()) Cell(other);
+ }
+
+ void clear_has_zero() {
+ _has_zero = false;
+ if (!std::is_trivially_destructible_v<Cell>) zero_value()->~Cell();
+ }
+
+ Cell* zero_value() { return std::launder(reinterpret_cast<Cell*>(&zero_value_storage)); }
+ const Cell* zero_value() const {
+ return std::launder(reinterpret_cast<const Cell*>(&zero_value_storage));
+ }
+
+ using LookupResult = Cell*;
+ using ConstLookupResult = const Cell*;
+
+ template <typename KeyHolder>
+ void ALWAYS_INLINE emplace(KeyHolder&&, LookupResult& it, bool& inserted, size_t = 0) {
+ if (!has_zero()) {
+ set_has_zero();
+ inserted = true;
+ } else
+ inserted = false;
+ it = zero_value();
+ }
+
+ template <typename Key>
+ LookupResult ALWAYS_INLINE find(const Key&, size_t = 0) {
+ return has_zero() ? zero_value() : nullptr;
+ }
+
+ template <typename Key>
+ ConstLookupResult ALWAYS_INLINE find(const Key&, size_t = 0) const {
+ return has_zero() ? zero_value() : nullptr;
+ }
+
+ size_t size() const { return has_zero() ? 1 : 0; }
+ bool empty() const { return !has_zero(); }
+ size_t get_buffer_size_in_bytes() const { return sizeof(Cell); }
+};
+
+template <size_t initial_size_degree = 8>
+struct StringHashTableGrower : public HashTableGrowerWithPrecalculation<initial_size_degree> {
+ // Smooth growing for string maps
+ void increase_size() { this->increase_size_degree(1); }
+};
+
+template <typename Mapped>
+struct StringHashTableLookupResult {
+ Mapped* mapped_ptr;
+ StringHashTableLookupResult() : mapped_ptr(nullptr) {} /// NOLINT
+ StringHashTableLookupResult(Mapped* mapped_ptr_) : mapped_ptr(mapped_ptr_) {} /// NOLINT
+ StringHashTableLookupResult(std::nullptr_t) {} /// NOLINT
+ const VoidKey getKey() const { return {}; } /// NOLINT
+ auto& get_mapped() { return *mapped_ptr; }
+ auto& operator*() { return *this; }
+ auto& operator*() const { return *this; }
+ auto* operator->() { return this; }
+ auto* operator->() const { return this; }
+ explicit operator bool() const { return mapped_ptr; }
+ friend bool operator==(const StringHashTableLookupResult& a, const std::nullptr_t&) {
+ return !a.mapped_ptr;
+ }
+ friend bool operator==(const std::nullptr_t&, const StringHashTableLookupResult& b) {
+ return !b.mapped_ptr;
+ }
+ friend bool operator!=(const StringHashTableLookupResult& a, const std::nullptr_t&) {
+ return a.mapped_ptr;
+ }
+ friend bool operator!=(const std::nullptr_t&, const StringHashTableLookupResult& b) {
+ return b.mapped_ptr;
+ }
+};
+
+template <typename Mapped>
+ALWAYS_INLINE inline auto lookup_result_get_mapped(StringHashTableLookupResult<Mapped*> cell) {
+ return &cell.get_mapped();
+}
+
+template <typename SubMaps>
+class StringHashTable : private boost::noncopyable {
+protected:
+ static constexpr size_t NUM_MAPS = 5;
+ // Map for storing empty string
+ using T0 = typename SubMaps::T0;
+
+ // Short strings are stored as numbers
+ using T1 = typename SubMaps::T1;
+ using T2 = typename SubMaps::T2;
+ using T3 = typename SubMaps::T3;
+
+ // Long strings are stored as StringRef along with saved hash
+ using Ts = typename SubMaps::Ts;
+ using Self = StringHashTable;
+
+ template <typename, typename, size_t>
+ friend class TwoLevelStringHashTable;
+
+ T0 m0;
+ T1 m1;
+ T2 m2;
+ T3 m3;
+ Ts ms;
+
+ using Cell = typename Ts::cell_type;
+
+ friend class const_iterator;
+ friend class iterator;
+
+ template <typename Derived, bool is_const>
+ class iterator_base {
+ using Container = std::conditional_t<is_const, const Self, Self>;
+
+ Container* container;
+ int sub_table_index;
+ typename T1::iterator iterator1;
+ typename T2::iterator iterator2;
+ typename T3::iterator iterator3;
+ typename Ts::iterator iterator4;
+
+ typename Ts::cell_type cell;
+
+ friend class StringHashTable;
+
+ public:
+ iterator_base() {}
+ iterator_base(Container* container_, bool end = false) : container(container_) {
+ if (end) {
+ sub_table_index = 4;
+ iterator4 = container->ms.end();
+ } else {
+ sub_table_index = 0;
+ if (container->m0.size() == 0)
+ sub_table_index++;
+ else
+ return;
+
+ iterator1 = container->m1.begin();
+ if (iterator1 == container->m1.end())
+ sub_table_index++;
+ else
+ return;
+
+ iterator2 = container->m2.begin();
+ if (iterator2 == container->m2.end())
+ sub_table_index++;
+ else
+ return;
+
+ iterator3 = container->m3.begin();
+ if (iterator3 == container->m3.end())
+ sub_table_index++;
+ else
+ return;
+
+ iterator4 = container->ms.begin();
+ }
+ }
+
+ bool operator==(const iterator_base& rhs) const {
+ if (sub_table_index != rhs.sub_table_index) return false;
+ switch (sub_table_index) {
+ case 0: {
+ return true;
+ }
+ case 1: {
+ return iterator1 == rhs.iterator1;
+ }
+ case 2: {
+ return iterator2 == rhs.iterator2;
+ }
+ case 3: {
+ return iterator3 == rhs.iterator3;
+ }
+ case 4: {
+ return iterator4 == rhs.iterator4;
+ }
+ }
+ __builtin_unreachable();
+ }
+
+ bool operator!=(const iterator_base& rhs) const { return !(*this == rhs); }
+
+ Derived& operator++() {
+ bool need_switch_to_next = false;
+ switch (sub_table_index) {
+ case 0: {
+ need_switch_to_next = true;
+ break;
+ }
+ case 1: {
+ iterator1.template operator++();
+ if (iterator1 == container->m1.end()) {
+ need_switch_to_next = true;
+ }
+ break;
+ }
+ case 2: {
+ iterator2.template operator++();
+ if (iterator2 == container->m2.end()) {
+ need_switch_to_next = true;
+ }
+ break;
+ }
+ case 3: {
+ iterator3.template operator++();
+ if (iterator3 == container->m3.end()) {
+ need_switch_to_next = true;
+ }
+ break;
+ }
+ case 4: {
+ iterator4.template operator++();
+ break;
+ }
+ }
+
+ while (need_switch_to_next) {
+ sub_table_index++;
+ need_switch_to_next = false;
+ switch (sub_table_index) {
+ case 1: {
+ iterator1 = container->m1.begin();
+ if (iterator1 == container->m1.end()) {
+ need_switch_to_next = true;
+ }
+ break;
+ }
+ case 2: {
+ iterator2 = container->m2.begin();
+ if (iterator2 == container->m2.end()) {
+ need_switch_to_next = true;
+ }
+ break;
+ }
+ case 3: {
+ iterator3 = container->m3.begin();
+ if (iterator3 == container->m3.end()) {
+ need_switch_to_next = true;
+ }
+ break;
+ }
+ case 4: {
+ iterator4 = container->ms.begin();
+ break;
+ }
+ }
+ }
+ while (need_switch_to_next)
+ ;
+
+ return static_cast<Derived&>(*this);
+ }
+
+ auto& operator*() const {
+ switch (sub_table_index) {
+ case 0: {
+ const_cast<iterator_base*>(this)->cell = *(container->m0.zero_value());
+ break;
+ }
+ case 1: {
+ const_cast<iterator_base*>(this)->cell = *iterator1;
+ break;
+ }
+ case 2: {
+ const_cast<iterator_base*>(this)->cell = *iterator2;
+ break;
+ }
+ case 3: {
+ const_cast<iterator_base*>(this)->cell = *iterator3;
+ break;
+ }
+ case 4: {
+ const_cast<iterator_base*>(this)->cell = *iterator4;
+ break;
+ }
+ }
+ return cell;
+ }
+ auto* operator->() const { return &(this->operator*()); }
+
+ auto get_ptr() const { return &(this->operator*()); }
+
+ size_t get_hash() const {
+ switch (sub_table_index) {
+ case 0: {
+ return container->m0.zero_value()->get_hash(container->m0);
+ }
+ case 1: {
+ return iterator1->get_hash(container->m1);
+ }
+ case 2: {
+ return iterator2->get_hash(container->m2);
+ }
+ case 3: {
+ return iterator3->get_hash(container->m3);
+ }
+ case 4: {
+ return iterator4->get_hash(container->ms);
+ }
+ }
+ }
+
+ size_t get_collision_chain_length() const { return 0; }
+
+ /**
+ * A hack for HashedDictionary.
+ *
+ * The problem: std-like find() returns an iterator, which has to be
+ * compared to end(). On the other hand, HashMap::find() returns
+ * LookupResult, which is compared to nullptr. HashedDictionary has to
+ * support both hash maps with the same code, hence the need for this
+ * hack.
+ *
+ * The proper way would be to remove iterator interface from our
+ * HashMap completely, change all its users to the existing internal
+ * iteration interface, and redefine end() to return LookupResult for
+ * compatibility with std find(). Unfortunately, now is not the time to
+ * do this.
+ */
+ operator Cell*() const { return nullptr; }
+ };
+
+public:
+ using Key = StringRef;
+ using key_type = Key;
+ using mapped_type = typename Ts::mapped_type;
+ using value_type = typename Ts::value_type;
+ using cell_type = typename Ts::cell_type;
+
+ using LookupResult = StringHashTableLookupResult<typename cell_type::mapped_type>;
+ using ConstLookupResult = StringHashTableLookupResult<const typename cell_type::mapped_type>;
+
+ StringHashTable() = default;
+
+ explicit StringHashTable(size_t reserve_for_num_elements)
+ : m1 {reserve_for_num_elements / 4},
+ m2 {reserve_for_num_elements / 4},
+ m3 {reserve_for_num_elements / 4},
+ ms {reserve_for_num_elements / 4} {}
+
+ StringHashTable(StringHashTable&& rhs) noexcept
+ : m1(std::move(rhs.m1)),
+ m2(std::move(rhs.m2)),
+ m3(std::move(rhs.m3)),
+ ms(std::move(rhs.ms)) {}
+
+ ~StringHashTable() = default;
+
+ // Dispatch is written in a way that maximizes the performance:
+ // 1. Always memcpy 8 times bytes
+ // 2. Use switch case extension to generate fast dispatching table
+ // 3. Funcs are named callables that can be force_inlined
+ //
+ // NOTE: It relies on Little Endianness
+ //
+ // NOTE: It requires padded to 8 bytes keys (IOW you cannot pass
+ // std::string here, but you can pass i.e. ColumnString::getDataAt()),
+ // since it copies 8 bytes at a time.
+ template <typename Self, typename KeyHolder, typename Func>
+ static auto ALWAYS_INLINE dispatch(Self& self, KeyHolder&& key_holder, Func&& func) {
+ StringHashTableHash hash;
+ const StringRef& x = key_holder_get_key(key_holder);
+ const size_t sz = x.size;
+ if (sz == 0) {
+ key_holder_get_key(key_holder);
+ return func(self.m0, VoidKey {}, 0);
+ }
+
+ if (x.data[sz - 1] == 0) {
+ // Strings with trailing zeros are not representable as fixed-size
+ // string keys. Put them to the generic table.
+ return func(self.ms, std::forward<KeyHolder>(key_holder), hash(x));
+ }
+
+ const char* p = x.data;
+ // pending bits that needs to be shifted out
+ const char s = (-sz & 7) * 8;
+ union {
+ StringKey8 k8;
+ StringKey16 k16;
+ StringKey24 k24;
+ doris::vectorized::UInt64 n[3];
+ };
+ switch ((sz - 1) >> 3) {
+ case 0: // 1..8 bytes
+ {
+ // first half page
Review Comment:
what's difference for different half page?
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
[GitHub] [doris] yiguolei merged pull request #10937: [improvement][agg]Import sub hash map
Posted by GitBox <gi...@apache.org>.
yiguolei merged PR #10937:
URL: https://github.com/apache/doris/pull/10937
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
[GitHub] [doris] mrhhsg commented on a diff in pull request #10937: [improvement][agg]Import sub hash map
Posted by GitBox <gi...@apache.org>.
mrhhsg commented on code in PR #10937:
URL: https://github.com/apache/doris/pull/10937#discussion_r922852800
##########
be/src/vec/common/hash_table/string_hash_table.h:
##########
@@ -0,0 +1,612 @@
+// 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.
+// This file is copied from
+// https://github.com/ClickHouse/ClickHouse/blob/master/src/Common/HashTable/StringHashTable.h
+// and modified by Doris
+
+#pragma once
+
+#include <new>
+#include <variant>
+
+#include "vec/common/hash_table/hash.h"
+
+using StringKey8 = doris::vectorized::UInt64;
+using StringKey16 = doris::vectorized::UInt128;
+struct StringKey24 {
+ doris::vectorized::UInt64 a;
+ doris::vectorized::UInt64 b;
+ doris::vectorized::UInt64 c;
+
+ bool operator==(const StringKey24 rhs) const { return a == rhs.a && b == rhs.b && c == rhs.c; }
+};
+
+inline StringRef ALWAYS_INLINE to_string_ref(const StringKey8& n) {
+ assert(n != 0);
+ return {reinterpret_cast<const char*>(&n), 8ul - (__builtin_clzll(n) >> 3)};
+}
+inline StringRef ALWAYS_INLINE to_string_ref(const StringKey16& n) {
+ assert(n.high != 0);
+ return {reinterpret_cast<const char*>(&n), 16ul - (__builtin_clzll(n.high) >> 3)};
+}
+inline StringRef ALWAYS_INLINE to_string_ref(const StringKey24& n) {
+ assert(n.c != 0);
+ return {reinterpret_cast<const char*>(&n), 24ul - (__builtin_clzll(n.c) >> 3)};
+}
+
+struct StringHashTableHash {
+#if defined(__SSE4_2__)
+ size_t ALWAYS_INLINE operator()(StringKey8 key) const {
+ size_t res = -1ULL;
+ res = _mm_crc32_u64(res, key);
+ return res;
+ }
+ size_t ALWAYS_INLINE operator()(StringKey16 key) const {
+ size_t res = -1ULL;
+ res = _mm_crc32_u64(res, key.low);
+ res = _mm_crc32_u64(res, key.high);
+ return res;
+ }
+ size_t ALWAYS_INLINE operator()(StringKey24 key) const {
+ size_t res = -1ULL;
+ res = _mm_crc32_u64(res, key.a);
+ res = _mm_crc32_u64(res, key.b);
+ res = _mm_crc32_u64(res, key.c);
+ return res;
+ }
+#else
+ size_t ALWAYS_INLINE operator()(StringKey8 key) const {
+ return util_hash::CityHash64(reinterpret_cast<const char*>(&key), 8);
+ }
+ size_t ALWAYS_INLINE operator()(StringKey16 key) const {
+ return util_hash::CityHash64(reinterpret_cast<const char*>(&key), 16);
+ }
+ size_t ALWAYS_INLINE operator()(StringKey24 key) const {
+ return util_hash::CityHash64(reinterpret_cast<const char*>(&key), 24);
+ }
+#endif
+ size_t ALWAYS_INLINE operator()(StringRef key) const { return StringRefHash()(key); }
+};
+
+template <typename Cell>
+struct StringHashTableEmpty //-V730
+{
+ using Self = StringHashTableEmpty;
+
+ bool _has_zero = false;
+ std::aligned_storage_t<sizeof(Cell), alignof(Cell)>
+ zero_value_storage; /// Storage of element with zero key.
+
+public:
+ bool has_zero() const { return _has_zero; }
+
+ void set_has_zero() {
+ _has_zero = true;
+ new (zero_value()) Cell();
+ }
+
+ void set_has_zero(const Cell& other) {
+ _has_zero = true;
+ new (zero_value()) Cell(other);
+ }
+
+ void clear_has_zero() {
+ _has_zero = false;
+ if (!std::is_trivially_destructible_v<Cell>) zero_value()->~Cell();
+ }
+
+ Cell* zero_value() { return std::launder(reinterpret_cast<Cell*>(&zero_value_storage)); }
+ const Cell* zero_value() const {
+ return std::launder(reinterpret_cast<const Cell*>(&zero_value_storage));
+ }
+
+ using LookupResult = Cell*;
+ using ConstLookupResult = const Cell*;
+
+ template <typename KeyHolder>
+ void ALWAYS_INLINE emplace(KeyHolder&&, LookupResult& it, bool& inserted, size_t = 0) {
+ if (!has_zero()) {
+ set_has_zero();
+ inserted = true;
+ } else
+ inserted = false;
+ it = zero_value();
+ }
+
+ template <typename Key>
+ LookupResult ALWAYS_INLINE find(const Key&, size_t = 0) {
+ return has_zero() ? zero_value() : nullptr;
+ }
+
+ template <typename Key>
+ ConstLookupResult ALWAYS_INLINE find(const Key&, size_t = 0) const {
+ return has_zero() ? zero_value() : nullptr;
+ }
+
+ size_t size() const { return has_zero() ? 1 : 0; }
+ bool empty() const { return !has_zero(); }
+ size_t get_buffer_size_in_bytes() const { return sizeof(Cell); }
+};
+
+template <size_t initial_size_degree = 8>
+struct StringHashTableGrower : public HashTableGrowerWithPrecalculation<initial_size_degree> {
+ // Smooth growing for string maps
+ void increase_size() { this->increase_size_degree(1); }
+};
+
+template <typename Mapped>
+struct StringHashTableLookupResult {
+ Mapped* mapped_ptr;
+ StringHashTableLookupResult() : mapped_ptr(nullptr) {} /// NOLINT
+ StringHashTableLookupResult(Mapped* mapped_ptr_) : mapped_ptr(mapped_ptr_) {} /// NOLINT
+ StringHashTableLookupResult(std::nullptr_t) {} /// NOLINT
+ const VoidKey getKey() const { return {}; } /// NOLINT
+ auto& get_mapped() { return *mapped_ptr; }
+ auto& operator*() { return *this; }
+ auto& operator*() const { return *this; }
+ auto* operator->() { return this; }
+ auto* operator->() const { return this; }
+ explicit operator bool() const { return mapped_ptr; }
+ friend bool operator==(const StringHashTableLookupResult& a, const std::nullptr_t&) {
+ return !a.mapped_ptr;
+ }
+ friend bool operator==(const std::nullptr_t&, const StringHashTableLookupResult& b) {
+ return !b.mapped_ptr;
+ }
+ friend bool operator!=(const StringHashTableLookupResult& a, const std::nullptr_t&) {
+ return a.mapped_ptr;
+ }
+ friend bool operator!=(const std::nullptr_t&, const StringHashTableLookupResult& b) {
+ return b.mapped_ptr;
+ }
+};
+
+template <typename Mapped>
+ALWAYS_INLINE inline auto lookup_result_get_mapped(StringHashTableLookupResult<Mapped*> cell) {
+ return &cell.get_mapped();
+}
+
+template <typename SubMaps>
+class StringHashTable : private boost::noncopyable {
+protected:
+ static constexpr size_t NUM_MAPS = 5;
+ // Map for storing empty string
+ using T0 = typename SubMaps::T0;
+
+ // Short strings are stored as numbers
+ using T1 = typename SubMaps::T1;
+ using T2 = typename SubMaps::T2;
+ using T3 = typename SubMaps::T3;
+
+ // Long strings are stored as StringRef along with saved hash
+ using Ts = typename SubMaps::Ts;
+ using Self = StringHashTable;
+
+ template <typename, typename, size_t>
+ friend class TwoLevelStringHashTable;
+
+ T0 m0;
+ T1 m1;
+ T2 m2;
+ T3 m3;
+ Ts ms;
+
+ using Cell = typename Ts::cell_type;
+
+ friend class const_iterator;
+ friend class iterator;
+
+ template <typename Derived, bool is_const>
+ class iterator_base {
+ using Container = std::conditional_t<is_const, const Self, Self>;
+
+ Container* container;
+ int sub_table_index;
+ typename T1::iterator iterator1;
+ typename T2::iterator iterator2;
+ typename T3::iterator iterator3;
+ typename Ts::iterator iterator4;
+
+ typename Ts::cell_type cell;
+
+ friend class StringHashTable;
+
+ public:
+ iterator_base() {}
+ iterator_base(Container* container_, bool end = false) : container(container_) {
+ if (end) {
+ sub_table_index = 4;
+ iterator4 = container->ms.end();
+ } else {
+ sub_table_index = 0;
+ if (container->m0.size() == 0)
+ sub_table_index++;
+ else
+ return;
+
+ iterator1 = container->m1.begin();
+ if (iterator1 == container->m1.end())
+ sub_table_index++;
+ else
+ return;
+
+ iterator2 = container->m2.begin();
+ if (iterator2 == container->m2.end())
+ sub_table_index++;
+ else
+ return;
+
+ iterator3 = container->m3.begin();
+ if (iterator3 == container->m3.end())
+ sub_table_index++;
+ else
+ return;
+
+ iterator4 = container->ms.begin();
+ }
+ }
+
+ bool operator==(const iterator_base& rhs) const {
+ if (sub_table_index != rhs.sub_table_index) return false;
+ switch (sub_table_index) {
+ case 0: {
+ return true;
+ }
+ case 1: {
+ return iterator1 == rhs.iterator1;
+ }
+ case 2: {
+ return iterator2 == rhs.iterator2;
+ }
+ case 3: {
+ return iterator3 == rhs.iterator3;
+ }
+ case 4: {
+ return iterator4 == rhs.iterator4;
+ }
+ }
+ __builtin_unreachable();
+ }
+
+ bool operator!=(const iterator_base& rhs) const { return !(*this == rhs); }
+
+ Derived& operator++() {
+ bool need_switch_to_next = false;
+ switch (sub_table_index) {
+ case 0: {
+ need_switch_to_next = true;
+ break;
+ }
+ case 1: {
+ iterator1.template operator++();
+ if (iterator1 == container->m1.end()) {
+ need_switch_to_next = true;
+ }
+ break;
+ }
+ case 2: {
+ iterator2.template operator++();
+ if (iterator2 == container->m2.end()) {
+ need_switch_to_next = true;
+ }
+ break;
+ }
+ case 3: {
+ iterator3.template operator++();
+ if (iterator3 == container->m3.end()) {
+ need_switch_to_next = true;
+ }
+ break;
+ }
+ case 4: {
+ iterator4.template operator++();
+ break;
+ }
+ }
+
+ while (need_switch_to_next) {
+ sub_table_index++;
+ need_switch_to_next = false;
+ switch (sub_table_index) {
+ case 1: {
+ iterator1 = container->m1.begin();
+ if (iterator1 == container->m1.end()) {
+ need_switch_to_next = true;
+ }
+ break;
+ }
+ case 2: {
+ iterator2 = container->m2.begin();
+ if (iterator2 == container->m2.end()) {
+ need_switch_to_next = true;
+ }
+ break;
+ }
+ case 3: {
+ iterator3 = container->m3.begin();
+ if (iterator3 == container->m3.end()) {
+ need_switch_to_next = true;
+ }
+ break;
+ }
+ case 4: {
+ iterator4 = container->ms.begin();
+ break;
+ }
+ }
+ }
+ while (need_switch_to_next)
+ ;
+
+ return static_cast<Derived&>(*this);
+ }
+
+ auto& operator*() const {
+ switch (sub_table_index) {
+ case 0: {
+ const_cast<iterator_base*>(this)->cell = *(container->m0.zero_value());
+ break;
+ }
+ case 1: {
+ const_cast<iterator_base*>(this)->cell = *iterator1;
+ break;
+ }
+ case 2: {
+ const_cast<iterator_base*>(this)->cell = *iterator2;
+ break;
+ }
+ case 3: {
+ const_cast<iterator_base*>(this)->cell = *iterator3;
+ break;
+ }
+ case 4: {
+ const_cast<iterator_base*>(this)->cell = *iterator4;
+ break;
+ }
+ }
+ return cell;
+ }
+ auto* operator->() const { return &(this->operator*()); }
+
+ auto get_ptr() const { return &(this->operator*()); }
+
+ size_t get_hash() const {
+ switch (sub_table_index) {
+ case 0: {
+ return container->m0.zero_value()->get_hash(container->m0);
+ }
+ case 1: {
+ return iterator1->get_hash(container->m1);
+ }
+ case 2: {
+ return iterator2->get_hash(container->m2);
+ }
+ case 3: {
+ return iterator3->get_hash(container->m3);
+ }
+ case 4: {
+ return iterator4->get_hash(container->ms);
+ }
+ }
+ }
+
+ size_t get_collision_chain_length() const { return 0; }
+
+ /**
+ * A hack for HashedDictionary.
+ *
+ * The problem: std-like find() returns an iterator, which has to be
+ * compared to end(). On the other hand, HashMap::find() returns
+ * LookupResult, which is compared to nullptr. HashedDictionary has to
+ * support both hash maps with the same code, hence the need for this
+ * hack.
+ *
+ * The proper way would be to remove iterator interface from our
+ * HashMap completely, change all its users to the existing internal
+ * iteration interface, and redefine end() to return LookupResult for
+ * compatibility with std find(). Unfortunately, now is not the time to
+ * do this.
+ */
+ operator Cell*() const { return nullptr; }
+ };
+
+public:
+ using Key = StringRef;
+ using key_type = Key;
+ using mapped_type = typename Ts::mapped_type;
+ using value_type = typename Ts::value_type;
+ using cell_type = typename Ts::cell_type;
+
+ using LookupResult = StringHashTableLookupResult<typename cell_type::mapped_type>;
+ using ConstLookupResult = StringHashTableLookupResult<const typename cell_type::mapped_type>;
+
+ StringHashTable() = default;
+
+ explicit StringHashTable(size_t reserve_for_num_elements)
+ : m1 {reserve_for_num_elements / 4},
+ m2 {reserve_for_num_elements / 4},
+ m3 {reserve_for_num_elements / 4},
+ ms {reserve_for_num_elements / 4} {}
+
+ StringHashTable(StringHashTable&& rhs) noexcept
+ : m1(std::move(rhs.m1)),
+ m2(std::move(rhs.m2)),
+ m3(std::move(rhs.m3)),
+ ms(std::move(rhs.ms)) {}
+
+ ~StringHashTable() = default;
+
+ // Dispatch is written in a way that maximizes the performance:
+ // 1. Always memcpy 8 times bytes
+ // 2. Use switch case extension to generate fast dispatching table
+ // 3. Funcs are named callables that can be force_inlined
+ //
+ // NOTE: It relies on Little Endianness
+ //
+ // NOTE: It requires padded to 8 bytes keys (IOW you cannot pass
+ // std::string here, but you can pass i.e. ColumnString::getDataAt()),
+ // since it copies 8 bytes at a time.
+ template <typename Self, typename KeyHolder, typename Func>
+ static auto ALWAYS_INLINE dispatch(Self& self, KeyHolder&& key_holder, Func&& func) {
+ StringHashTableHash hash;
+ const StringRef& x = key_holder_get_key(key_holder);
+ const size_t sz = x.size;
+ if (sz == 0) {
+ key_holder_get_key(key_holder);
+ return func(self.m0, VoidKey {}, 0);
+ }
+
+ if (x.data[sz - 1] == 0) {
+ // Strings with trailing zeros are not representable as fixed-size
+ // string keys. Put them to the generic table.
+ return func(self.ms, std::forward<KeyHolder>(key_holder), hash(x));
+ }
+
+ const char* p = x.data;
+ // pending bits that needs to be shifted out
+ const char s = (-sz & 7) * 8;
+ union {
+ StringKey8 k8;
+ StringKey16 k16;
+ StringKey24 k24;
+ doris::vectorized::UInt64 n[3];
+ };
+ switch ((sz - 1) >> 3) {
+ case 0: // 1..8 bytes
+ {
+ // first half page
Review Comment:
I am not sure, maybe avoid illegal address access？
--
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: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org