Vergleichendes Benchmarking: ILP-, A*- und Branch-and-Bound-Algorithmen in Hochdurchsatzszenarien

In diesem Blogbeitrag vergleichen wir die Leistung von drei verschiedenen Algorithmen, die in einem aktuellen persönlichen Projekt verwendet wurden: dem ILP (Integer Linear Programming)-Algorithmus, dem Lokaler Algorithmus unter Verwendung des A*-Algorithmus und eine optimierte Lösung unter Verwendung des Branch and Bound-Algorithmus. Alle Algorithmen wurden mit demselben Datensatz getestet, wobei die ILP- und Branch-and-Bound-Implementierungen die gleiche Arbeitslast teilten, während die A*-Implementierung aufgrund von Leistungseinschränkungen eingeschränkt war.

Haftungsausschluss: Obwohl ich nicht auf die spezifischen Codedetails des Projekts eingehen werde, werde ich einige Erkenntnisse daraus teilen. Die Codebasis ist nicht zur öffentlichen Offenlegung bestimmt und dient als Haftungsausschluss zur Wahrung ihrer Vertraulichkeit.

Benchmark-Ergebnisse

Hier sind die Benchmark-Ergebnisse für alle drei Algorithmen:

goos: linux
goarch: amd64
pkg: github.com/sosalejandro/<my-project>/<my-package>/pkg
cpu: 13th Gen Intel(R) Core(TM) i7-13700HX

BenchmarkGenerateReportILP-24                            724       1694029 ns/op       30332 B/op        181 allocs/op
BenchmarkGenerateReportILPParallel-24                   6512        187871 ns/op       34545 B/op        184 allocs/op
BenchmarkGenerateReportLocal-24                            2     851314106 ns/op    559466456 B/op   7379756 allocs/op
BenchmarkBranchGenerateReportLocal-24                 101449         12106 ns/op       29932 B/op        165 allocs/op
BenchmarkGenerateReportLocalParallel-24                    3     349605952 ns/op    559422440 B/op   7379837 allocs/op
BenchmarkBranchGenerateReportLocalParallel-24         120543         10755 ns/op       29933 B/op        165 allocs/op
PASS
coverage: 81.4% of statements
ok      github.com/sosalejandro/<my-project>/<my-package>/pkg   11.121s
</my-package></my-project></my-package></my-project>

Workload-Konfiguration

Alle Algorithmen wurden mit demselben Datensatz getestet, aber der Arbeitsaufwand (d. h. die Häufigkeit, mit der jedes Element verarbeitet wird) unterschied sich zwischen den Implementierungen.

ILP- und Branch-and-Bound-Implementierungsarbeitsaufwand:

plan := []Plan{
    {ID: "1", Times: 100},
    {ID: "2", Times: 150},
    {ID: "3", Times: 200},
    {ID: "8", Times: 50},
    {ID: "9", Times: 75},
    {ID: "10", Times: 80},
    {ID: "11", Times: 90},
    {ID: "12", Times: 85},
    {ID: "13", Times: 60},
    {ID: "14", Times: 110},
}

A* Implementierungsaufwand:

plan := []Plan{
    {ID: "1", Times: 1},
    {ID: "2", Times: 1},
    {ID: "3", Times: 5},
    {ID: "8", Times: 5},
    {ID: "9", Times: 5},
    {ID: "10", Times: 5},
    {ID: "11", Times: 9},
    {ID: "12", Times: 5},
    {ID: "13", Times: 5},
    {ID: "14", Times: 5},
}

Workload-Analyse

Um die Auswirkungen dieser Arbeitslasten auf die Benchmark-Ergebnisse zu verstehen, berechnen wir die Gesamtzahl der Iterationen (d. h. die Summe der Zeitwerte) für jede Implementierung.

Gesamtzahl der Iterationen:

• ILP und Branch-and-Bound-Implementierungen:

  100 + 150 + 200 + 50 + 75 + 80 + 90 + 85 + 60 + 110 = 1000

• A*-Implementierung:

  1 + 1 + 5 + 5 + 5 + 5 + 9 + 5 + 5 + 5 = 46

Arbeitsbelastungsverhältnis:

ILP Iterations / A* Iterations = 1000 / 46 ≈ 21.74

Das bedeutet, dass die ILP- und Branch-and-Bound-Implementierungen ungefähr 21,74-mal mehr Iterationen verarbeiten im Vergleich zur A*-Implementierung.

