011
29.07.2005, 09:16 Uhr
virtual
Sexiest Bit alive
(Operator)
|
Mich hat der Thread angeregt, mal nahzudenken, die man memcmp "verschnellern" kann.
Hier das Ergebnis:
| C++: |
int fmemcmp(const void* p1, const void* p2, size_t n) {
const signed char* a = (const signed char*)p1;
const signed char* b = (const signed char*)p2;
if (a==b) {
return 0;
}
else if ((a-b)%sizeof(int)) {
return memcmp(a,b,n);
}
else {
const signed char* ea = a+n;
while(((long)a)%sizeof(int)) {
int res = *a++ - *b++;
if (res) return res;
}
while (ea-a>=sizeof(int)) {
if (*(int*)a!=*(int*)b) {
return *(int*)a>*(int*)b? 1:-1;
}
a += sizeof(int);
b += sizeof(int);
}
while (ea!=a) {
int res = *a++ - *b++;
if (res) return res;
}
}
return 0;
}
|
Ein normales memcmp wird normalerweise byteweise vergleichen. Diese Routine probiert einen möglichst großen Bereich int weise (bei mir: 4 Byte) zu vergleichen. Dabei sollten die Anfangsadressen der zu vergleichenden Speicherbereiche durch sizeof(int) teilbar sein: Sind sie es nicht, kann es je nach Prozessor zu geschwindigkeitseinbußen kommen. ( in diesem Fall switcht die Routine über zum normalen memcmp, ist also nach wie vor universell einsetzbar.
Optimiert ist das Ganze für grosse Speicherblöcke, dh ich erwarte eigentlich Nachteile für kleine Speicherbereiche, weil sich da der Overhead von den ganzen if Abfragen bemerkbar machen dürfte. Getestet habe ich das mit 40000 Vergleiche von zwei Inhaltsgleichen Arrays so um die 1MB Größe, mit folgenden Programm (stopwatch ist eine kleine Klasse zur Zeitmessung, kann ich bei Bedarf schicken):
| C++: |
int main() {
char a[1000004];
char b[1000004];
memcpy(a, b, sizeof(a));
stopwatch stdsw;
stopwatch fastsw;
for(int i=0; i<10000; ++i) {
for(int j=0; j<4; ++j) {
stdsw.start();
memcmp(a+j, b+j, 1000000-j);
stdsw.stop();
fastsw.start();
fmemcmp(a+j, b+j, 1000000-j);
fastsw.stop();
}
}
std::cout<<"Standard: "<<stdsw<<std::endl;
std::cout<<"Fast: "<<fastsw<<std::endl;
}
|
Die ergebnisse sind:
| Code: |
Standard: 290.698460
Fast: 206.034660
|
Dh nach meiner Lesart kommt meine Version mit 70% der Rechenzeit des normalen memcpy aus. Ich halte das nicht für die ultimative Lösung, zumal ich - wie gesagt - meine, daß die fmemcmp Funktion mit abnehmender Arraylänge möglicherweise Langsamer als das memcmp arbeitet.
Ich wollte ao eigentlich nur beweisen, daß ich zumindestens probiere, früh aufzustehen. 
--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21) |
