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

Parametrize sorting networks on the swap function #161

Open
Morwenn opened this issue Mar 2, 2020 · 0 comments
Open

Parametrize sorting networks on the swap function #161

Morwenn opened this issue Mar 2, 2020 · 0 comments
Labels

Comments

@Morwenn
Copy link
Owner

Morwenn commented Mar 2, 2020

Papers like Engineering Faster Sorters for Small Sets of Items by Bingmann & al. and Applying Sorting Networks to Synthesize Optimized Sorting Libraries by Codish & al. highlight the need for cpp-sort to be able to parametrize sorting networks on their swapping function.

This is actually a bit tricky considering that there's already iter_swap as a customization point which depends on the iterator type and swap on the value type. Even our own swap_if optimization in the library's internals is only applied when iter_swap isn't picked first. I guess that it would be possible to hijack that by wrapping some type somewhere in a dummy template to make sure that overload resolution picks swap(sorting_network_tag<T>&, sorting_network_tag<T>&); and that this overload calls the sorting function associated to the sorting network, but that's more templates, more random overload resolution and obscure customization points. It would also only work with stateless function types associated to the sorting network type, which is limited but should be enough for a compare-and-swap function.

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