Gebt doch endlich mal richtige Gründe gegen die Sprache D an!

Ich werd' einen Teufel tun und einen Compiler programmieren, der das könnte! Der schickt dir dann zwar den Code-Blob raus, wenn überhaupt, aber dieser Blob shuffelt dann statt zu sortieren, und das langsamer als Bubblesort ein Array sortieren würde, das nach jeder Iteration wieder geshuffelt wird.
Was willst Du denn von mir? Du sagtest sowas sollte möglich sein, ich drückte die Meinung aus, dass es schon möglich sei. Dann sagtest Du übersichtlich, also deutete ich, dass es Dir eher um die "Abstrakte" Möglichkeit geht, extrem expandiertet Code-Blobs zu erzeugen. Und nun soll ich Dir eigentlich das Template schreiben? Häh?

knivil

Ich werd' einen Teufel tun und einen Compiler programmieren, der das könnte!

Es geht nicht um einen neuen Compiler, Templates in C++ sind ausreichend, der Compiler ist schon da.

Was willst du von mir? Du hast dich doch hingestellt und meintest, dass sei moeglich. Tja, nur hat es noch nie jemand gemacht, in C++, in D in

Oder um deine Worte zu benutzen: Was wird wohl der ofizielle Grund sein? Merkste was?

Ich mein, das ist doch keine Kunst? Statt der Berechnungen der Indizes in den Variablen des gegebenen Pseudo-Codes, rechnest Du das halt direkt aus den Template-Parametern aus und statt einer Schleife generierst Du eine Variadic-Index-Liste und expandierst diese in entsprechend viele Calls auf die Zielfunktion. Dann noch das Array überall als Referenz durchflutschen und eine Spezialisierung als Rekursionsende, die eben das Compare-Swap durchführt. Und hinterher hoffen, dass der Compiler das alles in die Top-Level-Funktion inlined.

knivil schrieb:

Wenn man Metaprogrammierung in anderen Sprachen anschaut, dann sind Templates in C++ totale Steinzeit. Leider kenne ich mich mit D nicht aus, aber ich sach mal: Templates in D sind auch totale Steinzeit.

Templates in C++ sind Steinzeit im Vergleich zu D.

Aktuell sind es String Mixins, also die Möglichkeit, jeden "constexpr"-String in den Quellcode einzufügen. Und constexpr ist per default alles. AST Macros sind leider erst geplant.

knivil

Ich mein, das ist doch keine Kunst? ...

Und noch mehr allgemeine Belehrungen. Ich Weiss welche Schritte notwendig sind, machen werde ich es trotzdem nicht. Warum wohl ...

Templates in C++ sind Steinzeit im Vergleich zu D.

Und D im Vergleich zu Scheme, wo alles quasi AST ist?

knivil schrieb:

Und D im Vergleich zu Scheme, wo alles quasi AST ist?

Nicht ganz ebenbürtig, aber gleich mächtig.

Na, dass der Template-Code dafür nicht schön wird, damit rennst Du bei mir doch offene Türen ein. Ich sagte doch selber ein paar Posts davor, dass ich das allmählich zum Kotzen finde. Wo ich früher in C für jeden Typ wieder ne Linked-List geschrieben habe, schreibe ich inzwischen für jeden TMP-Algorithmus eine Template-Forward-Deklaration und X Spezialisierungen. Aber wenn man darüber jetzt noch versucht eine weitere Template-Abstraktionsschicht zu pflanzen setzt allmählich mein Gehirn aus.
Dein ursprünglicher Post klang nunmal aber so, als wärst Du der Meinung, es ginge gar nicht erst - obwohl es jetzt soooo aufwändig jetzt ja auch nicht ist, weil der Algorithmus recht handlich ist. Und Deine Antwort auf meine Antwort konnte ich dann nur noch so deuten, dass Du eine Lösung für das Problem suchst, das darin besteht, dass Template-Code für solcherlei Probleme viel zu kompliziert ist. Meine Antwort war darauf: Versichere dem Compiler, dass es terminiert, dann könnte der hypothetische Compiler das eigentlich, ohne dass man noch ein Deut an dem Code verändern müsste, der auch zur Laufzeit das gleiche tun würde. Fragt sich halt, wie oft man soetwas braucht. Aber so müsste man keine neue Template-Magie erfinden.

knivil

Ich sagte doch selber ein paar Posts davor

Ich habe deine Aussagen nicht angezweifelt. Ich habe einen Wunsch geaussert. Er war nicht direkt an dich gerichtet. Und ich will keinen hypothetischen Kompiler, da es im Prinzip das gleiche ist, wenn der Kompiler einfach toll optimieren koennte, was er nicht kann. Ich will einen "einfachen" Codegenerator.

Na da wollen wir doch dasselbe.
Aber woher soll ich diese Aussage aus

Mein Wunsch ist ja immer noch ein durch Templates generiertes Sortiernetzwerk a la

