Kleiner Coding-Contest

[hardware]

umbenannt

[seldon]

Ich werf der Vollständigkeit halber noch mal eine andere Methode in die Runde:

int foo(uint32_t x, uint32_t y) {
  return (x & -x) == x &&
         (y & -y) == y && 
         (x | y)  != x &&
         x;
}

Dabei mache ich mir zunutze, dass -x == ~x + 1, wodurch

x      00001000    00001010
~x     11110111    11110101
-x     11111000    11110110
x & -x 00001000    00000010

...mit anderen Worten: x & -x isoliert das niederwertigste Bit von x, und das ist genau dann x, wenn x höchstens ein gesetztes Bit hat.

Es sieht mir allerdings danach aus, als käme zumindest clang mit der !(x & (x - 1))-Variante besser zurecht, weil er da leal missbrauchen kann, um mit einer Instruction x - 1 in ein zweites Register zu schubsen; für -x braucht er movl und negl. Das wird für den gcc auf x86(-64) dann auch gelten. Wie das bei solchen Low-Level-Angelegenheiten immer so ist, YMMV auf anderen Architekturen.

[Columbo]

Ich habe das ganze mal gemessen.

#include <cstdint>

bool foo1(uint32_t u, uint32_t v)
{
	return !(u & (u - 1))
	    && !(v & (v - 1))
	    && u != v
	    && u && v;
}

bool foo2(int32_t u, int32_t v)
{
	int temp1 = u - 1;
	int temp2 = v - 1;

	return temp1 >= 0 && !(temp1 & u)
          && temp2 >= 0 && !(temp2 & v)
          && u != v;
}

int foo3(uint32_t x, uint32_t y)
{
  return (x & -x) == x &&
         (y & -y) == y &&
         (x | y)  != x &&
         x;
}

bool foo4(uint32_t u, uint32_t v)
{
	asm goto (
R"(
	mov %%eax, %%ecx
	sub $1, %%ecx
	js %l2
	test %%eax, %%ecx
	jnz %l2

	mov %%ebx, %%ecx
	sub $1, %%ecx
	js %l2
	test %%ebx, %%ecx
	jnz %l2

	test %%eax, %%ebx
	jnz %l2
)"
	:: "a"(u), "b"(v)
	: "%ecx"
	: RET_FALSE );

	return true;
	RET_FALSE: return false;
}

bool foo5(uint32_t u, uint32_t v)
{
	uint8_t B = 1;
	asm (
R"(
	blsr %%eax, %%ecx
	setz %%dl
	and %%dl, %0
	setnc %%dl
	and %%dl, %0

	blsr %%ebx, %%ecx
	setz %%dl
	and %%dl, %0
	setnc %%dl
	and %%dl, %0

	test %%eax, %%ebx
	setz %%dl
	and %%dl, %0
)"
	: "+r"(B)
	: "a"(u), "b"(v)
	: "%ecx", "%dl" );

	return B;
}

bool foo6(uint32_t u, uint32_t v)
{
	uint8_t B = 1;
	asm (
R"(
	popcnt %%eax, %%ecx
	cmp $1, %%ecx
	sete %%dl
	and %%dl, %0

	popcnt %%ebx, %%ecx
	cmp $1, %%ecx
	sete %%dl
	and %%dl, %0

	test %%eax, %%ebx
	setz %%dl
	and %%dl, %0
)"
	: "+r"(B)
	: "a"(u), "b"(v)
	: "%ecx", "%dl" );

	return B;
}

#include <random>
#include <iostream>
#include <iomanip>

template< typename F >
void test( F foo, char const* name, std::size_t N = 200000000 )
{
	auto first = clock();
	std::minstd_rand rng( time(nullptr) );
	std::uniform_int_distribution<uint32_t> dis( 0, 31 );

	while(N--)
	{
		auto d1 = (1 << dis(rng)),
		     d2 = (1 << dis(rng));
		foo( d1, d2 );
	}

	auto measured = 1. * (clock() - first) / CLOCKS_PER_SEC;
	std::cout << std::setw(15) << std::right << name << ": " <<  measured << '\n';
}

int main()
{
	test( foo1, "Arcoth" );
	test( foo2, "hustbaer" );
	test( foo3, "seldon" );
	test( foo4, "Marthog" );
	test( foo5, "Arcoth's BLSR" );
	test( foo6, "Arcoth's POPCNT" );
}

g++ -O3 -std=c++1y:
         Arcoth: 8.46297
       hustbaer: 7.63319
         seldon: 7.58602
        Marthog: 8.56772
  Arcoth's BLSR: 8.89045
Arcoth's POPCNT: 8.67961

Da ich von effizientem Assembler äußerst wenig Ahnung habe, habe ich einfach mal hustbaers Booyahh-Rufen gefolgt und die bedingten Sprünge eliminiert.
Das Ergebnis scheint eindeutig, aber vielleicht kann jemand ja foo5 und foo6 verbessern (bzw. umschreiben ).

[volkard]

Die Messung macht jetzt bei den Sprüngen, ob eine Zahl genau ein Bit gesetzt hat, aber immer in eine Richtung, wodurch die bedingten Sprünge da so billig werden wie unbedingte, weils die Sprungvorhersage immer recht hat.

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.

[camper]

Die Varianten 5 und 6 sind schon mal falsch, weil jedesmal das gleiche Register mit set verwendet wird, damit wird das Ergebnis vorheriger set-Instruktionen überschrieben. uint8_t als lokale Variable ist auch keine gute Idee, so muss der Compiler beim return noch einen Vergleich mit 0 einbauen.
Ich biete mal noch

bool foo(uint32_t u, uint32_t v)
{
    bool res;
    uint32_t a, b;
    asm (
R"(
    popcnt %[u], %[u_cnt]
    popcnt %[v], %[v_cnt]
    dec %[u_cnt]
    dec %[v_cnt]
    or %[u_cnt], %[v_cnt]
    setz %[res]
    xor %[u], %[v]
    cmovz %[v], %k[res]
)"
    : [res]"=&r,r,r"(res)
    : [u]"r,r,r"(u), [v]"r,r,r"(v), [u_cnt]"r,0,r"(a), [v_cnt]"r,r,0"(b) );

    return res;
}

an. Ist aber wahrscheinlich auch nicht schneller.

[Columbo]

Die Varianten 5 und 6 sind schon mal falsch, weil jedesmal das gleiche Register mit set verwendet wird, damit wird das Ergebnis vorheriger set-Instruktionen überschrieben.

Kann es sein, dass du was falsch verstanden hast? Oder habe ich irgendwo einen Denkfehler?

uint8_t als lokale Variable ist auch keine gute Idee, so muss der Compiler beim return noch einen Vergleich mit 0 einbauen.

Ich dachte halt nur, bei einem bool ist es nicht definiert, wie true dargestellt wird.
Und ich wende ja and drauf an.

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 habe die Testfunktion zu

template< typename F >
void test( F foo, char const* name, std::size_t N = 50000, std::size_t times = 10000 )
{
	std::minstd_rand rng( time(nullptr) );
	std::uniform_int_distribution<uint32_t> dis( 0, 31 );

	std::vector<clock_t> vec;
	vec.reserve(times);

	for (auto t = times; t--;)
	{
		auto first = std::chrono::high_resolution_clock::now();
		for (auto n = N; n--;)
		{
			auto d1 = (1 << dis(rng)),
			     d2 = (1 << dis(rng));
			foo( d1, d2 );
		}
		vec.push_back( (std::chrono::high_resolution_clock::now() - first).count() );
	}

	std::cout << std::setw(16) << std::right << name << ": " << *std::min_element(std::begin(vec), std::end(vec)) << '\n';
}

umgeschrieben.

Jetzt erhalte ich (mit campers Version) sowas

g++ -O3
          Arcoth: 2007824
        hustbaer: 2043283
          seldon: 2022938
         Marthog: 1971211
   Arcoth's BLSR: 2066844
 Arcoth's POPCNT: 2042884
campers's POPCNT: 1975276

Das heißt: Marthogs Version ist Top, gefolgt von camper und dann meiner ersten. Was allerdings total verdreht ist.

