No project description provided
Project description
AlgBench: A Python-util to run benchmarks for the empirical evaluation of algorithms.
There are a number of challenges when performing benchmarks for (long-running) algorithms.
- Saving all information requires a lot of boilerplate code and often you forget something.
- If you add some further instances or want to compare an additional parameter, you have to check which data is already available to skip existing entries. Same if you need to interrupt the benchmark.
- Just piping the results into a file can create a huge amount of data, no longer fitting into memory.
- Proper benchmarks often take days or even weeks to run, such that parallelization is necessary (e.g., with slurm) which requires a thread-safe database.
- Many file formats and databases are difficult to access or impossible to repair once corrupted.
AlgBench tries to ease your life by
- saving a lot of the information and data (function arguments, return values, runtime, environment information, stdout, etc.) automatically with a single line of code
- remembering which function arguments have already run and skipping those
- providing a compressible database to save memory, and saving highly redundant information, e.g., of the environment, only once
- providing an NFS-compatible parallel database and compatibility to distribution libraries, such as slurminade
- using a simple format based on JSON and Zip to allow simple parsing and even repairing broken databases by hand
There is a predecessor project, called AeMeasure. AeMeasure made saving the data easy, but required more boilerplate code and reading the data was more difficult and less efficient.
Usage
There is one important class Benchmark
to run the benchmark, and two important
functions describe
and read_as_pandas
to analyze the results.
class Benchmark(builtins.object) | ||
Benchmark(path: str) -> None This is the heart of the library. It allows to run, save, and load a benchmark. The function `add` will run a configuration, if it is not already in the database. You can also split this into `check` and `run`. This may be advised if you want to distribute the execution. ```python from algbench import Benchmark benchmark = Benchmark("./test_benchmark") def f(x, _test=2, default="default"): print(x) # here you would run your algorithm return {"r1": x, "r2": "test"} benchmark.add(f, 1, _test=None) benchmark.add(f, 2) benchmark.add(f, 3, _test=None) benchmark.compress() for entry in benchmark: print(entry["parameters"], entry["data"]) ``` The following functions are thread-safe: - exists - run - add - insert - front - __iter__ Don't call any of the other functions while the benchmark is running. It could lead to data loss. | ||
Methods defined here:
Data descriptors defined here:
|
You can find an example for graph coloring. The important parts are shown below.
Running a benchmark
from _utils import InstanceDb
from algbench import Benchmark
import networkx as nx
benchmark = Benchmark("03_benchmark_data")
instances = InstanceDb("./01_instances.zip")
def load_instance_and_run(instance_name: str, alg_params):
# load the instance outside the actual measurement
g = instances[instance_name]
def eval_greedy_alg(instance_name: str, alg_params, _instance: nx.Graph):
# arguments starting with `_` are not saved.
coloring = nx.coloring.greedy_coloring.greedy_color(_instance, **alg_params)
return { # the returned values are saved to the database
"num_vertices": _instance.number_of_nodes(),
"num_edges": _instance.number_of_edges(),
"coloring": coloring,
"n_colors": max(coloring.values()) + 1,
}
benchmark.add(eval_greedy_alg, instance_name, alg_params, g)
alg_params_to_evaluate = [
{"strategy": "largest_first", "interchange": True},
{"strategy": "largest_first", "interchange": False},
{"strategy": "random_sequential", "interchange": True},
{"strategy": "random_sequential", "interchange": False},
{"strategy": "smallest_last", "interchange": True},
{"strategy": "smallest_last", "interchange": False},
{"strategy": "independent_set"},
{"strategy": "connected_sequential_bfs", "interchange": True},
{"strategy": "connected_sequential_bfs", "interchange": False},
{"strategy": "connected_sequential_dfs", "interchange": True},
{"strategy": "connected_sequential_dfs", "interchange": False},
{"strategy": "saturation_largest_first"},
]
if __name__ == "__main__":
for instance_name in instances:
print(instance_name)
for conf in alg_params_to_evaluate:
load_instance_and_run(instance_name, conf)
benchmark.compress()
Analyzing the data
from algbench import describe, read_as_pandas, Benchmark
describe("./03_benchmark_data/")
parameters:
| func: eval_greedy_alg
| args:
|| instance_name: graph_0
|| alg_params:
||| strategy: largest_first
||| interchange: True
env:
| hostname: workstation-r7
| python_version: 3.10.9 (main, Jan 11 2023, 15:21:40) [GCC 11.2.0]
| python: /home/krupke/anaconda3/envs/mo310/bin/python3
| cwd: /home/krupke/Repositories/AlgBench/examples/graph_coloring
| environment: [{'name': 'virtualenv', 'path': '/home/krupke/.local/lib/python3.10/site-pack...
data:
| result:
|| num_vertices: 50
|| num_edges: 275
|| coloring:
||| 0: 2
||| 1: 0
||| 2: 1
||| 3: 1
||| 4: 3
||| 5: 1
||| 6: 4
||| 7: 3
||| 8: 3
||| 9: 3
||| 10: 1
||| 11: 4
||| 12: 1
||| 13: 2
||| 14: 3
||| 15: 0
||| 16: 0
||| 17: 0
||| 18: 0
||| 19: 1
||| ...
|| n_colors: 6
| timestamp: 2023-05-25T15:22:37.540734
| runtime: 0.0009615421295166016
| stdout:
| stderr:
| env_fingerprint: b2cee276004fd00bcb5343f9d8e9199c13c25fec
| args_fingerprint: 10ce65b7a61d5ecbfcb1f4e390d72122f7a1f6ec
# we can also see the raw data of the first entry using `front`
Benchmark("./03_benchmark_data/").front()
{'parameters': {'func': 'eval_greedy_alg',
'args': {'instance_name': 'graph_0',
'alg_params': {'strategy': 'largest_first', 'interchange': True}}},
'env': {'hostname': 'workstation-r7',
'python_version': '3.10.9 (main, Jan 11 2023, 15:21:40) [GCC 11.2.0]',
'python': '/home/krupke/anaconda3/envs/mo310/bin/python3',
'cwd': '/home/krupke/Repositories/AlgBench/examples/graph_coloring',
'environment': [{'name': 'virtualenv',
'path': '/home/krupke/.local/lib/python3.10/site-packages',
'version': '20.14.1'},
{'name': 'cfgv',
'path': '/home/krupke/.local/lib/python3.10/site-packages',
'version': '3.3.1'},
{'name': 'pre-commit',
'path': '/home/krupke/.local/lib/python3.10/site-packages',
'version': '2.18.1'},
{'name': 'identify',
'path': '/home/krupke/.local/lib/python3.10/site-packages',
'version': '2.4.12'},
{'name': 'py',
'path': '/home/krupke/.local/lib/python3.10/site-packages',
'version': '1.11.0'},
{'name': 'nodeenv',
'path': '/home/krupke/.local/lib/python3.10/site-packages',
'version': '1.6.0'},
...
'runtime': 0.0009615421295166016,
'stdout': '',
'stderr': '',
'env_fingerprint': 'b2cee276004fd00bcb5343f9d8e9199c13c25fec',
'args_fingerprint': '10ce65b7a61d5ecbfcb1f4e390d72122f7a1f6ec'}}
# we can extract a full pandas tables using `read_as_pandas`
t = read_as_pandas(
"./03_benchmark_data/",
lambda result: {
"instance": result["parameters"]["args"]["instance_name"],
"strategy": result["parameters"]["args"]["alg_params"]["strategy"],
"interchange": result["parameters"]["args"]["alg_params"].get(
"interchange", None
),
"colors": result["data"]["result"]["n_colors"],
},
)
t
instance strategy interchange colors
0 graph_0 largest_first True 6
1 graph_0 largest_first False 7
2 graph_0 random_sequential True 6
3 graph_0 random_sequential False 7
4 graph_0 smallest_last True 6
... ... ... ... ...
1195 graph_99 connected_sequential_bfs True 15
1196 graph_99 connected_sequential_bfs False 17
1197 graph_99 connected_sequential_dfs True 14
1198 graph_99 connected_sequential_dfs False 15
1199 graph_99 saturation_largest_first None 15
[1200 rows x 4 columns]
On doing good empirical evaluations of algorithms
To get a feeling on the interesting instances and parameters, or generally on where to look deeper, you should first perform an explorative study. For such an explorative study, you should select some random parameters and instances, and just look how the numbers look. Iteratively change the parameters and instances, until you know what to evaluate properly. At that point, you can state some research questions and design corresponding workhorse studies to answer them.
Here are some general hints:
- Create a separate folder for every study.
- Add a README.md into each folder that describes the study. At least describe in a sentence, who created this study when in which context.
- Have separated, numerated files for preparing, running, processing, checking, and evaluating the study.
- Extract a simplified pandas table from the database with only the important
data (e.g., stdout or environment information are only necessary for debugging
and don't need to be shared for evaluation). You can save pandas tables as
.json.zip
such that they are small and can simply be added to your Git, even when the full data is too large. - The file for checking the generated data should also describe it.
- Use a separate Jupyter-notebook for each family of plots you want to generate.
- Save the plots into files whose name you can easily trace back to the generating notebook. You will probably copy them later into some paper and half a year later, when you receive the reviews and want to do some changes, you have to find the code that generated them.
Using Git LFS for the data
The data are large binary files. Use Git LFS to add them to your repository more efficiently.
You can find a guide here on how to install Git LFS.
Run
git lfs install
to set up git LFS and
git lfs track "*.zip"
to manage all zips via LFS.
Alternatively, you can also just edit .gitattributes
by hand
*.zip filter=lfs diff=lfs merge=lfs -text
Finally, add .gitattributes
to git via
git add .gitattributes
Version History
- 0.1.3 Fixed bug in arg fingerprint set.
- 0.1.2 Fixed bug with empty rows in pandas table.
- 0.1.1 Fixed bug with
delete_if
. - 0.1.0 First complete version
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.