Skip to content

Latest commit

 

History

History

AutoBenchmark

README.md

AutoBenchmark

Determine the speed of various AceSorting functions, for various array sizes.

Version: AceSorting v1.0.0

DO NOT EDIT: This file was auto-generated using make README.md.

Dependencies

This program depends on the following libraries:

How to Generate

This requires the AUniter script to execute the Arduino IDE programmatically.

The Makefile has rules to generate the *.txt results file for several microcontrollers that I usually support, but the $ make benchmarks command does not work very well because the USB port of the microcontroller is a dynamically changing parameter. I created a semi-automated way of collect the *.txt files:

  1. Connect the microcontroller to the serial port. I usually do this through a USB hub with individually controlled switch.
  2. Type $ auniter ports to determine its /dev/ttyXXX port number (e.g. /dev/ttyUSB0 or /dev/ttyACM0).
  3. If the port is USB0 or ACM0, type $ make nano.txt, etc.
  4. Switch off the old microontroller.
  5. Go to Step 1 and repeat for each microcontroller.

The generate_table.awk program reads one of *.txt files and prints out an ASCII table that can be directly embedded into this README.md file. For example the following command produces the table in the Nano section below:

$ ./generate_table.awk < nano.txt

Fortunately, we no longer need to run generate_table.awk for each *.txt file. The process has been automated using the generate_readme.py script which will be invoked by the following command:

$ make README.md

CPU Time Changes

v0.1

  • Initial results.
  • The C-library qsort() is far slower than the C++ version because it uses a callback to a comparison function through a function pointer.

v0.3

  • No performance change after rerouting 2-argument sorting functions into the 3-argument versions using a default lambda expression.

v0.3+

  • Add N=1000 for SparkFun Pro Micro because it has 2.5kB of ram.
    • Except for C-library qsort() which seems to run out of stack space due to recursion.
    • The Shell Sort algorithms seem to hold up well compared to Quick Sort for N=1000.
    • Increase Shell Sort to Quick Sort recommendation cut over from N >= ~100 to ~1000.

v1.0.0

  • Upgrade various tool chains. No significant changes to runtimes.

Results

The following results show the runtime of each sorting function in milliseconds, when sorting different array sizes.

Arduino Nano

  • 16MHz ATmega328P
  • Arduino IDE 1.8.16, Arduino CLI 0.19.2
  • Arduino AVR Boards 1.8.3
  • micros() has a resolution of 4 microseconds
+---------------------+------------------------+---------+---------+---------+
|            \      N |    10 |    30 |    100 |     300 |    1000 |    3000 |
| Function    \       |       |       |        |         |         |         |
|---------------------+-------+-------+--------+---------+---------+---------|
| bubbleSort()        | 0.099 | 1.044 | 12.305 | 118.589 |         |         |
| insertionSort()     | 0.049 | 0.251 |  2.463 |  21.287 |         |         |
| selectionSort()     | 0.087 | 0.552 |  5.364 |  46.272 |         |         |
|---------------------+-------+-------+--------+---------+---------+---------|
| shellSortClassic()  | 0.074 | 0.305 |  1.711 |   6.868 |         |         |
| shellSortKnuth()    | 0.100 | 0.325 |  1.431 |   5.683 |         |         |
| shellSortTokuda()   | 0.075 | 0.336 |  1.617 |   6.555 |         |         |
|---------------------+-------+-------+--------+---------+---------+---------|
| combSort13()        | 0.167 | 0.533 |  2.215 |   8.260 |         |         |
| combSort13m()       | 0.165 | 0.557 |  2.232 |   8.176 |         |         |
| combSort133()       | 0.084 | 0.400 |  1.968 |   7.730 |         |         |
| combSort133m()      | 0.087 | 0.419 |  1.979 |   7.805 |         |         |
|---------------------+-------+-------+--------+---------+---------+---------|
| quickSortMiddle()   | 0.096 | 0.374 |  1.582 |   5.536 |         |         |
| quickSortMedian()   | 0.117 | 0.423 |  1.717 |   5.905 |         |         |
| quickSortMdnSwppd() | 0.092 | 0.337 |  1.397 |   4.895 |         |         |
|---------------------+-------+-------+--------+---------+---------+---------|
| qsort()             | 0.208 | 0.827 |  3.643 |  13.068 |         |         |
+---------------------+-------+-------+--------+---------+---------+---------+

SparkFun Pro Micro

  • 16 MHz ATmega32U4
  • Arduino IDE 1.8.16, Arduino CLI 0.19.2
  • SparkFun AVR Boards 1.1.13
  • micros() has a resolution of 4 microseconds
