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

[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).