c++: Lookup-Table Inhalt zur Compilezeit erstellen

[Matho (Gast)]

Hallo,
nur eine kurze Frage:
Was ist die schönste Methode, eine lookup-Table zur Compilezeit zu 
füllen?
Googelt man danach, findet man seltsame Lösungen, ja älter der 
C++-Standard ist (c++03, c++11, c++14, c++17). Mit 'schön' meine ich, so 
einfach/übersichtlich und so alt wie möglich. Dazu fehl mir der 
Überblick.

Hier mal eine (Pseudo-)Code Beispiel:

template<uint8_t Size> class foo{
    int table[Size];

    foo(void){ for(int i = 0; i<Size;++i) table[i] = fkt(i, Size); }
};

Kann mir jemand sagen, wie es richtig geht und ob sich zB. c++17 lohnt?
Danke schon mal
Matho

[Dr. Sommer (Gast)]

std::make_index_sequence nutzen, an eine Funktion übergeben und dort 
Spezialisierung nutzen um ein Parameter Pack "size_t... I" zu erhalten. 
Dieses kann man dann nutzen um ein std::array zu befüllen und zurück zu 
geben.

[Matho (Gast)]

Wow, danke. Das ging aber schnell!
Über sowas ähnliches bin ich auch beim googeln gestolpert (glaube ich).
Weißt du zufällig, welchem c++-Standard das entspricht, und ob das auch 
für µCs gilt?
Ich fürche, das funktioniert nur mit std::array ?!

Hier der "Spezialfall", nur der Vollständigkeit halber:
Beitrag "gcc/c++: Compilezeit-Array für progmem erstellen lassen"


Wie hätte man das denn bei c++03 (vor c++11) gemacht? Ich frage mich 
schon lange, wie man konstante Arrays nach der Art

array[i] = fkt(i,Size); //Size:Template-Parameter, i:Index

initialisiert..!?

[Dr. Sommer (Gast)]

Matho schrieb:
> Weißt du zufällig, welchem c++-Standard das entspricht, und ob das auch
> für µCs gilt?

C++14. Man kann sich std::(make_)index_sequence aber auch problemlos in 
C++11 selber bauen.

Das klappt problemlos auch für µC, habe ich schon gemacht. Lediglich der 
AVR-GCC liefert die Standard-Bibliothek nicht mit, weshalb man da viel 
selbst coden muss.

Matho schrieb:
> Ich fürche, das funktioniert nur mit std::array ?!
So direkt ja. Es ginge auch mit normalen Arrays, aber die können dann 
nicht in beliebige Scopes gepackt werden. Aber wo ist das Problem bei 
std::array? Das kann man falls nötig auch simpel nachbauen.

Matho schrieb:
> Wie hätte man das denn bei c++03 (vor c++11) gemacht?
Mit Code-Generatoren...

Matho schrieb:
> Ich frage mich
> schon lange, wie man konstante Arrays nach der Art
Genau wie oben beschrieben.

[Dr. Sommer (Gast)]

Hier ein Beispiel: https://ideone.com/G3KuxT

Über die "generate"-Funktion kann man sich beliebige Arrays als 
constexpr berechnen lassen. Man gibt die Berechnungsfunktion als eigene 
Funktion an. Ab C++17 gehen auch Lambdas. Die myLUT-Variable wird vom 
Compiler berechnet und in den Flash gepackt. Prinzipiell ist das 
Compiler-Unabhängig und portabel; mit dem ARM-GCC funktioniert es. Für 
den AVR muss man sich die Standard Library etwas nachbauen.

[Torsten R. (Firma: Torrox.de) (torstenrobitzki)]

Folgendes funktioniert bereits mit C++11:

#include <iostream>
#include <iterator>
#include <algorithm>
#include <tuple>
#include <type_traits>

template < typename T >
struct fkt {
  static constexpr int result = T::value * 2;
};

template < typename >
struct table;

template < typename ... Ts >
struct table< std::tuple< Ts... > >
{
  static const int content[ sizeof ...(Ts) ];
};

template < typename ... Ts >
const int table< std::tuple< Ts... > >::content[ sizeof ...(Ts) ] = {
  fkt< Ts >::result...
};

template < int I >
using int_c = std::integral_constant< int, I >;
using input = std::tuple< int_c< 0 >, int_c< 1 >, int_c< 2 > >;

