Forum: PC-Programmierung c++: Lookup-Table Inhalt zur Compilezeit erstellen


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Matho (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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:
1
template<uint8_t Size> class foo{
2
    int table[Size];
3
4
    foo(void){ for(int i = 0; i<Size;++i) table[i] = fkt(i, Size); }
5
};

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

von Dr. Sommer (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Matho (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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
1
array[i] = fkt(i,Size); //Size:Template-Parameter, i:Index
initialisiert..!?

von Dr. Sommer (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Dr. Sommer (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Torsten R. (Firma: Torrox.de) (torstenrobitzki)


Bewertung
0 lesenswert
nicht lesenswert
Folgendes funktioniert bereits mit C++11:
1
#include <iostream>
2
#include <iterator>
3
#include <algorithm>
4
#include <tuple>
5
#include <type_traits>
6
7
template < typename T >
8
struct fkt {
9
  static constexpr int result = T::value * 2;
10
};
11
12
template < typename >
13
struct table;
14
15
template < typename ... Ts >
16
struct table< std::tuple< Ts... > >
17
{
18
  static const int content[ sizeof ...(Ts) ];
19
};
20
21
template < typename ... Ts >
22
const int table< std::tuple< Ts... > >::content[ sizeof ...(Ts) ] = {
23
  fkt< Ts >::result...
24
};
25
26
template < int I >
27
using int_c = std::integral_constant< int, I >;
28
using input = std::tuple< int_c< 0 >, int_c< 1 >, int_c< 2 > >;
29
30
int main()
31
{
32
    auto const& result = table< input >::content;
33
    std::copy(
34
        std::begin( result ), std::end( result ),
35
        std::ostream_iterator< int >( std::cout, "\n" ) );
36
}

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

: Bearbeitet durch User
von Dr. Sommer (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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

von Torsten R. (Firma: Torrox.de) (torstenrobitzki)


Bewertung
0 lesenswert
nicht lesenswert
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:
1
template < int I, typename L = std::tuple<> >
2
struct index_up_to;
3
4
template < typename ... Ts >
5
struct index_up_to< -1, std::tuple< Ts... > > {
6
  using index = std::tuple< Ts... >;
7
};
8
9
template < int I, typename ... Ts >
10
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.
1
template < typename, template< typename > class F >
2
struct table;
3
4
template < typename ... Ts, template< typename > class F >
5
struct table< std::tuple< Ts... >, F >
6
{
7
  static const int content[ sizeof ...(Ts) ];
8
};
9
10
template < typename ... Ts, template< typename > class F >
11
const int table< std::tuple< Ts... >, F >::content[ sizeof ...(Ts) ] = {
12
  F< Ts >::result...
13
};

Und zu guter Letzt:
1
int main()
2
{
3
    auto const& result = table< index_up_to< 3 >::index, fkt >::content;
4
    std::copy(
5
        std::begin( result ), std::end( result ),
6
        std::ostream_iterator< int >( std::cout, "\n" ) );
7
}

von Dr. Sommer (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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...

von Torsten R. (Firma: Torrox.de) (torstenrobitzki)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Dr. Sommer (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Wilhelm M. (wimalopaan)


Bewertung
0 lesenswert
nicht lesenswert
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:
>
1
> template<uint8_t Size> class foo{
2
>     int table[Size];
3
> 
4
>     foo(void){ for(int i = 0; i<Size;++i) table[i] = fkt(i, Size); }
5
> };
6
>

Wenn fkt(...) constexpr ist, kannst Du es auch mit eine IIFE aka 
constexpr-lambda machen:
1
constexpr int fkt(size_t value) {
2
    return value;
3
}
4
constexpr size_t Size = 16;
5
constexpr auto test = [&]{
6
    std::array<int, Size> a;
7
    for(size_t i = 0; i < Size; ++i) {
8
        a[i] = fkt(i);
9
    }
10
    return a;
11
};

von M.K. B. (mkbit)


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

von Oliver S. (oliverso)


Bewertung
0 lesenswert
nicht lesenswert
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

: Bearbeitet durch User
von Nop (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Dr. Sommer (Gast)


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

Haha! Weil
1
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.:
1
constexpr int corrFac = 42;
2
constexpr int offset = 7;
3
constexpr int calibrate (int x) { return x*corrFac + offset; }
4
constexpr auto myLUT = generate<10> ([&] (auto i) { return calibrate (i) ^ 0xF00; });
5
6
void calc (int i, int j) {
7
  myLUT [i] + (corrFac * j) ^ offset;
8
}
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.

von Nop (Gast)


Bewertung
-1 lesenswert
nicht lesenswert
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.

von Dr. Sommer (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Jan (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Dr. Sommer (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Jan schrieb:
> Wie debuggt man solchen Template code?

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

von Wilhelm M. (wimalopaan)


Bewertung
1 lesenswert
nicht lesenswert
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:
1
#include <cstdint>
2
#include <cstddef>
3
#include <array>
4
#include <iostream>
5
6
constexpr int fkt(size_t value) {
7
    return 2 * value;
8
}
9
constexpr size_t Size = 16;
10
constexpr auto test = []{
11
    std::array<int, Size> a{};
12
    for(size_t i = 0; i < Size; ++i) {
13
        a[i] = fkt(i);
14
    }
15
    return a;
16
}();
17
18
int main() {
19
    for(const auto& v : test) {
20
        std::cout << v << '\n';
21
    }
22
}

von Oliver S. (oliverso)


Bewertung
0 lesenswert
nicht lesenswert
Mal eben klammheimlich hier und da ein paar fehlende Klammern 
hinzugefügt ;)

Oliver

von Wilhelm M. (wimalopaan)


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

Ja, war ja alles ungetestet ...

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.