herauslesen und was gibt Dir dann noch den Anlass, auf meine freundlich in Frage gestellte Antwort darauf, dass es doch ginge, mit verbalen Angriffen zu antworten?
Ich schrieb NICHT: "Du bist dumm, das geht doch!"

Im übrigen eignen sich die Mixins von D hervorragend für sowas, wenn ich das richtig sehe (aber natürlich nicht ganz so hervorragend wie es der hypothetische Compiler könnte). Und natürlich könnte ein hervorragend optimierender Compiler das Problem NICHT allgemein lösen, denn er kann zwar aggressiv zu werke gehen, aber kann doch nur unter Umständen beweisen, dass das, was er da gerade tut überhaupt terminiert, ansonsten MUSS er doch irgendwann einen Schlussstrich setzen. Oder sehe ich da gerade etwas falsch?

knivil

mit verbalen Angriffen zu antworten?

Echt hart, ich finde sie nicht. Bestimmt habe ich sie herauseditiert.

überhaupt terminiert

Ich verrate es dir: terminiert, da ein Sortiernetzwerk von 8 aus zwei der Groesse 4 + Merger rekursiv aufgebaut werden kann. Und genau das kann als Template/Metaprogramm ausgedrueckt werden. Hat nur noch keener gemacht.

Na klar, hier könnte der Compiler einen Divide&Conquer-Algorithmus erkennen. Drum schrieb ich ja im "allgemeinen", weil es für mich keinen Sinn ergab, in diesen hypothetischen Compiler nur eine Spezialoptimierungsroutine für Odd-Even-Mergesort zu integrieren. Wobei ich jetzt einsehe, dass es da natürlich echt viele D&Cs gibt, die Verwendungen finden, also könnte es sich dennoch lohnen.
Aber anderersesits - tun die Compiler das nicht sowieso schon, bis sie der Meinung sind, dass weiterer "Bloat" des Codes im Verhältnis zur Datenmenge, die davon verarbeitet wird, nicht mehr sinnvoll ist? Ist der Code für 128 oder 256 Elemente "gebloatet" wirklich noch schneller als der normale Runtime-Code? Diese Frage zu beantworten motiviert mich jetzt dazu, dieses Template jetzt wirklich einmal zu schreiben

Na wenn nicht "verbale Angriffe" dann doch wenigstens ziemlich pampig. Jetzt hat sich mein Wortschatz für derlei Verhalten erschöpft, außerdem muss ich ein template schreiben!

knivil

decimad schrieb:

Ist der Code für 128 oder 256 Elemente "gebloatet" wirklich noch schneller als der normale Runtime-Code?

Das kommt auf die Hardware an. Es gibt Prozessoren mit 256 Registern, die a la VLIW bspw. 10 Befehle gleichzeitig abarbeiten und einen SWAPIF-Befehl kennen.

Diese Frage zu beantworten motiviert mich jetzt dazu, dieses Template jetzt wirklich einmal zu schreiben

Fuehl dich nicht gezwungen.

Na wenn nicht "verbale Angriffe" dann doch wenigstens ziemlich pampig.

Was immer dir beliebt.

Columbo

ch verrate es dir: terminiert, da ein Sortiernetzwerk von 8 aus zwei der Groesse 4 + Merger rekursiv aufgebaut werden kann. Und genau das kann als Template/Metaprogramm ausgedrueckt werden. Hat nur noch keener gemacht.

Ich verstehe immer noch nicht ganz, aber hier ist ein Anfang für die ersten Swaps:

using size_type = unsigned;
using index_type = unsigned;

template<typename T>
using eval = typename T::type;

template<index_type ... args>
struct index_list
{
	using type = index_list;
	static constexpr size_type length = sizeof...(args);
	static constexpr index_type array[]{args...};
};

template<index_type ... args>
constexpr index_type index_list<args...>::array[];

template <typename, typename> struct multiply;
template <index_type... indices, index_type... tail>
struct multiply<index_list<indices...>,
                index_list<tail...   >> : index_list<indices..., (sizeof...(indices)+indices)...,
                                                                 (2*sizeof...(indices)+indices)...,
                                                                 (3*sizeof...(indices)+indices)...,
                                                                 (4*sizeof...(indices)+tail)...> {};
template <index_type N>
struct make_index_list :
	multiply< eval<make_index_list<N/4>>,
	          eval<make_index_list<N%4>> > {};

template <> struct make_index_list<3> : index_list<0, 1, 2> {};
template <> struct make_index_list<2> : index_list<0, 1> {};
template <> struct make_index_list<1> : index_list<0> {};
template <> struct make_index_list<0> : index_list<> {};

template <typename T,
          template<index_type> class,
          typename = eval<make_index_list<T::length>>> struct transform;

template <index_type... indices,
          template<index_type> class function,
          index_type... enums>
struct transform<index_list<indices...>, function, index_list<enums...>> :
	index_list< function<index_list<indices...>::array[enums]>::value... > {};

