Feature/radix sort - Githubissues

IntelPython / dpctl

Python SYCL bindings and SYCL-based Python Array API library

https://intelpython.github.io/dpctl/

Apache License 2.0

102 stars 30 forks source link

Feature/radix sort #1867

Closed oleksandr-pavlyk closed 2 weeks ago

oleksandr-pavlyk commented 1 month ago

This PR implements radix sort, and exposes it via new kind keyword of dpt.sort and dpt.argsort functions. Supported values of kind keyword are "stable", "radixsort", and "mergesort", with the default value being None (same as "stable"). The "stable" kind uses radix sort for boolean and short integral types,

[x] Have you provided a meaningful PR description?
[x] Have you added a test, reproducer or referred to an issue with a reproducer?
[x] Have you tested your changes locally for CPU and GPU devices?
[x] Have you made sure that new changes do not introduce compiler warnings?
[x] Have you checked performance impact of proposed changes?
[x] Have you added documentation for your changes, if necessary?
[x] Have you added your changes to the changelog?
[ ] If this PR is a work in progress, are you opening the PR as a draft?

github-actions[bot] commented 1 month ago

Deleted rendered PR docs from intelpython.github.com/dpctl, latest should be updated shortly. :crossed_fingers:

github-actions[bot] commented 1 month ago

Array API standard conformance tests for dpctl=0.19.0dev0=py310hdf72452_145 ran successfully. Passed: 894 Failed: 1 Skipped: 119

coveralls commented 1 month ago

coverage: 87.705% (+0.02%) from 87.686% when pulling 6637ddfc33291c26ceb536d8adc2f3454da3666a on feature/radix-sort into 778254488d3f616ccf4164b8bbee31d8274a7c0d on master.

oleksandr-pavlyk commented 1 month ago

Build with DPCTL_TARGET_CUDA=ON succeeds, test suite run on RTX 3050 passed.

github-actions[bot] commented 1 month ago

Array API standard conformance tests for dpctl=0.19.0dev0=py310hdf72452_149 ran successfully. Passed: 894 Failed: 1 Skipped: 119

github-actions[bot] commented 1 month ago

Array API standard conformance tests for dpctl=0.19.0dev0=py310hdf72452_158 ran successfully. Passed: 894 Failed: 1 Skipped: 119

ndgrigorian commented 1 month ago

https://github.com/IntelPython/dpctl/blob/3c05c1bdaa74c92171bbcf0cc0750370120fee47/dpctl/tensor/libtensor/include/kernels/sorting/merge_sort.hpp#L809

This line and the initial sorted_block_size value seem to be unused.

static constexpr size_t determine_automatically = 0;
size_t sorted_block_size =
    (sort_nelems >= 512) ? 512 : determine_automatically;

True or not, in merge_sort_detail::sort_over_work_group_contig_impl the sorted_block_size is set to the same value with no check against the current value of sorted_block_size. So these lines can seemingly be removed entirely.

github-actions[bot] commented 4 weeks ago

Array API standard conformance tests for dpctl=0.19.0dev0=py310hdf72452_174 ran successfully. Passed: 894 Failed: 1 Skipped: 119

ndgrigorian commented 3 weeks ago

Nit: renaming of sort.cpp/sort.hpp and argsort.cpp/argsort.hpp to merge_sort and merge_argsort may be good for clarity.

github-actions[bot] commented 3 weeks ago

Array API standard conformance tests for dpctl=0.19.0dev0=py310hdf72452_188 ran successfully. Passed: 894 Failed: 1 Skipped: 119

oleksandr-pavlyk commented 3 weeks ago

@ndgrigorian I have pushed changes to address all the issues highlighted in review.

github-actions[bot] commented 3 weeks ago

Array API standard conformance tests for dpctl=0.19.0dev0=py310hdf72452_189 ran successfully. Passed: 895 Failed: 0 Skipped: 119

github-actions[bot] commented 2 weeks ago

Array API standard conformance tests for dpctl=0.19.0dev0=py310hdf72452_193 ran successfully. Passed: 895 Failed: 0 Skipped: 119

github-actions[bot] commented 2 weeks ago

Array API standard conformance tests for dpctl=0.19.0dev0=py310hdf72452_194 ran successfully. Passed: 894 Failed: 1 Skipped: 119

oleksandr-pavlyk commented 2 weeks ago

@antonwolfy Thank you for the suggestion. I am going to act on it in a separate PR