Kleiner Coding-Contest

[camper]

mit

const auto N = 1000u;

template<typename F, F* foo>
void test(const std::uint32_t* data, char const* name, std::size_t times = 1000000 )
{
    using namespace std::chrono;
    auto best = high_resolution_clock::duration::max();

    auto check = 0u;
    for (auto t = times; t--;)
    {
        auto start = high_resolution_clock::now();
        auto n = -2*N;
        do {
            check += !!foo( data[2*N+n], data[2*N+n+1] );
        } while( n+=2 );
        auto end = high_resolution_clock::now();
        if ( end - start < best )
        {
            best = end - start;
            t = times;
            check = 0; // für hustbaer
        }
    }

    std::cout << std::setw(16) << std::right << name << ": " << best.count() << "\tcheck\t" << check << '\n';
}

int main()
{
    std::minstd_rand rng( time(nullptr) );
    std::uniform_int_distribution<uint32_t> dis( 0, 31 );

    std::vector<uint32_t> values;
    std::generate_n(std::back_inserter(values), 2*N, [&]{ return 1 << dis(rng); } );
//    std::generate_n(std::back_inserter(values), 2*N, [&]{ return dis(rng); } );

    test<decltype(foo1), foo1>( &*std::begin(values), "Arcoth" );
    test<decltype(foo2), foo2>( &*std::begin(values), "hustbaer" );
    test<decltype(foo3), foo3>( &*std::begin(values), "seldon" );
    test<decltype(foo4), foo4>( &*std::begin(values), "Marthog" );
    test<decltype(foo5), foo5>( &*std::begin(values), "camper's POPCNT" );
    test<decltype(foo6), foo6>( &*std::begin(values), "Arcoth's POPCNT" );
}

wird alles ordentlich geinlined. Im Falle des Falles hätte man ja nur eine solche Funktion im Programm, die nicht über einen Zeiger aufgerufen wird.

[Columbo]

template<typename F, F* foo>

Asterisk solltest du weglassen können.

auto n = -2*N;
        do {
            check += !!foo( data[2*N+n], data[2*N+n+1] );
        } while( n+=2 );

Völlig irre!
Warum nicht

std::size_t n = 0;
        do
            check += !!foo( data[n], data[n+1] );
        while( n += 2 != 2*N );

?

[camper]

Arcoth schrieb:

template<typename F, F* foo>

Asterisk solltest du weglassen können.

Das ist kein Funktionsparameter...

Arcoth schrieb:

auto n = -2*N;
        do {
            check += !!foo( data[2*N+n], data[2*N+n+1] );
        } while( n+=2 );

Völlig irre!
Warum nicht

std::size_t n = 0;
        do
            check += !!foo( data[n], data[n+1] );
        while( n += 2 != 2*N );

?

Da warnt gcc gleich vor undefiniertem Verhalten. Zu einfach nach Korrektur des offenbaren Fehler.

[camper]

Ich hab noch zwei

bool exactly_one_bit_set_false(uint32_t v)
{
    uint32_t a;
    asm goto( R"(
        popcnt %[v], %[cnt]
        dec %[cnt]
        jz %l2
    )" :: [v]"r"(v), [cnt]"r"(a) :: RET_TRUE );
    return false;
RET_TRUE:
    return true;
}
bool exactly_one_bit_set_true(uint32_t v)
{
    uint32_t a;
    asm goto( R"(
        popcnt %[v], %[cnt]
        dec %[cnt]
        jnz %l2
    )" :: [v]"r"(v), [cnt]"r"(a) :: RET_FALSE );
    return true;
RET_FALSE:
    return false;
}

bool foo7(uint32_t u, uint32_t v)
{
    return exactly_one_bit_set_false(u)
        && exactly_one_bit_set_false(v)
        && ( u != v );
}

bool foo8(uint32_t u, uint32_t v)
{
    return exactly_one_bit_set_true(u)
        && exactly_one_bit_set_true(v)
        && ( u != v );
}

foo7 scheint dabei schneller als jede andere bisherige Variante zu sein. Jedenfalls dann, wenn der Compiler inlinen kann.

[Columbo]

Das ist kein Funktionsparameter...

A non-type template-parameter of type [..] “function returning T” is adjusted to be of
type [..] “pointer to function returning T” [..]

Zu einfach nach Korrektur des offenbaren Fehler.

Klammern vergessen, war schließlich ungetestet.

dec %[cnt]
jz %l2

Clever! Ist das die Standardmethode um zu testen ob eine Variable den Wert 1 hat?

Jedenfalls dann, wenn der Compiler inlinen kann.

Ja, aber nur wegen der Branch-Prediction vom jnz . Ich schreib' mal eine Variante wo nicht nur Zweierpotenzen übergeben werden.

[camper]

Arcoth schrieb:

Das ist kein Funktionsparameter...

A non-type template-parameter of type [..] “function returning T” is adjusted to be of
type [..] “pointer to function returning T” [..]

