google / emboss

Emboss is a tool for generating code that reads and writes binary data structures.
Apache License 2.0
68 stars 21 forks source link

Make `.Ok()` on Arrays Faster #90

Open reventlov opened 1 year ago

reventlov commented 1 year ago

The generated code for .Ok() on an array is basically a loop, like:

bool Ok() const {
  for (int i = 0; i < ElementCount(); ++i) {
    if (!(*this)[i].Ok()) return false;
  }
  return true;
}

When array elements are simple types, such as UInt with no constraints, .Ok() on each element devolves to a bounds check; unfortunately, no C++ compiler appears to implement an optimization that hoists the bounds checks out of the loop, so the array .Ok() method ends up repeating a huge amount of busywork.

To remedy this, the C++ back end could emit static functions on views like bool OkIsEquivalentToIsComplete() and bool IsCompleteIsAStaticSizeCheck(), then the array's .Ok() could be something like:

bool Ok() const {
  if (decltype((*this)[0])::OkIsEquivalentToIsComplete() &&
      decltype((*this)[0])::IsCompleteIsAStaticSizeCheck()) {
    return (*this)[0].Ok();
  } else {
    for (int i = 0; i < ElementCount(); ++i) {
      if (!(*this)[i].Ok()) return false;
    }
    return true;
  }
}

In C++17, the outer if can become if constexpr.