Why does `std.mem.sort` have the `context` field?

[allonsyeet]

TL;DR

Why does std.mem.sort take in a context structure? I’ve only used Rust, Julia, Python and OCaml and their sort implementations don’t do that. This seems like (to me, who’s not a very good programmer) a strange thing a standard library sort function to have? The other languages I know don’t have that, but I did learn that libc has it, which makes me think there’s a common use case for this that I’m unaware of. Could somebody point me in the right direction to learn why this is such a common need? Tysm!

---

Context

I was looking at std.mem.sort, and I noticed it’s signature is this:

pub fn sort( comptime T: type, items: []T, context: anytype, comptime lessThanFn: fn (@TypeOf(context), lhs: T, rhs: T) bool, ) void

I couldn’t understand why it had the context field present because I’ve not seen that before in a standard library sort function. I was advised to look at the tests and I found tests in std.sort line 371,

test "sort with context in the middle of a slice" {
    const Context = struct {
        items: []i32,

        pub fn lessThan(ctx: @This(), a: usize, b: usize) bool {
            return ctx.items[a] < ctx.items[b];
        }

        pub fn swap(ctx: @This(), a: usize, b: usize) void {
            return mem.swap(i32, &ctx.items[a], &ctx.items[b]);
        }
    };

    const i32cases = [_][]const []const i32{
        &[_][]const i32{
            &[_]i32{ 0, 1, 8, 3, 6, 5, 4, 2, 9, 7, 10, 55, 32, 39, 58, 21, 88, 43, 22, 59 },
            &[_]i32{ 50, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 21, 22, 32, 39, 43, 55, 58, 59, 88 },
        },
    };

    const ranges = [_]struct { start: usize, end: usize }{
        .{ .start = 10, .end = 20 },
        .{ .start = 1, .end = 11 },
        .{ .start = 3, .end = 7 },
    };

    inline for (context_sort_funcs) |sortFn| {
        for (i32cases) |case| {
            for (ranges) |range| {
                var buf: [20]i32 = undefined;
                const slice = buf[0..case[0].len];
                @memcpy(slice, case[0]);
                sortFn(range.start, range.end, Context{ .items = slice });
                try testing.expectEqualSlices(i32, case[1][range.start..range.end], slice[range.start..range.end]);
            }
        }
    }
}

In this specific test, the context is a type erased structure that contains data to be sorted and conforms to the interface of having a fn swap(@This(), usize, usize) void function and a fn lessThan(@This(), usize, usize) bool function, and the algorithms context_sort_funcs are functions that take in bounds and the context structure and use the interface to sort the data.

My specific question is that is this kind of pattern very common in lower level programming languages? I’ve only used a few higher level languages (Julia, Python, OCaml and Rust) so I’m completely lost as to what the common use case for this is, and why couldn’t the end user of the sort function handle this, and the sort function itself just sorts arrays of things you can compare?

[vulpesx]

it allows it to support arbitrary types, even ones that could not otherwise be compared with zigs operators.

[Wunka]

There are two different kinds of context
The context in

pub fn sort( comptime T: type, items: []T, context: anytype, comptime lessThanFn: fn (@TypeOf(context), lhs: T, rhs: T) bool, ) void

is so that you can give “context” information to your own lessThen method. you may need that or not.

In your second example the sortContext variants are used. These accepts a Context struct which have a lessthan and a swap method. Defining both and not only lessthan (as is with the other option) allows you to use sort on structures where you cannot just use std.mem.swap (I actually had a use case for this today)

[allonsyeet]

That would be the lessThanFn not the context right?

[vulpesx]

Your right that the lessThan function contributes more to supporting other types compared to the context.

The context allows you to have more data that may be relevent to the sorting, an example:

you have other slices whoes order needs to be kept in sync with the data you are sorting.

That other slice may also contribute to the sorting in addition to the main data, e.g each items gets a priority.

[abdullah-b-al]

As others have said, the point of the context is to provide control to the user of the function.

The reason why lower level languages choose this approach is because its the simplest way to provide control to the user. All you need is a pointer to user data and pointer(s) to functions. It’s an ad-hoc interface that doesn’t require special features to make work. All languages are capable of this, but higher level languages prefer different approaches.

