Forum: Compiler & IDEs Geschwindigkeit eines ARM9 mit 180MHz (UDP Checksum-Berechnung)


von Daniel G. (motello)


Lesenswert?

Hallo,

ich wundere mich etwas über die Zeit, die meine Funktionen zur 
Ausführung brauchen. Ohne den Quellcode zu kennen ist es natürlich 
schwer eine Aussage zu machen, aber mir geht es nicht um ein paar 
Prozentpunkte sondern darum, ob ich etwas so gravierend falsch gemacht 
habe, dass die Ausführzeit beispielsweise doppelt so hoch ist wie 
erreichbar.

Als Beispiel meinen ultra light weight TCP/IP Stack der folgendes macht:
- ein paar Felder in den Protokoll Headern setzen (DIX, IP, UDP)
- UDP und IP checksums berechnen (dauert wohl am längsten)
- Header in den TX Buffer kopieren (Daten von 444 Byte sind schon drin).

Das ganze braucht 140us. Der Prozessor Takt ist 180MHz, die Master Clock 
90MHz. Es ist ein AT91SAM9260 MCU mit SDRAM. DCache ist für die TX 
Buffer nicht aktiviert.

Nun meine Fragen:
Hat jemand Erfahrung mit anderen TCP/IP Stack auf einem ähnlichen 
Prozessor und kann mir etwas über die Dauer sagen? Vielleicht hat ja 
auch jemand einen Link oder Buchtipp, wo ich etwas über die Ausführzeit 
von Funktionen und Algorithmen lernen kann oder muss ich selbst durch 
messen und ausprobieren ein Gefühl dafür entwickeln? 140us kommt mir 
ziemlich lang vor und es ist schon sehr hilfreich, wenn man von 
vornherein Zeiten abschätzen kann.

Ich freue mich auf Tipps und Hinweise!
Viele Grüße
Daniel

von Daniel G. (motello)


Lesenswert?

Ich habe nun nochmal den Checksum algorithmus überarbeitet und dabei die 
Tatsache genutzt, dass man die berechnung von big endian daten auch in 
little endian durchführen kann. somit ist die routine nun fast doppelt 
so schnell (89us). Kommt mir aber immer noch ziemlich lang vor.

Zuvor habe ich die 16bit wörter in little endian umgewandelt zur 
berechnung.

hier der code meiner UDP-checksum routine:
1
unsigned short eth_chksum_udp (struct PD_typ *RxPd)
2
{
3
4
  int words;
5
  int i;
6
  long sum = 0;
7
  unsigned short *ptr;
8
  union {
9
    unsigned char u8[20];
10
    unsigned short u16[10];
11
    unsigned long u32[5];
12
  } header;
13
14
/* 
15
 * assemble pseudo header 
16
 */
17
  /* IP addresses */
18
  header.u32[0] = RxPd->ip_header->srcIP;
19
  header.u32[1] = RxPd->ip_header->destIP;
20
  /* append zero-byte */
21
  header.u8[8] = 0;
22
  /* protocol-ID */
23
  header.u8[9] = RxPd->ip_header->prot;
24
  /* UDP length field */
25
  header.u16[5] = RxPd->udp_header->length;
26
27
/*
28
 * copy udp-header
29
 */
30
31
  memcpy(header.u8+12, RxPd->udp_header, 6);
32
33
  /* zero udp-checksum field */
34
  header.u16[9] = 0;
35
36
/* 
37
 * calculate checksum
38
 */
39
40
  /* calculation for pseudo and udp header */
41
  for (i = 0; i < 10; i++) {
42
    sum += header.u16[i];
43
    sum += (sum & 0x10000) >> 16;
44
    sum = sum & 0xffff;
45
  }
46
47
  /* calculate 16-bit words in UDP payload */
48
  words = ((endians(RxPd->udp_header->length))-8) / 2;
49
50
  /* set payload pointer */
51
  ptr = (unsigned short*) RxPd->PMI_prot;
52
53
  /* calculation for UDP payload */
54
  for (i = 0; i < words; i++) {
55
    sum += ptr[i];
56
    sum += (sum & 0x10000) >> 16;
57
    sum = sum & 0xffff;
58
  }
59
60
  /* if the length is odd, append last byte and a zero-byte */
61
  if ( (endians(RxPd->udp_header->length)) % 2) {
62
    sum += ptr[words] & 0xff;
63
    //most significant byte is zero, useless to add
64
    sum += (sum & 0x10000) >> 16;
65
    sum = sum & 0xffff;
66
  }
67
68
  sum = endians((unsigned short)sum);
69
70
  if (~sum)
71
    return (unsigned short) ~sum;
72
73
  else 
74
    return 0xffff;
75
76
}