g++ mag es jedenfalls nicht. Ist wohl auch noch nicht abschliessend geklärt. Der Interpretationsspielraum hier kommt dadurch zustande, dass nicht klar ist, ob diese Parameteranpassung beim Template selbst (dann muss der Stern hin) oder erst bei der konkreten Templatespezialisierung (dann ist er nicht erforderlich) durchgeführt wird.

[hustbaer]

Wäre es nicht hinsichtlich Inlining das beste auf Funktionszeiger zu verzichten und die Funktionen als Funktor zu übergeben?

Und... ich glaube zwar dass die Funktion nicht wirklich gut vektorisierbar ist, aber um dem Compiler ne bessere Chance zu geben würde ich den do-while Loop auf nen normalen for Loop umschreiben:

for (int n = 0; n < N; n++)
            check += !!foo(data[2 * n], data[2 * n + 1]);

[Columbo]

Das war ein Flüchtigkeitsfehler.

Den nächsten haste aber gleich eingebaut.

Hoffe dass das hier korrekt ist:

const auto N = 1000u;

template <typename F, F* foo>
void test( std::uint32_t const* data, char const* name, std::size_t times = 1000000 )
{
	using namespace std::chrono;

	auto best = high_resolution_clock::duration::max();

	uintmax_t parity = 0;
	for (auto t = times; t--;)
	{
		auto start = high_resolution_clock::now();

		for( unsigned n = 0; n != N; ++n )
			parity += foo( data[2*n], data[2*n+1] );

		auto end = high_resolution_clock::now();
		auto current_time = end - start;
		if ( current_time < best )
		{
			best = current_time;
			t = times;
			parity = 0;
		}
	}

	std::cout << std::setw(20) << std::right << name << ": " << best.count() << "\tparity\t" << parity << '\n';
}

int main()
{
	std::minstd_rand rng( time(nullptr) );
	std::uniform_int_distribution<uint32_t> dis( 0, 31 );

	std::vector<uint32_t> values;
	values.reserve(2*N);

	for( std::size_t n = 0; n != 2*N; ++n )
		if( rng() % 2 )
			values.push_back( 1 << dis(rng) );
		else
			values.push_back( dis(rng) );

	test<decltype(foo1), foo1>( &*std::begin(values), "Arcoth" );
	test<decltype(foo2), foo2>( &*std::begin(values), "hustbaer" );
	test<decltype(foo3), foo3>( &*std::begin(values), "seldon" );
	test<decltype(foo4), foo4>( &*std::begin(values), "Marthog" );
	test<decltype(foo5), foo5>( &*std::begin(values), "camper's POPCNT (1)" );
	test<decltype(foo6), foo6>( &*std::begin(values), "camper's POPCNT (2)" );
}

g++ -O3
              Arcoth: 990	parity	328000000
            hustbaer: 1353	parity	328000000
              seldon: 1172	parity	328000000
             Marthog: 1304	parity	328000000
 camper's POPCNT (1): 1371	parity	328000000
 camper's POPCNT (2): 4992	parity	328000000

g++ [(ohne Optimierung)]
              Arcoth: 11718	parity	323000000
            hustbaer: 11326	parity	323000000
              seldon: 11500	parity	323000000
             Marthog: 12090	parity	323000000
 camper's POPCNT (1): 6422	parity	323000000
 camper's POPCNT (2): 12230	parity	323000000

Wobei (1) deine allererste Variante ist, und (2) das von dir geschriebene foo7 .

[camper]

Es ist schon gar nicht mehr ganz klar, was eigentlich gemessen wird. Bei mir ist zunächst seldons Variante stets besser als Arcoths. Füge ich eine weiter Funktion hinzu ist wieder Arcoths Variante besser. Hier spielen also leider noch andere Faktoren eine Rolle.
Auch schön ist

bool foo7(uint32_t u, uint32_t v)
{
    return __builtin_popcount(u) == 1
        && __builtin_popcount(v) == 1
        && ( u != v );
}

manchmal durchgängig schneller als andere, Stelle ich die Reihenfolge um, schon wieder nicht.
Letzlich keine Aufgabe mit gutem Optimierungspotential - der Compiler erzeugt von sich aus schon passablen Code.

[Columbo]

manchmal durchgängig schneller als andere

Lol! Die habe ich als erstes ausprobiert, nachdem ich __builtin_popcount vorgeschlagen habe (spul ein paar Seiten zurück), aber GCC hat da einen Funktionsaufruf drinnen gehabt (zumindest nach GCC-Explorer) - das kann also unmöglich schnell sein... ist es aber. Poste mal den Assembler auf deiner Maschine.

[Columbo]

Hier haben wir es:

foo7(unsigned int, unsigned int):
	pushq	%rbp
	pushq	%rbx
	movl	%edi, %edi
	movq	%rdi, %rbx
	movl	%esi, %ebp
	subq	$8, %rsp
	call	__popcountdi2
	xorl	%edx, %edx
	cmpl	$1, %eax
	je	.L6
	addq	$8, %rsp
	movl	%edx, %eax
	popq	%rbx
	popq	%rbp
	ret
