non-algorithmic factors

1 files changed, 12 insertions, 0 deletions

diff --git a/report/report.tex b/report/report.tex
index ae260a1..201d69b 100644
--- a/report/report.tex
+++ b/report/report.tex
@@ -344,6 +344,18 @@ random. We also see that Quicksort behaves as expected with a best-case runtime
 of $\mathcal O(n\log n)$ when the input is random, and a worst-case runtime of
 $\mathcal O(n^2)$ when the input is either sorted or reversely sorted.
 
+\subsection{Nonagorithmic factors}
+Although the asymptotic run times are caused by the algorithms themselves,
+the total run times are also greatly affected by the concrete implementations
+of highly repeated functions. A good example is our old generate_output function,
+which was extremely slow.  This function has since been removed and exchanged with
+a new approach using a buffer. The implementation looped over the sorted list and
+used 4 write syscalls per coordinate: One for printing x-coordinate, one for
+printing y, one for tab, and one for a newline character. Thus 4 million syscalls
+would be needed just to print a sorted list of 1 million coordinates, which causes
+an enormous program overhead. So the point is that even though the problem studied
+is efficient sorting, correct usage of registers, memory and syscalls will greatly
+affect and boost performance. 
 
 \section{Conclusion}