von Tauwetter (Gast)


Lesenswert?

Sieh Dir doch einmal den Ass.-Code an, der vom Compiler erzeugt wird. Da 
erkennt man am besten, was nicht optimal ablaufen könnte.

Ausdrücke wie: sum += ptr[i]; können u.U. uneffizient sein, wenn ptr nur 
hier gebraucht wird. ptr++ wird ggf. schneller ausgeführt.
Ich weiß nicht, wie groß 'int i' ist. 16bit oder 32bit? Nimm immer den 
Datentyp, den der Prozessor intern verwendet; das sollte hier 32bit 
sein. Andernfalls muß bei jeder Operation ggf. erst auf 32bit erweitert 
werden.
Nutze internes RAM solange es geht; externe Speicherzugriffe brauchen 
eine Ewigkeit. Dein Stack liegt hoffentlich auch im internen RAM?

Und selbst wenn alles optimal übersetzt ist: auch ein 200MHz µC braucht 
seine Zeit für die Programmabarbeitung.

von Marcus H. (mharnisch) Benutzerseite


Lesenswert?

Hallo Daniel

Daniel G. schrieb:
> Ich habe nun nochmal den Checksum algorithmus überarbeitet und dabei die
> Tatsache genutzt, dass man die berechnung von big endian daten auch in
> little endian durchführen kann. somit ist die routine nun fast doppelt
> so schnell (89us).

Aber die zuerst genannten 140µs waren doch die Zeit, die "das ganze"
(header, check sum, copy) gedauert hat, wenn ich Dich recht verstehe.

Die Routine liest die Daten, kopiert sie aber nicht. Wenn das woanders
nochmal gemacht wird kostet es viel Zeit -- besonders wenn die Daten
nicht im Cache liegen. Aber ich habe gerade etwas den Überblick
verloren, welche Deiner Daten als non-cacheable markiert waren :-)

Soweit ich das sehe, kannst Du die Prüfsumme auch für 32bit Worte
bilden und am Ende auf 16bit zusammenfalten. In beiden Fällen hilft
inline Assembler, mit dem man Zugriff auf das Carry Flag hat. Ist
schon einige Takte flotter als das was man mit einem C compiler
hinbekommt. Bevor Du dort optimierst, solltest Du allerdings unbedingt
die Speicherzugriffe überprüft haben.

Weitere Tips: http://tools.ietf.org/html/rfc1071#section-2

Gruß
Marcus
http://www.doulos.com/arm

von Daniel G. (motello)


Lesenswert?

Danke für die Antworten!

das was am gesamten TCP/IP Stack mit EMAC Treiber überhaupt nennenswerte 
Zeit in Anspruch nimmt, ist allein die UDP checksum routine. Der Rest 
braucht nur wenige us.

Die Daten auf die die checksum routine zugreift ist weder cached noch 
buffered, nämlich der EMAC TX buffer Bereich des AT91SAM9260.

Ich weiß noch nicht, in wie weit es Sinn macht, in die Optimierung Zeit 
zu stecken (weil die Latenz möglicherweise schon klein genug ist), aber 
das mit dem zusammenrechnen der 32-bit wörter werde ich mal probieren! 
Auch werde ich mir mal den Assembler code ansehen.

Ich schreibe das Ergebnis, sobald ich es habe!

Viele Grüße,
Daniel

von Marcus H. (mharnisch) Benutzerseite


Lesenswert?

Daniel G. schrieb:
> Die Daten auf die die checksum routine zugreift ist weder cached noch
> buffered, nämlich der EMAC TX buffer Bereich des AT91SAM9260.

