Go to the documentation of this file.
8 #ifndef XGBOOST_COMMON_PARTITION_BUILDER_H_
9 #define XGBOOST_COMMON_PARTITION_BUILDER_H_
17 #include "../common/column_matrix.h"
27 template<
size_t BlockSize>
30 template<
typename Func>
31 void Init(
const size_t n_tasks,
size_t n_nodes, Func funcNTask) {
36 for (
size_t i = 1; i < n_nodes+1; ++i) {
50 template <
bool default_left,
bool any_missing,
typename ColumnType>
54 size_t* p_left_part = left_part.
data();
55 size_t* p_right_part = right_part.
data();
56 size_t nleft_elems = 0;
57 size_t nright_elems = 0;
58 auto state = column.GetInitialState(rid_span.
front());
60 for (
auto rid : rid_span) {
61 const int32_t bin_id = column.GetBinIdx(rid, &state);
62 if (any_missing && bin_id == ColumnType::kMissingId) {
64 p_left_part[nleft_elems++] = rid;
66 p_right_part[nright_elems++] = rid;
69 if (bin_id <= split_cond) {
70 p_left_part[nleft_elems++] = rid;
72 p_right_part[nright_elems++] = rid;
77 return {nleft_elems, nright_elems};
81 template <
typename BinIdxType,
bool any_missing>
83 const int32_t split_cond,
90 const bst_uint fid = tree[nid].SplitIndex();
91 const bool default_left = tree[nid].DefaultLeft();
92 const auto column_ptr = column_matrix.
GetColumn<BinIdxType, any_missing>(fid);
94 std::pair<size_t, size_t> child_nodes_sizes;
100 child_nodes_sizes = PartitionKernel<true, any_missing>(column, rid_span,
101 split_cond, left, right);
103 child_nodes_sizes = PartitionKernel<false, any_missing>(column, rid_span,
104 split_cond, left, right);
107 CHECK_EQ(any_missing,
true);
111 child_nodes_sizes = PartitionKernel<true, any_missing>(column, rid_span,
112 split_cond, left, right);
114 child_nodes_sizes = PartitionKernel<false, any_missing>(column, rid_span,
115 split_cond, left, right);
119 const size_t n_left = child_nodes_sizes.first;
120 const size_t n_right = child_nodes_sizes.second;
131 CHECK_NE(local_block_ptr, (
BlockInfo*)
nullptr);
137 const size_t task_idx =
GetTaskIdx(nid, begin);
138 return {
mem_blocks_.at(task_idx)->Left(), end - begin };
142 const size_t task_idx =
GetTaskIdx(nid, begin);
143 return {
mem_blocks_.at(task_idx)->Right(), end - begin };
186 size_t* left_result = rows_indexes +
mem_blocks_[task_idx]->n_offset_left;
187 size_t* right_result = rows_indexes +
mem_blocks_[task_idx]->n_offset_right;
189 const size_t* left =
mem_blocks_[task_idx]->Left();
190 const size_t* right =
mem_blocks_[task_idx]->Right();
192 std::copy_n(left,
mem_blocks_[task_idx]->n_left, left_result);
193 std::copy_n(right,
mem_blocks_[task_idx]->n_right, right_result);
209 return &left_data_[0];
213 return &right_data_[0];
216 size_t left_data_[BlockSize];
217 size_t right_data_[BlockSize];
228 #endif // XGBOOST_COMMON_PARTITION_BUILDER_H_
void MergeToArray(int nid, size_t begin, size_t *rows_indexes)
Definition: partition_builder.h:183
size_t * Right()
Definition: partition_builder.h:212
Definition: partition_builder.h:28
common::Span< size_t > GetRightBuffer(int nid, size_t begin, size_t end)
Definition: partition_builder.h:141
size_t max_n_tasks_
Definition: partition_builder.h:222
size_t begin() const
Definition: threading_utils.h:43
std::vector< std::shared_ptr< BlockInfo > > mem_blocks_
Definition: partition_builder.h:221
void Partition(const size_t node_in_set, const size_t nid, const common::Range1d range, const int32_t split_cond, const ColumnMatrix &column_matrix, const RegTree &tree, const size_t *rid)
Definition: partition_builder.h:82
a collection of columns, with support for construction from GHistIndexMatrix.
Definition: column_matrix.h:141
size_t n_offset_right
Definition: partition_builder.h:206
size_t n_offset_left
Definition: partition_builder.h:205
size_t n_left
Definition: partition_builder.h:202
std::vector< std::pair< size_t, size_t > > left_right_nodes_sizes_
Definition: partition_builder.h:219
@ kDenseColumn
Definition: column_matrix.h:23
Definition: column_matrix.h:111
Definition: column_matrix.h:68
define regression tree to be the most common tree model. This is the data structure used in xgboost's...
Definition: tree_model.h:131
XGBOOST_DEVICE reference front() const
Definition: span.h:525
common::Span< size_t > GetLeftBuffer(int nid, size_t begin, size_t end)
Definition: partition_builder.h:136
Definition: partition_builder.h:201
size_t n_right
Definition: partition_builder.h:203
size_t * Left()
Definition: partition_builder.h:208
size_t GetTaskIdx(int nid, size_t begin)
Definition: partition_builder.h:196
ColumnType
column type
Definition: column_matrix.h:22
The input data structure of xgboost.
void SetNRightElems(int nid, size_t begin, size_t end, size_t n_right)
Definition: partition_builder.h:151
void AllocateForTask(size_t id)
Definition: partition_builder.h:128
size_t GetNLeftElems(int nid) const
Definition: partition_builder.h:157
Definition: threading_utils.h:37
std::vector< size_t > blocks_offsets_
Definition: partition_builder.h:220
void CalculateRowOffsets()
Definition: partition_builder.h:167
std::unique_ptr< const Column< BinIdxType > > GetColumn(unsigned fid) const
Definition: column_matrix.h:246
constexpr XGBOOST_DEVICE pointer data() const __span_noexcept
Definition: span.h:542
uint32_t bst_uint
unsigned integer type used for feature index.
Definition: base.h:113
size_t end() const
Definition: threading_utils.h:47
auto get(U &json) -> decltype(detail::GetImpl(*Cast< T >(&json.GetValue())))&
Get Json value.
Definition: json.h:556
void SetNLeftElems(int nid, size_t begin, size_t end, size_t n_left)
Definition: partition_builder.h:146
std::pair< size_t, size_t > PartitionKernel(const ColumnType &column, common::Span< const size_t > rid_span, const int32_t split_cond, common::Span< size_t > left_part, common::Span< size_t > right_part)
Definition: partition_builder.h:51
size_t GetNRightElems(int nid) const
Definition: partition_builder.h:161
namespace of xgboost
Definition: base.h:110
void Init(const size_t n_tasks, size_t n_nodes, Func funcNTask)
Definition: partition_builder.h:31