C++Guns – RoboBlog blogging the bot

Es gibt eine Menge Implementationen und Arbeit über Intervall Datentypen in C++, aber nichts, was einfach mal einfach wäre.

Riesen Linksammlung http://www.cs.utep.edu/interval-comp/

Doc No: A Proposal to add Interval Arithmetic o the C++ Standard Library (revision 2) von 2008 http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2137.pdf

BOOST natürlich https://www.boost.org/doc/libs/1_69_0/libs/numeric/interval/doc/interval.htm

Und sogar ein Versuch in ganz modernen C++ Moore: Interval Arithmetic in C++20 https://arxiv.org/abs/1802.08558

Die alle behandeln Intervall Arithemtik. Das meinte ich eigentlich nicht. Ehr sowas wie Qt hier:

QMediaTimeRange QMediaTimeInterval

Ein geschlossenes / halboffenes Intervall. Für Zeiten oder Daten. Obe und Untergrenze. Vergleiche ob ein Wert im Interval liegt. Das langt doch schon.

DataInterval

-Wshadow is not that bad. We live in a modern world and don't use C if we can use C++ with a better defined scope and namespaces. So we can catch more errors on compile time.

First: what kind or errors can be detected with -Werror=shadow

Warn whenever a local variable or type declaration shadows another variable, parameter, type, class member, or whenever a built-in function is shadowed.

struct A {
    int i;              // note: shadowed declaration is here

    void func(int i) {} // error: declaration of 'i' shadows a member of 'A' [-Werror=shadow]
};

This kind or error also occurs if you define a constructor like following code. It defines a type Axis which has a title and a range. The range must be valid. The constructor of the Axis does something. So aggregate initialization is not possible.

struct Axis {
    string title;
    Range range;

    Axis(string title, Range range) 
    : title(title), range(range)       // error: declaration of 'range' shadows a member of 'Axis'
                                       // error: declaration of 'title' shadows a member of 'Axis'
    {
        // check if range is valid, error otherwise
    }
};

You can, of course, rename the constructor arguments or member variables. But that is not nice and results in either ugly code or a less proper interface.

The right solution is to split your type into two. One which only store data and another which does something with that data. Let's call the data-type AxisData. Try again:

struct Axis {
    struct AxisData {
        string title;
        Range range;
    };

    AxisData d;

    Axis(string title, Range range) 
    : d{title, range}
    {
        // check if range.isValid()
    }
};

No more errors! The extra variable d is no overhead, as you can see in my previous post.
To hide this implementation details from the programmer, provide some access function and switch from struct to class because Axis is now a type which manage it's data.

So this is the (final, add some references) implementation:

class Axis {
    struct AxisData {
        string title;
        Range range;
    };

    AxisData d;

public:

    Axis(string title, Range range) 
    : d{title, range}
    {
        // check if range.isValid()
    }

    string title() const {
        return d.title;
    }

    Range range() const {
        return d.range;
    }
};

The following code snips does NOT create a level of indirection. You can see it by introspect the assembler code.
So don't worry, start structure your data. See the next post for a practice example.

Example 1

Lets begin with a simple struct contains 3 members: double, float, int. Sum them up. And see what the compile generate

struct A {
    double d;
    float f;
    int i;
};

static_assert(sizeof(A) == 16);

auto func(const A& a){
    return a.d + a.f + a.i;
}

With the static assert sizeof you can be sure there is no padding in the data structure. The generate ASM code compiled with GCC 8.1 -O1 I comment it to make it easier for you.

func(A const&):
        pxor    %xmm0, %xmm0              # xmm0 = 0
        cvtss2sd        8(%rdi), %xmm0    # convert float to double and store it in xmm0
        addsd   (%rdi), %xmm0             # add double and the converted float to xmm0
        pxor    %xmm1, %xmm1              # xmm1 = 0
        cvtsi2sd        12(%rdi), %xmm1   # convert integer to double and store it in xmm1
        addsd   %xmm1, %xmm0              # add the already added float+double to the converted integer to xmm0
        ret                               # return xmm0 as result

You can see two conversions from int/float to double and two additions. You can also see the offsets. The double value has offset 0, the float value 8 bytes and the integer value (8+4)=12 bytes. This is quite straight. So add more code.