Leistungsvergleich

Lassen Sie uns die Benchmark-Ergebnisse in Bezug auf die Arbeitsbelastungsunterschiede aufschlüsseln.

Benchmark	Runs	ns/op	B/op	allocs/op	Total Time (ns)
BenchmarkGenerateReportILP-24	724	1,694,029	30,332	181	≈ 1,225,836,996
BenchmarkGenerateReportILPParallel-24	6,512	187,871	34,545	184	≈ 1,223,607,552
BenchmarkBranchGenerateReportLocal-24	101,449	12,106	29,932	165	≈ 1,224,505,394
BenchmarkGenerateReportLocal-24	2	851,314,106	559,466,456	7,379,756	≈ 1,702,628,212
BenchmarkGenerateReportLocalParallel-24	3	349,605,952	559,422,440	7,379,837	≈ 1,048,817,856
BenchmarkBranchGenerateReportLocalParallel-24	120,543	10,755	29,933	165	≈ 1,295,219,065

Beobachtungen

1. Ausführungszeit pro Vorgang:
   • BenchmarkGenerateReportILP-24 vs. BenchmarkBranchGenerateReportLocal-24:
     • Branch and Bound ist 99,29 % schneller als ILP und reduziert die Ausführungszeit von 1.694.029 ns/op auf 12.106 ns/op .

• BenchmarkGenerateReportILP-24 vs BenchmarkGenerateReportLocal-24:

  • ILP ist 99,80 % schneller als Local und reduziert die Ausführungszeit von 851.314.106 ns/op auf 1.694.029 ns/op.

• BenchmarkGenerateReportILPParallel-24 vs BenchmarkBranchGenerateReportLocalParallel-24:

  • Branch and Bound Parallel ist 94,28 % schneller als ILP Parallel und reduziert die Ausführungszeit von 187.871 ns/op auf 10.755 ns /op.

• BenchmarkGenerateReportILPParallel-24 vs. BenchmarkGenerateReportLocalParallel-24:

  • ILP Parallel ist 99,95 % schneller als Local Parallel und reduziert die Ausführungszeit von 349.605.952 ns/op auf 187.871 ns/op .

1. Speicherzuweisungen:

   • ILP-Implementierungen:Leichter Anstieg der Speichernutzung und -zuweisungen bei paralleler Ausführung.
   • Branch-and-Bound-Implementierungen: Geringere Speichernutzung und -zuweisungen im Vergleich zu den A*-Implementierungen.
   • A*-Implementierungen: Extrem hohe Speicherzuweisungen, was zu einer ineffizienten Ressourcennutzung führt.

2. Durchsatz:

   • ILP Parallel und Branch and Bound Parallel können aufgrund der höheren Arbeitsbelastung ungefähr 21,74-mal mehr Iterationen verarbeiten.
   • A*-Implementierungen haben Probleme mit dem Durchsatz, nicht aufgrund der deutlich geringeren Anzahl von Iterationen, sondern aufgrund der ineffizienten Speichernutzung und Implementierung.

Auswirkungen unterschiedlicher Arbeitsbelastung auf die Leistung

Angesichts der Tatsache, dass die ILP- und Branch-Algorithmen 21,74-mal mehr Durchsatz pro Testiteration verarbeiten, wirkt sich dieser Unterschied in der Arbeitslast auf die Leistung und Effizienz jedes Algorithmus aus:

• ILP- ​​und Branch-Algorithmen: Da diese einen größeren Durchsatz bewältigen, sind sie für höhere Arbeitslasten optimiert. Obwohl sie mehr Vorgänge abwickeln, sorgen sie für kürzere Ausführungszeiten. Dies legt nahe, dass sie nicht nur recheneffizient sind, sondern auch für Hochdurchsatzszenarien gut geeignet sind.

• Lokaler Algorithmus: Mit einem geringeren Durchsatz und einer höheren Ausführungszeit ist dieser Algorithmus bei der Bewältigung erhöhter Arbeitslasten weniger effizient. Bei einer Skalierung auf den gleichen Durchsatz wie ILP oder Branch würde sich die Ausführungszeit erheblich verlängern, was darauf hindeutet, dass es nicht ideal für Fälle mit hohem Durchsatz ist.

