Array view implementations in Magnum

Sim­i­lar­ly to the point­er and ref­er­ence wrap­pers de­scribed in the last ar­ti­cle, Mag­num’s ar­ray views re­cent­ly re­ceived STL com­pat­i­bil­i­ty as well. Let’s take that as an op­por­tu­ni­ty to com­pare them with the stan­dard im­ple­men­ta­tion in std::span.

This was meant to be a short blog post show­ing the new STL com­pat­i­bil­i­ty of var­i­ous Ar­rayView class­es. How­ev­er, af­ter div­ing deep in­to std::span, there was sud­den­ly much more to write about.

The sto­ry of wait­ing for a thing to get stan­dard­ized…

Ar­ray views were un­doubte­ly one of the main work­flow-defin­ing struc­tures since they were added to Mag­num al­most six years ago; back then called ArrayReference, as I didn’t dis­cov­er the idea of slic­ing them yet. Sud­den­ly it was no longer need­ed to pass ref­er­ences to std::vec­tor / std::ar­ray around, or — the hor­ror — a point­er and a size. Back then, still in the brave new C++11 world, I won­dered how long it would take be­fore the stan­dard in­tro­duces an equiv­a­lent, al­low­ing me to get rid of my own in fa­vor of a well-test­ed, well-op­ti­mized and well-known im­ple­men­ta­tion.

Fast for­ward to 2019, we might soon be there with std::span, sched­uled for in­clu­sion in C++2a. In the mean­time, Mag­num’s Con­tain­ers::Ar­rayView sta­bi­lized, learned from its past mis­takes and was used in so many con­texts that I dare to say it’s fea­ture-com­plete. In the process it re­ceived a fixed-size vari­ant called Con­tain­ers::Stati­cAr­rayView and, most re­cent­ly, Con­tain­ers::StridedAr­rayView, for eas­i­er it­er­a­tion over sparse da­ta. I’ll be show­ing its sparse mag­ic in a lat­er ar­ti­cle.

… and ul­ti­mate­ly re­al­iz­ing it’s not re­al­ly what we want

Much like std::op­tion­al, orig­i­nal­ly sched­uled for C++11 but due to its de­sign be­com­ing more and more com­plex (constexpr sup­port, op­tion­al ref­er­ences, …), caus­ing it to be de­layed un­til C++17; std::span is, in my opin­ion, ar­riv­ing way too late as well.

In­stead of ship­ping a min­i­mal vi­able im­ple­men­ta­tion as soon as pos­si­ble to get code­bas­es jump on it — and let its fu­ture de­sign adapt to us­er feed­back — de­sign-in-a-vac­u­um means C++2a will ship with a com­plex im­ple­men­ta­tion and a set of gude­lines that users have to adapt to in­stead.

In short, the C++2a std::span pro­vides:

  • the usu­al in­dex-based and it­er­a­tor ac­cess to el­e­ments of the view,
  • both dy­nam­ic-size and fixed-size ar­ray views in a sin­gle type (which, as I un­for­tu­nate­ly soon re­al­ized, on­ly com­pli­cates ev­ery­thing with­out hav­ing any re­al ben­e­fits)
  • im­plic­it con­ver­sion from C-style ar­rays, std::ar­ray and std::vec­tor,
  • and a well-meant, but fun­da­men­tal­ly bro­ken im­plic­it con­ver­sion from any type that con­tains a data() and a size() mem­ber. If that sounds dan­ger­ous, it’s be­cause it re­al­ly is. More on that be­low.

Orig­i­nal­ly, std::span was meant to not on­ly han­dle both dy­nam­ic and fixed-size ar­ray views, but al­so mul­ti-di­men­sion­al and strid­ed views. For­tu­nate­ly such func­tion­al­i­ty was sep­a­rat­ed in­to std::mdspan, to ar­rive prob­a­bly no ear­li­er than in C++23 (again, way too late). If you want to know more about mul­ti-di­men­sion­al ar­ray views and how they com­pare to the pro­posed stan­dard con­tain­ers, have a look at Mul­ti-di­men­sion­al strid­ed ar­ray views in Mag­num.

