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

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

[Kellerautomat]

So, nach einer Neuinstallation klappt das Eclipse Plugin endlich. Aber die Code-Completion finde ich mehr als enttaeuschend. Bei Konstruktoren kann der mir nicht mal die Parameter aller verschiedenen Overloads anzeigen. Ausserdem ist Code-Completion case-sensitive.

[decimad]

Ich hab lieber keine tolle Code-Completion bis Du sie uns programmiert hast, als das in C++-Template-Form hinzuschreiben ;). Kannst ja mal auf der DDT-Liste stänkern, vielleicht fühlt sich dann jemand motiviert!

[knivil]

Nun, meine Loesung http://ideone.com/gOIzqH , und die Probleme mit VS 2013 http://www.c-plusplus.net/forum/320689 . Insgesamt gefaellt mir das noch nicht ganz, da "parallele" swap_if's wie in der ersten Ebene nicht direkt hintereinander stehen (es stehen die 8 parallelen Operationen nicht hintereinander). Gleiches gilt fuer den rosa Rattenschwanz. Funktioniert mit VS 2010, g++ und clang++. bitonic_sort-Template sollte C++03 entsprechen, d.h. ueberall benutzbar sein.

Im Nachhinein betrachtet, war es doch gar nicht so schwer. Zwar noch recht lang, aber vielleicht kannmit den Moeglichkeiten von C++11 das Template klarer gestalltet werden. Mal schauen.

Einige Verstaendnisfragen zur Loesung in

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

Mit GenerateOddEven werden Strings generiert, die dann durch mixin an besagter Stelle als Code eingefuegt werden?

[decimad]

Ja, genau.

[decimad]

Ich fühle mich aber gerade ziemlich dumm, weil mir keine Breadth-First-Umsetzung zu dem Algorithmus einfällt, die es hinbekommt, CAS aus gleicher Stufe zusammenzuhalten. Die einzige Option wäre, die Stufe in den Funktionen mitzureichen und in den CAS-Anweisungen zu vermerken und hinterher nach der Stufe zu sortieren. Aber das muss doch irgendwie klüger gehen.