+---------------------+------------------------+---------+---------+---------+
|            \      N |    10 |    30 |    100 |     300 |    1000 |    3000 |
| Function    \       |       |       |        |         |         |         |
|---------------------+-------+-------+--------+---------+---------+---------|
| bubbleSort()        | 0.083 | 1.211 | 13.093 | 118.403 |         |         |
| insertionSort()     | 0.044 | 0.259 |  2.515 |  21.941 | 240.911 |         |
| selectionSort()     | 0.084 | 0.555 |  5.388 |  46.517 | 509.037 |         |
|---------------------+-------+-------+--------+---------+---------+---------|
| shellSortClassic()  | 0.076 | 0.311 |  1.738 |   6.895 |  28.869 |         |
| shellSortKnuth()    | 0.100 | 0.336 |  1.450 |   5.681 |  25.273 |         |
| shellSortTokuda()   | 0.076 | 0.339 |  1.636 |   6.543 |  28.090 |         |
|---------------------+-------+-------+--------+---------+---------+---------|
| combSort13()        | 0.163 | 0.532 |  2.235 |   8.240 |  36.409 |         |
| combSort13m()       | 0.166 | 0.559 |  2.225 |   8.279 |  34.916 |         |
| combSort133()       | 0.085 | 0.385 |  2.030 |   7.787 |  34.229 |         |
| combSort133m()      | 0.088 | 0.422 |  1.991 |   7.713 |  34.179 |         |
|---------------------+-------+-------+--------+---------+---------+---------|
| quickSortMiddle()   | 0.098 | 0.367 |  1.601 |   5.659 |  22.104 |         |
| quickSortMedian()   | 0.118 | 0.432 |  1.701 |   5.984 |  22.732 |         |
| quickSortMdnSwppd() | 0.087 | 0.335 |  1.385 |   4.871 |  18.914 |         |
|---------------------+-------+-------+--------+---------+---------+---------|
| qsort()             | 0.202 | 0.876 |  3.685 |  13.098 |         |         |
+---------------------+-------+-------+--------+---------+---------+---------+

SAMD21 M0 Mini

  • 48 MHz ARM Cortex-M0+
  • Arduino IDE 1.8.16, Arduino CLI 0.19.2
  • SparkFun SAMD Core 1.8.4
+---------------------+------------------------+---------+---------+---------+
|            \      N |    10 |    30 |    100 |     300 |    1000 |    3000 |
| Function    \       |       |       |        |         |         |         |
|---------------------+-------+-------+--------+---------+---------+---------|
| bubbleSort()        | 0.035 | 0.309 |  3.417 |  31.707 | 368.210 |         |
| insertionSort()     | 0.014 | 0.096 |  0.881 |   8.132 |  87.196 |         |
| selectionSort()     | 0.024 | 0.160 |  1.628 |  14.305 | 157.637 |         |
|---------------------+-------+-------+--------+---------+---------+---------|
| shellSortClassic()  | 0.016 | 0.066 |  0.350 |   1.405 |   5.861 |  22.452 |
| shellSortKnuth()    | 0.019 | 0.066 |  0.289 |   1.153 |   5.112 |  19.448 |
| shellSortTokuda()   | 0.020 | 0.082 |  0.390 |   1.555 |   6.673 |  24.186 |
|---------------------+-------+-------+--------+---------+---------+---------|
| combSort13()        | 0.035 | 0.121 |  0.515 |   1.940 |   8.554 |  31.045 |
| combSort13m()       | 0.036 | 0.126 |  0.532 |   1.963 |   8.252 |  29.795 |
| combSort133()       | 0.021 | 0.092 |  0.473 |   1.842 |   8.258 |  28.208 |
| combSort133m()      | 0.021 | 0.100 |  0.473 |   1.829 |   7.968 |  28.906 |
|---------------------+-------+-------+--------+---------+---------+---------|
| quickSortMiddle()   | 0.022 | 0.074 |  0.319 |   1.088 |   4.246 |  14.142 |
| quickSortMedian()   | 0.026 | 0.089 |  0.344 |   1.161 |   4.343 |  14.457 |
| quickSortMdnSwppd() | 0.020 | 0.071 |  0.284 |   0.999 |   3.775 |  12.605 |
|---------------------+-------+-------+--------+---------+---------+---------|
| qsort()             | 0.053 | 0.208 |  0.862 |   3.110 |  12.192 |  41.025 |
+---------------------+-------+-------+--------+---------+---------+---------+

STM32

  • STM32 "Blue Pill", STM32F103C8, 72 MHz ARM Cortex-M3
  • Arduino IDE 1.8.16, Arduino CLI 0.19.2
  • STM32duino 2.0.0
