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

[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

[decimad]

Wenn das nicht die Reihenfolge ist, die Du möchtest, dann müssen wir einen anderen Algorithmus wählen

[decimad]

Okay, das war ja auch total dumm von mir, ich kann ja auch gleich den Code hier reinposten, den D generiert

if(arr[0]>arr[1]) swap(arr[0], arr[1]);
if(arr[2]>arr[3]) swap(arr[2], arr[3]);
if(arr[0]>arr[2]) swap(arr[0], arr[2]);
if(arr[1]>arr[3]) swap(arr[1], arr[3]);
if(arr[1]>arr[2]) swap(arr[1], arr[2]);
if(arr[0]>arr[1]) swap(arr[0], arr[1]);
if(arr[4]>arr[5]) swap(arr[4], arr[5]);
if(arr[6]>arr[7]) swap(arr[6], arr[7]);
if(arr[4]>arr[6]) swap(arr[4], arr[6]);
if(arr[5]>arr[7]) swap(arr[5], arr[7]);
if(arr[5]>arr[6]) swap(arr[5], arr[6]);
if(arr[4]>arr[5]) swap(arr[4], arr[5]);
if(arr[0]>arr[4]) swap(arr[0], arr[4]);
if(arr[2]>arr[6]) swap(arr[2], arr[6]);
if(arr[2]>arr[4]) swap(arr[2], arr[4]);
if(arr[0]>arr[2]) swap(arr[0], arr[2]);
if(arr[1]>arr[5]) swap(arr[1], arr[5]);
if(arr[3]>arr[7]) swap(arr[3], arr[7]);
if(arr[3]>arr[5]) swap(arr[3], arr[5]);
if(arr[1]>arr[3]) swap(arr[1], arr[3]);
if(arr[1]>arr[2]) swap(arr[1], arr[2]);
if(arr[0]>arr[1]) swap(arr[0], arr[1]);
if(arr[3]>arr[4]) swap(arr[3], arr[4]);
if(arr[0]>arr[1]) swap(arr[0], arr[1]);
if(arr[5]>arr[6]) swap(arr[5], arr[6]);
if(arr[0]>arr[1]) swap(arr[0], arr[1]);

[Ethon]

Super in D.
Auch ne Demonstration welchen Vorteil es bietet anstatt std::string/vector builtin Typen zu haben.

[decimad]

Und total automatisches constexpr vor allem, ich hab ja nix sagen müssen. Das kommt meinem "hypothetischen" Compiler schon recht nahe, außer dass man halt selber die "variablen" strings zusammensetzen muss.
Ich bin mega begeistert von den paar Sachen, die ich hier nebenbei so in der Doku überflogen habe, während ich mir das nötige anlas für das Problem hier.

[Kellerautomat]

Gibts fuer D ueberhaupt ne brauchbare IDE? Das Eclipse Plugin scheint mit aktuellen Versionen nicht zu funktionieren, bei "D-IDE" (offenbar eine schlechte Kopie von MSVC, und das ist schon mies) konnte ich nicht mal ein Projekt erstellen (Create-Button ausgegraut, keine Fehlermeldung). Visual Studio Plugins funktionieren soweit ich weiss nicht mit Express.

Edit: Cross-Plattform waere uebrigens nett. (Windows, Mac OS

[decimad]

Ich sehe in der DDT-Gruppe kein Rumgeschreie, dass es nicht funzen würde. Überrascht mich jetzt, dass das nicht funktioniert, vor allem wäre das auch die einzige Variante, die Deinen Ansprüchen genügen würde. Wobei der Debugger-support mit gdb wohl hakelig sein soll. Ich hab hier VS benutzt und das scheint gut zu funktionieren, mindestens mal gut genug, um die Sprache besser kennen zu lernen und damit kleine Konsolentools zu schreiben.

[volkard]

decimad schrieb:

(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)

Also (ich zerteile so in Zeilen, daß keine zwei Zeilen auf das selbe Element zugreifen müssen):

(0,1)(2,3) //beide gehen noch parallel
(0,2)(1,3) //auch
(1,2) //leider zugriff auf die 1, ganz ungeschickt
(0,1) //und nochmal
(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)

macht 19 Zeilen.

decimad schrieb:

Wenn das nicht die Reihenfolge ist, die Du möchtest, dann müssen wir einen anderen Algorithmus wählen

Jo. Aber woher nehmen? Alternativ erstmal die Zugriffe sammeln und dann geeignet umsortieren. Greedy die Zeilen vollmachen, würde ich mal versuchen, wobei halt kein Zugriff einen anderen Zugriff aufs selbe Element überholen darf.
Uih, und das Nachsortieren geht in D ganz einfach. In C++ würde ich mir einen abbrechen.

[otze]

@Decimad: Wow. Nun will ich auch mixins :).