Mag­num’s ar­ray views

So, what’s Con­tain­ers::Ar­rayView ca­pa­ble of? Like std::span, it can be im­plic­it­ly con­struct­ed from a C ar­ray ref­er­ence, or ex­plic­it­ly from a pair of point­er and a size. It’s al­so pos­si­ble to slice the ar­ray, equiv­a­lent­ly to std::span::sub­span() and friends:

float data[] { 1.0f, 4.2f, 133.7f, 2.4f };
Containers::ArrayView<float> a = data;

// Multiply the first three items 10 times
for(float& i: a.prefix(3)) i *= 10.0f;

Sim­i­lar­ly it goes for stat­i­cal­ly-sized ar­ray views. It’s pos­si­ble to con­vert be­tween dy­nam­i­cal­ly-sized and stat­i­cal­ly-sized ar­ray views us­ing fixed-size slice<n>() and re­lat­ed APIs — again, std::span has that too:

// Implicit conversion allowed only if data has 4 elements as well
Containers::StaticArrayView<float, 4> b = data;

// A function accepting a view on exactly three floats
float min3(Containers::StaticArrayView<float, 3>) { ... }

float min = min3(b.suffix<3>());

For de­bug per­for­mance rea­sons, the el­e­ment ac­cess is not bounds-checked (in fact, to re­duce the it­er­a­tion over­head even more, the views are im­plic­it­ly con­vert­ible to point­ers in­stead of pro­vid­ing cus­tom it­er­a­tors or an operator[]). On the oth­er hand, slic­ing is checked, so it­er­at­ing over a slice is pre­ferred over man­u­al­ly cal­cu­lat­ing an in­dex sub­range and in­dex­ing that way. If you step over with your slice, you’ll get a de­tailed Python-like as­ser­tion mes­sage:

a.slice(3, 7);
Containers::ArrayView::slice(): slice [3:7] out of range for 4 elements

Of course, fixed-size slices on fixed-size ar­ray views are checked al­ready at com­pile time.

STL com­pat­i­bil­i­ty

Con­tin­u­ing with how Con­tain­ers::Point­er, Con­tain­ers::Ref­er­ence and Con­tain­ers::Op­tion­al re­cent­ly be­came con­vert­ible from/to std::unique_p­tr, std::ref­er­ence_wrap­per and std::op­tion­al; ar­ray views now ex­pose a sim­i­lar func­tion­al­i­ty. The Con­tain­ers::Ar­rayView can be im­plic­it­ly cre­at­ed from a std::vec­tor or an std::ar­ray ref­er­ence, plus Con­tain­ers::Stati­cAr­rayView can be im­plic­it­ly con­vert­ed from the (fixed-size) std::ar­ray. All you need to do is in­clud­ing the Cor­rade/Con­tain­ers/Ar­rayView­Stl.h head­er to get the con­ver­sion def­i­ni­tions. Sim­i­lar­ly as men­tioned in the pre­vi­ous ar­ti­cle, it’s a sep­a­rate head­er to avoid un­con­di­tion­al heavy #include <vector> and #include <array> be­ing tran­si­tive­ly present in all code that touch­es ar­ray views. With that in place, you can do things like the fol­low­ing — with slic­ing prop­er­ly bounds-checked, but no fur­ther over­head re­sult­ing from it­er­a­tor or el­e­ment ac­cess:

#include <Corrade/Containers/ArrayViewStl.h>

std::vector<float> data;

float sum{}; // Sum of the first 100 elements
for(float i: Containers::arrayView(data).prefix(100))
    sum += i;

