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

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.