Example 2

This example create a nested struct Bdata inside struct B. Sum the values up again and see what the compiler generate.

struct B {
    struct Bdata {
        double d;
        float f;
        int i;
    };

    Bdata b;
};

static_assert(sizeof(B) == 16);

auto func2(const B& a){
    return a.b.d + a.b.f + a.b.i;
}

It is exactly, 100%, the same assembler code as example1 ! So i don't show it here again. The memory layout of struct B is the same as struct A, so the same ASM code is generated. No overhead by the extra variable b.

Example 3

In the next example a std::tuple is used to store the 3 values. The access is provided with the function std::get. It looks different. But wait...

struct C {
    std::tuple<double, float, int> c;
};

static_assert(sizeof(C) == 16);

auto func3(const C& a){
    return std::get<0>(a.c) + std::get<1>(a.c) + std::get<2>(a.c);
}

This time, the generated code is different

func3(C const&):
        pxor    %xmm0, %xmm0             # xmm0 = 0
        cvtss2sd        4(%rdi), %xmm0   # convert float to double and store it in xmm0
        addsd   8(%rdi), %xmm0           # add double and the converted float to xmm0
        pxor    %xmm1, %xmm1             # xmm1 = 0
        cvtsi2sd        (%rdi), %xmm1    # convert integer to double and store it in xmm1
        addsd   %xmm1, %xmm0             # add the already added float+double to the converted integer to xmm0
        ret                              # return xmm0 as result

But if you take a closer look, it is still the same! Only the memory layout has changed. First the integer, then the float, then the double. A std::stuple store it's values in reverse order! But the generated assembler code is 100% identical to the first example!

Example 4

In the last example I change the structure a little bit. But you can guess, the result is still the same.

struct D {
    double d;

    struct Ddata {    
        float f;
        int i;
    };

    Ddata x;
};

static_assert(sizeof(D) == 16);

auto func4(const D& a){
    return a.d + a.x.f + a.x.i;
}

See the next post for a practice example.

Update zu Passing random generators around (functor) In jenen Beispiel habe ich den RNG per std::function übergeben. Das muss nicht sein. Mit std::function verliert man die inline Performance. Und es geht auch ohne seltsames std::bind.

Aktualisierter Code:

#include <random>
#include <iostream>
#include <functional>
#include <omp.h>

// can be passed by value. it has no state
template<typename Function>
int function2(Function dice) {
  int sum = 0;
  for(int i=0; i < 1000; i++) {
    sum += dice();
  }
  return sum;
}

// pass by reference, it has state
int function(std::minstd_rand& generator) {
  // we need random numbers from 0 to 10
  std::uniform_int_distribution<int> distribution(0,10);
  // lambda instead of bind
  auto dice = [&](){ return distribution(generator); };

  return function2(dice);
}

int main() {
  omp_set_num_threads(2);

  // create  random generatores with random seed
  std::minstd_rand seedGen;
  std::minstd_rand generators[omp_get_num_threads()];
  for(int i=0; i < omp_get_num_threads(); i++) {
    generators[i].seed(seedGen());
  }

#pragma omp parallel for
  for(int i=0; i < 8; i++) {
    const int id = omp_get_thread_num();
    // pass one generator to our function
    int sum = function(generators[id]);

    std::cout << "Thread " << id << " sum " << sum << "\n";
  }

  std::cout << "Info sizeof std::function<int()> " << sizeof(std::function<int()>) << "\n";

  return 0;
}

I say: Pass (template) function objects per Forwarding references! and not per value. The reason is simple: it works also with function objects with state.

https://en.cppreference.com/w/cpp/language/reference

A little example will show it:

#include <iostream>
#include <random>
using namespace std;

template<typename Function>
auto perValue(Function f) {
  return f();
}

template<typename Function>
auto perForwardReference(Function&& f) {
  return f();
}

int main() {
  std::minstd_rand gen(1156823295);
  
  cout << "Generate 5 random numbers:\n";
  cout << "calls to perValue:\n";
  for(int i=0; i < 5; i++) {
    cout << perValue(gen) << "\n";
  }
  
  cout << "calls to perForwardReference:\n";
  for(int i=0; i < 5; i++) {
    cout << perForwardReference(gen) << "\n";
  }  
}