In case you’re feel­ing like us­ing the stan­dard C++2a std::span in­stead (or you in­ter­face with a li­brary us­ing it), there’s no need to wor­ry ei­ther. A com­pat­i­bil­i­ty with it is pro­vid­ed in Cor­rade/Con­tain­ers/Ar­rayView­StlSpan.h. As far as I’m aware, on­ly libc++ ships an im­ple­men­ta­tion of it at the mo­ment. For the span there’s many more dif­fer­ent con­ver­sion pos­si­bil­i­ties, see the docs for more in­for­ma­tion. This con­ver­sion is again sep­a­rate from the rest be­cause (at least the libc++) #include <span> man­aged to gain al­most twice the weight as both #include <vector> and #include <array> to­geth­er. I don’t know how’s that pos­si­ble for just a fan­cy pair of point­er and size with a hand­ful of one-lin­er mem­ber func­tions to be that big, but here we are.

Ar­ray cast­ing

When work­ing with graph­ics da­ta, you of­ten end up with a non-de­script “ar­ray of bytes”, com­ing from ei­ther some file for­mat or be­ing down­load­ed from the GPU. Be­ing able to rein­ter­pret them as a con­crete type is of­ten very de­sired and Mag­num pro­vides Con­tain­ers::ar­ray­Cast() for that. Be­sides change of type, it al­so prop­er­ly re­cal­cu­lates the size to cor­re­spond to the new type.

Containers::ArrayView<char> data;
auto positions = Containers::arrayCast<Vector3>(data); // array of Vector3

Apart from the con­ve­nience, its main pur­pose is to di­rect the reinterpret_cast<> ma­chine gun away from your feet. While it can’t ful­ly stop it from fir­ing, it’ll check that both types are stan­dard lay­out (so with­out vta­bles and oth­er fun­ny busi­ness), that one type has its size a mul­ti­ple of the oth­er and that the to­tal byte size of the view doesn’t change af­ter the cast. That al­lows you to do fanci­er things as well, such as rein­ter­pret­ing an ar­ray of Ma­trix3 in­to an ar­ray of its col­umn vec­tors:

Containers::ArrayView<Matrix3> poses;
auto baseVectors = Containers::arrayCast<Vector3>(poses);

Note that a cast of the poses to Vec­tor4 would not be per­mit­ted by the checks above. Which is a good thing.

Type era­sure

Com­ple­men­tary to the cast­ing func­tion­al­i­ty, some APIs in Mag­num ac­cept ar­ray views with­out re­quir­ing any par­tic­u­lar type — var­i­ous GPU da­ta up­load func­tions, im­age views and so on. Such APIs care on­ly about the da­ta point­er and byte size. A Con­tain­ers::Ar­rayView<con­st void> spe­cial­iza­tion is used for such case and to make it pos­si­ble to pass in ar­ray views of any type, it’s im­plic­it­ly con­vert­ible from them, with their size get­ting re­cal­cu­lat­ed to byte count.

Look­ing at std::span, it pro­vides some­thing sim­i­lar through std::as_bytes(), how­ev­er it’s an ex­plic­it op­er­a­tion and is us­ing the fan­cy new std::byte type (which, in my opin­ion, doesn’t add any­thing use­ful over the sim­i­lar­ly opaque void*) — and al­so, due to that, is not constexpr (while the Mag­num ar­ray view type era­sure is).

Point­er-like se­man­tics

Mag­num’s ar­ray views were de­lib­er­ate­ly cho­sen to have se­man­tics sim­i­lar to C ar­rays — they’re im­plic­it­ly con­vert­ible to its un­der­ly­ing point­er type (which, again, al­lows us to op­ti­mize de­bug per­for­mance by not hav­ing to ex­plic­it­ly pro­vide operator[]) and the usu­al point­er arith­metic works on them as well. That al­lows them to be more eas­i­ly used when in­ter­fac­ing with C APIs, for ex­am­ple like be­low. The std::span doesn’t ex­pose any such func­tion­al­i­ty.

Containers::ArrayView<const void> data;
std::FILE* file;
std::fwrite(data, 1, data.size(), file);