In Szenarien mit erhöhter Arbeitslast würden ILP und Branch Local übertreffen aufgrund ihrer Fähigkeit, einen höheren Durchsatz effizient zu verwalten. Wenn umgekehrt die Arbeitslast reduziert würde, könnte die Leistung des lokalen Algorithmus näher an der von ILP und Branch liegen, würde aber aufgrund grundlegender Unterschiede in der Algorithmuseffizienz wahrscheinlich immer noch hinterherhinken.

Algorithmusübersicht

Um ein klareres Verständnis dafür zu vermitteln, wie die einzelnen Algorithmen an die Problemlösung herangehen, finden Sie hier einen allgemeinen Überblick über ihre Mechanismen und Methoden.

Ganzzahlige lineare Programmierung (ILP)

Zweck:

ILP ist eine Optimierungstechnik, mit der das beste Ergebnis (z. B. maximaler Gewinn oder niedrigste Kosten) in einem mathematischen Modell ermittelt wird, dessen Anforderungen durch lineare Beziehungen dargestellt werden. Es ist besonders effektiv für Probleme, die durch lineare Einschränkungen und eine lineare Zielfunktion ausgedrückt werden können.

Allgemeiner Arbeitsablauf:

1. Variablen definieren:
   
   Identifizieren Sie die Entscheidungsvariablen, die die zu treffenden Entscheidungen darstellen.

2. Zielfunktion:
   
   Formulieren Sie eine lineare Gleichung, die maximiert oder minimiert werden muss.

3. Einschränkungen:
   
   Legen Sie lineare Ungleichungen oder Gleichheiten fest, die die Lösung erfüllen muss.

4. Lösen:
   
   Verwenden Sie einen ILP-Löser, um die optimalen Werte der Entscheidungsvariablen zu finden, die die Zielfunktion maximieren oder minimieren und gleichzeitig alle Einschränkungen erfüllen.

Pseudocode:

goos: linux
goarch: amd64
pkg: github.com/sosalejandro/<my-project>/<my-package>/pkg
cpu: 13th Gen Intel(R) Core(TM) i7-13700HX

BenchmarkGenerateReportILP-24                            724       1694029 ns/op       30332 B/op        181 allocs/op
BenchmarkGenerateReportILPParallel-24                   6512        187871 ns/op       34545 B/op        184 allocs/op
BenchmarkGenerateReportLocal-24                            2     851314106 ns/op    559466456 B/op   7379756 allocs/op
BenchmarkBranchGenerateReportLocal-24                 101449         12106 ns/op       29932 B/op        165 allocs/op
BenchmarkGenerateReportLocalParallel-24                    3     349605952 ns/op    559422440 B/op   7379837 allocs/op
BenchmarkBranchGenerateReportLocalParallel-24         120543         10755 ns/op       29933 B/op        165 allocs/op
PASS
coverage: 81.4% of statements
ok      github.com/sosalejandro/<my-project>/<my-package>/pkg   11.121s
</my-package></my-project></my-package></my-project>

A*-Algorithmus (lokale Implementierung)

Zweck:

A* ist ein Pfadfindungs- und Graph-Traversal-Algorithmus, der für seine Leistung und Genauigkeit bekannt ist. Es findet effizient den kürzesten Weg zwischen Knoten, indem es Funktionen der Suche nach einheitlichen Kosten und der reinen heuristischen Suche kombiniert.

Allgemeiner Arbeitsablauf:

1. Initialisierung:
   
   Beginnen Sie mit einem Anfangsknoten und fügen Sie ihn der Prioritätswarteschlange hinzu.

2. Schleife:

   • Entfernen Sie den Knoten mit der niedrigsten Kostenschätzung aus der Prioritätswarteschlange.
   • Wenn es sich um den Zielknoten handelt, beenden Sie ihn.
   • Andernfalls erweitern Sie den Knoten, indem Sie seine Nachbarn erkunden.
   • Berechnen Sie für jeden Nachbarn die neuen Kosten und aktualisieren Sie die Prioritätswarteschlange entsprechend.

3. Kündigung:
   
   Der Algorithmus schließt ab, wenn der Zielknoten erreicht ist oder die Prioritätswarteschlange leer ist (was anzeigt, dass kein Pfad vorhanden ist).

Pseudocode:

goos: linux
goarch: amd64
pkg: github.com/sosalejandro/<my-project>/<my-package>/pkg
cpu: 13th Gen Intel(R) Core(TM) i7-13700HX