Generate 5 random numbers:
calls to perValue:
4
4
4
4
4
calls to perForwardReference:
4
193084
730423176
870612250
1216431607

It doesn’t work because the random number generate object has a state. The call to function perValue() change this state on a copy of the generator. And not the one, we pass as argument. But there is no compile time error. Not a single warning. That's the worst case IMO.

The C++ standard and Scott Meyers book "Effective STL" recommend to pass by value. IMO for historical reasons.

C++11 §25.1/10:
[ Note: Unless otherwise specified, algorithms that take function objects as arguments are permitted to copy those function objects freely. Programmers for whom object identity is important should consider using a wrapper class that points to a noncopied implementation object such as reference_wrapper (20.8.3), or some equivalent solution. —end note ]

stackoverflow: why function objects should be pass-by-value

The standard should be updated and the book is horrible outdated. It was written 2008 and forward references come with C++2011. The old solution is to wrap the function into something which can be pass by value, but also change the state. We have now (2011) std::function for that task. And not this ugly thing in the book.

Schonmal probiert den ein und selben template Datentypen mit sich selbst zu nutzen? Mach nichts, ich auch nicht ;)

Als erstes Beispiel ein einfacher, nicht rekursiver Datentyp:

template<typename T>
struct Test {	
	T x;
};

auto func() {
   Test{0};
}

error: class template argument deduction failed:
    Test{0};
error: no matching function for call to 'Test(int)'
note: candidate: 'template<class T> Test(Test<T>)-> Test<T>'

Seit C++17 gibt es Class template argument deduction. Allerdings muss man für User-defined typen auch User-defined deduction guides angeben. Dieser hier ist sehr simpel.

template<typename T>
Test(T) -> Test<T>;

Damit compiliert das oben gezeigte Beispiel (ab GCC7).
Und nun zu dem rekursiven Typen. Ob es geklappt hat, lässt sich mit einem static_assert mit std::is_same zeigen.

template<typename T>
auto func2(T) {	
    static_assert(std::is_same_v<T, Test<Test<int>> >);
}

auto func() {
  func2( Test{Test{0}} ); // Dies ruft den Copy-Konstruktor auf
}

In instantiation of 'auto func2(T) [with T = Test<int>]':
error: static assertion failed

Nein es hat nicht geklappt. Der Grund hierfür ist, dass wir ja eigentlich den Copy-Konstruktor aufgerufen haben.

Mit den deduction guides können wir aber dem Compiler bessere Anweisungen geben.

template<typename T>
Test(Test<T>) -> Test<Test<T>>;

Damit compiliert der Code nun.

Vielen Dank an Freundlich aus dem #c++ Chat für die Fragestellung ;)

See

https://stackoverflow.com/questions/13532784/why-can-i-use-auto-on-a-private-type
https://stackoverflow.com/questions/31185119/preventing-return-of-private-inner-class-instance

struct A {
private:
    struct inner {
    };

public:
  inner func() { }
  void func2(inner) {}
};

auto func() {
    A a;    
    auto x = a.func();
    decltype(x) y;
    a.func2(y);

    A::inner z; // Not ok
}

Auf den ersten Blick etwas überraschend, aber wenn man bedenkt, dass die Zugriffsregeln nur für Namen gelten, ist alles wieder konsistent. Den Namen einer Privaten Klasse darf nicht genutzt werden, aber der Typ schon. Daher funktioniert hier auto, da kein Name explizit hingeschrieben werden muss.

Selbe Argumentation gibt auch für Templates oder temporäre Objekte. Da auch hier das Symbol inner nicht außerhalb der Klasse A auftaucht.

A a;
a.func2(a.func());

Betrachte ein unstruturiertes Gitternetz bestehend aus Punkte und Dreiecken. Jeder Punkt kann durchnummeriert werden. Für jeden Punkt IP bezeichnet die Variable NCONN die Anzahl der angeschlossenen Punkte pro Punkt. Und die Variable NCONE bezeichnet die angeschlossene Dreiecke pro Punkt.
Es ist leicht zu sehen, dass Punkte am Rand eine unterschiedliche Anzahl von angeschlossenen Punkte und Dreiecke haben. Wärend Punkte im Mesh gleich viele angeschlossene Punkte und Dreiecke haben.