+---------------------+------------------------+---------+---------+---------+
|            \      N |    10 |    30 |    100 |     300 |    1000 |    3000 |
| Function    \       |       |       |        |         |         |         |
|---------------------+-------+-------+--------+---------+---------+---------|
| bubbleSort()        | 0.020 | 0.178 |  2.226 |  19.830 | 228.062 |         |
| insertionSort()     | 0.009 | 0.050 |  0.505 |   4.213 |  45.588 |         |
| selectionSort()     | 0.018 | 0.102 |  1.023 |   8.931 |  98.184 |         |
|---------------------+-------+-------+--------+---------+---------+---------|
| shellSortClassic()  | 0.015 | 0.057 |  0.304 |   1.243 |   5.209 |  19.819 |
| shellSortKnuth()    | 0.013 | 0.058 |  0.283 |   1.135 |   5.055 |  19.186 |
| shellSortTokuda()   | 0.012 | 0.047 |  0.226 |   0.905 |   3.888 |  14.132 |
|---------------------+-------+-------+--------+---------+---------+---------|
| combSort13()        | 0.017 | 0.080 |  0.404 |   1.592 |   7.157 |  26.489 |
| combSort13m()       | 0.018 | 0.083 |  0.413 |   1.589 |   6.966 |  25.383 |
| combSort133()       | 0.016 | 0.073 |  0.381 |   1.499 |   6.636 |  22.964 |
| combSort133m()      | 0.017 | 0.080 |  0.381 |   1.468 |   6.436 |  22.875 |
|---------------------+-------+-------+--------+---------+---------+---------|
| quickSortMiddle()   | 0.017 | 0.062 |  0.253 |   0.904 |   3.610 |  12.357 |
| quickSortMedian()   | 0.020 | 0.071 |  0.284 |   0.992 |   3.762 |  12.718 |
| quickSortMdnSwppd() | 0.015 | 0.057 |  0.236 |   0.850 |   3.298 |  11.342 |
|---------------------+-------+-------+--------+---------+---------+---------|
| qsort()             | 0.033 | 0.135 |  0.612 |   2.214 |   8.876 |  30.671 |
+---------------------+-------+-------+--------+---------+---------+---------+

ESP8266

  • NodeMCU 1.0 clone, 80MHz ESP8266
  • Arduino IDE 1.8.16, Arduino CLI 0.19.2
  • ESP8266 Boards 3.0.2
+---------------------+------------------------+---------+---------+---------+
|            \      N |    10 |    30 |    100 |     300 |    1000 |    3000 |
| Function    \       |       |       |        |         |         |         |
|---------------------+-------+-------+--------+---------+---------+---------|
| bubbleSort()        | 0.017 | 0.145 |  1.604 |  14.477 | 169.490 |         |
| insertionSort()     | 0.008 | 0.036 |  0.338 |   2.895 |  31.947 |         |
| selectionSort()     | 0.013 | 0.071 |  0.715 |   6.270 |  69.023 |         |
|---------------------+-------+-------+--------+---------+---------+---------|
| shellSortClassic()  | 0.008 | 0.032 |  0.180 |   0.719 |   3.030 |  11.560 |
| shellSortKnuth()    | 0.009 | 0.031 |  0.149 |   0.588 |   2.608 |  10.006 |
| shellSortTokuda()   | 0.007 | 0.029 |  0.137 |   0.552 |   2.358 |   8.532 |
|---------------------+-------+-------+--------+---------+---------+---------|
| combSort13()        | 0.014 | 0.052 |  0.238 |   0.899 |   4.001 |  14.567 |
| combSort13m()       | 0.015 | 0.056 |  0.240 |   0.903 |   3.903 |  14.197 |
| combSort133()       | 0.010 | 0.043 |  0.209 |   0.852 |   3.840 |  13.288 |
| combSort133m()      | 0.010 | 0.047 |  0.222 |   0.850 |   3.733 |  13.341 |
|---------------------+-------+-------+--------+---------+---------+---------|
| quickSortMiddle()   | 0.013 | 0.044 |  0.175 |   0.616 |   2.353 |   8.087 |
| quickSortMedian()   | 0.015 | 0.049 |  0.189 |   0.634 |   2.370 |   7.764 |
| quickSortMdnSwppd() | 0.012 | 0.037 |  0.149 |   0.513 |   1.951 |   6.597 |
|---------------------+-------+-------+--------+---------+---------+---------|
| qsort()             | 0.028 | 0.094 |  0.405 |   1.472 |   5.826 |  19.875 |
+---------------------+-------+-------+--------+---------+---------+---------+

ESP32

  • ESP32-01 Dev Board, 240 MHz Tensilica LX6
  • Arduino IDE 1.8.16, Arduino CLI 0.19.2
  • ESP32 Boards 1.0.6
