比较基准测试：高吞吐量场景中的 ILP、A* 和分支定界算法
- Susan Sarandon原创
- 2024-11-06 04:44:02232浏览
在这篇博文中，我们将比较最近个人项目中使用的三种不同算法的性能：ILP（整数线性规划） 算法、使用 A* 算法的本地算法，以及使用 Branch and Bound 算法的优化解决方案。所有算法都使用相同的数据集进行测试，ILP 和分支定界实现共享相同的工作负载，而 A* 实现由于性能限制而受到限制。
免责声明：虽然我不会深入研究该项目的具体代码细节，但我会从中分享一些见解。该代码库不打算公开披露，这是尊重其机密性的免责声明。
基准测试结果
以下是所有三种算法的基准测试结果：
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
工作负载配置
所有算法均使用同一组数据进行测试，但实现之间的工作负载（即处理每个项目的次数）不同。
ILP 和分支定界实施工作量：
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* 实施工作量：
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},
}
工作量分析
为了了解这些工作负载对基准测试结果的影响，我们来计算每个实现的迭代总数（即 Times 值的总和）。
总迭代次数：
- ILP 和分支定界实现：
100 + 150 + 200 + 50 + 75 + 80 + 90 + 85 + 60 + 110 = 1000
- A* 实施：
1 + 1 + 5 + 5 + 5 + 5 + 9 + 5 + 5 + 5 = 46
工作负载比例：
ILP Iterations / A* Iterations = 1000 / 46 ≈ 21.74
这意味着与 A* 实现相比，ILP 和分支定界实现处理的迭代次数大约多21.74 倍。
性能比较
让我们根据工作负载差异来分解基准测试结果。
| 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 |
观察结果
-
每个操作的执行时间：
-
BenchmarkGenerateReportILP-24 与 BenchmarkBranchGenerateReportLocal-24：
- 分支和绑定 比 ILP 快 99.29%，将执行时间从 1,694,029 ns/op 减少到 12,106 ns/op .
-
BenchmarkGenerateReportILP-24 与 BenchmarkBranchGenerateReportLocal-24：
-
BenchmarkGenerateReportILP-24 与 BenchmarkGenerateReportLocal-24：
- ILP 比 本地 快 99.80%，将执行时间从 851,314,106 ns/op 减少到 1,694,029 ns/op.
-
BenchmarkGenerateReportILPParallel-24 与 BenchmarkBranchGenerateReportLocalParallel-24：
- 分支和绑定并行比ILP并行快94.28%，将执行时间从187,871 ns/op减少到10,755 ns /op.
-
BenchmarkGenerateReportILPParallel-24 与 BenchmarkGenerateReportLocalParallel-24：
- ILP 并行 比 本地并行 快 99.95%，将执行时间从 349,605,952 ns/op 减少到 187,871 ns/op .
-
内存分配：
- ILP 实现： 并行运行时内存使用和分配略有增加。
- 分支和绑定实现：与 A* 实现相比，内存使用量和分配更低。
- A* 实现： 极高的内存分配，导致资源利用率低下。
-
吞吐量：
- ILP 并行 和 分支定界并行 由于工作负载较高，可以处理 大约 21.74 倍的迭代。
- A* 实现 吞吐量困难不是因为迭代次数显着减少，而是因为内存使用和实现效率低下。
不同工作负载对性能的影响
鉴于 ILP 和 Branch 算法每次测试迭代处理 21.74 倍 的吞吐量，这种工作负载差异会影响每个算法的性能和效率：
ILP 和分支算法：由于这些算法可处理更大的吞吐量，因此它们针对更高的工作负载进行了优化。尽管处理更多操作，但它们仍保持更快的执行时间。这表明它们不仅计算效率高，而且非常适合高吞吐量场景。
本地算法：吞吐量较小，执行时间较长，该算法在处理增加的工作负载时效率较低。如果扩展到与 ILP 或 Branch 相同的吞吐量，其执行时间将显着增加，这表明它对于高吞吐量情况并不理想。
在工作负载增加的情况下，ILP 和 Branch 将优于 Local，因为它们能够有效管理更高的吞吐量。相反，如果工作量减少，Local 算法的性能可能更接近 ILP 和 Branch，但由于算法效率的根本差异，仍然可能落后。
算法概述
为了更清楚地了解每种算法如何解决问题，这里对其机制和方法进行了总体概述。
整数线性规划 (ILP)
目的：
ILP 是一种优化技术，用于在数学模型中找到最佳结果（例如最大利润或最低成本），其要求由线性关系表示。它对于可以用线性约束和线性目标函数表示的问题特别有效。
一般工作流程：
定义变量：
确定代表要做出的选择的决策变量。目标函数：
制定需要最大化或最小化的线性方程。约束：
建立解必须满足的线性不等式或等式。解决：
利用 ILP 求解器找到决策变量的最优值，在满足所有约束的同时最大化或最小化目标函数。
伪代码：
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
A*算法（本地实现）
目的：
A* 是一种寻路和图遍历算法，以其性能和准确性而闻名。它通过结合统一成本搜索和纯启发式搜索的特征，有效地找到节点之间的最短路径。
一般工作流程：
初始化：
从初始节点开始并将其添加到优先级队列中。-
循环：
- 从优先级队列中删除成本估计最低的节点。
- 如果是目标节点，则终止。
- 否则，通过探索其邻居来扩展节点。
- 对于每个邻居，计算新的成本并相应地更新优先级队列。
终止：
当到达目标节点或优先级队列为空（表示不存在路径）时，算法结束。
伪代码：
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
分支定界算法
目的：
分支定界是一种系统地探索解空间的优化算法。它将问题划分为更小的子问题（分支），并使用边界来消除无法产生比当前最佳解决方案更好的解决方案（边界）的子问题。
一般工作流程：
初始化：
从初始解决方案开始，然后设置最知名的解决方案。分支：
在每个节点，将问题分成更小的子问题。边界：
计算每个分支中最佳可能解决方案的乐观估计（上限）。修剪：
丢弃上限比已知解决方案更差的分支。搜索：
使用深度优先或最佳优先搜索递归地探索剩余分支。终止：
当所有分支都被修剪或探索后，最知名的解决方案就是最优的。
伪代码：
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
对比分析
| 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. |
对服务器性能的影响
-
可扩展性：
- 分支和绑定实现展示了出色的可扩展性，可以有效处理大量并发请求并减少延迟。
- ILP Parallel 实现还表现出出色的可扩展性，能够有效处理大量并发请求并减少延迟。
- 由于性能限制，A* 实现不适合高负载环境。
-
资源利用率：
- 分支和限界实现高效利用资源，内存消耗低，执行时间快。
- ILP Parallel 有效利用多核 CPU，提供高吞吐量和可管理的内存消耗。
- A* 实现 消耗过多内存，可能导致资源耗尽。
工作负载对性能的影响
工作负载差异影响算法的性能：
分支限界实现可以有效地处理与 ILP 实现相同的工作负载，提供快速的执行时间和较低的内存使用量，使其适合扩展。
ILP 实施 由于优化的求解器，可以有效地处理更大的工作负载。
A* 实现 由于高执行时间和内存使用而导致性能不佳。
结论
使用优化解决方案与分支定界算法进行了额外的比较，这表明它在性能和资源利用率方面比 ILP 和 A* 算法有显着改进。分支定界算法使用的工作负载与 ILP 算法相同。
基于分支和界限的BenchmarkBranchGenerateReportLocalParallel功能展示了卓越的性能改进，使其非常适合需要高并发和高效资源管理的服务器环境。
通过专注于利用分支定界方法的优势并针对特定问题对其进行优化，我们可以确保项目保持高性能和可扩展性，能够轻松处理不断增长的需求。
最后的想法
平衡性能、可扩展性和开发人员体验对于构建强大的应用程序至关重要。 分支定界 方法已被证明是当前设置中最有效的方法，通过合理的开发工作可带来显着的性能提升。
通过不断分析、优化和利用每种算法方法的优势，我们可以维护一个高性能、可扩展且对开发人员友好的系统。
以上是比较基准测试：高吞吐量场景中的 ILP、A* 和分支定界算法的详细内容。更多信息请关注PHP中文网其他相关文章！