Wann ist für eine Methode die Optimierung für Speicher im Vergleich zur Leistungsgeschwindigkeit vorzunehmen?

107

Ich habe vor kurzem bei Amazon interviewt. Während einer Codierungssitzung fragte der Interviewer, warum ich eine Variable in einer Methode deklariert habe. Ich erklärte meinen Prozess und er forderte mich auf, das gleiche Problem mit weniger Variablen zu lösen. Zum Beispiel (das war nicht aus dem Interview) habe ich mit Methode A begonnen und es dann durch Entfernen zu Methode B verbessert . Er war erfreut und sagte, dies würde die Speichernutzung durch diese Methode verringern.int s

Ich verstehe die Logik dahinter, aber meine Frage ist:

Wann ist es angebracht, Methode A gegen Methode B zu verwenden und umgekehrt?

Sie können sehen, dass Methode A eine höhere Speichernutzung hat, da sie int sdeklariert ist, aber nur eine Berechnung durchführen muss, d a + b. H. Andererseits hat Methode B eine geringere Speichernutzung, muss jedoch zwei Berechnungen durchführen, dh a + bzweimal. Wann verwende ich eine Technik über der anderen? Oder wird eine der Techniken immer der anderen vorgezogen? Was ist bei der Bewertung der beiden Methoden zu beachten?

Methode A:

private bool IsSumInRange(int a, int b)
{
    int s = a + b;

    if (s > 1000 || s < -1000) return false;
    else return true;
}

Methode B:

private bool IsSumInRange(int a, int b)
{
    if (a + b > 1000 || a + b < -1000) return false;
    else return true;
}
Corey P
quelle
229
Ich wette, dass ein moderner Compiler in beiden Fällen dieselbe Assembly generiert.
17 von 26
12
Ich habe die Frage auf den ursprünglichen Zustand zurückgesetzt, da Ihre Bearbeitung meine Antwort ungültig gemacht hat - bitte tun Sie das nicht! Wenn Sie eine Frage stellen, wie Sie Ihren Code verbessern können, ändern Sie die Frage nicht, indem Sie den Code auf die gezeigte Weise verbessern. Dadurch erscheinen die Antworten bedeutungslos.
Doc Brown
76
Warten Sie eine Sekunde, sie fragten, ob sie sich davon befreien könnten, int swährend sie mit diesen magischen Zahlen für obere und untere Schranken völlig in Ordnung sind?
null
34
Denken Sie daran: Profil vor dem Optimieren. Mit modernen Compilern können Methode A und Methode B auf denselben Code optimiert werden (unter Verwendung höherer Optimierungsstufen). Mit modernen Prozessoren könnten sie auch Anweisungen haben, die mehr als Addition in einer einzigen Operation ausführen.
Thomas Matthews
142
Weder; auf Lesbarkeit optimieren.
Andy

Antworten:

148

Anstatt darüber zu spekulieren, was passieren kann oder nicht, schauen wir uns das an. Ich muss C ++ verwenden, da ich keinen C # -Compiler zur Hand habe ( siehe auch das C # -Beispiel von VisualMelon ), aber ich bin sicher, dass die gleichen Prinzipien unabhängig davon gelten.

Wir werden die beiden Alternativen, denen Sie begegnet sind, in das Interview aufnehmen. Wir werden auch eine Version hinzufügen, die abswie in einigen Antworten vorgeschlagen verwendet wird.

#include <cstdlib>

bool IsSumInRangeWithVar(int a, int b)
{
    int s = a + b;

    if (s > 1000 || s < -1000) return false;
    else return true;
}

bool IsSumInRangeWithoutVar(int a, int b)
{
    if (a + b > 1000 || a + b < -1000) return false;
    else return true;
}

bool IsSumInRangeSuperOptimized(int a, int b) {
    return (abs(a + b) < 1000);
}

Jetzt kompiliere es ohne jegliche Optimierung: g++ -c -o test.o test.cpp

Jetzt können wir genau sehen, was dies erzeugt: objdump -d test.o

0000000000000000 <_Z19IsSumInRangeWithVarii>:
   0:   55                      push   %rbp              # begin a call frame
   1:   48 89 e5                mov    %rsp,%rbp
   4:   89 7d ec                mov    %edi,-0x14(%rbp)  # save first argument (a) on stack
   7:   89 75 e8                mov    %esi,-0x18(%rbp)  # save b on stack
   a:   8b 55 ec                mov    -0x14(%rbp),%edx  # load a and b into edx
   d:   8b 45 e8                mov    -0x18(%rbp),%eax  # load b into eax
  10:   01 d0                   add    %edx,%eax         # add a and b
  12:   89 45 fc                mov    %eax,-0x4(%rbp)   # save result as s on stack
  15:   81 7d fc e8 03 00 00    cmpl   $0x3e8,-0x4(%rbp) # compare s to 1000
  1c:   7f 09                   jg     27                # jump to 27 if it's greater
  1e:   81 7d fc 18 fc ff ff    cmpl   $0xfffffc18,-0x4(%rbp) # compare s to -1000
  25:   7d 07                   jge    2e                # jump to 2e if it's greater or equal
  27:   b8 00 00 00 00          mov    $0x0,%eax         # put 0 (false) in eax, which will be the return value
  2c:   eb 05                   jmp    33 <_Z19IsSumInRangeWithVarii+0x33>
  2e:   b8 01 00 00 00          mov    $0x1,%eax         # put 1 (true) in eax
  33:   5d                      pop    %rbp
  34:   c3                      retq

0000000000000035 <_Z22IsSumInRangeWithoutVarii>:
  35:   55                      push   %rbp
  36:   48 89 e5                mov    %rsp,%rbp
  39:   89 7d fc                mov    %edi,-0x4(%rbp)
  3c:   89 75 f8                mov    %esi,-0x8(%rbp)
  3f:   8b 55 fc                mov    -0x4(%rbp),%edx
  42:   8b 45 f8                mov    -0x8(%rbp),%eax  # same as before
  45:   01 d0                   add    %edx,%eax
  # note: unlike other implementation, result is not saved
  47:   3d e8 03 00 00          cmp    $0x3e8,%eax      # compare to 1000
  4c:   7f 0f                   jg     5d <_Z22IsSumInRangeWithoutVarii+0x28>
  4e:   8b 55 fc                mov    -0x4(%rbp),%edx  # since s wasn't saved, load a and b from the stack again
  51:   8b 45 f8                mov    -0x8(%rbp),%eax
  54:   01 d0                   add    %edx,%eax
  56:   3d 18 fc ff ff          cmp    $0xfffffc18,%eax # compare to -1000
  5b:   7d 07                   jge    64 <_Z22IsSumInRangeWithoutVarii+0x2f>
  5d:   b8 00 00 00 00          mov    $0x0,%eax
  62:   eb 05                   jmp    69 <_Z22IsSumInRangeWithoutVarii+0x34>
  64:   b8 01 00 00 00          mov    $0x1,%eax
  69:   5d                      pop    %rbp
  6a:   c3                      retq

000000000000006b <_Z26IsSumInRangeSuperOptimizedii>:
  6b:   55                      push   %rbp
  6c:   48 89 e5                mov    %rsp,%rbp
  6f:   89 7d fc                mov    %edi,-0x4(%rbp)
  72:   89 75 f8                mov    %esi,-0x8(%rbp)
  75:   8b 55 fc                mov    -0x4(%rbp),%edx
  78:   8b 45 f8                mov    -0x8(%rbp),%eax
  7b:   01 d0                   add    %edx,%eax
  7d:   3d 18 fc ff ff          cmp    $0xfffffc18,%eax
  82:   7c 16                   jl     9a <_Z26IsSumInRangeSuperOptimizedii+0x2f>
  84:   8b 55 fc                mov    -0x4(%rbp),%edx
  87:   8b 45 f8                mov    -0x8(%rbp),%eax
  8a:   01 d0                   add    %edx,%eax
  8c:   3d e8 03 00 00          cmp    $0x3e8,%eax
  91:   7f 07                   jg     9a <_Z26IsSumInRangeSuperOptimizedii+0x2f>
  93:   b8 01 00 00 00          mov    $0x1,%eax
  98:   eb 05                   jmp    9f <_Z26IsSumInRangeSuperOptimizedii+0x34>
  9a:   b8 00 00 00 00          mov    $0x0,%eax
  9f:   5d                      pop    %rbp
  a0:   c3                      retq

Wir können anhand der Stapeladressen (z. B. das In -0x4im mov %edi,-0x4(%rbp)Vergleich zum -0x14In mov %edi,-0x14(%rbp)) erkennen, dass IsSumInRangeWithVar()16 zusätzliche Bytes auf dem Stapel verwendet werden.