[PinieP]

The languages you mentioned implement equivalent behaviour.

• In rust you can use sort_by to sort with a custom comparator function.
• In julia you can pass lt=sort_func to sort and sort!
• python 3 chose a different path and only allows you to sort after mapping the values to a sort key.

Since these languages have closures, they do not need a separate context parameter. The context can be bundled into the closure.

[allonsyeet]

Okay yeah I re read the two different sort functions and realized the tests I posted have a different context than the one in std.mem.sort thank you for pointing that out!

[allonsyeet]

Oh! I see, it’s like a very rudimentary way of providing the Ord typeclass and allowing the comparison function to refer to data other than the slice being sorted. It’s just a typeclass and a closure! Tysm, that sorta made things click a bit along with the other replies.

[Sze]

@allonsyeet

In this specific test, the context is a type erased structure that contains data to be sorted and conforms to the interface of having a fn swap(@This(), usize, usize) void function and a fn lessThan(@This(), usize, usize) bool function

There isn’t any type erasure going on here, I think that is a misunderstanding of type erasure.
With type erasure you have some type and you deliberately hide it by using a more general type that has less or basically zero information about what you have stored in that more general type.
So when I have a *u32 pointer and convert it to *anyopaque, then other code no longer can restore that type information because it could be any kind of pointer it is just some address, so restoring that type information is only possible by storing some other data that tells you what you have stored there.

Here everything deals with concrete types, Context is fully concrete, the context_sort_funcs are generic functions because they accept any arbitrary instance of a type and then use that instance in a ducktyping manner, which results in a compile error if that instance doesn’t have the two functions/methods you described.

@allonsyeet

My specific question is that is this kind of pattern very common in lower level programming languages?

Don’t know but I like the sortContext functions a lot because:

@allonsyeet

and why couldn’t the end user of the sort function handle this, and the sort function itself just sorts arrays of things you can compare?

…because having to (having no other choice than to) create arrays or slices before being able to start sorting sucks (in some situations)

These sortContext functions allow you to sort everything (without it having to be a classical slice element) as long as you are able to order it and swap two of them. It doesn’t impose other restrictions on how you implement the two functions.

Here is an example that demonstrates why it can be nice to be able to sort arbitrary logical groupings of things without having to first transform them into a single thing that can be put into a slice (look at the nested topics):

Best pattern for callback parametrization

There is also std.mem.sortContext which is (currently) implemented via std.sort.insertionContext: context must have methods swap and lessThan I think std.sort is a simpler interface, while std.sortContext allows you to not only define the comparison function but also how the swap function works (which is useful when the default swap function std.mem.swap doesn’t work for what you consider to be the “element” while sorting. Here is an example where I use a custom swap function to sort rows o…

Another example where sortContext is useful is if you have several parallel arrays that are related to another by their index (like typical in data oriented design), because it allows you to sort them all at the same time, this is how MultiArrayList implements sorting.

For these cases just imagine how terrible it would be to first create a slice that has all the data in AoS format, then sort it and convert it back to SoA.

I think languages fall into these categories:

1. they have already opted into terrible waste (like python using a pointer for everything, where you just sort an array of pointers which point to more pointers which point to more …), so they basically don’t care

2. they support one kind of memory layout and everything needs to use that and programmers just have to engineer solutions around that (like re-implementing your own sort functions, or adding extra steps to be able to sort things which aren’t in the expected layout)

3. the language’s typesystem is complex enough, so that it can model types where the memory layout doesn’t have to be AoS, or you can create views/projections that can group the data in a way where you can express the logical-relations of the data as a type or abstracted without having to fully materialize these relations as AoS single element slices
   (For example Odin has soa data types so the type system can treat these arrays like other normal arrays and thus sorting them should work like normally. However the sortContext also allows you to sort arbitrary groups of elements, I am not familiar enough with Odin to know whether they have an easy way to do that.)

So they either just use a worse memory layout, or they know enough to do it automatically (which can come at the cost of a either more restrictive language (taking control away from the user) or a way more complex type system).