#include <type_traits>
namespace functions
{
	template<index_type a>
	struct multiply
	{
		template<index_type b>
		struct function : std::integral_constant<index_type, a*b> {};
	};
}

#include <iostream>

void CMP_SWAP(int* a, int i, int j)
{
	std::cout << '(' << i << ',' << j << "), ";
	if (a[i] > a[j])
		std::swap(a[i], a[j]);
}

template< index_type first,
          index_type diff,
          index_type... indices >
void compute_impl( int* a, index_list<indices...> )
{
	bool _[]{ (CMP_SWAP(a, first + indices, first + indices + diff), false)... };
}

template< index_type first,
          index_type stride,
          index_type pair_diff,
          index_type amount >
void compute( int* a )
{
	using list = eval<make_index_list<amount>>;
	using multiplied = eval<transform<list, functions::multiply<stride>::template function>>;
	return compute_impl<first, pair_diff>(a, multiplied{});
}

template< index_type len >
void sort_network( int *a )
{
	compute<0, 2, 1, len/2>(a); std::cout<< '\n';
	compute<0, 1, 2, len/2-2>(a);
	compute<len/2, 1, 2, len/2-2>(a);
}

#include <iterator>
#include <algorithm>

int main()
{
	using namespace std;

	int a[]{ 8, 7, 6, 5, 4, 3, 2, 1 };
	sort_network<8>(a);
	copy( begin(a), end(a), ostream_iterator<int>(cout << '\n', ", ") );
}

Die Ausgabe ist zum Test.

Edit: Hier der Output:

(0,1), (2,3), (4,5), (6,7), 
(0,2), (1,3), (4,6), (5,7), 
5, 6, 7, 8, 1, 2, 3, 4,

knivil

Ich habe mir noch nicht ganz die Muehe gemacht, es zu verstehen, aber es sollte Code generiert werden ... hier wird ein lokales Array angelegt, leider kann ich nicht darauf vertrauen, dass der Compiler es wegoptimiert ... oder doch?

void compute_impl( int* a, index_list<indices...> ) 
{ 
     bool _[]{ (CMP_SWAP(a, first + indices, first + indices + diff), false)... }; 
}

Meine Umsetzungsvorstellung ist dahingehend, dass ich ein Sortiernetzwerke bspw. fuer 8 auf zwei fuer 4 und Merger zurueckfuehre. D.h. es ist eigentlich nicht noetig, Templates mit variablen Argumenten zu benutzen.

Columbo

Natürlich optimiert er das weg - es wird doch nicht verwendet.

Du kannst es auch sonst ganz explizit machen

(void)std::initializer_list<bool>{ (CMP_SWAP(a, first + indices, first + indices + diff), false)... };

So wird die initializer_list definitiv nicht angelegt, es ist eine discarded-value expression.

Columbo

Meine Umsetzungsvorstellung ist dahingehend, dass ich ein Sortiernetzwerke bspw. fuer 8 auf zwei fuer 4 und Merger zurueckfuehre. D.h. es ist eigentlich nicht noetig, Templates mit variablen Argumenten zu benutzen.

Das heißt, zuerst beide sortieren und dann mergen? Und das ganze rekursiv?

Am Besten, zeige mal ein Beispiel, wie du dir das ganze vorstellst. Also was für einen Code du hinschreibst, und welche Effekte dieser haben soll.

Dann bräuchtest Du doch aber ein allgemeines "Merge"-Netzwerk? Das für sich selbst ist doch schon wieder ein kompliziertes Problem, für das man sich ein Netzwerk ersinnen müsste. Es sei denn, es geht Dir nur darum einen Basisblock, der gut auf die Hardware mapped umzusetzen und damit dann einen allgemeinen Mergesort aufzubauen.
Das Array ist nur ein Trick, um mehrere Calls zu erzeugen, weil Variadic-Packs nur in einem Kontext ausgepackt werden können, der eine Komma-Separierte Liste erlaubt... Da die Funktionscalls, die beim Auspacken entstehen aber nichts zurückgeben, steht da prinzipiell nur bool _[] = { false }, was wohl jeder Compiler wegzaubern kann. Eine der vielen Schwächen von Variadics btw...

Sone: sind Compiler schneller in der Erzeugung der Index-Listen, wenn man diese Instanzieruntstiefe/4-Taktik anwendet? Oder geht's nur darum, 4 mal größere Indexlisten erzeugen zu können, bevor der Compiler die Rekursiongrätsche macht?

Erm, um die log4(N) herum meine ich wohl...

knivil

Es gibt viele Wege, leider habt ihr es geschafft. Jetzt befasse ich mich ernsthaft damit. Dauert aber eine Weile.

So wird die initializer_list definitiv nicht angelegt, es ist eine discarded-value expression.

Abwarten, Tee trinken. Mal schauen, wie der Asm-Code ausschaut.