+---------------------+------------------------+---------+---------+---------+
|            \      N |    10 |    30 |    100 |     300 |    1000 |    3000 |
| Function    \       |       |       |        |         |         |         |
|---------------------+-------+-------+--------+---------+---------+---------|
| bubbleSort()        | 0.006 | 0.050 |  0.579 |   5.806 |  66.006 |         |
| insertionSort()     | 0.004 | 0.016 |  0.152 |   1.340 |  14.679 |         |
| selectionSort()     | 0.006 | 0.030 |  0.301 |   2.666 |  29.460 |         |
|---------------------+-------+-------+--------+---------+---------+---------|
| shellSortClassic()  | 0.004 | 0.014 |  0.077 |   0.304 |   1.268 |   4.877 |
| shellSortKnuth()    | 0.004 | 0.013 |  0.061 |   0.246 |   1.105 |   4.195 |
| shellSortTokuda()   | 0.004 | 0.014 |  0.066 |   0.259 |   1.113 |   4.027 |
|---------------------+-------+-------+--------+---------+---------+---------|
| combSort13()        | 0.005 | 0.019 |  0.095 |   0.375 |   1.685 |   6.245 |
| combSort13m()       | 0.005 | 0.021 |  0.098 |   0.372 |   1.656 |   5.952 |
| combSort133()       | 0.004 | 0.018 |  0.093 |   0.366 |   1.622 |   5.648 |
| combSort133m()      | 0.005 | 0.021 |  0.093 |   0.366 |   1.584 |   5.594 |
|---------------------+-------+-------+--------+---------+---------+---------|
| quickSortMiddle()   | 0.005 | 0.017 |  0.072 |   0.254 |   1.000 |   3.379 |
| quickSortMedian()   | 0.006 | 0.018 |  0.072 |   0.251 |   0.953 |   3.222 |
| quickSortMdnSwppd() | 0.005 | 0.014 |  0.058 |   0.207 |   0.829 |   2.830 |
|---------------------+-------+-------+--------+---------+---------+---------|
| qsort()             | 0.009 | 0.034 |  0.145 |   0.531 |   2.090 |   7.246 |
+---------------------+-------+-------+--------+---------+---------+---------+

Teensy 3.2

  • 96 MHz ARM Cortex-M4
  • Arduino IDE 1.8.16, Arduino CLI 0.19.2
  • Teensyduino 1.55
  • Compiler options: "Faster"
+---------------------+------------------------+---------+---------+---------+
|            \      N |    10 |    30 |    100 |     300 |    1000 |    3000 |
| Function    \       |       |       |        |         |         |         |
|---------------------+-------+-------+--------+---------+---------+---------|
| bubbleSort()        | 0.008 | 0.087 |  0.970 |   9.312 | 104.824 |         |
| insertionSort()     | 0.006 | 0.038 |  0.371 |   3.391 |  36.381 |         |
| selectionSort()     | 0.010 | 0.065 |  0.654 |   5.716 |  62.882 |         |
|---------------------+-------+-------+--------+---------+---------+---------|
| shellSortClassic()  | 0.007 | 0.030 |  0.162 |   0.646 |   2.718 |  10.450 |
| shellSortKnuth()    | 0.006 | 0.027 |  0.130 |   0.527 |   2.354 |   8.936 |
| shellSortTokuda()   | 0.007 | 0.029 |  0.135 |   0.543 |   2.306 |   8.356 |
|---------------------+-------+-------+--------+---------+---------+---------|
| combSort13()        | 0.008 | 0.037 |  0.181 |   0.710 |   3.233 |  11.701 |
| combSort13m()       | 0.008 | 0.038 |  0.188 |   0.721 |   3.131 |  11.470 |
| combSort133()       | 0.008 | 0.035 |  0.175 |   0.693 |   3.169 |  10.778 |
| combSort133m()      | 0.008 | 0.038 |  0.179 |   0.712 |   3.036 |  10.818 |
|---------------------+-------+-------+--------+---------+---------+---------|
| quickSortMiddle()   | 0.007 | 0.026 |  0.112 |   0.397 |   1.522 |   5.217 |
| quickSortMedian()   | 0.009 | 0.031 |  0.120 |   0.416 |   1.602 |   5.303 |
| quickSortMdnSwppd() | 0.007 | 0.025 |  0.102 |   0.361 |   1.417 |   4.804 |
|---------------------+-------+-------+--------+---------+---------+---------|
| qsort()             | 0.016 | 0.071 |  0.313 |   1.164 |   4.599 |  15.684 |
+---------------------+-------+-------+--------+---------+---------+---------+