Hardware inspirierte Schleife. Unsinn?

Question

Neulich habe ich in Verilog einen coolen Trick gelernt. Wenn Sie wiederholt etwas tun müssen. Sie könnten ein Schieberegister verwenden, um die Anzahl der Inkrementierungen zu zählen. Verschieben Sie einfach eine 1 von LSB zu MSB, und wenn es die MSB erreicht, sind Sie fertig.

In C würde es so etwas wie diese:

for(j=0b1; !(j & (1<<16)); j=j<<1) 
{ 
/*do a thing 16 times*/ 
} 

Ich weiß, es Nutzung wegen der Bit-Breite begrenzt ist, aber es ist keine Beteiligung hinaus, so dass es schnell ist. Also meine Frage: Gibt es eine Verwendung von diesem? Lohnt es sich, in C oder einer anderen Hochsprache zu verwenden?

Vielleicht in eingebetteten Systemen, wo Ressourcen begrenzt sind.

Dank

Answer 1

es ist beteiligt keine Zugabe, so dass es schnell ist

, für die CPU-Architektur verschieben schneller als Zugabe? Was bringt Sie auch dazu, zu glauben, dass der Compiler für diese spezifische Architektur die Optimierung von Addition zu Verschiebung nicht automatisch durchführt, wenn sich herausstellen sollte, dass die Verschiebung schneller ist?

Gibt es eine Verwendung von diesem?

Für Optimierungszwecke, nein, es gibt keine Verwendung davon.

Für andere Zwecke, ja, Code wie dieser wird häufig zum Ausblenden einzelner Bits eines Bytes verwendet.Ich glaube, die beiden häufigsten Ansätze sind diese:

uint8_t mask; 

for(mask = 0x01; mask != 0x00; mask<<=1) 
{ 
    do_something (data & mask); 
} 

oder

for(i=0; i<8; i++) 
{ 
    do_something (data & (1<<i)); 
} 

Answer 2

Das ist sehr nicht wert. Es macht den Code viel weniger sauber und schwieriger zu lesen, und der Leistungsunterschied ist vernachlässigbar.

Ihr Compiler kann diese Arten von Optimierungen viel besser als Sie können. Kurze Loops wie diese könnten sogar aus Performance-Gründen abgerollt werden. Wenn Sie die Schleife jedoch so schreiben, könnte ein Compiler das nicht so einfach herausfinden, und Sie könnten das Programm sogar verlangsamen.

Dies ist wirklich ein Fall von Mikro-Optimierung, die fast nie einen spürbaren Unterschied auf der Laufzeit Ihres Programms machen wird.

Answer 3

In einer echten CPU ist die Addition eines der schnellsten Dinge, die Sie tun können; ein Bitshift ist nicht schneller. Und Sie werden es dem Compiler schwerer machen, effizient zu optimieren.

Answer 4

Schneller? Bist du dir da sicher? Zumindest in der MIPS-Architektur dauert eine Bitverschiebung genau so lange wie eine Addition. Ich wäre überrascht, wenn dies nicht auch für die gängigsten Consumer-orientierten Prozessorarchitekturen gelten würde.

Außerdem, wie Oleksi bemerkt, ist dies ziemlich schwer zu lesen. Wahrscheinlich nicht wert eine nicht vorhandene Geschwindigkeitszunahme.

Answer 5

In der Regel, wenn Sie eine bestimmte Anzahl von Zeiten immer Schleife auf> 0 und Loop-Overhead minimieren, dann denke ich, das die „beste“ sein wird:

unsigned i = 16; 

do { 
// do something here 
} while (--i); 



You might get the same result with: 

unsigned i = 0x8000; 

do { 
// do something here 
} while (i>>=1); 

An diesem Punkt, den Sie suchen haben würden bei der Montage.

Answer 6

Es scheint mir, dass die meisten der Kommentatoren nicht wirklich verstehen, worüber der Fragesteller spricht. Verilog-Sprache ist für Hardware-Design und Hardware-Design ist sehr unterschiedlich, als Software-Design, keine CPU-Zyklen oder ähnliches. Aber kurze Antwort ist immer noch: Nein. Lange Antwort:

Für die sichere Verschiebung ist viel einfacher als Addition. Zum Schalten gibt es viel weniger Logik von FF (Flipflop) nach FF. Zusätzlich muss der Übertrag von dem LSB-Bit zu dem MSB-Bit übertragen werden, was log2 (N) -Niveaus der Logik bedeutet (N ist der oberste Wert, den der Zähler erreichen würde). Andererseits würde das Schieberegister N FFs verwenden, während der Addierer nur log2 (N) FFs verwenden würde. Es gibt also einen Performance/Area Trade Off, der auch stark von N abhängig ist.Einige 'unabhängige' Informationen über Addierer: http://en.wikipedia.org/wiki/Adder_%28electronics%29 Konnte ähnlichen Artikel für Verschiebung nicht finden, aber sobald Sie Addierer verstehen, sollte Shifter offensichtlich sein.

Dies ist möglicherweise wichtig, wenn Sie die Zustandsmaschine in RTL entwerfen. Aber der Code, den Sie vorgestellt haben, hat eigentlich nichts mit dem oben genannten zu tun. Diese "for" -Schleife in Verilog bedeutet, dass alle "Arbeiten" in einem einzigen Zyklus ausgeführt werden. Also wird es tatsächlich N Logiken geben. Diese Schleife hat nichts mit der Implementierung zu tun. Es könnte sogar den Verilog-Compiler verwirren, um etwas Seltsames auszuspucken und die Simulation zu beeinflussen (wo CPU-Zyklen wichtig sind und ob die obigen Antworten gültig wären). Jemand mit mehr Erfahrung mit Tools könnte dies kommentieren.

Answer 7

(Stand Stefan Antwort, ich nehme an, Sie über die C-Version von der Verilog-Version inspiriert sind gefragt, nicht dazu in Verilog zu tun.)

Auf vielen Architekturen, das ist eigentlich noch schlimmer, weil Die Bitverschiebung nimmt eine zusätzliche Anweisung, während die Addition für die Schleifenvariable vollständig frei ist.

Komplett?

Ja. Weil es auf vielen Architekturen einzelne Anweisungen gibt, die einen Zähler dekrementieren und einen Zweig verzweigen, wenn er nicht null ist - und diese Anweisungen nehmen genauso viel Zeit in Anspruch wie jeder andere Vergleichs- und Verzweigungsbefehl. Wenn Sie jedoch eine Schicht machen, erfordert das einen zusätzlichen Instruktionszyklus. Es ist noch schlimmer, wenn Ihre Plattform keine "Gleich- und Zweigniederlassung" -Anweisung hat - und nicht alle von ihnen; Einige machen Sie subtrahieren und in zwei Anweisungen mit Null vergleichen.

Auch auf einer RISC-Plattform ohne Dekrement-Vergleichs-Verzweigungsbefehl ist die Countdown-Schleife wahrscheinlich schneller, da Sie einfach (eine Anweisung) subtrahieren und die Verzweigung-Wenn-Nicht-Null-Anweisung verwenden können. Sie benötigen eine Verschiebung (eine Anweisung) und eine bitweise - und (eine Anweisung) vor der Verzweigung - wenn - Null. Und das setzt voraus, dass Sie sogar eine Verzweigung-wenn-Null haben.

Darüber hinaus ist es für eine einfache for (i = 0; i < N; i++)-Schleife trivial für den Compiler, es in eine "count down to 0" -Schleife umzuwandeln, wenn das schneller ist - Sie müssen selten selbst diese Klugheit selbst tun.

Answer 8

Inkrement ist ein ganz spezieller Fall der Addition. In den meisten Prozessoren und sicherlich den meisten RISC-Prozessoren werden eine Verschiebung und ein Inkrement in der Ausführungszeit identisch sein. Tatsächlich wird in den meisten Architekturen der Zusatz auch nicht länger dauern.

Wenn Sie Ihren Schleifencode idiomatisch halten, ist der Optimierer in der Lage, die Schleife einfach abzuwickeln und sie in jedem Fall schneller zu machen. Wenn Sie den Loop-Mechanismus "ungewöhnlich" machen, kann der Optimierer ihn möglicherweise nicht optimieren.