Comment by jiggawatts
19 hours ago
This is why array random access and linked-list random access have wildly different performance characteristics.
Another thing I noticed is that the spike on the left hand side of his graphs is the overhead of file access.
Without this overhead, small array random access should have a lot better per-element cost.
To be clear, the overhead on the left part is only due to file access for the last two graphs (the "direct" summation ones with just one blue line). For all the charts with both blue and yellow lines, there is no file access happening on the left hand side of the graphs, since the file gets read into memory first and then the measurements are run.