3. Überladene Funktion auswählen

Überladene Funktion auswählen

  • Mod

    Das nennst du peinlich? Ich habe heute Morgen eine halbe Stunde gesucht was hier falsch ist:

    unsigned y_square = 1;
	unsigned x_square = 1;

	for (unsigned y = 1; y != root; ++y)
	{

		for (unsigned x = 1; x != root; ++x)
		{
			// ...
			// ...
			// ...
			x_square += 2*x+1;
		}

		y_square += 2*y+1;
	}

    volkard hätte es natürlich sofort gesehen, der sieht sowas einfach direkt.

    0
  • V

    Arcoth schrieb:

    volkard hätte es natürlich sofort gesehen, der sieht sowas einfach direkt.

    hab's auch nicht direkt gesehen.
    mir wäre es aber nicht passiert.
    beim schleife-verdoppeln wäre square als an-die-schleife-gekettet mit der schleife bewegt worden.

    0

  • Das fehlende x_square = 1 oder was?
    Sowas kann man schonmal übersehen.

    0
  • ?

    Ist das premature Optimization? x*x ist viel schneller als +=(x<<1)+1. Und dass man den Scope seiner Variablen minimal halten soll ist ja schon seit Jahrzehnten bekannt. Zudem ist das vermutlich unnötiger Brute-Force den man algorithmisch optimieren kann.

    0

  • tinyscope schrieb:

    Ist das premature Optimization? x*x ist viel schneller als +=(x<<1)+1.

    Hast du es ausprobiert?

    0
  • F

    @Arcoth
    Geht's darum, dass x_square vor der Schleife definiert wird anstatt in der äusseren? Ein Kopierfehler - wie ich ihn begangen habe - ist doch immer peinlicher als ein Logikfehler.

    0
  • ?

    hustbaer schrieb:

    tinyscope schrieb:

    Ist das premature Optimization? x*x ist viel schneller als +=(x<<1)+1.

    Hast du es ausprobiert?

    Ja. 2.15s vs 1.38s bei -O3 und

    void f(int i);

void g(int x) {
  for (int i=1; i<x; ++i)
    f(i*i);
}

void h(int x) {
  for (int i=0, square=1; i!=x; ++i, square+=2*i+1)
    f(square);
}

    (x=1000*1000*1000)

    0
  • ?

    2.15s vs 1.38s bezog sich auf h (Arcoth) vs h (i*i).

    0
  • ?

    * h vs g.

    0

  • Das muss aber ein seltsamer Compiler sein, der dir die Schleife nicht komplett wegoptimiert. 😉

    Hab's aber grad selbst ausprobiert, und muss zu meinem Erstaunen feststellen dass du Recht hast. (Also nicht dass die Schleife nicht wegoptimiert wird, sondern dass x*x wirklich schneller ist als die += Variante.)

    0
  • V

    hustbaer schrieb:

    tinyscope schrieb:

    Ist das premature Optimization? x*x ist viel schneller als +=(x<<1)+1.

    Hast du es ausprobiert?

    vor 2-3 Jahren hatte ich es ausprobiert, i7 mit AFAIR 6 Takten pro integer-multiplikation. Es war fast gleich.

    ungefähr so gleich wie bei tinyscopes messung nur andersrum und noch weniger signifikant. bei "(x=1000*1000*1000)" und "2.15s vs 1.38s" reden wir von vielleicht 3 takten, die werden von allem, was mit den

    // ...
            // ...
            // ...

    steckt, komplett marginalisiert. ich hatte eher sowas wie einen takt zugunsten Arcoths.

    ich erwarte, daß in zukunft noch ein paarhundertmillionen transistoren in die multiplikation gesteckt werden. außerdem nimmt, vermute ich, die multiplikation ein wenig registerdruck weg, was nur zieht, wenn in f() sauwenig passiert, vielleicht sind tinyscopes messungen deswegen signifikanter als in der praxis.

    würde selbst für private forschung, wo ich schon extrem auf jeden takt achte (manche nennen es krank, aber es ist halt ein hobby, da muss ich nicht nach stechuhr mindestens 2250 zeilen pro woche einloggen), wo ich schnellere (weil passendere) replacements für vector, array, queue, stack benutze, hier einfach bei * bleiben. Den Takt gebe ich mir.

    0
  • V

    hustbaer schrieb:

    Hab's aber grad selbst ausprobiert, und muss zu meinem Erstaunen feststellen dass du Recht hast. (Also nicht dass die Schleife nicht wegoptimiert wird, sondern dass x*x wirklich schneller ist als die += Variante.)

    Vielleicht wieder lahmer, wenn man das Problem mit Multithreading lösen läßt und auf 8 Hyperkernen nur 4 ALUs hat.
    Es ist unsicher zur Zeit, fürchte ich. Trend geht nach *.

    💡 Geschäftsidee 💡
    Ich verkaufe meine Game nicht, sondern verschenke die normale Version oder zu kelienm Preis!
    Aaber ich biete an, daß man eine auf den Zielrechner optimierte exe erwerben kann. Dazu einfach meinen Messer runterladen, der testet alle und jede Funktion aus. Auch ob zum Quadratzahlenaufzählen diese oder jene Version schneller ist. Auch ob der vergötterte Twister den MWC packt. Auch ob double oder float besser flutschen, auch ob…
    Und mit so 20 oder 50 Parametern wird dem Kunden die speziell angepaßte exe automatisch oder per Hand compiliert, und die kann er für 25€ oder halt größerem Preis kaufen. Mehr frames, mehr frags.

    0

  • Wieso sollten 8 Hyperkerne nur 4 ALUs haben, wenn ein Core schon 5 hat? 😉

    #define _CRT_SECURE_NO_WARNINGS
