7 #ifndef XGBOOST_COMMON_HIST_UTIL_H_ 8 #define XGBOOST_COMMON_HIST_UTIL_H_ 21 #include "../tree/param.h" 24 #include "../include/rabit/rabit.h" 64 *
this = std::forward<HistogramCuts&&>(that);
78 monitor_ = std::move(that.monitor_);
79 cut_ptrs_ = std::move(that.cut_ptrs_);
80 cut_values_ = std::move(that.cut_values_);
81 min_vals_ = std::move(that.min_vals_);
108 auto it = std::upper_bound(values.cbegin() + beg, values.cbegin() + end, value);
109 BinIdx idx = it - values.cbegin();
131 static bool UseGroup(
DMatrix* dmat);
141 std::vector<bst_uint>
const& group_ptr,
size_t const base_rowid) {
142 using KIt = std::vector<bst_uint>::const_iterator;
143 KIt res = std::lower_bound(group_ptr.cbegin(), group_ptr.cend() - 1, base_rowid);
145 bool const found = res != group_ptr.cend() - 1;
147 LOG(FATAL) <<
"Row " << base_rowid <<
" does not lie in any group!";
149 uint32_t group_ind = std::distance(group_ptr.cbegin(), res);
153 void AddCutPoint(WQSketch::SummaryContainer
const& summary,
int max_bin) {
154 size_t required_cuts = std::min(summary.size, static_cast<size_t>(max_bin));
155 for (
size_t i = 1; i < required_cuts; ++i) {
164 virtual void Build(
DMatrix* dmat, uint32_t
const max_num_bins) = 0;
170 static std::vector<size_t> LoadBalance(
SparsePage const& page,
size_t const nthreads);
176 monitor_.
Init(__FUNCTION__);
180 void Concat(std::vector<std::unique_ptr<SparseCuts>>
const& cuts, uint32_t n_cols);
183 uint32_t max_num_bins,
184 bool const use_group_ind,
185 uint32_t beg, uint32_t end, uint32_t thread_id);
186 void Build(
DMatrix* dmat, uint32_t
const max_num_bins)
override;
197 monitor_.
Init(__FUNCTION__);
199 void Init(std::vector<WQSketch>* sketchs, uint32_t max_num_bins,
size_t max_rows);
200 void Build(
DMatrix* p_fmat, uint32_t max_num_bins)
override;
205 size_t sketch_batch_num_elements = 0);
208 template <
typename AdapterT>
211 size_t sketch_batch_num_elements = 0);
222 SetBinTypeSize(binTypeSize_);
229 if (offset_ptr_ !=
nullptr) {
230 return func_(data_ptr_, i) + offset_ptr_[i%p_];
232 return func_(data_ptr_, i);
236 binTypeSize_ = binTypeSize;
237 switch (binTypeSize) {
239 func_ = &GetValueFromUint8;
242 func_ = &GetValueFromUint16;
245 func_ = &GetValueFromUint32;
258 return static_cast<T*
>(data_ptr_);
264 return offset_.size();
267 return data_.size() / (binTypeSize_);
270 data_.resize(nBytesData);
271 data_ptr_ =
reinterpret_cast<void*
>(data_.data());
274 offset_.resize(nDisps);
275 offset_ptr_ = offset_.data();
278 std::vector<uint8_t>::const_iterator
begin()
const {
279 return data_.begin();
281 std::vector<uint8_t>::const_iterator
end()
const {
286 static uint32_t GetValueFromUint8(
void *t,
size_t i) {
287 return reinterpret_cast<uint8_t*
>(t)[i];
289 static uint32_t GetValueFromUint16(
void* t,
size_t i) {
290 return reinterpret_cast<uint16_t*
>(t)[i];
292 static uint32_t GetValueFromUint32(
void* t,
size_t i) {
293 return reinterpret_cast<uint32_t*
>(t)[i];
296 using Func = uint32_t (*)(
void*, size_t);
298 std::vector<uint8_t> data_;
299 std::vector<uint32_t> offset_;
303 uint32_t* offset_ptr_ {
nullptr};
326 void Init(
DMatrix* p_fmat,
int max_num_bins);
328 template<
typename BinIdxType>
330 size_t batch_threads,
const SparsePage& batch,
336 size_t batch_threads,
const SparsePage& batch,
337 size_t rbegin,
size_t nbins);
339 void ResizeIndex(
const size_t rbegin,
const SparsePage& batch,
340 const size_t n_offsets,
const size_t n_index,
344 auto nfeature = cut.
Ptrs().size() - 1;
345 for (
unsigned fid = 0; fid < nfeature; ++fid) {
346 auto ibegin = cut.
Ptrs()[fid];
347 auto iend = cut.
Ptrs()[fid + 1];
348 for (
auto i = ibegin; i < iend; ++i) {
349 counts[fid] += hit_count[i];
358 std::vector<size_t> hit_count_tloc_;
367 : row_ptr(row_ptr), index(index) {}
371 return {&index[0] + row_ptr[i], row_ptr[i + 1] - row_ptr[i]};
381 const tree::TrainParam& param);
384 return {blocks_[i].row_ptr_begin, blocks_[i].index_begin};
388 return blocks_.size();
392 std::vector<size_t> row_ptr_;
393 std::vector<uint32_t> index_;
396 const size_t* row_ptr_begin;
397 const size_t* row_ptr_end;
398 const uint32_t* index_begin;
399 const uint32_t* index_end;
401 std::vector<Block> blocks_;
431 size_t begin,
size_t end);
440 constexpr uint32_t kMax = std::numeric_limits<uint32_t>::max();
441 CHECK_NE(row_ptr_[nid], kMax);
442 tree::GradStats* ptr =
443 const_cast<tree::GradStats*
>(dmlc::BeginPtr(data_) + row_ptr_[nid]);
444 return {ptr, nbins_};
449 const uint32_t k_max = std::numeric_limits<uint32_t>::max();
450 return (nid < row_ptr_.size() && row_ptr_[nid] != k_max);
455 if (nbins_ != nbins) {
466 constexpr uint32_t kMax = std::numeric_limits<uint32_t>::max();
467 if (nid >= row_ptr_.size()) {
468 row_ptr_.resize(nid + 1, kMax);
470 CHECK_EQ(row_ptr_[nid], kMax);
472 if (data_.size() < nbins_ * (nid + 1)) {
473 data_.resize(nbins_ * (nid + 1));
476 row_ptr_[nid] = nbins_ * n_nodes_added_;
484 uint32_t n_nodes_added_ = 0;
486 std::vector<tree::GradStats> data_;
489 std::vector<size_t> row_ptr_;
500 if (nbins != nbins_) {
501 hist_buffer_.Init(nbins);
509 const std::vector<GHistRow>& targeted_hists) {
510 hist_buffer_.Init(nbins_);
511 tid_nid_to_hist_.clear();
512 hist_memory_.clear();
513 threads_to_nids_map_.clear();
515 targeted_hists_ = targeted_hists;
517 CHECK_EQ(nodes, targeted_hists.size());
520 nthreads_ = nthreads;
522 MatchThreadsToNodes(space);
523 AllocateAdditionalHistograms();
524 MatchNodeNidPairToHist();
526 hist_was_used_.resize(nthreads * nodes_);
527 std::fill(hist_was_used_.begin(), hist_was_used_.end(),
static_cast<int>(
false));
532 CHECK_LT(nid, nodes_);
533 CHECK_LT(tid, nthreads_);
535 size_t idx = tid_nid_to_hist_.at({tid, nid});
538 if (!hist_was_used_[tid * nodes_ + nid]) {
540 hist_was_used_[tid * nodes_ + nid] =
static_cast<int>(
true);
548 CHECK_GT(end, begin);
549 CHECK_LT(nid, nodes_);
551 GHistRow dst = targeted_hists_[nid];
553 bool is_updated =
false;
554 for (
size_t tid = 0; tid < nthreads_; ++tid) {
555 if (hist_was_used_[tid * nodes_ + nid]) {
557 const size_t idx = tid_nid_to_hist_.at({tid, nid});
574 const size_t space_size = space.
Size();
575 const size_t chunck_size = space_size / nthreads_ + !!(space_size % nthreads_);
577 threads_to_nids_map_.resize(nthreads_ * nodes_,
false);
579 for (
size_t tid = 0; tid < nthreads_; ++tid) {
580 size_t begin = chunck_size * tid;
581 size_t end = std::min(begin + chunck_size, space_size);
583 if (begin < space_size) {
587 for (
size_t nid = nid_begin; nid <= nid_end; ++nid) {
589 threads_to_nids_map_[tid * nodes_ + nid] =
true;
596 size_t hist_allocated_additionally = 0;
598 for (
size_t nid = 0; nid < nodes_; ++nid) {
599 int nthreads_for_nid = 0;
601 for (
size_t tid = 0; tid < nthreads_; ++tid) {
602 if (threads_to_nids_map_[tid * nodes_ + nid]) {
611 hist_allocated_additionally += std::max<int>(0, nthreads_for_nid - 1);
614 for (
size_t i = 0; i < hist_allocated_additionally; ++i) {
615 hist_buffer_.AddHistRow(i);
620 size_t hist_total = 0;
621 size_t hist_allocated_additionally = 0;
623 for (
size_t nid = 0; nid < nodes_; ++nid) {
624 bool first_hist =
true;
625 for (
size_t tid = 0; tid < nthreads_; ++tid) {
626 if (threads_to_nids_map_[tid * nodes_ + nid]) {
628 hist_memory_.push_back(targeted_hists_[nid]);
631 hist_memory_.push_back(hist_buffer_[hist_allocated_additionally]);
632 hist_allocated_additionally++;
635 tid_nid_to_hist_[{tid, nid}] = hist_total++;
636 CHECK_EQ(hist_total, hist_memory_.size());
645 size_t nthreads_ = 0;
673 GHistBuilder(
size_t nthread, uint32_t nbins) : nthread_{nthread}, nbins_{nbins} {}
676 void BuildHist(
const std::vector<GradientPair>& gpair,
682 void BuildBlockHist(
const std::vector<GradientPair>& gpair,
695 size_t nthread_ { 0 };
697 uint32_t nbins_ { 0 };
703 #endif // XGBOOST_COMMON_HIST_UTIL_H_ void InitilizeHistByZeroes(GHistRow hist, size_t begin, size_t end)
fill a histogram by zeros
void Init(uint32_t nbins)
Definition: hist_util.h:454
void ReduceHist(size_t nid, size_t begin, size_t end)
Definition: hist_util.h:547
DenseCuts(HistogramCuts *container)
Definition: hist_util.h:195
Definition: hist_util.h:220
void SetBinTypeSize(BinTypeSize binTypeSize)
Definition: hist_util.h:235
Index index
The index data.
Definition: hist_util.h:318
float bst_float
float type, used for storing statistics
Definition: base.h:111
BinIdx SearchBin(float value, uint32_t column_id) const
Definition: hist_util.h:104
XGBOOST_DEVICE constexpr index_type size() const __span_noexcept
Definition: span.h:531
void Copy(const HostDeviceVector< T > &other)
HistCollection hist_buffer_
Buffer for additional histograms for Parallel processing.
Definition: hist_util.h:649
size_t GetNumBlock() const
Definition: hist_util.h:387
void IncrementHist(GHistRow dst, const GHistRow add, size_t begin, size_t end)
Increment hist as dst += add in range [begin, end)
uint32_t FeatureBins(uint32_t feature) const
Definition: hist_util.h:88
Definition: hist_util.h:362
BinIdx SearchBin(Entry const &e) const
Definition: hist_util.h:116
static uint32_t SearchGroupIndFromRow(std::vector< bst_uint > const &group_ptr, size_t const base_rowid)
Definition: hist_util.h:140
void CopyHist(GHistRow dst, const GHistRow src, size_t begin, size_t end)
Copy hist from src to dst in range [begin, end)
void AddHistRow(bst_uint nid)
Definition: hist_util.h:465
std::vector< bool > threads_to_nids_map_
Buffer for additional histograms for Parallel processing.
Definition: hist_util.h:658
std::vector< uint32_t > const & Ptrs() const
Definition: hist_util.h:96
util to compute quantiles
Definition: hist_util.h:215
The input data structure of xgboost.
T * data() const
Definition: hist_util.h:257
HistogramCuts & operator=(HistogramCuts const &that)
Definition: hist_util.h:67
GHistBuilder(size_t nthread, uint32_t nbins)
Definition: hist_util.h:673
HistogramCuts cut
The corresponding cuts.
Definition: hist_util.h:322
void MatchNodeNidPairToHist()
Definition: hist_util.h:619
Internal data structured used by XGBoost during training. There are two ways to create a customized D...
Definition: data.h:451
size_t GetFirstDimension(size_t i) const
Definition: threading_utils.h:89
Cut configuration for dense dataset.
Definition: hist_util.h:190
In-memory storage unit of sparse batch, stored in CSR format.
Definition: data.h:211
bool IsDense() const
Definition: hist_util.h:353
HistogramCuts & operator=(HistogramCuts &&that) noexcept(true)
Definition: hist_util.h:77
Definition: hist_util.h:127
std::vector< size_t > hit_count
hit count of each index
Definition: hist_util.h:320
span class implementation, based on ISO++20 span<T>. The interface should be the same.
Definition: span.h:126
Definition: hist_util.h:216
builder for histograms of gradient statistics
Definition: hist_util.h:670
size_t OffsetSize() const
Definition: hist_util.h:263
std::vector< float > const & MinValues() const
Definition: hist_util.h:98
HostDeviceVector< bst_float > cut_values_
Definition: hist_util.h:48
GHistIndexBlock operator[](size_t i) const
Definition: hist_util.h:383
Quantile sketch use WQSummary.
Definition: quantile.h:831
XGBOOST_DEVICE constexpr pointer data() const __span_noexcept
Definition: span.h:526
Quick Utility to compute subset of rows.
GHistRow GetInitializedHist(size_t tid, size_t nid)
Definition: hist_util.h:531
HistogramCuts(HistogramCuts const &that)
Definition: hist_util.h:54
void Init(std::string label)
Definition: timer.h:82
BinTypeSize GetBinTypeSize() const
Definition: hist_util.h:253
size_t TotalBins() const
Definition: hist_util.h:100
HistogramCuts(HistogramCuts &&that) noexcept(true)
Definition: hist_util.h:63
std::vector< uint8_t >::const_iterator begin() const
Definition: hist_util.h:278
std::vector< uint8_t >::const_iterator end() const
Definition: hist_util.h:281
Cut configuration for sparse dataset.
Definition: hist_util.h:168
const size_t * row_ptr
Definition: hist_util.h:363
size_t Size() const
Definition: threading_utils.h:84
histogram of gradient statistics for multiple nodes
Definition: hist_util.h:436
void Reset(size_t nthreads, size_t nodes, const BlockedSpace2d &space, const std::vector< GHistRow > &targeted_hists)
Definition: hist_util.h:508
void MatchThreadsToNodes(const BlockedSpace2d &space)
Definition: hist_util.h:573
Definition: hist_util.h:377
HistogramCuts * p_cuts_
Definition: hist_util.h:134
std::vector< int > hist_was_used_
Marks which hists were used, it means that they should be merged. Contains only {true or false} value...
Definition: hist_util.h:655
GHistRow operator[](bst_uint nid) const
Definition: hist_util.h:439
common::Monitor monitor_
Definition: hist_util.h:45
std::vector< T > & HostVector()
void Build(DMatrix *dmat, uint32_t const max_num_bins)
void Resize(const size_t nBytesData)
Definition: hist_util.h:269
uint32_t operator[](size_t i) const
Definition: hist_util.h:228
Index()
Definition: hist_util.h:221
GHistIndexRow operator[](size_t i) const
Definition: hist_util.h:370
HistogramCuts DeviceSketch(int device, DMatrix *dmat, int max_bins, size_t sketch_batch_num_elements=0)
a collection of columns, with support for construction from GHistIndexMatrix.
Definition: column_matrix.h:99
HostDeviceVector< float > min_vals_
Definition: hist_util.h:51
BinTypeSize
Definition: hist_util.h:214
SparseCuts(HistogramCuts *container)
Definition: hist_util.h:174
uint32_t BinIdx
Definition: hist_util.h:44
std::vector< GHistRow > targeted_hists_
Contains histograms for final results.
Definition: hist_util.h:660
namespace of xgboost
Definition: base.h:102
size_t Size() const
Definition: hist_util.h:266
data structure to store an instance set, a subset of rows (instances) associated with a particular no...
Definition: row_set.h:24
uint32_t * Offset() const
Definition: hist_util.h:260
const std::vector< T > & ConstHostVector() const
Definition: threading_utils.h:54
Timing utility used to measure total method execution time over the lifetime of the containing object...
Definition: timer.h:47
std::vector< GHistRow > hist_memory_
Allocated memory for histograms used for construction.
Definition: hist_util.h:662
HistogramCuts AdapterDeviceSketch(AdapterT *adapter, int num_bins, float missing, size_t sketch_batch_num_elements=0)
size_t max_num_bins
Definition: hist_util.h:324
uint32_t GetNumBins() const
Definition: hist_util.h:689
CutsBuilder(HistogramCuts *p_cuts)
Definition: hist_util.h:137
void AddCutPoint(WQSketch::SummaryContainer const &summary, int max_bin)
Definition: hist_util.h:153
std::vector< size_t > row_ptr
row pointer to rows by element position
Definition: hist_util.h:316
Stores temporary histograms to compute them in parallel Supports processing multiple tree-nodes for n...
Definition: hist_util.h:497
void AllocateAdditionalHistograms()
Definition: hist_util.h:595
Element from a sparse vector.
Definition: data.h:167
uint32_t bst_uint
unsigned integer type used for feature index.
Definition: base.h:105
Monitor monitor_
Definition: hist_util.h:192
HostDeviceVector< uint32_t > cut_ptrs_
Definition: hist_util.h:49
void Init(size_t nbins)
Definition: hist_util.h:499
void SubtractionHist(GHistRow dst, const GHistRow src1, const GHistRow src2, size_t begin, size_t end)
Compute Subtraction: dst = src1 - src2 in range [begin, end)
preprocessed global index matrix, in CSR format
Definition: hist_util.h:314
std::vector< float > const & Values() const
Definition: hist_util.h:97
bst_feature_t index
feature index
Definition: data.h:169
bst_float fvalue
feature value
Definition: data.h:171
const uint32_t * index
Definition: hist_util.h:364
void GetFeatureCounts(size_t *counts) const
Definition: hist_util.h:343
void Resize(size_t new_size, T v=T())
std::map< std::pair< size_t, size_t >, size_t > tid_nid_to_hist_
map pair {tid, nid} to index of allocated histogram from hist_memory_
Definition: hist_util.h:664
void ResizeOffset(const size_t nDisps)
Definition: hist_util.h:273
Definition: hist_util.h:217
bool RowExists(bst_uint nid) const
Definition: hist_util.h:448
GHistIndexBlock(const size_t *row_ptr, const uint32_t *index)
Definition: hist_util.h:366
Definition: hist_util.h:36
DMatrix * p_fmat
Definition: hist_util.h:323