Verbessrungsvorschläge zu meiner ip-to-contry funktion gesucht

Hallo,

ich habe mir eine ip-to-country funktion geschrieben. Alles funktioniert bereits wunderbar. Da ich jedoch keine Mathegenie bin, ist meine Auswertefunktion geschwindigkeitstechnisch nicht sonderlich optimal (vermute ich mal?). Zur Bestimmung des richtigen Wertes in einer Struktur mit 101312 Werten, setze ich ein Verfahren ein das genau in der Mitte der Struktur prüft ob der Wert oberhalb oder unterhalb der Mitte liegt, vom Rest prüfe ich wieder ob der Wert unterhalb oder oberhalb liegt und so weiter. Ich poste hier mal meinen Code und würde mich freuen wenn jemand Verbesseungen daran vornehmen könnte.

Ich benutze folgende Struktur die bereits mit Werten gefüllt ist:

#define MAX_GEOIPLINES	101312		//die Anzahl Zeilen/Datensätze in der Geoipliste

typedef struct _geoip{
	short		code;
	u_int		ip;
}geoip_t;

extern 	geoip_t		geoip[MAX_GEOIPLINES];

diese Struktur sieht gefüllt so aus

0,0		//Zeile 1, Anfang des Wertebereichs
33996351,77	//ip range: 0 bis 33996351, Land: 77
68257567,225	//ip range: 3399635 bis 68257567, Land: 225
68257599,38	//ip range: 68257568 bis 68257599, Land: 38
68259583,225	//ip range: 68257600 bis 68259583, Land: 225
:
:
3741057023,119	//analog wie oben
4294967295,0	//Zeile 101312, Ende des Wertebereichs (2^32 -1)

mit dieser Funktion nehme ich die Auswertung vor:

short GetCountry(u_int prove){

	int		position, start=0, end= MAX_GEOIPLINES, quit = 0, lastposition = 0;
	short		back = -1;

	position = (end - start)/2;
	do{
		if(prove == geoip[position].ip){
			back = geoip[position].code;
		}else if(prove > geoip[position].ip){
			if(prove <= geoip[position+1].ip){
				back = geoip[position+1].code;
			}else{
				start = position;
				position += (end - start)/2;
				if(position == lastposition){
					start++;
					position++;
				}
			}

		}else if(prove < geoip[position].ip){
			if(prove > geoip[position-1].ip){
				back = geoip[position].code;
			}else{
				end = position;
				position -= (end - start)/2;
				if(position == lastposition){
					start--;
					position--;
				}
			}
		}
		quit++;
		lastposition = position;
	}while((quit != 24) && (back == -1));			//Abbruch wenn gefunden oder wenn Schleife 32x durchlaufen
	return back;
}

Ich bin sicher da ist noch was rauszuholen bei dem Code. Oder auch ein alternativer Verfahren, ist mir recht. Ich kenn nur keins

Hi !
Alternative:
Mach dir eine C-Schnittstelle zu einer Datenbank.
Zu deinem Thema gibt es fertige csv Dateien zum runterladen, die kannst du in die DB importieren.
http://www.maxmind.com/app/csv

Alternative schrieb:

Hi !
Alternative:
Mach dir eine C-Schnittstelle zu einer Datenbank.
Zu deinem Thema gibt es fertige csv Dateien zum runterladen, die kannst du in die DB importieren.
http://www.maxmind.com/app/csv

Ich verwende eine modifizierte maxmind datenbank für die Struktur. Die Auswertung möchte ich gerne in meinem Programm vornehmen und nicht durch eine externe dll. Da ich auf einen Schlag bis zu 40000 IP Adressen den entsprechenden Ländern zuordne, kann ich mir vorstellen daß dies durch eine externe dll erheblich länger dauert. Mir geht es eigentlich mehr darum ob/wie mein Code verbessert werden könnte.

wenn du es schneller haben wills musst du std::map aus C++ nachprogrammieren.

doch nicht

ip-to-country schrieb:

Mir geht es eigentlich mehr darum ob/wie mein Code verbessert werden könnte.

Ja, man kann. Wie sieht es mit einer Optimierungsprovision aus ?
1€/ms ?

Alternative schrieb:

Ja, man kann. Wie sieht es mit einer Optimierungsprovision aus ?
1€/ms ?

Bruuuuuuder !!!
Das ist ja Wucher !
Ich machs für die Hälfte
40000 IPs stinken förmlich nach kommerzieller Anwendung, da kann Bruder ip-to-country ruhig was springen lassen^^

Badestrand

Einen besseren Algorithmus kenne ich nicht, aber ein paar Kleinigkeiten:

if(prove == geoip[position].ip)
{
    back = geoip[position].code;
}

Diese Abfrage würde ich hinter die beiden anderen (>,<) stellen, schließlich wird das die Bedingung sein, die am seltensten erfüllt wird. Die Abfrage kannst du dann übrigens auch gleich weg machen und dich auf ein "else" beschränken, mehr als diese drei Möglichkeiten gibt's schließlich nicht..

Und du kannst den Wert auch direkt zurückgeben, statt "back" zu setzen und den Code zur Abbruchbedingung durchlaufen zu lassen.

typedef struct _geoip{
    short        code;
    u_int        ip;
}geoip_t;

Hier könntest du evtl (musst du mal ausprobieren) mit Alignment noch etwas rausholen:

typedef struct _geoip{
    u_int        ip;   // ip als erstes, hier ist schließlich die aligned'te Adresse und auf ip wird öfter zugegriffen als auf code
    short        code;
    short        dummy1; // Mit den dreien wird's auf 128 Bit aligned
    u_int        dummy2;
    u_int        dummy3;
}geoip_t;

Es kann ja nochmal jemand seinen Senf dazugeben, gerade beim Alignment bin ich definitiv nicht auf dem Stand der Zeit.

Alternative schrieb:

Ja, man kann. Wie sieht es mit einer Optimierungsprovision aus ?
1€/ms ?

Bin selbst armer Schüler und kann mir so teure Leute nicht leisten, trotzdem Danke für das Angebot.

@Badestrand hast natürich Recht mit der Reihenfolge ist schon noch was rauszuholen. Das mit dem Alignment von dem du redest, damit kann ich gar nichts anfangen, weil ich nicht weiss was es ist, möglicherweise hats du ein kurze Erklärung für mich parat.

Im übrigen hab ich gerade mal eine Zeitmessung durchgeführt. Ohne ip-to-Country Prüfung ist mein Code zu Verarbeitung von 16500 IP Adressen 134ms schneller als mit ip-to-Country Prüfung, also ca. 8µs pro Durchlauf damit kann ich leben.

Badestrand

ip-to-country schrieb:

@Badestrand hast natürich Recht mit der Reihenfolge ist schon noch was rauszuholen. Das mit dem Alignment von dem du redest, damit kann ich gar nichts anfangen, weil ich nicht weiss was es ist, möglicherweise hats du ein kurze Erklärung für mich parat.

Klaro! Also soweit ich weiß, kann der Prozessor ein wenig schneller auf Daten zugreifen, die auf geraden Speicheradressen liegen. "Gerade" wäre eigentlich alles, was durch 4 teilbar ist. Noch "gerader" sind Adressen, die z.B. durch 32 oder 64 teilbar sind.

Im Allgemeinen werden structs z.B. vom Compiler automatisch an solchen Grenzen ausgerichtet. Für die Größe deine Struktur "geoip_t" spuckt mir mein Compiler "8" aus, obwohl die Struktur an sich ja nur 6 Bytes groß ist. Wenn man mehrere dieser 6-Byte-Strukturen hintereinander hat, hat ja spätestens die zweite Struktur eine ungerade Anfangsadresse; also verschwendet der Compiler pro Struktur 2 Bytes und alle Anfangsadressen sind durch 8 teilbar.
In der jetzigen Form ist die Adresse des "ip"-Feldes der Struktur immer "Anfangsadresse_der_Struktur+4" (um code zu überspringen, code wird bei mir auf 4 Bytes aligned), also nicht mehr durch 8 teilbar. Auf "ip" wird aber öfter zugegriffen als auf code, deshalb sollte das auf die "geradere" Adresse. Wenn man die Struktur noch mit Dummy-Variablen auffüllt, bekommt das "ip"-Feld jeweils "noch geraderere" Adresssen. Soweit der Sinn hinter dem Ganzen

#define MAX_GEOIPLINES    101312 
//#pragma pack(1)
typedef struct
{
    int 	range;
	// short country
    unsigned country;
}GeoIp;
//#pragma pack()
GeoIp  geoip[MAX_GEOIPLINES];

GeoIp* GetCountry( int code )
{
	int a = 1, b = MAX_GEOIPLINES -1, i = 0;

	while( a <= b )
	{
		i = ( a + b )/2;
		if ( code > geoip[i].range )
			a = i+1;
		else if ( code < ( geoip[i-1].range + 1 ) )
			b = i-1;
		else
			return  &geoip[i];
	}
	return NULL;
}

Wichtig, initialisiere:

geoip[0].range = -1;

damit auch das erste Element geoip[1] gefunden wird.

Das Alignment betreffend:
Welchen Wert spuckt bei dir ein sizeof(struct geoip_t) aus ?
Vermutlich 4. Demnach was ich gelesen habe ist eine Aurichtung auf 4-Byte-Grenzen Standard.
Damit wird ein Auffüllen mit Dummys wohl nichts bringen, wäre eventuell auszumessen.
Nimm gleich zwei int, dann ist die 4-Byte-Geschichte ok.

Moin,

erstmal danke für die Hinweise und Tips. Also sizeof(struct geoip_t) ist bei mir = 8. Danke Big Brother für den Bsp Code den werde ich heute mittag gleich mal ausprobieren. Zu deiner Anmerkung mit geoip[0].range = -1 in meiner Struktur ist geoip[0].range = 0 und auch als Dummy gedacht, muss ich das wirklich ändern?

ip-to-country schrieb:

Moin,
erstmal danke für die Hinweise und Tips. Also sizeof(struct geoip_t) ist bei mir = 8.

Ich meinte eigentlich in beiden Fällen 8, weiss auch nicht wieso ich 4 schrieb.

ip-to-country schrieb:

Zu deiner Anmerkung mit geoip[0].range = -1 in meiner Struktur ist geoip[0].range = 0 und auch als Dummy gedacht, muss ich das wirklich ändern?

Ja, bei einem Suchwert == 0 würde die Zeile
code < ( geoip[i-1].range + 1 )
dafür sorgen, das nix gefunden wird.

Naja, ne 0er Ip gibts glaub ich sowieso nicht.

ip-to-country schrieb:

Die Auswertung möchte ich gerne in meinem Programm vornehmen und nicht durch eine externe dll. Da ich auf einen Schlag bis zu 40000 IP Adressen den entsprechenden Ländern zuordne, kann ich mir vorstellen daß dies durch eine externe dll erheblich länger dauert. Mir geht es eigentlich mehr darum ob/wie mein Code verbessert werden könnte.

Es gibt die Möglichkeit des statischen linkens( ohne dll, SqlLight und Co.

Selbst wenn: sind die C-Routinen einer dll erstmal im Arbeitsspeicher gemappt, dürfte es keine Unterschiede bezüglich der Geschwindigkeit geben.

Big Brother schrieb:

Naja, ne 0er Ip gibts glaub ich sowieso nicht.

Jo hast recht gibts eh nicht, ausserdem kann ich menen u_init nicht auf einen negative Wert stellen (oder?). So ich lass jetzt gleich mal den Code durchlaufen. Gruß.

http://www.c-plusplus.net/forum/viewtopic-var-t-is-211783.html

@Big Brother danke noch mal für den verbesserten Algorithmus, der Code hat einen Geschwindigkeitsvorteil von 17% gebracht.