Kürzlich hatte ich eine Frage zum Interview - Ich wurde gebeten, bitweise Operationen in Bezug auf die Leistung zu vergleichen.
Geben Sie eine kurze Beschreibung der Leistung verschiedener Bitoperationen.
Ich denke, dass diese Frage ziemlich allgemein und ziemlich maschinenspezifisch sein könnte, aber ich denke auch, dass es einige allgemeine Regeln darüber geben sollte, die Sie erwähnen müssen (und ich nicht:).
Also - was würden Sie antworten?
Ich sollte wahrscheinlich auch sagen, dass es eine gute Idee ist, ihre Leistung in C (oder C ++, was auch immer) zu vergleichen, weil ich annahm, dass diese Sprachen mehr Platz für den Compiler bieten bitbezogene Optimierungen.
Danke.
Okay, der vollständige Problemkontext.
Das Interview hatte mehrere Abschnitte und einige von ihnen waren wirklich ein Kinderspiel, manche waren ein Albtraum. Bit-bezogene Abschnitt war ziemlich hart und einschließlich der Fragen wie:
Fließkommazahlangaben, float , double
Schnell float - & gt; int Konvertierungen (und noch schneller, wenn Sie den Bereich kennen)
Das war nicht sehr schwierig, aber als letzte Frage in diesem bitbezogenen Abschnitt wurde ich gebeten, Bitoperationen, die ich kenne, zu zählen und ihre Leistung zu vergleichen.
Ich habe auf etwas nicht wirklich Beschreibendes wie geantwortet "es ist Architektur, Compiler, ... spezifisch, es wird nicht wirklich wichtig sein, bitweise ist schon ziemlich Low-Level" , aber ich denke Diese Antwort ist schlecht.
Ich würde mir vorstellen, dass sie Bitoperationen mit arithmetischen Äquivalenten vergleichen.
Beispiel: "Ist a = (a>>1) schneller als a = (a / 2) ?"
In vielen Fällen benötigen einfache Operationen wie diese (aus verschiedenen Gründen einschließlich Software- und Hardware-Optimierungen, Pipelining, Caching usw.) effektiv einen CPU-Zyklus, so dass Sie auf modernen Prozessoren wahrscheinlich keinen Unterschied sehen werden - aber wenn sie ausgeführt werden Wenn Sie mehrere Anweisungen parallel über mehrere ALUs ausführen, können Sie immer noch von einer besseren Ausnutzung der parallelen Pfade der CPU profitieren, wenn Sie arithmetische und bitweise Operationen mischen. Wenn Sie in einer höheren Programmiersprache schreiben, optimiert der Compiler Ihren Code sehr wahrscheinlich, um die bessere Form zu verwenden. Sie sehen also die gleiche Leistung, unabhängig davon, auf welche Art Sie Ihren Code schreiben!
Es gibt jedoch Fälle, in denen bitweise Operationen wesentlich schneller sein können als einfache Arithmetik / Logik - zum Beispiel können Sie einige Operationen auf alle Bytes in einem 32-Bit- oder 64-Bit-Wert mit einigen bitweisen Operationen anwenden (das heißt effektiv alle Bytes gleichzeitig verarbeiten), die sonst viel Schleifen- und Vergleichslogik erfordern würden, um inkrementell zu arbeiten. Sehen Sie hier für einige großartige Beispiele, was erreicht werden kann. In diesen Fällen kann oft ein erheblicher Leistungsvorteil erzielt werden. (Obwohl die genaue Verstärkung stark von der CPU abhängen kann, auf die Sie zielen)
(Alternativ könnten sie auch nur bedeuten "ist eine Schiebeoperation schneller als ein XOR", in diesem Fall ist bei modernen Prozessoren in den meisten Fällen die Antwort wahrscheinlich "nein" - die meisten bitweisen Operationen sind schnell. Aber das wäre a ziemlich sinnlose Frage zu stellen ...)
Das ist eine sehr merkwürdige Frage, die gestellt werden muss. Vor allem, weil die Sprache irrelevant sein sollte - solange Sie in einer kompilierten Sprache schreiben, sollte jede bitweise Operation bis zu einer einzigen Assembler-Anweisung kompiliert werden selbst in den einfachsten Assembler-Sprachen.
Zweitens, sobald diese einzelne Assembly-Anweisung den Prozessor trifft, sollte sie in einem einzigen Zyklus ausgewertet werden - bitweises Zeug ist einfach so einfach. Es ist möglich, dass ein platzhungriger Prozessor die Verschiebung in einigen Zyklen implementiert (sie benötigen viel mehr Schaltungen als die anderen, um schnell zu arbeiten), aber das erscheint auf modernen Maschinen ziemlich unwahrscheinlich, so dass sogar Verschiebungen ein Zyklus sein sollten Anweisungen.
Hier ist was Wikipedia zu dem Thema zu sagen hat:
Eine bitweise Operation funktioniert auf einem oder mehr Bitmuster oder Binärzahlen auf der Ebene ihrer einzelnen Bits. Bei den meisten älteren Mikroprozessoren bitweise Operationen sind etwas schneller als Additions- und Subtraktionsoperationen und normalerweise bedeutend schneller als Multiplikation und Division Operationen. Auf modernen Architekturen das ist nicht bitweise der Fall Operationen sind im Allgemeinen gleich Geschwindigkeit als Zusatz (obwohl noch schneller als Multiplikation).
Hoffe, das hilft!
Tags und Links c++ performance bits