sort with custom `cmp_fn`

[rain mantle]

In Go, I can easily sort a slice with something like:

sort.Slice(my_slice, func(i, j int) bool {
    return my_slice[i][2] < my_slice[j][2]
})

The portion func(i, j int) bool { return my_slice[i][2] < my_slice[j][2] } is an anonymous function (lambda) that is used to determine sort order. Therefore, that quick one-liner (3-liner for readibility) will sort based on the value of index 2. As a result, if my_slice starts as:
[ [1, 2, 1], [2, 3, 9], [3, 4, 5] ]
then it will sort to:
[ [1, 2, 1], [3, 4, 5], [2, 3, 9] ]

Looking at the doc page for algorithm.sort, it appears to take a cmp_fn arg (like the above anonymous function). Does anybody have sample code I can peek at for how to actually implement? ...tiny brain is confused. 😊

Derp. The cmp_fn is for partition. For some reason, I thought it was sort too. This is what I get for trying to multi-task. #bonk-self

But I guess my Q remains:
Has anybody designed a clean method for custom sort functions?

from testing import assert_equal

fn main() raises:
    var my_list = List[List[Int]](
        List(1, 2, 9),
        List(7, 8, 1),
        List(4, 5, 6),
    )

    # TODO: sort my_list on the basis of each sub-list's index 2

    var want = List[List[Int]](
        List(7, 8, 1), # 1 is smallest
        List(4, 5, 6), # 6 is mid
        List(1, 2, 9), # 9 is largest
    )

    for i in range(len(my_list)):
        for j in range(len(my_list[i])):
            print("i:", i, "& j:", j)
            assert_equal(
                my_list[i][j],
                want[i][j],
            )

[cobalt arrow]

i did something here.

https://joyofmojo.com/generic_quicksort/

As i couldnt find anything in Mojo itself i ended up implementing quicksort myself before i realized i dont actually need sort in my project 😄

[rain mantle]

Awesome! Ty. ❤️

At first MojoCON, I'm gonna owe a lot of people a free coffee....... ☕

[cobalt arrow]

check carefully, everything on this website is just trying things and probably buggy.

[rain mantle]

yep, dumping into a file rn. ...but might have to mess with it tomorrow. I just noticed the time and need to be up early. 🙂

[faint fern]

I did multiple sorting algorithms here: https://github.com/mzaks/mojo-sort but stopped maintaining it for lack of time. If you are interested I am gladly accepting PRs 😄

[rain mantle]

Awesome! I'll look at it later today when I have some free time. ❤️

[rain mantle]

@faint fern , I'm derping hard here. I did some edits that were obvious (s/let /var / and the like), but I'm stumbling on how to adjust the function signature. If you have free time to do a moment of hand-holding so I can work through this one signature, then I think I can help with the file-by-file update to current Mojo syntax.

https://github.com/dimitrilw/mojo-sort/blob/quick_sort/quick_sort/sort.mojo

I should have added the list of changes I made:

order changes were made is bottom-to-top -- that's just screenshot of the branch's commit history

and I will rebase into single commit with more clear notes before PR... I just do sloppy one-liners when in "just make it work" mode 😄

[faint fern]

Hey @rain mantle I just pushed an update, there are still a few issues like multi key sort seems to be buggy, and radix sort seems to crash, which I think is rather a compiler bug, but I need more investigation. Otherwise insertion sort, selection sort, quick sort, count sort, radix sort 11, radix sort 13 and radix sort 16 seem to work fine.

There is also a fast binary search implementation in the repo based on https://en.algorithmica.org/hpc/data-structures/binary-search/ which seems to perform 1.7 to 2.4 times faster than regular binary search on m1

[rain mantle]

@faint fern , you're awesome. ❤️

I really need to learn about the SIMD data type. Honestly, I've always seen SIMD stuff as magical. Time for me to peek behind the curtain.

Re the faster binary search on m1:
First, I'm assuming "m1" = Apple Silicon M1 chipset. If that assumption is wrong, then everything following is garbage. 😄

Have you bench'ed the two searches on other hardware? I'd help, but I'm on M1 Max, not Intel/M2/AMD/etc.

If the performance is substantially better for different hardware, then I wonder if we would benefit from a wrapper binary-search which has a sys check for hardware type before using a given optimized binary search algo. What do you think?

And that "we" in the phrase "we would benefit" wasn't to steal your glory. It was more a "we, the Mojo users that depend on the awesome work of peeps like you." 😊

Last:
I'm reading all the diffs. Just reviewing your code changes is really helping me better understand Mojo.

No joke: I find that after doing basics in a new language (hello world, a sudoku solver, whatever), then I learn best by refactoring existing code and/or reviewing the refactors that others have made. So this is helpful for me in far more ways than "yay, free search algos!" Ty! :bunhop:

hrm... really miss my various "bunny" emoji. 😐

[faint fern]

I can do a benchmark run on intel i7 as well, will check if I can find time tomorrow. But generally it seems to be on par with the article I linked to:

As typical for predication, this trick is very fragile to compiler optimizations — depending on the compiler and how the function is invoked, it may still leave a branch or generate suboptimal code. It works fine on Clang 10, yielding a 2.5-3x improvement on small arrays: