xgboost

hist_util.h
Go to the documentation of this file.
1
7 #ifndef XGBOOST_COMMON_HIST_UTIL_H_
8 #define XGBOOST_COMMON_HIST_UTIL_H_
9
10 #include <xgboost/data.h>
11 #include <xgboost/generic_parameters.h>
12 #include <limits>
13 #include <vector>
14 #include <algorithm>
15 #include <memory>
16 #include <utility>
17 #include <map>
18
19 #include "row_set.h"
20 #include "common.h"
21 #include "threading_utils.h"
22 #include "../tree/param.h"
23 #include "./quantile.h"
24 #include "./timer.h"
25 #include "../include/rabit/rabit.h"
26
27 namespace xgboost {
28 namespace common {
33 using GHistIndexRow = Span<uint32_t const>;
34
35 // A CSC matrix representing histogram cuts, used in CPU quantile hist.
36 // The cut values represent upper bounds of bins containing approximately equal numbers of elements
37 class HistogramCuts {
38 protected:
39 using BinIdx = uint32_t;
40
41 public:
42 HostDeviceVector<bst_float> cut_values_; // NOLINT
43 HostDeviceVector<uint32_t> cut_ptrs_; // NOLINT
44 // storing minimum value in a sketch set.
45 HostDeviceVector<float> min_vals_; // NOLINT
46
47 HistogramCuts();
48 HistogramCuts(HistogramCuts const& that) {
49 cut_values_.Resize(that.cut_values_.Size());
50 cut_ptrs_.Resize(that.cut_ptrs_.Size());
51 min_vals_.Resize(that.min_vals_.Size());
52 cut_values_.Copy(that.cut_values_);
53 cut_ptrs_.Copy(that.cut_ptrs_);
54 min_vals_.Copy(that.min_vals_);
55 }
56
57 HistogramCuts(HistogramCuts&& that) noexcept(true) {
58 *this = std::forward<HistogramCuts&&>(that);
59 }
60
61 HistogramCuts& operator=(HistogramCuts const& that) {
62 cut_values_.Resize(that.cut_values_.Size());
63 cut_ptrs_.Resize(that.cut_ptrs_.Size());
64 min_vals_.Resize(that.min_vals_.Size());
65 cut_values_.Copy(that.cut_values_);
66 cut_ptrs_.Copy(that.cut_ptrs_);
67 min_vals_.Copy(that.min_vals_);
68 return *this;
69 }
70
71 HistogramCuts& operator=(HistogramCuts&& that) noexcept(true) {
72 cut_ptrs_ = std::move(that.cut_ptrs_);
73 cut_values_ = std::move(that.cut_values_);
74 min_vals_ = std::move(that.min_vals_);
75 return *this;
76 }
77
78 uint32_t FeatureBins(uint32_t feature) const {
79 return cut_ptrs_.ConstHostVector().at(feature + 1) -
80 cut_ptrs_.ConstHostVector()[feature];
81 }
82
83 // Getters. Cuts should be of no use after building histogram indices, but currently
84 // it's deeply linked with quantile_hist, gpu sketcher and gpu_hist. So we preserve
85 // these for now.
86 std::vector<uint32_t> const& Ptrs() const { return cut_ptrs_.ConstHostVector(); }
87 std::vector<float> const& Values() const { return cut_values_.ConstHostVector(); }
88 std::vector<float> const& MinValues() const { return min_vals_.ConstHostVector(); }
89
90 size_t TotalBins() const { return cut_ptrs_.ConstHostVector().back(); }
91
92 // Return the index of a cut point that is strictly greater than the input
93 // value, or the last available index if none exists
94 BinIdx SearchBin(float value, uint32_t column_id) const {
95 auto beg = cut_ptrs_.ConstHostVector().at(column_id);
96 auto end = cut_ptrs_.ConstHostVector().at(column_id + 1);
97 const auto &values = cut_values_.ConstHostVector();
98 auto it = std::upper_bound(values.cbegin() + beg, values.cbegin() + end, value);
99 BinIdx idx = it - values.cbegin();
100 if (idx == end) {
101 idx -= 1;
102 }
103 return idx;
104 }
105
106 BinIdx SearchBin(Entry const& e) const {
107 return SearchBin(e.fvalue, e.index);
108 }
109 };
110
111 inline HistogramCuts SketchOnDMatrix(DMatrix *m, int32_t max_bins) {
112 HistogramCuts out;
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);
118 }
119 std::vector<bst_row_t> reduced(info.num_col_, 0);
120 for (auto const& page : m->GetBatches<SparsePage>()) {
121 auto const &entries_per_column =
122 HostSketchContainer::CalcColumnSize(page, info.num_col_, threads);
123 for (size_t i = 0; i < entries_per_column.size(); ++i) {
124 reduced[i] += entries_per_column[i];
125 }
126 }
127 HostSketchContainer container(reduced, max_bins,
128 HostSketchContainer::UseGroup(info));
129 for (auto const &page : m->GetBatches<SparsePage>()) {
130 container.PushRowPage(page, info);
131 }
132 container.MakeCuts(&out);
133 return out;
134 }
135
136 enum BinTypeSize {
137 kUint8BinsTypeSize = 1,
138 kUint16BinsTypeSize = 2,
139 kUint32BinsTypeSize = 4
140 };
141
142 struct Index {
143 Index() {
144 SetBinTypeSize(binTypeSize_);
145 }
146 Index(const Index& i) = delete;
147 Index& operator=(Index i) = delete;
148 Index(Index&& i) = delete;
149 Index& operator=(Index&& i) = delete;
150 uint32_t operator[](size_t i) const {
151 if (offset_ptr_ != nullptr) {
152 return func_(data_ptr_, i) + offset_ptr_[i%p_];
153 } else {
154 return func_(data_ptr_, i);
155 }
156 }
157 void SetBinTypeSize(BinTypeSize binTypeSize) {
158 binTypeSize_ = binTypeSize;
159 switch (binTypeSize) {
160 case kUint8BinsTypeSize:
161 func_ = &GetValueFromUint8;
162 break;
163 case kUint16BinsTypeSize:
164 func_ = &GetValueFromUint16;
165 break;
166 case kUint32BinsTypeSize:
167 func_ = &GetValueFromUint32;
168 break;
169 default:
170 CHECK(binTypeSize == kUint8BinsTypeSize ||
171 binTypeSize == kUint16BinsTypeSize ||
172 binTypeSize == kUint32BinsTypeSize);
173 }
174 }
175 BinTypeSize GetBinTypeSize() const {
176 return binTypeSize_;
177 }
178 template<typename T>
179 T* data() const { // NOLINT
180 return static_cast<T*>(data_ptr_);
181 }
182 uint32_t* Offset() const {
183 return offset_ptr_;
184 }
185 size_t OffsetSize() const {
186 return offset_.size();
187 }
188 size_t Size() const {
189 return data_.size() / (binTypeSize_);
190 }
191 void Resize(const size_t nBytesData) {
192 data_.resize(nBytesData);
193 data_ptr_ = reinterpret_cast<void*>(data_.data());
194 }
195 void ResizeOffset(const size_t nDisps) {
196 offset_.resize(nDisps);
197 offset_ptr_ = offset_.data();
198 p_ = nDisps;
199 }
200 std::vector<uint8_t>::const_iterator begin() const { // NOLINT
201 return data_.begin();
202 }
203 std::vector<uint8_t>::const_iterator end() const { // NOLINT
204 return data_.end();
205 }
206
207 private:
208 static uint32_t GetValueFromUint8(void *t, size_t i) {
209 return reinterpret_cast<uint8_t*>(t)[i];
210 }
211 static uint32_t GetValueFromUint16(void* t, size_t i) {
212 return reinterpret_cast<uint16_t*>(t)[i];
213 }
214 static uint32_t GetValueFromUint32(void* t, size_t i) {
215 return reinterpret_cast<uint32_t*>(t)[i];
216 }
217
218 using Func = uint32_t (*)(void*, size_t);
219
220 std::vector<uint8_t> data_;
221 std::vector<uint32_t> offset_; // size of this field is equal to number of features
222 void* data_ptr_;
223 BinTypeSize binTypeSize_ {kUint8BinsTypeSize};
224 size_t p_ {1};
225 uint32_t* offset_ptr_ {nullptr};
226 Func func_;
227 };
228
229
236 struct GHistIndexMatrix {
238 std::vector<size_t> row_ptr;
240 Index index;
242 std::vector<size_t> hit_count;
244 HistogramCuts cut;
245 DMatrix* p_fmat;
246 size_t max_num_bins;
247 // Create a global histogram matrix, given cut
248 void Init(DMatrix* p_fmat, int max_num_bins);
249
250 // specific method for sparse data as no posibility to reduce allocated memory
251 template <typename BinIdxType, typename GetOffset>
252 void SetIndexData(common::Span<BinIdxType> index_data_span,
253 size_t batch_threads, const SparsePage &batch,
254 size_t rbegin, size_t nbins, GetOffset get_offset) {
255 const xgboost::Entry *data_ptr = batch.data.HostVector().data();
256 const std::vector<bst_row_t> &offset_vec = batch.offset.HostVector();
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 ParallelFor(omp_ulong(batch_size), batch_threads, [&](omp_ulong i) {
261 const int tid = omp_get_thread_num();
262 size_t ibegin = row_ptr[rbegin + i];
263 size_t iend = row_ptr[rbegin + i + 1];
264 const size_t size = offset_vec[i + 1] - offset_vec[i];
265 SparsePage::Inst inst = {data_ptr + offset_vec[i], size};
266 CHECK_EQ(ibegin + inst.size(), iend);
267 for (bst_uint j = 0; j < inst.size(); ++j) {
268 uint32_t idx = cut.SearchBin(inst[j]);
269 index_data[ibegin + j] = get_offset(idx, j);
270 ++hit_count_tloc_[tid * nbins + idx];
271 }
272 });
273 }
274
275 void ResizeIndex(const size_t n_index,
276 const bool isDense);
277
278 inline void GetFeatureCounts(size_t* counts) const {
279 auto nfeature = cut.Ptrs().size() - 1;
280 for (unsigned fid = 0; fid < nfeature; ++fid) {
281 auto ibegin = cut.Ptrs()[fid];
282 auto iend = cut.Ptrs()[fid + 1];
283 for (auto i = ibegin; i < iend; ++i) {
284 counts[fid] += hit_count[i];
285 }
286 }
287 }
288 inline bool IsDense() const {
289 return isDense_;
290 }
291
292 private:
293 std::vector<size_t> hit_count_tloc_;
294 bool isDense_;
295 };
296
297 template <typename GradientIndex>
298 int32_t XGBOOST_HOST_DEV_INLINE BinarySearchBin(bst_uint begin, bst_uint end,
299 GradientIndex const &data,
300 uint32_t const fidx_begin,
301 uint32_t const fidx_end) {
302 uint32_t previous_middle = std::numeric_limits<uint32_t>::max();
303 while (end != begin) {
304 auto middle = begin + (end - begin) / 2;
305 if (middle == previous_middle) {
306 break;
307 }
308 previous_middle = middle;
309
310 auto gidx = data[middle];
311
312 if (gidx >= fidx_begin && gidx < fidx_end) {
313 return static_cast<int32_t>(gidx);
314 } else if (gidx < fidx_begin) {
315 begin = middle;
316 } else {
317 end = middle;
318 }
319 }
320 // Value is missing
321 return -1;
322 }
323
324 struct GHistIndexBlock {
325 const size_t* row_ptr;
326 const uint32_t* index;
327
328 inline GHistIndexBlock(const size_t* row_ptr, const uint32_t* index)
329 : row_ptr(row_ptr), index(index) {}
330
331 // get i-th row
332 inline GHistIndexRow operator[](size_t i) const {
333 return {&index[0] + row_ptr[i], row_ptr[i + 1] - row_ptr[i]};
334 }
335 };
336
337 class ColumnMatrix;
338
339 class GHistIndexBlockMatrix {
340 public:
341 void Init(const GHistIndexMatrix& gmat,
342 const ColumnMatrix& colmat,
343 const tree::TrainParam& param);
344
345 inline GHistIndexBlock operator[](size_t i) const {
346 return {blocks_[i].row_ptr_begin, blocks_[i].index_begin};
347 }
348
349 inline size_t GetNumBlock() const {
350 return blocks_.size();
351 }
352
353 private:
354 std::vector<size_t> row_ptr_;
355 std::vector<uint32_t> index_;
356 const HistogramCuts* cut_;
357 struct Block {
358 const size_t* row_ptr_begin;
359 const size_t* row_ptr_end;
360 const uint32_t* index_begin;
361 const uint32_t* index_end;
362 };
363 std::vector<Block> blocks_;
364 };
365
366 template<typename GradientSumT>
367 using GHistRow = Span<xgboost::detail::GradientPairInternal<GradientSumT> >;
368
372 template<typename GradientSumT>
373 void InitilizeHistByZeroes(GHistRow<GradientSumT> hist, size_t begin, size_t end);
374
378 template<typename GradientSumT>
379 void IncrementHist(GHistRow<GradientSumT> dst, const GHistRow<GradientSumT> add,
380 size_t begin, size_t end);
381
385 template<typename GradientSumT>
386 void CopyHist(GHistRow<GradientSumT> dst, const GHistRow<GradientSumT> src,
387 size_t begin, size_t end);
388
392 template<typename GradientSumT>
393 void SubtractionHist(GHistRow<GradientSumT> dst, const GHistRow<GradientSumT> src1,
394 const GHistRow<GradientSumT> src2,
395 size_t begin, size_t end);
396
400 template<typename GradientSumT>
401 class HistCollection {
402 public:
403 using GHistRowT = GHistRow<GradientSumT>;
404 using GradientPairT = xgboost::detail::GradientPairInternal<GradientSumT>;
405
406 // access histogram for i-th node
407 GHistRowT operator[](bst_uint nid) const {
408 constexpr uint32_t kMax = std::numeric_limits<uint32_t>::max();
409 const size_t id = row_ptr_[nid];
410 CHECK_NE(id, kMax);
411 GradientPairT* ptr = nullptr;
412 if (contiguous_allocation_) {
413 ptr = const_cast<GradientPairT*>(data_[0].data() + nbins_*id);
414 } else {
415 ptr = const_cast<GradientPairT*>(data_[id].data());
416 }
417 return {ptr, nbins_};
418 }
419
420 // have we computed a histogram for i-th node?
421 bool RowExists(bst_uint nid) const {
422 const uint32_t k_max = std::numeric_limits<uint32_t>::max();
423 return (nid < row_ptr_.size() && row_ptr_[nid] != k_max);
424 }
425
426 // initialize histogram collection
427 void Init(uint32_t nbins) {
428 if (nbins_ != nbins) {
429 nbins_ = nbins;
430 // quite expensive operation, so let's do this only once
431 data_.clear();
432 }
433 row_ptr_.clear();
434 n_nodes_added_ = 0;
435 }
436
437 // create an empty histogram for i-th node
438 void AddHistRow(bst_uint nid) {
439 constexpr uint32_t kMax = std::numeric_limits<uint32_t>::max();
440 if (nid >= row_ptr_.size()) {
441 row_ptr_.resize(nid + 1, kMax);
442 }
443 CHECK_EQ(row_ptr_[nid], kMax);
444
445 if (data_.size() < (nid + 1)) {
446 data_.resize((nid + 1));
447 }
448
449 row_ptr_[nid] = n_nodes_added_;
450 n_nodes_added_++;
451 }
452 // allocate thread local memory i-th node
453 void AllocateData(bst_uint nid) {
454 if (data_[row_ptr_[nid]].size() == 0) {
455 data_[row_ptr_[nid]].resize(nbins_, {0, 0});
456 }
457 }
458 // allocate common buffer contiguously for all nodes, need for single Allreduce call
459 void AllocateAllData() {
460 const size_t new_size = nbins_*data_.size();
461 contiguous_allocation_ = true;
462 if (data_[0].size() != new_size) {
463 data_[0].resize(new_size);
464 }
465 }
466
467 private:
469 uint32_t nbins_ = 0;
471 uint32_t n_nodes_added_ = 0;
473 bool contiguous_allocation_ = false;
474
475 std::vector<std::vector<GradientPairT>> data_;
476
478 std::vector<size_t> row_ptr_;
479 };
480
486 template<typename GradientSumT>
487 class ParallelGHistBuilder {
488 public:
489 using GHistRowT = GHistRow<GradientSumT>;
490
491 void Init(size_t nbins) {
492 if (nbins != nbins_) {
493 hist_buffer_.Init(nbins);
494 nbins_ = nbins;
495 }
496 }
497
498 // Add new elements if needed, mark all hists as unused
499 // targeted_hists - already allocated hists which should contain final results after Reduce() call
500 void Reset(size_t nthreads, size_t nodes, const BlockedSpace2d& space,
501 const std::vector<GHistRowT>& targeted_hists) {
502 hist_buffer_.Init(nbins_);
503 tid_nid_to_hist_.clear();
504 threads_to_nids_map_.clear();
505
506 targeted_hists_ = targeted_hists;
507
508 CHECK_EQ(nodes, targeted_hists.size());
509
510 nodes_ = nodes;
511 nthreads_ = nthreads;
512
513 MatchThreadsToNodes(space);
514 AllocateAdditionalHistograms();
515 MatchNodeNidPairToHist();
516
517 hist_was_used_.resize(nthreads * nodes_);
518 std::fill(hist_was_used_.begin(), hist_was_used_.end(), static_cast<int>(false));
519 }
520
521 // Get specified hist, initialize hist by zeros if it wasn't used before
522 GHistRowT GetInitializedHist(size_t tid, size_t nid) {
523 CHECK_LT(nid, nodes_);
524 CHECK_LT(tid, nthreads_);
525
526 int idx = tid_nid_to_hist_.at({tid, nid});
527 if (idx >= 0) {
528 hist_buffer_.AllocateData(idx);
529 }
530 GHistRowT hist = idx == -1 ? targeted_hists_[nid] : hist_buffer_[idx];
531
532 if (!hist_was_used_[tid * nodes_ + nid]) {
533 InitilizeHistByZeroes(hist, 0, hist.size());
534 hist_was_used_[tid * nodes_ + nid] = static_cast<int>(true);
535 }
536
537 return hist;
538 }
539
540 // Reduce following bins (begin, end] for nid-node in dst across threads
541 void ReduceHist(size_t nid, size_t begin, size_t end) {
542 CHECK_GT(end, begin);
543 CHECK_LT(nid, nodes_);
544
545 GHistRowT dst = targeted_hists_[nid];
546
547 bool is_updated = false;
548 for (size_t tid = 0; tid < nthreads_; ++tid) {
549 if (hist_was_used_[tid * nodes_ + nid]) {
550 is_updated = true;
551
552 int idx = tid_nid_to_hist_.at({tid, nid});
553 GHistRowT src = idx == -1 ? targeted_hists_[nid] : hist_buffer_[idx];
554
555 if (dst.data() != src.data()) {
556 IncrementHist(dst, src, begin, end);
557 }
558 }
559 }
560 if (!is_updated) {
561 // In distributed mode - some tree nodes can be empty on local machines,
562 // So we need just set local hist by zeros in this case
563 InitilizeHistByZeroes(dst, begin, end);
564 }
565 }
566
567 protected:
568 void MatchThreadsToNodes(const BlockedSpace2d& space) {
569 const size_t space_size = space.Size();
570 const size_t chunck_size = space_size / nthreads_ + !!(space_size % nthreads_);
571
572 threads_to_nids_map_.resize(nthreads_ * nodes_, false);
573
574 for (size_t tid = 0; tid < nthreads_; ++tid) {
575 size_t begin = chunck_size * tid;
576 size_t end = std::min(begin + chunck_size, space_size);
577
578 if (begin < space_size) {
579 size_t nid_begin = space.GetFirstDimension(begin);
580 size_t nid_end = space.GetFirstDimension(end-1);
581
582 for (size_t nid = nid_begin; nid <= nid_end; ++nid) {
583 // true - means thread 'tid' will work to compute partial hist for node 'nid'
584 threads_to_nids_map_[tid * nodes_ + nid] = true;
585 }
586 }
587 }
588 }
589
590 void AllocateAdditionalHistograms() {
591 size_t hist_allocated_additionally = 0;
592
593 for (size_t nid = 0; nid < nodes_; ++nid) {
594 int nthreads_for_nid = 0;
595
596 for (size_t tid = 0; tid < nthreads_; ++tid) {
597 if (threads_to_nids_map_[tid * nodes_ + nid]) {
598 nthreads_for_nid++;
599 }
600 }
601
602 // In distributed mode - some tree nodes can be empty on local machines,
603 // set nthreads_for_nid to 0 in this case.
604 // In another case - allocate additional (nthreads_for_nid - 1) histograms,
605 // because one is already allocated externally (will store final result for the node).
606 hist_allocated_additionally += std::max<int>(0, nthreads_for_nid - 1);
607 }
608
609 for (size_t i = 0; i < hist_allocated_additionally; ++i) {
610 hist_buffer_.AddHistRow(i);
611 }
612 }
613
614 void MatchNodeNidPairToHist() {
615 size_t hist_allocated_additionally = 0;
616
617 for (size_t nid = 0; nid < nodes_; ++nid) {
618 bool first_hist = true;
619 for (size_t tid = 0; tid < nthreads_; ++tid) {
620 if (threads_to_nids_map_[tid * nodes_ + nid]) {
621 if (first_hist) {
622 tid_nid_to_hist_[{tid, nid}] = -1;
623 first_hist = false;
624 } else {
625 tid_nid_to_hist_[{tid, nid}] = hist_allocated_additionally++;
626 }
627 }
628 }
629 }
630 }
631
633 size_t nbins_ = 0;
635 size_t nthreads_ = 0;
637 size_t nodes_ = 0;
639 HistCollection<GradientSumT> hist_buffer_;
645 std::vector<int> hist_was_used_;
646
648 std::vector<bool> threads_to_nids_map_;
650 std::vector<GHistRowT> targeted_hists_;
655 std::map<std::pair<size_t, size_t>, int> tid_nid_to_hist_;
656 };
657
661 template<typename GradientSumT>
662 class GHistBuilder {
663 public:
664 using GHistRowT = GHistRow<GradientSumT>;
665
666 GHistBuilder() = default;
667 GHistBuilder(size_t nthread, uint32_t nbins) : nthread_{nthread}, nbins_{nbins} {}
668
669 // construct a histogram via histogram aggregation
670 void BuildHist(const std::vector<GradientPair>& gpair,
671 const RowSetCollection::Elem row_indices,
672 const GHistIndexMatrix& gmat,
673 GHistRowT hist,
674 bool isDense);
675 // same, with feature grouping
676 void BuildBlockHist(const std::vector<GradientPair>& gpair,
677 const RowSetCollection::Elem row_indices,
678 const GHistIndexBlockMatrix& gmatb,
679 GHistRowT hist);
680 // construct a histogram via subtraction trick
681 void SubtractionTrick(GHistRowT self,
682 GHistRowT sibling,
683 GHistRowT parent);
684
685 uint32_t GetNumBins() const {
686 return nbins_;
687 }
688
689 private:
691 size_t nthread_ { 0 };
693 uint32_t nbins_ { 0 };
694 };
695 } // namespace common
696 } // namespace xgboost
697 #endif // XGBOOST_COMMON_HIST_UTIL_H_
xgboost::common::GHistIndexBlockMatrix
Definition: hist_util.h:339
xgboost::common::HostSketchContainer::MakeCuts
void MakeCuts(HistogramCuts *cuts)
xgboost::common::GHistIndexMatrix::row_ptr
std::vector< size_t > row_ptr
row pointer to rows by element position
Definition: hist_util.h:238
xgboost::Entry::index
bst_feature_t index
feature index
Definition: data.h:186
xgboost::common::BinTypeSize
BinTypeSize
Definition: hist_util.h:136
quantile.h
util to compute quantiles
xgboost::DMatrix::Info
virtual MetaInfo & Info()=0
meta information of the dataset
XGBOOST_HOST_DEV_INLINE
#define XGBOOST_HOST_DEV_INLINE
Definition: base.h:91
xgboost::common::GHistIndexBlockMatrix::GetNumBlock
size_t GetNumBlock() const
Definition: hist_util.h:349
xgboost::common::IncrementHist
void IncrementHist(GHistRow< GradientSumT > dst, const GHistRow< GradientSumT > add, size_t begin, size_t end)
Increment hist as dst += add in range [begin, end)
xgboost::detail::GradientPairInternal
Implementation of gradient statistics pair. Template specialisation may be used to overload different...
Definition: base.h:141
xgboost::common::HistCollection::AllocateData
void AllocateData(bst_uint nid)
Definition: hist_util.h:453
xgboost::common::ParallelGHistBuilder::GetInitializedHist
GHistRowT GetInitializedHist(size_t tid, size_t nid)
Definition: hist_util.h:522
xgboost::SparsePage::Size
size_t Size() const
Definition: data.h:266
xgboost::common::HostSketchContainer
Definition: quantile.h:704
xgboost::common::ParallelGHistBuilder::nodes_
size_t nodes_
number of nodes which will be processed in parallel
Definition: hist_util.h:637
xgboost::common::HistogramCuts::TotalBins
size_t TotalBins() const
Definition: hist_util.h:90
xgboost::SparsePage
In-memory storage unit of sparse batch, stored in CSR format.
Definition: data.h:243
xgboost::common::BlockedSpace2d::Size
size_t Size() const
Definition: threading_utils.h:84
xgboost::common::HistogramCuts::HistogramCuts
HistogramCuts(HistogramCuts const &that)
Definition: hist_util.h:48
xgboost::common::kUint16BinsTypeSize
@ kUint16BinsTypeSize
Definition: hist_util.h:138
xgboost::common::HistCollection::AllocateAllData
void AllocateAllData()
Definition: hist_util.h:459
xgboost::common::HistogramCuts::BinIdx
uint32_t BinIdx
Definition: hist_util.h:39
xgboost::Entry
Element from a sparse vector.
Definition: data.h:184
row_set.h
Quick Utility to compute subset of rows.
xgboost::common::HistogramCuts
Definition: hist_util.h:37
xgboost::common::GHistIndexMatrix::p_fmat
DMatrix * p_fmat
Definition: hist_util.h:245
xgboost::common::ParallelGHistBuilder::threads_to_nids_map_
std::vector< bool > threads_to_nids_map_
Buffer for additional histograms for Parallel processing
Definition: hist_util.h:648
xgboost::HostDeviceVector< bst_float >
xgboost::common::GHistIndexBlock::row_ptr
const size_t * row_ptr
Definition: hist_util.h:325
xgboost::common::ParallelGHistBuilder::ReduceHist
void ReduceHist(size_t nid, size_t begin, size_t end)
Definition: hist_util.h:541
xgboost::common::HistogramCuts::HistogramCuts
HistogramCuts()
xgboost::common::GHistIndexMatrix::index
Index index
The index data.
Definition: hist_util.h:240
xgboost::common::ParallelGHistBuilder::Reset
void Reset(size_t nthreads, size_t nodes, const BlockedSpace2d &space, const std::vector< GHistRowT > &targeted_hists)
Definition: hist_util.h:500
xgboost::common::Index::ResizeOffset
void ResizeOffset(const size_t nDisps)
Definition: hist_util.h:195
xgboost::common::Index
Definition: hist_util.h:142
xgboost::common::GHistIndexBlockMatrix::Init
void Init(const GHistIndexMatrix &gmat, const ColumnMatrix &colmat, const tree::TrainParam &param)
xgboost::common::HistogramCuts::HistogramCuts
HistogramCuts(HistogramCuts &&that) noexcept(true)
Definition: hist_util.h:57
xgboost::common::Index::Resize
void Resize(const size_t nBytesData)
Definition: hist_util.h:191
xgboost::common::GHistIndexMatrix::cut
HistogramCuts cut
The corresponding cuts.
Definition: hist_util.h:244
xgboost::common::HistogramCuts::cut_ptrs_
HostDeviceVector< uint32_t > cut_ptrs_
Definition: hist_util.h:43
xgboost::common::BlockedSpace2d::GetFirstDimension
size_t GetFirstDimension(size_t i) const
Definition: threading_utils.h:89
xgboost::common::HistogramCuts::SearchBin
BinIdx SearchBin(float value, uint32_t column_id) const
Definition: hist_util.h:94
xgboost::common::ParallelGHistBuilder::tid_nid_to_hist_
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:655
xgboost::common::GHistIndexMatrix::GetFeatureCounts
void GetFeatureCounts(size_t *counts) const
Definition: hist_util.h:278
xgboost::common::GHistIndexMatrix::Init
void Init(DMatrix *p_fmat, int max_num_bins)
xgboost::common::CopyHist
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)
xgboost::DMatrix
Internal data structured used by XGBoost during training.
Definition: data.h:449
xgboost::common::HostSketchContainer::CalcColumnSize
static std::vector< bst_row_t > CalcColumnSize(SparsePage const &page, bst_feature_t const n_columns, size_t const nthreads)
xgboost::common::ColumnMatrix
a collection of columns, with support for construction from GHistIndexMatrix.
Definition: column_matrix.h:101
xgboost::omp_ulong
dmlc::omp_ulong omp_ulong
define unsigned long for openmp loop
Definition: base.h:268
xgboost::common::GHistIndexBlock::index
const uint32_t * index
Definition: hist_util.h:326
xgboost::common::BlockedSpace2d
Definition: threading_utils.h:54
xgboost::common::Index::Offset
uint32_t * Offset() const
Definition: hist_util.h:182
xgboost::common::GHistBuilder::GetNumBins
uint32_t GetNumBins() const
Definition: hist_util.h:685
xgboost::common::ParallelGHistBuilder::AllocateAdditionalHistograms
void AllocateAdditionalHistograms()
Definition: hist_util.h:590
xgboost::common::Index::SetBinTypeSize
void SetBinTypeSize(BinTypeSize binTypeSize)
Definition: hist_util.h:157
xgboost::common::Index::Size
size_t Size() const
Definition: hist_util.h:188
xgboost::common::Index::data
T * data() const
Definition: hist_util.h:179
xgboost::HostDeviceVector::HostVector
std::vector< T > & HostVector()
xgboost::common::GHistIndexMatrix::SetIndexData
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
xgboost::common::GHistIndexMatrix
preprocessed global index matrix, in CSR format
Definition: hist_util.h:236
xgboost::common::HistCollection::AddHistRow
void AddHistRow(bst_uint nid)
Definition: hist_util.h:438
xgboost::common::HistogramCuts::Ptrs
std::vector< uint32_t > const & Ptrs() const
Definition: hist_util.h:86
xgboost::common::HistCollection::Init
void Init(uint32_t nbins)
Definition: hist_util.h:427
xgboost::common::HistCollection
histogram of gradient statistics for multiple nodes
Definition: hist_util.h:401
xgboost::common::HistogramCuts::min_vals_
HostDeviceVector< float > min_vals_
Definition: hist_util.h:45
xgboost::common::HistCollection::operator[]
GHistRowT operator[](bst_uint nid) const
Definition: hist_util.h:407
xgboost::common::HistogramCuts::operator=
HistogramCuts & operator=(HistogramCuts &&that) noexcept(true)
Definition: hist_util.h:71
xgboost::common::BinarySearchBin
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:298
timer.h
xgboost::common::ParallelGHistBuilder
Stores temporary histograms to compute them in parallel Supports processing multiple tree-nodes for n...
Definition: hist_util.h:487
xgboost::common::GHistBuilder::GHistBuilder
GHistBuilder(size_t nthread, uint32_t nbins)
Definition: hist_util.h:667
xgboost::common::Index::operator[]
uint32_t operator[](size_t i) const
Definition: hist_util.h:150
xgboost::common::HistCollection::RowExists
bool RowExists(bst_uint nid) const
Definition: hist_util.h:421
xgboost::common::GHistBuilder::GHistBuilder
GHistBuilder()=default
xgboost::common::GHistIndexBlock::GHistIndexBlock
GHistIndexBlock(const size_t *row_ptr, const uint32_t *index)
Definition: hist_util.h:328
xgboost::common::InitilizeHistByZeroes
void InitilizeHistByZeroes(GHistRow< GradientSumT > hist, size_t begin, size_t end)
fill a histogram by zeros
xgboost::common::HistogramCuts::FeatureBins
uint32_t FeatureBins(uint32_t feature) const
Definition: hist_util.h:78
xgboost::common::HistogramCuts::MinValues
std::vector< float > const & MinValues() const
Definition: hist_util.h:88
xgboost::common::GHistIndexBlock::operator[]
GHistIndexRow operator[](size_t i) const
Definition: hist_util.h:332
xgboost::common::ParallelGHistBuilder::nbins_
size_t nbins_
number of bins in each histogram
Definition: hist_util.h:633
xgboost::common::Index::operator=
Index & operator=(Index i)=delete
xgboost::common::GHistIndexMatrix::hit_count
std::vector< size_t > hit_count
hit count of each index
Definition: hist_util.h:242
xgboost::common::ParallelFor
void ParallelFor(Index size, size_t nthreads, Func fn)
Definition: threading_utils.h:137
xgboost::common::ParallelGHistBuilder::MatchThreadsToNodes
void MatchThreadsToNodes(const BlockedSpace2d &space)
Definition: hist_util.h:568
xgboost::HostDeviceVector::Copy
void Copy(const HostDeviceVector< T > &other)
xgboost::common::GHistIndexMatrix::ResizeIndex
void ResizeIndex(const size_t n_index, const bool isDense)
xgboost::common::SubtractionHist
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)
xgboost::common::ParallelGHistBuilder::nthreads_
size_t nthreads_
number of threads for parallel computation
Definition: hist_util.h:635
xgboost::common::ParallelGHistBuilder::MatchNodeNidPairToHist
void MatchNodeNidPairToHist()
Definition: hist_util.h:614
xgboost::HostDeviceVector::Size
size_t Size() const
xgboost::HostDeviceVector::Resize
void Resize(size_t new_size, T v=T())
xgboost::common::SketchOnDMatrix
HistogramCuts SketchOnDMatrix(DMatrix *m, int32_t max_bins)
Definition: hist_util.h:111
xgboost::common::GHistIndexMatrix::IsDense
bool IsDense() const
Definition: hist_util.h:288
xgboost::common::Index::GetBinTypeSize
BinTypeSize GetBinTypeSize() const
Definition: hist_util.h:175
xgboost::common::HostSketchContainer::UseGroup
static bool UseGroup(MetaInfo const &info)
Definition: quantile.h:725
xgboost::common::GHistIndexMatrix::max_num_bins
size_t max_num_bins
Definition: hist_util.h:246
common.h
Common utilities.
xgboost::common::GHistBuilder::BuildBlockHist
void BuildBlockHist(const std::vector< GradientPair > &gpair, const RowSetCollection::Elem row_indices, const GHistIndexBlockMatrix &gmatb, GHistRowT hist)
xgboost::common::GHistBuilder::GHistRowT
GHistRow< GradientSumT > GHistRowT
Definition: hist_util.h:664
xgboost::common::GHistBuilder::BuildHist
void BuildHist(const std::vector< GradientPair > &gpair, const RowSetCollection::Elem row_indices, const GHistIndexMatrix &gmat, GHistRowT hist, bool isDense)
generic_parameters.h
xgboost::common::Span
span class implementation, based on ISO++20 span<T>. The interface should be the same.
Definition: span.h:142
xgboost::common::kUint32BinsTypeSize
@ kUint32BinsTypeSize
Definition: hist_util.h:139
data.h
The input data structure of xgboost.
xgboost::common::GHistIndexBlockMatrix::operator[]
GHistIndexBlock operator[](size_t i) const
Definition: hist_util.h:345
xgboost::common::kUint8BinsTypeSize
@ kUint8BinsTypeSize
Definition: hist_util.h:137
xgboost::SparsePage::offset
HostDeviceVector< bst_row_t > offset
Definition: data.h:246
threading_utils.h
xgboost::common::Index::Index
Index()
Definition: hist_util.h:143
xgboost::common::ParallelGHistBuilder::Init
void Init(size_t nbins)
Definition: hist_util.h:491
xgboost::common::HistogramCuts::SearchBin
BinIdx SearchBin(Entry const &e) const
Definition: hist_util.h:106
xgboost::common::HostSketchContainer::PushRowPage
void PushRowPage(SparsePage const &page, MetaInfo const &info)
xgboost::HostDeviceVector::ConstHostVector
const std::vector< T > & ConstHostVector() const
xgboost::common::Span::size
constexpr XGBOOST_DEVICE index_type size() const __span_noexcept
Definition: span.h:547
xgboost::common::Span::data
constexpr XGBOOST_DEVICE pointer data() const __span_noexcept
Definition: span.h:542
xgboost::common::HistogramCuts::cut_values_
HostDeviceVector< bst_float > cut_values_
Definition: hist_util.h:42
xgboost::bst_uint
uint32_t bst_uint
unsigned integer type used for feature index.
Definition: base.h:113
xgboost::common::GHistIndexBlock
Definition: hist_util.h:324
xgboost::common::ParallelGHistBuilder::targeted_hists_
std::vector< GHistRowT > targeted_hists_
Contains histograms for final results
Definition: hist_util.h:650
xgboost::Entry::fvalue
bst_float fvalue
feature value
Definition: data.h:188
xgboost::common::Index::begin
std::vector< uint8_t >::const_iterator begin() const
Definition: hist_util.h:200
xgboost::common::ParallelGHistBuilder::hist_buffer_
HistCollection< GradientSumT > hist_buffer_
Buffer for additional histograms for Parallel processing
Definition: hist_util.h:639
xgboost::DMatrix::GetBatches
BatchSet< T > GetBatches(const BatchParam &param={})
Gets batches. Use range based for loop over BatchSet to access individual batches.
xgboost::common::HistogramCuts::operator=
HistogramCuts & operator=(HistogramCuts const &that)
Definition: hist_util.h:61
xgboost::common::Index::end
std::vector< uint8_t >::const_iterator end() const
Definition: hist_util.h:203
xgboost::common::HistogramCuts::Values
std::vector< float > const & Values() const
Definition: hist_util.h:87
xgboost::SparsePage::data
HostDeviceVector< Entry > data
the data of the segments
Definition: data.h:248
xgboost::common::GHistBuilder::SubtractionTrick
void SubtractionTrick(GHistRowT self, GHistRowT sibling, GHistRowT parent)
xgboost::common::ParallelGHistBuilder::hist_was_used_
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:645
xgboost::common::Index::OffsetSize
size_t OffsetSize() const
Definition: hist_util.h:185
xgboost::common::GHistBuilder
builder for histograms of gradient statistics
Definition: hist_util.h:662
xgboost
namespace of xgboost
Definition: base.h:110