Da IsSumInRangeWithoutVar()der Stack keinen Speicherplatz zum Speichern des Zwischenwerts zuweist s, muss er neu berechnet werden, was dazu führt, dass diese Implementierung 2 Anweisungen länger dauert.

Komisch, IsSumInRangeSuperOptimized()sieht sehr ähnlich aus IsSumInRangeWithoutVar(), außer dass es zuerst -1000 und dann 1000 Sekunden sind.

Lassen Sie uns jetzt kompilieren nur mit den grundlegendsten Optimierungen: g++ -O1 -c -o test.o test.cpp. Das Ergebnis:

0000000000000000 <_Z19IsSumInRangeWithVarii>:
   0:   8d 84 37 e8 03 00 00    lea    0x3e8(%rdi,%rsi,1),%eax
   7:   3d d0 07 00 00          cmp    $0x7d0,%eax
   c:   0f 96 c0                setbe  %al
   f:   c3                      retq

0000000000000010 <_Z22IsSumInRangeWithoutVarii>:
  10:   8d 84 37 e8 03 00 00    lea    0x3e8(%rdi,%rsi,1),%eax
  17:   3d d0 07 00 00          cmp    $0x7d0,%eax
  1c:   0f 96 c0                setbe  %al
  1f:   c3                      retq

0000000000000020 <_Z26IsSumInRangeSuperOptimizedii>:
  20:   8d 84 37 e8 03 00 00    lea    0x3e8(%rdi,%rsi,1),%eax
  27:   3d d0 07 00 00          cmp    $0x7d0,%eax
  2c:   0f 96 c0                setbe  %al
  2f:   c3                      retq

Würden Sie sich das ansehen: Jede Variante ist identisch . Der Compiler ist in der Lage , etwas ganz klug zu tun: abs(a + b) <= 1000entsprechen unter a + b + 1000 <= 2000Berücksichtigung setbeist einen nicht signierten Vergleich, so dass eine negative Zahl eine sehr große positive Zahl wird. Der leaBefehl kann tatsächlich alle diese Hinzufügungen in einem Befehl ausführen und alle bedingten Verzweigungen beseitigen.

Für die Beantwortung Ihrer Frage müssen Sie fast immer nicht den Speicher oder die Geschwindigkeit optimieren, sondern die Lesbarkeit . Das Lesen von Code ist viel schwieriger als das Schreiben, und das Lesen von Code, der zur "Optimierung" missbraucht wurde, ist viel schwieriger als das Lesen von Code, der klar geschrieben wurde. Meistens sind diese "Optimierungen" vernachlässigbar oder haben in diesem Fall keine tatsächlichen Auswirkungen auf die Leistung.


Folgefrage: Was ändert sich, wenn dieser Code in einer interpretierten Sprache statt kompiliert ist? Ist die Optimierung dann wichtig oder hat sie das gleiche Ergebnis?

Messen wir! Ich habe die Beispiele in Python transkribiert:

def IsSumInRangeWithVar(a, b):
    s = a + b
    if s > 1000 or s < -1000:
        return False
    else:
        return True

def IsSumInRangeWithoutVar(a, b):
    if a + b > 1000 or a + b < -1000:
        return False
    else:
        return True

def IsSumInRangeSuperOptimized(a, b):
    return abs(a + b) <= 1000

from dis import dis
print('IsSumInRangeWithVar')
dis(IsSumInRangeWithVar)

print('\nIsSumInRangeWithoutVar')
dis(IsSumInRangeWithoutVar)

print('\nIsSumInRangeSuperOptimized')
dis(IsSumInRangeSuperOptimized)

print('\nBenchmarking')
import timeit
print('IsSumInRangeWithVar: %fs' % (min(timeit.repeat(lambda: IsSumInRangeWithVar(42, 42), repeat=50, number=100000)),))
print('IsSumInRangeWithoutVar: %fs' % (min(timeit.repeat(lambda: IsSumInRangeWithoutVar(42, 42), repeat=50, number=100000)),))
print('IsSumInRangeSuperOptimized: %fs' % (min(timeit.repeat(lambda: IsSumInRangeSuperOptimized(42, 42), repeat=50, number=100000)),))

Führen Sie mit Python 3.5.2 Folgendes aus:

IsSumInRangeWithVar
  2           0 LOAD_FAST                0 (a)
              3 LOAD_FAST                1 (b)
              6 BINARY_ADD
              7 STORE_FAST               2 (s)

  3          10 LOAD_FAST                2 (s)
             13 LOAD_CONST               1 (1000)
             16 COMPARE_OP               4 (>)
             19 POP_JUMP_IF_TRUE        34
             22 LOAD_FAST                2 (s)
             25 LOAD_CONST               4 (-1000)
             28 COMPARE_OP               0 (<)
             31 POP_JUMP_IF_FALSE       38

  4     >>   34 LOAD_CONST               2 (False)
             37 RETURN_VALUE

  6     >>   38 LOAD_CONST               3 (True)
             41 RETURN_VALUE
             42 LOAD_CONST               0 (None)
             45 RETURN_VALUE

IsSumInRangeWithoutVar
  9           0 LOAD_FAST                0 (a)
              3 LOAD_FAST                1 (b)
              6 BINARY_ADD
              7 LOAD_CONST               1 (1000)
             10 COMPARE_OP               4 (>)
             13 POP_JUMP_IF_TRUE        32
             16 LOAD_FAST                0 (a)
             19 LOAD_FAST                1 (b)
             22 BINARY_ADD
             23 LOAD_CONST               4 (-1000)
             26 COMPARE_OP               0 (<)
             29 POP_JUMP_IF_FALSE       36

 10     >>   32 LOAD_CONST               2 (False)
             35 RETURN_VALUE

 12     >>   36 LOAD_CONST               3 (True)
             39 RETURN_VALUE
             40 LOAD_CONST               0 (None)
             43 RETURN_VALUE

IsSumInRangeSuperOptimized
 15           0 LOAD_GLOBAL              0 (abs)
              3 LOAD_FAST                0 (a)
              6 LOAD_FAST                1 (b)
              9 BINARY_ADD
             10 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             13 LOAD_CONST               1 (1000)
             16 COMPARE_OP               1 (<=)
             19 RETURN_VALUE

Benchmarking
IsSumInRangeWithVar: 0.019361s
IsSumInRangeWithoutVar: 0.020917s
IsSumInRangeSuperOptimized: 0.020171s

Das Zerlegen in Python ist nicht sonderlich interessant, da der Bytecode "Compiler" nicht viel zur Optimierung beiträgt.

Die Leistung der drei Funktionen ist nahezu identisch. Wir könnten in Versuchung IsSumInRangeWithVar()geraten, dies zu tun, da es nur einen geringen Geschwindigkeitszuwachs gibt. Ich füge zwar hinzu, als ich verschiedene Parameter ausprobierte timeit, IsSumInRangeSuperOptimized()kam aber manchmal am schnellsten heraus, sodass ich vermute, dass dies eher externe Faktoren sind, die für den Unterschied verantwortlich sind, als ein wesentlicher Vorteil einer Implementierung.

Wenn dies wirklich leistungskritischer Code ist, ist eine interpretierte Sprache einfach eine sehr schlechte Wahl. Wenn ich das gleiche Programm mit pypy laufen lasse, bekomme ich:

IsSumInRangeWithVar: 0.000180s
IsSumInRangeWithoutVar: 0.001175s
IsSumInRangeSuperOptimized: 0.001306s

Allein die Verwendung von pypy, das die JIT-Kompilierung verwendet, um einen Großteil des Interpreter-Overheads zu eliminieren, hat zu einer Leistungsverbesserung von 1 oder 2 Größenordnungen geführt. Ich war ziemlich schockiert zu sehen, dass IsSumInRangeWithVar()es eine Größenordnung schneller ist als die anderen. Also habe ich die Reihenfolge der Benchmarks geändert und bin noch einmal gelaufen:

IsSumInRangeSuperOptimized: 0.000191s
IsSumInRangeWithoutVar: 0.001174s
IsSumInRangeWithVar: 0.001265s

Anscheinend geht es also nicht um die schnelle Implementierung, sondern um die Reihenfolge, in der ich das Benchmarking durchführe!

Ich würde gerne näher darauf eingehen, weil ich ehrlich gesagt nicht weiß, warum dies passiert. Aber ich glaube, es wurde darauf hingewiesen: Mikrooptimierungen wie die Angabe eines Zwischenwerts als Variable sind selten relevant. Bei einer interpretierten Sprache oder einem hochoptimierten Compiler besteht das erste Ziel immer noch darin, klaren Code zu schreiben.