Damit wird jeder Zugriff bestenfalls einen Buszyklus dauern. Wären die
Daten cacheable, würden die Daten der folgenden Schleifeniteration
durch den line-fill dem Core bereits vorliegen sobald dieser sie
benötigt. Können wir davon ausgehen, dass ein Block à acht Worte
(32bit) in diesem Bereich nicht mehr verändert wird, während darauf
lesend zugegriffen wird?

> Ich weiß noch nicht, in wie weit es Sinn macht, in die Optimierung Zeit
> zu stecken (weil die Latenz möglicherweise schon klein genug ist), aber
> das mit dem zusammenrechnen der 32-bit wörter werde ich mal probieren!
> Auch werde ich mir mal den Assembler code ansehen.

Versuchs erstmal mit dem Speicher. Wenn Du dann noch Spaß hast, weiter
zu optimieren kannst Du Dich mit dem Rest beschäftigen.

Gruß
Marcus

von Daniel G. (motello)


Lesenswert?

Marcus Harnisch schrieb:
> Weitere Tips: http://tools.ietf.org/html/rfc1071#section-2

Habe anhand des Dokuments mal meinen Code überarbeitet. Suche seit 
gestern unermüdlich den Fehler: Die Checksumme wird nur für manche 
Pakete richtig berechnet und teilweise nur genau jedes Zweite mal. 
Konnte leider keine weiteren "Regeln" finden.

Vielleicht kann ja mal jemand in den Code schauen:
1
unsigned short eth_chksum_udp (struct PD_typ *Pd)
2
{
3
4
  int words;
5
  int i;
6
  int udp_payload_length;
7
  unsigned long sum = 0;
8
  unsigned long temp;
9
  unsigned long *ptr;
10
  
11
  struct {
12
    unsigned long srcIP;
13
    unsigned long destIP;
14
    unsigned char zero;
15
    unsigned char prot;
16
    unsigned short UDP_length;
17
    unsigned char UDP_header[6];
18
    unsigned short UDP_chksum;
19
  } __attribute__ ((packed)) pseudo_header;
20
21
/* 
22
 * assemble pseudo header 
23
 */
24
  /* IP addresses */
25
  pseudo_header.srcIP = Pd->ip_header->srcIP;
26
  pseudo_header.destIP = Pd->ip_header->destIP;
27
  /* append zero-byte */
28
  pseudo_header.zero = 0;
29
  /* protocol-ID */
30
  pseudo_header.prot = Pd->ip_header->prot;
31
  /* UDP length field */
32
  pseudo_header.UDP_length = Pd->udp_header->length;
33
  /* copy UDP header exept checksum */
34
  memcpy(pseudo_header.UDP_header, Pd->udp_header, 6);
35
  /* zero udp-checksum field */
36
  pseudo_header.UDP_chksum = 0;
37
38
  udp_payload_length = endians(Pd->udp_header->length) - 8;
39
40
/* 
41
 * calculate checksum of pseudo header
42
 */
43
44
  ptr = (unsigned long*) &pseudo_header;
45
46
  /* calculation for pseudo and udp header */
47
  for (i = 0; i < 5; i++) {
48
    asm volatile (
49
      "ldr r2, [%[ptr]], #4\n\t"
50
        "adds %[sum], %[sum], r2\n\t"
51
      "adc %[sum], %[sum], #0"
52
      : [sum] "+r" (sum), [ptr] "+r" (ptr)
53
      :: "r2", "cc"
54
    );
55
  }
56
57
/* 
58
 * calculate checksum of data
59
 */
60
61
  /* calculate number of 32-bit words in UDP payload */
62
  words = udp_payload_length / 4;
63
64
  /* set payload pointer */
65
  ptr = (unsigned long*) Pd->PMI_prot;
66
67
  /* calculation for UDP payload */
68
  for (i = 0; i < words; i++) {
69
    asm volatile (
70
      "ldr r2, [%[ptr]], #4\n\t"
71
        "adds %[sum], %[sum], r2\n\t"
72
      "adc %[sum], %[sum], #0"
73
      : [sum] "+r" (sum), [ptr] "+r" (ptr)
74
      :: "r2", "cc"
75
    );
76
  }
77
  
78
  /* compute the last word, the length may be odd so that zero bytes
79
   * have to be appended */
80
  i = udp_payload_length % 4;
81
  temp = *ptr;
82
  temp &= ~(0xffffffff << (i*8));
83
84
  asm volatile (
85
      "adds %[sum], %[sum], %[temp]\n\t"
86
    "adc %[sum], %[sum], #0"
87
    : [sum] "+r" (sum)
88
    : [temp] "r" (temp)
89
    : "cc"
90
  );
91
92
  /* fold the result to 16 bit */
93
  temp = sum & 0xffff;
94
  temp += sum >> 16;
95
  temp += (temp & 0x10000) >> 16;
96
  
97
  sum = endians((unsigned short)temp);
98
99
  if (sum < 0xffff)
100
    return (unsigned short) ~sum;
101
102
  else
103
    return 0xffff;
104
105
}

