Kleiner Coding-Contest

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

?

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 .