int main()
{
    auto const& result = table< input >::content;
    std::copy(
        std::begin( result ), std::end( result ),
        std::ostream_iterator< int >( std::cout, "\n" ) );
}

Ausgang ist dabei eine Typliste, mit Werten, die die Ausgangsbasis für 
Deine Tabellen-Werte bilden. Wenn das blos ein Index ist, kannst Du Dir 
dafür dann natürlich eine Meta-Funktion schreiben, die diese Index-Liste 
bildet.

mfg Torsten

[Dr. Sommer (Gast)]

Torsten R. schrieb:
> Folgendes funktioniert bereits mit C++11:

Das Wichtigste fehlt aber, nämlich die Berechnung der Sequenz 0, 1, 2... 
Und "table" ist leider fix auf "f" hartkodiert.

Mithilfe dieses Codes
https://stackoverflow.com/a/17426611
kann man sich index_sequence und make_index_sequence selbst 
implementieren und in mein o.g. Beispiel einbauen sodass es auch mit 
C++11 geht:
https://ideone.com/YBsyWI

[Torsten R. (Firma: Torrox.de) (torstenrobitzki)]

Dr. Sommer schrieb:
> Torsten R. schrieb:
>> Folgendes funktioniert bereits mit C++11:
>
> Das Wichtigste fehlt aber, nämlich die Berechnung der Sequenz 0, 1, 2...

Naja, das hätte ich jetzt einfach als "Fleißarbeit" gesehen. Dies hier 
ist meine Lösung:

template < int I, typename L = std::tuple<> >
struct index_up_to;

template < typename ... Ts >
struct index_up_to< -1, std::tuple< Ts... > > {
  using index = std::tuple< Ts... >;
};

template < int I, typename ... Ts >
struct index_up_to< I, std::tuple< Ts... > > : index_up_to< I - 1, std::tuple< int_c< I >, Ts... > > {};

> Und "table" ist leider fix auf "f" hartkodiert.

Es war halt ein Beispiel. Wenn der OP das nicht um fkt alleine erweitert 
bekommt, dann kann er mit der von mir gezeigten Lösung wahrscheinlich 
auch nichts anfangen.

template < typename, template< typename > class F >
struct table;

template < typename ... Ts, template< typename > class F >
struct table< std::tuple< Ts... >, F >
{
  static const int content[ sizeof ...(Ts) ];
};

template < typename ... Ts, template< typename > class F >
const int table< std::tuple< Ts... >, F >::content[ sizeof ...(Ts) ] = {
  F< Ts >::result...
};

Und zu guter Letzt:

int main()
{
    auto const& result = table< index_up_to< 3 >::index, fkt >::content;
    std::copy(
        std::begin( result ), std::end( result ),
        std::ostream_iterator< int >( std::cout, "\n" ) );
}

[Dr. Sommer (Gast)]

Torsten R. schrieb:
> Dies hier
> ist meine Lösung:

Die aber leider lineare Compilier-Zeit fordert - die gängige Lösung nur 
logarithmische.

Hier eine "Universal"-Version: https://ideone.com/woWjAl

Diese funktioniert mit C++11, 14 und 17. Es werden die 
Standard-Bibliothek-Mechanismen verwendet falls vorhanden und ansonsten 
selbst implementiert. Dadurch funktioniert es auch mit dem AVR-GCC. Ist 
natürlich ziemlich hässlich in "namespace std" etwas hineinzupacken aber 
so ist das halt beim AVR...

[Torsten R. (Firma: Torrox.de) (torstenrobitzki)]

Dr. Sommer schrieb:
> Torsten R. schrieb:
>> Dies hier
>> ist meine Lösung:
>
> Die aber leider lineare Compilier-Zeit fordert - die gängige Lösung nur
> logarithmische.

Ich würde erst einmal mit der einfachen Lösung anfangen. Wenn O(N) bei 
der Erzeugung des Index ein Problem ist, aber nicht bei der Berechnen 
der Tabellen-Inhalte (die zwangsläufig in O(N) zu passieren hat), dann 
würde ich die Lösung noch mal überdenken.

[Dr. Sommer (Gast)]

Torsten R. schrieb:
> Wenn O(N) bei
> der Erzeugung des Index ein Problem ist, aber nicht bei der Berechnen
> der Tabellen-Inhalte (die zwangsläufig in O(N) zu passieren hat), dann
> würde ich die Lösung noch mal überdenken.