von Marcus H. (mharnisch) Benutzerseite


Lesenswert?

Daniel G. schrieb:
> Vielleicht kann ja mal jemand in den Code schauen:

Beim Überfliegen ist mir erstmal nichts aufgefallen.

Allerdings kann man das ganze auch elegant mit einem 64bit Akkumulator 
in C implementieren. Das obere Wort summiert die Carries (deferred 
carry). Ein guter Compiler setzt das so um, dass Du Dir dieses 
scheußliche GCC-Inline Assembler Geraffel sparen kannst. Am Ende high 
und low word addieren, und dann noch mal high und low half-word. Oder 
habe ich hier einen Denkfehler gemacht?

Das deferred Carry hat noch einen anderen Vorteil: Die Abhängigkeiten 
zwischen den Iterationen verschwinden. Damit kann das auf performanteren 
CPUs unter Ausnutzung der SIMD Einheiten vektorisiert werden. Für den 
Cortex-A9 übersetzt (mit 32 Bit Akku) sieht das schon ganz lecker aus.

Aber viel wichtiger: DEN CACHE EINSCHALTEN! Da es um Lesezugriffe geht, 
reicht ja WT Konfiguration.

Gruß
Marcus

von Daniel G. (motello)


Lesenswert?

Marcus Harnisch schrieb:
> Allerdings kann man das ganze auch elegant mit einem 64bit Akkumulator
> in C implementieren. Das obere Wort summiert die Carries (deferred
> carry). Ein guter Compiler setzt das so um, dass Du Dir dieses
> scheußliche GCC-Inline Assembler Geraffel sparen kannst. Am Ende high
> und low word addieren, und dann noch mal high und low half-word. Oder
> habe ich hier einen Denkfehler gemacht?

Vielen Dank für den guten Tipp! Ist GCC denn einer dieser guten 
Compiler? :-) Wie du es sagst, müsste es gehen, so habe ich den 
Algorithmus auch verstanden.

Ich bin den gesamten Assembler code instruction für instruction 
durchgegangen und alles ist genau so wie ich es wollte. Vielleicht ist 
doch etwas an meinem Algorithmus falsch:

1. Die Wörter (32bit) zusammenrechnen und nach jeder addition das carry 
bit, wenn vorhanden, aufaddieren.

2. beide halbwörter addieren und carry dazu addieren.

3. invertieren

Oder funktioniert das mit dem carry aufaddieren im asm code nicht wie 
ich denke?

Um caches kümmere ich mich danach. erstmal diese Baustelle beenden.

von Daniel G. (motello)


Lesenswert?

Vielleicht ist es sinnvoll den Titel zu ändern und zumindest "UDP 
checksum" mit reinzunehmen, wegen der suchfunktion.

Vorschlag: "UDP checksum Geschwindigkeit auf ARM9"

Kann das mal ein Admin bitte machen?

von Marcus H. (mharnisch) Benutzerseite


Lesenswert?

Daniel G. schrieb:
> Ist GCC denn einer dieser guten Compiler? :-)