Wenn weitere Optimierungen erforderlich sein könnten, Benchmarking . Denken Sie daran, dass die besten Optimierungen nicht von den kleinen Details, sondern vom größeren algorithmischen Bild herrühren: pypy wird für die wiederholte Auswertung derselben Funktion um eine Größenordnung schneller sein als cpython, da es schnellere Algorithmen verwendet (JIT-Compiler vs. Interpretation), um das zu evaluieren Programm. Und der codierte Algorithmus ist ebenfalls zu berücksichtigen: Eine Suche in einem B-Baum ist schneller als eine verknüpfte Liste.

Nachdem Sie sichergestellt haben, dass Sie die richtigen Tools und Algorithmen für den Job verwenden, sollten Sie sich darauf vorbereiten, tief in die Details des Systems einzutauchen. Die Ergebnisse können selbst für erfahrene Entwickler sehr überraschend sein. Aus diesem Grund müssen Sie einen Benchmark haben, um die Änderungen zu quantifizieren.

Phil Frost
quelle
6
Um ein Beispiel in C # bereitzustellen : SharpLab erstellt für beide Methoden identische asm (Desktop CLR v4.7.3130.00 (clr.dll) auf x86)
VisualMelon
2
@VisualMelon lustigerweise die positive Prüfung: "return (((a + b)> = -1000) && ((a + b) <= 1000))" ergibt ein anderes Ergebnis. : sharplab.io/…
Pieter B
12
Die Lesbarkeit kann möglicherweise die Optimierung eines Programms erleichtern. Der Compiler kann einfach umschreiben, um eine entsprechende Logik wie oben zu verwenden, nur wenn er tatsächlich herausfindet, was Sie versuchen. Wenn Sie viele Bithacks der alten Schule verwenden , zwischen Ints und Zeigern hin- und herschieben, veränderlichen Speicher usw. wiederverwenden, kann es für den Compiler viel schwieriger sein, zu beweisen, dass eine Transformation äquivalent ist, und es bleibt nur, was Sie geschrieben haben , die suboptimal sein kann.
Leushenko
1
@ Corey siehe bearbeiten.
Phil Frost
2
@ Corey: Diese Antwort sagt Ihnen genau, was ich in meiner Antwort geschrieben habe: Es gibt keinen Unterschied, wenn Sie einen anständigen Compiler verwenden, und stattdessen konzentrieren Sie sich auf die Lesbarkeit. Natürlich sieht es besser fundiert aus - vielleicht glauben Sie mir jetzt.
Doc Brown
67

So beantworten Sie die angegebene Frage:

Wann ist für eine Methode die Optimierung für Speicher im Vergleich zur Leistungsgeschwindigkeit vorzunehmen?

Es gibt zwei Dinge, die Sie festlegen müssen:

  • Was schränkt Ihre Bewerbung ein?
  • Wo kann ich den größten Teil dieser Ressource zurückgewinnen?

Um die erste Frage beantworten zu können, müssen Sie die Leistungsanforderungen für Ihre Anwendung kennen. Wenn es keine Leistungsanforderungen gibt, gibt es keinen Grund, auf die eine oder andere Weise zu optimieren. Die Leistungsanforderungen helfen Ihnen, an den Ort von "gut genug" zu gelangen.

Die Methode, die Sie alleine bereitgestellt haben, würde für sich genommen keine Leistungsprobleme verursachen. Vielleicht müssen Sie jedoch innerhalb einer Schleife und bei der Verarbeitung einer großen Datenmenge etwas anders darüber nachdenken, wie Sie das Problem angehen.

Erkennen, was die Anwendung einschränkt

Beginnen Sie mit einem Systemmonitor, das Verhalten Ihrer Anwendung zu untersuchen. Behalten Sie die CPU-, Festplatten-, Netzwerk- und Speichernutzung im Auge, während sie ausgeführt wird. Ein oder mehrere Gegenstände werden ausgereizt, während alles andere mäßig genutzt wird (es sei denn, Sie treffen die perfekte Balance, aber das passiert so gut wie nie).

Wenn Sie genauer hinsehen müssen, verwenden Sie normalerweise einen Profiler . Es gibt Speicher- und Prozessprofiler , die verschiedene Dinge messen. Das Erstellen von Profilen hat zwar erhebliche Auswirkungen auf die Leistung, Sie instrumentieren jedoch Ihren Code, um herauszufinden, was nicht stimmt.

Angenommen, Ihre CPU- und Festplattenauslastung ist am höchsten. Sie suchen zunächst nach "Hot Spots" oder Code, der entweder häufiger als der Rest aufgerufen wird oder einen erheblich längeren Prozentsatz der Verarbeitung beansprucht.

Wenn Sie keine Hotspots finden können, beginnen Sie mit der Suche nach Speicher. Möglicherweise erstellen Sie mehr Objekte als erforderlich, und Ihre Speicherbereinigung läuft über die Zeit hinaus.

Leistung zurückfordern

Denken Sie kritisch. Die folgende Liste der Änderungen richtet sich nach der Höhe der Kapitalrendite:

  • Architektur: Suchen Sie nach Kommunikationsengpässen
  • Algorithmus: Die Art und Weise, wie Sie Daten verarbeiten, muss möglicherweise geändert werden
  • Hot Spots: Wenn Sie minimieren, wie oft Sie den Hot Spot anrufen, können Sie einen großen Bonus erzielen
  • Mikrooptimierungen: Es ist nicht üblich, aber manchmal müssen Sie wirklich an kleinere Optimierungen denken (wie das von Ihnen bereitgestellte Beispiel), insbesondere wenn es sich um einen Hotspot in Ihrem Code handelt.

In solchen Situationen müssen Sie die wissenschaftliche Methode anwenden. Überlegen Sie sich eine Hypothese, nehmen Sie die Änderungen vor und testen Sie sie. Wenn Sie Ihre Leistungsziele erreichen, sind Sie fertig. Wenn nicht, fahren Sie mit dem nächsten Punkt in der Liste fort.


Beantwortung der Frage in Fettdruck:

Wann ist es angebracht, Methode A gegen Methode B zu verwenden und umgekehrt?

Ehrlich gesagt ist dies der letzte Schritt bei dem Versuch, mit Leistungs- oder Speicherproblemen umzugehen. Die Auswirkungen von Methode A im Vergleich zu Methode B sind je nach Sprache und Plattform (in einigen Fällen) sehr unterschiedlich.

Nahezu jede kompilierte Sprache mit einem halbwegs anständigen Optimierer generiert mit jeder dieser Strukturen einen ähnlichen Code. Diese Annahmen gelten jedoch nicht unbedingt für proprietäre Sprachen und Spielzeugsprachen, für die es keinen Optimierer gibt.

Welche Option eine bessere Auswirkung hat, hängt davon ab, ob sumes sich um eine Stapelvariable oder eine Heap-Variable handelt. Dies ist eine Auswahl der Sprachimplementierung. In C, C ++ und Java sind beispielsweise Zahlenprimitive wie a intstandardmäßig Stapelvariablen. Ihr Code hat keine größeren Auswirkungen auf den Arbeitsspeicher, wenn er einer Stapelvariablen zugewiesen wird, als dies bei vollständig integriertem Code der Fall wäre.

Andere Optimierungen, die Sie möglicherweise in C-Bibliotheken finden (insbesondere in älteren), bei denen Sie sich entscheiden müssen, ob Sie ein zweidimensionales Array zuerst nach unten oder zuerst nach oben kopieren möchten, sind plattformabhängige Optimierungen. Es erfordert einige Kenntnisse darüber, wie der Chipsatz, auf den Sie abzielen, den Speicherzugriff am besten optimiert. Es gibt subtile Unterschiede zwischen den Architekturen.

Fazit ist, dass Optimierung eine Kombination aus Kunst und Wissenschaft ist. Es erfordert kritisches Denken sowie ein gewisses Maß an Flexibilität bei der Herangehensweise an das Problem. Suchen Sie nach großen Dingen, bevor Sie kleine Dinge beschuldigen.

