[WIP] Fixing and improving algorithms with view expressions

[fuchsto]

Addresses #346, among others.

A diff that demonstrates the benefit of view expressions pretty well: https://github.com/dash-project/dash/pull/410/files#diff-c4c2bc3b549c09735c61251a8f8d8ecfR1149

With view expressions, dash::copy(lbegin, lend, gbegin) is now supported and also allows non-contiguous global destination ranges (blocked, strided, anything a pattern might define). Its full implementation:

template <class ValueType, class GlobOutputIt>
GlobOutputIt copy(
  const ValueType  * in_first,
  const ValueType  * in_last,
  GlobOutputIt       out_first) {
  // Return value, initialize with begin of output range, indicating no
  // values have been copied:
  GlobOutputIt out_last   = out_first;
  // Number of elements to copy in total:
  auto num_elements       = std::distance(in_first, in_last);
  // Global iterator pointing at hypothetical end of output range:
  GlobOutputIt out_h_last = out_first + num_elements;
  // Create range from global output iterators:
  auto out_range  = dash::make_range(out_first, out_h_last);
  // Be happy:
  auto out_blocks = dash::blocks(out_range);
  auto in_copy_it = in_first;
  for (auto block : out_blocks) {
    out_last   = static_cast<GlobOutputIt>(
                   dash::internal::copy_block(
                     in_copy_it,
                     in_copy_it + block.size(),
                     block.begin()));
    in_copy_it = in_first + dash::distance(out_first, out_last);
  }
  return out_last;
}

Also added example ex.02.array-views for illustration:

https://github.com/dash-project/dash/blob/feat-192-nviews/dash/examples/ex.02.array-views/main.cpp

  // Note that global range is strided:
  dash::Array<float> a(array_size, dash::BLOCKCYCLIC(3));
  initialize_array(a);

  auto copy_num_elem       = a.size() / 2;
  auto copy_dest_begin_idx = a.size() / 4;
  auto copy_dest_end_idx   = copy_dest_begin_idx + copy_num_elem;

  std::vector<float> buf(copy_num_elem);
  std::iota(buf.begin(), buf.end(), 0.9999);

  a.barrier();

  if (dash::myid() == 0) {
    print("array: " << range_str(a));
    print("copy target index range: "
          << "[" << copy_dest_begin_idx << "," << copy_dest_end_idx << ")");

    auto copy_begin_it   = a.begin() + copy_dest_begin_idx;
    auto copy_end_it_exp = copy_begin_it + copy_num_elem;

    auto dest_range      = dash::make_range(copy_begin_it,
                                            copy_end_it_exp);
    // Using temporaries from view expressions instead of named values to
    // test move propagation:
    print("target index set:  " << dash::index(dest_range));
    print("target block set:  " << dash::index(dash::blocks(dest_range)));
    print("copy target range: " << range_str(dest_range));

    for (const auto & block : dash::blocks(dest_range)) {
      print("copy to block: " << range_str(block));
    }
    // copy local buffer to global array:
    auto copy_end_it     = dash::copy(
                             buf.data(),
                             buf.data() + copy_num_elem,
                             copy_begin_it);
  }
  a.barrier();
  print("modified array: " << range_str(a));

Output:

$ mpirun -n 3 ./bin/ex.02.array-views.mpi
array:  0|0.0100  1|0.0201  2|0.0302  3|1.0103  4|1.0204  5|1.0305  6|2.0106  7|2.0207  8|2.0308  9|0.0409 10|0.0510 11|0.0611 12|1.0412 13|1.0513 14|1.0614 15|2.0415 16|2.0516
copy target index range: [4,12)
target index set:  int { 4 5 6 7 8 9 10 11 }
target block set:  int { 1 2 3 }
copy target range:  4|1.0204  5|1.0305  6|2.0106  7|2.0207  8|2.0308  9|0.0409 10|0.0510 11|0.0611
copy to block:  4|1.0204  5|1.0305
copy to block:  6|2.0106  7|2.0207  8|2.0308
copy to block:  9|0.0409 10|0.0510 11|0.0611
modified array:  0|0.0100  1|0.0201  2|0.0302  3|1.0103  4|0.9999  5|1.9999  6|2.9999  7|3.9999  8|4.9999  9|5.9999 10|6.9999 11|7.9999 12|1.0412 13|1.0513 14|1.0614 15|2.0415 16|2.0516
modified array:  0|0.0100  1|0.0201  2|0.0302  3|1.0103  4|0.9999  5|1.9999  6|2.9999  7|3.9999  8|4.9999  9|5.9999 10|6.9999 11|7.9999 12|1.0412 13|1.0513 14|1.0614 15|2.0415 16|2.0516
modified array:  0|0.0100  1|0.0201  2|0.0302  3|1.0103  4|0.9999  5|1.9999  6|2.9999  7|3.9999  8|4.9999  9|5.9999 10|6.9999 11|7.9999 12|1.0412 13|1.0513 14|1.0614 15|2.0415 16|2.0516

[fuchsto]

@dhinf Sorry it took me some more days, but strided multidimensional views seem to be stable now and can be used to implement halo packing. We should have a Skype session on this soon.

[fuchsto]

State in commit c170d7c is stable, now fixing dash::transform, changes in PR #398 are merged and rewritten using views.

[devreal]

What is the status of this PR? The [WIP] label has been removed a while ago and a review was requested. However, there still seems to be work going on and all checks fail. I could start a review on my overlay/flight tomorrow, but only if this PR is reasonably stable.