Moduo-Operation dauert zu lange

Hallo zusammen,

kann es sein, dass die modulo-Operation ein vergleichweise aufwendiger CPU-Befehl ist? Hier eine kurze Schilderung meiner Erfahrung:
In meinem Programm verwende ich einige HASH-Tabellen. Die Hash-funktion sieht dabei so aus (es werden Tabellen mit der Größe 2^k verwendet):

unsigned int hashPosition = unsigned int(key & (HASHSIZE-1));

Dies funktioniert auch sehr gut. Anzumerken ist vllt., dass die Variable key eine 64-Bit Variable (unsigned __int64) ist.

Ersetze ich dann aber die bitweise UND-Operation durch die Modulo-Operation, verdreifacht sich die Laufzeit des Programms, wenn viele Hash-Zugriffe nötig sind.

unsigned int hashPosition = (key % (unsigned int)HASHSIZE);

Eigentlich hätte ich erwartet, dass der Compiler dies optimieren kann. Dies scheint aber nicht der Fall zu sein. Oder habe ich einen Fehler in der Berechnung drin. Ich habe auch extra darauf geachtet dass jeweils unsigned Variablen verwendet werden.

Für Meinungen und Anregungen wäre ich sher dankbar...

Franz

icarus2

Im Verlauf diess Threads hats gerade vor kurzem eine solche Diskussion gegeben: http://www.c-plusplus.net/forum/294476

Offenbar kann es wirklich sein, dass so etwas nicht optimiert wird.

Bashar

Das Problem aus dem anderen Thread kann es eigentlich nicht sein, weil hier nur unsigned-Werte beteiligt sind, und dort gilt generell a % 2^k == a & (2^k-1) [^ ist natürlich hoch, nicht xor].

Ist HASHSIZE wirklich konstant? Welchen Datentyp hat HASHSIZE? Mir kommt es komisch vor, dass du HASHSIZE nach unsigned int castest, aber nicht key.

BTW C++-Fragen gehören IMHO ins C++-Forum.

SeppJ

Bashar schrieb:

Das Problem aus dem anderen Thread kann es eigentlich nicht sein, weil hier nur unsigned-Werte beteiligt sind, und dort gilt generell a % 2^k == a & (2^k-1) [^ ist natürlich hoch, nicht xor].

In dem anderen Thread wurde aber auch festgestellt, dass nur so Wunderoptimierer wie der gcc das optimieren.

volkard

Modulo einer compilezeitkonstanten Zweierpotenz zu AND optimieren kann jeder.
Bashar ist auf dem richtigen Weg, denke ich. Franz muß nur noch antworten.

Naja, HASHSIZE habe ich mit #define festgelegt. Ich bin mir nicht sicher, ob mit define festgelegte Konstanten automatisch unsigned int sind.
Deshalb der cast davor.

Da key ja eine unsigned 64-Bit-Variable ist, ist ein cast zu unsigned int bei Verwendung einer Modulo-Operation meiner Meinung nach nicht zulässig (korrigiert mich, wenn ich falsch liege).
Daher habe ich das hier nicht gemacht.

Bashar

SeppJ schrieb:

In dem anderen Thread wurde aber auch festgestellt, dass nur so Wunderoptimierer wie der gcc das optimieren.

Nein, das betraf (x%2 + 2)%2 ==> x&1 für x vom Typ signed int.

volkard

Klingt alles ok.
Meiner Erfahrung nach müßte der Compiler das optimieren.
Welcher Compiler und welches BS isses denn?

SeppJ

FranzMeier schrieb:

Naja, HASHSIZE habe ich mit #define festgelegt. Ich bin mir nicht sicher, ob mit define festgelegte Konstanten automatisch unsigned int sind.
Deshalb der cast davor.

Define ist bloß eine Textersetzung. Wenn du schreibst

#define foo 1
a = foo;

dann wird daraus a = 1; , also ein int-Literal. Schreibst du

#define foo 1U
a = foo;

dann wird daraus a = 1U; .

volkard schrieb:

Klingt alles ok.
Meiner Erfahrung nach müßte der Compiler das optimieren.
Welcher Compiler und welches BS isses denn?

Als Entwicklungsumgebung verwende ich den CodeGear C++-Builder 2009. Ich konnte jetzt auf die schnelle aber nicht herausfinden,
ob da ein bekannter Compiler anderer Unternehmen verwendet wird oder ob dies eine Eigenentwicklung ist (Ich vermut ein Borland-Compiler)

Betriebssystem: Windows 7 Buisiness 64-Bit

Bashar

FranzMeier schrieb:

Da key ja eine unsigned 64-Bit-Variable ist, ist ein cast zu unsigned int bei Verwendung einer Modulo-Operation meiner Meinung nach nicht zulässig (korrigiert mich, wenn ich falsch liege).

Das würde bewirken, dass die höherwertigen 32 Bits (ich geh mal davon aus, dass unsigned int ein 32-Bit-Wort ist) abgeschnitten werden. Arithmetisch ist das also ein "modulo 2^32". Da deine HASHSIZE auch eine Zweierpotenz ist, sollte das am Ergebnis nichts ändern.

Bashar schrieb:

FranzMeier schrieb:

Da key ja eine unsigned 64-Bit-Variable ist, ist ein cast zu unsigned int bei Verwendung einer Modulo-Operation meiner Meinung nach nicht zulässig (korrigiert mich, wenn ich falsch liege).

Das würde bewirken, dass die höherwertigen 32 Bits (ich geh mal davon aus, dass unsigned int ein 32-Bit-Wort ist) abgeschnitten werden. Arithmetisch ist das also ein "modulo 2^32". Da deine HASHSIZE auch eine Zweierpotenz ist, sollte das am Ergebnis nichts ändern.

Ja, stimmt, da hast Du recht...
Aber das wäre eine Optimierung von Hand. Normalerweise hätte der Compiler das erkennen müssen. Ich schau mir beizeiten vllt. mal den erzeugten Assembler-Code an...

Bashar

FranzMeier schrieb:

Aber das wäre eine Optimierung von Hand. Normalerweise hätte der Compiler das erkennen müssen.

Es ist auch nur eine Vermutung, dass der Compiler Schwierigkeiten bei der Optimierung von 64-Bit-Integern hat.

Wutz

Ein Compiler muss überhaupt nichts optimieren, schon gar nicht so, wie es der jeweilige Programmierer gern hätte oder es glaubt genau wissen zu müssen, dass genau so und nicht anders 'optimiert' werden muss.
Der Compiler muss auch überhaupt nichts anmahnen oder sonstwie auf irgendwas hinweisen, es sei denn, man verwendet compilereigene und somit nicht standardkonforme Erweiterungen, die der Compilerbauer entsprechend dokumentiert hat.
Nichtnullbeginnende Ziffernfolgen ohne Qualifizierer und '.' sind immer int und nicht unsigned int und werden dezimal interpretiert.

volkard

Wutz schrieb:

Ein Compiler muss überhaupt nichts optimieren,

Doch, denn anderenfalls benutze ich einen anderen Compiler, Du Quatschkopf.

Bashar

wutz: Ich interpretiere das als Maßnahme zur Reviermarkierung.

volkard

FranzMeier schrieb:

Naja, HASHSIZE habe ich mit #define festgelegt.

Ich bin zu 99% sicher, daß Du den Fehler nicht gemacht hast, aber nur zur Sicherheit: HASHSIZE ist nur eine Zahl wie 1024 und kein Rechenausdruck wie 1<<10 oder hat sichernde Schutzklammern drum wie (1<<10)?

volkard schrieb:

Ich bin zu 99% sicher, daß Du den Fehler nicht gemacht hast, aber nur zur Sicherheit: HASHSIZE ist nur eine Zahl wie 1024 und kein Rechenausdruck wie 1<<10 oder hat sichernde Schutzklammern drum wie (1<<10)?

HASHSIZE ist eine einfache Zahl, also 2^22 = 4194304

#define HASHSIZE 4194304

Und die Compilereinstellungen passen sicher auch? Nicht, dass die irgendwie untergegangen sind?