[camper]

Arcoth schrieb:

camper schrieb:

Die Varianten 5 und 6 sind schon mal falsch, weil jedesmal das gleiche Register mit set verwendet wird, damit wird das Ergebnis vorheriger set-Instruktionen überschrieben.

Kann es sein, dass du was falsch verstanden hast?

Ja, das kann sein. Die and-Verknüpfung mit B ist ja ein bisschen umständlich, das habe ich nicht durchdacht.

Arcoth schrieb:

camper schrieb:

uint8_t als lokale Variable ist auch keine gute Idee, so muss der Compiler beim return noch einen Vergleich mit 0 einbauen.

Ich dachte halt nur, bei einem bool ist es nicht definiert, wie true dargestellt wird.
Und ich wende ja and drauf an.

Der Compiler hat sich an die ABI-Spezifikation (ich beziehe mich mal auf die mir vorliegende System V AMD64 ABI v1.0)zu halten, die besagt, dass bei der Funktionsrückgabe von bools die bits 1-7 nicht gesetzt sein dürfen. Weil der Compiler natürlich nicht wissen kann, ob dass bei deinem B schon der Fall ist, muss er entsprechend (überflüssigerweise) anpassen.

[Columbo]

camper schrieb:

Die and-Verknüpfung mit B ist ja ein bisschen umständlich, das habe ich nicht durchdacht.

In der Tat, die ist umständlich. Deswegen gibt es ja auch deutlich bessere Methoden, wie du demonstriert hast.

camper schrieb:

Der Compiler hat sich an die ABI-Spezifikation (ich beziehe mich mal auf die mir vorliegende System V AMD64 ABI v1.0)zu halten, die besagt, dass bei der Funktionsrückgabe von bools die bits 1-7 nicht gesetzt sein dürfen.

Also kann bei false der LSB gesetzt sein?

Bei Itanium ist das klarer:

The bool value false is encoded as 0, true as 1.

[hustbaer]

Da gehört noch was rein was das Ergebnis des Funktionsaufrufs verwendet. Ohne die Verwendung des Ergebnisses sind Performance-Messungen Quatsch, da man nur misst welche Version sich vom Optimizer besser eliminieren lässt.

template< typename F >
void test( F foo, char const* name, std::size_t N = 50000, std::size_t times = 10000 )
{
    std::minstd_rand rng( 42 );
    std::uniform_int_distribution<uint32_t> dis( 0, 31 );

    std::vector<clock_t> vec;
    vec.reserve(times);

    size_t check = 0;
    for (auto t = times; t--;)
    {
        auto first = std::chrono::high_resolution_clock::now();
        for (auto n = N; n--;)
        {
            auto d1 = (1 << dis(rng)),
                 d2 = (1 << dis(rng));
            check += foo( d1, d2 ) ? 1 : 0;
        }
        vec.push_back( (std::chrono::high_resolution_clock::now() - first).count() );
    }

    std::cout << std::setw(16) << std::right << name << ": " << *std::min_element(std::begin(vec), std::end(vec)) << ", check = " << check << '\n';
}

EDIT: Und natürlich mit identischem Seed für alle Varianten messen.

Und was jetzt noch fehlt, wären Inputs die eben nicht aus genau einem Bit bestehen. Die Conditional-Jumps für diese Varianten werden mit dem aktuellen Test ja auch perfekt predicted.

[camper]

Die Messung wird sowieso durch den Zufallsgenerator dominiert.

template< typename F >
void test( F foo, char const* name, std::size_t N = 5000 /* sollte in L1-Chache passen */, std::size_t times = 100000 )
{
    std::minstd_rand rng( time(nullptr) );
    std::uniform_int_distribution<uint32_t> dis( 0, 31 );

    std::vector<uint32_t> values;

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

    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();
        for (auto n = 2*N; n-=2;)
        {
            check += !!foo( values[n], values[n+1] );
        }
        auto end = high_resolution_clock::now();
        if ( end - start < best )
        {
            best = end - start;
            t = times;
        }
    }

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

berichtigt das und erschlägt gleich noch das seed-Problem.