.L6:
	movl	%ebp, %edi
	call	__popcountdi2
	cmpl	$1, %eax
	sete	%dl
	cmpl	%ebp, %ebx
	setne	%al
	addq	$8, %rsp
	andl	%eax, %edx
	movl	%edx, %eax
	popq	%rbx
	popq	%rbp
	ret

Zeile 8 und 19.
Und das bei g++ mit dritten Optimierungslevel.

[camper]

popcnt ist ein SSE4.2-Befehl. Wenn also SSE4.2 nicht explizit oder per -march aktiviert ist, muss der Compiler logischerweise etwas anderes daraus machen...

[Columbo]

camper schrieb:

popcnt ist ein SSE4.2-Befehl.

Nein, POPCNT wurde zwar zeitgleich mit 4.2 eingeführt, ist aber kein Teil dieser SSE-Erweiterung und hat sein eigenes CPUID-Bit (das 23ste von ECX).

[camper]

Selbst wenn du recht hättest, solltest du überlegen, ob es sinnvoll ist, jeden vermeintlichen Fehler korrigieren zu wollen.

[Columbo]

Selbst wenn du recht hättest, solltest du überlegen, ob es sinnvoll ist, jeden vermeintlichen Fehler korrigieren zu wollen.

Ich könnte dir nun Machiavelli zitieren, ganz in deinem Stil, aber ich werde meine (eigentlich unangebrachte) Klugscheißerei mal unterlassen. :p

Letzlich keine Aufgabe mit gutem Optimierungspotential - der Compiler erzeugt von sich aus schon passablen Code.

Dann schlage eine vor, du scheinst dich mit derartigem ja sehr gut auszukennen.

[volkard]

Arcoth schrieb:

Statt bis 200000000 zu messen miss lieber 1000 mal bis 200000 und nimm den schnellsten Lauf. Du willst nämlich das Reinhacken des BS in die Messung eliminieren, was damit viel viel zuverlässiger geht als mit Duchschnittsmessung.

Gottogott! Jetzt bekomme ich total verrückte Ergebnisse!

Ich petz Dir die Ohren ab, wenn Du nicht zu messen lernst.

[volkard]

Arcoth schrieb:

Was soll das !! da? Verhindert das eine Optimierung?

Die Koplett-Wegmach-Optimierung wird verhindert durch check+= nebst einer nicht wegoptimierbaren Verwendung von check, am Einfachten einer Bildschirmausgabe.

!!foo ist nur eine andere Schreibweise für bool(foo).
Eine nicht offensichtliche Schreibweise und daher eigentlich streng zu vermeiden. Aaaber, da gibt's leider ein Außenweltproblem damit: Der MSVC warnt rum bei f(bool);f(einInt) mit so dummen Sprüchen "coversion loses significant digits" oder so. Sorry, hab den Spruch vergessen, bin zu lange unter Linux. Der MSVC warnt aber genau gleich bei f(bool(einInt);! Eigentlich muss der Cast auch bedeuten "Lieber Compiler, ich weiß, was ich tue, halt mal hier die Klappe!". Tut er aber nicht bei MSVC. Aber bei f(!!einInt) hält er die Klappe.

Also benutzen wir gelegentlich aus Angewohnheit !! statt bool().

[Columbo]

!!foo ist nur eine andere Schreibweise für bool(foo).

Das ist mir klar. Hast du die darauf folgende Konversation verfolgt? Es ging darum, dass das !! überflüssig ist, weil die Rückgabewerte aller Funktionen schon bool sind.

Ich petz Dir die Ohren ab, wenn Du nicht zu messen lernst.

[volkard]

[quote="Arcoth"]

!!foo ist nur eine andere Schreibweise für bool(foo).

Das ist mir klar. Hast du die darauf folgende Konversation verfolgt? Es ging darum, dass das !! überflüssig ist, weil die Rückgabewerte aller Funktionen schon bool sind.

Sorry, war nicht auf dem Laufenden.

Arcoth schrieb:

Ich petz Dir die Ohren ab, wenn Du nicht zu messen lernst.

5 signifikante Stellen kriegt man selbst unter Windows recht stabil gemessen mit vielleicht einem Minütchen Messzeit.
Trotz -march=native schlagen bei mir anscheinend Alignmentsachen noch rein: Manchmal spielt die Reihenfolge, in der die zu messenden Funktionen im Quellcode stehen, eine entscheidende Rolle.
Euren Messcode schaue ich mir morgen früh an, kam noch nicht dazu.

[volkard]

camper schrieb:

t = times;

Jup, das ist der Bringer.
Genau so messe ich. Es ist unglaublich stabil im Summe, daß es die Quirligkeiten den Betriebssystems komplett ausklammert.

Ich habs zwar vielfach in diesem Forum schon gezeigt, aber da hatte die Mehrheit dann doch nur den Durchschnitt messen wollen und ich facepalmte wie wild.

@camper: hattest Du diese Schleife selber gefunden oder wars von mir oder einer anderen Quelle?