[
https://issues.apache.org/jira/browse/ARROW-1559?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16255589#comment-16255589
]
ASF GitHub Bot commented on ARROW-1559:
---------------------------------------
cpcloud commented on a change in pull request #1266: ARROW-1559: [C++] Add
Unique kernel and refactor DictionaryBuilder to be a stateful kernel
URL: https://github.com/apache/arrow/pull/1266#discussion_r151464797
##########
File path: cpp/src/arrow/compute/kernels/hash.cc
##########
@@ -0,0 +1,822 @@
+// 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 "arrow/compute/kernels/hash.h"
+
+#include <exception>
+#include <limits>
+#include <memory>
+#include <mutex>
+#include <sstream>
+#include <string>
+#include <vector>
+
+#include "arrow/builder.h"
+#include "arrow/compute/context.h"
+#include "arrow/compute/kernel.h"
+#include "arrow/compute/kernels/util-internal.h"
+#include "arrow/util/hash-util.h"
+
+namespace arrow {
+namespace compute {
+
+namespace {
+
+// Initially 1024 elements
+static constexpr int64_t kInitialHashTableSize = 1 << 10;
+
+typedef int32_t hash_slot_t;
+static constexpr hash_slot_t kHashSlotEmpty =
std::numeric_limits<int32_t>::max();
+
+// The maximum load factor for the hash table before resizing.
+static constexpr double kMaxHashTableLoad = 0.7;
+
+enum class SIMDMode : char { NOSIMD, SSE4, AVX2 };
+
+#define CHECK_IMPLEMENTED(KERNEL, FUNCNAME, TYPE) \
+ if (!KERNEL) { \
+ std::stringstream ss; \
+ ss << FUNCNAME << " not implemented for " << type->ToString(); \
+ return Status::NotImplemented(ss.str()); \
+ }
+
+Status NewHashTable(int64_t size, MemoryPool* pool, std::shared_ptr<Buffer>*
out) {
+ auto hash_table = std::make_shared<PoolBuffer>(pool);
+
+ RETURN_NOT_OK(hash_table->Resize(sizeof(hash_slot_t) * size));
+ int32_t* slots = reinterpret_cast<hash_slot_t*>(hash_table->mutable_data());
+ std::fill(slots, slots + size, kHashSlotEmpty);
+
+ *out = hash_table;
+ return Status::OK();
+}
+
+// This is a slight design concession -- some hash actions have the possibility
+// of failure. Rather than introduce extra error checking into all actions, we
+// will raise an internal exception so that only the actions where errors can
+// occur will experience the extra overhead
+class HashException : public std::exception {
+ public:
+ explicit HashException(const std::string& msg, StatusCode code =
StatusCode::Invalid)
+ : msg_(msg), code_(code) {}
+
+ ~HashException() throw() {}
+
+ const char* what() const throw() override;
+
+ StatusCode code() const { return code_; }
+
+ private:
+ std::string msg_;
+ StatusCode code_;
+};
+
+const char* HashException::what() const throw() { return msg_.c_str(); }
+
+class HashTable {
+ public:
+ HashTable(const std::shared_ptr<DataType>& type, MemoryPool* pool)
+ : type_(type),
+ pool_(pool),
+ initialized_(false),
+ hash_table_(nullptr),
+ hash_slots_(nullptr),
+ hash_table_size_(0),
+ mod_bitmask_(0) {}
+
+ virtual ~HashTable() {}
+
+ virtual Status Append(const ArrayData& input) = 0;
+ virtual Status Flush(Datum* out) = 0;
+ virtual Status GetDictionary(std::shared_ptr<ArrayData>* out) = 0;
+
+ protected:
+ Status Init(int64_t elements);
+
+ std::shared_ptr<DataType> type_;
+ MemoryPool* pool_;
+ bool initialized_;
+
+ // The hash table contains integer indices that reference the set of observed
+ // distinct values
+ std::shared_ptr<Buffer> hash_table_;
+ hash_slot_t* hash_slots_;
+
+ /// Size of the table. Must be a power of 2.
+ int64_t hash_table_size_;
+
+ /// Size at which we decide to resize
+ int64_t hash_table_load_threshold_;
+
+ // Store hash_table_size_ - 1, so that j & mod_bitmask_ is equivalent to j %
+ // hash_table_size_, but uses far fewer CPU cycles
+ int64_t mod_bitmask_;
+};
+
+Status HashTable::Init(int64_t elements) {
+ DCHECK_EQ(elements, BitUtil::NextPower2(elements));
+ RETURN_NOT_OK(NewHashTable(elements, pool_, &hash_table_));
+ hash_slots_ = reinterpret_cast<hash_slot_t*>(hash_table_->mutable_data());
+ hash_table_size_ = elements;
+ hash_table_load_threshold_ =
+ static_cast<int64_t>(static_cast<double>(elements) * kMaxHashTableLoad);
+ mod_bitmask_ = elements - 1;
+ initialized_ = true;
+ return Status::OK();
+}
+
+template <typename Type, typename Action, typename Enable = void>
+class HashTableKernel : public HashTable {};
+
+// Types of hash actions
+//
+// unique: append to dictionary when not found, no-op with slot
+// dictionary-encode: append to dictionary when not found, append slot #
+// match: raise or set null when not found, otherwise append slot #
+// isin: set false when not found, otherwise true
+// value counts: append to dictionary when not found, increment count for slot
+
+template <typename Type, typename Enable = void>
+class HashDictionary {};
+
+// ----------------------------------------------------------------------
+// Hash table pass for nulls
+
+template <typename Type, typename Action>
+class HashTableKernel<Type, Action, enable_if_null<Type>> : public HashTable {
+ public:
+ using HashTable::HashTable;
+
+ Status Init() {
+ // No-op, do not even need to initialize hash table
+ return Status::OK();
+ }
+
+ Status Append(const ArrayData& arr) override {
+ if (!initialized_) {
+ RETURN_NOT_OK(Init());
+ }
+ auto action = static_cast<Action*>(this);
+ RETURN_NOT_OK(action->Reserve(arr.length));
+ for (int64_t i = 0; i < arr.length; ++i) {
+ action->ObserveNull();
+ }
+ return Status::OK();
+ }
+
+ Status GetDictionary(std::shared_ptr<ArrayData>* out) override {
+ // TODO(wesm): handle null being a valid dictionary value
+ auto null_array = std::make_shared<NullArray>(0);
+ *out = null_array->data();
+ return Status::OK();
+ }
+};
+
+// ----------------------------------------------------------------------
+// Hash table pass for primitive types
+
+template <typename Type>
+struct HashDictionary<Type, enable_if_has_c_type<Type>> {
+ using T = typename Type::c_type;
+
+ explicit HashDictionary(MemoryPool* pool)
+ : pool(pool), buffer(std::make_shared<PoolBuffer>(pool)), size(0),
capacity(0) {}
+
+ Status Init() {
+ this->size = 0;
+ return Resize(kInitialHashTableSize);
+ }
+
+ Status DoubleSize() { return Resize(this->size * 2); }
+
+ Status Resize(const int64_t elements) {
+ RETURN_NOT_OK(this->buffer->Resize(elements * sizeof(T)));
+
+ this->capacity = elements;
+ this->values = reinterpret_cast<T*>(this->buffer->mutable_data());
+ return Status::OK();
+ }
+
+ MemoryPool* pool;
+ std::shared_ptr<ResizableBuffer> buffer;
+ T* values;
+ int64_t size;
+ int64_t capacity;
+};
+
+#define GENERIC_HASH_PASS(HASH_INNER_LOOP)
\
Review comment:
I suspect we can elide macros using CRTP, but that can be done in a
follow-up patch. Something like this:
```cpp
template <typename Kernel>
class HashTableKernelBase {
// interface methods, static_cast<Kernel*>(this) then call implementation
};
template <typename Type, typename Action, typename Enable = void>
class HashTableKernel : public HashTableKernelBase<HashTableKernel<Type,
Action, Enable>> {
// specific methods: inner loop, hash pass, etc
};
template <typename Type, typename Action>
class HashTableKernel<Type, Action, enable_if_null<Type>> {
};
```
No macros, no runtime polymorphism overhead :)
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
> [C++] Kernel implementations for "unique" (compute distinct elements of array)
> ------------------------------------------------------------------------------
>
> Key: ARROW-1559
> URL: https://issues.apache.org/jira/browse/ARROW-1559
> Project: Apache Arrow
> Issue Type: New Feature
> Components: C++
> Reporter: Wes McKinney
> Assignee: Uwe L. Korn
> Labels: Analytics, pull-request-available
> Fix For: 0.8.0
>
>
--
This message was sent by Atlassian JIRA
(v6.4.14#64029)
