Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Some algorithms don't work with long strings #142

Closed
3 tasks done
Morwenn opened this issue Jan 30, 2019 · 1 comment
Closed
3 tasks done

Some algorithms don't work with long strings #142

Morwenn opened this issue Jan 30, 2019 · 1 comment
Labels
Milestone

Comments

@Morwenn
Copy link
Owner

Morwenn commented Jan 30, 2019

A new tests uncovered issues when sing some sorters with long strings (too big for SSO to apply). I thought it was mostly due to self-move (as with issue #141), but apparently more algorithms break, so while self-moves are a problem, there are other issues at play. Here are some failing sorters:

@Morwenn
Copy link
Owner Author

Morwenn commented Feb 8, 2019

Apparently at least part of the issue with block_sort is due to the fact that I changed a few std::copy to std::move blindly when adapting the algorithms and making sure that it would work with move-only types, which actually introduced a few self-moves.

Specifically I just found such an issue with a call to merge_move where, when merging [first, middle, last), the remaining value of [middle, last) sometimes overrode themselves when they didn't change position. Changing the merge_move call by a buffered_inplace_merge solved this specific issue (see commit f9a0c62), and I'm pretty sure that the remaining issue in block_sort, but also in grail_sort, are similar to this one. After all these algorithms are the only two to use merge_move in the library (occasionally doing it right).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

1 participant