Bei oberflächlicher Inspektion sieht der erzeugte Code OK aus. Für 
tiefergehende Untersuchungen hab ich gerade keine Zeit.

Gruß
Marcus

von Daniel G. (motello)


Lesenswert?

Habe den Fehler noch finden können: Die Daten auf die ich 32-bit 
Wort-weise zugreifen wollte waren nicht aligned :-| Wenn C durch 
Assembler ersetzt wird, ist das natürlich fatal. Wie konnte mir das nur 
passieren?!?!?!

Werden den Code nun überarbeiten und nur halbe Wörter mit deferred carry 
zusammenzählen. Melde mich dann wieder!

Viele Grüße
Daniel

von Marcus H. (mharnisch) Benutzerseite


Lesenswert?

Daniel G. schrieb:
> Habe den Fehler noch finden können: Die Daten auf die ich 32-bit
> Wort-weise zugreifen wollte waren nicht aligned :-| Wenn C durch
> Assembler ersetzt wird, ist das natürlich fatal.

Das ist immer fatal -- auch in C (wenn der compiler es nicht 
mitbekommt). Du kannst es bei Deinem Core wenigstens durch einen Fault 
abfangen:
http://infocenter.arm.com/help/topic/com.arm.doc.ddi0198e/Babcjcbe.html

Hast Du Einfluss auf das Aligment der Daten?

> Werden den Code nun überarbeiten und nur halbe Wörter mit deferred carry
> zusammenzählen.

Halbe Worte? Nun als Referenz vielleicht. Aber denke daran, dass Du 
damit etwa doppelt so viele Speicherzugriffe hast, die wohlgemerkt alle 
über den Systembus und nicht etwa vom Cache :^) bedient werden.

--
Marcus

von Daniel G. (motello)


Lesenswert?

Marcus Harnisch schrieb:
> Das ist immer fatal -- auch in C (wenn der compiler es nicht
> mitbekommt). Du kannst es bei Deinem Core wenigstens durch einen Fault
> abfangen:
> http://infocenter.arm.com/help/topic/com.arm.doc.d...

DANKE!!! Deine Tipps sind ja Gold wert!

Werde mich heute nochmal an den Code machen und mir eine elegante Lösung 
überlegen. Vielleicht auch mit viel asm weil dann die carries durch adcs 
gleich mit der wort-addition aufaddiert werden können.

ja, ja, die caches mach ich auch an! Muss mich vorher nur noch 
cache-clean kümmern, bevor EMAC per DMA auf die Daten zugreift. :-)

von Daniel G. (motello)


Lesenswert?

Habe die Routine nochmal überarbeitet. Nun erreiche ich ohne Caches (die 
ich dann auch noch anschalte) eine Berechnungszeit von etwa 30us für die 
UDP checksum bei einer Paketgröße von 450B.

Der Code besteht aus zwei Teilen: einer Routine (eth_chksum_sum) die die 
one's complement sum berechnet und für UDP und IP benutzt werden kann. 
Und dann eben für IP und UDP die hauptroutine. Hier der Code:


1
/************************************************
2
 * UDP CHECKSUM CALCULATION                     *
3
 ************************************************/
4
5
unsigned short eth_chksum_udp (struct PD_typ *Pd)
6
{
7
8
  unsigned int udp_length;
9
  unsigned long sum;
10
  
11
  struct {
12
    unsigned long srcIP;
13
    unsigned long destIP;
14
    unsigned char zero;
15
    unsigned char prot;
16
    unsigned short UDP_length;
17
  } __attribute__((packed, aligned(4))) pseudo_header;
18
19
20
/* 
21
 * assemble pseudo header 
22
 */
23
24
  /* IP addresses */
25
  pseudo_header.srcIP = Pd->ip_header->srcIP;
26
  pseudo_header.destIP = Pd->ip_header->destIP;
27
  /* append zero-byte */
28
  pseudo_header.zero = 0;
29
  /* protocol-ID */
30
  pseudo_header.prot = Pd->ip_header->prot;
31
  /* UDP length field */
32
  pseudo_header.UDP_length = Pd->udp_header->length;
33
34
35
/*
36
 * calculate checksum
37
 */
38
  
39
  /* UDP frame length in bytes */
40
  udp_length = endians(Pd->udp_header->length);
41
42
43
  /* pseuso header */
44
  sum = eth_chksum_sum (&pseudo_header, 12);
45
46
  /* UDP header */
47
  sum += eth_chksum_sum (Pd->udp_header, 6);
48
  sum += sum >> 16;  //carry
49
  sum &= 0xffff;
50
51
  /* UDP payload */
52
  sum += eth_chksum_sum (Pd->PMI_prot, udp_length - 8);
53
  sum += sum >> 16;  //carry
54
  sum &= 0xffff;
55
56
  if (sum < 0xffff)
57
    return (unsigned short) ~sum;
58
59
  else
60
    return 0xffff;
61
62
}
63
64
65
/************************************************
66
 * One's complement sum                         *
67
 ************************************************/
