diff options
| -rw-r--r-- | report/report.tex | 12 |
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} |