Permalink
Switch branches/tags
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
1864 lines (1706 sloc) 30.3 KB

Benchmarks

Doing:



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

addEdge

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

Clique

1 10 100 1000
Alga 44.80 ns 165.5 ns 1.203 μs 11.28 μs
Containers 76.18 ns 548.7 ns 38.71 μs 23.49 ms
Fgl 132.1 ns 2.156 μs 198.6 μs 28.05 ms
Hash-Graph 165.8 ns 3.959 μs 379.4 μs 39.55 ms

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

  • Alga was 3506.42 times faster than Hash-Graph
  • Containers was 1.68 times faster than Hash-Graph
  • Fgl was 1.41 times faster than Hash-Graph

addVertex

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

Clique

1 10 100 1000
Alga 34.91 ns 142.8 ns 1.057 μs 10.72 μs
Containers 94.81 ns 637.2 ns 39.74 μs 24.49 ms
Fgl 75.32 ns 2.002 μs 195.7 μs 27.97 ms
Hash-Graph 98.69 ns 3.936 μs 375.1 μs 41.25 ms

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

  • Alga was 3848.57 times faster than Hash-Graph
  • Containers was 1.68 times faster than Hash-Graph
  • Fgl was 1.47 times faster than Hash-Graph

creation

Description: Create a graph from a list of edges

Clique

1 10 100 1000
Alga 45.29 ns 627.5 ns 35.93 μs 5.769 ms
Containers 51.65 ns 1.212 μs 116.3 μs 83.19 ms
Fgl 39.24 ns 18.53 μs 10.27 ms 3.227 s
Hash-Graph 29.39 ns 21.98 μs 7.351 ms 3.604 s

SUMMARY:

  • Alga was the fastest 3 times
  • Hash-Graph was the fastest 1 times

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

  • Alga was 624.77 times faster than Hash-Graph
  • Containers was 43.33 times faster than Hash-Graph
  • Fgl was 1.12 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 572.9 ns 14.35 μs 3.380 ms 417.1 ms
Containers 113.1 ns 2.335 μs 169.7 μs 29.44 ms
Fgl 205.2 ns 5.940 μs 573.4 μs 121.0 ms
Hash-Graph 63.26 ns 5.782 μs 560.5 μs 113.6 ms

SUMMARY:

  • Containers was the fastest 3 times
  • Hash-Graph was the fastest 1 times

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

  • Containers was 14.17 times faster than Alga
  • Hash-Graph was 3.67 times faster than Alga
  • Fgl was 3.45 times faster than Alga

edgeCount

Description: Count the edges of the graph

Clique

1 10 100 1000
Alga 39.07 ns 3.561 μs 137.3 μs 97.17 ms
Containers 28.15 ns 257.2 ns 28.44 μs 21.22 ms
Fgl 33.19 ns 1.876 μs 208.1 μs 112.2 ms
Hash-Graph 39.78 ns 1.004 μs 58.04 μs 6.288 ms

SUMMARY:

  • Containers was the fastest 3 times
  • Hash-Graph was the fastest 1 times

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

  • Hash-Graph was 17.85 times faster than Fgl
  • Containers was 5.29 times faster than Fgl
  • Alga was 1.16 times faster than Fgl

edgeList

Description: Produce a list of the edges in the graph

Clique

1 10 100 1000
Alga 33.99 ns 3.597 μs 146.5 μs 84.28 ms
Containers 37.56 ns 861.9 ns 78.68 μs 22.73 ms
Fgl 32.31 ns 2.974 μs 322.8 μs 131.1 ms
Hash-Graph 33.83 ns 1.792 μs 305.1 μs 245.6 ms

SUMMARY:

  • Containers was the fastest 3 times

There was 1 ex-aequo

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

  • Containers was 10.80 times faster than Hash-Graph
  • Alga was 2.91 times faster than Hash-Graph
  • Fgl was 1.87 times faster than Hash-Graph

equality

Description: Test if two graphs are equals

Clique

1 10 100 1000
Alga 392.3 ns 4.616 μs 126.1 μs 10.47 ms
Containers 29.05 ns 266.4 ns 23.92 μs 10.57 ms
Fgl 162.7 ns 13.87 μs 3.047 ms 569.8 ms
Hash-Graph 64.49 ns 4.106 μs 436.8 μs 56.09 ms

SUMMARY:

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

There was 1 ex-aequo

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

  • Containers was 104.41 times faster than Fgl
  • Alga was 77.93 times faster than Fgl
  • Hash-Graph was 18.54 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 37.33 ns 188.1 ns 1.282 μs 13.74 μs
Containers 27.25 ns 97.83 ns 898.0 ns 9.442 μs
Fgl 118.6 ns 1.351 μs 18.39 μs 458.8 μs
Hash-Graph 98.48 ns 148.0 ns 162.9 ns 177.8 ns

SUMMARY:

  • Hash-Graph was the fastest 12 times
  • Containers was the fastest 6 times

There was 1 ex-aequo

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

  • Hash-Graph was 3059.71 times faster than Fgl
  • Containers was 51.47 times faster than Fgl
  • Alga was 37.64 times faster than Fgl

hasVertex

Description: Test if the given vertex is in the graph

Clique

1 10 100 1000
Alga 23.10 ns 100.0 ns 571.1 ns 5.494 μs
Containers 21.83 ns 22.00 ns 21.64 ns 21.65 ns
Fgl 43.11 ns 613.1 ns 11.56 μs 327.2 μs
Hash-Graph 25.55 ns 32.01 ns 37.02 ns 41.35 ns

SUMMARY:

  • Containers was the fastest 11 times

