3. LUT zu Compilezeit generieren lassen

LUT zu Compilezeit generieren lassen

  • ?

    Ich brauche eine Look-Up-Table, deren Größe von eine Compilezeit-Konstanten abhängig ist. Die einzelnen Elemente kann ich mit einem TMP-Konstrukt generieren. Wie bekomme ich das Ganze jedoch zusammen? Kann ich irgendwie ein Array zur Compilezeit mit den TMP-Generierten Werten füllen lassen?

    MfG

    0
  • Mod

    Kann ich irgendwie ein Array zur Compilezeit mit den TMP-Generierten Werten füllen lassen?

    Definitiv. Zeig einfach mal dein Konstrukt zur Generierung. Ist es rekursiv? Oder mit einem Index? Beides gut machbar.

    Edit: Welchen Sprachstandard verwendest du? C++11 waere gut.

    0
  • N

    Ja, z.B. so.

    0
  • Mod

    Nexus schrieb:

    Ja, z.B. so.

    Da passiert ueberhaupt nichts zur Compilezeit, oder? Ich dachte, er will ein constexpr -Array?

    0
  • ?

    Hi Arcoth. Der Generator selbst errechnet sich die Werte rekursiv, jedoch sind die einzelnen LUT-Werte voneinander unabhängig generierbar (also mit Index). Das soll in C++03 laufen. Mein Code:

    template<std::size_t base, std::size_t exp>
struct tmp_pow
{
	static const std::size_t value = base * tmp_pow<base, exp - 1>::value;
};
template<std::size_t base>
struct tmp_pow<base, 0>
{
	static const std::size_t value = 1;
};

template<unsigned char val>
struct gen
{
	static const std::size_t value = (val & 1) + gen<(val >> 1)>::value;
};
template<>
struct gen<0>
{
	static const std::size_t value = 0;
};

std::size_t f(unsigned char val)
{
	static const std::size_t lut[tmp_pow<2, std::numeric_limits<unsigned char>::digits>::value] = ?;
	return lut[val];
}

    Hier soll nun lut[0] = gen<0>::value , lut[1] = gen<1>::value , etc. sein. Wenn ich ein static const -Array habe und es mit Compilezeit-Konstanten fülle, dann dürfte der Compiler das direkt so in den Programmspeicher kopieren, oder?

    0
  • Mod 

    tmp_pow<2, std::numeric_limits<unsigned char>::digits>::value>

    Nein, nein, nein!

    1 << CHAR_BIT // Edit: Lieber CHAR_BIT

    (Warum nicht einfach gleich 256 ...)

    So, und dein Problem laesst sich relativ einfach loesen; und zwar mittels binaer rekursiver Makros.

    Mit Boost.Preprocessor wird es einfacher und schoener (hast du Zugang dazu?), aber probier erstmal sowas:

    #define OP ( v ) (v & 1) + gen<(val >> 1)>::value
#define OP2( v ) OP(v), OP(v+1)
#define OP4( v ) OP2(v), OP2(v+2)
#define OP8( v ) OP4(v), OP4(v+4)
#define OP16( v ) OP8(v), OP8(v+8)
#define OP32( v ) OP16(v), OP16(v+16)
#define OP64( v ) OP32(v), OP32(v+32)
#define OP128( v ) OP64(v), OP64(v+64)
#define OP256( v ) OP128(v), OP128(v+128)

static const std::size_t lut[] = { OP256(0) };

    Ich bin gerade in der Schule und kann dir daher leider nicht zu viel testen. 😞

    0
  • ?

    Ja schon, ich hätte auch ein Programm schreiben können dass mir den Code für die 256 Werte generiert. Ich frage jedoch ob das portabel geht da ja nicht jede Maschine 8 Bits pro Byte hat (daher auch die Limits statt 256). Geht das?

    0
  • C
    Mod

    Variadic Templates helfen hier. Die mAn wichtigste Einsicht hierbei ist, dass sich praktisch alle anfallenden Probleme leicht lösen lassen, sofern man sie in Abhängigkeit einer Sequenz 0,1,2,...,N mit beliebigem N formulieren kann. Diese Sequenz kann leicht als Templateargumentliste erzeugt werden (in C++1y schon fertig als std::integer_sequence und std::make_integer_sequence in <utility>)

    template <typename T, T... I>
struct integer_sequence {
    using value_type = T;
    static constexpr std::size_t size() noexcept { return sizeof...(I); }
};

template <typename T, T N, T... I>
struct make_integer_sequence_impl : make_integer_sequence_impl<T, N-1, 0, 1+I...> {};

template <typename T, T... I>
struct make_integer_sequence_impl<T, 0, I...>
{
    using type = integer_sequence<T, I...>;
};

template<class T, T N>
using make_integer_sequence = typename make_integer_sequence_impl<T, N>::type;

///////////////////////////////////////////
...

template <std::size_t... I>
std::size_t f(unsigned char val, std::integer_sequence<std::size_t, I...>)
{
    static const std::size_t lut[] = { gen<I>::value... };
    return lut[val];
}

