Discussion:
Noch ne Vergleichschleife
(zu alt für eine Antwort)
Rainer Weikusat
2016-12-28 22:22:37 UTC
Permalink
Das vergleicht untentschluesselte aber als gueltig bekannte
ISAKMP-Nachrichten. Ausser in 'seltenen Faellen' ist deren Laenge ohne
Rest durch 8 teilbar. 64-bit-Alignment ist seitens des
Speicherallokationscodes sichergestellt.

Ist das wenigstens einigermassen verstaendlich?

-----------
static int is_this_msg(vchar_t *msg, struct isakmp_seen *seen)
{
uint8_t *p_msg, *p_seen;
unsigned cur, last, x;

last = msg->l;
if (last != seen->msg->l) return 0;

p_msg = (void *)msg->v;
p_seen = (void *)seen->msg->v;
/* no point comparing the cookies (=> RFC2408, 3.1) */
cur = 16;
do {
if (*(uint64_t *)(p_msg + cur) != *(uint64_t *)(p_seen + cur))
return 0;

cur += 8;
} while (cur < last);

switch (x = last % 8) {
case 7:
case 6:
case 5:
case 4:
if (*(uint32_t *)(p_msg + cur) != *(uint32_t *)(p_seen + cur))
return 0;
if (x == 4) return 1;

cur += 4;
if (x == 5) goto cmp_last;

case 3:
case 2:
if (*(uint16_t *)(p_msg + cur) != *(uint16_t *)(p_seen + cur))
return 0;
if (!(x & 1)) return 1;

cur += 2;

case 1:
cmp_last:
if (p_msg[cur] != p_seen[cur]) return 0;
}

return 1;
}
Rainer Weikusat
2016-12-28 22:27:29 UTC
Permalink
Post by Rainer Weikusat
Das vergleicht untentschluesselte aber als gueltig bekannte
ISAKMP-Nachrichten. Ausser in 'seltenen Faellen' ist deren Laenge ohne
Rest durch 8 teilbar. 64-bit-Alignment ist seitens des
Speicherallokationscodes sichergestellt.
Ist das wenigstens einigermassen verstaendlich?
-----------
static int is_this_msg(vchar_t *msg, struct isakmp_seen *seen)
{
uint8_t *p_msg, *p_seen;
unsigned cur, last, x;
last = msg->l;
if (last != seen->msg->l) return 0;
p_msg = (void *)msg->v;
p_seen = (void *)seen->msg->v;
/* no point comparing the cookies (=> RFC2408, 3.1) */
cur = 16;
do {
if (*(uint64_t *)(p_msg + cur) != *(uint64_t *)(p_seen + cur))
return 0;
cur += 8;
} while (cur < last);
Die Bedingung ist falsch.
Peter J. Holzer
2016-12-29 15:37:39 UTC
Permalink
Post by Rainer Weikusat
Post by Rainer Weikusat
Das vergleicht untentschluesselte aber als gueltig bekannte
ISAKMP-Nachrichten. Ausser in 'seltenen Faellen' ist deren Laenge ohne
Rest durch 8 teilbar. 64-bit-Alignment ist seitens des
Speicherallokationscodes sichergestellt.
Ist das wenigstens einigermassen verstaendlich?
IMHO ja. Ich würde allerdings einen einfachen Aufruf von memcmp
verständlicher finden und bei einem Code-Review nach Benchmarks fragen.
Post by Rainer Weikusat
Post by Rainer Weikusat
-----------
static int is_this_msg(vchar_t *msg, struct isakmp_seen *seen)
{
uint8_t *p_msg, *p_seen;
unsigned cur, last, x;
last = msg->l;
if (last != seen->msg->l) return 0;
p_msg = (void *)msg->v;
p_seen = (void *)seen->msg->v;
/* no point comparing the cookies (=> RFC2408, 3.1) */
cur = 16;
do {
if (*(uint64_t *)(p_msg + cur) != *(uint64_t *)(p_seen + cur))
return 0;
cur += 8;
} while (cur < last);
Die Bedingung ist falsch.
Ja. Außerdem: Ist sichergestellt, dass last mindestens 24 ist? Ich hätte
da eher eine while-Schleife als eine do-Schleife verwendet.

hp
--
_ | Peter J. Holzer | Fluch der elektronischen Textverarbeitung:
|_|_) | | Man feilt solange an seinen Text um, bis
| | | ***@hjp.at | die Satzbestandteile des Satzes nicht mehr
__/ | http://www.hjp.at/ | zusammenpaßt. -- Ralph Babel
Rainer Weikusat
2016-12-29 23:03:47 UTC
Permalink
Post by Peter J. Holzer
Post by Rainer Weikusat
Post by Rainer Weikusat
Das vergleicht untentschluesselte aber als gueltig bekannte
ISAKMP-Nachrichten. Ausser in 'seltenen Faellen' ist deren Laenge ohne
Rest durch 8 teilbar. 64-bit-Alignment ist seitens des
Speicherallokationscodes sichergestellt.
Ist das wenigstens einigermassen verstaendlich?
IMHO ja. Ich würde allerdings einen einfachen Aufruf von memcmp
verständlicher finden und bei einem Code-Review nach Benchmarks fragen.
Das ist mit zweierlei Mass gemessen:

if (msg->l == seen->msg->l && memcmp(msg->v, seen->msg->v, msg->l) == 0)

kommt Dir deshalb verstaendlicher vor als

if (is_seen_msg(msg, seen))

weil Du Dir beim zweiten Mal den Code der Vergleichsfunktion ansiehst
und beim ersten Mal nicht.

Man koennte das natuerlich in eine Inline-Funktion einwickeln.

Ausserdem kann man 'memcmp' nicht benchmarken, weil seine
Implementierung nicht definiert ist. Es gibt hier auch noch andere
Effekte wie i-cache-Fussabdruck.

Spasseshalber habe ich das mal getan:

Fuer eine relative 'grosse' Testnachricht ist memcmp auf meinem
'Arbeitscomputer' ca 1.8mal schneller als [*]

int is_this_msg_0(uint8_t *p_msg, uint8_t *p_seen, unsigned last)
{
unsigned cur, x;

x = last & ~7;

/* no point comparing the cookies (=> RFC2408, 3.1) */
cur = 16;
do {
if (*(uint64_t *)(p_msg + cur) != *(uint64_t *)(p_seen + cur))
return 0;
cur += 8;
} while (cur < x);

while (__builtin_expect(x < last, 0)) {
if (p_msg[x] != p_seen[x]) return 0;
++x;
}

return 1;
}

Special-casing fuer die letzten 7 byte eliminiert weil "nicht der Muehe
wert" (wird in >87% der Faelle nicht benutzt werden). Absolut betraegt
dieser Unterschied gigantische 0.000000023s pro Aufruf. Damit kann ich
leben. Entscheidend ist, dass diese Funktion in Profilen aufgefallen
ist, und durch 8-byte-weises Vergleichen um ca 77% schneller wird.

[*] Allerdings koennte man ein 'Testfeld' benutzen, bei dem diese
memcmp-Implementierung zu einer byte-pro-byte Schleife degeneriert.
Andernfalls vergleich sie 16 byte auf einmal mit 4x unrolling was
natuerlich schneller ist.
Post by Peter J. Holzer
Post by Rainer Weikusat
Post by Rainer Weikusat
-----------
static int is_this_msg(vchar_t *msg, struct isakmp_seen *seen)
{
uint8_t *p_msg, *p_seen;
unsigned cur, last, x;
last = msg->l;
if (last != seen->msg->l) return 0;
p_msg = (void *)msg->v;
p_seen = (void *)seen->msg->v;
/* no point comparing the cookies (=> RFC2408, 3.1) */
cur = 16;
do {
if (*(uint64_t *)(p_msg + cur) != *(uint64_t *)(p_seen + cur))
return 0;
cur += 8;
} while (cur < last);
Die Bedingung ist falsch.
Ja. Außerdem: Ist sichergestellt, dass last mindestens 24 ist?
Die 'gesehene' Nachricht ist eine gueltige ISAKMP (IKE[v1])-Nachricht dh
sie beginnt mit einem 28-byte header. Weil die Laenge der anderen gleich
ist, "passt das".

Danke fuers ansehen und kommentieren.
Peter J. Holzer
2016-12-31 13:10:52 UTC
Permalink
Post by Rainer Weikusat
Post by Peter J. Holzer
Post by Rainer Weikusat
Das vergleicht untentschluesselte aber als gueltig bekannte
ISAKMP-Nachrichten. Ausser in 'seltenen Faellen' ist deren Laenge ohne
Rest durch 8 teilbar. 64-bit-Alignment ist seitens des
Speicherallokationscodes sichergestellt.
Ist das wenigstens einigermassen verstaendlich?
IMHO ja. Ich würde allerdings einen einfachen Aufruf von memcmp
verständlicher finden und bei einem Code-Review nach Benchmarks fragen.
if (msg->l == seen->msg->l && memcmp(msg->v, seen->msg->v, msg->l) == 0)
kommt Dir deshalb verstaendlicher vor als
if (is_seen_msg(msg, seen))
Kommt es mir nicht. Mir kommt is_seen_msg(msg, seen) wesentlich
verständlicher vor.
Post by Rainer Weikusat
weil Du Dir beim zweiten Mal den Code der Vergleichsfunktion ansiehst
und beim ersten Mal nicht.
Ich meinte die Vergleichsfunktion. Ca. 30 Zeilen der Vergleichsfunktion
sind eine geinlinete Version von memcmp, die auf 64-bit-Alignment
optimiert ist. Diese 30 Zeilen könnte man durch einen Aufruf von memcmp
ersetzen.

Die Variante mit memcmp fände ich leichter lesbar.

Dafür ist Deine Variante wahrscheinlich schneller.

Man muss dann abwägen, was wichtiger ist. Ich neige generell eher dazu,
Lesbarkeit zu bevorzugen, und ich habe gelernt, dass das Bauchgefühl bei
Performance-Optimierungen oft trügen kann. Daher würde ich prinzipiell,
wenn ein Kollege mit 30 Zeilen Code statt 1 Zeile Code daherkommt, und
behauptet, das sei schneller, fragen, ob er das gemessen hat, wenn ja,
wie, und wieviel schneller es ist.

Wenn sich dann herausstellt, dass der Performance-Gewinn nicht-trivial
ist, kann ich mit etwas längerem Code, der schön in einer Funktion
gekapselt ist, so wie hier, gut leben.
Post by Rainer Weikusat
Man koennte das natuerlich in eine Inline-Funktion einwickeln.
Ausserdem kann man 'memcmp' nicht benchmarken, weil seine
Implementierung nicht definiert ist. Es gibt hier auch noch andere
Effekte wie i-cache-Fussabdruck.
Man kann sowieso immer nur eine Implementierung und bestimmte Daten
benchmarken. Darin unterscheidet sich Dein Code von memcmp nur graduell,
aber nicht prinzipiell.
Post by Rainer Weikusat
Fuer eine relative 'grosse' Testnachricht ist memcmp auf meinem
'Arbeitscomputer' ca 1.8mal schneller als [*]
Das würde für memcmp sprechen (wenn die "relativ 'großen'
Testnachrichten" typisch sind).
[...]
Post by Rainer Weikusat
Entscheidend ist, dass diese Funktion in Profilen aufgefallen
ist, und durch 8-byte-weises Vergleichen um ca 77% schneller wird.
Ja, da zahlt sich eine Optimierung aus.

hp
--
_ | Peter J. Holzer | Fluch der elektronischen Textverarbeitung:
|_|_) | | Man feilt solange an seinen Text um, bis
| | | ***@hjp.at | die Satzbestandteile des Satzes nicht mehr
__/ | http://www.hjp.at/ | zusammenpaßt. -- Ralph Babel
Rainer Weikusat
2017-01-01 19:43:09 UTC
Permalink
[...]
Post by Peter J. Holzer
Kommt es mir nicht. Mir kommt is_seen_msg(msg, seen) wesentlich
verständlicher vor.
Post by Rainer Weikusat
weil Du Dir beim zweiten Mal den Code der Vergleichsfunktion ansiehst
und beim ersten Mal nicht.
Ich meinte die Vergleichsfunktion. Ca. 30 Zeilen der Vergleichsfunktion
sind eine geinlinete Version von memcmp, die auf 64-bit-Alignment
optimiert ist. Diese 30 Zeilen könnte man durch einen Aufruf von memcmp
ersetzen.
[...]
Post by Peter J. Holzer
Man kann sowieso immer nur eine Implementierung und bestimmte Daten
benchmarken. Darin unterscheidet sich Dein Code von memcmp nur graduell,
aber nicht prinzipiell.
Post by Rainer Weikusat
Fuer eine relative 'grosse' Testnachricht ist memcmp auf meinem
'Arbeitscomputer' ca 1.8mal schneller als [*]
Das würde für memcmp sprechen (wenn die "relativ 'großen'
Testnachrichten" typisch sind).
"Begrenzt". Diese Routine soll nicht byte pro byte vergleichen weil das
extrem viel mehr Rechenzeit braucht, als wuenschenswert (empirisch
ermittelte Tatsache). Jetzt ist memcmp aber eine 'schwarze Kiste' wo
oben Daten hineinfallen und unten ein Resultat heraus. Dh man kann das
eigentlich nur verwenden, wenn Ausfuehrungsgeschwindigkeit keine Rolle
spielt, denn die Implementierung koennte

https://opensource.apple.com/source/Libc/Libc-391.2.3/string/FreeBSD/memcmp.c.auto.html

sein (und das ist - getreu des Ursprungs - eine schlechte C
Implementierung) oder sonst irgendwas.

Ebenfalls getreu des Ursprungs ist glibc mempmp natuerlich
'handoptimierter' Maschinencode. Der macht ca halb so viele Vergleiche
wie die C-Implementierung, die ich gepostet hatte, ist aber deutlich
langsamer als 'doppelt so schnell'. Tatsaechlich laesst sich der
Laufzeitunterschied durch 4x unrolling via Duff's Device bei
Beibehaltung der uint64_t-Vergleiche auf ca 1/3 verringern. In diesem
Code ist also irgendwo der Wurm drin.

Hinzu kommt was die 'Maschinencode-Handoptimierer' generelll uebersehen,
naemlich, Code materialisiert sich nicht auf magische Weise
ausfuehrungsfertig in einer CPU sondern das sind zunaechst mal Daten,
die aus dem Hauptspeicher geladen werden muessen. Und die 'optimierte'
glibc memcmp-Routine ist erheblich groesser als 83% der Nachrichten, die
verglichen werden sollen.
Thomas Jahns
2017-01-02 08:52:48 UTC
Permalink
Post by Rainer Weikusat
Das vergleicht untentschluesselte aber als gueltig bekannte
ISAKMP-Nachrichten. Ausser in 'seltenen Faellen' ist deren Laenge ohne
Rest durch 8 teilbar. 64-bit-Alignment ist seitens des
Speicherallokationscodes sichergestellt.
Ist das wenigstens einigermassen verstaendlich?
-----------
static int is_this_msg(vchar_t *msg, struct isakmp_seen *seen)
{
uint8_t *p_msg, *p_seen;
unsigned cur, last, x;
last = msg->l;
if (last != seen->msg->l) return 0;
p_msg = (void *)msg->v;
p_seen = (void *)seen->msg->v;
/* no point comparing the cookies (=> RFC2408, 3.1) */
cur = 16;
do {
if (*(uint64_t *)(p_msg + cur) != *(uint64_t *)(p_seen + cur))
return 0;
cur += 8;
} while (cur < last);
Gibt es einen Grund, das so vektorisierungsunfreundlich zu schreiben? Die
64-bit-Register zu verwenden ist ja schon gut, aber mit AVX2, Neon oder VMX
(oder wie IBM ihre Vektor-Extension gerade nennen) sollte noch mehr gehen (wenn
die Nachrichtenlänge hinreichend groß ist).

Thomas
Rainer Weikusat
2017-01-02 17:02:33 UTC
Permalink
Post by Thomas Jahns
Post by Rainer Weikusat
Das vergleicht untentschluesselte aber als gueltig bekannte
ISAKMP-Nachrichten. Ausser in 'seltenen Faellen' ist deren Laenge ohne
Rest durch 8 teilbar. 64-bit-Alignment ist seitens des
Speicherallokationscodes sichergestellt.
Ist das wenigstens einigermassen verstaendlich?
-----------
static int is_this_msg(vchar_t *msg, struct isakmp_seen *seen)
{
uint8_t *p_msg, *p_seen;
unsigned cur, last, x;
last = msg->l;
if (last != seen->msg->l) return 0;
p_msg = (void *)msg->v;
p_seen = (void *)seen->msg->v;
/* no point comparing the cookies (=> RFC2408, 3.1) */
cur = 16;
do {
if (*(uint64_t *)(p_msg + cur) != *(uint64_t *)(p_seen + cur))
return 0;
cur += 8;
} while (cur < last);
Gibt es einen Grund, das so vektorisierungsunfreundlich zu schreiben?
Insofern sich das feststellen laesst, ist dass per se nicht
vektorisierbar (unbekannte Zahl von Iterationen, nicht unabhaengig
voneinander).

Ein weiterer guter Grund waere: Wildes rumgehacke um "handoptmierten
gcc-code" zu produzieren (der hoffentlich irgendwelche features
aktiviert, die zu dokumentieren niemand fuer Wert hielt) ist
"handoptimierter Maschinencode" in gruen. Selbiges is genau dann
gerechtfertigt, wenn keine andere Moeglichkeit existiert.

Loading...