Ich bin vor kurzem auf die folgende Interviewfrage gestoßen:
Wie können Sie eine Zahl effizient und optimiert mit 7 multiplizieren?
Ich weiß, dass ich mit 8 multiplizieren kann (oder um drei Bits nach links verschieben) und dann den ursprünglichen Wert subtrahieren:
%Vor%Aber gibt es andere Lösungen?
Um ein Vielfaches von 7 effizient zu erhalten:
%Vor%7 ist ein Vielfaches von 7. Das beantwortet die Frage, die Sie gestellt haben, aber ich bin mir sicher, dass es nicht die Frage beantwortet, die Sie stellen möchten.
EDIT: Das obige basiert auf dem ursprünglichen Titel der Frage, den ich gerade korrigiert habe.
Um effizient mit 7 zu multiplizieren, schreiben Sie einfach:
%Vor% und rufen Sie Ihren Compiler mit Optimierung auf. Lassen Sie den Compiler herausfinden, ob eine einzelne MUL-Anweisung oder etwas wie (x<<3) - x für die aktuelle Maschine effizienter ist .
Es gibt noch eine weitere implizite Frage: Auf welche Antwort hat der Interviewer gesucht? Ich hoffe, dass "der Compiler sich darum kümmern" würde eine akzeptable Antwort sein. (x<<3) - x ist wahrscheinlich die naheliegendste Mikrooptimierung - aber es kann zu falschen Antworten führen, wenn x<<3 überläuft und je nach System langsamer als eine MUL-Anweisung.
(Wenn ich der Interviewer wäre, wäre ich mehr beeindruckt von einer guten Erklärung und einem besseren Verständnis der Probleme als von irgendeiner spezifischen Antwort.)
BEARBEITEN
Wenn Sie noch mehr darüber nachdenken, sind die hier besprochenen Arten von Mikrooptimierungen nützlich , wenn Sie mehr über die möglichen Werte von x wissen als der Compiler. Wenn Sie wissen, dass x aufgrund der Art Ihrer Programmlogik immer im Bereich 0..10 liegt, könnte eine Nachschlagetabelle leicht schneller als eine Multiplikationsoperation sein. Oder wenn Sie wissen, dass x in diesem Bereich 99% der Zeit ist, könnte eine Nachschlagetabelle mit einem Fallback auf eine tatsächliche Multiplikation genau das Richtige sein.
Wenn jedoch die Analyse des Programmablaufs durch den Compiler es nicht erlaubt, nachzuweisen , dass x immer in diesem Bereich liegt, kann diese Art der Optimierung nicht durchgeführt werden.
Aber solche Umstände sind sehr selten. Und wenn Ihr Code in einer neuen Umgebung ausgeführt wird, in der x 11 sein kann (vielleicht läuft er auf einem Gerät mit einer größeren Anzeige), kaboom . Und die Leistungsverbesserung war sehr wahrscheinlich in erster Linie nicht signifikant.
Es gibt Zeiten, in denen eine Mikrooptimierung angebracht ist, aber es gibt erhebliche Kosten für die Entwicklungs- und Testzeit. Tun Sie es nur, wenn tatsächliche Messungen anzeigen, dass es sich lohnt.
Für einen begrenzten Bereich können Sie eine Nachschlagetabelle verwenden:
%Vor%Das mag klingen albern (und es ist wahrscheinlich für diesen speziellen Fall), aber es ist oft praktisch für Dinge, wo es echte Kosten für die Berechnung gibt. Ich bin nur nicht sicher, dass die Multiplikation mit sieben zählt als einer dieser Fälle.
Für einen Anfang ist das Multiplizieren von x mit 7 (oder das Verschieben von x drei Bits, die übrig sind, dann das Subtrahieren von x ) eine Operation, die vollständig innerhalb der CPU ausgeführt werden kann. Bei einer Tabellensuche sehen Sie möglicherweise eine Multiplikation mit vier (zwei Bits nach links verschieben), gefolgt von einem Add, um die richtige Adresse zu erhalten, aber dann müssen Sie auf den Speicher zugreifen, um die eigentliche Suche durchzuführen - sogar mit Caching und all den anderen Erstaunliche Tricks, die die aktuellen CPUs können, werden wahrscheinlich die Dinge verlangsamen.
Es besteht auch eine gute Chance, dass Ihr Compiler bereits alle Tricks zur schnellen Multiplikation kennt. Wenn Ihre Sieben eine Konstante ist (oder const int oder gleichwertig), wird der Compiler wahrscheinlich den schnellsten Weg gewählt haben und es gibt eine gute Chance, dass die Compilerschreiber viel mehr über diese Art von Sachen wissen als normale Sterbliche :-) (a)
Aber in Fällen, in denen die Berechnungskosten relativ hoch sind, ist das Berechnen der Werte einmal und das Einbetten dieser Werte in Ihren Code als Nachschlagetabelle eine der Standardoptimierungsstrategien (Austauschzeit für Speicherplatz).
(a) Untersuchen Sie den folgenden Code:
%Vor% Bei der normalen Kompilation von gcc kommt mult7 heraus, da die Verschiebung drei übrig bleibt und den Trick subtrahiert:
Bei -O3 (was ich gerne den wahnsinnigen Optimierungslevel nennen würde), wird das Ganze in main mit:
Beachten Sie, dass diese Inlining-Aktion nur aufgrund der statischen Eigenschaft der Funktion möglich ist. Wenn sie für den Linker sichtbar wäre, müsste sie als separate Funktion verwaltet werden, falls eine andere Objektdatei sie aufrufen müsste.
Wenn Sie das static entfernen, wird es tatsächlich nicht-inlined mit dem gesamten Stack-Frame-Setup und dem Teardown, aber es verwendet zumindest den (vermutlich) effizienteren Trick, der unten erwähnt wird. Sie können den Stack-Frame-Code in gcc loswerden, wenn Sie -fomit-frame-pointer verwenden, vorausgesetzt, dass dies den Code nicht beeinträchtigt, aber dies beginnt, sich ein wenig in die dunkle Seite zu vertiefen :-)
Dieser Trick besteht darin, die Anweisung LEA zu verwenden, um edx auf eax * 8 zu setzen und dann eax davon zu subtrahieren. Die gleiche Theorie wie die sall/subl bei normaler Optimierung, nur etwas andere Mechanik.
Unterste Zeile, vertrauen Sie Ihrem Compiler. Wenn Sie num mit 7 multiplizieren möchten, verwenden Sie Folgendes:
Die Chancen stehen gut, dass Sie eine Verbesserung durch eine solche Mikrooptimierung erreichen können, wenn Sie auf die Makroebene (Auswahl von Algorithmen und Datenstrukturen usw.) schauen.
Die Art, wie ich es machen würde, wäre etwas wie
%Vor%ie. 2 ^ 3 = 8, dann subtrahiere die Zahl, die multipliziert wird, um ein Vielfaches von 7 zu erhalten.
Ich habe gerade den folgenden Code mit gcc kompiliert:
%Vor%und dies ist ein gdb-Dump von dem, zu dem es kompiliert wurde:
%Vor%Es scheint also so, als ob mein Rechner dreimal nach links verschoben wird und dann die Zahl, die multipliziert wird, subtrahiert wird, was gcc für optimal hält.
BEARBEITEN: Bei einem Optimierungslevel von mindestens 1 ( -O1 ), verwendet gcc den lea Trick:
Tatsächlich ist die effizienteste Möglichkeit, mit 7 zu multiplizieren, zu sein, den Multiplikationsoperator zu verwenden. Es hängt von der relativen Geschwindigkeit der jeweiligen Anweisungen auf der Zielplattform ab.
IMO, eine vollständige Antwort auf eine solche Interviewfrage sollte auch Folgendes erwähnen:
Diese Art der Optimierung wird normalerweise am besten dem Compiler / Compiler-Writer überlassen. (Tatsächlich scheint es aus einer anderen Antwort zu sein, dass gcc diesen Fall optimiert.)
Sie (als Programmierer) sollten nur Zeit darauf verwenden, wenn 1) ein echtes (messbares) Leistungsproblem vorliegt und 2) Ihr Profiler Ihnen sagt, dass die Aussagen, die Sie betrachten, leistungskritisch sind.
In seiner Antwort. Olaf schrieb dies:
"Ich stimme Stephen C nicht zu, wenn er Ihnen sagt, was Sie tun sollten (oder sollten). Wenn das alles so wäre, gäbe es keine Innovationen in der Softwareindustrie."
Es scheint, dass Olaf, dass einer oder mehrere der folgenden nicht glaubt:
Es stimmt, dass, wenn jeder immer nach dem Ratschlag handelte, den er erhalten würde, es weniger Innovation gäbe. Aber die Kehrseite ist, dass der Job in der Hand typischerweise nicht viel Innovation erfordert. (Und es erfordert selten Handoptimierung ...)
Außerdem, wenn das Ignorieren von Ratschlägen (Best Practice) eine Tugend wäre, dann würden 75% der Software-Ingenieure ihre Zeit damit verbringen, "Spaghetti", Assembler-Code oder die Ergebnisse einer Modeerscheinung aus den 1990er Jahren in der Designmethodik beizubehalten.
Sie sollten also zumindest den Rat verstehen und die möglichen Folgen abwägen, die sich daraus ergeben, wenn Sie ihn ignorieren. Wie der Chef, der seine "Innovation" (oder genauer, Zeitverschwendung) bei seinen Projekten schlecht sieht.
Wie Stephen C sagt: "Der effizienteste Weg, um 7 zu multiplizieren, kann der Multiplikationsoperator sein."
In diesem Artikel - Befehlswartezeiten und Durchsatz für AMD- und Intel x86-Prozessoren - Torbjörn Granlund vom Royal Das Institut für Technologie in Stockholm zeigt, dass eine vorzeichenlose Multiplikation 3/5 Taktzyklen in 32/64-Bit-Modi auf der K10-Architektur und 4/4 auf Sandy Bridge erfordert. Wenn Sie mehrere Multiples Back-to-Back ausführen müssen, kann der K10 jeden 32/64-Bit-Zyklus mit jedem weiteren Taktzyklus multiplizieren. Dies bedeutet, dass es auf drei Multiplikationen in verschiedenen Stufen gleichzeitig (3/1) und 2.5 (5/2) in 64-Bit arbeiten kann. Sandy Bridge gibt einen jeden / jeden Taktzyklus in 32/64 aus. Dies bedeutet zwei (4/2) oder vier (4/1) Anweisungen gleichzeitig.
Ich persönlich glaube, dass es Ihnen schwer fallen wird, dies durch eine Mehrschicht-Sequenz zu verbessern. Ich stimme Stephen C nicht zu, wenn er Ihnen sagt, was Sie tun sollten (oder sollten). Wenn alle das täte, gäbe es keine Innovationen in der Softwarebranche.
Also: Los!
Tags und Links c