std::size_t f(unsigned char val)
{
    return f(val, make_integer_sequence<std::size_t, tmp_pow<2, std::numeric_limits<unsigned char>::digits>::value>{});
}

    (ungetestet, wahrscheinlich Schreibfehler drin).

    0
  • Mod

    Geht das?

    Warum nicht einfach die ersten 2048 Werte mit obiger Methode generieren und dann nur die ersten paar nutzen die du brauchst?

    0
  • Mod

    Variadic Templates helfen hier.

    Und sind voellig fehl am Platz. Der TE braucht C++03.

    0
  • ?

    Arcoth schrieb:

    Geht das?

    Warum nicht einfach die ersten 2048 Werte mit obiger Methode generieren und dann nur die ersten paar nutzen die du brauchst?

    Das ist doch immer noch nicht portabel. Was wenn die Maschine 16-Bit-Bytes hat? Es wäre mir ab liebsten, wenn der Code komplett unabhängig von der Plattform ist.

    0
  • C
    Mod

    LUTher schrieb:

    Arcoth schrieb:

    Geht das?

    Warum nicht einfach die ersten 2048 Werte mit obiger Methode generieren und dann nur die ersten paar nutzen die du brauchst?

    Das ist doch immer noch nicht portabel. Was wenn die Maschine 16-Bit-Bytes hat? Es wäre mir ab liebsten, wenn der Code komplett unabhängig von der Plattform ist.

    Das wird nichts mit C++03, sofern der Code auch noch einigermaßen standardkonform sein soll (man könnte theoretisch mit boost::tuple oder std::tr1::tuple etwas nicht ganz Konformes bauen - allerings mit nicht vertretbarer Performance). Für so etwas sind dann eben Codegeneratoren zuständig.

    0
  • Mod

    Das wird nichts mit C++03, sofern der Code auch noch einigermaßen standardkonform sein soll (man könnte theoretisch mit boost::tuple oder std::tr1::tuple etwas nicht ganz Konformes bauen - allerings mit nicht vertretbarer Performance). Für so etwas sind dann eben Codegeneratoren zuständig.

    👍
    MPL versagt auch, oder? 🙂

    Ich schlage dann vor

    #define OP( v ) gen<v>::value
#define OP2( v ) OP(v), OP(v+1)
#define OP4( v ) OP2(v), OP2(v+2)
#define OP8( v ) OP4(v), OP4(v+4)
#define OP16( v ) OP8(v), OP8(v+8)
#define OP32( v ) OP16(v), OP16(v+16)
#define OP64( v ) OP32(v), OP32(v+32)
#define OP128( v ) OP64(v), OP64(v+64)
#define OP256( v ) OP128(v), OP128(v+128)
#define OP512( v ) OP256(v), OP256(v+256)
#define OP1024( v ) OP512(v), OP512(v+512)
#define OP2048( v ) OP1024(v), OP1024(v+1024)
#define OP4096( v ) OP2048(v), OP2048(v+2048)
#define OP8192( v ) OP4096(v), OP4096(v+4096)
#define OP16384( v ) OP8192(v), OP8192(v+8192)
#define OP32768( v ) OP16384(v), OP16384(v+16384)
#define OP65536( v ) OP32768(v), OP32768(v+32768)

#define CONCAT_(a, b) a##b
#define CONCAT(a, b) CONCAT_(a, b)

#define POW28 256
#define POW29 512
#define POW210 1024
#define POW211 2048
#define POW212 4096
#define POW213 8192
#define POW214 16384
#define POW215 32768
#define POW216 65536

#include <climits>
#include <cstddef>

template<unsigned char val>
struct gen
{
	static const std::size_t value = (val & 1) + gen<(val >> 1)>::value;
};
template<>
struct gen<0>
{
	static const std::size_t value = 0;
};

