比较基准测试：高吞吐量场景中的 ILP、A* 和分支定界算法

在这篇博文中，我们将比较最近个人项目中使用的三种不同算法的性能：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
</my-package></my-project></my-package></my-project>

工作负载配置

所有算法均使用同一组数据进行测试，但实现之间的工作负载（即处理每个项目的次数）不同。

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

观察结果

1. 每个操作的执行时间：
   • BenchmarkGenerateReportILP-24 与 BenchmarkBranchGenerateReportLocal-24：
     • 分支和绑定 比 ILP 快 99.29%，将执行时间从 1,694,029 ns/op 减少到 12,106 ns/op .

• 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 .

1. 内存分配：

   • ILP 实现： 并行运行时内存使用和分配略有增加。
   • 分支和绑定实现：与 A* 实现相比，内存使用量和分配更低。
   • A* 实现： 极高的内存分配，导致资源利用率低下。

2. 吞吐量：

   • ILP 并行 和 分支定界并行 由于工作负载较高，可以处理 大约 21.74 倍的迭代。
   • A* 实现 吞吐量困难不是因为迭代次数显着减少，而是因为内存使用和实现效率低下。

不同工作负载对性能的影响

鉴于 ILP 和 Branch 算法每次测试迭代处理 21.74 倍 的吞吐量，这种工作负载差异会影响每个算法的性能和效率：

• ILP 和分支算法：由于这些算法可处理更大的吞吐量，因此它们针对更高的工作负载进行了优化。尽管处理更多操作，但它们仍保持更快的执行时间。这表明它们不仅计算效率高，而且非常适合高吞吐量场景。

• 本地算法：吞吐量较小，执行时间较长，该算法在处理增加的工作负载时效率较低。如果扩展到与 ILP 或 Branch 相同的吞吐量，其执行时间将显着增加，这表明它对于高吞吐量情况并不理想。

在工作负载增加的情况下，ILP 和 Branch 将优于 Local，因为它们能够有效管理更高的吞吐量。相反，如果工作量减少，Local 算法的性能可能更接近 ILP 和 Branch，但由于算法效率的根本差异，仍然可能落后。

算法概述

为了更清楚地了解每种算法如何解决问题，这里对其机制和方法进行了总体概述。

整数线性规划 (ILP)

目的：

ILP 是一种优化技术，用于在数学模型中找到最佳结果（例如最大利润或最低成本），其要求由线性关系表示。它对于可以用线性约束和线性目标函数表示的问题特别有效。

一般工作流程：

1. 定义变量：
   
   确定代表要做出的选择的决策变量。

2. 目标函数：
   
   制定需要最大化或最小化的线性方程。

3. 约束：
   
   建立解必须满足的线性不等式或等式。

4. 解决：
   
   利用 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
</my-package></my-project></my-package></my-project>

A*算法（本地实现）

目的：

A* 是一种寻路和图遍历算法，以其性能和准确性而闻名。它通过结合统一成本搜索和纯启发式搜索的特征，有效地找到节点之间的最短路径。

一般工作流程：

1. 初始化：
   
   从初始节点开始并将其添加到优先级队列中。

2. 循环：

   • 从优先级队列中删除成本估计最低的节点。
   • 如果是目标节点，则终止。
   • 否则，通过探索其邻居来扩展节点。
   • 对于每个邻居，计算新的成本并相应地更新优先级队列。

3. 终止：
   
   当到达目标节点或优先级队列为空（表示不存在路径）时，算法结束。

伪代码：

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>

分支定界算法

目的：

分支定界是一种系统地探索解空间的优化算法。它将问题划分为更小的子问题（分支），并使用边界来消除无法产生比当前最佳解决方案更好的解决方案（边界）的子问题。

一般工作流程：

1. 初始化：
   
   从初始解决方案开始，然后设置最知名的解决方案。

2. 分支：
   
   在每个节点，将问题分成更小的子问题。

3. 边界：
   
   计算每个分支中最佳可能解决方案的乐观估计（上限）。

4. 修剪：
   
   丢弃上限比已知解决方案更差的分支。

5. 搜索：
   
   使用深度优先或最佳优先搜索递归地探索剩余分支。

6. 终止：
   
   当所有分支都被修剪或探索后，最知名的解决方案就是最优的。

伪代码：

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>

对比分析

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中文网其他相关文章！