There was 3 ex-aequo

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

  • Containers was 11.74 times faster than Alga
  • Hash-Graph was 6.26 times faster than Alga
  • Fgl was 1.42 times faster than Alga

isEmpty

Description: Test if the graph is empty

Clique

1 10 100 1000
Alga 19.80 ns 23.74 ns 22.80 ns 23.10 ns
Containers 18.15 ns 18.08 ns 18.06 ns 18.05 ns
Fgl 18.90 ns 19.26 ns 18.28 ns 18.83 ns
Hash-Graph 17.80 ns 19.05 ns 17.97 ns 19.58 ns

SUMMARY:

There was 4 ex-aequo

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

  • Containers was 1.28 times faster than Alga
  • Fgl was 1.23 times faster than Alga
  • Hash-Graph was 1.18 times faster than Alga

mergeContext

Description: Merge a FGL context in the graph

Clique

1 10 100 1000
Fgl 110.9 ns 1.989 μs 198.2 μs 28.23 ms
Hash-Graph 117.5 ns 3.667 μs 379.8 μs 39.42 ms

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

SUMMARY:

  • Fgl was the fastest 11 times
  • Hash-Graph was the fastest 1 times

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

  • Fgl was 1.39 times faster than Hash-Graph

reachable

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

Clique

1 10 100 1000
Alga 743.8 ns 9.689 μs 1.586 ms 213.2 ms
Containers 122.6 ns 1.063 μs 81.28 μs 16.26 ms
Fgl 279.4 ns 4.613 μs 320.0 μs 61.30 ms
Hash-Graph 61.33 ns 2.891 μs 279.1 μs 68.27 ms

SUMMARY:

  • Hash-Graph was the fastest 4 times
  • Containers was the fastest 3 times

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

  • Hash-Graph was 221.32 times faster than Alga
  • Containers was 25.66 times faster than Alga
  • Fgl was 3.46 times faster than Alga

removeEdge

Description: Remove an edge of the graph

Clique

10 100 1000
Alga 2.381 μs 20.60 μs 255.7 μs
Containers 644.8 ns 39.54 μs 23.64 ms
Fgl 4.435 μs 238.1 μs 30.54 ms
Hash-Graph 4.026 μs 367.6 μs 41.58 ms

SUMMARY:

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

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

  • Alga was 163.06 times faster than Hash-Graph
  • Containers was 1.76 times faster than Hash-Graph
  • Fgl was 1.36 times faster than Hash-Graph

removeVertex

Description: Remove a vertex of the graph

Clique

1 10 100 1000
Alga 30.90 ns 340.8 ns 2.928 μs 30.81 μs
Containers 34.90 ns 755.9 ns 42.36 μs 22.37 ms
Fgl 83.19 ns 2.529 μs 213.2 μs 29.73 ms
Hash-Graph 78.62 ns 6.574 μs 435.7 μs 42.43 ms

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

  • Alga was 1377.35 times faster than Hash-Graph
  • Containers was 1.90 times faster than Hash-Graph
  • Fgl was 1.43 times faster than Hash-Graph

topSort

Description: Topological sorting of the vertices

Clique

1 10 100 1000
Alga 586.5 ns 15.48 μs 2.971 ms 395.6 ms
Containers 153.3 ns 2.491 μs 172.2 μs 28.08 ms
Fgl 421.3 ns 9.675 μs 820.7 μs 142.3 ms
Hash-Graph 206.5 ns 7.264 μs 339.8 μs 36.24 ms

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

  • Containers was 14.09 times faster than Alga
  • Hash-Graph was 10.92 times faster than Alga
  • Fgl was 2.78 times faster than Alga

transpose

Description: Transpose (invert all the edges) the graph

Clique

1 10 100 1000
Alga 25.77 ns 313.6 ns 2.838 μs 28.99 μs
Containers 88.96 ns 2.061 μs 272.4 μs 96.98 ms
Fgl 114.6 ns 12.88 μs 2.182 ms 396.2 ms
Hash-Graph 52.62 ns 13.91 μs 4.246 ms 773.6 ms

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

  • Alga was 26686.27 times faster than Hash-Graph
  • Containers was 7.98 times faster than Hash-Graph
  • Fgl was 1.95 times faster than Hash-Graph

vertexCount

Description: Count the vertices of the graph

Clique

1 10 100 1000
Alga 30.68 ns 201.0 ns 2.281 μs 37.06 μs
Containers 20.87 ns 20.95 ns 20.94 ns 20.90 ns
Fgl 20.56 ns 102.3 ns 917.4 ns 10.53 μs
Hash-Graph 22.32 ns 83.46 ns 792.2 ns 8.835 μs

SUMMARY:

  • Containers was the fastest 3 times

There was 1 ex-aequo

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

  • Containers was 1773.10 times faster than Alga
  • Hash-Graph was 4.19 times faster than Alga
  • Fgl was 3.52 times faster than Alga

vertexList

Description: Produce a list of the vertices in the graph

Clique

1 10 100 1000
Alga 40.90 ns 308.6 ns 3.293 μs 45.92 μs
Containers 31.70 ns 150.3 ns 1.072 μs 10.39 μs
Fgl 53.32 ns 459.8 ns 4.914 μs 46.78 μs
Hash-Graph 23.10 ns 201.0 ns 2.247 μs 26.21 μs

SUMMARY:

  • Containers was the fastest 3 times
  • Hash-Graph was the fastest 1 times

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

  • Containers was 4.50 times faster than Fgl
  • Hash-Graph was 1.79 times faster than Fgl
  • Alga was 1.02 times faster than Fgl