68
69
unsigned long eth_chksum_sum (void* ptr, unsigned int length) {
70
71
/* 
72
 * the routine assumes, that the data has at least a 16bit
73
 * alignment. The length of the data can be odd. 
74
 */
75
76
  unsigned long temp = 0, sum = 0;
77
  unsigned int aligned_bytes, unaligned_bytes;
78
79
  /* return if ptr hasn't got at least a 16bit alignment */
80
  if ((unsigned int)ptr % 2) {
81
    return 0;
82
  }
83
84
  /* if pointer is not 4B aligned */
85
  if ((unsigned int)ptr % 4) {
86
    unaligned_bytes = 2 + ((length - 2) & 3);
87
    aligned_bytes = length - unaligned_bytes;
88
89
    /* add the halfword before the first aligned word */
90
    sum = *(unsigned short*)ptr;
91
    
92
    /* adjust pointer and counter */
93
    ptr += 2;
94
    unaligned_bytes -= 2;
95
  }
96
97
  /* if pointer is 4B aligned */
98
  else {
99
    unaligned_bytes = length & 3;
100
    aligned_bytes = length - unaligned_bytes;
101
  }
102
  
103
104
  /* start calculation */
105
  if (aligned_bytes) {
106
    asm volatile (
107
      /* sum loop */
108
      "1:"                "\t"
109
      "ldr  r2, [%[ptr]], #4"      "\n\t"
110
      "adds  %[sum], %[sum], r2"      "\n\t"
111
      "adc  %[sum], %[sum], #0"      "\n\t"
112
113
      /* check loop termination condition */
114
      "subs  %[abytes], %[abytes], #4"  "\n\t"
115
      "bne  1b"              "\n\t"
116
117
      :[sum] "+r" (sum), [ptr] "+r" (ptr), [abytes] "+r" (aligned_bytes)
118
      :: "r2", "cc"
119
    );
120
  }
121
122
  /* add remaining bytes, if existent */
123
  if (unaligned_bytes) {
124
    
125
    temp = *(unsigned long*)ptr;
126
    temp &= ~(0xffffffff << (unaligned_bytes*8));
127
128
    asm volatile (
129
      "adds  %[sum], %[sum], %[temp]"  "\n\t"
130
      "adc  %[sum], %[sum], #0"
131
      :[sum] "+r" (sum)
132
      :[temp] "r" (temp)
133
      : "cc"
134
    );
135
  }
136
137
  /* fold 32bit sum to 16bit */
138
  temp = sum & 0xffff;
139
  temp += sum >> 16;
140
  temp += temp >> 16;
141
  sum = temp & 0xffff;
142
143
  return sum;
144
145
}

von Marcus H. (mharnisch) Benutzerseite


Lesenswert?

Daniel G. schrieb:
> Habe die Routine nochmal überarbeitet. Nun erreiche ich ohne Caches (die
> ich dann auch noch anschalte) eine Berechnungszeit von etwa 30us für die
> UDP checksum bei einer Paketgröße von 450B.

Sehr schön :-)

> Der Code besteht aus zwei Teilen: einer Routine (eth_chksum_sum) die die
> one's complement sum berechnet und für UDP und IP benutzt werden kann.
> Und dann eben für IP und UDP die hauptroutine.

