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" 41 T* ptr =
static_cast<T*
>(std::malloc(n *
sizeof(T)));
42 CHECK(ptr) <<
"Failed to allocate memory";
44 std::memcpy(ptr, ptr_, n_ *
sizeof(T));
88 const T*
end()
const {
123 *
this = std::forward<HistogramCuts&&>(that);
127 monitor_ = std::move(that.
monitor_);
135 void Build(
DMatrix* dmat, uint32_t
const max_num_bins);
138 return cut_ptrs_.at(feature+1) - cut_ptrs_[feature];
144 std::vector<uint32_t>
const&
Ptrs()
const {
return cut_ptrs_; }
145 std::vector<float>
const&
Values()
const {
return cut_values_; }
146 std::vector<float>
const&
MinValues()
const {
return min_vals_; }
151 auto beg = cut_ptrs_.at(column_id);
152 auto end = cut_ptrs_.at(column_id + 1);
153 auto it = std::upper_bound(cut_values_.cbegin() + beg, cut_values_.cbegin() +
end, value);
154 if (it == cut_values_.cend()) {
155 it = cut_values_.cend() - 1;
157 BinIdx idx = it - cut_values_.cbegin();
179 static bool UseGroup(
DMatrix* dmat);
186 std::vector<bst_uint>
const& group_ptr,
size_t const base_rowid) {
187 using KIt = std::vector<bst_uint>::const_iterator;
188 KIt res = std::lower_bound(group_ptr.cbegin(), group_ptr.cend() - 1, base_rowid);
190 bool const found = res != group_ptr.cend() - 1;
192 LOG(FATAL) <<
"Row " << base_rowid <<
" does not lie in any group!";
194 uint32_t group_ind = std::distance(group_ptr.cbegin(), res);
199 if (summary.size > 1 && summary.size <= 16) {
201 for (
size_t i = 1; i < summary.size; ++i) {
202 bst_float cpt = (summary.data[i].value + summary.data[i - 1].value) / 2.0f;
208 for (
size_t i = 2; i < summary.size; ++i) {
209 bst_float cpt = summary.data[i - 1].value;
218 virtual void Build(
DMatrix* dmat, uint32_t
const max_num_bins) = 0;
224 static std::vector<size_t> LoadBalance(
SparsePage const& page,
size_t const nthreads);
230 monitor_.
Init(__FUNCTION__);
234 void Concat(std::vector<std::unique_ptr<SparseCuts>>
const& cuts, uint32_t n_cols);
237 uint32_t max_num_bins,
238 bool const use_group_ind,
239 uint32_t beg, uint32_t
end, uint32_t thread_id);
240 void Build(
DMatrix* dmat, uint32_t
const max_num_bins)
override;
251 monitor_.
Init(__FUNCTION__);
253 void Init(std::vector<WXQSketch>* sketchs, uint32_t max_num_bins);
254 void Build(
DMatrix* p_fmat, uint32_t max_num_bins)
override;
283 void Init(
DMatrix* p_fmat,
int max_num_bins);
286 return {&index[0] + row_ptr[i],
288 row_ptr[i + 1] - row_ptr[i])};
291 auto nfeature = cut.
Ptrs().size() - 1;
292 for (
unsigned fid = 0; fid < nfeature; ++fid) {
293 auto ibegin = cut.
Ptrs()[fid];
294 auto iend = cut.
Ptrs()[fid + 1];
295 for (
auto i = ibegin; i < iend; ++i) {
296 counts[fid] += hit_count[i];
302 std::vector<size_t> hit_count_tloc_;
310 : row_ptr(row_ptr), index(index) {}
314 return {&index[0] + row_ptr[i], row_ptr[i + 1] - row_ptr[i]};
324 const tree::TrainParam& param);
327 return {blocks_[i].row_ptr_begin, blocks_[i].index_begin};
331 return blocks_.size();
335 std::vector<size_t> row_ptr_;
336 std::vector<uint32_t> index_;
339 const size_t* row_ptr_begin;
340 const size_t* row_ptr_end;
341 const uint32_t* index_begin;
342 const uint32_t* index_end;
344 std::vector<Block> blocks_;
383 constexpr uint32_t kMax = std::numeric_limits<uint32_t>::max();
384 CHECK_NE(row_ptr_[nid], kMax);
385 tree::GradStats* ptr =
386 const_cast<tree::GradStats*
>(dmlc::BeginPtr(data_) + row_ptr_[nid]);
387 return {ptr, nbins_};
392 const uint32_t k_max = std::numeric_limits<uint32_t>::max();
393 return (nid < row_ptr_.size() && row_ptr_[nid] != k_max);
398 if (nbins_ != nbins) {
409 constexpr uint32_t kMax = std::numeric_limits<uint32_t>::max();
410 if (nid >= row_ptr_.size()) {
411 row_ptr_.resize(nid + 1, kMax);
413 CHECK_EQ(row_ptr_[nid], kMax);
415 if (data_.size() < nbins_ * (nid + 1)) {
416 data_.resize(nbins_ * (nid + 1));
419 row_ptr_[nid] = nbins_ * n_nodes_added_;
427 uint32_t n_nodes_added_ = 0;
429 std::vector<tree::GradStats> data_;
432 std::vector<size_t> row_ptr_;
443 if (nbins != nbins_) {
444 hist_buffer_.Init(nbins);
452 const std::vector<GHistRow>& targeted_hists) {
453 hist_buffer_.Init(nbins_);
454 tid_nid_to_hist_.clear();
455 hist_memory_.clear();
456 threads_to_nids_map_.clear();
458 targeted_hists_ = targeted_hists;
460 CHECK_EQ(nodes, targeted_hists.size());
463 nthreads_ = nthreads;
465 MatchThreadsToNodes(space);
466 AllocateAdditionalHistograms();
467 MatchNodeNidPairToHist();
469 hist_was_used_.resize(nthreads * nodes_);
470 std::fill(hist_was_used_.begin(), hist_was_used_.end(),
static_cast<int>(
false));
475 CHECK_LT(nid, nodes_);
476 CHECK_LT(tid, nthreads_);
478 size_t idx = tid_nid_to_hist_.at({tid, nid});
481 if (!hist_was_used_[tid * nodes_ + nid]) {
483 hist_was_used_[tid * nodes_ + nid] =
static_cast<int>(
true);
491 CHECK_GT(end, begin);
492 CHECK_LT(nid, nodes_);
494 GHistRow dst = targeted_hists_[nid];
496 bool is_updated =
false;
497 for (
size_t tid = 0; tid < nthreads_; ++tid) {
498 if (hist_was_used_[tid * nodes_ + nid]) {
500 const size_t idx = tid_nid_to_hist_.at({tid, nid});
517 const size_t space_size = space.
Size();
518 const size_t chunck_size = space_size / nthreads_ + !!(space_size % nthreads_);
520 threads_to_nids_map_.resize(nthreads_ * nodes_,
false);
522 for (
size_t tid = 0; tid < nthreads_; ++tid) {
523 size_t begin = chunck_size * tid;
524 size_t end = std::min(begin + chunck_size, space_size);
526 if (begin < space_size) {
530 for (
size_t nid = nid_begin; nid <= nid_end; ++nid) {
532 threads_to_nids_map_[tid * nodes_ + nid] =
true;
539 size_t hist_allocated_additionally = 0;
541 for (
size_t nid = 0; nid < nodes_; ++nid) {
542 int nthreads_for_nid = 0;
544 for (
size_t tid = 0; tid < nthreads_; ++tid) {
545 if (threads_to_nids_map_[tid * nodes_ + nid]) {
554 hist_allocated_additionally += std::max<int>(0, nthreads_for_nid - 1);
557 for (
size_t i = 0; i < hist_allocated_additionally; ++i) {
558 hist_buffer_.AddHistRow(i);
563 size_t hist_total = 0;
564 size_t hist_allocated_additionally = 0;
566 for (
size_t nid = 0; nid < nodes_; ++nid) {
567 bool first_hist =
true;
568 for (
size_t tid = 0; tid < nthreads_; ++tid) {
569 if (threads_to_nids_map_[tid * nodes_ + nid]) {
571 hist_memory_.push_back(targeted_hists_[nid]);
574 hist_memory_.push_back(hist_buffer_[hist_allocated_additionally]);
575 hist_allocated_additionally++;
578 tid_nid_to_hist_[{tid, nid}] = hist_total++;
579 CHECK_EQ(hist_total, hist_memory_.size());
588 size_t nthreads_ = 0;
616 inline void Init(
size_t nthread, uint32_t nbins) {
622 void BuildHist(
const std::vector<GradientPair>& gpair,
627 void BuildBlockHist(
const std::vector<GradientPair>& gpair,
648 #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:397
void ReduceHist(size_t nid, size_t begin, size_t end)
Definition: hist_util.h:490
DenseCuts(HistogramCuts *container)
Definition: hist_util.h:249
std::vector< float > min_vals_
Definition: hist_util.h:117
void AddCutPoint(WXQSketch::SummaryContainer const &summary)
Definition: hist_util.h:198
float bst_float
float type, used for storing statistics
Definition: base.h:111
std::vector< uint32_t > cut_ptrs_
Definition: hist_util.h:116
XGBOOST_DEVICE constexpr index_type size() const __span_noexcept
Definition: span.h:521
T * end()
Definition: hist_util.h:84
T back() const
Definition: hist_util.h:63
HistCollection hist_buffer_
Buffer for additional histograms for Parallel processing.
Definition: hist_util.h:592
size_t GetNumBlock() const
Definition: hist_util.h:330
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:137
Definition: hist_util.h:305
static uint32_t SearchGroupIndFromRow(std::vector< bst_uint > const &group_ptr, size_t const base_rowid)
Definition: hist_util.h:185
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:408
std::size_t index_type
Definition: span.h:394
std::vector< bool > threads_to_nids_map_
Buffer for additional histograms for Parallel processing.
Definition: hist_util.h:601
std::vector< uint32_t > const & Ptrs() const
Definition: hist_util.h:144
util to compute quantiles
The input data structure of xgboost.
BinIdx SearchBin(Entry const &e)
Definition: hist_util.h:161
Definition: hist_util.h:34
HistogramCuts cut
The corresponding cuts.
Definition: hist_util.h:281
void MatchNodeNidPairToHist()
Definition: hist_util.h:562
Internal data structured used by XGBoost during training. There are two ways to create a customized D...
Definition: data.h:428
size_t GetFirstDimension(size_t i) const
Definition: threading_utils.h:87
Cut configuration for dense dataset.
Definition: hist_util.h:244
std::vector< uint32_t > index
The index data.
Definition: hist_util.h:277
In-memory storage unit of sparse batch, stored in CSR format.
Definition: data.h:188
const T * begin() const
Definition: hist_util.h:80
HistogramCuts & operator=(HistogramCuts &&that) noexcept(true)
Definition: hist_util.h:126
Definition: hist_util.h:172
std::vector< size_t > hit_count
hit count of each index
Definition: hist_util.h:279
~SimpleArray()
Definition: hist_util.h:35
Quantile sketch use WXQSummary.
Definition: quantile.h:839
span class implementation, based on ISO++20 span<T>. The interface should be the same.
Definition: span.h:115
T * data()
Definition: hist_util.h:67
builder for histograms of gradient statistics
Definition: hist_util.h:613
GHistIndexRow operator[](size_t i) const
Definition: hist_util.h:285
std::vector< float > const & MinValues() const
Definition: hist_util.h:146
std::vector< bst_float > cut_values_
Definition: hist_util.h:115
GHistIndexBlock operator[](size_t i) const
Definition: hist_util.h:326
XGBOOST_DEVICE constexpr pointer data() const __span_noexcept
Definition: span.h:516
Quick Utility to compute subset of rows.
GHistRow GetInitializedHist(size_t tid, size_t nid)
Definition: hist_util.h:474
void Init(std::string label)
Definition: timer.h:82
size_t TotalBins() const
Definition: hist_util.h:148
HistogramCuts(HistogramCuts &&that) noexcept(true)
Definition: hist_util.h:122
size_t size() const
Definition: hist_util.h:59
Cut configuration for sparse dataset.
Definition: hist_util.h:222
const size_t * row_ptr
Definition: hist_util.h:306
void resize(size_t n)
Definition: hist_util.h:40
const T * end() const
Definition: hist_util.h:88
size_t Size() const
Definition: threading_utils.h:82
histogram of gradient statistics for multiple nodes
Definition: hist_util.h:379
void Reset(size_t nthreads, size_t nodes, const BlockedSpace2d &space, const std::vector< GHistRow > &targeted_hists)
Definition: hist_util.h:451
void MatchThreadsToNodes(const BlockedSpace2d &space)
Definition: hist_util.h:516
Definition: hist_util.h:320
HistogramCuts * p_cuts_
Definition: hist_util.h:177
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:598
GHistRow operator[](bst_uint nid) const
Definition: hist_util.h:382
T * begin()
Definition: hist_util.h:76
common::Monitor monitor_
Definition: hist_util.h:113
size_t DeviceSketch(int device, int max_bin, int gpu_batch_nrows, DMatrix *dmat, HistogramCuts *hmat)
Builds the cut matrix on the GPU.
GHistIndexRow operator[](size_t i) const
Definition: hist_util.h:313
a collection of columns, with support for construction from GHistIndexMatrix.
Definition: column_matrix.h:64
const T * data() const
Definition: hist_util.h:71
SparseCuts(HistogramCuts *container)
Definition: hist_util.h:228
uint32_t BinIdx
Definition: hist_util.h:112
std::vector< GHistRow > targeted_hists_
Contains histograms for final results.
Definition: hist_util.h:603
namespace of xgboost
Definition: base.h:102
data structure to store an instance set, a subset of rows (instances) associated with a particular no...
Definition: row_set.h:23
Definition: threading_utils.h:52
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:605
CutsBuilder(HistogramCuts *p_cuts)
Definition: hist_util.h:182
void Init(size_t nthread, uint32_t nbins)
Definition: hist_util.h:616
std::vector< size_t > row_ptr
row pointer to rows by element position
Definition: hist_util.h:275
Stores temporary histograms to compute them in parallel Supports processing multiple tree-nodes for n...
Definition: hist_util.h:440
void AllocateAdditionalHistograms()
Definition: hist_util.h:538
Element from a sparse vector.
Definition: data.h:142
T & operator[](size_t idx)
Definition: hist_util.h:51
uint32_t bst_uint
unsigned integer type used for feature index.
Definition: base.h:105
Monitor monitor_
Definition: hist_util.h:246
void Init(size_t nbins)
Definition: hist_util.h:442
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)
uint32_t GetNumBins()
Definition: hist_util.h:634
preprocessed global index matrix, in CSR format Transform floating values to integer index in histogr...
Definition: hist_util.h:273
std::vector< float > const & Values() const
Definition: hist_util.h:145
bst_feature_t index
feature index
Definition: data.h:144
bst_float fvalue
feature value
Definition: data.h:146
const uint32_t * index
Definition: hist_util.h:307
void GetFeatureCounts(size_t *counts) const
Definition: hist_util.h:290
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:607
bool RowExists(bst_uint nid) const
Definition: hist_util.h:391
GHistIndexBlock(const size_t *row_ptr, const uint32_t *index)
Definition: hist_util.h:309
Definition: hist_util.h:104
T & operator[](size_t idx) const
Definition: hist_util.h:55
BinIdx SearchBin(float value, uint32_t column_id)
Definition: hist_util.h:150