xgboost
span.h
Go to the documentation of this file.
1 
29 #ifndef XGBOOST_SPAN_H_
30 #define XGBOOST_SPAN_H_
31 
32 #include <xgboost/base.h>
33 #include <xgboost/logging.h>
34 
35 #include <cinttypes> // size_t
36 #include <limits> // numeric_limits
37 #include <iterator>
38 #include <type_traits>
39 #include <cstdio>
40 
58 #if defined(_MSC_VER) && _MSC_VER < 1910
59 
60 #define __span_noexcept
61 
62 #pragma push_macro("constexpr")
63 #define constexpr /*constexpr*/
64 
65 #else
66 
67 #define __span_noexcept noexcept
68 
69 #endif // defined(_MSC_VER) && _MSC_VER < 1910
70 
71 namespace xgboost {
72 namespace common {
73 
74 // Usual logging facility is not available inside device code.
75 // assert is not supported in mac as of CUDA 10.0
76 #define KERNEL_CHECK(cond) \
77  do { \
78  if (!(cond)) { \
79  printf("\nKernel error:\n" \
80  "In: %s: %d\n" \
81  "\t%s\n\tExpecting: %s\n" \
82  "\tBlock: [%d, %d, %d], Thread: [%d, %d, %d]\n\n", \
83  __FILE__, __LINE__, __PRETTY_FUNCTION__, #cond, blockIdx.x, \
84  blockIdx.y, blockIdx.z, threadIdx.x, threadIdx.y, threadIdx.z); \
85  asm("trap;"); \
86  } \
87  } while (0);
88 
89 #if defined(__CUDA_ARCH__)
90 #define SPAN_CHECK KERNEL_CHECK
91 #elif defined(XGBOOST_STRICT_R_MODE) && XGBOOST_STRICT_R_MODE == 1 // R package
92 #define SPAN_CHECK CHECK // check from dmlc
93 #else // not CUDA, not R
94 #define SPAN_CHECK(cond) \
95  do { \
96  if (XGBOOST_EXPECT(!(cond), false)) { \
97  fprintf(stderr, "[xgboost] Condition %s failed.\n", #cond); \
98  fflush(stderr); /* It seems stderr on Windows is beffered? */ \
99  std::terminate(); \
100  } \
101  } while (0);
102 #endif // __CUDA_ARCH__
103 
104 namespace detail {
111 using ptrdiff_t = typename std::conditional< // NOLINT
112  std::is_same<std::ptrdiff_t, std::int64_t>::value,
113  std::ptrdiff_t, std::int64_t>::type;
114 } // namespace detail
115 
116 #if defined(_MSC_VER) && _MSC_VER < 1910
117 constexpr const std::size_t
118 dynamic_extent = std::numeric_limits<std::size_t>::max(); // NOLINT
119 #else
120 constexpr std::size_t dynamic_extent = std::numeric_limits<std::size_t>::max(); // NOLINT
121 #endif // defined(_MSC_VER) && _MSC_VER < 1910
122 
123 enum class byte : unsigned char {}; // NOLINT
124 
125 template <class ElementType, std::size_t Extent>
126 class Span;
127 
128 namespace detail {
129 
130 template <typename SpanType, bool IsConst>
132  using ElementType = typename SpanType::element_type;
133 
134  public:
135  using iterator_category = std::random_access_iterator_tag; // NOLINT
136  using value_type = typename SpanType::value_type; // NOLINT
138 
139  using reference = typename std::conditional< // NOLINT
140  IsConst, const ElementType, ElementType>::type&;
141  using pointer = typename std::add_pointer<reference>::type; // NOLINT
142 
143  constexpr SpanIterator() = default;
144 
146  const SpanType* _span,
147  typename SpanType::index_type _idx) __span_noexcept :
148  span_(_span), index_(_idx) {}
149 
151  template <bool B, typename std::enable_if<!B && IsConst>::type* = nullptr>
152  XGBOOST_DEVICE constexpr SpanIterator( // NOLINT
154  : SpanIterator(other_.span_, other_.index_) {}
155 
157  SPAN_CHECK(index_ < span_->size());
158  return *(span_->data() + index_);
159  }
161  return *(*this + n);
162  }
163 
165  SPAN_CHECK(index_ != span_->size());
166  return span_->data() + index_;
167  }
168 
170  SPAN_CHECK(index_ != span_->size());
171  index_++;
172  return *this;
173  }
174 
176  auto ret = *this;
177  ++(*this);
178  return ret;
179  }
180 
182  SPAN_CHECK(index_ != 0 && index_ <= span_->size());
183  index_--;
184  return *this;
185  }
186 
188  auto ret = *this;
189  --(*this);
190  return ret;
191  }
192 
194  auto ret = *this;
195  return ret += n;
196  }
197 
199  SPAN_CHECK((index_ + n) <= span_->size());
200  index_ += n;
201  return *this;
202  }
203 
205  SPAN_CHECK(span_ == rhs.span_);
206  return index_ - rhs.index_;
207  }
208 
210  auto ret = *this;
211  return ret -= n;
212  }
213 
215  return *this += -n;
216  }
217 
218  // friends
219  XGBOOST_DEVICE constexpr friend bool operator==(
221  return _lhs.span_ == _rhs.span_ && _lhs.index_ == _rhs.index_;
222  }
223 
224  XGBOOST_DEVICE constexpr friend bool operator!=(
226  return !(_lhs == _rhs);
227  }
228 
229  XGBOOST_DEVICE constexpr friend bool operator<(
231  return _lhs.index_ < _rhs.index_;
232  }
233 
234  XGBOOST_DEVICE constexpr friend bool operator<=(
236  return !(_rhs < _lhs);
237  }
238 
239  XGBOOST_DEVICE constexpr friend bool operator>(
241  return _rhs < _lhs;
242  }
243 
244  XGBOOST_DEVICE constexpr friend bool operator>=(
246  return !(_rhs > _lhs);
247  }
248 
249  protected:
250  const SpanType *span_ { nullptr };
251  typename SpanType::index_type index_ { 0 };
252 };
253 
254 
255 // It's tempting to use constexpr instead of structs to do the following meta
256 // programming. But remember that we are supporting MSVC 2013 here.
257 
265 template <std::size_t Extent, std::size_t Offset, std::size_t Count>
266 struct ExtentValue : public std::integral_constant<
267  std::size_t, Count != dynamic_extent ?
268  Count : (Extent != dynamic_extent ? Extent - Offset : Extent)> {};
269 
274 template <typename T, std::size_t Extent>
275 struct ExtentAsBytesValue : public std::integral_constant<
276  std::size_t,
277  Extent == dynamic_extent ?
278  Extent : sizeof(T) * Extent> {};
279 
280 template <std::size_t From, std::size_t To>
281 struct IsAllowedExtentConversion : public std::integral_constant<
282  bool, From == To || From == dynamic_extent || To == dynamic_extent> {};
283 
284 template <class From, class To>
285 struct IsAllowedElementTypeConversion : public std::integral_constant<
286  bool, std::is_convertible<From(*)[], To(*)[]>::value> {};
287 
288 template <class T>
289 struct IsSpanOracle : std::false_type {};
290 
291 template <class T, std::size_t Extent>
292 struct IsSpanOracle<Span<T, Extent>> : std::true_type {};
293 
294 template <class T>
295 struct IsSpan : public IsSpanOracle<typename std::remove_cv<T>::type> {};
296 
297 // Re-implement std algorithms here to adopt CUDA.
298 template <typename T>
299 struct Less {
300  XGBOOST_DEVICE constexpr bool operator()(const T& _x, const T& _y) const {
301  return _x < _y;
302  }
303 };
304 
305 template <typename T>
306 struct Greater {
307  XGBOOST_DEVICE constexpr bool operator()(const T& _x, const T& _y) const {
308  return _x > _y;
309  }
310 };
311 
312 template <class InputIt1, class InputIt2,
313  class Compare =
315 XGBOOST_DEVICE bool LexicographicalCompare(InputIt1 first1, InputIt1 last1,
316  InputIt2 first2, InputIt2 last2) {
317  Compare comp;
318  for (; first1 != last1 && first2 != last2; ++first1, ++first2) {
319  if (comp(*first1, *first2)) {
320  return true;
321  }
322  if (comp(*first2, *first1)) {
323  return false;
324  }
325  }
326  return first1 == last1 && first2 != last2;
327 }
328 
329 } // namespace detail
330 
331 
399 template <typename T,
400  std::size_t Extent = dynamic_extent>
401 class Span {
402  public:
403  using element_type = T; // NOLINT
404  using value_type = typename std::remove_cv<T>::type; // NOLINT
405  using index_type = std::size_t; // NOLINT
407  using pointer = T*; // NOLINT
408  using reference = T&; // NOLINT
409 
411  using const_iterator = const detail::SpanIterator<Span<T, Extent>, true>; // NOLINT
414 
415  // constructors
416  constexpr Span() __span_noexcept = default;
417 
419  size_(_count), data_(_ptr) {
420  SPAN_CHECK(!(Extent != dynamic_extent && _count != Extent));
421  SPAN_CHECK(_ptr || _count == 0);
422  }
423 
425  size_(_last - _first), data_(_first) {
426  SPAN_CHECK(data_ || size_ == 0);
427  }
428 
429  template <std::size_t N>
430  XGBOOST_DEVICE constexpr Span(element_type (&arr)[N]) // NOLINT
431  __span_noexcept : size_(N), data_(&arr[0]) {}
432 
433  template <class Container,
434  class = typename std::enable_if<
435  !std::is_const<element_type>::value &&
437  std::is_convertible<typename Container::pointer, pointer>::value &&
438  std::is_convertible<typename Container::pointer,
439  decltype(std::declval<Container>().data())>::value>::type>
440  Span(Container& _cont) : // NOLINT
441  size_(_cont.size()), data_(_cont.data()) {
442  static_assert(!detail::IsSpan<Container>::value, "Wrong constructor of Span is called.");
443  }
444 
445  template <class Container,
446  class = typename std::enable_if<
447  std::is_const<element_type>::value &&
449  std::is_convertible<typename Container::pointer, pointer>::value &&
450  std::is_convertible<typename Container::pointer,
451  decltype(std::declval<Container>().data())>::value>::type>
452  Span(const Container& _cont) : size_(_cont.size()), // NOLINT
453  data_(_cont.data()) {
454  static_assert(!detail::IsSpan<Container>::value, "Wrong constructor of Span is called.");
455  }
456 
457  template <class U, std::size_t OtherExtent,
458  class = typename std::enable_if<
461  XGBOOST_DEVICE constexpr Span(const Span<U, OtherExtent>& _other) // NOLINT
462  __span_noexcept : size_(_other.size()), data_(_other.data()) {}
463 
464  XGBOOST_DEVICE constexpr Span(const Span& _other)
465  __span_noexcept : size_(_other.size()), data_(_other.data()) {}
466 
468  size_ = _other.size();
469  data_ = _other.data();
470  return *this;
471  }
472 
474 
475  XGBOOST_DEVICE constexpr iterator begin() const __span_noexcept { // NOLINT
476  return {this, 0};
477  }
478 
479  XGBOOST_DEVICE constexpr iterator end() const __span_noexcept { // NOLINT
480  return {this, size()};
481  }
482 
483  XGBOOST_DEVICE constexpr const_iterator cbegin() const __span_noexcept { // NOLINT
484  return {this, 0};
485  }
486 
487  XGBOOST_DEVICE constexpr const_iterator cend() const __span_noexcept { // NOLINT
488  return {this, size()};
489  }
490 
492  return reverse_iterator{end()};
493  }
494 
495  XGBOOST_DEVICE constexpr reverse_iterator rend() const __span_noexcept { // NOLINT
496  return reverse_iterator{begin()};
497  }
498 
500  return const_reverse_iterator{cend()};
501  }
502 
504  return const_reverse_iterator{cbegin()};
505  }
506 
507  // element access
508 
509  XGBOOST_DEVICE reference front() const { // NOLINT
510  return (*this)[0];
511  }
512 
513  XGBOOST_DEVICE reference back() const { // NOLINT
514  return (*this)[size() - 1];
515  }
516 
518  SPAN_CHECK(_idx < size());
519  return data()[_idx];
520  }
521 
523  return this->operator[](_idx);
524  }
525 
526  XGBOOST_DEVICE constexpr pointer data() const __span_noexcept { // NOLINT
527  return data_;
528  }
529 
530  // Observers
531  XGBOOST_DEVICE constexpr index_type size() const __span_noexcept { // NOLINT
532  return size_;
533  }
534  XGBOOST_DEVICE constexpr index_type size_bytes() const __span_noexcept { // NOLINT
535  return size() * sizeof(T);
536  }
537 
538  XGBOOST_DEVICE constexpr bool empty() const __span_noexcept { // NOLINT
539  return size() == 0;
540  }
541 
542  // Subviews
543  template <std::size_t Count>
545  SPAN_CHECK(Count <= size());
546  return {data(), Count};
547  }
548 
550  std::size_t _count) const {
551  SPAN_CHECK(_count <= size());
552  return {data(), _count};
553  }
554 
555  template <std::size_t Count>
557  SPAN_CHECK(Count <= size());
558  return {data() + size() - Count, Count};
559  }
560 
562  std::size_t _count) const {
563  SPAN_CHECK(_count <= size());
564  return subspan(size() - _count, _count);
565  }
566 
571  template <std::size_t Offset,
572  std::size_t Count = dynamic_extent>
573  XGBOOST_DEVICE auto subspan() const -> // NOLINT
575  detail::ExtentValue<Extent, Offset, Count>::value> {
576  SPAN_CHECK((Count == dynamic_extent) ?
577  (Offset <= size()) : (Offset + Count <= size()));
578 
579  return {data() + Offset, Count == dynamic_extent ? size() - Offset : Count};
580  }
581 
583  index_type _offset,
584  index_type _count = dynamic_extent) const {
585  SPAN_CHECK((_count == dynamic_extent) ?
586  (_offset <= size()) : (_offset + _count <= size()));
587  return {data() + _offset, _count ==
588  dynamic_extent ? size() - _offset : _count};
589  }
590 
591  private:
592  index_type size_ { 0 };
593  pointer data_ { nullptr };
594 };
595 
596 template <class T, std::size_t X, class U, std::size_t Y>
598  if (l.size() != r.size()) {
599  return false;
600  }
601  for (auto l_beg = l.cbegin(), r_beg = r.cbegin(); l_beg != l.cend();
602  ++l_beg, ++r_beg) {
603  if (*l_beg != *r_beg) {
604  return false;
605  }
606  }
607  return true;
608 }
609 
610 template <class T, std::size_t X, class U, std::size_t Y>
612  return !(l == r);
613 }
614 
615 template <class T, std::size_t X, class U, std::size_t Y>
616 XGBOOST_DEVICE constexpr bool operator<(Span<T, X> l, Span<U, Y> r) {
617  return detail::LexicographicalCompare(l.begin(), l.end(),
618  r.begin(), r.end());
619 }
620 
621 template <class T, std::size_t X, class U, std::size_t Y>
622 XGBOOST_DEVICE constexpr bool operator<=(Span<T, X> l, Span<U, Y> r) {
623  return !(l > r);
624 }
625 
626 template <class T, std::size_t X, class U, std::size_t Y>
629  typename Span<T, X>::iterator, typename Span<U, Y>::iterator,
631  r.begin(), r.end());
632 }
633 
634 template <class T, std::size_t X, class U, std::size_t Y>
636  return !(l < r);
637 }
638 
639 template <class T, std::size_t E>
642  return {reinterpret_cast<const byte*>(s.data()), s.size_bytes()};
643 }
644 
645 template <class T, std::size_t E>
648  return {reinterpret_cast<byte*>(s.data()), s.size_bytes()};
649 }
650 
651 } // namespace common
652 } // namespace xgboost
653 
654 #if defined(_MSC_VER) &&_MSC_VER < 1910
655 #undef constexpr
656 #pragma pop_macro("constexpr")
657 #undef __span_noexcept
658 #endif // _MSC_VER < 1910
659 
660 #endif // XGBOOST_SPAN_H_
byte
Definition: span.h:123
XGBOOST_DEVICE constexpr bool operator>=(Span< T, X > l, Span< U, Y > r)
Definition: span.h:635
XGBOOST_DEVICE constexpr friend bool operator>=(SpanIterator _lhs, SpanIterator _rhs) __span_noexcept
Definition: span.h:244
#define SPAN_CHECK(cond)
Definition: span.h:94
XGBOOST_DEVICE Span< element_type, Count > first() const
Definition: span.h:544
XGBOOST_DEVICE constexpr index_type size() const __span_noexcept
Definition: span.h:531
XGBOOST_DEVICE Span(pointer _first, pointer _last)
Definition: span.h:424
XGBOOST_DEVICE constexpr bool empty() const __span_noexcept
Definition: span.h:538
XGBOOST_DEVICE reference operator()(index_type _idx) const
Definition: span.h:522
XGBOOST_DEVICE SpanIterator & operator--()
Definition: span.h:181
XGBOOST_DEVICE SpanIterator operator--(int)
Definition: span.h:187
std::size_t index_type
Definition: span.h:405
XGBOOST_DEVICE Span< element_type, dynamic_extent > subspan(index_type _offset, index_type _count=dynamic_extent) const
Definition: span.h:582
XGBOOST_DEVICE constexpr SpanIterator(const SpanIterator< SpanType, B > &other_) __span_noexcept
Definition: span.h:152
XGBOOST_DEVICE constexpr bool operator>(Span< T, X > l, Span< U, Y > r)
Definition: span.h:627
XGBOOST_DEVICE constexpr iterator end() const __span_noexcept
Definition: span.h:479
XGBOOST_DEVICE SpanIterator operator-(difference_type n) const
Definition: span.h:209
XGBOOST_DEVICE SpanIterator & operator+=(difference_type n)
Definition: span.h:198
Span(const Container &_cont)
Definition: span.h:452
XGBOOST_DEVICE constexpr friend bool operator<=(SpanIterator _lhs, SpanIterator _rhs) __span_noexcept
Definition: span.h:234
Definition: span.h:299
XGBOOST_DEVICE SpanIterator operator+(difference_type n) const
Definition: span.h:193
const BinIdxType element_type
Definition: span.h:403
Definition: span.h:306
XGBOOST_DEVICE auto as_bytes(Span< T, E > s) __span_noexcept -> Span< const byte, detail::ExtentAsBytesValue< T, E >::value >
Definition: span.h:640
Span(Container &_cont)
Definition: span.h:440
XGBOOST_DEVICE reference operator[](difference_type n) const
Definition: span.h:160
detail::ptrdiff_t difference_type
Definition: span.h:406
typename SpanType::value_type value_type
Definition: span.h:136
XGBOOST_DEVICE reference back() const
Definition: span.h:513
XGBOOST_DEVICE constexpr Span(const Span &_other) __span_noexcept
Definition: span.h:464
const BinIdxType & reference
Definition: span.h:408
XGBOOST_DEVICE auto as_writable_bytes(Span< T, E > s) __span_noexcept -> Span< byte, detail::ExtentAsBytesValue< T, E >::value >
Definition: span.h:646
XGBOOST_DEVICE constexpr friend bool operator!=(SpanIterator _lhs, SpanIterator _rhs) __span_noexcept
Definition: span.h:224
XGBOOST_DEVICE constexpr bool operator()(const T &_x, const T &_y) const
Definition: span.h:307
Definition: span.h:295
std::random_access_iterator_tag iterator_category
Definition: span.h:135
XGBOOST_DEVICE Span< element_type, dynamic_extent > first(std::size_t _count) const
Definition: span.h:549
span class implementation, based on ISO++20 span<T>. The interface should be the same.
Definition: span.h:126
XGBOOST_DEVICE SpanIterator & operator++()
Definition: span.h:169
typename std::conditional< IsConst, const ElementType, ElementType >::type & reference
Definition: span.h:140
XGBOOST_DEVICE SpanIterator & operator-=(difference_type n)
Definition: span.h:214
XGBOOST_DEVICE bool LexicographicalCompare(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2)
Definition: span.h:315
XGBOOST_DEVICE constexpr friend bool operator>(SpanIterator _lhs, SpanIterator _rhs) __span_noexcept
Definition: span.h:239
typename std::remove_cv< const BinIdxType >::type value_type
Definition: span.h:404
typename std::conditional< std::is_same< std::ptrdiff_t, std::int64_t >::value, std::ptrdiff_t, std::int64_t >::type ptrdiff_t
Definition: span.h:113
XGBOOST_DEVICE Span< element_type, Count > last() const
Definition: span.h:556
XGBOOST_DEVICE constexpr pointer data() const __span_noexcept
Definition: span.h:526
XGBOOST_DEVICE constexpr const_reverse_iterator crend() const __span_noexcept
Definition: span.h:503
XGBOOST_DEVICE constexpr SpanIterator(const SpanType *_span, typename SpanType::index_type _idx) __span_noexcept
Definition: span.h:145
constexpr std::size_t dynamic_extent
Definition: span.h:120
XGBOOST_DEVICE constexpr reverse_iterator rbegin() const __span_noexcept
Definition: span.h:491
XGBOOST_DEVICE constexpr bool operator()(const T &_x, const T &_y) const
Definition: span.h:300
XGBOOST_DEVICE constexpr bool operator!=(Span< T, X > l, Span< U, Y > r)
Definition: span.h:611
#define XGBOOST_DEVICE
Tag function as usable by device.
Definition: base.h:84
SpanType::index_type index_
Definition: span.h:251
namespace of xgboost
Definition: base.h:102
XGBOOST_DEVICE constexpr reverse_iterator rend() const __span_noexcept
Definition: span.h:495
XGBOOST_DEVICE Span< element_type, dynamic_extent > last(std::size_t _count) const
Definition: span.h:561
XGBOOST_DEVICE reference front() const
Definition: span.h:509
defines configuration macros of xgboost.
XGBOOST_DEVICE constexpr const_reverse_iterator crbegin() const __span_noexcept
Definition: span.h:499
const SpanType * span_
Definition: span.h:250
XGBOOST_DEVICE auto subspan() const -> Span< element_type, detail::ExtentValue< Extent, Offset, Count >::value >
Definition: span.h:573
XGBOOST_DEVICE constexpr Span(element_type(&arr)[N]) __span_noexcept
Definition: span.h:430
XGBOOST_DEVICE constexpr const_iterator cbegin() const __span_noexcept
Definition: span.h:483
XGBOOST_DEVICE SpanIterator operator++(int)
Definition: span.h:175
const BinIdxType * pointer
Definition: span.h:407
XGBOOST_DEVICE reference operator[](index_type _idx) const
Definition: span.h:517
XGBOOST_DEVICE constexpr friend bool operator<(SpanIterator _lhs, SpanIterator _rhs) __span_noexcept
Definition: span.h:229
XGBOOST_DEVICE constexpr index_type size_bytes() const __span_noexcept
Definition: span.h:534
XGBOOST_DEVICE constexpr const_iterator cend() const __span_noexcept
Definition: span.h:487
#define __span_noexcept
span class based on ISO++20 span
Definition: span.h:67
XGBOOST_DEVICE Span & operator=(const Span &_other) __span_noexcept
Definition: span.h:467
XGBOOST_DEVICE constexpr friend bool operator==(SpanIterator _lhs, SpanIterator _rhs) __span_noexcept
Definition: span.h:219
typename std::add_pointer< reference >::type pointer
Definition: span.h:141
XGBOOST_DEVICE constexpr Span(const Span< U, OtherExtent > &_other) __span_noexcept
Definition: span.h:461
detail::ptrdiff_t difference_type
Definition: span.h:137
XGBOOST_DEVICE constexpr iterator begin() const __span_noexcept
Definition: span.h:475
XGBOOST_DEVICE difference_type operator-(SpanIterator rhs) const
Definition: span.h:204
XGBOOST_DEVICE ~Span() __span_noexcept
Definition: span.h:473
XGBOOST_DEVICE reference operator*() const
Definition: span.h:156
XGBOOST_DEVICE pointer operator->() const
Definition: span.h:164
XGBOOST_DEVICE bool operator==(Span< T, X > l, Span< U, Y > r)
Definition: span.h:597