VTK-m  2.0
FunctorsTBB.h
Go to the documentation of this file.
1 //============================================================================
2 // Copyright (c) Kitware, Inc.
3 // All rights reserved.
4 // See LICENSE.txt for details.
5 //
6 // This software is distributed WITHOUT ANY WARRANTY; without even
7 // the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
8 // PURPOSE. See the above copyright notice for more information.
9 //============================================================================
10 #ifndef vtk_m_cont_tbb_internal_FunctorsTBB_h
11 #define vtk_m_cont_tbb_internal_FunctorsTBB_h
12 
13 #include <vtkm/TypeTraits.h>
14 #include <vtkm/Types.h>
16 #include <vtkm/cont/Error.h>
19 
20 #include <algorithm>
21 #include <iterator>
22 #include <sstream>
23 #include <type_traits>
24 
25 VTKM_THIRDPARTY_PRE_INCLUDE
26 
27 #if defined(VTKM_MSVC)
28 
29 // TBB's header include a #pragma comment(lib,"tbb.lib") line to make all
30 // consuming libraries link to tbb, this is bad behavior in a header
31 // based project
32 #pragma push_macro("__TBB_NO_IMPLICITLINKAGE")
33 #define __TBB_NO_IMPLICIT_LINKAGE 1
34 
35 #endif // defined(VTKM_MSVC)
36 
37 // TBB includes windows.h, so instead we want to include windows.h with the
38 // correct settings so that we don't clobber any existing function
39 #include <vtkm/internal/Windows.h>
40 
41 
42 #include <numeric>
43 #include <tbb/blocked_range.h>
44 #include <tbb/blocked_range3d.h>
45 #include <tbb/parallel_for.h>
46 #include <tbb/parallel_reduce.h>
47 #include <tbb/parallel_scan.h>
48 #include <tbb/parallel_sort.h>
49 #include <tbb/partitioner.h>
50 #include <tbb/tick_count.h>
51 
52 #if defined(VTKM_MSVC)
53 #pragma pop_macro("__TBB_NO_IMPLICITLINKAGE")
54 #endif
55 
56 VTKM_THIRDPARTY_POST_INCLUDE
57 
58 namespace vtkm
59 {
60 namespace cont
61 {
62 namespace tbb
63 {
64 
65 namespace internal
66 {
67 template <typename ResultType, typename Function>
68 using WrappedBinaryOperator = vtkm::cont::internal::WrappedBinaryOperator<ResultType, Function>;
69 }
70 
71 // The "grain size" of scheduling with TBB. Not a lot of thought has gone
72 // into picking this size.
73 static constexpr vtkm::Id TBB_GRAIN_SIZE = 1024;
74 
75 template <typename InputPortalType, typename OutputPortalType>
76 struct CopyBody
77 {
78  InputPortalType InputPortal;
79  OutputPortalType OutputPortal;
82 
83  CopyBody(const InputPortalType& inPortal,
84  const OutputPortalType& outPortal,
85  vtkm::Id inOffset,
86  vtkm::Id outOffset)
87  : InputPortal(inPortal)
88  , OutputPortal(outPortal)
89  , InputOffset(inOffset)
90  , OutputOffset(outOffset)
91  {
92  }
93 
94  // MSVC likes complain about narrowing type conversions in std::copy and
95  // provides no reasonable way to disable the warning. As a work-around, this
96  // template calls std::copy if and only if the types match, otherwise falls
97  // back to a iterative casting approach. Since std::copy can only really
98  // optimize same-type copies, this shouldn't affect performance.
99  template <typename InIter, typename OutIter>
100  void DoCopy(InIter src, InIter srcEnd, OutIter dst, std::false_type) const
101  {
102  using InputType = typename InputPortalType::ValueType;
103  using OutputType = typename OutputPortalType::ValueType;
104  while (src != srcEnd)
105  {
106  // The conversion to InputType and then OutputType looks weird, but it is necessary.
107  // *src actually returns an ArrayPortalValueReference, which can automatically convert
108  // itself to InputType but not necessarily OutputType. Thus, we first convert to
109  // InputType, and then allow the conversion to OutputType.
110  *dst = static_cast<OutputType>(static_cast<InputType>(*src));
111  ++src;
112  ++dst;
113  }
114  }
115 
116 
117  template <typename InIter, typename OutIter>
118  void DoCopy(InIter src, InIter srcEnd, OutIter dst, std::true_type) const
119  {
120  std::copy(src, srcEnd, dst);
121  }
122 
123 
124 
125  void operator()(const ::tbb::blocked_range<vtkm::Id>& range) const
126  {
127  if (range.empty())
128  {
129  return;
130  }
131 
132  auto inIter = vtkm::cont::ArrayPortalToIteratorBegin(this->InputPortal);
133  auto outIter = vtkm::cont::ArrayPortalToIteratorBegin(this->OutputPortal);
134 
135  using InputType = typename InputPortalType::ValueType;
136  using OutputType = typename OutputPortalType::ValueType;
137 
138  this->DoCopy(inIter + this->InputOffset + range.begin(),
139  inIter + this->InputOffset + range.end(),
140  outIter + this->OutputOffset + range.begin(),
141  std::is_same<InputType, OutputType>());
142  }
143 };
144 
145 template <typename InputPortalType, typename OutputPortalType>
146 void CopyPortals(const InputPortalType& inPortal,
147  const OutputPortalType& outPortal,
148  vtkm::Id inOffset,
149  vtkm::Id outOffset,
150  vtkm::Id numValues)
151 {
153  Kernel kernel(inPortal, outPortal, inOffset, outOffset);
154  ::tbb::blocked_range<vtkm::Id> range(0, numValues, TBB_GRAIN_SIZE);
155  ::tbb::parallel_for(range, kernel);
156 }
157 
158 template <typename InputPortalType,
159  typename StencilPortalType,
160  typename OutputPortalType,
161  typename UnaryPredicateType>
163 {
164  using ValueType = typename InputPortalType::ValueType;
165  using StencilType = typename StencilPortalType::ValueType;
166 
167  struct Range
168  {
173 
174 
176  : InputBegin(-1)
177  , InputEnd(-1)
178  , OutputBegin(-1)
179  , OutputEnd(-1)
180  {
181  }
182 
183 
184  Range(vtkm::Id inputBegin, vtkm::Id inputEnd, vtkm::Id outputBegin, vtkm::Id outputEnd)
185  : InputBegin(inputBegin)
186  , InputEnd(inputEnd)
187  , OutputBegin(outputBegin)
188  , OutputEnd(outputEnd)
189  {
190  this->AssertSane();
191  }
192 
193 
194  void AssertSane() const
195  {
196  VTKM_ASSERT("Input begin precedes end" && this->InputBegin <= this->InputEnd);
197  VTKM_ASSERT("Output begin precedes end" && this->OutputBegin <= this->OutputEnd);
198  VTKM_ASSERT("Output not past input" && this->OutputBegin <= this->InputBegin &&
199  this->OutputEnd <= this->InputEnd);
200  VTKM_ASSERT("Output smaller than input" &&
201  (this->OutputEnd - this->OutputBegin) <= (this->InputEnd - this->InputBegin));
202  }
203 
204 
205  bool IsNext(const Range& next) const { return this->InputEnd == next.InputBegin; }
206  };
207 
208  InputPortalType InputPortal;
209  StencilPortalType StencilPortal;
210  OutputPortalType OutputPortal;
211  UnaryPredicateType UnaryPredicate;
213 
214  VTKM_CONT
215  CopyIfBody(const InputPortalType& inputPortal,
216  const StencilPortalType& stencilPortal,
217  const OutputPortalType& outputPortal,
218  UnaryPredicateType unaryPredicate)
219  : InputPortal(inputPortal)
220  , StencilPortal(stencilPortal)
221  , OutputPortal(outputPortal)
222  , UnaryPredicate(unaryPredicate)
223  {
224  }
225 
226 
227  CopyIfBody(const CopyIfBody& body, ::tbb::split)
228  : InputPortal(body.InputPortal)
230  , OutputPortal(body.OutputPortal)
232  {
233  }
234 
235 
236 
237  void operator()(const ::tbb::blocked_range<vtkm::Id>& range)
238  {
239  if (range.empty())
240  {
241  return;
242  }
243 
244  bool firstRun = this->Ranges.OutputBegin < 0; // First use of this body object
245  if (firstRun)
246  {
247  this->Ranges.InputBegin = range.begin();
248  }
249  else
250  {
251  // Must be a continuation of the previous input range:
252  VTKM_ASSERT(this->Ranges.InputEnd == range.begin());
253  }
254  this->Ranges.InputEnd = range.end();
255  this->Ranges.AssertSane();
256 
257  using InputIteratorsType = vtkm::cont::ArrayPortalToIterators<InputPortalType>;
258  using StencilIteratorsType = vtkm::cont::ArrayPortalToIterators<StencilPortalType>;
259  using OutputIteratorsType = vtkm::cont::ArrayPortalToIterators<OutputPortalType>;
260 
261  InputIteratorsType inputIters(this->InputPortal);
262  StencilIteratorsType stencilIters(this->StencilPortal);
263  OutputIteratorsType outputIters(this->OutputPortal);
264 
265  using InputIteratorType = typename InputIteratorsType::IteratorType;
266  using StencilIteratorType = typename StencilIteratorsType::IteratorType;
267  using OutputIteratorType = typename OutputIteratorsType::IteratorType;
268 
269  InputIteratorType inIter = inputIters.GetBegin();
270  StencilIteratorType stencilIter = stencilIters.GetBegin();
271  OutputIteratorType outIter = outputIters.GetBegin();
272 
273  vtkm::Id readPos = range.begin();
274  const vtkm::Id readEnd = range.end();
275 
276  // Determine output index. If we're reusing the body, pick up where the
277  // last block left off. If not, use the input range.
278  vtkm::Id writePos;
279  if (firstRun)
280  {
281  this->Ranges.OutputBegin = range.begin();
282  this->Ranges.OutputEnd = range.begin();
283  writePos = range.begin();
284  }
285  else
286  {
287  writePos = this->Ranges.OutputEnd;
288  }
289  this->Ranges.AssertSane();
290 
291  // We're either writing at the end of a previous block, or at the input
292  // location. Either way, the write position will never be greater than
293  // the read position.
294  VTKM_ASSERT(writePos <= readPos);
295 
296  UnaryPredicateType predicate(this->UnaryPredicate);
297  for (; readPos < readEnd; ++readPos)
298  {
299  if (predicate(stencilIter[readPos]))
300  {
301  outIter[writePos] = inIter[readPos];
302  ++writePos;
303  }
304  }
305 
306  this->Ranges.OutputEnd = writePos;
307  }
308 
309 
310 
311  void join(const CopyIfBody& rhs)
312  {
313  using OutputIteratorsType = vtkm::cont::ArrayPortalToIterators<OutputPortalType>;
314  using OutputIteratorType = typename OutputIteratorsType::IteratorType;
315 
316  OutputIteratorsType outputIters(this->OutputPortal);
317  OutputIteratorType outIter = outputIters.GetBegin();
318 
319  this->Ranges.AssertSane();
320  rhs.Ranges.AssertSane();
321  // Ensure that we're joining two consecutive subsets of the input:
322  VTKM_ASSERT(this->Ranges.IsNext(rhs.Ranges));
323 
324  vtkm::Id srcBegin = rhs.Ranges.OutputBegin;
325  const vtkm::Id srcEnd = rhs.Ranges.OutputEnd;
326  const vtkm::Id dstBegin = this->Ranges.OutputEnd;
327 
328  // move data:
329  if (srcBegin != dstBegin && srcBegin != srcEnd)
330  {
331  // Sanity check:
332  VTKM_ASSERT(srcBegin < srcEnd);
333  std::copy(outIter + srcBegin, outIter + srcEnd, outIter + dstBegin);
334  }
335 
336  this->Ranges.InputEnd = rhs.Ranges.InputEnd;
337  this->Ranges.OutputEnd += srcEnd - srcBegin;
338  this->Ranges.AssertSane();
339  }
340 };
341 
342 
343 template <typename InputPortalType,
344  typename StencilPortalType,
345  typename OutputPortalType,
346  typename UnaryPredicateType>
347 VTKM_CONT vtkm::Id CopyIfPortals(InputPortalType inputPortal,
348  StencilPortalType stencilPortal,
349  OutputPortalType outputPortal,
350  UnaryPredicateType unaryPredicate)
351 {
352  const vtkm::Id inputLength = inputPortal.GetNumberOfValues();
353  VTKM_ASSERT(inputLength == stencilPortal.GetNumberOfValues());
354 
355  if (inputLength == 0)
356  {
357  return 0;
358  }
359 
361  inputPortal, stencilPortal, outputPortal, unaryPredicate);
362  ::tbb::blocked_range<vtkm::Id> range(0, inputLength, TBB_GRAIN_SIZE);
363 
364  ::tbb::parallel_reduce(range, body);
365 
366  body.Ranges.AssertSane();
367  VTKM_ASSERT(body.Ranges.InputBegin == 0 && body.Ranges.InputEnd == inputLength &&
368  body.Ranges.OutputBegin == 0 && body.Ranges.OutputEnd <= inputLength);
369 
370  return body.Ranges.OutputEnd;
371 }
372 
373 template <class InputPortalType, class T, class BinaryOperationType>
375 {
376  T Sum;
378  bool FirstCall;
379  InputPortalType InputPortal;
380  BinaryOperationType BinaryOperation;
381 
382  VTKM_CONT
383  ReduceBody(const InputPortalType& inputPortal,
384  T initialValue,
385  BinaryOperationType binaryOperation)
386  : Sum(vtkm::TypeTraits<T>::ZeroInitialization())
387  , InitialValue(initialValue)
388  , FirstCall(true)
389  , InputPortal(inputPortal)
390  , BinaryOperation(binaryOperation)
391  {
392  }
393 
394 
395  ReduceBody(const ReduceBody& body, ::tbb::split)
396  : Sum(vtkm::TypeTraits<T>::ZeroInitialization())
397  , InitialValue(body.InitialValue)
398  , FirstCall(true)
399  , InputPortal(body.InputPortal)
401  {
402  }
403 
404 
405 
406  void operator()(const ::tbb::blocked_range<vtkm::Id>& range)
407  {
408  using InputIteratorsType = vtkm::cont::ArrayPortalToIterators<InputPortalType>;
409  InputIteratorsType inputIterators(this->InputPortal);
410 
411  //use temp, and iterators instead of member variable to reduce false sharing
412  typename InputIteratorsType::IteratorType inIter =
413  inputIterators.GetBegin() + static_cast<std::ptrdiff_t>(range.begin());
414 
415  T temp = this->BinaryOperation(*inIter, *(inIter + 1));
416  ++inIter;
417  ++inIter;
418  for (vtkm::Id index = range.begin() + 2; index != range.end(); ++index, ++inIter)
419  {
420  temp = this->BinaryOperation(temp, *inIter);
421  }
422 
423  //determine if we also have to add the initial value to temp
424  if (range.begin() == 0)
425  {
426  temp = this->BinaryOperation(temp, this->InitialValue);
427  }
428 
429  //Now we can save temp back to sum, taking into account if
430  //this task has been called before, and the sum value needs
431  //to also be reduced.
432  if (this->FirstCall)
433  {
434  this->Sum = temp;
435  }
436  else
437  {
438  this->Sum = this->BinaryOperation(this->Sum, temp);
439  }
440 
441  this->FirstCall = false;
442  }
443 
444 
445 
446  void join(const ReduceBody& left)
447  {
448  // std::cout << "join" << std::endl;
449  this->Sum = this->BinaryOperation(left.Sum, this->Sum);
450  }
451 };
452 
453 
454 template <class InputPortalType, typename T, class BinaryOperationType>
455 VTKM_CONT static auto ReducePortals(InputPortalType inputPortal,
456  T initialValue,
457  BinaryOperationType binaryOperation)
458  -> decltype(binaryOperation(initialValue, inputPortal.Get(0)))
459 {
460  using ResultType = decltype(binaryOperation(initialValue, inputPortal.Get(0)));
461  using WrappedBinaryOp = internal::WrappedBinaryOperator<ResultType, BinaryOperationType>;
462 
463  WrappedBinaryOp wrappedBinaryOp(binaryOperation);
464  ReduceBody<InputPortalType, ResultType, WrappedBinaryOp> body(
465  inputPortal, initialValue, wrappedBinaryOp);
466  vtkm::Id arrayLength = inputPortal.GetNumberOfValues();
467 
468  if (arrayLength > 1)
469  {
470  ::tbb::blocked_range<vtkm::Id> range(0, arrayLength, TBB_GRAIN_SIZE);
471  ::tbb::parallel_reduce(range, body);
472  return body.Sum;
473  }
474  else if (arrayLength == 1)
475  {
476  //ReduceBody does not work with an array of size 1.
477  return binaryOperation(initialValue, inputPortal.Get(0));
478  }
479  else // arrayLength == 0
480  {
481  // ReduceBody does not work with an array of size 0.
482  return static_cast<ResultType>(initialValue);
483  }
484 }
485 
486 // Define this to print out timing information from the reduction and join
487 // operations in the tbb ReduceByKey algorithm:
488 //#define VTKM_DEBUG_TBB_RBK
489 
490 template <typename KeysInPortalType,
491  typename ValuesInPortalType,
492  typename KeysOutPortalType,
493  typename ValuesOutPortalType,
494  class BinaryOperationType>
496 {
497  using KeyType = typename KeysInPortalType::ValueType;
498  using ValueType = typename ValuesInPortalType::ValueType;
499 
500  struct Range
501  {
506 
507 
509  : InputBegin(-1)
510  , InputEnd(-1)
511  , OutputBegin(-1)
512  , OutputEnd(-1)
513  {
514  }
515 
516 
517  Range(vtkm::Id inputBegin, vtkm::Id inputEnd, vtkm::Id outputBegin, vtkm::Id outputEnd)
518  : InputBegin(inputBegin)
519  , InputEnd(inputEnd)
520  , OutputBegin(outputBegin)
521  , OutputEnd(outputEnd)
522  {
523  this->AssertSane();
524  }
525 
526 
527  void AssertSane() const
528  {
529  VTKM_ASSERT("Input begin precedes end" && this->InputBegin <= this->InputEnd);
530  VTKM_ASSERT("Output begin precedes end" && this->OutputBegin <= this->OutputEnd);
531  VTKM_ASSERT("Output not past input" && this->OutputBegin <= this->InputBegin &&
532  this->OutputEnd <= this->InputEnd);
533  VTKM_ASSERT("Output smaller than input" &&
534  (this->OutputEnd - this->OutputBegin) <= (this->InputEnd - this->InputBegin));
535  }
536 
537 
538  bool IsNext(const Range& next) const { return this->InputEnd == next.InputBegin; }
539  };
540 
541  KeysInPortalType KeysInPortal;
542  ValuesInPortalType ValuesInPortal;
543  KeysOutPortalType KeysOutPortal;
544  ValuesOutPortalType ValuesOutPortal;
545  BinaryOperationType BinaryOperation;
547 #ifdef VTKM_DEBUG_TBB_RBK
548  double ReduceTime;
549  double JoinTime;
550 #endif
551 
552  VTKM_CONT
553  ReduceByKeyBody(const KeysInPortalType& keysInPortal,
554  const ValuesInPortalType& valuesInPortal,
555  const KeysOutPortalType& keysOutPortal,
556  const ValuesOutPortalType& valuesOutPortal,
557  BinaryOperationType binaryOperation)
558  : KeysInPortal(keysInPortal)
559  , ValuesInPortal(valuesInPortal)
560  , KeysOutPortal(keysOutPortal)
561  , ValuesOutPortal(valuesOutPortal)
562  , BinaryOperation(binaryOperation)
563 #ifdef VTKM_DEBUG_TBB_RBK
564  , ReduceTime(0)
565  , JoinTime(0)
566 #endif
567  {
568  }
569 
570 
571  ReduceByKeyBody(const ReduceByKeyBody& body, ::tbb::split)
572  : KeysInPortal(body.KeysInPortal)
577 #ifdef VTKM_DEBUG_TBB_RBK
578  , ReduceTime(0)
579  , JoinTime(0)
580 #endif
581  {
582  }
583 
584 
585 
586  void operator()(const ::tbb::blocked_range<vtkm::Id>& range)
587  {
588 #ifdef VTKM_DEBUG_TBB_RBK
589  ::tbb::tick_count startTime = ::tbb::tick_count::now();
590 #endif // VTKM_DEBUG_TBB_RBK
591  if (range.empty())
592  {
593  return;
594  }
595 
596  bool firstRun = this->Ranges.OutputBegin < 0; // First use of this body object
597  if (firstRun)
598  {
599  this->Ranges.InputBegin = range.begin();
600  }
601  else
602  {
603  // Must be a continuation of the previous input range:
604  VTKM_ASSERT(this->Ranges.InputEnd == range.begin());
605  }
606  this->Ranges.InputEnd = range.end();
607  this->Ranges.AssertSane();
608 
609  using KeysInIteratorsType = vtkm::cont::ArrayPortalToIterators<KeysInPortalType>;
610  using ValuesInIteratorsType = vtkm::cont::ArrayPortalToIterators<ValuesInPortalType>;
611  using KeysOutIteratorsType = vtkm::cont::ArrayPortalToIterators<KeysOutPortalType>;
612  using ValuesOutIteratorsType = vtkm::cont::ArrayPortalToIterators<ValuesOutPortalType>;
613 
614  KeysInIteratorsType keysInIters(this->KeysInPortal);
615  ValuesInIteratorsType valuesInIters(this->ValuesInPortal);
616  KeysOutIteratorsType keysOutIters(this->KeysOutPortal);
617  ValuesOutIteratorsType valuesOutIters(this->ValuesOutPortal);
618 
619  using KeysInIteratorType = typename KeysInIteratorsType::IteratorType;
620  using ValuesInIteratorType = typename ValuesInIteratorsType::IteratorType;
621  using KeysOutIteratorType = typename KeysOutIteratorsType::IteratorType;
622  using ValuesOutIteratorType = typename ValuesOutIteratorsType::IteratorType;
623 
624  KeysInIteratorType keysIn = keysInIters.GetBegin();
625  ValuesInIteratorType valuesIn = valuesInIters.GetBegin();
626  KeysOutIteratorType keysOut = keysOutIters.GetBegin();
627  ValuesOutIteratorType valuesOut = valuesOutIters.GetBegin();
628 
629  vtkm::Id readPos = range.begin();
630  const vtkm::Id readEnd = range.end();
631 
632  // Determine output index. If we're reusing the body, pick up where the
633  // last block left off. If not, use the input range.
634  vtkm::Id writePos;
635  if (firstRun)
636  {
637  this->Ranges.OutputBegin = range.begin();
638  this->Ranges.OutputEnd = range.begin();
639  writePos = range.begin();
640  }
641  else
642  {
643  writePos = this->Ranges.OutputEnd;
644  }
645  this->Ranges.AssertSane();
646 
647  // We're either writing at the end of a previous block, or at the input
648  // location. Either way, the write position will never be greater than
649  // the read position.
650  VTKM_ASSERT(writePos <= readPos);
651 
652  // Initialize reduction variables:
653  BinaryOperationType functor(this->BinaryOperation);
654  KeyType currentKey = keysIn[readPos];
655  ValueType currentValue = valuesIn[readPos];
656  ++readPos;
657 
658  // If the start of the current range continues a previous key block,
659  // initialize with the previous result and decrement the write index.
660  VTKM_ASSERT(firstRun || writePos > 0);
661  if (!firstRun && keysOut[writePos - 1] == currentKey)
662  {
663  // Ensure that we'll overwrite the continued key values:
664  --writePos;
665 
666  // Update our accumulator with the partial value:
667  currentValue = functor(valuesOut[writePos], currentValue);
668  }
669 
670  // Special case: single value in range
671  if (readPos >= readEnd)
672  {
673  keysOut[writePos] = currentKey;
674  valuesOut[writePos] = currentValue;
675  ++writePos;
676 
677  this->Ranges.OutputEnd = writePos;
678  return;
679  }
680 
681  for (;;)
682  {
683  while (readPos < readEnd && currentKey == keysIn[readPos])
684  {
685  currentValue = functor(currentValue, valuesIn[readPos]);
686  ++readPos;
687  }
688 
689  VTKM_ASSERT(writePos <= readPos);
690  keysOut[writePos] = currentKey;
691  valuesOut[writePos] = currentValue;
692  ++writePos;
693 
694  if (readPos < readEnd)
695  {
696  currentKey = keysIn[readPos];
697  currentValue = valuesIn[readPos];
698  ++readPos;
699  continue;
700  }
701 
702  break;
703  }
704 
705  this->Ranges.OutputEnd = writePos;
706 
707 #ifdef VTKM_DEBUG_TBB_RBK
708  ::tbb::tick_count endTime = ::tbb::tick_count::now();
709  double time = (endTime - startTime).seconds();
710  this->ReduceTime += time;
711  std::ostringstream out;
712  out << "Reduced " << range.size() << " key/value pairs in " << time << "s. "
713  << "InRange: " << this->Ranges.InputBegin << " " << this->Ranges.InputEnd << " "
714  << "OutRange: " << this->Ranges.OutputBegin << " " << this->Ranges.OutputEnd << "\n";
715  std::cerr << out.str();
716 #endif
717  }
718 
719 
720 
721  void join(const ReduceByKeyBody& rhs)
722  {
725  using KeysIteratorType = typename KeysIteratorsType::IteratorType;
726  using ValuesIteratorType = typename ValuesIteratorsType::IteratorType;
727 
728 #ifdef VTKM_DEBUG_TBB_RBK
729  ::tbb::tick_count startTime = ::tbb::tick_count::now();
730 #endif
731 
732  this->Ranges.AssertSane();
733  rhs.Ranges.AssertSane();
734  // Ensure that we're joining two consecutive subsets of the input:
735  VTKM_ASSERT(this->Ranges.IsNext(rhs.Ranges));
736 
737  KeysIteratorsType keysIters(this->KeysOutPortal);
738  ValuesIteratorsType valuesIters(this->ValuesOutPortal);
739  KeysIteratorType keys = keysIters.GetBegin();
740  ValuesIteratorType values = valuesIters.GetBegin();
741 
742  const vtkm::Id dstBegin = this->Ranges.OutputEnd;
743  const vtkm::Id lastDstIdx = this->Ranges.OutputEnd - 1;
744 
745  vtkm::Id srcBegin = rhs.Ranges.OutputBegin;
746  const vtkm::Id srcEnd = rhs.Ranges.OutputEnd;
747 
748  // Merge boundaries if needed:
749  if (keys[srcBegin] == keys[lastDstIdx])
750  {
751  values[lastDstIdx] = this->BinaryOperation(values[lastDstIdx], values[srcBegin]);
752  ++srcBegin; // Don't copy the key/value we just reduced
753  }
754 
755  // move data:
756  if (srcBegin != dstBegin && srcBegin != srcEnd)
757  {
758  // Sanity check:
759  VTKM_ASSERT(srcBegin < srcEnd);
760  std::copy(keys + srcBegin, keys + srcEnd, keys + dstBegin);
761  std::copy(values + srcBegin, values + srcEnd, values + dstBegin);
762  }
763 
764  this->Ranges.InputEnd = rhs.Ranges.InputEnd;
765  this->Ranges.OutputEnd += srcEnd - srcBegin;
766  this->Ranges.AssertSane();
767 
768 #ifdef VTKM_DEBUG_TBB_RBK
769  ::tbb::tick_count endTime = ::tbb::tick_count::now();
770  double time = (endTime - startTime).seconds();
771  this->JoinTime += rhs.JoinTime + time;
772  std::ostringstream out;
773  out << "Joined " << (srcEnd - srcBegin) << " rhs values into body in " << time << "s. "
774  << "InRange: " << this->Ranges.InputBegin << " " << this->Ranges.InputEnd << " "
775  << "OutRange: " << this->Ranges.OutputBegin << " " << this->Ranges.OutputEnd << "\n";
776  std::cerr << out.str();
777 #endif
778  }
779 };
780 
781 
782 template <typename KeysInPortalType,
783  typename ValuesInPortalType,
784  typename KeysOutPortalType,
785  typename ValuesOutPortalType,
786  typename BinaryOperationType>
787 VTKM_CONT vtkm::Id ReduceByKeyPortals(KeysInPortalType keysInPortal,
788  ValuesInPortalType valuesInPortal,
789  KeysOutPortalType keysOutPortal,
790  ValuesOutPortalType valuesOutPortal,
791  BinaryOperationType binaryOperation)
792 {
793  const vtkm::Id inputLength = keysInPortal.GetNumberOfValues();
794  VTKM_ASSERT(inputLength == valuesInPortal.GetNumberOfValues());
795 
796  if (inputLength == 0)
797  {
798  return 0;
799  }
800 
801  using ValueType = typename ValuesInPortalType::ValueType;
802  using WrappedBinaryOp = internal::WrappedBinaryOperator<ValueType, BinaryOperationType>;
803  WrappedBinaryOp wrappedBinaryOp(binaryOperation);
804 
805  ReduceByKeyBody<KeysInPortalType,
806  ValuesInPortalType,
807  KeysOutPortalType,
808  ValuesOutPortalType,
809  WrappedBinaryOp>
810  body(keysInPortal, valuesInPortal, keysOutPortal, valuesOutPortal, wrappedBinaryOp);
811  ::tbb::blocked_range<vtkm::Id> range(0, inputLength, TBB_GRAIN_SIZE);
812 
813 #ifdef VTKM_DEBUG_TBB_RBK
814  std::cerr << "\n\nTBB ReduceByKey:\n";
815 #endif
816 
817  ::tbb::parallel_reduce(range, body);
818 
819 #ifdef VTKM_DEBUG_TBB_RBK
820  std::cerr << "Total reduce time: " << body.ReduceTime << "s\n";
821  std::cerr << "Total join time: " << body.JoinTime << "s\n";
822  std::cerr << "\nend\n";
823 #endif
824 
825  body.Ranges.AssertSane();
826  VTKM_ASSERT(body.Ranges.InputBegin == 0 && body.Ranges.InputEnd == inputLength &&
827  body.Ranges.OutputBegin == 0 && body.Ranges.OutputEnd <= inputLength);
828 
829  return body.Ranges.OutputEnd;
830 }
831 
832 #ifdef VTKM_DEBUG_TBB_RBK
833 #undef VTKM_DEBUG_TBB_RBK
834 #endif
835 
836 template <class InputPortalType, class OutputPortalType, class BinaryOperationType>
838 {
839  using ValueType = typename std::remove_reference<typename OutputPortalType::ValueType>::type;
841  bool FirstCall;
842  InputPortalType InputPortal;
843  OutputPortalType OutputPortal;
844  BinaryOperationType BinaryOperation;
845 
846  VTKM_CONT
847  ScanInclusiveBody(const InputPortalType& inputPortal,
848  const OutputPortalType& outputPortal,
849  BinaryOperationType binaryOperation)
850  : Sum(vtkm::TypeTraits<ValueType>::ZeroInitialization())
851  , FirstCall(true)
852  , InputPortal(inputPortal)
853  , OutputPortal(outputPortal)
854  , BinaryOperation(binaryOperation)
855  {
856  }
857 
858 
859  ScanInclusiveBody(const ScanInclusiveBody& body, ::tbb::split)
860  : Sum(vtkm::TypeTraits<ValueType>::ZeroInitialization())
861  , FirstCall(true)
862  , InputPortal(body.InputPortal)
863  , OutputPortal(body.OutputPortal)
865  {
866  }
867 
868 
869 
870  void operator()(const ::tbb::blocked_range<vtkm::Id>& range, ::tbb::pre_scan_tag)
871  {
872  using InputIteratorsType = vtkm::cont::ArrayPortalToIterators<InputPortalType>;
873  InputIteratorsType inputIterators(this->InputPortal);
874 
875  //use temp, and iterators instead of member variable to reduce false sharing
876  typename InputIteratorsType::IteratorType inIter =
877  inputIterators.GetBegin() + static_cast<std::ptrdiff_t>(range.begin());
878  ValueType temp = this->FirstCall ? *inIter++ : this->BinaryOperation(this->Sum, *inIter++);
879  this->FirstCall = false;
880  for (vtkm::Id index = range.begin() + 1; index != range.end(); ++index, ++inIter)
881  {
882  temp = this->BinaryOperation(temp, *inIter);
883  }
884  this->Sum = temp;
885  }
886 
887 
888 
889  void operator()(const ::tbb::blocked_range<vtkm::Id>& range, ::tbb::final_scan_tag)
890  {
891  using InputIteratorsType = vtkm::cont::ArrayPortalToIterators<InputPortalType>;
892  using OutputIteratorsType = vtkm::cont::ArrayPortalToIterators<OutputPortalType>;
893 
894  InputIteratorsType inputIterators(this->InputPortal);
895  OutputIteratorsType outputIterators(this->OutputPortal);
896 
897  //use temp, and iterators instead of member variable to reduce false sharing
898  typename InputIteratorsType::IteratorType inIter =
899  inputIterators.GetBegin() + static_cast<std::ptrdiff_t>(range.begin());
900  typename OutputIteratorsType::IteratorType outIter =
901  outputIterators.GetBegin() + static_cast<std::ptrdiff_t>(range.begin());
902  ValueType temp = this->FirstCall ? *inIter++ : this->BinaryOperation(this->Sum, *inIter++);
903  this->FirstCall = false;
904  *outIter++ = temp;
905  for (vtkm::Id index = range.begin() + 1; index != range.end(); ++index, ++inIter, ++outIter)
906  {
907  *outIter = temp = this->BinaryOperation(temp, *inIter);
908  }
909  this->Sum = temp;
910  }
911 
912 
913 
914  void reverse_join(const ScanInclusiveBody& left)
915  {
916  this->Sum = this->BinaryOperation(left.Sum, this->Sum);
917  }
918 
919 
920 
921  void assign(const ScanInclusiveBody& src) { this->Sum = src.Sum; }
922 };
923 
924 template <class InputPortalType, class OutputPortalType, class BinaryOperationType>
926 {
927  using ValueType = typename std::remove_reference<typename OutputPortalType::ValueType>::type;
928 
930  bool FirstCall;
931  InputPortalType InputPortal;
932  OutputPortalType OutputPortal;
933  BinaryOperationType BinaryOperation;
934 
935  VTKM_CONT
936  ScanExclusiveBody(const InputPortalType& inputPortal,
937  const OutputPortalType& outputPortal,
938  BinaryOperationType binaryOperation,
939  const ValueType& initialValue)
940  : Sum(initialValue)
941  , FirstCall(true)
942  , InputPortal(inputPortal)
943  , OutputPortal(outputPortal)
944  , BinaryOperation(binaryOperation)
945  {
946  }
947 
948 
949  ScanExclusiveBody(const ScanExclusiveBody& body, ::tbb::split)
950  : Sum(body.Sum)
951  , FirstCall(true)
952  , InputPortal(body.InputPortal)
953  , OutputPortal(body.OutputPortal)
955  {
956  }
957 
958 
959 
960  void operator()(const ::tbb::blocked_range<vtkm::Id>& range, ::tbb::pre_scan_tag)
961  {
962  using InputIteratorsType = vtkm::cont::ArrayPortalToIterators<InputPortalType>;
963  InputIteratorsType inputIterators(this->InputPortal);
964 
965  //move the iterator to the first item
966  typename InputIteratorsType::IteratorType iter =
967  inputIterators.GetBegin() + static_cast<std::ptrdiff_t>(range.begin());
968 
969  ValueType temp = *iter;
970  ++iter;
971  if (!(this->FirstCall && range.begin() > 0))
972  {
973  temp = this->BinaryOperation(this->Sum, temp);
974  }
975  for (vtkm::Id index = range.begin() + 1; index != range.end(); ++index, ++iter)
976  {
977  temp = this->BinaryOperation(temp, *iter);
978  }
979  this->Sum = temp;
980  this->FirstCall = false;
981  }
982 
983 
984 
985  void operator()(const ::tbb::blocked_range<vtkm::Id>& range, ::tbb::final_scan_tag)
986  {
987  using InputIteratorsType = vtkm::cont::ArrayPortalToIterators<InputPortalType>;
988  using OutputIteratorsType = vtkm::cont::ArrayPortalToIterators<OutputPortalType>;
989 
990  InputIteratorsType inputIterators(this->InputPortal);
991  OutputIteratorsType outputIterators(this->OutputPortal);
992 
993  //move the iterators to the first item
994  typename InputIteratorsType::IteratorType inIter =
995  inputIterators.GetBegin() + static_cast<std::ptrdiff_t>(range.begin());
996  typename OutputIteratorsType::IteratorType outIter =
997  outputIterators.GetBegin() + static_cast<std::ptrdiff_t>(range.begin());
998 
999  ValueType temp = this->Sum;
1000  for (vtkm::Id index = range.begin(); index != range.end(); ++index, ++inIter, ++outIter)
1001  {
1002  //copy into a local reference since Input and Output portal
1003  //could point to the same memory location
1004  ValueType v = *inIter;
1005  *outIter = temp;
1006  temp = this->BinaryOperation(temp, v);
1007  }
1008  this->Sum = temp;
1009  this->FirstCall = false;
1010  }
1011 
1012 
1013 
1015  {
1016  //The contract we have with TBB is that they will only join
1017  //two objects that have been scanned, or two objects which
1018  //haven't been scanned
1019  VTKM_ASSERT(left.FirstCall == this->FirstCall);
1020  if (!left.FirstCall && !this->FirstCall)
1021  {
1022  this->Sum = this->BinaryOperation(left.Sum, this->Sum);
1023  }
1024  }
1025 
1026 
1027 
1028  void assign(const ScanExclusiveBody& src) { this->Sum = src.Sum; }
1029 };
1030 
1031 
1032 template <class InputPortalType, class OutputPortalType, class BinaryOperationType>
1033 VTKM_CONT static typename std::remove_reference<typename OutputPortalType::ValueType>::type
1034 ScanInclusivePortals(InputPortalType inputPortal,
1035  OutputPortalType outputPortal,
1036  BinaryOperationType binaryOperation)
1037 {
1038  using ValueType = typename std::remove_reference<typename OutputPortalType::ValueType>::type;
1039 
1040  using WrappedBinaryOp = internal::WrappedBinaryOperator<ValueType, BinaryOperationType>;
1041 
1042  WrappedBinaryOp wrappedBinaryOp(binaryOperation);
1043  ScanInclusiveBody<InputPortalType, OutputPortalType, WrappedBinaryOp> body(
1044  inputPortal, outputPortal, wrappedBinaryOp);
1045  vtkm::Id arrayLength = inputPortal.GetNumberOfValues();
1046 
1047  ::tbb::blocked_range<vtkm::Id> range(0, arrayLength, TBB_GRAIN_SIZE);
1048  ::tbb::parallel_scan(range, body);
1049  return body.Sum;
1050 }
1051 
1052 
1053 template <class InputPortalType, class OutputPortalType, class BinaryOperationType>
1054 VTKM_CONT static typename std::remove_reference<typename OutputPortalType::ValueType>::type
1055 ScanExclusivePortals(
1056  InputPortalType inputPortal,
1057  OutputPortalType outputPortal,
1058  BinaryOperationType binaryOperation,
1059  typename std::remove_reference<typename OutputPortalType::ValueType>::type initialValue)
1060 {
1061  using ValueType = typename std::remove_reference<typename OutputPortalType::ValueType>::type;
1062 
1063  using WrappedBinaryOp = internal::WrappedBinaryOperator<ValueType, BinaryOperationType>;
1064 
1065  WrappedBinaryOp wrappedBinaryOp(binaryOperation);
1066  ScanExclusiveBody<InputPortalType, OutputPortalType, WrappedBinaryOp> body(
1067  inputPortal, outputPortal, wrappedBinaryOp, initialValue);
1068  vtkm::Id arrayLength = inputPortal.GetNumberOfValues();
1069 
1070  ::tbb::blocked_range<vtkm::Id> range(0, arrayLength, TBB_GRAIN_SIZE);
1071  ::tbb::parallel_scan(range, body);
1072 
1073  // Seems a little weird to me that we would return the last value in the
1074  // array rather than the sum, but that is how the function is specified.
1075  return body.Sum;
1076 }
1077 
1078 template <typename InputPortalType, typename IndexPortalType, typename OutputPortalType>
1080 {
1081 public:
1082  VTKM_CONT ScatterKernel(InputPortalType inputPortal,
1083  IndexPortalType indexPortal,
1084  OutputPortalType outputPortal)
1085  : ValuesPortal(inputPortal)
1086  , IndexPortal(indexPortal)
1087  , OutputPortal(outputPortal)
1088  {
1089  }
1090 
1091  VTKM_CONT
1092  void operator()(const ::tbb::blocked_range<vtkm::Id>& range) const
1093  {
1094  // The TBB device adapter causes array classes to be shared between
1095  // control and execution environment. This means that it is possible for
1096  // an exception to be thrown even though this is typically not allowed.
1097  // Throwing an exception from here is bad because there are several
1098  // simultaneous threads running. Get around the problem by catching the
1099  // error and setting the message buffer as expected.
1100  try
1101  {
1102  VTKM_VECTORIZATION_PRE_LOOP
1103  for (vtkm::Id i = range.begin(); i < range.end(); i++)
1104  {
1105  VTKM_VECTORIZATION_IN_LOOP
1106  OutputPortal.Set(i, ValuesPortal.Get(IndexPortal.Get(i)));
1107  }
1108  }
1109  catch (vtkm::cont::Error& error)
1110  {
1111  this->ErrorMessage.RaiseError(error.GetMessage().c_str());
1112  }
1113  catch (...)
1114  {
1115  this->ErrorMessage.RaiseError("Unexpected error in execution environment.");
1116  }
1117  }
1118 
1119 private:
1120  InputPortalType ValuesPortal;
1121  IndexPortalType IndexPortal;
1122  OutputPortalType OutputPortal;
1123  vtkm::exec::internal::ErrorMessageBuffer ErrorMessage;
1124 };
1125 
1126 
1127 template <typename InputPortalType, typename IndexPortalType, typename OutputPortalType>
1128 VTKM_CONT static void ScatterPortal(InputPortalType inputPortal,
1129  IndexPortalType indexPortal,
1130  OutputPortalType outputPortal)
1131 {
1132  const vtkm::Id size = inputPortal.GetNumberOfValues();
1133  VTKM_ASSERT(size == indexPortal.GetNumberOfValues());
1134 
1136  inputPortal, indexPortal, outputPortal);
1137 
1138  ::tbb::blocked_range<vtkm::Id> range(0, size, TBB_GRAIN_SIZE);
1139  ::tbb::parallel_for(range, scatter);
1140 }
1141 
1142 template <typename PortalType, typename BinaryOperationType>
1144 {
1145  using ValueType = typename PortalType::ValueType;
1146 
1147  struct Range
1148  {
1153 
1154 
1155 
1157  : InputBegin(-1)
1158  , InputEnd(-1)
1159  , OutputBegin(-1)
1160  , OutputEnd(-1)
1161  {
1162  }
1163 
1164 
1165 
1166  Range(vtkm::Id inputBegin, vtkm::Id inputEnd, vtkm::Id outputBegin, vtkm::Id outputEnd)
1167  : InputBegin(inputBegin)
1168  , InputEnd(inputEnd)
1169  , OutputBegin(outputBegin)
1170  , OutputEnd(outputEnd)
1171  {
1172  this->AssertSane();
1173  }
1174 
1175 
1176 
1177  void AssertSane() const
1178  {
1179  VTKM_ASSERT("Input begin precedes end" && this->InputBegin <= this->InputEnd);
1180  VTKM_ASSERT("Output begin precedes end" && this->OutputBegin <= this->OutputEnd);
1181  VTKM_ASSERT("Output not past input" && this->OutputBegin <= this->InputBegin &&
1182  this->OutputEnd <= this->InputEnd);
1183  VTKM_ASSERT("Output smaller than input" &&
1184  (this->OutputEnd - this->OutputBegin) <= (this->InputEnd - this->InputBegin));
1185  }
1186 
1187 
1188 
1189  bool IsNext(const Range& next) const { return this->InputEnd == next.InputBegin; }
1190  };
1191 
1192  PortalType Portal;
1193  BinaryOperationType BinaryOperation;
1195 
1196  VTKM_CONT
1197  UniqueBody(const PortalType& portal, BinaryOperationType binaryOperation)
1198  : Portal(portal)
1199  , BinaryOperation(binaryOperation)
1200  {
1201  }
1202 
1203  VTKM_CONT
1204  UniqueBody(const UniqueBody& body, ::tbb::split)
1205  : Portal(body.Portal)
1207  {
1208  }
1209 
1210 
1211 
1212  void operator()(const ::tbb::blocked_range<vtkm::Id>& range)
1213  {
1214  if (range.empty())
1215  {
1216  return;
1217  }
1218 
1219  bool firstRun = this->Ranges.OutputBegin < 0; // First use of this body object
1220  if (firstRun)
1221  {
1222  this->Ranges.InputBegin = range.begin();
1223  }
1224  else
1225  {
1226  // Must be a continuation of the previous input range:
1227  VTKM_ASSERT(this->Ranges.InputEnd == range.begin());
1228  }
1229  this->Ranges.InputEnd = range.end();
1230  this->Ranges.AssertSane();
1231 
1232  using IteratorsType = vtkm::cont::ArrayPortalToIterators<PortalType>;
1233  using IteratorType = typename IteratorsType::IteratorType;
1234 
1235  IteratorsType iters(this->Portal);
1236  IteratorType data = iters.GetBegin();
1237 
1238  vtkm::Id readPos = range.begin();
1239  const vtkm::Id readEnd = range.end();
1240 
1241  // Determine output index. If we're reusing the body, pick up where the
1242  // last block left off. If not, use the input range.
1243  vtkm::Id writePos;
1244  if (firstRun)
1245  {
1246  this->Ranges.OutputBegin = range.begin();
1247  this->Ranges.OutputEnd = range.begin();
1248  writePos = range.begin();
1249  }
1250  else
1251  {
1252  writePos = this->Ranges.OutputEnd;
1253  }
1254  this->Ranges.AssertSane();
1255 
1256  // We're either writing at the end of a previous block, or at the input
1257  // location. Either way, the write position will never be greater than
1258  // the read position.
1259  VTKM_ASSERT(writePos <= readPos);
1260 
1261  // Initialize loop variables:
1262  BinaryOperationType functor(this->BinaryOperation);
1263  ValueType current = data[readPos];
1264  ++readPos;
1265 
1266  // If the start of the current range continues a previous block of
1267  // identical elements, initialize with the previous result and decrement
1268  // the write index.
1269  VTKM_ASSERT(firstRun || writePos > 0);
1270  if (!firstRun && functor(data[writePos - 1], current))
1271  {
1272  // Ensure that we'll overwrite the duplicate value:
1273  --writePos;
1274 
1275  // Copy the last data value into current. TestingDeviceAdapter's test
1276  // using the FuseAll functor requires that the first value in a set of
1277  // duplicates must be used, and this ensures that condition is met.
1278  current = data[writePos];
1279  }
1280 
1281  // Special case: single value in range
1282  if (readPos >= readEnd)
1283  {
1284  data[writePos] = current;
1285  ++writePos;
1286 
1287  this->Ranges.OutputEnd = writePos;
1288  return;
1289  }
1290 
1291  for (;;)
1292  {
1293  // Advance readPos until the value changes
1294  while (readPos < readEnd && functor(current, data[readPos]))
1295  {
1296  ++readPos;
1297  }
1298 
1299  // Write out the unique value
1300  VTKM_ASSERT(writePos <= readPos);
1301  data[writePos] = current;
1302  ++writePos;
1303 
1304  // Update the current value if there are more entries
1305  if (readPos < readEnd)
1306  {
1307  current = data[readPos];
1308  ++readPos;
1309  continue;
1310  }
1311 
1312  // Input range is exhausted if we reach this point.
1313  break;
1314  }
1315 
1316  this->Ranges.OutputEnd = writePos;
1317  }
1318 
1319 
1320 
1321  void join(const UniqueBody& rhs)
1322  {
1323  using IteratorsType = vtkm::cont::ArrayPortalToIterators<PortalType>;
1324  using IteratorType = typename IteratorsType::IteratorType;
1325 
1326  this->Ranges.AssertSane();
1327  rhs.Ranges.AssertSane();
1328 
1329  // Ensure that we're joining two consecutive subsets of the input:
1330  VTKM_ASSERT(this->Ranges.IsNext(rhs.Ranges));
1331 
1332  IteratorsType iters(this->Portal);
1333  IteratorType data = iters.GetBegin();
1334  BinaryOperationType functor(this->BinaryOperation);
1335 
1336  const vtkm::Id dstBegin = this->Ranges.OutputEnd;
1337  const vtkm::Id lastDstIdx = this->Ranges.OutputEnd - 1;
1338 
1339  vtkm::Id srcBegin = rhs.Ranges.OutputBegin;
1340  const vtkm::Id srcEnd = rhs.Ranges.OutputEnd;
1341 
1342  // Merge boundaries if needed:
1343  if (functor(data[srcBegin], data[lastDstIdx]))
1344  {
1345  ++srcBegin; // Don't copy the duplicate value
1346  }
1347 
1348  // move data:
1349  if (srcBegin != dstBegin && srcBegin != srcEnd)
1350  {
1351  // Sanity check:
1352  VTKM_ASSERT(srcBegin < srcEnd);
1353  std::copy(data + srcBegin, data + srcEnd, data + dstBegin);
1354  }
1355 
1356  this->Ranges.InputEnd = rhs.Ranges.InputEnd;
1357  this->Ranges.OutputEnd += srcEnd - srcBegin;
1358  this->Ranges.AssertSane();
1359  }
1360 };
1361 
1362 
1363 template <typename PortalType, typename BinaryOperationType>
1364 VTKM_CONT vtkm::Id UniquePortals(PortalType portal, BinaryOperationType binaryOperation)
1365 {
1366  const vtkm::Id inputLength = portal.GetNumberOfValues();
1367  if (inputLength == 0)
1368  {
1369  return 0;
1370  }
1371 
1372  using WrappedBinaryOp = internal::WrappedBinaryOperator<bool, BinaryOperationType>;
1373  WrappedBinaryOp wrappedBinaryOp(binaryOperation);
1374 
1375  UniqueBody<PortalType, WrappedBinaryOp> body(portal, wrappedBinaryOp);
1376  ::tbb::blocked_range<vtkm::Id> range(0, inputLength, TBB_GRAIN_SIZE);
1377 
1378  ::tbb::parallel_reduce(range, body);
1379 
1380  body.Ranges.AssertSane();
1381  VTKM_ASSERT(body.Ranges.InputBegin == 0 && body.Ranges.InputEnd == inputLength &&
1382  body.Ranges.OutputBegin == 0 && body.Ranges.OutputEnd <= inputLength);
1383 
1384  return body.Ranges.OutputEnd;
1385 }
1386 }
1387 }
1388 }
1389 #endif //vtk_m_cont_tbb_internal_FunctorsTBB_h
vtkm::cont::ArrayPortalToIteratorBegin
VTKM_SUPPRESS_EXEC_WARNINGS VTKM_EXEC_CONT vtkm::cont::ArrayPortalToIterators< PortalType >::IteratorType ArrayPortalToIteratorBegin(const PortalType &portal)
Convenience function for converting an ArrayPortal to a begin iterator.
Definition: ArrayPortalToIterators.h:178
vtkm::cont::tbb::UniqueBody::ValueType
typename PortalType::ValueType ValueType
Definition: FunctorsTBB.h:1145
vtkm::cont::tbb::CopyIfPortals
VTKM_CONT vtkm::Id CopyIfPortals(InputPortalType inputPortal, StencilPortalType stencilPortal, OutputPortalType outputPortal, UnaryPredicateType unaryPredicate)
Definition: FunctorsTBB.h:347
vtkm::cont::tbb::ScanInclusiveBody::ValueType
typename std::remove_reference< typename OutputPortalType::ValueType >::type ValueType
Definition: FunctorsTBB.h:839
vtkm::cont::tbb::ScanInclusiveBody
Definition: FunctorsTBB.h:837
vtkm::cont::tbb::ReduceByKeyBody::Range::IsNext
bool IsNext(const Range &next) const
Definition: FunctorsTBB.h:538
vtkm::cont::tbb::CopyIfBody::Range::OutputBegin
vtkm::Id OutputBegin
Definition: FunctorsTBB.h:171
vtkm::cont::tbb::CopyBody::CopyBody
CopyBody(const InputPortalType &inPortal, const OutputPortalType &outPortal, vtkm::Id inOffset, vtkm::Id outOffset)
Definition: FunctorsTBB.h:83
vtkm::cont::tbb::CopyIfBody::Ranges
Range Ranges
Definition: FunctorsTBB.h:212
vtkm::cont::tbb::CopyIfBody::Range::InputEnd
vtkm::Id InputEnd
Definition: FunctorsTBB.h:170
vtkm::cont::tbb::ReduceBody::FirstCall
bool FirstCall
Definition: FunctorsTBB.h:378
vtkm::cont::tbb::CopyIfBody::join
void join(const CopyIfBody &rhs)
Definition: FunctorsTBB.h:311
FunctorsGeneral.h
vtkm::cont::tbb::ReduceByKeyBody::join
void join(const ReduceByKeyBody &rhs)
Definition: FunctorsTBB.h:721
vtkm::cont::tbb::UniqueBody::Range::Range
Range(vtkm::Id inputBegin, vtkm::Id inputEnd, vtkm::Id outputBegin, vtkm::Id outputEnd)
Definition: FunctorsTBB.h:1166
vtkm::cont::tbb::UniqueBody::BinaryOperation
BinaryOperationType BinaryOperation
Definition: FunctorsTBB.h:1193
vtkm
Groups connected points that have the same field value.
Definition: Atomic.h:19
vtkm::cont::tbb::CopyBody::OutputPortal
OutputPortalType OutputPortal
Definition: FunctorsTBB.h:79
vtkm::cont::tbb::ReduceByKeyBody::BinaryOperation
BinaryOperationType BinaryOperation
Definition: FunctorsTBB.h:545
vtkm::cont::tbb::ScanInclusiveBody::reverse_join
void reverse_join(const ScanInclusiveBody &left)
Definition: FunctorsTBB.h:914
vtkm::cont::tbb::ReduceBody::Sum
T Sum
Definition: FunctorsTBB.h:376
vtkm::TypeTraits
The TypeTraits class provides helpful compile-time information about the basic types used in VTKm (an...
Definition: TypeTraits.h:61
vtkm::cont::tbb::ReduceByKeyBody::Range
Definition: FunctorsTBB.h:500
vtkm::cont::tbb::ReduceByKeyBody::ReduceByKeyBody
VTKM_CONT ReduceByKeyBody(const KeysInPortalType &keysInPortal, const ValuesInPortalType &valuesInPortal, const KeysOutPortalType &keysOutPortal, const ValuesOutPortalType &valuesOutPortal, BinaryOperationType binaryOperation)
Definition: FunctorsTBB.h:553
Types.h
vtkm::cont::tbb::ReduceByKeyBody::Range::OutputEnd
vtkm::Id OutputEnd
Definition: FunctorsTBB.h:505
VTKM_ASSERT
#define VTKM_ASSERT(condition)
Definition: Assert.h:43
vtkm::cont::tbb::ScanInclusiveBody::BinaryOperation
BinaryOperationType BinaryOperation
Definition: FunctorsTBB.h:844
vtkm::cont::tbb::UniqueBody::UniqueBody
VTKM_CONT UniqueBody(const PortalType &portal, BinaryOperationType binaryOperation)
Definition: FunctorsTBB.h:1197
vtkm::cont::tbb::UniqueBody::UniqueBody
VTKM_CONT UniqueBody(const UniqueBody &body, ::tbb::split)
Definition: FunctorsTBB.h:1204
vtkm::cont::tbb::ScatterKernel::ValuesPortal
InputPortalType ValuesPortal
Definition: FunctorsTBB.h:1120
vtkm::cont::tbb::ScanInclusiveBody::assign
void assign(const ScanInclusiveBody &src)
Definition: FunctorsTBB.h:921
vtkm::cont::tbb::UniqueBody::Range::AssertSane
void AssertSane() const
Definition: FunctorsTBB.h:1177
ArrayPortalToIterators.h
vtkm::cont::tbb::ScanInclusiveBody::Sum
ValueType Sum
Definition: FunctorsTBB.h:840
vtkm::cont::tbb::ScanExclusiveBody::assign
void assign(const ScanExclusiveBody &src)
Definition: FunctorsTBB.h:1028
vtkm::cont::tbb::UniqueBody::join
void join(const UniqueBody &rhs)
Definition: FunctorsTBB.h:1321
vtkm::cont::tbb::ReduceBody::ReduceBody
ReduceBody(const ReduceBody &body, ::tbb::split)
Definition: FunctorsTBB.h:395
vtkm::cont::tbb::ReduceBody::BinaryOperation
BinaryOperationType BinaryOperation
Definition: FunctorsTBB.h:380
vtkm::cont::tbb::ReduceByKeyBody::Range::Range
Range()
Definition: FunctorsTBB.h:508
vtkm::cont::tbb::ScatterKernel::ScatterKernel
VTKM_CONT ScatterKernel(InputPortalType inputPortal, IndexPortalType indexPortal, OutputPortalType outputPortal)
Definition: FunctorsTBB.h:1082
vtkm::cont::tbb::UniqueBody::Range::OutputBegin
vtkm::Id OutputBegin
Definition: FunctorsTBB.h:1151
vtkm::cont::Error
The superclass of all exceptions thrown by any VTKm function or method.
Definition: Error.h:33
vtkm::cont::tbb::CopyIfBody::Range::InputBegin
vtkm::Id InputBegin
Definition: FunctorsTBB.h:169
vtkm::cont::tbb::UniqueBody::Range
Definition: FunctorsTBB.h:1147
vtkm::cont::tbb::ReduceByKeyBody::ValuesInPortal
ValuesInPortalType ValuesInPortal
Definition: FunctorsTBB.h:542
vtkm::cont::tbb::UniquePortals
VTKM_CONT vtkm::Id UniquePortals(PortalType portal, BinaryOperationType binaryOperation)
Definition: FunctorsTBB.h:1364
vtkm::cont::tbb::CopyBody
Definition: FunctorsTBB.h:76
vtkm::cont::tbb::CopyBody::DoCopy
void DoCopy(InIter src, InIter srcEnd, OutIter dst, std::true_type) const
Definition: FunctorsTBB.h:118
vtkm::cont::tbb::ReduceBody::ReduceBody
VTKM_CONT ReduceBody(const InputPortalType &inputPortal, T initialValue, BinaryOperationType binaryOperation)
Definition: FunctorsTBB.h:383
vtkm::cont::tbb::CopyIfBody::Range::Range
Range()
Definition: FunctorsTBB.h:175
vtkm::cont::tbb::UniqueBody::Portal
PortalType Portal
Definition: FunctorsTBB.h:1192
vtkm::cont::tbb::ScanExclusiveBody::reverse_join
void reverse_join(const ScanExclusiveBody &left)
Definition: FunctorsTBB.h:1014
vtkm::cont::tbb::ReduceByKeyBody::KeyType
typename KeysInPortalType::ValueType KeyType
Definition: FunctorsTBB.h:497
vtkm::Id
vtkm::Int32 Id
Represents an ID (index into arrays).
Definition: Types.h:191
vtkm::cont::tbb::CopyBody::InputOffset
vtkm::Id InputOffset
Definition: FunctorsTBB.h:80
vtkm::cont::tbb::ReduceByKeyBody::Range::Range
Range(vtkm::Id inputBegin, vtkm::Id inputEnd, vtkm::Id outputBegin, vtkm::Id outputEnd)
Definition: FunctorsTBB.h:517
vtkm::cont::tbb::ReduceByKeyBody::Range::InputEnd
vtkm::Id InputEnd
Definition: FunctorsTBB.h:503
vtkm::cont::tbb::ScanInclusiveBody::InputPortal
InputPortalType InputPortal
Definition: FunctorsTBB.h:842
vtkm::cont::tbb::UniqueBody::Range::IsNext
bool IsNext(const Range &next) const
Definition: FunctorsTBB.h:1189
vtkm::cont::tbb::ReduceByKeyBody::ReduceByKeyBody
ReduceByKeyBody(const ReduceByKeyBody &body, ::tbb::split)
Definition: FunctorsTBB.h:571
vtkm::cont::tbb::UniqueBody::Ranges
Range Ranges
Definition: FunctorsTBB.h:1194
vtkm::cont::tbb::ScanExclusiveBody::FirstCall
bool FirstCall
Definition: FunctorsTBB.h:930
vtkm::cont::tbb::ReduceByKeyBody
Definition: FunctorsTBB.h:495
vtkm::cont::tbb::CopyIfBody::StencilPortal
StencilPortalType StencilPortal
Definition: FunctorsTBB.h:209
TypeTraits.h
vtkm::cont::tbb::CopyIfBody::Range
Definition: FunctorsTBB.h:167
vtkm::Sum
Binary Predicate that takes two arguments argument x, and y and returns sum (addition) of the two val...
Definition: BinaryOperators.h:33
vtkm::cont::tbb::ReduceByKeyBody::Range::AssertSane
void AssertSane() const
Definition: FunctorsTBB.h:527
vtkm::cont::tbb::ReduceByKeyBody::KeysInPortal
KeysInPortalType KeysInPortal
Definition: FunctorsTBB.h:541
vtkm::cont::ArrayPortalToIterators
Definition: ArrayPortalToIterators.h:27
vtkm::cont::tbb::CopyIfBody::UnaryPredicate
UnaryPredicateType UnaryPredicate
Definition: FunctorsTBB.h:211
vtkm::cont::tbb::CopyIfBody::InputPortal
InputPortalType InputPortal
Definition: FunctorsTBB.h:208
vtkm::cont::tbb::CopyIfBody::operator()
void operator()(const ::tbb::blocked_range< vtkm::Id > &range)
Definition: FunctorsTBB.h:237
ErrorMessageBuffer.h
vtkm::cont::tbb::ReduceByKeyBody::operator()
void operator()(const ::tbb::blocked_range< vtkm::Id > &range)
Definition: FunctorsTBB.h:586
vtkm::cont::tbb::CopyIfBody::Range::Range
Range(vtkm::Id inputBegin, vtkm::Id inputEnd, vtkm::Id outputBegin, vtkm::Id outputEnd)
Definition: FunctorsTBB.h:184
vtkm::cont::tbb::ReduceBody
Definition: FunctorsTBB.h:374
Error.h
vtkm::cont::tbb::ScanInclusiveBody::FirstCall
bool FirstCall
Definition: FunctorsTBB.h:841
vtkm::cont::tbb::UniqueBody
Definition: FunctorsTBB.h:1143
vtkm::cont::tbb::ScanExclusiveBody::Sum
ValueType Sum
Definition: FunctorsTBB.h:929
vtkm::cont::tbb::ReduceByKeyBody::Ranges
Range Ranges
Definition: FunctorsTBB.h:546
VTKM_CONT
#define VTKM_CONT
Definition: ExportMacros.h:57
vtkm::cont::tbb::ScatterKernel::OutputPortal
OutputPortalType OutputPortal
Definition: FunctorsTBB.h:1122
vtkm::cont::tbb::ReduceByKeyBody::ValueType
typename ValuesInPortalType::ValueType ValueType
Definition: FunctorsTBB.h:498
vtkm::cont::tbb::CopyIfBody::CopyIfBody
VTKM_CONT CopyIfBody(const InputPortalType &inputPortal, const StencilPortalType &stencilPortal, const OutputPortalType &outputPortal, UnaryPredicateType unaryPredicate)
Definition: FunctorsTBB.h:215
vtkm::cont::tbb::UniqueBody::operator()
void operator()(const ::tbb::blocked_range< vtkm::Id > &range)
Definition: FunctorsTBB.h:1212
vtkm::cont::tbb::ReduceBody::join
void join(const ReduceBody &left)
Definition: FunctorsTBB.h:446
vtkm::cont::tbb::CopyIfBody::Range::IsNext
bool IsNext(const Range &next) const
Definition: FunctorsTBB.h:205
vtkm::cont::tbb::ScatterKernel::IndexPortal
IndexPortalType IndexPortal
Definition: FunctorsTBB.h:1121
vtkm::cont::tbb::ScanExclusiveBody::operator()
void operator()(const ::tbb::blocked_range< vtkm::Id > &range, ::tbb::pre_scan_tag)
Definition: FunctorsTBB.h:960
vtkm::cont::tbb::CopyBody::OutputOffset
vtkm::Id OutputOffset
Definition: FunctorsTBB.h:81
vtkm::cont::tbb::ReduceBody::operator()
void operator()(const ::tbb::blocked_range< vtkm::Id > &range)
Definition: FunctorsTBB.h:406
vtkm::cont::tbb::ScanExclusiveBody
Definition: FunctorsTBB.h:925
vtkm::cont::Error::GetMessage
const std::string & GetMessage() const
Definition: Error.h:38
vtkm::cont::tbb::CopyIfBody::Range::AssertSane
void AssertSane() const
Definition: FunctorsTBB.h:194
vtkm::cont::tbb::CopyIfBody::StencilType
typename StencilPortalType::ValueType StencilType
Definition: FunctorsTBB.h:165
vtkm::cont::tbb::CopyIfBody::ValueType
typename InputPortalType::ValueType ValueType
Definition: FunctorsTBB.h:164
vtkm::cont::tbb::CopyBody::DoCopy
void DoCopy(InIter src, InIter srcEnd, OutIter dst, std::false_type) const
Definition: FunctorsTBB.h:100
vtkm::cont::tbb::UniqueBody::Range::Range
Range()
Definition: FunctorsTBB.h:1156
vtkm::cont::tbb::ScanInclusiveBody::OutputPortal
OutputPortalType OutputPortal
Definition: FunctorsTBB.h:843
vtkm::cont::tbb::ReduceByKeyBody::ValuesOutPortal
ValuesOutPortalType ValuesOutPortal
Definition: FunctorsTBB.h:544
vtkm::cont::tbb::ScatterKernel
Definition: FunctorsTBB.h:1079
vtkm::cont::tbb::ReduceBody::InitialValue
T InitialValue
Definition: FunctorsTBB.h:377
vtkm::cont::tbb::ScanExclusiveBody::operator()
void operator()(const ::tbb::blocked_range< vtkm::Id > &range, ::tbb::final_scan_tag)
Definition: FunctorsTBB.h:985
vtkm::cont::tbb::ScanInclusiveBody::operator()
void operator()(const ::tbb::blocked_range< vtkm::Id > &range, ::tbb::final_scan_tag)
Definition: FunctorsTBB.h:889
vtkm::cont::tbb::ScanInclusiveBody::ScanInclusiveBody
VTKM_CONT ScanInclusiveBody(const InputPortalType &inputPortal, const OutputPortalType &outputPortal, BinaryOperationType binaryOperation)
Definition: FunctorsTBB.h:847
vtkm::cont::tbb::CopyIfBody::Range::OutputEnd
vtkm::Id OutputEnd
Definition: FunctorsTBB.h:172
vtkm::cont::tbb::ReduceByKeyPortals
VTKM_CONT vtkm::Id ReduceByKeyPortals(KeysInPortalType keysInPortal, ValuesInPortalType valuesInPortal, KeysOutPortalType keysOutPortal, ValuesOutPortalType valuesOutPortal, BinaryOperationType binaryOperation)
Definition: FunctorsTBB.h:787
vtkm::cont::tbb::ScanExclusiveBody::ScanExclusiveBody
ScanExclusiveBody(const ScanExclusiveBody &body, ::tbb::split)
Definition: FunctorsTBB.h:949
vtkm::cont::tbb::ScanExclusiveBody::ValueType
typename std::remove_reference< typename OutputPortalType::ValueType >::type ValueType
Definition: FunctorsTBB.h:927
vtkm::cont::tbb::ReduceByKeyBody::KeysOutPortal
KeysOutPortalType KeysOutPortal
Definition: FunctorsTBB.h:543
vtkm::cont::tbb::ScanExclusiveBody::BinaryOperation
BinaryOperationType BinaryOperation
Definition: FunctorsTBB.h:933
vtkm::cont::tbb::UniqueBody::Range::InputBegin
vtkm::Id InputBegin
Definition: FunctorsTBB.h:1149
vtkm::cont::tbb::ScanExclusiveBody::ScanExclusiveBody
VTKM_CONT ScanExclusiveBody(const InputPortalType &inputPortal, const OutputPortalType &outputPortal, BinaryOperationType binaryOperation, const ValueType &initialValue)
Definition: FunctorsTBB.h:936
vtkm::cont::tbb::ScanInclusiveBody::ScanInclusiveBody
ScanInclusiveBody(const ScanInclusiveBody &body, ::tbb::split)
Definition: FunctorsTBB.h:859
vtkm::cont::tbb::ScanInclusiveBody::operator()
void operator()(const ::tbb::blocked_range< vtkm::Id > &range, ::tbb::pre_scan_tag)
Definition: FunctorsTBB.h:870
vtkm::cont::tbb::ScanExclusiveBody::OutputPortal
OutputPortalType OutputPortal
Definition: FunctorsTBB.h:932
vtkm::cont::tbb::CopyIfBody
Definition: FunctorsTBB.h:162
vtkm::cont::tbb::ReduceByKeyBody::Range::OutputBegin
vtkm::Id OutputBegin
Definition: FunctorsTBB.h:504
vtkm::cont::tbb::ScatterKernel::ErrorMessage
vtkm::exec::internal::ErrorMessageBuffer ErrorMessage
Definition: FunctorsTBB.h:1123
vtkm::cont::tbb::UniqueBody::Range::InputEnd
vtkm::Id InputEnd
Definition: FunctorsTBB.h:1150
vtkm::cont::tbb::CopyIfBody::OutputPortal
OutputPortalType OutputPortal
Definition: FunctorsTBB.h:210
vtkm::cont::tbb::ScatterKernel::operator()
VTKM_CONT void operator()(const ::tbb::blocked_range< vtkm::Id > &range) const
Definition: FunctorsTBB.h:1092
vtkm::cont::tbb::UniqueBody::Range::OutputEnd
vtkm::Id OutputEnd
Definition: FunctorsTBB.h:1152
Windows.h
vtkm::cont::tbb::CopyPortals
void CopyPortals(const InputPortalType &inPortal, const OutputPortalType &outPortal, vtkm::Id inOffset, vtkm::Id outOffset, vtkm::Id numValues)
Definition: FunctorsTBB.h:146
vtkm::cont::tbb::ReduceBody::InputPortal
InputPortalType InputPortal
Definition: FunctorsTBB.h:379
vtkm::cont::tbb::ScanExclusiveBody::InputPortal
InputPortalType InputPortal
Definition: FunctorsTBB.h:931
vtkm::cont::tbb::ReduceByKeyBody::Range::InputBegin
vtkm::Id InputBegin
Definition: FunctorsTBB.h:502
vtkm::cont::tbb::CopyIfBody::CopyIfBody
CopyIfBody(const CopyIfBody &body, ::tbb::split)
Definition: FunctorsTBB.h:227
vtkm::cont::tbb::CopyBody::InputPortal
InputPortalType InputPortal
Definition: FunctorsTBB.h:78
vtkm::cont::tbb::CopyBody::operator()
void operator()(const ::tbb::blocked_range< vtkm::Id > &range) const
Definition: FunctorsTBB.h:125