Structures and runtime functions of streaming top-k heap. More...

#include "../Shared/funcannotations.h"

Include dependency graph for TopKRuntime.cpp:

This graph shows which files directly or indirectly include this file:

Classes
struct	KeyAccessor< KeyT, IndexT >

struct	KeyComparator< KeyT >

Macros
#define	DEF_GET_BIN_FROM_K_HEAP(key_type)

Enumerations
enum	HeapOrdering { HeapOrdering::MIN, HeapOrdering::MAX }

enum	NullsOrdering { NullsOrdering::FIRST, NullsOrdering::LAST }

Functions
template<typename KeyT = int64_t, typename NodeT = int64_t>
ALWAYS_INLINE DEVICE void	sift_down (NodeT *heap, const size_t heap_size, const NodeT curr_idx, const KeyComparator< KeyT > &compare, const KeyAccessor< KeyT, NodeT > &accessor)

template<typename KeyT = int64_t, typename NodeT = int64_t>
ALWAYS_INLINE DEVICE void	sift_up (NodeT *heap, const NodeT curr_idx, const KeyComparator< KeyT > &compare, const KeyAccessor< KeyT, NodeT > &accessor)

template<typename KeyT = int64_t, typename NodeT = int64_t>
ALWAYS_INLINE DEVICE void	push_heap (int64_t heap_ptr, int64_t rows_ptr, NodeT &node_count, const uint32_t row_size_quad, const uint32_t key_offset, const KeyComparator< KeyT > &comparator, const KeyAccessor< KeyT, NodeT > &accessor, const KeyT curr_key)

template<typename KeyT = int64_t, typename NodeT = int64_t>
ALWAYS_INLINE DEVICE bool	pop_and_push_heap (int64_t heap_ptr, int64_t rows_ptr, const NodeT node_count, const uint32_t row_size_quad, const uint32_t key_offset, const KeyComparator< KeyT > &compare, const KeyAccessor< KeyT, NodeT > &accessor, const KeyT curr_key)

template<typename KeyT = int64_t>
ALWAYS_INLINE DEVICE int64_t *	get_bin_from_k_heap_impl (int64_t *heaps, const uint32_t k, const uint32_t row_size_quad, const uint32_t key_offset, const bool min_heap, const bool has_null, const bool nulls_first, const KeyT null_key, const KeyT curr_key)

Detailed Description

Structures and runtime functions of streaming top-k heap.

Definition in file TopKRuntime.cpp.

Macro Definition Documentation

#define DEF_GET_BIN_FROM_K_HEAP ( key_type )

Value:

extern "C" RUNTIME_EXPORT NEVER_INLINE DEVICE int64_t* get_bin_from_k_heap_##key_type( \
      int64_t* heaps,                                                                    \
      const uint32_t k,                                                                  \
      const uint32_t row_size_quad,                                                      \
      const uint32_t key_offset,                                                         \
      const bool min_heap,                                                               \
      const bool has_null,                                                               \
      const bool nulls_first,                                                            \
      const key_type null_key,                                                           \
      const key_type curr_key) {                                                         \
    return get_bin_from_k_heap_impl(heaps,                                               \
                                    k,                                                   \
                                    row_size_quad,                                       \
                                    key_offset,                                          \
                                    min_heap,                                            \
                                    has_null,                                            \
                                    nulls_first,                                         \
                                    null_key,                                            \
                                    curr_key);                                           \
  }

Definition at line 237 of file TopKRuntime.cpp.

Enumeration Type Documentation

enum HeapOrdering

strong

Enumerator
MIN
MAX

Definition at line 25 of file TopKRuntime.cpp.

25 { MIN, MAX };

MAX

Definition: FilterPushdownTestTableFunctions.cpp:32

MIN

Definition: FilterPushdownTestTableFunctions.cpp:32

enum NullsOrdering

strong

Enumerator
FIRST
LAST

Definition at line 27 of file TopKRuntime.cpp.

27 { FIRST, LAST };

NullsOrdering::FIRST

NullsOrdering::LAST

Function Documentation

template<typename KeyT = int64_t>

ALWAYS_INLINE DEVICE int64_t* get_bin_from_k_heap_impl	(	int64_t *	heaps,
		const uint32_t	k,
		const uint32_t	row_size_quad,
		const uint32_t	key_offset,
		const bool	min_heap,
		const bool	has_null,
		const bool	nulls_first,
		const KeyT	null_key,
		const KeyT	curr_key
	)

Definition at line 183 of file TopKRuntime.cpp.

References FIRST, LAST, MAX, MIN, pop_and_push_heap(), pos_start_impl(), pos_step_impl(), and push_heap().

                                                                             {
   const int32_t thread_global_index = pos_start_impl(nullptr);
   const int32_t thread_count = pos_step_impl();
   int64_t& node_count = heaps[thread_global_index];
   int64_t* heap_ptr = heaps + thread_count + thread_global_index * k;
   int64_t* rows_ptr =
       heaps + thread_count + thread_count * k + thread_global_index * row_size_quad * k;
   KeyComparator<KeyT> compare((min_heap ? HeapOrdering::MIN : HeapOrdering::MAX),
                               has_null,
                               null_key,
                               nulls_first ? NullsOrdering::FIRST : NullsOrdering::LAST);
   KeyAccessor<KeyT, int64_t> accessor(reinterpret_cast<int8_t*>(rows_ptr),
                                       row_size_quad * sizeof(int64_t),
                                       key_offset / sizeof(KeyT));
   if (node_count < static_cast<int64_t>(k)) {
     push_heap(heap_ptr,
               rows_ptr,
               node_count,
               row_size_quad,
               key_offset,
               compare,
               accessor,
               curr_key);
     const auto last_bin_index = node_count - 1;
     auto row_ptr = rows_ptr + last_bin_index * row_size_quad;
     row_ptr[0] = last_bin_index;
     return row_ptr + 1;
   } else {
     const int64_t top_bin_idx = heap_ptr[0];
     const bool rejected = !pop_and_push_heap(heap_ptr,
                                              rows_ptr,
                                              node_count,
                                              row_size_quad,
                                              key_offset,
                                              compare,
                                              accessor,
                                              curr_key);
     if (rejected) {
       return nullptr;
     }
     auto row_ptr = rows_ptr + top_bin_idx * row_size_quad;
     row_ptr[0] = top_bin_idx;
     return row_ptr + 1;
   }
 }

Here is the call graph for this function:

template<typename KeyT = int64_t, typename NodeT = int64_t>

ALWAYS_INLINE DEVICE bool pop_and_push_heap	(	int64_t *	heap_ptr,
		int64_t *	rows_ptr,
		const NodeT	node_count,
		const uint32_t	row_size_quad,
		const uint32_t	key_offset,
		const KeyComparator< KeyT > &	compare,
		const KeyAccessor< KeyT, NodeT > &	accessor,
		const KeyT	curr_key
	)

Definition at line 160 of file TopKRuntime.cpp.

Referenced by get_bin_from_k_heap_impl().

                                                                  {
   const NodeT top_bin_idx = static_cast<NodeT>(heap_ptr[0]);
   int8_t* top_row_ptr = reinterpret_cast<int8_t*>(rows_ptr + top_bin_idx * row_size_quad);
   auto top_key = reinterpret_cast<KeyT*>(top_row_ptr + key_offset);
   if (compare(curr_key, *top_key)) {
     return false;
   }
   // kick out
   *top_key = curr_key;
   // sift down
   sift_down<KeyT, NodeT>(heap_ptr, node_count, 0, compare, accessor);
   return true;
 }

Here is the caller graph for this function:

template<typename KeyT = int64_t, typename NodeT = int64_t>

ALWAYS_INLINE DEVICE void push_heap	(	int64_t *	heap_ptr,
		int64_t *	rows_ptr,
		NodeT &	node_count,
		const uint32_t	row_size_quad,
		const uint32_t	key_offset,
		const KeyComparator< KeyT > &	comparator,
		const KeyAccessor< KeyT, NodeT > &	accessor,
		const KeyT	curr_key
	)

Definition at line 142 of file TopKRuntime.cpp.

Referenced by get_bin_from_k_heap_impl().

                                                          {
   const NodeT bin_index = node_count++;
   heap_ptr[bin_index] = bin_index;
   int8_t* row_ptr = reinterpret_cast<int8_t*>(rows_ptr + bin_index * row_size_quad);
   auto key_ptr = reinterpret_cast<KeyT*>(row_ptr + key_offset);
   *key_ptr = curr_key;
   // sift up
   sift_up<KeyT, NodeT>(heap_ptr, bin_index, comparator, accessor);
 }

Here is the caller graph for this function:

template<typename KeyT = int64_t, typename NodeT = int64_t>

ALWAYS_INLINE DEVICE void sift_down	(	NodeT *	heap,
		const size_t	heap_size,
		const NodeT	curr_idx,
		const KeyComparator< KeyT > &	compare,
		const KeyAccessor< KeyT, NodeT > &	accessor
	)

Definition at line 82 of file TopKRuntime.cpp.

References KeyAccessor< KeyT, IndexT >::get().

                                                                               {
   for (NodeT i = curr_idx, last = static_cast<NodeT>(heap_size); i < last;) {
 #ifdef __CUDACC__
     const auto left_child = min(2 * i + 1, last);
     const auto right_child = min(2 * i + 2, last);
 #else
     const auto left_child = std::min(2 * i + 1, last);
     const auto right_child = std::min(2 * i + 2, last);
 #endif
     auto candidate_idx = last;
     if (left_child < last) {
       if (right_child < last) {
         const auto left_key = accessor.get(heap[left_child]);
         const auto right_key = accessor.get(heap[right_child]);
         candidate_idx = compare(left_key, right_key) ? left_child : right_child;
       } else {
         candidate_idx = left_child;
       }
     } else {
       candidate_idx = right_child;
     }
     if (candidate_idx >= last) {
       break;
     }
     const auto curr_key = accessor.get(heap[i]);
     const auto candidate_key = accessor.get(heap[candidate_idx]);
     if (compare(curr_key, candidate_key)) {
       break;
     }
     auto temp_id = heap[i];
     heap[i] = heap[candidate_idx];
     heap[candidate_idx] = temp_id;
     i = candidate_idx;
   }
 }

Here is the call graph for this function:

template<typename KeyT = int64_t, typename NodeT = int64_t>

ALWAYS_INLINE DEVICE void sift_up	(	NodeT *	heap,
		const NodeT	curr_idx,
		const KeyComparator< KeyT > &	compare,
		const KeyAccessor< KeyT, NodeT > &	accessor
	)

Definition at line 123 of file TopKRuntime.cpp.

References KeyAccessor< KeyT, IndexT >::get().

                                                                             {
   for (NodeT i = curr_idx; i > 0 && (i - 1) < i;) {
     const auto parent = (i - 1) / 2;
     const auto curr_key = accessor.get(heap[i]);
     const auto parent_key = accessor.get(heap[parent]);
     if (compare(parent_key, curr_key)) {
       break;
     }
     auto temp_id = heap[i];
     heap[i] = heap[parent];
     heap[parent] = temp_id;
     i = parent;
   }
 }

Here is the call graph for this function:

Classes

Macros

Enumerations

Functions

Detailed Description

Macro Definition Documentation

Enumeration Type Documentation

Function Documentation