is your benchmark in the actual board?

SD sorting is demand-by-user task which is not performance critical. Screen update once in a second and tools like Octoprint don't repeatedly request file list at all. However, increasing use of flash and, especially, RAM is very much undesirable.

SD sorting is demand-by-user task which is not performance critical. Screen update once in a second and tools like Octoprint don't repeatedly request file list at all. However, increasing use of flash and, especially, RAM is very much undesirable.

I submitted issue #28064 which this came from. User wait time isn't the issue, but the sort time is causing the watchdog timer to expire forcing a continuous reboot on power up. (more details can be read above)

I'm responsible for being critical about the bubblesort. Bubblesort = bad was pounded into me throughout university and I guess it stuck.

Using a better sort vs additional RAM use is a tough discussion. If it was just for user experience, I'd say save the RAM.

Microcontroller programming is specialized. You always have to consider the memory and flash usage as both are a very limited resource as are cpu cycles.

If you want to add an option to do a quick sort that is fine, but it has to be optional so those that do not want to allocate resources to it can stick to bubble sort.

Microcontroller programming is specialized. You always have to consider the memory and flash usage as both are a very limited resource as are cpu cycles.

If you want to add an option to do a quick sort that is fine, but it has to be optional so those that do not want to allocate resources to it can stick to bubble sort.

totally agree.

is your benchmark in the actual board?

@dbuezas no this was taken from a quick script I wrote up to test/compare the two sorts using the code. I suppose what I can do make an actual test and log the results somehow... unless I am able to make this happen in Simulator. I'm able to load a bunch of .gcode in an .img file, but will this work in the simulator?

Using a better sort vs additional RAM use is a tough discussion. If it was just for user experience, I'd say save the RAM.

@TheAndr0id thats understandable, Its possible to optimize the code in some way. ~70bytes wont really make or break it seeing that there arent any conflicts with the test configs
edit: my mistake, i mean bytes, not KB.
I've since updated the code and it uses the same exact memory. theres no changes when it comes to flash/ram

updated code now uses same exact memory/flash like theres no changes

heres some more stuff to consider

• separate bubble/quick sort functions results in more memory. 24B for bubble, 32B for quick
• adding quick sort results in 72B total (now with improved changes)
• • I know before I said it didn't add any, but quicksort() had to be changed for safety

You could measure the actual time it takes with millis() and then writing to serial.

You could measure the actual time it takes with millis() and then writing to serial.

so far I did try that, not sure exactly where to put, results are inconclusive or similar enough.
I put a start time right before function, and stop time right after - well for the simulator.

Most important thing is to keep the RAM usage from increasing, and if Quick Sort is always faster and always uses no extra RAM, then we can just replace the bubble sort entirely with quick sort.

Most important thing is to keep the RAM usage from increasing, and if Quick Sort is always faster and always uses no extra RAM, then we can just replace the bubble sort entirely with quick sort.

Well, originally it did use exactly 72bytes more, then I revised it and it made no change,
then I had to revise:

  void CardReader::_quicksort(uint8_t* arr, int16_t low, int16_t high) {
    if (low < high) {
        int16_t pi = _partition(arr, low, high);
        _quicksort(arr, low, pi - 1);
        _quicksort(arr, pi + 1, high);
    }
  }

in - update naming, use both bubble and quick sort

The recursive quick sort has been replaced with an iterative version to avoid potential stack overflows, which resulted in an extra 72bytes oddly enough.
if it matters, technically we can remove the functions and save 24B for bubble, 32B for quick to place all that code within presort() like it was to begin with.

i see it was

  void CardReader::presort() {
...
    const int16_t fileCnt = get_num_items();

and that gave an error with NOMORE, so then should we rename the arguments for bubblesort()/quicksort() which use fileCnt?

Recursion will end up using more ram at runtime.

I'd suggest putting your energy into something actually useful, like implementing sorting by modification timestamp, instead of making changes for the sake of changes.

I'd suggest putting your energy into something actually useful, like implementing sorting by modification timestamp, instead of making changes for the sake of changes.

well it isn't for that, but for performance and optimization, and who knows may actually end up being better in the long run. but I did explicitly state "I'm not sure how this will do"
and that is actually a good idea, sort by time; to have either the oldest or newest files first...unfortunately setting preferences is usually set during compile time - so then there would need to be like a little menu with options for how to sort.

well it isn't for that, but for performance and optimization

how often you run file sorting? Operations that use sorted list take longer than sorting itself, so, again, optimizing it is very moot. We aren't sorting millions of names to make difference even remotely noticeable. So, since it is infrequently used operation, minimizing flash and ram(both static allocation and runtime stack use) use is priority.

unfortunately setting preferences is usually set during compile time - so then there would need to be like a little menu with options for how to sort.

For screen it is already selected via defines - either sorting by name or by place in FAT.
File list gcode already has means for selecting sorting order.

minimizing flash and ram(both static allocation and runtime stack use) use is priority.

so far that difference is minute. no difference in ram, barely any for flash

I wanna say this is ready for review to merge. I can't comment on an actual performance comparison, but you can just lookup that Quick sort is much better in ways than Bubble sort regarding that.

if someone can whip up some code that spews results to terminal i can probably test on a real machine. Simulator doesn't do it justice.