double - caching

Seikilos

Wir haben bei uns durch Profiling festgestellt, dass eine Methode, die wir benutzen, bis zu 50 % der Ausführungszeit frisst. Das kommt nicht von irgendwoher, die Methode ist aus nem 3rdParty, also nicht von uns, recht Komplex und ein zentraler Anlaufpunkt. Das Ergebnis der Methode ist ein double. (Ums genau zusagen, macht diese Methode geografische Projektionen)
Da sie der Kern der Anwendung ist, habe ich darüber nachgedacht, ob es sich lohnt, einen cache für die Werte zu benutzen.
Wenn wir bei doubles bleiben, würd ich eine map<double,double> anlegen, und ihr etwa 10 mb an an Speicherplatz geben. Was wohl ungefähr 1024 * 1024 * 10 / 64 ca 160.000 doubles wären (was sehr wenig ist)

Mein Problem ist, ich muss ja mitunter zusehen, dass die map nicht zu groß wird, zum anderen muss ich ein double IS_EQUAL benutzen, was kein reines look up ist (Ungenauigkeit und so)
Sprich direkter Zugriff auf Map is so nicht gegeben, außer die doubles kommen nicht in voller präzision da rein, sondern schon um ein DELTA reduziert. Dann kann ich mein eingehendes Double auch auf die Präzision reduzieren und ein direktes look up machen.

Allerdings wirkt das für mich nicht gerade performance-schonender. Es gibt im Grunde zwei Szenarion: Framerate ohne Benutzer Interaktion (sehr viele doubles bleiben gleich) und Framerate während ein Benutzer Funktionen wie Zoom ausführt (sehr viele doubles ändern sich auf einmal)
Kritisch ist natürlich wenn Benutzeraktion statt findet, da dort die lags am ehesten zu spüren sind. Nun gewinnen wir garnichts, wenn das caching super klappt, solange keine benutzeraktion vorhandenen ist und bei der benutzer aktion ständig cache misses und die damit verbundenen kosten des hinzufügens des wertes und des truncate der map auf einen konstanten faktor.

Hat jemand ein paar Tipps oder Kommentare?

Danke

Bloops

Also für mich hört sich das Ganze eher nach Interpolation an...

Eine weitere Sache ist, dass man asynchron im Hintergrund die nächste Zoomstufe vorberechnen kann, wenn der User noch gar nicht das zoom-Kommando gegeben hat.

Seikilos

Was hat das mit Interpolation zutun? Ich will keine Zwischenwerte errechnen.

Das mit asynchronen irgendwas wird kaum möglich sein. Wir setzen sehr viel Paging ein, weil die visualisierten Datenmengen im GB bereich liegen. Jede mögliche Benutzeraktion kann hier nicht vorberechnet werden. Weil Scrollen und Zoomen (nur zwei der vielen Interaktionen) nicht in alle Kombinationen berechnet werden können (Kachelung, LOD)

Sebastian Pizer

Vielleicht sagst Du noch, wie diese Double-Werte benutzt werden.

Ich habe eventuell einen ähnlichen Fall: Eine recht komplizierte Abbildung von 3D nach 2D, die aber in einer kleinen Umgebung jeweils näherungsweise eine affinlineare Abbildung ist. Ich berechne daher einige Werte auf einem Gitter vor und interpoliere dann dazwischen, weil's so viel schneller geht.

Seikilos

Das wird natürlich auch so gemacht.
Es werden Texturen aufgezogen und nur dort zwsichen berechneten Werten interpoliert. Das ist kein Thema.
Da wir aber noch ein Grid haben und einzelne Objekte, die korrekt in der projezierten 2D Ebene (ohne Textur) plaziert werden müssen. Muss der Update dieser Objekte ständig durchgeführt werden.
Die Doublewerte sind die Koordinaten der Objekte, die wirklich per Vertex projeziert werden müssen

volkard

Einen double zu kürzen, sollte so wenige Takte brauchen, das glaubst Du gar nicht.

#include <iostream>
#include <ctime>
using namespace std;

