OmniSciDB  0264ff685a
Intervals.h
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2020 OmniSci, Inc.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 /*
18  * @file Intervals.h
19  * @author Matt Pulver <matt.pulver@omnisci.com>
20  * @description Divide up indexes (A, A+1, A+2, ..., B-2, B-1) among
21  * N workers as evenly as possible in a range-based for loop:
22  * for (auto const& interval : makeIntervals(A, B, N)) {}
23  * where interval is a 2-member struct of (begin,end) values.
24  * This just does the arithmetic to divide up work into chunks;
25  * asynchronous thread management is done separately.
26  *
27  * This is a common pattern when dividing work among CPU threads.
28  * This is NOT appropriate for GPU threads which are better done with strides.
29  * 2 guarantees:
30  * - Larger intervals always precede smaller intervals.
31  * - The difference in work between any two intervals never exceeds 1.
32  *
33  * Example Usage. Divide up this loop:
34  *
35  * for (int i=0 ; i<100 ; ++i)
36  * work(i);
37  *
38  * into 3 parallel workers:
39  *
40  * for (auto const& interval : makeIntervals(0, 100, 3))
41  * spawn_thread(work, interval);
42  *
43  * where, for example, spawn_thread spawns threads running:
44  *
45  * for (int j=interval.begin ; j<interval.end ; ++j)
46  * work(j);
47  *
48  * This would be equivalent to running the following 3 loops in parallel:
49  *
50  * for (int j= 0 ; j< 34 ; ++j) work(j);
51  * for (int j=34 ; j< 67 ; ++j) work(j);
52  * for (int j=67 ; j<100 ; ++j) work(j);
53  *
54  * The number of iterations in this example is 34, 33, 33, respectively.
55  * In general the larger iterations always precede the smaller, and the
56  * maximum difference between the largest and smallest never exceeds 1.
57  */
58 
59 #pragma once
60 
61 #include <iterator>
62 #include <limits>
63 #include <type_traits>
64 
66 struct Interval {
67  T const begin;
68  T const end;
69  U const index; // [0, n_workers)
70 };
71 
73 class Intervals {
74  T const begin_;
75  U const total_size_;
76  U const quot_;
77  U const rem_;
78 
79  Intervals(T begin, T end, U n_workers)
80  : begin_(begin)
81  , total_size_(begin < end && n_workers ? end - begin : 0)
82  , quot_(n_workers ? total_size_ / n_workers : 0)
83  , rem_(n_workers ? total_size_ % n_workers : 0) {
84  static_assert(std::is_integral<T>::value);
85  }
86 
87  public:
88  class Iterator : public std::iterator<std::input_iterator_tag, Interval<T>> {
90  U const quot_;
91  U rem_;
92  U index{0};
93 
94  public:
95  Iterator(T begin, U quot, U rem) : begin_(begin), quot_(quot), rem_(rem) {}
97  return {begin_, T(begin_ + quot_ + bool(rem_)), index};
98  }
99  void operator++() {
100  begin_ += quot_ + (rem_ && rem_--);
101  ++index;
102  }
103  bool operator==(Iterator const& rhs) const { return begin_ == rhs.begin_; }
104  bool operator!=(Iterator const& rhs) const { return begin_ != rhs.begin_; }
105  };
106 
107  bool empty() const { return !total_size_; }
108  Iterator begin() const { return {begin_, quot_, rem_}; }
109  Iterator end() const { return {static_cast<T>(begin_ + total_size_), quot_, 0}; }
110  template <typename T1, typename U1>
111  friend Intervals<T1> makeIntervals(T1 begin, T1 end, std::size_t n_workers);
112 };
113 
115 Intervals<T> makeIntervals(T begin, T end, std::size_t n_workers) {
116  if constexpr (sizeof(U) < sizeof(std::size_t)) {
117  if (std::numeric_limits<U>::max() < n_workers) {
118  n_workers = std::numeric_limits<U>::max();
119  }
120  }
121  return {begin, end, static_cast<U>(n_workers)};
122 }
U const index
Definition: Intervals.h:69
Interval< T > operator*() const
Definition: Intervals.h:96
bool operator==(Iterator const &rhs) const
Definition: Intervals.h:103
Iterator end() const
Definition: Intervals.h:109
T const begin
Definition: Intervals.h:67
T const begin_
Definition: Intervals.h:74
Intervals< T > makeIntervals(T begin, T end, std::size_t n_workers)
Definition: Intervals.h:115
Intervals(T begin, T end, U n_workers)
Definition: Intervals.h:79
bool empty() const
Definition: Intervals.h:107
Iterator begin() const
Definition: Intervals.h:108
U const total_size_
Definition: Intervals.h:75
T const end
Definition: Intervals.h:68
Iterator(T begin, U quot, U rem)
Definition: Intervals.h:95
bool operator!=(Iterator const &rhs) const
Definition: Intervals.h:104
U const rem_
Definition: Intervals.h:77
U const quot_
Definition: Intervals.h:76