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	(	T	begin,
		T	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().

                                                                {
  if constexpr (sizeof(U) < sizeof(std::size_t)) {  // NOLINT
    if (std::numeric_limits<U>::max() < n_workers) {
      n_workers = std::numeric_limits<U>::max();
    }
  }
  return {begin, end, static_cast<U>(n_workers)};
}

Here is the call graph for this function:

Here is the caller graph for this function: