Gruppe 104: Claus-Dieter Volko, Matthias Wagner, Stefan Nastic
Die Programme wurden folgendermaßen erzeugt und getestet:
gcc -O spXX.c
papiex -e PAPI_TOT_CYC -e PAPI_TOT_INS -e PAPI_BR_MSP -e PAPI_FP_OPS a.out <input-bench-littleendian >/dev/null
Das Ursprungsprogramm.
PAPI_TOT_CYC ................................. 1.61048e+08
PAPI_TOT_INS ................................. 2.43945e+08
PAPI_BR_MSP .................................. 1.71534e+06
PAPI_FP_OPS .................................. 501
Zuerst wird die main-Funktion verbessert. Statt eines Arrayindex i wird nun mit einem Pointer gearbeitet. Dadurch kann auch die Variable start effizienter berechnet werden. Der zweite Parameter der Funktion optimize_rewrite wird durch eine Zählvariable ninsts ersetzt, wodurch wieder einige Rechenoperationen entfallen.
Vergleichen der Dateien sp01.c und sp02.c
***** sp01.c
PrimNum data [MAX_INPUT_SIZE];
PrimNum *start = data;
size_t input_size;
int i;
***** sp02.c
PrimNum data [MAX_INPUT_SIZE];
PrimNum *start;
size_t input_size;
PrimNum *i;
int ninsts;
*****
***** sp01.c
input_size = fread (data, sizeof (PrimNum), MAX_INPUT_SIZE, stdin);
for (i = 0; i < input_size; i++)
if (data [i] == -1)
{
optimize_rewrite (start, data + i - start);
start = data + i + 1;
}
***** sp02.c
input_size = fread (data, sizeof (PrimNum), MAX_INPUT_SIZE, stdin);
for (i = start = data, ninsts = 0; input_size; input_size--, i++, ninsts++)
if (*i == -1)
{
optimize_rewrite (start, ninsts);
start = i;
start++;
ninsts = -1;
}
*****
PAPI_TOT_CYC ................................. 1.53302e+08
PAPI_TOT_INS ................................. 2.43783e+08
PAPI_BR_MSP .................................. 1.38008e+06
PAPI_FP_OPS .................................. 511
-> Verbesserung, daher: Änderungen beibehalten
Die Funktionen optimize_rewrite und prepare_super_table werden in die Funktion main eingebaut, wodurch die Funktionsaufrufe entfallen; vor allem wegen der zahlreichen Aufrufe von optimize_rewrite dürfte dies einiges bringen.
PAPI_TOT_CYC ................................. 1.49929e+08
PAPI_TOT_INS ................................. 2.42726e+08
PAPI_BR_MSP .................................. 1.14848e+06
PAPI_FP_OPS .................................. 524
-> Verbesserung, daher: Änderungen beibehalten
Die Funktion is_relocateable wird in die Funktion main integriert.
PAPI_TOT_CYC ................................. 1.49952e+08
PAPI_TOT_INS ................................. 2.36096e+08
PAPI_BR_MSP .................................. 1.22888e+06
PAPI_FP_OPS .................................. 488
-> (kleine) Verbesserung, daher: Änderungen beibehalten
Anstatt eine Variable maxstates zu definieren, deren Wert sich im Lauf des Programms nicht ändert, die aber Speicherplatz belegt, wird nun ein Makro maxstates definiert.
Vergleichen der Dateien sp04.c und SP05.C
***** sp04.c
static int static_super_number = 10000; /* number of ss used if available */
#define MAX_STATE 9 /* maximum number of states */
static int maxstates = MAX_STATE; /* number of states for stack caching */
***** SP05.C
#define static_super_number 10000 /* number of ss used if available */
#define MAX_STATE 9 /* maximum number of states */
#define maxstates MAX_STATE /* number of states for stack caching */
*****
PAPI_TOT_CYC ................................. 1.49184e+08
PAPI_TOT_INS ................................. 2.35025e+08
PAPI_BR_MSP .................................. 1.23168e+06
PAPI_FP_OPS .................................. 488
-> (kleine) Verbesserung, daher: Änderungen beibehalten
In der Funktion main wurde an zwei verschiedenen Stellen die Summe super2 + c->offset berechnet. Um eine Berechnung einzusparen, wird dieser Wert nun in einer Variable temp zwischengespeichert.
Vergleichen der Dateien sp05.c und SP06.C
***** sp05.c
{
int hash = hash_super (super2 + c->offset, c->length);
struct super_table_entry **p = &super_table [hash];
***** SP06.C
{
int temp = super2 + c->offset;
int hash = hash_super (temp, c->length);
struct super_table_entry **p = &super_table [hash];
*****
***** sp05.c
e->next = *p;
e->start = super2 + c->offset;
e->length = c->length;
***** SP06.C
e->next = *p;
e->start = temp;
e->length = c->length;
*****
PAPI_TOT_CYC ................................. 1.48652e+08
PAPI_TOT_INS ................................. 2.36025e+08
PAPI_BR_MSP .................................. 1.14927e+06
PAPI_FP_OPS .................................. 486
-> Verbesserung, daher: Änderungen beibehalten
In einer der Schleifen werden zwei Vergleiche mit der Variablen c->length durchgeführt. Nun ist es aber so, dass max_super anfangs mit 2 initialisiert und im weiteren Lauf des Programms eventuell erhöht, jedoch nie vermindert wird. Daher kann c->length nur dann größer als max_super sein, wenn c->length auch größer oder gleich 2 ist. Aus diesem Grund kann man die beiden if-Abfragen ineinander verschachteln. Ist die erste Abfrage negativ, so wird die zweite Abfrage nun nicht mehr ausgeführt.
Vergleichen der Dateien sp06.c und SP07.C
***** sp06.c
}
if (c->length > max_super)
max_super = c->length;
if (c->length >= 2)
nsupers++;
}
***** SP07.C
}
if (c->length >= 2)
{
nsupers++;
if (c->length > max_super)
max_super = c->length;
}
}
*****
PAPI_TOT_CYC ................................. 1.48367e+08
PAPI_TOT_INS ................................. 2.36023e+08
PAPI_BR_MSP .................................. 1.14368e+06
PAPI_FP_OPS .................................. 486
-> (kleine) Verbesserung, daher: Änderungen beibehalten
Wie bei sp06.c wurde die zweimalige Berechnung derselben Summe beseitigt, indem sie in der Variablen temp zwischengespeichert wird.
Vergleichen der Dateien sp07.c und SP08.C
***** sp07.c
{
struct super_state **ss_listp = lookup_super (super2 + c->offset, c->length);
struct super_state *ss = malloc (sizeof (struct super_state));
***** SP08.C
{
int temp = super2 + c->offset;
struct super_state **ss_listp = lookup_super (temp, c->length);
struct super_state *ss = malloc (sizeof (struct super_state));
*****
***** sp07.c
{
int temp = super2 + c->offset;
int hash = hash_super (temp, c->length);
***** SP08.C
{
int hash = hash_super (temp, c->length);
*****
PAPI_TOT_CYC ................................. 1.4804e+08
PAPI_TOT_INS ................................. 2.36025e+08
PAPI_BR_MSP .................................. 1.17629e+06
PAPI_FP_OPS .................................. 520
-> (kleine) Verbesserung, daher: Änderungen beibehalten
Das Programm enthielt bisher die folgende if-Abfrage:
if ((c->length < 2 || nsupers < static_super_number) && c->state_in < maxstates && c->state_out < maxstates)
Im Inneren der if-Schleife befand sich dann eine Abfrage, ob c->length >= 2. Wenn eine der beiden Eintrittsbedingungen in die äußere if-Schleife, nämlich c->length < 2, erfüllt ist, so erübrigt sich die innere if-Abfrage. Diese Optimierung wurde umgesetzt, indem der Code
if ((c->length < 2 || nsupers < static_super_number) && c->state_in < maxstates && c->state_out < maxstates)
{
INNERFUNC01
if (c->length >= 2)
{
nsupers++;
if (c->length > max_super)
max_super = c->length;
}
}
durch
if (c->length < 2)
{
INNERFUNC01
}
else if (nsupers < static_super_number)
{
INNERFUNC01
/* c->length >= 2 */
nsupers++;
if (c->length > max_super)
max_super = c->length;
}
ersetzt wurde.
PAPI_TOT_CYC ................................. 1.48252e+08
PAPI_TOT_INS ................................. 2.36088e+08
PAPI_BR_MSP .................................. 1.17237e+06
PAPI_FP_OPS .................................. 513
-> statistisch im Mittel eine geringfügige Verschlechterung der Zyklenzahl, theoretisch dürfte diese Veränderung aber eine geringfügige Verbesserung bewirken, daher: Änderungen beibehalten
Die Funktion init_waypoints wird in die Hauptfunktion eingebaut.
PAPI_TOT_CYC ................................. 1.47626e+08
PAPI_TOT_INS ................................. 2.36331e+08
PAPI_BR_MSP .................................. 1.08e+06
PAPI_FP_OPS .................................. 489
-> Verbesserung, daher: Änderungen beibehalten
Auf Intel-Prozessoren ist es billiger, wenn man eine Schleife solange laufen lässt, bis der Schleifenzähler den Wert Null hat, als wenn man einen anderen Wert als Abbruchbedingung nimmt. Dies wird nun ausgenützt.
Vergleichen der Dateien sp10.c und SP11.C
***** sp10.c
int k;
for (k = maxstates - 1; k; k--)
***** SP11.C
int k;
int l;
for (k = maxstates - 1; k; k--)
*****
***** sp10.c
transitions (inst [ninsts], trans [ninsts]);
for (i = ninsts - 1; i >= 0; i--)
{
for (k = maxstates - 1; k; k--)
***** SP11.C
transitions (inst [ninsts], trans [ninsts]);
for (l = ninsts; l; l--)
{
i = l - 1;
for (k = maxstates - 1; k; k--)
*****
PAPI_TOT_CYC ................................. 1.46761e+08
PAPI_TOT_INS ................................. 2.36585e+08
PAPI_BR_MSP .................................. 1.09991e+06
PAPI_FP_OPS .................................. 492
-> Verbesserung, daher: Änderungen beibehalten
In einer for-Schleife gilt als Abbruchbedingung:
j <= max_super && i + j <= ninsts
j ist der Schleifenzähler dieser Schleife. i ist der Schleifenzähler einer äußeren Schleife und wird im Inneren der inneren Schleife nicht verändert. Daher steht der Wert von ninsts - i schon vor Beginn der inneren Schleife fest. Es ergibt sich daher die Möglichkeit, vor der inneren Schleife einen Wert loop_until zu berechnen:
loop_until = ninsts - i < max_super ? ninsts - i : max_super;
Als Abbruchbedingung kann dann j <= loop_until genommen werden. Das könnte vorteilhaft sein, wenn ninsts - i viel größer als max_super ist, weil dann bei jedem Durchlauf mit j > max_super ein Vergleich entfällt.
Vergleichen der Dateien sp11.c und SP12.C
***** sp11.c
{
i = l - 1;
for (k = maxstates - 1; k; k--)
***** SP12.C
{
int loop_until;
i = l - 1;
loop_until = ninsts - i < max_super ? ninsts - i : max_super;
for (k = maxstates - 1; k; k--)
*****
***** sp11.c
inst [i] [0].cost = INF_COST;
for (j = 1; j <= max_super && i + j <= ninsts; j++)
{
***** SP12.C
inst [i] [0].cost = INF_COST;
for (j = 1; j <= loop_until; j++)
{
*****
PAPI_TOT_CYC ................................. 1.49749e+08
PAPI_TOT_INS ................................. 2.3646e+08
PAPI_BR_MSP .................................. 1.14813e+06
PAPI_FP_OPS .................................. 520
-> bringt bei den Testdaten eine recht deutliche Verschlechterung mit sich, daher: Änderungen verwerfen
Im Programm kommen viele assert-Anweisungen vor. Diese werden jedoch nicht benötigt. Sie dienen nur zum Debuggen. Falls das Programm fehlerfrei ist, können sie getrost entfernt werden. Wir probieren, ob dies zu einer Effizienzsteigerung führt.
PAPI_TOT_CYC ................................. 1.50988e+08
PAPI_TOT_INS ................................. 2.35271e+08
PAPI_BR_MSP .................................. 1.13472e+06
PAPI_FP_OPS .................................. 476
-> Verschlechterung, daher: Änderungen verwerfen
Da an einigen Stellen innerhalb derselben Schleife die Summe i + j verwendet wird, wird versucht, diese Summe in einer Variablen temp zwischenzuspeichern.
PAPI_TOT_CYC ................................. 1.46683e+08
PAPI_TOT_INS ................................. 2.36585e+08
PAPI_BR_MSP .................................. 1.09888e+06
PAPI_FP_OPS .................................. 489
-> (kleine) Verbesserung, daher: Änderungen beibehalten
In einer for-Schleife mit Zählvariablen i kommt die Zeile
fputs (prim_names [super2 [c->offset + i]], stdout);
vor; diese wird durch
fputs (prim_names [*ptr], stdout);
ersetzt, wobei ptr mit super2 + c->offset initialisiert und bei jedem Schleifendurchlauf um 1 erhöht wird. Außerdem wird nun von oben herab- statt hinaufgezählt.
Vergleichen der Dateien sp14.c und SP15.C
***** sp14.c
putchar ('_');
for (i = 0; i < c->length; i++)
{
fputs (prim_names [super2 [c->offset + i]], stdout);
putchar('_');
}
***** SP15.C
putchar ('_');
for (i = c->length; i; i--, ptr++)
{
fputs (prim_names [*ptr], stdout);
putchar ('_');
}
*****
PAPI_TOT_CYC ................................. 1.47858e+08
PAPI_TOT_INS ................................. 2.3697e+08
PAPI_BR_MSP .................................. 1.10483e+06
PAPI_FP_OPS .................................. 515
-> Verschlechterung, daher: Änderungen verwerfen
Die Funktion printinst wird durch ein Makro ersetzt, wodurch in main mehrere Funktionsaufrufe pro Schleifendurchlauf eingespart werden.
PAPI_TOT_CYC ................................. 1.46872e+08
PAPI_TOT_INS ................................. 2.35625e+08
PAPI_BR_MSP .................................. 1.13667e+06
PAPI_FP_OPS .................................. 473
-> ungefähr gleich gut wie bisher beste Lösung, daher: Änderungen beibehalten
Im Programm werden mehrmals Variablen p definiert, die aber jeweils nur einmal gebraucht werden. Daher wird nun auf die Erzeugung dieser Variablen verzichtet.
PAPI_TOT_CYC ................................. 1.4689e+08
PAPI_TOT_INS ................................. 2.35625e+08
PAPI_BR_MSP .................................. 1.13713e+06
PAPI_FP_OPS .................................. 481
-> ungefähr gleich gut wie bisher beste Lösung, wahrscheinlich unterscheidet sich der erzeugte Code kaum; Änderungen können beibehalten werden
Die Funktion transition wird in das Hauptprogramm eingebettet.
PAPI_TOT_CYC ................................. 1.45285e+08
PAPI_TOT_INS ................................. 2.27568e+08
PAPI_BR_MSP .................................. 1.10047e+06
PAPI_FP_OPS .................................. 474
-> Verbesserung, daher: Änderungen beibehalten
Im Programm kommt eine optimierungsbedürftige for-Schleife vor:
if (superp != NULL)
{
struct super_state *supers = *superp;
for (; supers != NULL; supers = supers->next)
{
...
}
...
}
Da beim ersten Durchlauf supers != NULL erfüllt ist, kann diese for-Schleife durch eine do-while-Schleife ersetzt werden.
PAPI_TOT_CYC ................................. 1.42833e+08
PAPI_TOT_INS ................................. 2.27461e+08
PAPI_BR_MSP .................................. 1.07408e+06
PAPI_FP_OPS .................................. 486
-> Verbesserung, daher: Änderungen beibehalten
Im Code kommt printf ("\n"); vor. Es wird probiert, ob puts (""); effizienter ist.
PAPI_TOT_CYC ................................. 1.4505e+08
PAPI_TOT_INS ................................. 2.29018e+08
PAPI_BR_MSP .................................. 1.0931e+06
PAPI_FP_OPS .................................. 483
-> Verschlechterung, daher: Änderungen verwerfen
Das Programm enthält kurz vor dem Ende des Quellcodes eine seltsame for-Schleife, die sich verbessern lässt:
Vergleichen der Dateien sp19.c und SP21.C
***** sp19.c
no_transition = ((!trans [0] [nextstate].relocatable) || trans [0] [nextstate].no_transition);
for (i = 0; i < ninsts; i++)
if (i == nextdyn)
{
if (!no_transition)
***** SP21.C
no_transition = ((!trans [0] [nextstate].relocatable) || trans [0] [nextstate].no_transition);
for (i = nextdyn; i < ninsts; )
{
if (!no_transition)
*****
***** sp19.c
nextstate = c->state_out;
nextdyn += c->length;
}
}
***** SP21.C
nextstate = c->state_out;
if (c->length > 0)
{
nextdyn += c->length;
i = nextdyn;
}
else
i = ninsts;
}
}
*****
PAPI_TOT_CYC ................................. 1.42736e+08
PAPI_TOT_INS ................................. 2.27494e+08
PAPI_BR_MSP .................................. 1.0718e+06
PAPI_FP_OPS .................................. 480
-> (kleine) Verbesserung, daher: Änderungen beibehalten
Es wird versucht, eine Verbesserung zu erreichen, indem die Funktion hash_super umgeschrieben wird: Aus
static int hash_super (PrimNum *start, int length)
{
int i, r;
for (i = 0, r = 0; i < length; i++)
{
r <<= 1;
r += start [i];
}
return r & (HASH_SIZE-1);
}
wird
static int hash_super (PrimNum *start, int length)
{
int r;
for (r = 0; length; length--, start++)
{
r <<= 1;
r += *start;
}
return r & (HASH_SIZE - 1);
}
PAPI_TOT_CYC ................................. 1.438e+08
PAPI_TOT_INS ................................. 2.28403e+08
PAPI_BR_MSP .................................. 1.04356e+06
PAPI_FP_OPS .................................. 475
-> Verschlechterung, daher: Änderungen verwerfen
Die Funktion hash_super wird in die sie aufrufenden Funktionen eingebettet.
PAPI_TOT_CYC ................................. 1.43462e+08
PAPI_TOT_INS ................................. 2.26708e+08
PAPI_BR_MSP .................................. 1.09736e+06
PAPI_FP_OPS .................................. 478
Die Funktionen lookup_super und cost_codesize werden in die aufrufenden Funktionen eingebettet (Inlining). Vor dem Einbetten liefert gprof folgende Analyse:
index % time self children called name
[1] 100.0 0.05 0.01 main [1]
0.01 0.00 3708755/3708755 cost_codesize [2]
0.00 0.00 136065/136065 lookup_super [3]
-----------------------------------------------
0.01 0.00 3708755/3708755 main [1]
[2] 16.7 0.01 0.00 3708755 cost_codesize [2]
-----------------------------------------------
0.00 0.00 136065/136065 main [1]
[3] 0.0 0.00 0.00 136065 lookup_super [3]
-----------------------------------------------
D.h. lookup_super und cost_codesize werden zusammen 3,84 Millionen mal aufgerufen. Durch das Inlining wird die Gesamtlaufzeit des Programmes leicht gesenkt, die Anzahl an branch mispredictions steigt jedoch:
PAPI_TOT_CYC ................................. 1.42665e+08
PAPI_TOT_INS ................................. 2.25737e+08
PAPI_BR_MSP .................................. 1.11932e+06
PAPI_FP_OPS .................................. 482
-> (kleine) Verbesserung, daher: Änderungen beibehalten
In Zeilen 3827f (sp25.c) wird ein Vergleich mittels memcmp vorgenommen:
if (length == p->length && memcmp ((char *)p->start, (char *)start, length * sizeof (PrimNum)) == 0) {
return &(p->ss_list);
}
(p->start) start
`---, `---,
,------------------------ ... -----------------,
| PN1 | PN2 | PN3 | PN4 | ... PNX | PNY | PNZ |
`------------------------ ... -----------------´
`--- z.B. l = 3 --´ `------ l = 3 ---´
Das Ergebnis der Änderung ist:
if (( length == p->length ) &&
( (length == 1 && (int*)p->start == (int*)start)
|| ( length == 2 && (long*)p->start == (long*)start )
|| ( memcmp ((char *)p->start, (char *)start, length * sizeof (PrimNum)) == 0)
)
)
PAPI_TOT_CYC ................................. 1.41517e+08
PAPI_TOT_INS ................................. 2.26637e+08
PAPI_BR_MSP .................................. 1.07972e+06
PAPI_FP_OPS .................................. 479
Feedback hierher senden