#define _SCL_SECURE_NO_WARNINGS
#define NOMINMAX

#include "targetver.h"

#include <iostream>
#include <string>
#include <cstdint>
#include <algorithm>
#include <vector>

#include <windows.h>

using namespace std;

__declspec(noinline) unsigned square_multiply(unsigned start, unsigned limit)
{
	unsigned accu = 0;
#pragma loop(hint_parallel(0))
	for (unsigned i = start; i <= limit; i++)
		accu += i*i;

	return accu;
}

__declspec(noinline) unsigned square_multiply_p8(unsigned start, unsigned limit)
{
	static const int batch_size = 10000;

	int batch_count = (limit - start + batch_size - 1) / batch_size;
	int slimit = limit;

	LONG accu = 0;
#pragma loop(no_vector)
#pragma loop(hint_parallel(8))
#pragma loop(ivdep)
	for (int i = start; i <= slimit; i += batch_size)
	{
		unsigned val = square_multiply(i, min(i + batch_size - 1, slimit));
		::InterlockedAdd(&accu, val);
	}

	return accu;
}

__declspec(noinline) unsigned square_multiply_novec(unsigned start, unsigned limit)
{
	unsigned accu = 0;
#pragma loop(no_parallel)
#pragma loop(no_vector)
	for (unsigned i = start; i <= limit; i++)
	{
		accu += i*i;
	}

	return accu;
}

__declspec(noinline) unsigned square_add(unsigned start, unsigned limit)
{
	unsigned accu = 0;
	unsigned square = start * start;
	for (unsigned i = start; i <= limit; i++)
	{
		accu += square;
		square += 2 * i + 1;
	}

	return accu;
}

__declspec(noinline) unsigned square_add_p8(unsigned start, unsigned limit)
{
	static const int batch_size = 10000;

	int batch_count = (limit - start + batch_size - 1) / batch_size;
	int slimit = limit;

	LONG accu = 0;
#pragma loop(no_vector)
#pragma loop(hint_parallel(8))
#pragma loop(ivdep)
	for (int i = start; i <= slimit; i += batch_size)
	{
		unsigned val = square_add(i, min(i + batch_size - 1, slimit));
		::InterlockedAdd(&accu, val);
	}

	return accu;
}

int volatile result = 0;
LARGE_INTEGER frequeny;

__declspec(noinline) uint64_t measure_one(char const* name, unsigned(*fun)(unsigned, unsigned), unsigned start, unsigned limit)
{
	SetThreadPriority(GetCurrentThread(), THREAD_PRIORITY_TIME_CRITICAL);
	Sleep(1);

	LARGE_INTEGER t0;
	QueryPerformanceCounter(&t0);

	result = fun(start, limit);

	LARGE_INTEGER t1;
	QueryPerformanceCounter(&t1);

	SetThreadPriority(GetCurrentThread(), THREAD_PRIORITY_NORMAL);

	return t1.QuadPart - t0.QuadPart;
}

void measure(char const* name, unsigned(*fun)(unsigned, unsigned), unsigned start, unsigned limit)
{
	uint64_t best_time = numeric_limits<uint64_t>::max();
	int best_result = 0;

	for (int rep = 0; rep < 10; rep++)
	{
		uint64_t t = measure_one(name, fun, start, limit);
		if (t < best_time)
		{
			rep = 0;
			best_time = t;
			best_result = result;
		}
	}

	cout << name << ": " << (best_time * 1000.0) / frequeny.QuadPart << " (" << best_result << ")\n";
}

#define MEASURE(fun) measure(#fun, fun, start, limit)

int main(int argc, char const** argv)
{
	QueryPerformanceFrequency(&frequeny);

	int start = 1234;
	int limit = 1234567;

	if (argc > 1)
		start = stoi(argv[1]);
	if (argc > 2)
		limit = stoi(argv[2]);

	cout << "start = " << start << ", limit = " << limit << "\n";

	MEASURE(square_multiply_p8);
	MEASURE(square_multiply);
	MEASURE(square_multiply_novec);
	MEASURE(square_add_p8);
	MEASURE(square_add);

	return 0;
}

    VS 2013, x64, /arch:AVX2 /Qpar
    Xeon E3-1245 v3 (quad core Haswell)

    start = 4455, limit = 1234567890
square_multiply_p8: 31.6727 (-1713703374)
square_multiply: 119.588 (-1713703374)
square_multiply_novec: 346.583 (-1713703374)
square_add_p8: 86.8956 (-1713703374)
square_add: 535.312 (-1713703374)
    0
  • Mod

    Tatsächlich, die Multiplikation scheint schneller zu sein - hätte ich nicht erwartet. Danke für den Tipp den ich sowieso nicht mehr brauche, der algorithmischen Optimierung wegen.

    0
Anmelden zum Antworten