static const std::size_t lut[] = { CONCAT(OP, CONCAT(POW2, CHAR_BIT))(0) }; // Concat mit CHAR_MAX klappt nicht, da Hexadezimal

    P.S.: Vielleicht kannste statt dem Initializer im Primärtemplate von gen einfach __builtin_popcount verwenden? Ist eine intrinsic und dürfte deutlich schneller kompilieren.

    0
  • ?

    Welche CPU/Maschine der letzten 30 Jahre hatte keine 8bit Bytes?

    Egal welchen Code ich hier im Thread betrachte. Keiner davon ist auch nur im Ansatz so wartbar wie eine zur Laufzeit mit einer einfachen Schleife erstellte Tabelle.

    Und wenn der Code so portabel sein soll, dass er mal auf einer Maschine vernuenftig laeuft deren Byte nicht aus 8 bits besteht ist eine Laufzeittabelle ohnehin besser.

    0
  • Mod

    Welche CPU/Maschine der letzten 30 Jahre hatte keine 8bit Bytes?

    C54x DSPs. Gibt auch noch ältere Maschinen mit 9-Bit char s die IIRC momentan im Betrieb sind. Google hilft!

    Egal welchen Code ich hier im Thread betrachte. Keiner davon ist auch nur im Ansatz so wartbar wie eine zur Laufzeit mit einer einfachen Schleife erstellte Tabelle.

    Der Code den camper gezeigt hat ist definitiv wartbar*.
    Nur vielleicht ein wenig komplizierter zu verstehen, aber sobald man mit variadic templates vertraut ist, sollte das verständlich werden.

    * und dank linearer Rekursion ineffizient, genau wie die meisten stdlib-Implementierungen, u.a. beim GCC. Hat nämlich superlineare Lauf(Compilier)zeitkomplexität.

    0
  • C
    Mod

    Arcoth schrieb:

    Der Code den camper gezeigt hat ist definitiv wartbar*.
    Nur vielleicht ein wenig komplizierter zu verstehen, aber sobald man mit variadic templates vertraut ist, sollte das verständlich werden.

    * und dank linearer Rekursion ineffizient, genau wie die meisten stdlib-Implementierungen, u.a. beim GCC. Hat nämlich superlineare Lauf(Compilier)zeitkomplexität.

    Wahrscheinlich ist er sogar falsch, partielle Spezialisierung auf einen T-Parameter, dessen Typ selbst deduziert werden muss, geht ja nicht. Die simple Variante habe ich hier für dem Verständnis förderlich gehalten. Für eine std-Implementierung erwarte ich etwas bessers.

    korrigiert könnte es z.B. so aussehen

    template <typename T> struct identity { using type = T; };

template <typename T, T N, T... I>
struct make_integer_sequence_impl
    : std::conditional<N==0, identity<integer_sequence<T, I...>>, make_integer_sequence_impl<T, N-1, 0, 1+I...>>::type
{};
    0
  • Mod

    Ich nehme auch mein Kommentar bezüglich camper zurück, denn hier ist noch die C++1y-Lösung mit VTMPL:

    #include "VTMPL/algorithms.hxx"

// So ähnlich kann man auch das Klassentemplate von LUTher definieren - per Makros spezialisieren
constexpr unsigned char popcnt( unsigned char val )
{
#if defined __GNUG__ || defined __clang__
	return __builtin_popcountll(val);
#else // defined
	unsigned char count = 0;
	while( val )
	{
		count += val & 1;
		val >>= 1;
	}

	return count;
#endif
}

#include <climits>

using type = vtmpl::generate< UCHAR_MAX+1, vtmpl::functions::from_function_ptr<unsigned char, popcnt> >;
// Zugriff auf das Array mit type::array

    @camper: Der Code ist falsch weil

    §14.5.5/8 schrieb:

    The type of a template parameter corresponding to a specialized non-type argument shall not be dependent on a parameter of the specialization.

    Und das trifft auf

    template <typename T, T... I>
struct make_integer_sequence_impl<T, 0, I...>
                                     ^

    Zu.

    0
  • Mod

    Für eine std-Implementierung erwarte ich etwas bessers.

    Vom GCC 4.10-Snapshot, <utility>

    template<size_t... _Indexes>
    struct _Index_tuple
    {
      typedef _Index_tuple<_Indexes..., sizeof...(_Indexes)> __next;
    };

  // Builds an _Index_tuple<0, 1, 2, ..., _Num-1>.
  template<size_t _Num>
    struct _Build_index_tuple
    {
      typedef typename _Build_index_tuple<_Num - 1>::__type::__next __type;
    };

  template<>
    struct _Build_index_tuple<0>
    {
      typedef _Index_tuple<> __type;
    };

// [...]

  template<typename _Tp, _Tp _Num,
	   typename _ISeq = typename _Build_index_tuple<_Num>::__type>
    struct _Make_integer_sequence;

  template<typename _Tp, _Tp _Num,  size_t... _Idx>
    struct _Make_integer_sequence<_Tp, _Num, _Index_tuple<_Idx...>>
    {
      static_assert( _Num >= 0,
		     "Cannot make integer sequence of negative length" );

      typedef integer_sequence<_Tp, static_cast<_Tp>(_Idx)...> __type;
    };
    0

  • @LUTher
    Du willst definitiv keinen 64K grossen Lookup-Table. Weil dir der die Performance ruiniert.
    Also entweder gleich die von Arcoth vorgeschlagene Intrinsic-Version, oder - wie auch schon vorgeschlagen wurde - einen Table mit 256 Werten und dann ggf. je nach char-Breite zwei oder mehr Lookups machen und zusammenaddieren.

    size_t my_popcnt(unsigned char ch)
{
    return lut[ch & 0xFF]
#if CHAR_BIT > 8
         + lut[(ch >> 8) & 0xFF]
#if CHAR_BIT > 16
         + lut[(ch >> 16) & 0xFF]
#if CHAR_BIT > 24
         + lut[(ch >> 24) & 0xFF]
#if CHAR_BIT > 32
#error F*ck this shit!
#endif
#endif
#endif
#endif
    ;
}
    0
Anmelden zum Antworten