search

alesbe / sorting-visualizer

Sorting visualizer made with SFML and C++ 📊
MIT License
17 stars 11 forks source link

[BUG]: Stopping some algorithms bugs the visualizer #15

Closed alesbe closed 2 years ago

alesbe commented 2 years ago

Describe you problem / suggestion:

Stopping Quick Sort does not stop the algorithm, it continues trying to sort in a weird way and after a while, the algorithm finishes.

bug

Steps to reproduce (optional):

Possible fix (optional):

Pressing backspace only clears and populates the array with sorted elements. Maybe we should change how the algorithm is stopped. (Joining the thread instead of detaching it?)

OS

alesbe commented 2 years ago

quickSort() does not check if the array is sorted to continue sorting, it does it in "one round". For example, the bubble sort repeats the algorithm until is sorted, and before each round checks if is already sorted, that does not happen with algorithms like quick sort, so clearing and populating the array does not work in this case.

We should implement a way to stop algorithms instead of sorting manually the array using clear and populate. Maybe using mutex to stop the process (sort thread)?

bazuin-32 commented 2 years ago

I want to first mention that I haven't done a lot of multithreaded programming in C++, but I have done some, so take my suggestions with a grain of salt.

The solution I have used for things like this in the past is to have a bool or std::atomic<bool> called interrupt, or something like that. It is initially set to false, and when the main thread wants to stop the processing thread, it sets it to true. The processing thread is always checking if interrupt has been set to true, and if it is then it returns as soon as possible. After setting the interrupt, the main thread can call join() on the processing thread which will wait until the thread finishes cleanup and returns, at which point the program can continue.

I don't think a mutex is really necessary in this case, since the processing thread never needs to modify the interrupt variable, it only reads from it. The last paragraph of this stack overflow answer leads me to believe that a std::atomic<bool> would be better here.

Regardless of the implementation, there's a few things I would like to point out:

  1. Right now, the main thread calls sortingThread.detach() after starting it. From what I've been able to find out, there's no way to stop a detached thread nicely, so that would need to change. Besides, the only reason you need to detach the thread right now is because you don't join it, if you make sure to join it then the detach is not necessary. Personally I think would be a better design anyways, but let me know if you think otherwise.
  2. The sorting thread runs in the SortController, but the actual sorting is done in the algo::*Sort functions. This means that the interrupt needs to be accessible for reading within both of these places, so that they can return when it is set to true and pop off the call stack back up to where the thread was started. Achieving this requires that the function signatures of all the sorting functions be changed to take a reference to this interrupt variable.
  3. NOTE: this one is more personal preference, don't feel bad to disagree and just let me know. Partially because of (2), I think all the threading, interrupt work, etc. should be moved to the SortController, and main can just call things like sortController.start(), sortController.stop(), etc. This would make it so that the interrupt variable only has to be passed down 1 "level" (to the algo::*Sort functions), and not 2 "levels" (first to SortController, then sort functions).

I know this is kind of a lot, it may not be the best solution, but I'm just offering my thoughts. Let me know what you think.

alesbe commented 2 years ago

You're completely right, I'm definitely implementing this. It's my first time using multi-threading so I didn't know about some things like std::atomic<bool>.

Also, creating a thread inside SortController instead of main() seems like a better idea!

Right now, the main thread calls sortingThread.detach() after starting it. From what I've been able to find out, there's no way to stop a detached thread nicely, so that would need to change. Besides, the only reason you need to detach the thread right now is because you don't join it, if you make sure to join it then the detach is not necessary. Personally I think would be a better design anyways, but let me know if you think otherwise.

Yes, the decision to detach the thread was because I didn't know how to detect when the vector is sorted from main to join it, so the solution to stop the thread was (kind of a workaround) to clear the vector, and repopulate, so the algorithm would detect that it's already sorted and stop the process.

NOTE: this one is more personal preference, don't feel bad to disagree and just let me know. Partially because of (2), I think all the threading, interrupt work, etc. should be moved to the SortController, and main can just call things like sortController.start(), sortController.stop(), etc. This would make it so that the interrupt variable only has to be passed down 1 "level" (to the algo::*Sort functions), and not 2 "levels" (first to SortController, then sort functions).

This seems like the best approach, I'll try to implement it.

Thank you so much for this! Also, maybe SortController.sortElements vector needs some changes, I don't think that it's safe to read directly the vector from main thread and modifying it from the other.

alesbe commented 2 years ago

I'm a bit busy these weeks and I never implemented something like this before so it's a bit hard for me to solve this issue in a short time, if anyone is having this issue, sorry!

I'll try to fix it when I find some time. If anyone is interested in solving this issue there are two solutions that comes to mind:

bazuin-32 commented 2 years ago

Ok, so I got a somewhat working solution now, but there is this one issue that I'm not sure about. When the sorting finishes on its own, the animation does a nice "sweep" from left to right. When it is interrupted though, it pauses briefly and then suddenly all turns green. I've attached a recording to try to show it better.

https://user-images.githubusercontent.com/86376856/172028483-0c10a277-8e55-4c8e-b565-dae8c5fd969a.mp4

When building in release mode (with optimizations), the pause is less but it is still there and the animation still isn't as clean.

I was hoping you might be able to think of something that I haven't. For reference, here is the diff of my changes.

Also, please let me know if you'd like me to change anything as far as code style, and I'll gladly do that.

Thanks.

alesbe commented 2 years ago

I can't test the changes right now because I'm outside, but everything looks really good!

Don't worry about the animation for now, I was trying to solve the issue myself a few days ago and I encounter the same bug when trying to join the thread without detaching it when pressing backspace.

Thank you so much for your contribution, also the changes to SortController makes more sense instead of making everything public, there are some design decisions that I made just because it was just a small project, but now more people are getting interested so this type of changes are always good!

Again, thanks for your time! You can do the PR if you want and I'll check it in a few hours, I created a dev branch for development and leave main for "official" versions, make sure to pull the changes from there before doing the PR! :)

bazuin-32 commented 2 years ago

I just realized what the problem was when the sorting thread is joined (or in the process of joining) the animation blocks the drawing thread until it is finished, and then the screen is updated after all the bars have turned green. I just added another thread just for running the animation, which can be detached, and that seems to solve that issue.