double kurzmach1(double d){
	//siehe http://de.wikipedia.org/wiki/IEEE_754
	unsigned long long l=*reinterpret_cast<unsigned long long*>(&d);
	//einfach hinten ein paar Bits löschen.
	l&=0xffffffff00000000ull;
	//sodele, 64 bits sind weg und trotzdem noch 5 genaue dezimalstellen.
	return *reinterpret_cast<double*>(&l);
}

double kurzmach2(double d){
	//vorhin 32 bit weggehauen? das erinnert mich doch an was. 
	return double(float(d));
}

int main(int argc, char* argv[])
{
	{
		cout<<"siebentel-tabelle\n";
		for(int i=0;i<=7;++i)
			cout<<i/7.0<<' '<<kurzmach(i/7.0)<<'\n';
		cout<<'\n';
	}
	double kurzezeit;
	{
		cout<<"summe roh\n";
		clock_t start=clock();
		double summe=0;
		for(int i=0;i<1000000000;++i){
			summe+=double(i);
		}
		kurzezeit=(clock()-start)/double(CLOCKS_PER_SEC);
		cout<<"zeit: "<<kurzezeit<<'\n';
		cout<<"summe: "<<summe<<'\n';
		cout<<'\n';
	}
	double langezeit;
	{
		cout<<"summe mit kurzmach-overhead\n";
		clock_t start=clock();
		double summe=0;
		for(int i=0;i<1000000000;++i){
			summe+=kurzmach(double(i));
		}
		langezeit=(clock()-start)/double(CLOCKS_PER_SEC);
		cout<<"zeit: "<<langezeit<<'\n';
		cout<<"summe: "<<summe<<'\n';
		cout<<'\n';
	}
	cout<<"zeit pro kurzmach: "<<(langezeit-kurzezeit)<<" nanosekunden\n";
  return 0;
}

Seikilos

Danke für den code.

volkard

Eine vergessliche und ungenaue hashtable sollte so schnell sein, das glaubst du gar nicht.

#include <iostream>
#include <ctime>
#include <cmath>
#include <iomanip>
#include <vector>
using namespace std;

double kurzmach1(double d){
	//siehe http://de.wikipedia.org/wiki/IEEE_754
	unsigned long long l=*reinterpret_cast<unsigned long long*>(&d);
	//einfach hinten ein paar Bits löschen.
	l&=0xffffffff00000000ull;
	//sodele, 64 bits sind weg und trotzdem noch 5 genaue dezimalstellen.
	return *reinterpret_cast<double*>(&l);
}

double kurzmach2(double d){
	//vorhin 32 bit weggehauen? das erinnert mich doch an was.
	return double(float(d));
}

template<typename T,T func>
struct doublecache{
	static size_t const size=65536;
	struct entry{
		double x;
		double y;
	};
	vector<entry> data;
	doublecache():
		data(size){
	}
	double get(double x){
		double kurz=kurzmach1(x);
		size_t pos=*reinterpret_cast<unsigned long long*>(&kurz)*568337%size;
		if(data[pos].x!=kurz){
			data[pos].x=kurz;
			data[pos].y=func(x);
		}
		return data[pos].y;
	}
};

double f(double x){
	double y=sqrt(1-x*x);
	return y;
}

int main(int argc, char* argv[])
{
	clock_t start=clock();
	double summe=0;
	doublecache<typeof(&f),&f> cache;
	for(int i=0;i<100000000;++i){
		double x=i/100000000.0;
//		double y=f(x);
		double y=cache.get(x);
		summe+=y;
	}
	cout<<"zeit: "<<(clock()-start)/double(CLOCKS_PER_SEC)<<'\n';
	cout<<"PI="<<setprecision(10)<<summe/100000000*4<<'\n';
  return 0;
}

Ohne cache:
zeit: 3.484
PI=3.141592674

Mit cache:
zeit: 2.921
PI=3.141593494

Ok, die Funktion f ist auch bewußt cachefreundlich gewählt. Aber sie ist auch ein echter Kurzrechner im Gegensatz Zu Deiner.