Skip to content

Latest commit

 

History

History
4690 lines (4496 loc) · 74.1 KB

File metadata and controls

4690 lines (4496 loc) · 74.1 KB

The content of this file was obtained with:

$ time run -g '("Clique",4)' -g '("Mesh",4)' -g '("RealLife",4)' -d Html -c

Benchmarks

Doing:



Using [("Clique",4),("Mesh",4),("RealLife",4)] as graphs

addEdge

Description: Add an edge (not already in the graph)

Clique

1 10 100 1000
Alga 72.12 ns 2.758 μs 304.4 μs 28.98 ms
Containers 88.16 ns 1.297 μs 121.4 μs 81.01 ms
Fgl 145.0 ns 19.18 μs 9.371 ms 3.411 s
Hash-Graph 197.2 ns 22.71 μs 7.616 ms 3.628 s

Mesh

1 10 100 1000
Alga 77.02 ns 821.0 ns 10.91 μs 113.0 μs
Containers 89.49 ns 622.0 ns 6.193 μs 73.91 μs
Fgl 148.5 ns 6.460 μs 219.8 μs 19.16 ms
Hash-Graph 197.0 ns 7.134 μs 221.1 μs 19.94 ms

RealLife

^[[B^[[B

0 1 2 3
Alga 1.351 μs 24.70 μs 194.1 μs 1.602 ms
Containers 834.0 ns 13.31 μs 113.8 μs 1.348 ms
Fgl 10.82 μs 547.1 μs 20.12 ms 588.7 ms
Hash-Graph 12.29 μs 546.2 μs 18.51 ms 575.9 ms

SUMMARY:

  • Containers was the fastest 27 times
  • Alga was the fastest 5 times

ABSTRACT: (Based on an average of the ratio between largest benchmarks)

  • Alga was 151.21 times faster than Hash-Graph
  • Containers was 105.65 times faster than Hash-Graph
  • Fgl was 1.05 times faster than Hash-Graph

addVertex

Description: Add a vertex (not already in the graph)

Clique

1 10 100 1000
Alga 54.09 ns 2.698 μs 279.8 μs 26.75 ms
Containers 107.4 ns 1.421 μs 124.0 μs 88.73 ms
Fgl 87.36 ns 19.12 μs 11.10 ms 3.396 s
Hash-Graph 116.2 ns 22.55 μs 7.917 ms 3.762 s

Mesh

1 10 100 1000
Alga 54.23 ns 750.1 ns 10.08 μs 109.2 μs
Containers 108.0 ns 739.1 ns 7.526 μs 78.35 μs
Fgl 91.16 ns 6.194 μs 225.1 μs 20.05 ms
Hash-Graph 113.3 ns 6.880 μs 230.3 μs 21.06 ms

RealLife

0 1 2 3
Alga 1.253 μs 23.21 μs 182.2 μs 1.503 ms
Containers 1.023 μs 14.46 μs 121.2 μs 1.445 ms
Fgl 11.11 μs 562.2 μs 21.23 ms 550.6 ms
Hash-Graph 12.34 μs 562.7 μs 19.73 ms 552.9 ms

SUMMARY:

  • Containers was the fastest 14 times
  • Alga was the fastest 6 times

There was 4 ex-aequo

ABSTRACT: (Based on an average of the ratio between largest benchmarks)

  • Alga was 166.92 times faster than Hash-Graph
  • Containers was 100.20 times faster than Hash-Graph
  • Fgl was 1.09 times faster than Hash-Graph

dff

Description: Produce a forest, obtained from a DFS (Deep First Search) of each vertex

Clique

1 10 100 1000
Alga 609.6 ns 30.67 μs 6.614 ms 857.0 ms
Containers 139.5 ns 3.219 μs 343.5 μs 101.0 ms
Fgl 264.1 ns 25.25 μs 11.57 ms 3.682 s
Hash-Graph 78.39 ns 25.85 μs 9.004 ms 3.926 s

Mesh

1 10 100 1000
Alga 588.7 ns 11.32 μs 165.7 μs 3.689 ms
Containers 140.3 ns 1.719 μs 18.23 μs 236.0 μs
Fgl 259.9 ns 11.20 μs 292.3 μs 19.66 ms
Hash-Graph 73.14 ns 8.289 μs 252.1 μs 20.14 ms

RealLife

0 1 2 3
Alga 17.29 μs 400.3 μs 5.837 ms 77.33 ms
Containers 2.568 μs 32.21 μs 287.0 μs 7.036 ms
Fgl 19.11 μs 690.8 μs 21.40 ms 575.6 ms
Hash-Graph 15.11 μs 586.0 μs 17.44 ms 540.3 ms

SUMMARY:

  • Containers was the fastest 10 times
  • Hash-Graph was the fastest 2 times

ABSTRACT: (Based on an average of the ratio between largest benchmarks)

  • Containers was 59.45 times faster than Hash-Graph
  • Alga was 5.41 times faster than Hash-Graph
  • Fgl was 1.02 times faster than Hash-Graph

edgeCount

Description: Count the edges of the graph

Clique

1 10 100 1000
Alga 51.68 ns 17.68 μs 3.405 ms 538.9 ms
Containers 41.59 ns 1.066 μs 107.9 μs 70.83 ms
Fgl 50.25 ns 18.05 μs 10.05 ms 3.346 s
Hash-Graph 55.24 ns 20.05 μs 7.648 ms 3.620 s

Mesh

1 10 100 1000
Alga 51.02 ns 4.832 μs 84.94 μs 1.463 ms
Containers 40.77 ns 382.1 ns 5.082 μs 53.40 μs
Fgl 44.22 ns 5.848 μs 203.3 μs 18.84 ms
Hash-Graph 52.64 ns 5.934 μs 199.1 μs 19.76 ms

RealLife

0 1 2 3
Alga 8.552 μs 253.0 μs 3.285 ms 48.20 ms
Containers 603.0 ns 10.81 μs 100.8 μs 1.174 ms
Fgl 10.32 μs 503.5 μs 18.87 ms 555.9 ms
Hash-Graph 10.47 μs 496.4 μs 17.56 ms 574.3 ms

SUMMARY:

  • Containers was the fastest 11 times

There was 1 ex-aequo

ABSTRACT: (Based on an average of the ratio between largest benchmarks)

  • Containers was 123.40 times faster than Hash-Graph
  • Alga was 7.91 times faster than Hash-Graph
  • Fgl was 1.07 times faster than Hash-Graph

edgeList

Description: Produce a list of the edges in the graph

Clique

1 10 100 1000
Alga 45.02 ns 17.64 μs 3.384 ms 480.9 ms
Containers 53.74 ns 1.660 μs 219.5 μs 73.73 ms
Fgl 42.50 ns 18.80 μs 9.586 ms 3.290 s
Hash-Graph 45.45 ns 20.37 μs 7.762 ms 3.738 s

Mesh

1 10 100 1000
Alga 45.04 ns 4.836 μs 85.89 μs 1.412 ms
Containers 55.53 ns 643.0 ns 8.628 μs 88.20 μs
Fgl 42.61 ns 6.108 μs 209.2 μs 19.97 ms
Hash-Graph 45.29 ns 5.794 μs 200.7 μs 20.17 ms

RealLife

0 1 2 3
Alga 8.370 μs 253.3 μs 3.420 ms 49.36 ms
Containers 983.6 ns 16.28 μs 148.8 μs 3.095 ms
Fgl 10.71 μs 512.2 μs 19.25 ms 621.4 ms
Hash-Graph 10.48 μs 504.2 μs 18.31 ms 563.5 ms

SUMMARY:

  • Containers was the fastest 10 times

There was 2 ex-aequo

ABSTRACT: (Based on an average of the ratio between largest benchmarks)

  • Containers was 101.38 times faster than Hash-Graph
  • Alga was 9.41 times faster than Hash-Graph
  • Fgl was 1.08 times faster than Hash-Graph

equality

Description: Test if two graphs are equals

Clique

1 10 100 1000
Alga 151.8 ns 24.86 μs 4.723 ms 694.8 ms
Containers 41.51 ns 1.081 μs 113.7 μs 80.74 ms
Fgl 181.9 ns 29.28 μs 11.70 ms 3.576 s
Hash-Graph 79.85 ns 22.66 μs 7.920 ms 3.518 s

Mesh

1 10 100 1000
Alga 153.2 ns 7.037 μs 122.6 μs 2.152 ms
Containers 40.31 ns 364.6 ns 4.846 μs 46.58 μs
Fgl 181.9 ns 10.59 μs 265.8 μs 19.00 ms
Hash-Graph 79.41 ns 7.013 μs 219.6 μs 18.48 ms

RealLife

0 1 2 3
Alga 11.50 μs 358.3 μs 4.712 ms 68.09 ms
Containers 549.0 ns 10.69 μs 95.32 μs 1.155 ms
Fgl 17.08 μs 616.9 μs 20.47 ms 547.5 ms
Hash-Graph 12.09 μs 546.8 μs 17.42 ms 542.7 ms

SUMMARY:

  • Containers was the fastest 22 times

There was 2 ex-aequo

ABSTRACT: (Based on an average of the ratio between largest benchmarks)

  • Containers was 111.91 times faster than Fgl
  • Alga was 5.96 times faster than Fgl
  • Hash-Graph was 1.03 times faster than Fgl

hasEdge

Description: Test if the given edge is in the graph (with arguments both in the graph and not in the graph (where applicable))

Clique

1 10 100 1000
Alga 50.19 ns 3.352 μs 498.1 μs 183.0 ms
Containers 38.11 ns 858.1 ns 90.20 μs 75.03 ms
Fgl 132.1 ns 18.19 μs 8.164 ms 3.329 s
Hash-Graph 113.9 ns 18.74 μs 7.322 ms 3.655 s

Mesh

1 10 100 1000
Alga 51.27 ns 978.7 ns 11.62 μs 152.1 μs
Containers 38.75 ns 293.8 ns 3.655 μs 40.63 μs
Fgl 125.0 ns 5.509 μs 198.3 μs 19.07 ms
Hash-Graph 118.6 ns 5.333 μs 198.2 μs 19.37 ms

RealLife

0 1 2 3
Alga 1.473 μs 25.91 μs 282.2 μs 6.916 ms
Containers 416.8 ns 7.998 μs 75.12 μs 944.5 μs
Fgl 9.339 μs 469.4 μs 16.96 ms 543.2 ms
Hash-Graph 9.781 μs 505.0 μs 18.33 ms 605.3 ms

ABSTRACT: (Based on an average of the ratio between largest benchmarks)

  • Containers was 124.08 times faster than Hash-Graph
  • Alga was 33.68 times faster than Hash-Graph
  • Fgl was 1.09 times faster than Hash-Graph

hasVertex

Description: Test if the given vertex is in the graph

Clique

1 10 100 1000
Alga 36.20 ns 873.1 ns 59.47 μs 6.111 ms
Containers 33.60 ns 773.0 ns 88.78 μs 70.13 ms
Fgl 56.77 ns 15.93 μs 7.607 ms 3.185 s
Hash-Graph 37.21 ns 18.46 μs 7.435 ms 3.593 s

Mesh

1 10 100 1000
Alga 35.60 ns 411.6 ns 4.024 μs 45.45 μs
Containers 32.97 ns 265.2 ns 3.583 μs 43.27 μs
Fgl 56.24 ns 4.953 μs 197.9 μs 18.94 ms
Hash-Graph 40.41 ns 4.965 μs 191.7 μs 20.55 ms

RealLife

0 1 2 3
Alga 498.7 ns 5.539 μs 69.34 μs 360.9 μs
Containers 391.7 ns 8.053 μs 74.56 μs 919.0 μs
Fgl 8.748 μs 470.6 μs 16.71 ms 545.8 ms
Hash-Graph 9.533 μs 490.6 μs 18.42 ms 617.3 ms

SUMMARY:

  • Alga was the fastest 23 times
  • Containers was the fastest 13 times

There was 8 ex-aequo

ABSTRACT: (Based on an average of the ratio between largest benchmarks)

  • Alga was 4251209.16 times faster than Hash-Graph
  • Containers was 129.61 times faster than Hash-Graph
  • Fgl was 1.14 times faster than Hash-Graph

isEmpty

Description: Test if the graph is empty

Clique

1 10 100 1000
Alga 34.26 ns 55.78 ns 55.83 ns 56.21 ns
Containers 31.80 ns 784.5 ns 86.15 μs 62.05 ms
Fgl 31.41 ns 12.20 μs 5.090 ms 2.598 s
Hash-Graph 30.53 ns 19.01 μs 7.358 ms 3.660 s

Mesh

1 10 100 1000
Alga 31.98 ns 57.75 ns 55.91 ns 56.82 ns
Containers 31.21 ns 270.0 ns 4.104 μs 34.66 μs
Fgl 30.86 ns 4.444 μs 191.6 μs 18.52 ms
Hash-Graph 30.57 ns 4.856 μs 193.3 μs 19.90 ms

RealLife

0 1 2 3
Alga 56.68 ns 55.96 ns 56.59 ns 55.72 ns
Containers 389.7 ns 7.943 μs 76.00 μs 921.1 μs
Fgl 7.775 μs 442.9 μs 16.03 ms 591.9 ms
Hash-Graph 9.349 μs 490.5 μs 18.49 ms 547.6 ms

SUMMARY:

  • Alga was the fastest 10 times

There was 2 ex-aequo

ABSTRACT: (Based on an average of the ratio between largest benchmarks)

  • Alga was 55016533.69 times faster than Hash-Graph
  • Containers was 147.25 times faster than Hash-Graph
  • Fgl was 1.34 times faster than Hash-Graph

mergeContext

Description: Merge a FGL context in the graph

Clique

1 10 100 1000
Fgl 127.3 ns 19.65 μs 10.84 ms 3.644 s
Hash-Graph 134.2 ns 22.35 μs 8.275 ms 3.637 s

Mesh

1 10 100 1000
Fgl 122.1 ns 6.470 μs 212.2 μs 18.58 ms
Hash-Graph 135.7 ns 6.823 μs 224.1 μs 18.64 ms

RealLife

0 1 2 3
Fgl 11.14 μs 524.2 μs 20.36 ms 552.4 ms
Hash-Graph 12.21 μs 549.4 μs 20.71 ms 551.1 ms

Not implemented for Containers because it is a nonsense. Not implemented for Alga because it is a nonsense.

SUMMARY:

  • Fgl was the fastest 9 times
  • Hash-Graph was the fastest 4 times

There was 23 ex-aequo

ABSTRACT: (Based on an average of the ratio between largest benchmarks)

  • Hash-Graph was 1.00 times faster than Fgl

reachable

Description: Produce a list of reachable vertices from a given one

Clique

1 10 100 1000
Alga 802.7 ns 24.79 μs 5.076 ms 725.8 ms
Containers 141.9 ns 1.910 μs 220.0 μs 77.65 ms
Fgl 335.5 ns 22.21 μs 10.38 ms 3.528 s
Hash-Graph 76.86 ns 21.64 μs 7.713 ms 3.736 s

Mesh

1 10 100 1000
Alga 795.0 ns 9.343 μs 131.2 μs 2.945 ms
Containers 140.5 ns 875.0 ns 8.857 μs 106.2 μs
Fgl 338.8 ns 9.245 μs 246.0 μs 19.03 ms
Hash-Graph 75.63 ns 6.666 μs 217.7 μs 19.42 ms

RealLife

0 1 2 3
Alga 14.42 μs 384.6 μs 4.939 ms 61.30 ms
Containers 1.258 μs 26.84 μs 165.2 μs 2.962 ms
Fgl 15.13 μs 709.4 μs 19.55 ms 558.9 ms
Hash-Graph 11.99 μs 574.3 μs 17.80 ms 554.6 ms

SUMMARY:

  • Containers was the fastest 20 times
  • Hash-Graph was the fastest 2 times

ABSTRACT: (Based on an average of the ratio between largest benchmarks)

  • Containers was 96.05 times faster than Hash-Graph
  • Alga was 6.00 times faster than Hash-Graph
  • Fgl was 1.03 times faster than Hash-Graph

removeEdge

Description: Remove an edge of the graph

Clique

10 100 1000
Alga 18.29 μs 8.461 ms 1.277 s
Containers 1.457 μs 116.7 μs 91.23 ms
Fgl 22.23 μs 9.930 ms 3.568 s
Hash-Graph 22.35 μs 7.810 ms 3.690 s

Mesh

10 100 1000
Alga 6.099 μs 85.10 μs 2.551 ms
Containers 674.7 ns 6.438 μs 65.30 μs
Fgl 7.715 μs 224.4 μs 19.56 ms
Hash-Graph 7.165 μs 224.9 μs 20.05 ms

RealLife

0 1 2 3
Alga 9.047 μs 199.9 μs 5.780 ms 56.08 ms
Containers 880.0 ns 13.73 μs 115.5 μs 1.364 ms
Fgl 12.17 μs 566.8 μs 20.31 ms 561.1 ms
Hash-Graph 12.17 μs 553.2 μs 18.94 ms 580.0 ms

ABSTRACT: (Based on an average of the ratio between largest benchmarks)

  • Containers was 98.90 times faster than Hash-Graph
  • Alga was 4.01 times faster than Hash-Graph
  • Fgl was 1.03 times faster than Hash-Graph

removeVertex

Description: Remove a vertex of the graph

Clique

1 10 100 1000
Alga 41.81 ns 5.458 μs 874.1 μs 261.2 ms
Containers 45.88 ns 1.536 μs 119.4 μs 75.03 ms
Fgl 95.03 ns 19.82 μs 10.55 ms 3.434 s
Hash-Graph 89.83 ns 25.59 μs 7.803 ms 3.658 s

Mesh

1 10 100 1000
Alga 42.15 ns 1.570 μs 21.49 μs 267.3 μs
Containers 45.51 ns 857.1 ns 10.82 μs 119.7 μs
Fgl 95.39 ns 6.573 μs 210.3 μs 19.54 ms
Hash-Graph 92.46 ns 8.124 μs 224.1 μs 20.75 ms

RealLife

0 1 2 3
Alga 2.366 μs 45.80 μs 491.3 μs 10.39 ms
Containers 1.317 μs 17.24 μs 134.8 μs 1.675 ms
Fgl 11.47 μs 531.2 μs 19.03 ms 559.3 ms
Hash-Graph 13.54 μs 562.8 μs 18.92 ms 550.1 ms

SUMMARY:

  • Containers was the fastest 28 times

There was 2 ex-aequo

ABSTRACT: (Based on an average of the ratio between largest benchmarks)

  • Containers was 102.29 times faster than Hash-Graph
  • Alga was 30.57 times faster than Hash-Graph
  • Fgl was 1.06 times faster than Hash-Graph

topSort

Description: Topological sorting of the vertices

Clique

1 10 100 1000
Alga 630.1 ns 30.49 μs 6.274 ms 991.2 ms
Containers 173.2 ns 3.374 μs 349.6 μs 105.0 ms
Fgl 463.3 ns 28.19 μs 10.52 ms 3.697 s
Hash-Graph 199.4 ns 28.38 μs 7.769 ms 3.697 s

Mesh

1 10 100 1000
Alga 625.9 ns 12.33 μs 185.2 μs 4.149 ms
Containers 169.7 ns 1.882 μs 19.86 μs 251.2 μs
Fgl 460.0 ns 14.04 μs 341.9 μs 24.82 ms
Hash-Graph 206.0 ns 12.37 μs 292.8 μs 21.03 ms

RealLife

0 1 2 3
Alga 19.00 μs 400.9 μs 6.216 ms 75.18 ms
Containers 2.815 μs 32.11 μs 298.5 μs 7.486 ms
Fgl 22.97 μs 793.7 μs 26.17 ms 653.8 ms
Hash-Graph 19.88 μs 531.0 μs 17.87 ms 595.1 ms

ABSTRACT: (Based on an average of the ratio between largest benchmarks)

  • Containers was 60.03 times faster than Fgl
  • Alga was 5.32 times faster than Fgl
  • Hash-Graph was 1.06 times faster than Fgl

transpose

Description: Transpose (invert all the edges) the graph

Clique

1 10 100 1000
Alga 38.71 ns 4.515 μs 497.0 μs 47.66 ms
Containers 103.2 ns 2.952 μs 466.9 μs 142.4 ms
Fgl 134.8 ns 31.11 μs 14.24 ms 3.891 s
Hash-Graph 69.94 ns 33.25 μs 12.24 ms 4.399 s

Mesh

1 10 100 1000
Alga 38.34 ns 1.334 μs 18.05 μs 196.8 μs
Containers 101.7 ns 1.249 μs 13.71 μs 185.2 μs
Fgl 132.3 ns 10.21 μs 264.1 μs 21.44 ms
Hash-Graph 69.69 ns 8.615 μs 251.1 μs 22.29 ms

RealLife

0 1 2 3
Alga 2.137 μs 40.26 μs 321.6 μs 2.601 ms
Containers 1.759 μs 30.62 μs 313.4 μs 6.828 ms
Fgl 17.61 μs 649.6 μs 24.12 ms 714.2 ms
Hash-Graph 15.23 μs 683.0 μs 23.38 ms 582.3 ms

SUMMARY:

  • Alga was the fastest 4 times
  • Containers was the fastest 4 times

There was 4 ex-aequo

ABSTRACT: (Based on an average of the ratio between largest benchmarks)

  • Alga was 125.06 times faster than Hash-Graph
  • Containers was 57.24 times faster than Hash-Graph
  • Fgl was 1.05 times faster than Hash-Graph

vertexCount

Description: Count the vertices of the graph

Clique

1 10 100 1000
Alga 44.06 ns 3.470 μs 800.4 μs 204.4 ms
Containers 32.68 ns 996.0 ns 85.82 μs 84.43 ms
Fgl 33.80 ns 12.86 μs 4.997 ms 2.707 s
Hash-Graph 35.17 ns 18.57 μs 7.493 ms 3.679 s

Mesh

1 10 100 1000
Alga 44.14 ns 979.0 ns 14.77 μs 248.2 μs
Containers 32.98 ns 268.2 ns 3.834 μs 33.93 μs
Fgl 33.80 ns 4.561 μs 191.8 μs 18.48 ms
Hash-Graph 35.03 ns 5.149 μs 192.5 μs 18.53 ms

RealLife

0 1 2 3
Alga 1.582 μs 41.72 μs 701.1 μs 11.45 ms
Containers 391.6 ns 7.954 μs 74.28 μs 929.1 μs
Fgl 8.252 μs 443.8 μs 16.06 ms 521.7 ms
Hash-Graph 9.660 μs 494.5 μs 17.94 ms 566.9 ms

SUMMARY:

  • Containers was the fastest 10 times

There was 2 ex-aequo

ABSTRACT: (Based on an average of the ratio between largest benchmarks)

  • Containers was 113.55 times faster than Hash-Graph
  • Alga was 23.88 times faster than Hash-Graph
  • Fgl was 1.32 times faster than Hash-Graph

vertexList

Description: Produce a list of the vertices in the graph

Clique

1 10 100 1000
Alga 52.50 ns 3.676 μs 743.7 μs 225.0 ms
Containers 44.04 ns 907.4 ns 136.8 μs 75.21 ms
Fgl 60.56 ns 15.03 μs 6.064 ms 2.841 s
Hash-Graph 35.31 ns 18.65 μs 8.874 ms 3.599 s

Mesh

1 10 100 1000
Alga 51.06 ns 1.093 μs 15.61 μs 255.7 μs
Containers 43.38 ns 395.4 ns 4.234 μs 44.22 μs
Fgl 60.50 ns 5.339 μs 201.9 μs 18.12 ms
Hash-Graph 34.43 ns 5.275 μs 191.5 μs 17.87 ms

RealLife

0 1 2 3
Alga 1.792 μs 42.48 μs 672.2 μs 11.51 ms
Containers 553.8 ns 8.867 μs 77.89 μs 931.1 μs
Fgl 9.500 μs 473.0 μs 16.19 ms 529.2 ms
Hash-Graph 9.491 μs 482.9 μs 17.04 ms 540.7 ms

SUMMARY:

  • Containers was the fastest 10 times
  • Hash-Graph was the fastest 2 times

ABSTRACT: (Based on an average of the ratio between largest benchmarks)

  • Containers was 119.57 times faster than Hash-Graph
  • Alga was 23.44 times faster than Hash-Graph
  • Fgl was 1.22 times faster than Hash-Graph