The point­er-like se­man­tics means al­so that operator== and oth­er com­par­i­son op­er­a­tors work the same way as on point­ers. Ac­cord­ing to cp­pref­er­ence at least, std::span doesn’t pro­vide any of these and since it doesn’t re­tain any­thing else from the point­er-like se­man­tics, it’s prob­a­bly for the bet­ter — since std::span has nei­ther re­al­ly a point­er nor a con­tain­er se­man­tics, both rea­sons for == be­hav­ior like on a point­er or like on a con­tain­er are equal­ly valid for ei­ther par­ty and equal­ly con­fus­ing for the oth­er.

Sized null views

While this seemed like an ug­ly wart at first, I have to ad­mit the whole API be­came more con­sis­tent with such fea­ture in place. It’s about the pos­si­bil­i­ty to have a view on a nullptr, but with a non-ze­ro size at­tached. This se­man­tics is used, among oth­er things, by a few OpenGL APIs, where pass­ing a null point­er to­geth­er with a size will cause a buf­fer or tex­ture to be al­lo­cat­ed but with con­tents unini­tial­ized. To do this, it seemed more nat­u­ral to al­low sized ar­ray views be cre­at­ed from nullptr than to add ded­i­cat­ed APIs for pre­al­lo­ca­tion. The fol­low­ing will pre­al­lo­cate a GPU buf­fer to 384 bytes:

GL::Buffer buffer;
buffer.setData({nullptr, 32*3*sizeof(float)});

Lat­er, when adding Con­tain­ers::Stati­cAr­rayView, this fea­ture al­lowed me to pro­vide it with an im­plic­it con­struc­tor. When check­ing out std::span, I dis­cov­ered that im­plic­it con­struc­tor of the fixed-size vari­ant is not pos­si­ble.

Containers::StaticArrayView<16, float> a;   // {nullptr, 16}
//std::span<float, 16> b;                   // doesn't compile :(

Now, let’s see those un­for­giv­ing num­bers

Be­low is the usu­al graph of pre­pro­cessed line count for each head­er, gen­er­at­ed us­ing the fol­low­ing com­mand with GCC 8.2. At the time of writ­ing, lib­st­dc++ doesn’t ship with <span> yet, so it’s ex­clud­ed from the com­par­i­son. To have more da­ta, there com­par­i­son in­cludes gsl::span im­ple­men­ta­tion from Mi­cro­soft’s Guide­line Sup­port Li­brary (ver­sion 2.0.0, re­quir­ing at least C++14) and nostd::span aka Span Lite 0.4.0 from Mar­tin Moene. As said be­fore, while pre­pro­cessed line count is not the on­ly fac­tor af­fect­ing com­pile times, it cor­re­lates with it pret­ty well.

echo "#include <vector>" | gcc -std=c++11 -P -E -x c++ - | wc -l
2451.0 lines 8608.0 lines 12029.0 lines 15117.0 lines 0.0 lines 30715.0 lines 17607.0 lines 0 5000 10000 15000 20000 25000 30000 lines <Containers/ArrayView.h> <vector> <array> <vector> + <array> <span> <gsl/span> <span.hpp> N/A C++14 Preprocessed line count, GCC 8.2, C++11

std::span ships in Clang’s libc++ 7.0 (and thus I as­sume in Xcode 10.0 as well), so here’s a com­par­i­son us­ing libc++. To make the com­par­i­son fair, it us­es the C++2a stan­dard in all cas­es:

echo "#include <span>" | clang++ -std=c++2a -stdlib=libc++ -P -E -x c++ - | wc -l
5954.0 lines 28147.0 lines 23632.0 lines 28512.0 lines 24098.0 lines 24456.0 lines 24178.0 lines 0 5000 10000 15000 20000 25000 lines <Containers/ArrayView.h> <vector> <array> <vector> + <array> <span> <gsl/span> <span.hpp> Preprocessed line count, Clang 7.0, libc++, C++2a

The Mag­num im­ple­men­ta­tion needs <type_traits> to do a bunch of SFI­NAE and com­pile-time checks, <utility> is need­ed for the std::for­ward() util­i­ty. While <utility> is com­par­a­tive­ly easy to re­place, I still don’t think writ­ing my own type traits head­ers is worth the time in­vest­ment, main­ly due to all the com­pil­er mag­ic that needs to be dif­fer­ent for each plat­form.