BenchmarkGenerateReportILP-24                            724       1694029 ns/op       30332 B/op        181 allocs/op
BenchmarkGenerateReportILPParallel-24                   6512        187871 ns/op       34545 B/op        184 allocs/op
BenchmarkGenerateReportLocal-24                            2     851314106 ns/op    559466456 B/op   7379756 allocs/op
BenchmarkBranchGenerateReportLocal-24                 101449         12106 ns/op       29932 B/op        165 allocs/op
BenchmarkGenerateReportLocalParallel-24                    3     349605952 ns/op    559422440 B/op   7379837 allocs/op
BenchmarkBranchGenerateReportLocalParallel-24         120543         10755 ns/op       29933 B/op        165 allocs/op
PASS
coverage: 81.4% of statements
ok      github.com/sosalejandro/<my-project>/<my-package>/pkg   11.121s
</my-package></my-project></my-package></my-project>

Branch-and-Bound-Algorithmus

Zweck:

Branch and Bound ist ein Optimierungsalgorithmus, der den Lösungsraum systematisch erkundet. Es unterteilt das Problem in kleinere Teilprobleme (Verzweigung) und verwendet Grenzen, um Teilprobleme zu eliminieren, die keine besseren Lösungen als die derzeit besten liefern können (Begrenzung).

Allgemeiner Arbeitsablauf:

1. Initialisierung:
   
   Beginnen Sie mit einer ersten Lösung und legen Sie die bekannteste Lösung fest.

2. Verzweigung:
   
   Teilen Sie das Problem an jedem Knoten in kleinere Teilprobleme auf.

3. Begrenzung:
   
   Berechnen Sie eine optimistische Schätzung (Obergrenze) der bestmöglichen Lösung in jedem Zweig.

4. Beschneiden:
   
   Verwerfen Sie Zweige, bei denen die Obergrenze schlechter ist als die bekannteste Lösung.

5. Suche:
   
   Erkunden Sie verbleibende Zweige rekursiv mithilfe der Tiefensuche oder der Bestensuche.

6. Kündigung:
   
   Wenn alle Zweige beschnitten oder erkundet wurden, ist die bekannteste Lösung optimal.

Pseudocode:

goos: linux
goarch: amd64
pkg: github.com/sosalejandro/<my-project>/<my-package>/pkg
cpu: 13th Gen Intel(R) Core(TM) i7-13700HX

BenchmarkGenerateReportILP-24                            724       1694029 ns/op       30332 B/op        181 allocs/op
BenchmarkGenerateReportILPParallel-24                   6512        187871 ns/op       34545 B/op        184 allocs/op
BenchmarkGenerateReportLocal-24                            2     851314106 ns/op    559466456 B/op   7379756 allocs/op
BenchmarkBranchGenerateReportLocal-24                 101449         12106 ns/op       29932 B/op        165 allocs/op
BenchmarkGenerateReportLocalParallel-24                    3     349605952 ns/op    559422440 B/op   7379837 allocs/op
BenchmarkBranchGenerateReportLocalParallel-24         120543         10755 ns/op       29933 B/op        165 allocs/op
PASS
coverage: 81.4% of statements
ok      github.com/sosalejandro/<my-project>/<my-package>/pkg   11.121s
</my-package></my-project></my-package></my-project>

Vergleichende Analyse

Feature	ILP Implementation	Local (A*) Implementation	Branch and Bound Implementation
Optimization Approach	Formulates the problem as a set of linear equations and inequalities to find the optimal solution.	Searches through possible states using heuristics to find the most promising path to the goal.	Systematically explores and prunes the solution space to find optimal solutions efficiently.
Scalability	Handles large-scale problems efficiently by leveraging optimized solvers.	Performance can degrade with increasing problem size due to the exhaustive nature of state exploration.	Efficient for combinatorial problems, with pruning reducing the search space significantly.
Development Time	Faster implementation as it relies on existing ILP solvers and libraries.	Requires more time to implement, especially when dealing with complex state management and heuristics.	Moderate development time, balancing complexity and optimization benefits.
Flexibility	Highly adaptable to various linear optimization problems with clear constraints and objectives.	Best suited for problems where pathfinding to a goal is essential, with heuristic guidance.	Effective for a wide range of optimization problems, especially combinatorial ones.
Performance	Demonstrates superior performance in handling a higher number of iterations with optimized memory usage.	While effective for certain scenarios, struggles with high memory allocations and longer execution times under heavy workloads.	Shows significant performance improvements over ILP and A* with optimized memory usage and faster execution times.
Developer Experience	Improves developer experience by reducing the need for extensive coding and optimization efforts.	May require significant debugging and optimization to achieve comparable performance levels.	Balances performance with manageable development effort, leveraging existing strategies for optimization.
Integration	Currently integrates a C ILP module with Golang, facilitating efficient computation despite cross-language usage.	Fully implemented within Golang, but may face limitations in performance and scalability without optimizations.	Implemented in Golang, avoiding cross-language integration complexities and enhancing performance.