[Columbo]

Da gehört noch was rein was das Ergebnis des Funktionsaufrufs verwendet.

Mein Fehler. Übrigens, warum das ? 1 : 0 ?
~~
Ich habe jetzt 50000x50000 gemessen, so Zehn Minuten~~
Mache ich mal mit campers Version.

[Columbo]

Ok, nach campers Messmethode sieht die Rangliste nicht anders aus als bei 50000²:

Arcoth: 9210	check	694714188
        hustbaer: 10347	check	495174870
          seldon: 10850	check	501203850
         Marthog: 11293	check	1361231708
   Arcoth's BLSR: 13419	check	1577699019
 Arcoth's POPCNT: 12890	check	488825540
campers's POPCNT: 9254	check	1223154165

!!foo( values[n-1], values[n-2] );

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

[camper]

Arcoth schrieb:

Also kann bei false der LSB gesetzt sein?

Wird ein bool im Speicher abgelegt, so nimmt es ein Byte ein mit den Werten 0 oder 1 für false bzw. true.
Wird ein bool dagegen in einem Register gespeichert, so entspricht jeder Wert ungleich 0 true.
Bei Übergabe eines bools als Funktionsparameter oder Rückgabewert signalisiert das niederwertigste Bit true bzw. false, bits 1-7 sind nicht gesetzt aber bits 8-63 bleiben unspezifiziert (unabhängig davon, ob die Übergabe auf dem Stack oder in einem Register erfolgt).

[camper]

Arcoth schrieb:

Was soll das !! da?

Faulheit.

[Columbo]

generate_n(std::back_inserter(values), 2*N, [&]{ return 1 << dis(rng); } );
    // [...]
        for (auto n = 2*N; n-=2;)
            check += !!foo( values[n], values[n+1] );

Ist das nicht ein OBOE?

camper schrieb:

Arcoth schrieb:

Was soll das !! da?

Faulheit.

Nein, die Rückgabewerte sind bool . Und zwar bei jeder Funktion.

[oenone]

Arcoth schrieb:

generate_n(std::back_inserter(values), 2*N, [&]{ return 1 << dis(rng); } );
    // [...]
        for (auto n = 2*N; n-=2;)
            check += !!foo( values[n], values[n+1] );

Ist das nicht ein OBOE?

Stimmt, es müsste (n-=2)>=0 sein. Ansonsten wird values[0] bzw. values[1] nie benutzt.

[camper]

Das war ein Flüchtigkeitsfehler. Mit

const auto N = 1000u;

template< typename F >
void test( F foo, 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;
        }
    }

    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); } );

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

fängt der Compiler endlich auch mal mit inlining an bei einigen Varianten. (hab keinen avx2-fähigen Prozessor)

[hustbaer]

Arcoth schrieb:

Da gehört noch was rein was das Ergebnis des Funktionsaufrufs verwendet.

Mein Fehler. Übrigens, warum das ? 1 : 0 ?

Naja implizite Konvertierung von bool nach int finde ich nicht unbedingt "schön", daher ? 1 : 0 .
Machen tut es ohne das ? 1 : 0 natürlich das selbe.

camper schrieb:

Die Messung wird sowieso durch den Zufallsgenerator dominiert.

template< typename F >
void test( F foo, char const* name, std::size_t N = 5000 /* sollte in L1-Chache passen */, std::size_t times = 100000 )
{
    std::minstd_rand rng( time(nullptr) );
    // ...
}

berichtigt das und erschlägt gleich noch das seed-Problem.

Wie man an den unterschiedlichen "check" Werten sieht, ist das seed-Problem immer noch da.
Es werden jetzt zwar alle Durchläufe für eine bestimmte Funktion mit den selben Zahlen gemacht, aber die verschiedenen Funktionen werden immer noch mit unterschiedlichen Zahlen getestet.

Der Wert heisst ja u.A. deswegen "check", weil man damit überprüfen kann ob auch alle Funktionen das selbe Ergebnis liefern

Aber ich sehe gerade dass du das in der letzten Variante eh schon behoben hast.

[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 );

?