Berin Loritsch
quelle
2
Diese Antwort konzentriert sich am meisten auf meine Frage und lässt sich von meinen Codierungsbeispielen, dh Methode A und Methode B, nicht einfangen.
Corey P
18
Ich bin der Meinung, dass dies die allgemeine Antwort auf die Frage ist, wie Leistungsengpässe behoben werden können. Es ist jedoch schwierig, die relative Speichernutzung einer bestimmten Funktion anhand von 4 oder 5 Variablen zu ermitteln, die diese Methode verwenden. Ich frage mich auch, wie relevant diese Optimierungsstufe ist, wenn der Compiler (oder Interpreter) dies wegoptimieren kann oder nicht.
Eric
@Eric, wie gesagt, die letzte Kategorie der Leistungsverbesserung wären Ihre Mikrooptimierungen. Die einzige Möglichkeit zu erraten, ob dies Auswirkungen hat, besteht darin, die Leistung / den Speicher in einem Profiler zu messen. Es ist selten, dass sich diese Art von Verbesserungen auszahlt, aber bei zeitsensiblen Leistungsproblemen in Simulatoren können ein paar gut platzierte Änderungen der Unterschied sein, ob Sie Ihr Zeitziel erreichen oder nicht. Ich glaube, ich kann einerseits zählen, wie oft es sich in über 20 Jahren Arbeit an Software ausgezahlt hat, aber es ist nicht Null.
Berin Loritsch
@BerinLoritsch Auch hier stimme ich Ihnen im Allgemeinen zu, in diesem speziellen Fall jedoch nicht. Ich habe meine eigene Antwort gegeben, aber ich habe persönlich keine Tools gesehen, die Ihnen Aufschluss darüber geben, wie Sie Leistungsprobleme im Zusammenhang mit der Stapelspeichergröße einer Funktion identifizieren können.
Eric
@ DocBrown, das habe ich behoben. In Bezug auf die zweite Frage stimme ich Ihnen ziemlich zu.
Berin Loritsch
45

"dies würde das Gedächtnis reduzieren" - em, nein. Selbst wenn dies der Fall wäre (was für einen anständigen Compiler nicht der Fall ist), wäre der Unterschied für eine reale Situation höchstwahrscheinlich vernachlässigbar.

Ich würde jedoch empfehlen, Methode A * zu verwenden (Methode A mit einer geringfügigen Änderung):

private bool IsSumInRange(int a, int b)
{
    int sum = a + b;

    if (sum > 1000 || sum < -1000) return false;
    else return true;
    // (yes, the former statement could be cleaned up to
    // return abs(sum)<=1000;
    // but let's ignore this for a moment)
}

aber aus zwei völlig unterschiedlichen gründen:

  • Indem Sie der Variablen seinen erklärenden Namen geben, wird der Code klarer

  • Es wird vermieden, dass der Code zweimal dieselbe Summierungslogik enthält, sodass der Code mehr TROCKEN wird, was bedeutet, dass weniger Fehler für Änderungen anfällig sind.

