Open Onotate opened 3 months ago
Runtime measurement for original code: For generate_nice_graph:
0.00 seconds to generate the graph.
21 iterations achieved in 9.58 seconds
PageRank of vertex 0: 0.001000
PageRank of vertex 100: 0.001000
PageRank of vertex 200: 0.001000
PageRank of vertex 300: 0.001000
PageRank of vertex 400: 0.001000
PageRank of vertex 500: 0.001000
PageRank of vertex 600: 0.001000
PageRank of vertex 700: 0.001000
PageRank of vertex 800: 0.001000
PageRank of vertex 900: 0.001000
Sum of all pageranks = 1.000000000000, total diff = 0.000000000000, max diff = 0.000000000000 and min diff = 0.000000000000.
Total time taken: 9.5852 seconds.
For generate_sneaky_graph:
0.00 seconds to generate the graph.
43 iterations achieved in 9.93 seconds
PageRank of vertex 0: 0.002541
PageRank of vertex 100: 0.001726
PageRank of vertex 200: 0.001494
PageRank of vertex 300: 0.001302
PageRank of vertex 400: 0.001127
PageRank of vertex 500: 0.000962
PageRank of vertex 600: 0.000800
PageRank of vertex 700: 0.000641
PageRank of vertex 800: 0.000483
PageRank of vertex 900: 0.000322
Sum of all pageranks = 1.000000000000, total diff = 1.168591825342, max diff = 0.624703182089 and min diff = 0.000000000000.
Total time taken: 9.9311 seconds.
The original code, though clear, uses many excessive code that can be changed to improve memory access and reduce looping operations:
memset
andmemcpy
for initialization and copy of arrays instead of using loops.The main calculation to update the page rank maybe refactored to reduce cache thrashing, but this may be a separate issue.
This issue thread will contain the runtime measurement of the original code, which will be posted later.