Ich dachte, das wäre der selbe Algorithmus. Warum zwei Funktionen?

>  Hier der Code:

Das mit dem Alignment würde ich viel pragmatischer angehen (falls das in 
Deinem System möglich ist). Das Aligment des Datenzeigers sollte eine 
Vorbedingung sein. Du könntest Dir einen entsprehenden Typ definieren 
und einen Parameter dieses Typs übergeben.
1
typedef uint8_t auint8_t __attribute__((aligned(4)));

Warum so viel Assembler. Das ist doch schlecht wartbar und vor allem 
nicht portabel. Vorteile neuer CPUs werden gar nicht ausgenutzt, da die 
Instruktionen hart verdrahtet sind. Der pipeline interlock zwischen dem 
Laden des Halbworts und Summieren ist ebenfalls hart verdrahtet. Ein 
Compiler würde durch geeignete Maßnahmen versuchen, das zu entspannen.

Versuch mal das hier. Sollte nicht erheblich langsamer sein (wenn 
überhaupt) und ist mehr oder weniger lesbar:
1
uint16_t chksum_32(auint8_t *ptr, uint32_t len)
2
{
3
    uint32_t i;
4
    uint32_t tail;
5
    uint32_t *wptr;
6
    uint64_t sum64 = 0;
7
    uint32_t sum32;
8
    uint16_t retval;
9
10
    if (len == 0)
11
        return 0xFFFF;
12
13
    assert(!((uint32_t)ptr % sizeof(uint32_t))); // ensure proper alignment
14
15
    wptr = (uint32_t *)ptr;
16
17
    for (i=0; i<len/4; i++) {
18
        sum64 += wptr[i];
19
    }
20
21
    if (len % 4) {
22
        // create bitmask to clear trailing bytes that are not part of the
23
        // data array.
24
        tail = wptr[i] & ~(0xFFFFFFFF << ((len % 4) * 8));
25
26
        sum64 += tail;
27
    }
28
    sum64  = (sum64 & 0xFFFFFFFF) + (sum64 >> 32); // Add carries and sum
29
    sum32  = (sum64 + (sum64 >> 32)) & 0xFFFFFFFF; // Add possible new carry
30
31
    sum32  = (sum32 & 0xFFFF) + (sum32 >> 16);     // Fold word into half word
32
    retval = (sum32 + (sum32 >> 16)) & 0xFFFF;     // Add possible new carry
33
34
    if (~retval)
35
        return ~retval;
36
    else 
37
        return 0xffff; 
38
}

von Marcus H. (mharnisch) Benutzerseite


Lesenswert?

Ich schrieb:
> In beiden Fällen hilft inline Assembler, mit dem man Zugriff auf das Carry
> Flag hat. Ist schon einige Takte flotter als das was man mit einem C
> compiler hinbekommt.

Wer schreibt denn so einen Mist ;-)

(Ich hatte zu dieser Zeit noch nicht die Idee mit dem 64bit Akkumulator, 
die sowohl von GCC als auch von RVCT sehr effizient umgesetzt wird)

Gruß
Marcus

von Daniel G. (motello)


Lesenswert?

Marcus Harnisch schrieb:
> Ich dachte, das wäre der selbe Algorithmus. Warum zwei Funktionen?

Hast mich nur falsch verstanden: Der algorithmus ist derselbe nur 
aufgerufen wird er von jeweils einer anderen Routine für IP und UDP. Die 
zu sendenden daten liegen noch verstreut und werden erst nach der 
checksummenberechnung zusammengesetzt. Daher kann die checksumme auch 
nicht am stück berechnet werden.

Marcus Harnisch schrieb:
> Der pipeline interlock zwischen dem
> Laden des Halbworts und Summieren ist ebenfalls hart verdrahtet. Ein
> Compiler würde durch geeignete Maßnahmen versuchen, das zu entspannen.

Was meinst Du? Ich lade doch kein Halbwort in asm?! Oder meinst du, dass 
ich nach dem addieren wieder zum laden springe? Wie könnte ein compiler 
das besser machen? die anzahl steht ja nicht fest, so das die schleife 
nicht abgewickelt werden kann.

Danke für den Code, ich werde mich Montag damit auseinander setzen.

Grüße
Daniel

von Marcus H. (mharnisch) Benutzerseite


Lesenswert?

Daniel G. schrieb:
> Was meinst Du? Ich lade doch kein Halbwort in asm?!

Entschuldige, das Wort natürlich. Es gibt zusätzlich zur externen
Speicherlatenz einen sogenannten load-use-interlock zwischen dem LDR
und der anschließenden Addition.  Ich fürchte, das der Compiler hier
nichts mehr optimieren kann. Das ist hier nur ein Taktzyklus, aber ein
gutes Beispiel für eine Optimierungs-Sackgasse durch zu starke
Einschränkung (Vorgabe der Assembler Befehle).

Das ist im Einzelfall durchaus sinnvoll, aber bei diesem einfachen
Algorithmus eher hinderlich wie sich im Laufe dieses Threads
herausstellte.

> Wie könnte ein compiler das besser machen? die anzahl steht ja nicht
> fest, so das die schleife nicht abgewickelt werden kann.

Klar kann sie. Nur für die übrigbleibenden Iterationen muss dann
weiterer Code ausgeführt werden. Du rollst ja die Schleife selbst
schon dadurch ab, dass Du ganze Worte lädst und dadurch zwei Halbworte
pro Iteration bearbeitest. Und am Ende bearbeitest Du das
abschließende Halbwort, falls vorhanden. Der Compiler macht das
ähnlich, nur eben für mehrere Worte.

Bei dem vom RealView Compiler erzeugten Code werden hier zwei Worte
pro Iteration bearbeitet. Durch die nun längere lineare Code Sequenz
hat der Compiler mehr Möglichkeiten die Befehle so umzusortieren, dass
Wartezeiten vermieden werden (z.B. durch Maximierung des Abstands
zwischen Laden und Bearbeiten eines Wortes). So stellt man zum
Beispiel fest, dass das erste Wort bereits vor Eintritt in die
Schleife geladen wird, während in der Schleife bereits das Wort der
nächsten Iteration aus dem Speicher geholt wird. Dadurch lassen sich
Latenzen auch gut verstecken.

Schönes Wochenende
Marcus

von Daniel G. (motello)


Lesenswert?

Guten Morgen!

Habe soeben die TX Buffer als write-through eingeschaltet und latenzen 
gemessen. Dabei ist mir aufgefallen, dass ich bei der letzten Messung 
vergessen hatte die compiler optimierung wieder einzuschalten. Die 
genannten 35us bezogen sich also auf ohne cache und ohne compiler 
optimierung.

Mit compiler opt. und cache komme ich jetzt auf etwa 8us für UDP 
checksum erzeugung.

8us sind etwa 1400 prozessor zyklen. 5 instruktionen per wort in der 
schleife in der die wörter zusammengerechnet werden, das sind bei einer 
paketgröße von 450B etwa 550 instruktionen. ldr braucht ein bisschen um 
daten zu holen, vor allem bei einem cache miss. Ein prozessor takt ist 
5,6ns lang. viel ist da wohl nicht mehr rauszuholen.

Ich muss mich erstmal wieder um andere Dinge kümmern, aber wenn ich hier 
noch weitere messungen oder experimente gemacht habe, schreib ich 
wieder!

von Andreas F. (aferber)


Lesenswert?

Nur mal so als kleiner Hinweis, wenn es dir auf ein Maximum an 
Geschwindigkeit ankommt, dann lass die Checksumme weg. Siehe RFC 768, 
die Prüfsumme ist bei UDP optional, zum weglassen das Feld im Header auf 
0 setzen.

Andreas

von Daniel G. (motello)


Lesenswert?

Andreas Ferber schrieb:
> Nur mal so als kleiner Hinweis, wenn es dir auf ein Maximum an
> Geschwindigkeit ankommt, dann lass die Checksumme weg. Siehe RFC 768,
> die Prüfsumme ist bei UDP optional, zum weglassen das Feld im Header auf
> 0 setzen.

Ich weiß, aber ich will wissen ob meine Daten richtig ankommen :-)

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.