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

knivil

decimad schrieb:

Übersehe ich gerade einen offensichtlichen Grund, aus dem das nicht schon gehen würde?

Es geht bestimmt, aber darum geht es nicht. Es geht darum, das mittels C++ Templates generisch fuer alle (naja, prinzipiell) Arraygroessen (Potenzen von 2) zu realisieren ... uebersichtlich.

Ach um Übersichtlichkeit geht's. Ja naja, wenn ein Compiler einfach den Quellcode für Compile-Zeit-Konstanten durchlaufen würde und sich dann nur noch diejenigen Anweisungen merkt, die von Runtime-Größen abhängen, dann könnte er praktisch den Algorithmus von Quelltextform in einen riesigen Code-Blob übersetzen, stimmt. Hat die Sache einen Haken?

Natürlich müsste man ihn per Attribut im Voraus davon überzeugen, dass der Algorithmus anhand der gegebenen Compile-Zeit-Größen terminiert. Ansonsten hätten einige Benutzer wohl zu klagen

knivil

Mach 's doch einfach anstatt mich mit allgemeinen Bemerkungen zu belehren ... Ich gebe mich auch mit einer unuebersichtlichen Loesung zufrieden. http://en.wikipedia.org/wiki/Bitonic_sorter

Columbo

knivil schrieb:

Mach 's doch einfach anstatt mich mit allgemeinen Bemerkungen zu belehren ... Ich gebe mich auch mit einer unuebersichtlichen Loesung zufrieden. http://en.wikipedia.org/wiki/Bitonic_sorter

Danke (für den Link). Jetzt geht es einfacher. (Habe schon angefangen)

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.