core/clist: use insertion sort

[maribu]

Contribution description

This replaces the previous clist sort implementation, which used a merge sort, with a simple insertion sort implementation.

The motivation is as follow:

1. The insertion sort is smaller (code size)
2. The performance benefit of the merge sort would only become noticeable on data sets that would be to large to comfortably handle on the MCUs RIOT targets
3. The previous implementation looked like a good candidate for the IOCCC, while the insertion sort is trivial to understand
4. Static analysis could provide for two statements an example control flow path that would trigger a NULL pointer dereferencation. The current code has no such defects.

Testing procedure

1. There is a unit test that should still pass.
2. Adding -fanalyzer should now be happy with the code
3. The code should now be understandable without spending hours on a white board

Issues/PRs references

None

[maribu]

I also improved the unit test a little bit to cover a few edge cases and to verify that the sorted list is actually sorted.

[riot-ci]

Murdock results

:x: FAILED

66f4a66b5e9583535ef3c27cf5a038c131587fb2 fixup! core/clist: use insertion sort

Success	Failures	Total	Runtime
5943	0	9842	05m:49s

Artifacts

[maribu]

Depends on and includes:

• [ ] https://github.com/RIOT-OS/RIOT/pull/21402
• [ ] https://github.com/RIOT-OS/RIOT/pull/21403

[maribu]

Some benchmarks:

native64

master (merge sort, IOCCC variant)

main(): This is RIOT! (Version: 2025.04-devel-520-g98b01-tests/bench/runtime_coreapis)
Runtime of Selected Core API functions

                 nop loop:       430us  ---   0.000us per call  ---  2325581395 calls per sec

             mutex_init():       893us  ---   0.000us per call  ---  1119820828 calls per sec
        mutex lock/unlock:    909438us  ---   0.909us per call  ---    1099580 calls per sec

       thread_flags_set():    319468us  ---   0.319us per call  ---    3130203 calls per sec
     thread_flags_clear():    325462us  ---   0.325us per call  ---    3072555 calls per sec