Com­pile times

To get some re­al tim­ing, I com­posed a tiny “mi­crobench­mark” shown be­low, with equiv­a­lent vari­ants for STL span, GSL span and span lite, us­ing both GCC 8.2 in C++11 mode and Clang 7.0 with libc++ in C++2a mode. Like in the pre­vi­ous ar­ti­cle, to bal­ance the com­par­i­son, I’m switch­ing to the stan­dard as­ser­tions by defin­ing COR­RADE_­S­TAN­DARD­_ASSERT and, for bet­ter sense of scale, there’s al­so a base­line time, which is from com­pil­ing just int main() {} with no #include at all.

#include <Corrade/Containers/ArrayView.h>

using namespace Corrade;

int main() {
    int data[]{1, 3, 42, 1337};

    auto a = Containers::arrayView(data);
    Containers::StaticArrayView<1, int> b = a.slice<1>(2);
    return b[0] - 42;
g++ main.cpp -DCORRADE_STANDARD_ASSERT -std=c++11                    # either
clang++ main.cpp -DCORRADE_STANDARD_ASSERT -std=c++2a -stdlib=libc++ # or
55.39 ± 2.47 ms 82.79 ± 6.78 ms 0.0 ± 0.0 ms 336.48 ± 14.49 ms 196.33 ± 4.19 ms 0 50 100 150 200 250 300 350 ms baseline Containers::ArrayView std::span gsl::span nonstd::span int main() {} N/A C++14 Compilation time, GCC 8.2, C++11
71.61 ± 3.28 ms 127.44 ± 3.81 ms 257.8 ± 6.56 ms 253.43 ± 3.73 ms 248.97 ± 5.23 ms 0 50 100 150 200 250 ms baseline Containers::ArrayView std::span gsl::span nonstd::span Compilation time, Clang 7.0, libc++, C++2a

De­bug per­for­mance

Look­ing at the size of as­sem­bly out­put for an un­op­ti­mized ver­sion of the snip­pet above, the Mag­num im­ple­men­ta­tion is 1/3 small­er than equiv­a­lent code writ­ten with Span Lite and about three times small­er than the same us­ing GSL span. In all cas­es the com­pil­er is able to op­ti­mize ev­ery­thing away at -O1. Un­for­tu­nate­ly Com­pil­er Ex­plor­er doesn’t have an op­tion to use libc++, so couldn’t make a com­par­i­son with std::span there.

The ba­by steps (and falls) of std::span

If you sur­vived all the way down here with­out abrupt­ly leav­ing with an ir­re­sistible urge to re­write ev­ery­thing in Rust be­come a barista in­stead, you’d think it stops just at aw­ful com­pile times. Well, no. It’s worse than that.

Hot take: im­plic­it all-catch­ing con­struc­tors are stupid

I dis­cov­ered the first is­sue when writ­ing the STL com­pat­i­bil­i­ty con­ver­sions. All Mag­num con­tain­ers and math types have a spe­cial con­struc­tor and a con­ver­sion op­er­a­tor that makes it pos­si­ble to con­vert a type ei­ther ex­plic­it­ly or — if the type is sim­ple enough, con­ver­sion not cost­ly and there are no risks of caus­ing am­bigu­ous op­er­a­tor over­loads — im­plic­it­ly from and to a third-par­ty type. This way Mag­num sup­ports seam­less us­age its math types with GLM, Bul­let Physics, Vulkan types or, for ex­am­ple, Dear ImGui.

This works well and caus­es no prob­lem as long as the third-par­ty type doesn’t have a con­struc­tor that ac­cepts any­thing you throw at it. I ran in­to this is­sue two weeks ago with Eigen, as both its Array and Matrix class­es have such a con­struc­tor. But in that case it’s not harm­ful, on­ly an­noy­ing, as the con­ver­sion can no longer be done di­rect­ly through an ex­plic­it con­ver­sion but rather us­ing some con­ver­sion func­tion.

In case of std::span, it’s much worse — there’s an all-catch­ing con­struc­tor tak­ing any con­tain­er-like type. It’s a well meant fea­ture, how­ev­er, it works even in the case of a fixed-size span — and there it gets dan­ger­ous, as shown be­low. And this is not just a cause of an im­ple­men­ta­tion is­sue in libc++, it’s de­signed this way in the stan­dard it­self — of all things (ex­cep­tions, as­serts, com­pile-time er­rors), it choos­es the worst — such con­ver­sion is de­clared as un­de­fined be­hav­ior. For­tu­nate­ly, the good peo­ple of Twit­ter al­ready rec­og­nized this as a de­fect and are work­ing on a so­lu­tion. Hope­ful­ly the fix gets in to­geth­er with the span and not tree years lat­er or some­thing.

#include <span>

struct Vec3 { // your usual Vec3 class
    size_t size() const { return 3; }
    float* data() { return _data; }
    const float* data() const { return _data; }

    private: float _data[3]{};

int main() {
    Vec3 a;
    std::span<float, 57> b = a; // this compiles?!?!

Im­plic­it con­ver­sion from std::ini­tial­iz­er_list is ac­tive­ly harf­mul

Some time ago there was a Twit­ter dis­cus­sion where it was sug­gest­ed to add a con­struc­tor tak­ing std::ini­tial­iz­er_list to an ar­ray view class. I won­dered why Mag­num’s Con­tain­ers::Ar­rayView class doesn’t have such an use­ful fea­ture … un­til I re­mem­bered why. Con­sid­er this in­no­cent-look­ing snip­pet, guess what hap­pens when you ac­cess b[0] lat­er? If you don’t know, try again with -fsanitize=address.

std::span<const std::string> b{{"hello", "there"}};
b[0]; // ?

Thing is, the above-men­tioned all-catch­ing con­struc­tor can cap­ture an std::ini­tial­iz­er_list as well, how­ev­er the prob­lem (com­pared to, let’s say, do­ing the same with a std::vec­tor), is that it gets con­struct­ed im­plic­it­ly — and so it’s very hard to re­al­ize the ini­tial­iz­er list el­e­ments are al­ready de­stroyed af­ter the semi­colon.

In case of Mag­num, rather than hav­ing ar­ray views im­plic­it­ly con­structible from std::ini­tial­iz­er_list, where it makes sense, APIs tak­ing an ar­ray view have al­so an ini­tial­iz­er list over­load. It makes the API sur­face larg­er, but that’s a rea­son­able price to pay for ar­ray views be­ing safer to use.

Sin­gle-head­er im­ple­men­ta­tion

The Mag­num Sin­gles repos­i­to­ry in­tro­duced pre­vi­ous­ly got a new neigh­bor — all the ar­ray view class­es, in a tiny, self-con­tained, de­pen­den­cy-less and fast-to-com­pile head­er file, meant to be bun­dled right in­to your project:

Li­brary LoC Pre­pro­cessed LoC De­scrip­tion
Cor­radeAr­rayView.h new 558 2453 See Con­tain­ers::Ar­rayView and Stati­cAr­rayView docs
Cor­radeOp­tion­al.h 328 2742 See Con­tain­ers::Op­tion­al docs
Cor­rade­Point­er.h 259 2321 See Con­tain­ers::Point­er docs
Cor­radeRef­er­ence.h 115 1639 See Con­tain­ers::Ref­er­ence docs
Cor­rade­Scope­Guard.h 131 34 See Con­tain­ers::Scope­Guard docs

Fun­ny thing is, even though the Con­tain­ers::Ar­rayView API is much larg­er than of Con­tain­ers::Op­tion­al, it still boils down to less code af­ter pre­pro­cess­ing — rea­son is sim­ply that the <new> in­clude was not need­ed, since ar­ray views don’t do any fan­cy al­lo­ca­tions.

* * *

Ques­tions? Com­plaints? Share your opin­ion on so­cial net­works: