Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
4691 lines (4496 sloc) 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
You can’t perform that action at this time.