Algorithm Optimisation: A Real Example - My insights

@steadbytes

This week I read Algorithm Optimisation: A Real Example and I recommend you all to read it too.
It's a good article.

I do think some items can be improved and I'll elaborate on them here.

• When dealing with a large range , plots should be logarithmic to improve visibility. In Algorithm Optimisation: A Real Example the plots are in raw values , making the different curves and points on the curves unusable.

• When benchmarking , we should remove outliers , the samples set being used by Algorithm Optimisation: A Real Example [1000 , 10000 , 100000 , 500000 , 1000000 , 2000000 , 5000000 , 10000000 , 20000000 , 50000000 , 100000000 , 200000000 , 500000000]
  Sample points 1000 , 10000 are too small and are too susceptible to noise (the buffer size used is 4096). From my tests these sample points vary too much and their results doesn't reflect the 10X size difference.

• When benchmarking , we should run the same test multiple times , one iteration isn't enough. For example , the machine used to run might be under a different load and if we only run once we won't be able to mitigate this effect. Hence I used Benchmark IPS to run each test multiple times.

Furthermore , while the actual solution given by Algorithm Optimisation: A Real Example is very good and show out of box thinking.
I suggest a different , much simpler solution that also have better performance.

Algorithm Optimisation: A Real Example still requires a malloc call the size of the file being read.
My proposed solution is instead of using the innovative linked list , we simply allocate all the memory needed beforehand and read the file directly into out result variable.

while ((read_len = read(fd, *data + len, BUFSIZE)) > 0) {
      len += read_len;
    }

This gives us almost 2X on our largest sample point of 100000000.

Code gist