Go to the documentation of this file.
7 #ifndef XGBOOST_COMMON_HIST_UTIL_H_
8 #define XGBOOST_COMMON_HIST_UTIL_H_
22 #include "../tree/param.h"
25 #include "../include/rabit/rabit.h"
58 *
this = std::forward<HistogramCuts&&>(that);
98 auto it = std::upper_bound(values.cbegin() + beg, values.cbegin() + end, value);
99 BinIdx idx = it - values.cbegin();
113 auto const& info = m->
Info();
114 const auto threads = omp_get_max_threads();
115 std::vector<std::vector<bst_row_t>> column_sizes(threads);
116 for (
auto& column : column_sizes) {
117 column.resize(info.num_col_, 0);
119 std::vector<bst_row_t> reduced(info.num_col_, 0);
121 auto const &entries_per_column =
123 for (
size_t i = 0; i < entries_per_column.size(); ++i) {
124 reduced[i] += entries_per_column[i];
151 if (offset_ptr_ !=
nullptr) {
152 return func_(data_ptr_, i) + offset_ptr_[i%p_];
154 return func_(data_ptr_, i);
158 binTypeSize_ = binTypeSize;
159 switch (binTypeSize) {
161 func_ = &GetValueFromUint8;
164 func_ = &GetValueFromUint16;
167 func_ = &GetValueFromUint32;
180 return static_cast<T*
>(data_ptr_);
186 return offset_.size();
189 return data_.size() / (binTypeSize_);
192 data_.resize(nBytesData);
193 data_ptr_ =
reinterpret_cast<void*
>(data_.data());
196 offset_.resize(nDisps);
197 offset_ptr_ = offset_.data();
200 std::vector<uint8_t>::const_iterator
begin()
const {
201 return data_.begin();
203 std::vector<uint8_t>::const_iterator
end()
const {
208 static uint32_t GetValueFromUint8(
void *t,
size_t i) {
209 return reinterpret_cast<uint8_t*
>(t)[i];
211 static uint32_t GetValueFromUint16(
void* t,
size_t i) {
212 return reinterpret_cast<uint16_t*
>(t)[i];
214 static uint32_t GetValueFromUint32(
void* t,
size_t i) {
215 return reinterpret_cast<uint32_t*
>(t)[i];
218 using Func = uint32_t (*)(
void*, size_t);
220 std::vector<uint8_t> data_;
221 std::vector<uint32_t> offset_;
225 uint32_t* offset_ptr_ {
nullptr};
251 template <
typename BinIdxType,
typename GetOffset>
253 size_t batch_threads,
const SparsePage &batch,
254 size_t rbegin,
size_t nbins, GetOffset get_offset) {
257 const size_t batch_size = batch.
Size();
258 CHECK_LT(batch_size, offset_vec.size());
259 BinIdxType* index_data = index_data_span.
data();
260 #pragma omp parallel for num_threads(batch_threads) schedule(static)
261 for (
omp_ulong i = 0; i < batch_size; ++i) {
262 const int tid = omp_get_thread_num();
263 size_t ibegin =
row_ptr[rbegin + i];
264 size_t iend =
row_ptr[rbegin + i + 1];
265 const size_t size = offset_vec[i + 1] - offset_vec[i];
267 CHECK_EQ(ibegin + inst.
size(), iend);
270 index_data[ibegin + j] = get_offset(idx, j);
271 ++hit_count_tloc_[tid * nbins + idx];
280 auto nfeature =
cut.
Ptrs().size() - 1;
281 for (
unsigned fid = 0; fid < nfeature; ++fid) {
283 auto iend =
cut.
Ptrs()[fid + 1];
284 for (
auto i = ibegin; i < iend; ++i) {
294 std::vector<size_t> hit_count_tloc_;
298 template <
typename GradientIndex>
300 GradientIndex
const &data,
301 uint32_t
const fidx_begin,
302 uint32_t
const fidx_end) {
303 uint32_t previous_middle = std::numeric_limits<uint32_t>::max();
304 while (end != begin) {
305 auto middle = begin + (end - begin) / 2;
306 if (middle == previous_middle) {
309 previous_middle = middle;
311 auto gidx = data[middle];
313 if (gidx >= fidx_begin && gidx < fidx_end) {
314 return static_cast<int32_t
>(gidx);
315 }
else if (gidx < fidx_begin) {
344 const tree::TrainParam& param);
347 return {blocks_[i].row_ptr_begin, blocks_[i].index_begin};
351 return blocks_.size();
355 std::vector<size_t> row_ptr_;
356 std::vector<uint32_t> index_;
359 const size_t* row_ptr_begin;
360 const size_t* row_ptr_end;
361 const uint32_t* index_begin;
362 const uint32_t* index_end;
364 std::vector<Block> blocks_;
367 template<
typename GradientSumT>
373 template<
typename GradientSumT>
379 template<
typename GradientSumT>
381 size_t begin,
size_t end);
386 template<
typename GradientSumT>
388 size_t begin,
size_t end);
393 template<
typename GradientSumT>
396 size_t begin,
size_t end);
401 template<
typename GradientSumT>
409 constexpr uint32_t kMax = std::numeric_limits<uint32_t>::max();
410 const size_t id = row_ptr_[nid];
413 if (contiguous_allocation_) {
414 ptr =
const_cast<GradientPairT*
>(data_[0].data() + nbins_*id);
418 return {ptr, nbins_};
423 const uint32_t k_max = std::numeric_limits<uint32_t>::max();
424 return (nid < row_ptr_.size() && row_ptr_[nid] != k_max);
429 if (nbins_ != nbins) {
440 constexpr uint32_t kMax = std::numeric_limits<uint32_t>::max();
441 if (nid >= row_ptr_.size()) {
442 row_ptr_.resize(nid + 1, kMax);
444 CHECK_EQ(row_ptr_[nid], kMax);
446 if (data_.size() < (nid + 1)) {
447 data_.resize((nid + 1));
450 row_ptr_[nid] = n_nodes_added_;
455 if (data_[row_ptr_[nid]].size() == 0) {
456 data_[row_ptr_[nid]].resize(nbins_, {0, 0});
461 const size_t new_size = nbins_*data_.size();
462 contiguous_allocation_ =
true;
463 if (data_[0].size() != new_size) {
464 data_[0].resize(new_size);
472 uint32_t n_nodes_added_ = 0;
474 bool contiguous_allocation_ =
false;
476 std::vector<std::vector<GradientPairT>> data_;
479 std::vector<size_t> row_ptr_;
487 template<
typename GradientSumT>
502 const std::vector<GHistRowT>& targeted_hists) {
509 CHECK_EQ(nodes, targeted_hists.size());
543 CHECK_GT(end, begin);
548 bool is_updated =
false;
549 for (
size_t tid = 0; tid <
nthreads_; ++tid) {
570 const size_t space_size = space.
Size();
575 for (
size_t tid = 0; tid <
nthreads_; ++tid) {
576 size_t begin = chunck_size * tid;
577 size_t end = std::min(begin + chunck_size, space_size);
579 if (begin < space_size) {
583 for (
size_t nid = nid_begin; nid <= nid_end; ++nid) {
592 size_t hist_allocated_additionally = 0;
594 for (
size_t nid = 0; nid <
nodes_; ++nid) {
595 int nthreads_for_nid = 0;
597 for (
size_t tid = 0; tid <
nthreads_; ++tid) {
607 hist_allocated_additionally += std::max<int>(0, nthreads_for_nid - 1);
610 for (
size_t i = 0; i < hist_allocated_additionally; ++i) {
616 size_t hist_allocated_additionally = 0;
618 for (
size_t nid = 0; nid <
nodes_; ++nid) {
619 bool first_hist =
true;
620 for (
size_t tid = 0; tid <
nthreads_; ++tid) {
662 template<
typename GradientSumT>
668 GHistBuilder(
size_t nthread, uint32_t nbins) : nthread_{nthread}, nbins_{nbins} {}
671 void BuildHist(
const std::vector<GradientPair>& gpair,
672 const RowSetCollection::Elem row_indices,
673 const GHistIndexMatrix& gmat,
678 const RowSetCollection::Elem row_indices,
679 const GHistIndexBlockMatrix& gmatb,
692 size_t nthread_ { 0 };
694 uint32_t nbins_ { 0 };
698 #endif // XGBOOST_COMMON_HIST_UTIL_H_
Definition: hist_util.h:340
void MakeCuts(HistogramCuts *cuts)
std::vector< size_t > row_ptr
row pointer to rows by element position
Definition: hist_util.h:238
bst_feature_t index
feature index
Definition: data.h:186
BinTypeSize
Definition: hist_util.h:136
util to compute quantiles
virtual MetaInfo & Info()=0
meta information of the dataset
#define XGBOOST_HOST_DEV_INLINE
Definition: base.h:91
size_t GetNumBlock() const
Definition: hist_util.h:350
void IncrementHist(GHistRow< GradientSumT > dst, const GHistRow< GradientSumT > add, size_t begin, size_t end)
Increment hist as dst += add in range [begin, end)
Implementation of gradient statistics pair. Template specialisation may be used to overload different...
Definition: base.h:141
void AllocateData(bst_uint nid)
Definition: hist_util.h:454
GHistRowT GetInitializedHist(size_t tid, size_t nid)
Definition: hist_util.h:523
size_t Size() const
Definition: data.h:275
Definition: quantile.h:704
size_t nodes_
number of nodes which will be processed in parallel
Definition: hist_util.h:638
size_t TotalBins() const
Definition: hist_util.h:90
In-memory storage unit of sparse batch, stored in CSR format.
Definition: data.h:243
size_t Size() const
Definition: threading_utils.h:84
HistogramCuts(HistogramCuts const &that)
Definition: hist_util.h:48
@ kUint16BinsTypeSize
Definition: hist_util.h:138
void AllocateAllData()
Definition: hist_util.h:460
uint32_t BinIdx
Definition: hist_util.h:39
Element from a sparse vector.
Definition: data.h:184
Quick Utility to compute subset of rows.
Definition: hist_util.h:37
DMatrix * p_fmat
Definition: hist_util.h:245
std::vector< bool > threads_to_nids_map_
Buffer for additional histograms for Parallel processing
Definition: hist_util.h:649
const size_t * row_ptr
Definition: hist_util.h:326
void ReduceHist(size_t nid, size_t begin, size_t end)
Definition: hist_util.h:542
Index index
The index data.
Definition: hist_util.h:240
void Reset(size_t nthreads, size_t nodes, const BlockedSpace2d &space, const std::vector< GHistRowT > &targeted_hists)
Definition: hist_util.h:501
void ResizeOffset(const size_t nDisps)
Definition: hist_util.h:195
Definition: hist_util.h:142
void Init(const GHistIndexMatrix &gmat, const ColumnMatrix &colmat, const tree::TrainParam ¶m)
HistogramCuts(HistogramCuts &&that) noexcept(true)
Definition: hist_util.h:57
void Resize(const size_t nBytesData)
Definition: hist_util.h:191
HistogramCuts cut
The corresponding cuts.
Definition: hist_util.h:244
HostDeviceVector< uint32_t > cut_ptrs_
Definition: hist_util.h:43
size_t GetFirstDimension(size_t i) const
Definition: threading_utils.h:89
BinIdx SearchBin(float value, uint32_t column_id) const
Definition: hist_util.h:94
std::map< std::pair< size_t, size_t >, int > tid_nid_to_hist_
map pair {tid, nid} to index of allocated histogram from hist_buffer_ and targeted_hists_,...
Definition: hist_util.h:656
void GetFeatureCounts(size_t *counts) const
Definition: hist_util.h:279
void Init(DMatrix *p_fmat, int max_num_bins)
void CopyHist(GHistRow< GradientSumT > dst, const GHistRow< GradientSumT > src, size_t begin, size_t end)
Copy hist from src to dst in range [begin, end)
Internal data structured used by XGBoost during training.
Definition: data.h:454
static std::vector< bst_row_t > CalcColumnSize(SparsePage const &page, bst_feature_t const n_columns, size_t const nthreads)
a collection of columns, with support for construction from GHistIndexMatrix.
Definition: column_matrix.h:101
dmlc::omp_ulong omp_ulong
define unsigned long for openmp loop
Definition: base.h:268
const uint32_t * index
Definition: hist_util.h:327
Definition: threading_utils.h:54
uint32_t * Offset() const
Definition: hist_util.h:182
uint32_t GetNumBins() const
Definition: hist_util.h:686
void AllocateAdditionalHistograms()
Definition: hist_util.h:591
void SetBinTypeSize(BinTypeSize binTypeSize)
Definition: hist_util.h:157
size_t Size() const
Definition: hist_util.h:188
T * data() const
Definition: hist_util.h:179
std::vector< T > & HostVector()
void SetIndexData(common::Span< BinIdxType > index_data_span, size_t batch_threads, const SparsePage &batch, size_t rbegin, size_t nbins, GetOffset get_offset)
Definition: hist_util.h:252
preprocessed global index matrix, in CSR format
Definition: hist_util.h:236
void AddHistRow(bst_uint nid)
Definition: hist_util.h:439
std::vector< uint32_t > const & Ptrs() const
Definition: hist_util.h:86
void Init(uint32_t nbins)
Definition: hist_util.h:428
histogram of gradient statistics for multiple nodes
Definition: hist_util.h:402
HostDeviceVector< float > min_vals_
Definition: hist_util.h:45
GHistRowT operator[](bst_uint nid) const
Definition: hist_util.h:408
HistogramCuts & operator=(HistogramCuts &&that) noexcept(true)
Definition: hist_util.h:71
int32_t XGBOOST_HOST_DEV_INLINE BinarySearchBin(bst_uint begin, bst_uint end, GradientIndex const &data, uint32_t const fidx_begin, uint32_t const fidx_end)
Definition: hist_util.h:299
Stores temporary histograms to compute them in parallel Supports processing multiple tree-nodes for n...
Definition: hist_util.h:488
GHistBuilder(size_t nthread, uint32_t nbins)
Definition: hist_util.h:668
uint32_t operator[](size_t i) const
Definition: hist_util.h:150
bool RowExists(bst_uint nid) const
Definition: hist_util.h:422
GHistIndexBlock(const size_t *row_ptr, const uint32_t *index)
Definition: hist_util.h:329
void InitilizeHistByZeroes(GHistRow< GradientSumT > hist, size_t begin, size_t end)
fill a histogram by zeros
uint32_t FeatureBins(uint32_t feature) const
Definition: hist_util.h:78
std::vector< float > const & MinValues() const
Definition: hist_util.h:88
GHistIndexRow operator[](size_t i) const
Definition: hist_util.h:333
size_t nbins_
number of bins in each histogram
Definition: hist_util.h:634
Index & operator=(Index i)=delete
std::vector< size_t > hit_count
hit count of each index
Definition: hist_util.h:242
void MatchThreadsToNodes(const BlockedSpace2d &space)
Definition: hist_util.h:569
void Copy(const HostDeviceVector< T > &other)
void ResizeIndex(const size_t n_index, const bool isDense)
void SubtractionHist(GHistRow< GradientSumT > dst, const GHistRow< GradientSumT > src1, const GHistRow< GradientSumT > src2, size_t begin, size_t end)
Compute Subtraction: dst = src1 - src2 in range [begin, end)
size_t nthreads_
number of threads for parallel computation
Definition: hist_util.h:636
void MatchNodeNidPairToHist()
Definition: hist_util.h:615
void Resize(size_t new_size, T v=T())
HistogramCuts SketchOnDMatrix(DMatrix *m, int32_t max_bins)
Definition: hist_util.h:111
bool IsDense() const
Definition: hist_util.h:289
BinTypeSize GetBinTypeSize() const
Definition: hist_util.h:175
static bool UseGroup(MetaInfo const &info)
Definition: quantile.h:725
size_t max_num_bins
Definition: hist_util.h:246
void BuildBlockHist(const std::vector< GradientPair > &gpair, const RowSetCollection::Elem row_indices, const GHistIndexBlockMatrix &gmatb, GHistRowT hist)
GHistRow< GradientSumT > GHistRowT
Definition: hist_util.h:665
void BuildHist(const std::vector< GradientPair > &gpair, const RowSetCollection::Elem row_indices, const GHistIndexMatrix &gmat, GHistRowT hist, bool isDense)
span class implementation, based on ISO++20 span<T>. The interface should be the same.
Definition: span.h:137
@ kUint32BinsTypeSize
Definition: hist_util.h:139
The input data structure of xgboost.
GHistIndexBlock operator[](size_t i) const
Definition: hist_util.h:346
@ kUint8BinsTypeSize
Definition: hist_util.h:137
HostDeviceVector< bst_row_t > offset
Definition: data.h:246
Index()
Definition: hist_util.h:143
void Init(size_t nbins)
Definition: hist_util.h:492
BinIdx SearchBin(Entry const &e) const
Definition: hist_util.h:106
void PushRowPage(SparsePage const &page, MetaInfo const &info)
const std::vector< T > & ConstHostVector() const
constexpr XGBOOST_DEVICE index_type size() const __span_noexcept
Definition: span.h:542
constexpr XGBOOST_DEVICE pointer data() const __span_noexcept
Definition: span.h:537
HostDeviceVector< bst_float > cut_values_
Definition: hist_util.h:42
uint32_t bst_uint
unsigned integer type used for feature index.
Definition: base.h:113
Definition: hist_util.h:325
std::vector< GHistRowT > targeted_hists_
Contains histograms for final results
Definition: hist_util.h:651
bst_float fvalue
feature value
Definition: data.h:188
std::vector< uint8_t >::const_iterator begin() const
Definition: hist_util.h:200
HistCollection< GradientSumT > hist_buffer_
Buffer for additional histograms for Parallel processing
Definition: hist_util.h:640
BatchSet< T > GetBatches(const BatchParam ¶m={})
Gets batches. Use range based for loop over BatchSet to access individual batches.
HistogramCuts & operator=(HistogramCuts const &that)
Definition: hist_util.h:61
std::vector< uint8_t >::const_iterator end() const
Definition: hist_util.h:203
std::vector< float > const & Values() const
Definition: hist_util.h:87
HostDeviceVector< Entry > data
the data of the segments
Definition: data.h:248
void SubtractionTrick(GHistRowT self, GHistRowT sibling, GHistRowT parent)
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:646
size_t OffsetSize() const
Definition: hist_util.h:185
builder for histograms of gradient statistics
Definition: hist_util.h:663
namespace of xgboost
Definition: base.h:110