OmniSciDB  a987f07e93
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Intervals.h File Reference

Divide up indexes (A, A+1, A+2, ..., B-2, B-1) among N workers as evenly as possible in a range-based for loop: for (auto const& interval : makeIntervals(A, B, N)) {} where interval is a 2-member struct of (begin,end) values. This just does the arithmetic to divide up work into chunks; asynchronous thread management is done separately. More...

#include <iterator>
#include <limits>
#include <type_traits>
+ Include dependency graph for Intervals.h:
+ This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

struct  Interval< T, U >
 
class  Intervals< T, U >
 
class  Intervals< T, U >::Iterator
 

Functions

template<typename T , typename U = typename std::make_unsigned<T>::type>
Intervals< T > makeIntervals (T begin, T end, std::size_t n_workers)
 

Detailed Description

Divide up indexes (A, A+1, A+2, ..., B-2, B-1) among N workers as evenly as possible in a range-based for loop: for (auto const& interval : makeIntervals(A, B, N)) {} where interval is a 2-member struct of (begin,end) values. This just does the arithmetic to divide up work into chunks; asynchronous thread management is done separately.

This is a common pattern when dividing work among CPU threads. This is NOT appropriate for GPU threads which are better done with strides. 2 guarantees:

  • Larger intervals always precede smaller intervals.
  • The difference in work between any two intervals never exceeds 1.

Example Usage. Divide up this loop:

for (int i=0 ; i<100 ; ++i) work(i);

into 3 parallel workers:

for (auto const& interval : makeIntervals(0, 100, 3)) spawn_thread(work, interval);

where, for example, spawn_thread spawns threads running:

for (int j=interval.begin ; j<interval.end ; ++j) work(j);

This would be equivalent to running the following 3 loops in parallel:

for (int j= 0 ; j< 34 ; ++j) work(j); for (int j=34 ; j< 67 ; ++j) work(j); for (int j=67 ; j<100 ; ++j) work(j);

The number of iterations in this example is 34, 33, 33, respectively. In general the larger iterations always precede the smaller, and the maximum difference between the largest and smallest never exceeds 1.

Definition in file Intervals.h.

Function Documentation

template<typename T , typename U = typename std::make_unsigned<T>::type>
Intervals<T> makeIntervals ( begin,
end,
std::size_t  n_workers 
)

Definition at line 122 of file Intervals.h.

References Intervals< T, U >::begin(), and Intervals< T, U >::end().

Referenced by ColumnFetcher::linearizeVarLenArrayColFrags(), ColumnarResults::materializeAllColumnsThroughIteration(), and ColumnarResults::materializeAllLazyColumns().

122  {
123  if constexpr (sizeof(U) < sizeof(std::size_t)) { // NOLINT
124  if (std::numeric_limits<U>::max() < n_workers) {
125  n_workers = std::numeric_limits<U>::max();
126  }
127  }
128  return {begin, end, static_cast<U>(n_workers)};
129 }

+ Here is the call graph for this function:

+ Here is the caller graph for this function: