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

[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.

[decimad]

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.

[decimad]

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

[decimad]

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.

[decimad]

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?

[decimad]

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.

[decimad]

Also ich benutze den Trick ein paar mal in meinem aktuellen Projekt und hatte mir das asm aus anderen Gründen angeschaut, dabei sind mir dort keine diesbezüglichen Ungewöhnlichkeiten aufgefallen, aka keine unnötigen zuweisungen oder stack-allozierungen. Viel mehr hatte ich das Problem, dass Tag-Argumente nicht komplett wegradiert wurden (was wohl nur einen Einfluss auf den Stackverbrauch hat, weil ansonsten nix getan wurde mit den unnötigen Funktionsargumenten). Was wieder zu hässlichen template-Strukturen führte. Würg.

[Columbo]

knivil schrieb:

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

Ich nehme einen grünen Tee.
Folögender Code: http://codepad.org/PaPFzQlR
GCC-Explorer:

__cxx_global_var_init:                  # @__cxx_global_var_init
	pushq	%rbp
	movq	%rsp, %rbp
	subq	$16, %rsp
	leaq	std::__ioinit, %rdi
	callq	std::ios_base::Init::Init()
	leaq	std::ios_base::Init::~Init(), %rdi
	leaq	std::__ioinit, %rsi
	leaq	__dso_handle, %rdx
	callq	__cxa_atexit
	movl	%eax, -4(%rbp)          # 4-byte Spill
	addq	$16, %rsp
	popq	%rbp
	ret

foo(unsigned int):                                # @foo(unsigned int)
	pushq	%rbp
	movq	%rsp, %rbp
	subq	$16, %rsp
	leaq	std::cout, %rax
	movl	%edi, -4(%rbp)
	movl	-4(%rbp), %esi
	movq	%rax, %rdi
	callq	std::basic_ostream<char, std::char_traits<char> >::operator<<(unsigned int)
	movq	%rax, -16(%rbp)         # 8-byte Spill
	addq	$16, %rsp
	popq	%rbp
	ret

main:                                   # @main
	pushq	%rbp
	movq	%rsp, %rbp
	callq	_ZN6repeatIXadL_Z3foojEELj7E10index_listIJLj0ELj1ELj2ELj3ELj4ELj5ELj6EEEE3runEv
	movl	$0, %eax
	popq	%rbp
	ret

_ZN6repeatIXadL_Z3foojEELj7E10index_listIJLj0ELj1ELj2ELj3ELj4ELj5ELj6EEEE3runEv: # @_ZN6repeatIXadL_Z3foojEELj7E10index_listIJLj0ELj1ELj2ELj3ELj4ELj5ELj6EEEE3runEv
	pushq	%rbp
	movq	%rsp, %rbp
	subq	$16, %rsp
	movl	$0, %edi
	callq	foo(unsigned int)
	movl	$1, %edi
	movb	$0, -7(%rbp)
	callq	foo(unsigned int)
	movl	$2, %edi
	movb	$0, -6(%rbp)
	callq	foo(unsigned int)
	movl	$3, %edi
	movb	$0, -5(%rbp)
	callq	foo(unsigned int)
	movl	$4, %edi
	movb	$0, -4(%rbp)
	callq	foo(unsigned int)
	movl	$5, %edi
	movb	$0, -3(%rbp)
	callq	foo(unsigned int)
	movl	$6, %edi
	movb	$0, -2(%rbp)
	callq	foo(unsigned int)
	movb	$0, -1(%rbp)
	addq	$16, %rsp
	popq	%rbp
	ret

global constructors keyed to a:                           # @global constructors keyed to a
	pushq	%rbp
	movq	%rsp, %rbp
	callq	__cxx_global_var_init
	popq	%rbp
	ret

Ein Array sehe ich nirgends. Und das ohne Optimierungs-Flags. Mit Optimierungs-Flags gibt mir der Explorer aber kein ASM.

Edit: Den GCC-Explorer Link habe ich entfernt, den will sowieso niemand sehen.

[Ethon]

Mit -O3 wird daraus bei clang

int main()
{
    std::cout << 0 << 1 << 2 << 3 << 4 << 5 << 6;
}

[decimad]

Hier meine D-Version des ganzen:

module main;

import std.stdio;
import std.algorithm;
import std.conv;

string GenerateCompareAndSwap(string array, int index0, int index1)
{
	string ind0 = to!string(index0);
	string ind1 = to!string(index1);

	return "if("~array~"["~ind0~"]>"~array~"["~ind1~"]) swap("~array~"["~ind0~"], "~array~"["~ind1~"]);\n";
}

string GenerateMerge( string x, int lo, int hi, int r )
{
	int step = r * 2;
	if (step < hi - lo) {
		string result = GenerateMerge(x, lo, hi, step) ~ GenerateMerge(x, lo + r, hi, step);

		for( int i = lo + r; i < hi-r; i+= step ) {
			result = result ~ GenerateCompareAndSwap(x, i, i + r) ~ GenerateCompareAndSwap(x, lo, lo + r);
		}

		return result;
	} else {
		return GenerateCompareAndSwap(x, lo, lo + r);
	}
}

string GenerateOddEvenImpl( string x, int lo, int hi )
{
	if ( hi - lo >= 1) {
		int mid = lo + (hi - lo)/2;
		return GenerateOddEvenImpl(x, lo, mid) ~ GenerateOddEvenImpl(x, mid + 1, hi) ~ GenerateMerge(x, lo, hi, 1);
	} else return "";
}

string GenerateOddEven( string x, int arraysize ) {
	if( arraysize == 0 ) {
		return "";
	} else {
		return GenerateOddEvenImpl( x, 0, arraysize-1 );
	}
};

int main(string[] argv)
{
	int[16] myarray = [3,4,5,1,74,2,78,43,6,21,74,53,2,5,2,1];

	mixin(GenerateOddEven("myarray", myarray.length));

	for(int i=0; i< myarray.length; ++i ) {
		writeln( myarray[i] );
	}

	return 0;
}

[volkard]

decimad schrieb:

Hier meine D-Version des ganzen:

module main;

import std.stdio;
import std.algorithm;
import std.conv;

string GenerateCompareAndSwap(string array, int index0, int index1)
{
	string ind0 = to!string(index0);
	string ind1 = to!string(index1);

	return "if("~array~"["~ind0~"]>"~array~"["~ind1~"]) swap("~array~"["~ind0~"], "~array~"["~ind1~"]);\n";
}

string GenerateMerge( string x, int lo, int hi, int r )
{
	int step = r * 2;
	if (step < hi - lo) {
		string result = GenerateMerge(x, lo, hi, step) ~ GenerateMerge(x, lo + r, hi, step);
		
		for( int i = lo + r; i < hi-r; i+= step ) {
			result = result ~ GenerateCompareAndSwap(x, i, i + r) ~ GenerateCompareAndSwap(x, lo, lo + r);
		}

		return result;
	} else {
		return GenerateCompareAndSwap(x, lo, lo + r);
	}
}

string GenerateOddEvenImpl( string x, int lo, int hi )
{
	if ( hi - lo >= 1) {
		int mid = lo + (hi - lo)/2;
		return GenerateOddEvenImpl(x, lo, mid) ~ GenerateOddEvenImpl(x, mid + 1, hi) ~ GenerateMerge(x, lo, hi, 1);
	} else return "";
}

string GenerateOddEven( string x, int arraysize ) {
	if( arraysize == 0 ) {
		return "";
	} else {
		return GenerateOddEvenImpl( x, 0, arraysize-1 );
	}
};

int main(string[] argv)
{
	int[16] myarray = [3,4,5,1,74,2,78,43,6,21,74,53,2,5,2,1];

	mixin(GenerateOddEven("myarray", myarray.length));

	for(int i=0; i< myarray.length; ++i ) {
		writeln( myarray[i] );
	}

	return 0;
}

Bitte Ausgabe reinfummeln, in welcher Reihenfolge verglichen wird. Und die Ausgabe zeigen.
1-2 3-4 5-6 7-8
1-3 2-4 4-6 5-7
1-2 5-6
1-4 2-5 3-6 4-7
2-4 3-5
1-2 3-4 5-6
Zum Beispiel. Das wäre nett.

Aber
0-1 2-3 4-5 6-7
0-2 1-3
1-2 4-6 5-7
5-6 0-4
2-6
2-4
1-5 3-7
3-5
1-2 3-4 5-6
wäre nicht so toll.

[decimad]

Okay, kleinen Moment!
Ich muss mich hier gerade erstmal reinfrickeln, das war mein allererstes D-Programm, das wird bestimmt auch schöner gehen alles.

[decimad]

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

1
2
3
4
5
43
74
78