Doc Brown
quelle
36
Ich würde es noch weiter aufräumen und mit "return sum> -1000 && sum <1000;"
17 von 26
36
@Corey Jeder anständige Optimierer verwendet ein CPU-Register für die sumVariable, was zu einer Speicherauslastung von Null führt. Und selbst wenn nicht, ist dies nur ein einziges Wort der Erinnerung in einer "Blatt" -Methode. In Anbetracht dessen, wie unglaublich speicherverschwenderisch Java oder C # aufgrund ihres GC- und Objektmodells sein können, verwendet eine lokale intVariable buchstäblich keinen erkennbaren Speicher. Dies ist eine sinnlose Mikrooptimierung.
Amon
10
@Corey: Wenn es " etwas komplexer" ist, wird es wahrscheinlich nicht zu einer "merklichen Speichernutzung". Vielleicht, wenn Sie ein wirklich komplexeres Beispiel konstruieren, aber das macht es zu einer anderen Frage. Beachten Sie auch, dass die Laufzeitumgebung bei komplexen Zwischenergebnissen möglicherweise intern temporäre Objekte erstellt, nur weil Sie keine bestimmte Variable für einen Ausdruck erstellen. Dies hängt also vollständig von den Details der Sprache, der Umgebung, der Optimierungsstufe und ab was auch immer du "bemerkbar" nennst.
Doc Brown
8
Zusätzlich zu den obigen Punkten bin ich mir ziemlich sicher, wie C # / Java sumein Implementierungsdetail speichern soll , und ich bezweifle, dass irgendjemand ein überzeugendes Argument dafür liefern könnte, ob ein alberner Trick wie das Vermeiden eines Lokals intdazu führen würde oder nicht diese Menge an Speicherbedarf auf lange Sicht. Die Lesbarkeit von IMO ist wichtiger. Die Lesbarkeit kann subjektiv sein, aber FWIW, ich persönlich würde es vorziehen, dass Sie niemals zweimal dieselbe Berechnung durchführen, nicht für die CPU-Auslastung, sondern weil ich Ihren Zusatz nur einmal überprüfen muss, wenn ich nach einem Fehler Ausschau halte.
JRH
2
... beachten Sie auch , dass Müll Sprachen gesammelt im Allgemeinen ein nicht vorhersehbar ist, „Meer der Erinnerung am laufenden Band“ , die (für C # sowieso) kann nur bis zu reinigen , wenn nötig , ich erinnere mich , ein Programm zu machen , die Gigabyte RAM zugewiesen und es nur gestartet " aufräumen "nach sich selbst, als der Speicher knapp wurde. Wenn der GC nicht ausgeführt werden muss, dauert es möglicherweise etwas länger und Sie sparen Ihre CPU für dringendere Aufgaben.
JRH
35

Sie können es besser machen als beide mit

return (abs(a + b) > 1000);

Die meisten Prozessoren (und daher auch Compiler) können abs () in einer einzigen Operation ausführen. Sie haben nicht nur weniger Summen, sondern auch weniger Vergleiche, die in der Regel rechenintensiver sind. Außerdem wird die Verzweigung entfernt, was bei den meisten Prozessoren sehr viel schlimmer ist, da Pipelining nicht mehr möglich ist.

Der Interviewer ist, wie andere Antworten sagten, eine Pflanze und hat nichts damit zu tun, ein technisches Interview zu führen.

Das heißt, seine Frage ist gültig. Und die Antwort darauf, wann und wie Sie optimieren, ist, wann Sie die Notwendigkeit bewiesen haben und ein Profil erstellt haben, um genau zu beweisen, welche Teile dies benötigen . Knuth ist bekannt dafür, dass vorzeitige Optimierung die Wurzel allen Übels ist, weil es zu einfach ist, unwichtige Abschnitte zu vergolden oder Änderungen (wie die Ihres Interviewers) vorzunehmen, die keine Wirkung haben, während die Stellen fehlen, die sie wirklich brauchen. Bis Sie einen eindeutigen Beweis dafür haben, dass dies wirklich notwendig ist, ist die Klarheit des Codes das wichtigere Ziel.

Edit FabioTurati weist zu Recht darauf hin, dass dies der entgegengesetzte logische Sinn zum Original ist (mein Fehler!) Und dass dies eine weitere Auswirkung von Knuths Zitat darstellt, bei dem wir das Risiko eingehen, den Code zu brechen, während wir versuchen, ihn zu optimieren.

Graham
quelle
2
@Corey, ich bin mir ziemlich sicher, dass der Graham die Anfrage "er hat mich herausgefordert, dasselbe Problem mit weniger Variablen zu lösen" wie erwartet ansteckt . Wenn ich der Interviewer sein würde, würde ich diese Antwort erwarten, bewegt sich nicht a+bin ifund es zweimal tun. Sie verstehen es falsch. "Er war erfreut und sagte, dass dies die Speichernutzung durch diese Methode verringern würde ." Sie sollten es nicht ernst nehmen, hier Fragen zu stellen. Hast du einen Job bekommen? Meiner Meinung nach
hast
1
Sie wenden gleichzeitig 2 Transformationen an: Sie haben die 2 Bedingungen mit in 1 umgewandelt, abs()und Sie haben auch eine einzige return, anstatt eine zu haben, wenn die Bedingung wahr ist ("if branch") und eine andere, wenn sie falsch ist ( "else branch"). Wenn Sie Code wie folgt ändern, müssen Sie vorsichtig sein: Es besteht die Gefahr, dass Sie versehentlich eine Funktion schreiben, die true zurückgibt, wenn sie false zurückgibt, und umgekehrt. Welches ist genau das, was hier passiert ist. Ich weiß, dass Sie sich auf eine andere Sache konzentriert haben, und Sie haben gute Arbeit geleistet. Trotzdem hätte es Sie leicht den Job kosten können ...
Fabio Turati
2
@FabioTurati Gut gesehen - danke! Ich werde die Antwort aktualisieren. Und es geht um Refactoring und Optimierung, was das Zitat von Knuth noch relevanter macht. Wir sollten beweisen, dass wir die Optimierung brauchen, bevor wir das Risiko eingehen.
Graham
2
Die meisten Prozessoren (und daher auch Compiler) können abs () in einer einzigen Operation ausführen. Leider nicht für ganze Zahlen. ARM64 verfügt über eine bedingte Negation, die verwendet werden kann, wenn bereits Flags von einem gesetzt sind adds, und ARM hat Reverse-Sub ( rsblt= Reverse-Sub, wenn weniger als) angegeben, aber für alle anderen Befehle sind mehrere zusätzliche Befehle erforderlich, um abs(a+b)oder zu implementieren abs(a). godbolt.org/z/Ok_Con zeigt die Ausgabe von x86-, ARM-, AArch64-, PowerPC-, MIPS- und RISC-V-ASM an. Nur durch Umwandlung des Vergleichs in einen Range-Check (unsigned)(a+b+999) <= 1998Ukann gcc ihn optimieren, wie in Phils Antwort.
Peter Cordes
2
Der "verbesserte" Code in dieser Antwort ist immer noch falsch, da er eine andere Antwort für ergibt IsSumInRange(INT_MIN, 0). Der ursprüngliche Code gibt zurück, falseweil INT_MIN+0 > 1000 || INT_MIN+0 < -1000; aber der "neue und verbesserte" Code gibt trueda zurück abs(INT_MIN+0) < 1000. (In einigen Sprachen wird eine Ausnahme
ausgelöst
16

Wann ist es angebracht, Methode A gegen Methode B zu verwenden und umgekehrt?

Hardware ist billig; Programmierer sind teuer . Die Kosten für die Zeit, die Sie beide für diese Frage verschwendet haben, sind wahrscheinlich weitaus schlimmer als jede Antwort.

Ungeachtet dessen würden die meisten modernen Compiler eine Möglichkeit finden, die lokale Variable in einem Register zu optimieren (anstatt Stapelspeicher zuzuweisen), sodass die Methoden hinsichtlich des ausführbaren Codes wahrscheinlich identisch sind. Aus diesem Grund würden die meisten Entwickler die Option auswählen, die die Absicht am klarsten kommuniziert (siehe Schreiben von wirklich offensichtlichem Code (ROC) ). Meiner Meinung nach wäre das Methode A.

Auf der anderen Seite, wenn dies eine rein akademische Übung ist, können Sie mit Methode C das Beste aus beiden Welten haben:

private bool IsSumInRange(int a, int b)
{
    a += b;
    return (a >= -1000 && a <= 1000);
}
John Wu
quelle
17
a+=bist ein guter Trick, aber ich muss erwähnen (nur für den Fall, dass dies nicht aus dem Rest der Antwort hervorgeht), dass es aus meiner Erfahrung heraus sehr schwierig sein kann, Fehler zu beheben und zu warten.
JRH
1
Ich stimme zu @jrh. Ich bin ein starker Befürworter von ROC, und so etwas ist alles andere als.
John Wu
3
"Hardware ist billig, Programmierer sind teuer." In der Welt der Unterhaltungselektronik ist diese Aussage falsch. Wenn Sie Millionen von Einheiten verkaufen, ist es eine sehr gute Investition, 500.000 USD an zusätzlichen Entwicklungskosten auszugeben, um 0,10 USD an Hardwarekosten pro Einheit zu sparen.
Bart van Ingen Schenau
2
@JohnWu: Sie haben die ifPrüfung vereinfacht , aber vergessen, das Ergebnis des Vergleichs umzukehren. Ihre Funktion kehrt nun , truewenn a + bist nicht im Bereich. Fügen Sie entweder ein !an die Außenseite der Bedingung ( return !(a > 1000 || a < -1000)) an oder verteilen Sie die !invertierenden Tests, um return a <= 1000 && a >= -1000;Or zu erhalten, damit die Reichweitenkontrolle return -1000 <= a && a <= 1000;
reibungslos
1
@JohnWu: An den Randbereichen ist die verteilte Logik immer noch geringfügig abweichend und erfordert <=/ >=, nicht </ >(mit </ >werden 1000 und -1000 als außerhalb des Bereichs liegend behandelt, der ursprüngliche Code behandelt sie als innerhalb des Bereichs liegend).
ShadowRanger
11

Ich würde für die Lesbarkeit optimieren. Methode X:

private bool IsSumInRange(int number1, int number2)
{
    return IsValueInRange(number1+number2, -1000, 1000);
}

private bool IsValueInRange(int Value, int Lowerbound, int Upperbound)
{
    return  (Value >= Lowerbound && Value <= Upperbound);
}

Kleine Methoden, die nur eine Sache tun, über die man aber leicht nachdenken kann.

(Dies ist eine persönliche Präferenz. Ich mag positive statt negative Tests. Ihr ursprünglicher Code testet tatsächlich, ob der Wert NICHT außerhalb des Bereichs liegt.)

Pieter B
quelle
5
Diese. (Überstimmte Kommentare darüber waren ähnlich bezüglich der Lesbarkeit). Als wir vor 30 Jahren mit Computern arbeiteten, die weniger als 1 MB RAM hatten, war es notwendig, die Leistung zu reduzieren - genau wie beim Jahr-2000-Problem sollten einige hunderttausend Datensätze erstellt werden, bei denen jeweils ein paar Bytes Speicher aufgrund von nicht verwendeten VARs und verschwendet werden Verweise usw. und es summiert sich schnell, wenn Sie nur 256k RAM haben. Jetzt, da wir es mit Computern zu tun haben, die mehrere Gigabyte RAM haben, ist es kein gutes Geschäft, auch nur ein paar MB RAM zu sparen, verglichen mit der Lesbarkeit und Wartbarkeit von Code.
Ivanivan
@ivanivan: Ich glaube nicht, dass es beim "y2k-Problem" wirklich um das Gedächtnis ging. Vom Standpunkt der Dateneingabe aus ist die Eingabe von zwei Ziffern effizienter als die Eingabe von vier, und es ist einfacher, die eingegebenen Daten beizubehalten, als sie in eine andere Form zu konvertieren.
Supercat
10
Jetzt müssen Sie 2 Funktionen nachverfolgen, um zu sehen, was passiert. Sie können es nicht zum Nennwert annehmen, da Sie anhand des Namens nicht erkennen können, ob es sich um inklusive oder exklusive Grenzen handelt. Wenn Sie diese Informationen hinzufügen, ist der Name der Funktion länger als der Code, der sie ausdrückt.
Peter
1
Optimieren Sie die Lesbarkeit und erstellen Sie kleine, leicht verständliche Funktionen - stimmen Sie zu. Aber ich stimme nicht stark , dass die Umbenennung aund bzu number1und number2Hilfsmittel Lesbarkeit in keiner Weise. Auch Ihre Benennung der Funktionen ist inkonsistent: Warum wird IsSumInRangeder Bereich hartcodiert IsValueInRange, wenn er als Argumente akzeptiert wird?
Abfahrt
Die 1. Funktion kann überlaufen. (Wie der Code anderer Antworten.) Obwohl die Komplexität des überlaufsicheren Codes ein Argument für die Implementierung in eine Funktion ist.
philipxy
6

Kurz gesagt, ich denke nicht, dass diese Frage für das aktuelle Computing relevant ist, aber aus historischer Sicht ist es eine interessante Denkübung.

Ihr Interviewer ist wahrscheinlich ein Fan des Mythical Man Month. In dem Buch macht Fred Brooks geltend, dass Programmierer im Allgemeinen zwei Versionen der wichtigsten Funktionen in ihrer Toolbox benötigen: eine speicheroptimierte Version und eine CPU-optimierte Version. Fred stützte sich dabei auf seine Erfahrung bei der Entwicklung des Betriebssystems IBM System / 360, bei dem Maschinen möglicherweise nur 8 Kilobyte RAM haben. In solchen Maschinen kann der für lokale Variablen in Funktionen erforderliche Speicher möglicherweise wichtig sein, insbesondere wenn der Compiler sie nicht effektiv optimiert hat (oder wenn Code direkt in Assemblersprache geschrieben wurde).

In der gegenwärtigen Zeit, glaube ich, wird es Ihnen schwer fallen, ein System zu finden, bei dem das Vorhandensein oder Fehlen einer lokalen Variablen in einer Methode einen spürbaren Unterschied macht. Damit eine Variable eine Rolle spielt, muss die Methode rekursiv sein, wobei eine tiefe Rekursion erwartet wird. Selbst dann ist es wahrscheinlich, dass die Stapeltiefe überschritten wird, was zu Stack Overflow-Ausnahmen führt, bevor die Variable selbst ein Problem verursacht. Das einzige reale Szenario, in dem es zu Problemen kommen kann, sind sehr große Arrays, die in einer rekursiven Methode auf dem Stapel zugeordnet sind. Aber das ist auch unwahrscheinlich, da ich denke, dass die meisten Entwickler zweimal über unnötige Kopien großer Arrays nachdenken würden.

Eric
quelle
4

Nach der Zuweisung ist s = a + b; Die Variablen a und b werden nicht mehr verwendet. Daher wird für s kein Speicher verwendet, wenn Sie keinen vollständig gehirngeschädigten Compiler verwenden. Speicher, der ohnehin für a und b verwendet wurde, wird wiederverwendet.

Aber diese Funktion zu optimieren ist völliger Unsinn. Wenn Sie Platz sparen könnten, wären es vielleicht 8 Bytes, während die Funktion ausgeführt wird (was wiederhergestellt wird, wenn die Funktion zurückkehrt), also absolut sinnlos. Wenn Sie Zeit sparen könnten, wären es einzelne Nanosekunden. Dies zu optimieren ist reine Zeitverschwendung.

gnasher729
quelle
3

Variablen vom Typ lokaler Werte werden auf dem Stack zugewiesen oder verwenden (wahrscheinlicher für solche kleinen Codeteile) Register im Prozessor und sehen niemals RAM. So oder so sind sie kurzlebig und nichts, worüber man sich Sorgen machen müsste. Sie ziehen die Speichernutzung in Betracht, wenn Sie Datenelemente in möglicherweise großen und langlebigen Sammlungen puffern oder in eine Warteschlange stellen müssen.

Dann kommt es darauf an, was Sie für Ihre Anwendung am meisten interessieren. Verarbeitungsgeschwindigkeit? Reaktionszeit? Speicherbedarf? Wartbarkeit? Konsequenz im Design? Ganz Dir überlassen.

Martin Maat
quelle
4
Nitpicking: Zumindest .NET (die Sprache des Posts ist nicht spezifiziert) garantiert nicht, dass lokale Variablen "auf dem Stack" zugewiesen werden. Siehe "Der Stack ist ein Implementierungsdetail" von Eric Lippert.
JRH
1
@jrh Lokale Variablen auf Stack oder Heap mögen ein Implementierungsdetail sein, aber wenn jemand wirklich eine Variable auf dem Stack haben möchte, gibt es sie stackallocund jetzt Span<T>. Möglicherweise nützlich an einem Hot Spot nach dem Profilieren. Darüber hinaus implizieren einige der Dokumente zu Strukturen, dass sich Werttypen möglicherweise auf dem Stapel befinden, während dies bei Referenztypen nicht der Fall ist. Wie auch immer, am besten vermeiden Sie ein bisschen GC.
Bob
2

Wie andere Antworten bereits sagten, müssen Sie überlegen, wofür Sie optimieren.

In diesem Beispiel vermute ich, dass jeder anständige Compiler für beide Methoden gleichwertigen Code generiert, sodass die Entscheidung keine Auswirkungen auf die Laufzeit oder den Arbeitsspeicher hat!

Dies wirkt sich auf die Lesbarkeit des Codes aus. (Code ist nur für Menschen lesbar, nicht nur für Computer.) Es gibt keinen allzu großen Unterschied zwischen den beiden Beispielen. Wenn alle anderen Dinge gleich sind, halte ich Kürze für eine Tugend, daher würde ich wahrscheinlich Methode B wählen. Aber alle anderen Dinge sind selten gleich, und in einem komplexeren realen Fall könnte dies einen großen Effekt haben.

Dinge, die man beachten muss:

  • Hat der Zwischenausdruck irgendwelche Nebenwirkungen? Wenn es unreine Funktionen aufruft oder Variablen aktualisiert, ist das Duplizieren natürlich eine Frage der Korrektheit, nicht nur des Stils.
  • Wie komplex ist der Zwischenausdruck? Wenn es viele Berechnungen durchführt und / oder Funktionen aufruft, kann es der Compiler möglicherweise nicht optimieren und dies würde die Leistung beeinträchtigen. (Allerdings, wie Knuth sagte , "sollten wir kleine Wirkungsgrade vergessen, sagen wir in 97% der Fälle".)
  • Hat die Zwischenvariable eine Bedeutung ? Könnte ihm ein Name gegeben werden, der erklärt, was los ist? Ein kurzer, aber informativer Name könnte den Code besser erklären, während ein bedeutungsloser nur visuelles Rauschen ist.
  • Wie lang ist der Zwischenausdruck? Wenn es lang ist, kann das Duplizieren den Code länger und schwerer lesbar machen (insbesondere, wenn ein Zeilenumbruch erzwungen wird). Andernfalls könnte die Duplizierung insgesamt kürzer sein.
Scherze
quelle
1

Wie viele der Antworten gezeigt haben, wird der Versuch, diese Funktion mit modernen Compilern abzustimmen, keinen Unterschied machen. Ein Optimierer kann höchstwahrscheinlich die beste Lösung finden (stimmen Sie mit der Antwort ab, die den Assembler-Code zum Beweis enthält!). Sie gaben an, dass der Code im Interview nicht genau der Code war, den Sie vergleichen sollten. Vielleicht macht das tatsächliche Beispiel also etwas mehr Sinn.

Aber schauen wir uns diese Frage noch einmal an: Dies ist eine Interviewfrage. Das eigentliche Problem ist also, wie sollten Sie darauf antworten, vorausgesetzt, Sie möchten versuchen, den Job zu bekommen?

Nehmen wir auch an, der Interviewer weiß, wovon er spricht und versucht nur zu sehen, was Sie wissen.

Ich würde erwähnen, dass der erste, der den Optimierer ignoriert, möglicherweise eine temporäre Variable auf dem Stapel erstellt, während der zweite dies nicht tut, aber die Berechnung zweimal durchführen würde. Daher verbraucht der erste mehr Speicher, ist aber schneller.

Sie können auch erwähnen, dass für eine Berechnung möglicherweise eine temporäre Variable zum Speichern des Ergebnisses erforderlich ist (damit es verglichen werden kann). Es spielt also keine Rolle, ob Sie diese Variable benennen oder nicht.

Ich würde dann erwähnen, dass in der Realität der Code optimiert und höchstwahrscheinlich äquivalenter Maschinencode generiert würde, da alle Variablen lokal sind. Es hängt jedoch davon ab, welchen Compiler Sie verwenden (vor nicht allzu langer Zeit konnte ich eine nützliche Leistungsverbesserung erzielen, indem ich eine lokale Variable in Java als "final" deklarierte).

Sie könnten erwähnen, dass der Stapel auf jeden Fall auf seiner eigenen Speicherseite liegt. Wenn Ihre zusätzliche Variable also nicht dazu führt, dass der Stapel die Seite überläuft, reserviert er in Wirklichkeit keinen weiteren Speicher. Wenn es überläuft, wird es jedoch eine ganz neue Seite wollen.

Ich würde erwähnen, dass ein realistischeres Beispiel die Wahl sein könnte, ob ein Cache verwendet werden soll, um die Ergebnisse vieler Berechnungen zu speichern, oder nicht, und dies würde eine Frage von CPU vs. Speicher aufwerfen.

All dies zeigt, dass Sie wissen, wovon Sie sprechen.

Ich würde es dem Ende überlassen zu sagen, dass es besser wäre, sich stattdessen auf die Lesbarkeit zu konzentrieren. Obwohl dies der Fall ist, kann es im Interviewkontext als "Ich weiß nichts über Leistung, aber mein Code liest sich wie eine Geschichte von Janet und John " interpretiert werden .

Was Sie nicht tun sollten, ist die üblichen langweiligen Aussagen darüber, wie Codeoptimierung nicht notwendig ist, nicht optimieren, bis Sie den Code profiliert haben (dies zeigt nur an, dass Sie keinen schlechten Code für sich selbst sehen können), Hardware kostet weniger als Programmierer , und bitte, bitte, zitiere Knuth nicht "vorzeitiges bla bla ...".

Die Leistung von Code ist in vielen Unternehmen ein echtes Problem, und viele Unternehmen benötigen Programmierer, die dies verstehen.

Insbesondere bei Organisationen wie Amazon hat ein Teil des Codes eine enorme Hebelwirkung. Ein Code-Snippet kann auf Tausenden von Servern oder Millionen von Geräten bereitgestellt werden und wird jeden Tag im Jahr milliardenfach aufgerufen. Es kann Tausende von ähnlichen Ausschnitten geben. Der Unterschied zwischen einem schlechten und einem guten Algorithmus kann leicht ein Faktor von tausend sein. Machen Sie die Zahlen und multiplizieren Sie das alles: Es macht einen Unterschied. Die potenziellen Kosten für die Organisation von fehlerhaftem Code können erheblich sein oder sogar schwerwiegende Folgen haben, wenn die Kapazität eines Systems knapp wird.

Darüber hinaus arbeiten viele dieser Organisationen in einem wettbewerbsorientierten Umfeld. Sie können Ihren Kunden also nicht einfach sagen, dass sie einen größeren Computer kaufen sollen, wenn die Software Ihres Mitbewerbers auf der Hardware, über die er verfügt, bereits ordnungsgemäß funktioniert oder wenn die Software auf einem Mobiltelefon ausgeführt wird und kein Upgrade möglich ist. Einige Anwendungen sind besonders leistungskritisch (Spiele und mobile Apps kommen in den Sinn) und können je nach Reaktionsfähigkeit oder Geschwindigkeit leben oder sterben.

Ich habe persönlich über zwei Jahrzehnte an vielen Projekten gearbeitet, bei denen Systeme aufgrund von Leistungsproblemen ausgefallen oder unbrauchbar waren, und ich wurde aufgefordert, diese Systeme zu optimieren. In allen Fällen lag dies an schlechtem Code, der von Programmierern geschrieben wurde, die das nicht verstanden haben die Auswirkungen dessen, was sie geschrieben haben. Außerdem ist es nie ein Stück Code, es ist immer überall. Wenn ich auftauche, ist es viel zu spät, über die Leistung nachzudenken: Der Schaden ist angerichtet.

Das Verstehen der Codeleistung ist eine gute Fähigkeit, die man genauso gut beherrscht wie das Verstehen der Codekorrektheit und des Codestils. Es kommt aus der Praxis. Leistungsstörungen können genauso schlimm sein wie Funktionsstörungen. Wenn das System nicht funktioniert, funktioniert es nicht. Egal warum. Ebenso sind Leistung und Funktionen, die nie verwendet werden, beide schlecht.

Wenn der Interviewer Sie nach der Leistung fragt, würde ich empfehlen, so viel Wissen wie möglich zu demonstrieren. Wenn die Frage schlecht erscheint, weisen Sie höflich darauf hin, warum Sie denken, dass dies in diesem Fall kein Problem darstellen würde. Zitiere nicht Knuth.

rghome
quelle
0

Sie sollten zunächst auf Korrektheit optimieren.

Ihre Funktion schlägt für Eingabewerte fehl, die nahe an Int.MaxValue liegen:

int a = int.MaxValue - 200;
int b = int.MaxValue - 200;
bool inRange = test.IsSumInRangeA(a, b);

Dies gibt true zurück, da die Summe zu -400 überläuft. Die Funktion funktioniert auch nicht für a = int.MinValue + 200. (summiert sich fälschlicherweise auf "400")

Wir werden nicht wissen, wonach der Interviewer gesucht hat, es sei denn, er oder sie mischt sich ein, aber "Überlauf ist real" .

Stellen Sie in einer Interview-Situation Fragen, um den Umfang des Problems zu verdeutlichen: Welche maximalen und minimalen Eingabewerte sind zulässig? Sobald Sie diese haben, können Sie eine Ausnahme auslösen, wenn der Anrufer Werte außerhalb des Bereichs sendet. Oder (in C #) können Sie einen markierten Abschnitt {} verwenden, der beim Überlauf eine Ausnahme auslöst. Ja, es ist mehr Arbeit und kompliziert, aber manchmal ist es das, was es braucht.

TomEberhard
quelle
Die Methoden waren nur Beispiele. Sie wurden nicht geschrieben, um korrekt zu sein, sondern um die eigentliche Frage zu veranschaulichen. Vielen Dank für die Eingabe!
Corey P
Ich denke, die Interviewfrage ist auf Leistung ausgerichtet, also müssen Sie die Absicht der Frage beantworten. Der Interviewer fragt nicht nach dem Verhalten an den Grenzen. Aber trotzdem interessanter Nebeneffekt.
rghome
1
@Corey Gute Interviewer als Fragestellung 1) beurteilen die Kandidatenfähigkeit in Bezug auf das Thema, wie von rghome hier vorgeschlagen, aber auch 2) als Öffnung für die größeren Themen (wie die unausgesprochene funktionale Korrektheit) und die Tiefe des verwandten Wissens - dies gilt umso mehr in späteren karriereinterviews - viel glück.
Chux
0

Ihre Frage hätte lauten sollen: "Muss ich das überhaupt optimieren?".

Version A und B unterscheiden sich in einem wichtigen Detail, das A bevorzugt, aber nicht mit der Optimierung zusammenhängt: Sie wiederholen den Code nicht.

Die eigentliche "Optimierung" nennt man "Common Subexpression Elimination", was so ziemlich jeder Compiler tut. Einige führen diese grundlegende Optimierung auch durch, wenn die Optimierungen deaktiviert sind. Das ist also keine wirkliche Optimierung (der generierte Code wird mit ziemlicher Sicherheit in jedem Fall genau gleich sein).

Aber wenn es keine Optimierung ist, warum ist es dann vorzuziehen? Okay, Sie wiederholen keinen Code, wen interessiert das?

Zunächst einmal besteht nicht das Risiko, dass versehentlich die Hälfte der Bedingungsklausel falsch ist. Aber was noch wichtiger ist: Jemand, der diesen Code liest, kann sofort erkennen, was Sie versuchen, anstatt eine if((((wtf||is||this||longexpression))))Erfahrung zu machen. Was der Leser sieht, ist if(one || theother), was gut ist. Nicht selten geschieht ich , dass Sie , dass andere Person Ihren eigenen Code drei Jahre später zu lesen und denken : „WTF bedeutet das?“. In diesem Fall ist es immer hilfreich, wenn Ihr Code sofort mitteilt, was die Absicht war. Wenn ein allgemeiner Unterausdruck richtig benannt ist, ist das der Fall.
Auch wenn zu irgendeinem Zeitpunkt in der Zukunft, Sie entscheiden , dass zB die Sie ändern müssen , a+bum a-b, müssen Sie ändern einOrt, nicht zwei. Und es besteht kein Risiko, dass (erneut) versehentlich der zweite Fehler auftritt.

Zu Ihrer eigentlichen Frage, wofür Sie optimieren sollten, sollte zunächst Ihr Code korrekt sein . Das ist das absolut Wichtigste. Code, der nicht korrekt ist, ist schlechter Code, auch wenn er, obwohl er falsch ist, "gut funktioniert" oder zumindest so aussieht, als ob er gut funktioniert. Danach sollte der Code lesbar sein (für jemanden, der mit dem Code nicht vertraut ist).
Was die Optimierung angeht ... man sollte auf keinen Fall absichtlich anti-optimierten Code schreiben, und ich sage auch nicht, dass man sich vor dem Start nicht mit dem Design auseinandersetzen sollte (z. B. den richtigen Algorithmus für das Problem auswählen, nicht die am wenigsten effiziente).

Aber für die meisten Anwendungen ist die Leistung, die Sie erzielen, wenn Sie korrekten, lesbaren Code mit einem vernünftigen Algorithmus und einem optimierenden Compiler ausführen, in der Regel in Ordnung. Es besteht kein Grund zur Sorge.

Wenn dies nicht der Fall ist, dh wenn die Leistung der Anwendung tatsächlich nicht den Anforderungen entspricht, und nur dann , sollten Sie sich Gedanken über lokale Optimierungen machen, wie die, die Sie versucht haben. Am liebsten würden Sie jedoch den Algorithmus der obersten Ebene überdenken. Wenn Sie eine Funktion aufgrund eines besseren Algorithmus 500-mal statt 50.000-mal aufrufen, hat dies eine größere Auswirkung als das Einsparen von drei Taktzyklen bei einer Mikrooptimierung. Wenn Sie nicht ständig mehrere hundert Zyklen bei einem wahlfreien Speicherzugriff warten, hat dies eine größere Auswirkung als ein paar zusätzliche kostengünstige Berechnungen usw. usw.

Die Optimierung ist eine schwierige Angelegenheit (Sie können ganze Bücher darüber schreiben und kein Ende finden), und es ist in der Regel Zeitverschwendung, eine bestimmte Stelle blind zu optimieren (ohne zu wissen, ob dies überhaupt der Engpass ist!). Ohne Profiling ist eine Optimierung nur sehr schwer möglich.

Aber als Faustregel, wenn Sie blind fliegen und einfach etwas tun müssen / wollen oder als allgemeine Standardstrategie, würde ich vorschlagen, für "Gedächtnis" zu optimieren.
Die Optimierung auf "Speicher" (insbesondere räumliche Lokalität und Zugriffsmuster) bringt normalerweise einen Vorteil, da der Zugriff auf RAM heutzutage zu den teuersten Dingen zählt (kurz vor dem Lesen von der Festplatte!). das kannst du prinzipiell tun. Während ALU andererseits billig ist und jede Woche schneller wird. Speicherbandbreite und Latenz verbessern sich nicht annähernd so schnell. Gute Lokalität und gute Zugriffsmuster können leicht einen 5-fachen Unterschied (20-fache in extremen, erfundenen Beispielen) in der Laufzeit im Vergleich zu schlechten Zugriffsmustern in datenlastigen Anwendungen bewirken. Sei nett zu deinen Caches und du wirst ein glücklicher Mensch sein.

Überlegen Sie, was die verschiedenen Dinge, die Sie tun können, kosten, um den vorherigen Absatz zu relativieren. Das Ausführen von so etwas a+bdauert ein oder zwei Zyklen (wenn es nicht optimiert ist), aber die CPU kann normalerweise mehrere Anweisungen pro Zyklus starten und nicht abhängige Anweisungen so weiterleiten, dass es realistischer ist, dass es Sie nur etwa einen halben Zyklus oder weniger kostet. Im Idealfall kostet der Compiler, wenn er sich gut terminieren lässt, je nach Situation null.
Das Abrufen von Daten ("Gedächtnis") kostet Sie entweder 4 bis 5 Zyklen, wenn Sie Glück haben und es befindet sich in L1, und ungefähr 15 Zyklen, wenn Sie nicht so Glück haben (L2-Treffer). Wenn sich die Daten überhaupt nicht im Cache befinden, dauert es mehrere hundert Zyklen. Wenn Ihr willkürliches Zugriffsmuster die Funktionen des TLB überschreitet (einfach mit nur ~ 50 Einträgen durchzuführen), fügen Sie weitere einige hundert Zyklen hinzu. Wenn Ihr willkürliches Zugriffsmuster tatsächlich einen Seitenfehler verursacht, kostet es Sie im besten Fall einige zehntausend Zyklen und im schlechtesten mehrere Millionen.
Denken Sie jetzt darüber nach, was möchten Sie am dringendsten vermeiden?

Damon
quelle
0

Wann ist für eine Methode die Optimierung für Speicher im Vergleich zur Leistungsgeschwindigkeit vorzunehmen?

Nachdem Sie die Funktionalität zuerst richtig eingestellt haben . Dann beschäftigt sich die Selektivität mit Mikrooptimierungen.


Als Interviewfrage zu Optimierungen provoziert der Code die übliche Diskussion, verfehlt jedoch das übergeordnete Ziel von Ist der Code funktionell korrekt?

Sowohl C ++ als auch C und andere betrachten den intÜberlauf als ein Problem von a + b. Es ist nicht gut definiert und C nennt es undefiniertes Verhalten . Es ist nicht spezifiziert, um "umzubrechen" - obwohl das das übliche Verhalten ist.

bool IsSumInRange(int a, int b) {
    int s = a + b;  // Overflow possible
    if (s > 1000 || s < -1000) return false;
    else return true;
}

Es wird IsSumInRange()erwartet, dass eine solche aufgerufene Funktion gut definiert ist und für alle intWerte von korrekt ausgeführt wird a,b. Das rohe a + bgeht nicht. AC-Lösung könnte verwenden:

#define N 1000
bool IsSumInRange_FullRange(int a, int b) {
  if (a >= 0) {
    if (b > INT_MAX - a) return false;
  } else {
    if (b < INT_MIN - a) return false;
  }
  int sum = a + b;
  if (sum > N || sum < -N) return false;
  else return true;
}

Der obige Code könnte , als durch die Verwendung eines breiteren Integer - Typ optimiert werden int, wenn verfügbar, wie unten oder der Verteilung sum > N, sum < -NTests in der if (a >= 0)Logik. Solche Optimierungen können jedoch bei einem intelligenten Compiler nicht wirklich zu einem "schnelleren" Code führen, und es lohnt sich auch nicht, besonders clever zu sein.

  long long sum a;
  sum += b;

Sogar die Verwendung abs(sum)ist anfällig für Probleme, wenn sum == INT_MIN.

chux
quelle
0

Um welche Art von Compilern handelt es sich und um welche Art von "Erinnerung"? Da in Ihrem Beispiel ein vernünftiger Optimierer vorausgesetzt wird, muss der Ausdruck a+bim Allgemeinen in einem Register (einer Form von Speicher) gespeichert werden, bevor eine solche Arithmetik ausgeführt werden kann.

Wenn es sich also um einen dummen Compiler handelt, der a+bzweimal vorkommt, werden in Ihrem zweiten Beispiel mehr Register (Speicher) zugewiesen , da Ihr erstes Beispiel diesen Ausdruck möglicherweise nur einmal in einem einzelnen Register speichert, das der lokalen Variablen zugeordnet ist, aber wir Ich spreche an dieser Stelle von sehr albernen Compilern ... es sei denn, Sie arbeiten mit einer anderen Art von albernem Compiler, der jede einzelne Variable über den gesamten Bereich verteilt. In diesem Fall würde der erste vielleicht mehr Trauer verursachen, als zu optimieren der Zweite*.

Ich möchte immer noch daran arbeiten und denke, dass der zweite Compiler wahrscheinlich mehr Speicherplatz für einen dummen Compiler benötigt, selbst wenn er dazu neigt, verschüttete Daten zu stapeln, da er möglicherweise drei Register für a+bund verschüttete Daten aund bmehr zuweist . Wenn es sich um den primitivsten Optimierer handelt, wird das Aufzeichnen a+bauf swahrscheinlich "helfen", weniger Register / Stapelspills zu verwenden.

Dies alles ist extrem spekulativ, wenn keine Messungen / Demontagen durchgeführt werden, und selbst im schlimmsten Fall handelt es sich nicht um einen "Memory vs. Performance" -Fall (denn selbst bei den schlimmsten Optimierern, die ich mir vorstellen kann, sprechen wir nicht darüber Über alles andere als temporären Speicher (z. B. Stack / Register) ist es bestenfalls ein reiner "Performance" -Fall, und unter allen vernünftigen Optimierern sind die beiden äquivalent besonders fehlende messungen? Das ist wie der Fokus auf Anweisungsauswahl / Registerzuweisung auf Assembly-Ebene, den ich niemals von jemandem erwarten würde, der produktiv bleiben möchte, wenn er beispielsweise einen Interpreter verwendet, der alles verschüttet.

Wann ist für eine Methode die Optimierung für Speicher im Vergleich zur Leistungsgeschwindigkeit vorzunehmen?

Was diese Frage angeht, wenn ich sie allgemeiner angehen kann, finde ich die beiden oft nicht diametral entgegengesetzt. Insbesondere wenn Ihre Zugriffsmuster sequentiell sind und die Geschwindigkeit des CPU-Caches gegeben ist, bedeutet eine Verringerung der Anzahl von Bytes, die sequentiell für nicht triviale Eingaben verarbeitet werden, (bis zu einem gewissen Punkt), dass diese Daten schneller durchsucht werden. Natürlich gibt es Bruchstellen, an denen, wenn die Daten im Austausch für viel, viel mehr Anweisungen viel, viel kleiner sind, es möglicherweise schneller ist, sequentiell in größerer Form im Austausch für weniger Anweisungen zu verarbeiten.

Ich habe jedoch festgestellt, dass viele Entwickler häufig unterschätzen, inwieweit eine Verringerung der Speichernutzung in solchen Fällen zu einer proportionalen Verringerung der Verarbeitungszeit führen kann. Es ist sehr intuitiv, Leistungskosten in Anweisungen zu übersetzen, anstatt den Speicherzugriff auf große LUTs zu beschränken, um einige kleine Berechnungen zu beschleunigen, und nur um festzustellen, dass die Leistung durch den zusätzlichen Speicherzugriff beeinträchtigt wird.

Bei Fällen mit sequenziellem Zugriff über ein großes Array (ohne lokale skalare Variablen wie in Ihrem Beispiel) gehe ich von der Regel aus, dass weniger Speicher zum sequenziellen Durchsuchen zu einer höheren Leistung führt, insbesondere, wenn der resultierende Code einfacher als sonst ist, bis dies nicht der Fall ist Bis meine Messungen und mein Profiler etwas anderes mitteilen und es wichtig ist, gehe ich in der gleichen Weise davon aus, dass das sequentielle Lesen einer kleineren Binärdatei auf der Festplatte schneller als eine größere Datei ist (selbst wenn die kleinere mehr Anweisungen erfordert) ), bis sich herausstellt, dass diese Annahme bei meinen Messungen nicht mehr zutrifft.

Drachen Energie
quelle