CGraphLib

Introduction

cgraphlib is a C extension for Python that provides a more efficient implementation of the internal toplogical graph sorter. This is the default implementation Taskade uses for execution.

The extension was inspired by graphlib. The other advantage is that coupled with the fact that taskade has no dependencies it is possible to still use taskade on versions of python that don't support graphlib.

Benchmark

To benchmark the performance of Taskade, we will be using the benchmark.py script by calling benchmark.sh. This script will create a random DAG with a specified number of tasks and dependencies, and then execute the DAG using Taskade and a few other popular libraries.

Execution Type	Task Count	cgraphlib Avg ± Std (s)	pygraphlib Avg ± Std (s)	cgraphlib x faster
Sync	1	0.000112 ± 0.000008	0.000123 ± 0.000004	1.10
Sync	10	0.000743 ± 0.000012	0.000798 ± 0.000024	1.07
Sync	100	0.017548 ± 0.000144	0.029783 ± 0.000235	1.70
Sync	500	0.238663 ± 0.001475	0.555585 ± 0.003965	2.33
Sync	1000	0.570467 ± 0.010899	1.391227 ± 0.020914	2.44
Sync	5000	3.860468 ± 0.060122	9.574127 ± 0.053635	2.48
Sync	10000	8.330627 ± 0.055351	20.504808 ± 0.248797	2.46
Sync	50000	53.619465 ± 0.318738	123.350060 ± 0.548668	2.30
Sync	100000	141.262903 ± 0.509695	290.261497 ± 0.827542	2.05
Threaded	1	0.000308 ± 0.000068	0.000369 ± 0.000095	1.20
Threaded	10	0.001401 ± 0.000135	0.001436 ± 0.000094	1.03
Threaded	100	0.019505 ± 0.000144	0.031843 ± 0.000247	1.63
Threaded	500	0.242867 ± 0.001770	0.566135 ± 0.002655	2.33
Threaded	1000	0.571698 ± 0.005058	1.421466 ± 0.004682	2.49
Threaded	5000	3.887257 ± 0.051935	9.790658 ± 0.119144	2.52
Threaded	10000	8.609358 ± 0.085867	21.039031 ± 0.219296	2.44
Threaded	50000	58.770154 ± 0.301631	131.879641 ± 0.322479	2.24
Threaded	100000	155.800541 ± 0.653699	311.092993 ± 0.508799	2.00
Process	1	1.977064 ± 0.679840	2.682294 ± 0.927356	1.36
Process	10	1.975413 ± 0.677598	2.676924 ± 0.924303	1.36
Process	100	2.015815 ± 0.678133	2.728529 ± 0.923138	1.35
Process	500	2.289209 ± 0.676583	3.311899 ± 0.922781	1.45
Process	1000	2.675230 ± 0.669569	4.204118 ± 0.919089	1.57
Process	5000	6.487916 ± 0.661428	13.031447 ± 0.924691	2.01
Process	10000	11.832457 ± 0.659005	25.058576 ± 0.857200	2.12
Process	50000	70.737856 ± 1.080970	146.915526 ± 0.944690	2.08
Process	100000	190.708719 ± 1.356575	353.259943 ± 0.801520	1.85
Async	1	0.000131 ± 0.000015	0.000145 ± 0.000013	1.10
Async	10	0.000490 ± 0.000015	0.000554 ± 0.000008	1.13
Async	100	0.012828 ± 0.000110	0.024954 ± 0.000117	1.95
Async	500	0.205863 ± 0.001378	0.520926 ± 0.003159	2.53
Async	1000	0.500223 ± 0.003213	1.321445 ± 0.010514	2.64
Async	5000	3.429843 ± 0.035481	9.155247 ± 0.077005	2.67
Async	10000	7.529800 ± 0.069054	19.617411 ± 0.184248	2.61
Async	50000	49.364607 ± 0.270251	120.704542 ± 0.377445	2.45
Async	100000	133.263472 ± 0.751990	291.191692 ± 2.279661	2.19