thread flags set/wait any:    978442us  ---   0.978us per call  ---    1022032 calls per sec
thread flags set/wait all:    972636us  ---   0.972us per call  ---    1028133 calls per sec
thread flags set/wait one:    979552us  ---   0.979us per call  ---    1020874 calls per sec

        msg_try_receive():    334414us  ---   0.334us per call  ---    2990305 calls per sec
              msg_avail():      4767us  ---   0.004us per call  ---  209775540 calls per sec

   clist_sort (#4, worst):     19603us  ---   0.019us per call  ---   51012600 calls per sec
     clist_sort (#4, avg):     20029us  ---   0.020us per call  ---   49927604 calls per sec
   clist_sort (#8, worst):     47127us  ---   0.047us per call  ---   21219258 calls per sec
     clist_sort (#8, avg):     49394us  ---   0.049us per call  ---   20245373 calls per sec
  clist_sort (#16, worst):    119396us  ---   0.119us per call  ---    8375489 calls per sec
    clist_sort (#16, avg):    115471us  ---   0.115us per call  ---    8660183 calls per sec
  clist_sort (#32, worst):    278381us  ---   0.278us per call  ---    3592199 calls per sec
    clist_sort (#32, avg):    312818us  ---   0.312us per call  ---    3196746 calls per sec
  clist_sort (#64, worst):    636261us  ---   0.636us per call  ---    1571682 calls per sec
    clist_sort (#64, avg):    780777us  ---   0.780us per call  ---    1280775 calls per sec
 clist_sort (#128, worst):   1424094us  ---   1.424us per call  ---     702200 calls per sec
   clist_sort (#128, avg):   1874443us  ---   1.874us per call  ---     533491 calls per sec
 clist_sort (#256, worst):   3235114us  ---   3.235us per call  ---     309108 calls per sec
   clist_sort (#256, avg):   4239094us  ---   4.239us per call  ---     235899 calls per sec

[SUCCESS]
{ "threads": [{ "name": "idle", "stack_size": 16384, "stack_used": 1080 }]}
{ "threads": [{ "name": "main", "stack_size": 20480, "stack_used": 4760 }]}

This PR (simple insertion sort)

main(): This is RIOT! (Version: 2025.04-devel-522-gc33cb94-core/clist_sort_insertion_sort)
Runtime of Selected Core API functions

                 nop loop:       593us  ---   0.000us per call  ---  1686340640 calls per sec

             mutex_init():      1268us  ---   0.001us per call  ---  788643533 calls per sec
        mutex lock/unlock:   1038304us  ---   1.038us per call  ---     963109 calls per sec

       thread_flags_set():    327235us  ---   0.327us per call  ---    3055907 calls per sec
     thread_flags_clear():    331057us  ---   0.331us per call  ---    3020627 calls per sec
thread flags set/wait any:    979440us  ---   0.979us per call  ---    1020991 calls per sec
thread flags set/wait all:    976936us  ---   0.976us per call  ---    1023608 calls per sec
thread flags set/wait one:    979527us  ---   0.979us per call  ---    1020900 calls per sec

        msg_try_receive():    330618us  ---   0.330us per call  ---    3024638 calls per sec
              msg_avail():      2910us  ---   0.002us per call  ---  343642611 calls per sec

   clist_sort (#4, worst):     16905us  ---   0.016us per call  ---   59154096 calls per sec
     clist_sort (#4, avg):     15056us  ---   0.015us per call  ---   66418703 calls per sec
   clist_sort (#8, worst):     33741us  ---   0.033us per call  ---   29637532 calls per sec
     clist_sort (#8, avg):     22386us  ---   0.022us per call  ---   44670776 calls per sec
  clist_sort (#16, worst):     73995us  ---   0.073us per call  ---   13514426 calls per sec
    clist_sort (#16, avg):     56454us  ---   0.056us per call  ---   17713536 calls per sec
  clist_sort (#32, worst):    194442us  ---   0.194us per call  ---    5142921 calls per sec
    clist_sort (#32, avg):    106041us  ---   0.106us per call  ---    9430314 calls per sec
  clist_sort (#64, worst):    394818us  ---   0.394us per call  ---    2532812 calls per sec
    clist_sort (#64, avg):    253255us  ---   0.253us per call  ---    3948589 calls per sec
 clist_sort (#128, worst):    753123us  ---   0.753us per call  ---    1327804 calls per sec
   clist_sort (#128, avg):    601839us  ---   0.601us per call  ---    1661573 calls per sec
 clist_sort (#256, worst):   1514474us  ---   1.514us per call  ---     660295 calls per sec
   clist_sort (#256, avg):   1330050us  ---   1.330us per call  ---     751851 calls per sec

[SUCCESS]
{ "threads": [{ "name": "idle", "stack_size": 16384, "stack_used": 1080 }]}
{ "threads": [{ "name": "main", "stack_size": 20480, "stack_used": 4760 }]}

same54-xpro

master (merge sort, IOCCC variant)

main(): This is RIOT! (Version: 2025.04-devel-520-g98b01-tests/bench/runtime_coreapis)
Runtime of Selected Core API functions

                 nop loop:     33335us  ---   0.033us per call  ---   29998500 calls per sec

             mutex_init():         2us  ---   0.000us per call  ---  1783793664 calls per sec
        mutex lock/unlock:    541669us  ---   0.541us per call  ---    1846145 calls per sec

       thread_flags_set():    275002us  ---   0.275us per call  ---    3636337 calls per sec
     thread_flags_clear():    266669us  ---   0.266us per call  ---    3749967 calls per sec
thread flags set/wait any:    941669us  ---   0.941us per call  ---    1061944 calls per sec
thread flags set/wait all:    800002us  ---   0.800us per call  ---    1249996 calls per sec
thread flags set/wait one:    933335us  ---   0.933us per call  ---    1071426 calls per sec

        msg_try_receive():    416669us  ---   0.416us per call  ---    2399986 calls per sec
              msg_avail():    133335us  ---   0.133us per call  ---    7499906 calls per sec

   clist_sort (#4, worst):      4127us  ---   4.127us per call  ---     242306 calls per sec
     clist_sort (#4, avg):      4202us  ---   4.202us per call  ---     237981 calls per sec
   clist_sort (#8, worst):     10352us  ---  10.352us per call  ---      96599 calls per sec
     clist_sort (#8, avg):     10358us  ---  10.358us per call  ---      96543 calls per sec
  clist_sort (#16, worst):     25110us  ---  25.110us per call  ---      39824 calls per sec
    clist_sort (#16, avg):     25002us  ---  25.002us per call  ---      39996 calls per sec
  clist_sort (#32, worst):     59235us  ---  59.235us per call  ---      16881 calls per sec
    clist_sort (#32, avg):     62160us  ---  62.160us per call  ---      16087 calls per sec
  clist_sort (#64, worst):    136694us  ---  136.694us per call  ---       7315 calls per sec
    clist_sort (#64, avg):    147785us  ---  147.785us per call  ---       6766 calls per sec
 clist_sort (#128, worst):    310018us  ---  310.018us per call  ---       3225 calls per sec
   clist_sort (#128, avg):    341994us  ---  341.994us per call  ---       2924 calls per sec
 clist_sort (#256, worst):    693477us  ---  693.477us per call  ---       1442 calls per sec
   clist_sort (#256, avg):    777652us  ---  777.652us per call  ---       1285 calls per sec

[SUCCESS]

This PR (simple insertion sort)

main(): This is RIOT! (Version: 2025.04-devel-522-gc33cb94-core/clist_sort_insertion_sort)
Runtime of Selected Core API functions

                 nop loop:     33335us  ---   0.033us per call  ---   29998500 calls per sec

             mutex_init():         2us  ---   0.000us per call  ---  1783793664 calls per sec
        mutex lock/unlock:    541669us  ---   0.541us per call  ---    1846145 calls per sec

       thread_flags_set():    275001us  ---   0.275us per call  ---    3636350 calls per sec
     thread_flags_clear():    266668us  ---   0.266us per call  ---    3749981 calls per sec
thread flags set/wait any:    941669us  ---   0.941us per call  ---    1061944 calls per sec
thread flags set/wait all:    800002us  ---   0.800us per call  ---    1249996 calls per sec
thread flags set/wait one:    933336us  ---   0.933us per call  ---    1071425 calls per sec

        msg_try_receive():    416668us  ---   0.416us per call  ---    2399992 calls per sec
              msg_avail():    133335us  ---   0.133us per call  ---    7499906 calls per sec

   clist_sort (#4, worst):      2252us  ---   2.252us per call  ---     444049 calls per sec
     clist_sort (#4, avg):      2443us  ---   2.443us per call  ---     409332 calls per sec
   clist_sort (#8, worst):      4852us  ---   4.852us per call  ---     206100 calls per sec
     clist_sort (#8, avg):      3918us  ---   3.918us per call  ---     255232 calls per sec
  clist_sort (#16, worst):     10052us  ---  10.052us per call  ---      99482 calls per sec
    clist_sort (#16, avg):      8485us  ---   8.485us per call  ---     117855 calls per sec
  clist_sort (#32, worst):     20452us  ---  20.452us per call  ---      48894 calls per sec
    clist_sort (#32, avg):     15069us  ---  15.069us per call  ---      66361 calls per sec
  clist_sort (#64, worst):     41252us  ---  41.252us per call  ---      24241 calls per sec
    clist_sort (#64, avg):     31985us  ---  31.985us per call  ---      31264 calls per sec
 clist_sort (#128, worst):     82852us  ---  82.852us per call  ---      12069 calls per sec
   clist_sort (#128, avg):     68819us  ---  68.819us per call  ---      14530 calls per sec
 clist_sort (#256, worst):    166052us  ---  166.052us per call  ---       6022 calls per sec
   clist_sort (#256, avg):    140085us  ---  140.085us per call  ---       7138 calls per sec

[SUCCESS]

[kaspar030]

I'm all for a fixed clist sort, but the benchmark seems misleading, the worst case is actually not the worst case for this insertion sort.

The performance benefit of the merge sort would only become noticeable on data sets that would be to large to comfortably handle on the MCUs RIOT targets

With the "fixed worst case", it becomes noticable with less than 32 list entries. At 32 list entries, the old merge sort is already 50% faster then this insertion sort (worst case). The nrf's memory fits 1000 times 32 list entries.

With 16384 list entries, merge sort can sort the list five times per second. (insertion sort is still running and will take a while, I will update this post when it is done.). This might be a size that is unlikely to come up on our little devices.

This insertion sort is still much faster in the "avg case" of this benchmark. (Which it shouldn't be actually. :slightly_smiling_face:)