Auswirkungen auf die Serverleistung

• Skalierbarkeit:

  • Die Branch and Bound-Implementierung zeigt eine hervorragende Skalierbarkeit und verarbeitet effizient eine große Anzahl gleichzeitiger Anfragen mit reduzierter Latenz.
  • Die ILP Parallel-Implementierung zeigt außerdem eine hervorragende Skalierbarkeit und verarbeitet effizient eine große Anzahl gleichzeitiger Anfragen mit reduzierter Latenz.
  • Die A*-Implementierung ist aufgrund von Leistungseinschränkungen für Umgebungen mit hoher Auslastung ungeeignet.

• Ressourcennutzung:

  • Branch-and-Bound-Implementierungen nutzen Ressourcen effizient, mit geringem Speicherverbrauch und schnellen Ausführungszeiten.
  • ILP Parallel nutzt effektiv Multi-Core-CPUs und bietet so einen hohen Durchsatz bei überschaubarem Speicherverbrauch.
  • A*-Implementierungen verbrauchen übermäßig viel Speicher, was möglicherweise zur Erschöpfung der Ressourcen führt.

Auswirkungen der Arbeitslast auf die Leistung

Die Workload-Unterschiede beeinflussen die Leistung der Algorithmen:

• Branch-and-Bound-Implementierung bewältigt die gleiche Arbeitslast wie die ILP-Implementierung effizient und sorgt für schnelle Ausführungszeiten und geringe Speichernutzung, sodass sie für die Skalierung geeignet ist.

• ILP-Implementierung bewältigt aufgrund optimierter Solver eine größere Arbeitslast effizient.

• A*-Implementierung hat aufgrund hoher Ausführungszeiten und Speichernutzung Probleme mit der Leistung.

Abschluss

Ein zusätzlicher Vergleich wurde mit einer optimierten Lösung mit dem Branch and Bound-Algorithmus hinzugefügt, der zeigt, wie sich diese im Hinblick auf Leistung und Ressourcennutzung gegenüber dem ILP- und dem A*-Algorithmus deutlich verbessert hat. Die beim Branch-and-Bound-Algorithmus verwendete Arbeitslast ist die gleiche wie beim ILP-Algorithmus.

Die Branch and Bound-basierte BenchmarkBranchGenerateReportLocalParallel-Funktion weist außergewöhnliche Leistungsverbesserungen auf und eignet sich daher hervorragend für Serverumgebungen, die eine hohe Parallelität und effizientes Ressourcenmanagement erfordern.

Indem wir uns darauf konzentrieren, die Stärken des Branch-and-Bound-Ansatzes zu nutzen und ihn für das spezifische Problem zu optimieren, können wir sicherstellen, dass das Projekt sowohl leistungsfähig als auch skalierbar bleibt und in der Lage ist, steigende Anforderungen problemlos zu bewältigen.

Letzte Gedanken

Das Gleichgewicht zwischen Leistung, Skalierbarkeit und Entwicklererfahrung ist entscheidend für die Entwicklung robuster Anwendungen. Der Branch and Bound-Ansatz hat sich im aktuellen Setup als der effizienteste erwiesen und bietet erhebliche Leistungssteigerungen bei vertretbarem Entwicklungsaufwand.

Durch die kontinuierliche Profilierung, Optimierung und Nutzung der Stärken jedes algorithmischen Ansatzes können wir ein leistungsstarkes, skalierbares und entwicklerfreundliches System aufrechterhalten.

Das obige ist der detaillierte Inhalt vonVergleichendes Benchmarking: ILP-, A*- und Branch-and-Bound-Algorithmen in Hochdurchsatzszenarien. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!