Folgender C++ könnte grob so ein Gitternetz beschreiben:

#include <vector>

struct Mesh {
  std::vector<int> NCONN, NCONE;

  void update_NCONN_NCONE() {
     // Genaue Impl. nicht relevant für das Rätsel
  }

  bool istRandpunkt(int IP) const {
    return NCONN[IP] != NCONE[IP];
  }
}

Vor der ersten Benutzung der Funktion isRandpunkt müssen die Variablen NCONN und NCONE gefüllt werden. Dies übernimmt die Funktion update_NCONN_NCONE. Die genaue Implementierung dieser Funktion ist für das Rätsel nicht relevant, und wird daher nicht angegeben.

Nun muss der Programmierer darauf achten, dass diese Funktion auch immer aufgerufen wird. Programmierer sind aber auch nur Menschen und machen Fehler. Sollte der Aufruf von update_NCONN_NCONE einmal vergessen werden, stürzt das Programm im besten Fall ab. Im schlechtesten Fall werden falsche Ergebnisse produziert.

Wie kann dem Programmierer geholfen werden?
Es muss auf eine Art sichergestellt werden, dass die Variablen NCONN und NCONE immer mit den aktuellen Daten gefüllt sind. Allerdings darf die Funktion update_NCONN_NCONE nicht unnötig oft aufgerufen werden, da sie unter Umständen eine lange Laufzeit zur Folge hat.

Beachtet auch, dass dieser Code zur Laufzeit in ein Programm geladen werden könnte (Library/Plugin).

Es gibt für jedes Problem viele Lösungen und auch wenige gute.

Beispiel
In der Funktion istRandpunkt bei jedem Aufruf zu testen, ob die Funktion update_NCONN_NCONE aufgerufen werden muss würde zwar sicherstellen, dass die Variablen immer aktuell sind. Allerdings ist das so keine gute Idee, da dies die Laufzeit negativ beeinflusst.

struct Mesh {
  mutable std::vector<int> NCONN, NCONE;
  mutable bool needUpdate = true;

  void update_NCONN_NCONE() {
     if(not needUpdate) return;
     needUpdate = false;
     // Genaue Impl. nicht relevant für das Rätsel
  }

  bool istRandpunkt(int IP) const {
    update_NCONN_NCONE();
    return NCONN[IP] != NCONE[IP];
  }
}

In der Implementierung zeigen sich noch weitere Hässlichkeiten. Die Funktion istRandpunkt sollte als const attributiert sein, da sie keine Daten ändert. Allerdings widerspricht das der Idee, die Variablen on-the-fly zu aktualisieren. Daher müssen sie als mutable deklariert werden.
Damit werden aber Dinge im Hintergrund getriggert, welcher der Programmierer nicht erwartet. Die Funktion istRandpunkt sagt vom Funktionsnamen nicht aus, dass noch ein Update passiert.

Lösung 1: Tags
Die Idee ist, dass die Funktion istRandPunkt nur dann aufgerufen/compiliert werden kann, wenn als Argument irgendetwas mitgegeben werden kann, was vorher nur von der Funktion update_NCONN_NCONE erstellt wurde. Beispielsweise mittels einer Tag Variable. Diese kann nur von update_NCONN_NCONE erstellt werden.

struct Mesh {
    private:
    struct Tag { };

public:
  std::vector<int> NCONN, NCONE;

  Tag update_NCONN_NCONE() {
     // Genaue Impl. nicht relevant für das Rätsel
     return Tag();
  }

  bool istRandpunkt(int IP, Tag) const {
    return NCONN[IP] != NCONE[IP];
  }
};

auto func() {
    Mesh mesh;    
    auto tag = mesh.update_NCONN_NCONE();
    return mesh.istRandpunkt(1, tag);
}

Der Nachteil ist schnell erkannt. Sobald mehr als ein Mesh existiert, kann die tag Variable mehrfach genutzt werden. Es existiert keine Bindung zu einer speziellen Instanz eines Mesh Types.

Lösung 1: Enums