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
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 | }
|
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.
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
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
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
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 | }
|
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
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.
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?
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
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
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
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. :-)
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 | }
|
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 | }
|
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
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
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
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!
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
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
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.