Das passiert aber durchaus. Die Tabelleninhalte zu berechnen ist einfach 
- nur ein Funktionsaufruf. Dein "index_up_to" hingegen ist eine 
rekursive template-Instanziierung, die braucht ziemlich lange zum 
kompilieren.

Ein "typename index_up_to<500>::index x;" braucht bei mir 8 Sekunden, 
ein "std::make_index_sequence<500> x;" nur 0,05. Ein "typename 
index_up_to<1000>::index x;" kompiliert gar nicht erst. 
make_index_sequence braucht selbst für 1 Mio nur 3 Sek.

[Wilhelm M. (wimalopaan)]

Matho schrieb:
> Hallo,
> nur eine kurze Frage:
> Was ist die schönste Methode, eine lookup-Table zur Compilezeit zu
> füllen?
> Googelt man danach, findet man seltsame Lösungen, ja älter der
> C++-Standard ist (c++03, c++11, c++14, c++17). Mit 'schön' meine ich, so
> einfach/übersichtlich und so alt wie möglich. Dazu fehl mir der
> Überblick.
>
> Hier mal eine (Pseudo-)Code Beispiel:
>

> template<uint8_t Size> class foo{
>     int table[Size];
> 
>     foo(void){ for(int i = 0; i<Size;++i) table[i] = fkt(i, Size); }
> };
>

Wenn fkt(...) constexpr ist, kannst Du es auch mit eine IIFE aka 
constexpr-lambda machen:

constexpr int fkt(size_t value) {
    return value;
}
constexpr size_t Size = 16;
constexpr auto test = [&]{
    std::array<int, Size> a;
    for(size_t i = 0; i < Size; ++i) {
        a[i] = fkt(i);
    }
    return a;
};

[M.K. B. (mkbit)]

Ab C++17 mit einem constexpr if.
https://en.cppreference.com/w/cpp/language/if

[Oliver S. (oliverso)]

Wilhelm M. schrieb:
> Wenn fkt(...) constexpr ist, kannst Du es auch mit eine IIFE aka
> constexpr-lambda machen:
>
> constexpr int fkt(size_t value) {
>     return value;
> }
> constexpr size_t Size = 16;
> constexpr auto test = [&]{
>     std::array<int, Size> a;
>     for(size_t i = 0; i < Size; ++i) {
>         a[i] = fkt(i);
>     }
>     return a;
> };

Kannst du das mal in einem complierbaren Progrämmchen zeigen?

Oliver

[Nop (Gast)]

Dann gibt's natürlich auch noch die altbewährte Methode, in einer 
beliebigen Sprache einfach ein C++-File zu erzeugen. Kann man sogar in 
Python machen. Wenn man das im Makefile mit entsprechenden 
Abhängigkeiten versieht, wird das eh nur aufgerufen, wenn das zugehörige 
Parameterfile sich geändert hat, welches dann in einem Domain-angepaßten 
Format ist, bis hin zu einer eigenen DSL (domain specific language).

Hauptnachteil ist dabei natürlich die leichtere Verständlichkeit und 
dadurch höhere Wartbarkeit.

[Dr. Sommer (Gast)]

Nop schrieb:
> Hauptnachteil ist dabei natürlich die leichtere Verständlichkeit und
> dadurch höhere Wartbarkeit.

Haha! Weil

constexpr auto myLUT = generate<10> ([&] (auto i) { return 2*i; });

so unglaublich schwer verständlich ist (ab C++17)?

Der Vorteil bei der C++-Variante (mit constexpr/Metaprogrammierungs) 
ist, dass sie sich besser in den Quelltext integriert. Solche 1-Zeiler 
kann ich in beliebiger Menge an beliebige Stellen in den Sourcecode 
packen. Der Compiler sorgt dafür dass das klappt. Bei Code-Generierung 
muss ich selbst dafür sorgen dass die generierten Tabellen an der 
richtigen Stelle landen.
Die C++-Variante kann zudem beliebige eigene constexpr-Funktionen oder 
Konstanten referenzieren, die ich dann auch anderweitig im Code benutzen 
kann. Bei generiertem Code muss ich aufpassen dass Generator und 
normaler Code die selben Funktionen/Konstanten verwenden.
z.B.:

constexpr int corrFac = 42;
constexpr int offset = 7;
constexpr int calibrate (int x) { return x*corrFac + offset; }
constexpr auto myLUT = generate<10> ([&] (auto i) { return calibrate (i) ^ 0xF00; });

void calc (int i, int j) {
  myLUT [i] + (corrFac * j) ^ offset;
}

corrFac, offset, calibrate kann ich trivial sowohl im normalen Code 
("calc") als auch in der LUT anwenden. Beim Generator braucht es wie du 
sagst Parameter-Files und DSLs und auch noch Parser dafür; die 
C++-Variante benutzt einfach den Parser im Compiler. Alles was zusammen 
gehört steht nebeneinander; das finde ich sehr gut wartbar. Ich kann 
sogar die Daten einer LUT in eine andere LUT einfließen lassen.

Bei der C++-Variante kann ich die LUT als Teil eines anderen templates 
generieren und template-Parameter mit einfließen lassen; das geht mit 
Generator überhaupt nicht.

[Nop (Gast)]

Dr. Sommer schrieb:

> Solche 1-Zeiler
> kann ich in beliebiger Menge an beliebige Stellen in den Sourcecode
> packen. Der Compiler sorgt dafür dass das klappt.

Naja für solche Trivialfälle würde man auch wohl kaum eine DSL nehmen, 
ne?

> Bei der C++-Variante kann ich die LUT als Teil eines anderen templates
> generieren und template-Parameter mit einfließen lassen

Exzessive Template-Metaprogrammierung ist schonmal ein guter Ansatz für 
write-only Wegwerfcode. Bei größeren Projekten gewinnt man außerdem auch 
noch die gigantischen Compile-Zeiten, für die C++ berüchtigt ist.

[Dr. Sommer (Gast)]

Nop schrieb:
> Naja für solche Trivialfälle würde man auch wohl kaum eine DSL nehmen,
> ne?

Logischerweise baut man sich da die gewünschte Nicht-Triviale Formel 
ein.

Nop schrieb:
> Exzessive Template-Metaprogrammierung

8 Zeilen (s.o.) würde ich nicht als exzessiv bezeichnen. Einen 
Code-Generator mit Parsen von Parameter-Files und DSLs kriegst du nicht 
kompakter hin.

Lieber lange Compile-Zeit als lange Frickel-Zeit. Aber wie gesagt (s.o.) 
geht mein Ansatz bei 1 Mio Elementen in wenigen Sekunden. Das sollte 
reichen.

[Jan (Gast)]

Wie debuggt man solchen Template code? Beim Generator kann ich ihn sehen 
und ggf sogar durchsteppen, bei Templates nicht oder?
Finde das ganze sehr interessant.

[Dr. Sommer (Gast)]

Jan schrieb:
> Wie debuggt man solchen Template code?

Compiler-Fehlermeldungen anschauen, die constexpr-Funktionen normal zur 
Laufzeit aufrufen und durchsteppen, static_assert ...

[Wilhelm M. (wimalopaan)]

Oliver S. schrieb:
> Wilhelm M. schrieb:
>> Wenn fkt(...) constexpr ist, kannst Du es auch mit eine IIFE aka
>> constexpr-lambda machen:
>>
>> constexpr int fkt(size_t value) {
>>     return value;
>> }
>> constexpr size_t Size = 16;
>> constexpr auto test = [&]{
>>     std::array<int, Size> a;
>>     for(size_t i = 0; i < Size; ++i) {
>>         a[i] = fkt(i);
>>     }
>>     return a;
>> };
>
> Kannst du das mal in einem complierbaren Progrämmchen zeigen?
>
> Oliver

Voila:

#include <cstdint>
#include <cstddef>
#include <array>
#include <iostream>

constexpr int fkt(size_t value) {
    return 2 * value;
}
constexpr size_t Size = 16;
constexpr auto test = []{
    std::array<int, Size> a{};
    for(size_t i = 0; i < Size; ++i) {
        a[i] = fkt(i);
    }
    return a;
}();

int main() {
    for(const auto& v : test) {
        std::cout << v << '\n';
    }
}

[Oliver S. (oliverso)]

Mal eben klammheimlich hier und da ein paar fehlende Klammern 
hinzugefügt ;)

Oliver

[Wilhelm M. (wimalopaan)]

Oliver S. schrieb:
> Mal eben klammheimlich hier und da ein paar fehlende Klammern
> hinzugefügt ;)

Ja, war ja alles ungetestet ...