There are two ways I know of: (1) throw type and memory safety out the window and use void pointers plus size/alignment like qsort(3) does; (2) require that users manually write an interface with a swap(int i, int j) function like Go before generics does. Both solutions are really bad.
In C# for example, generics are important to keep values on the stack instead of the heap, not only avoiding garbage collection but improving data locality.
That's what I am talking about. I don't know much about modern C optimizations.
What can be measureable though is function call overhead - if you write a sort function that takes a function pointer and your sort function calls that, there is a lot of work for saving the local state, preparing all the arguments for the function, etc. That work can potentially be avoided if the compiler can inline the function call into (a copy of) your sort function.
Lets say it's 4 8bit ints. It can be sequentially and directly in memory like:
stack: [0x01, 0x02, 0x03, 0x03]
stack: [0x07002412, 0x0700241A, 0x07002424, 0x070036A0]
heap (or stack, really):
0x07002412: 0x01
0x0700241A: 0x02
0x07002424: 0x03
0x070036A0: 0x04
That is what "void*" is doing. You're using a pointer instead of a value.
In C# this is what generics allow you to avoid.
// This is like my first memory layout above.
struct Foo<T> { public T MyField; }
// This is like the second layout above.
struct Foo { public object MyField; }When I do need to sort, I just use qsort from libc. It's also easy to write my own version of qsort.
I once measured qsort vs std::sort on plain ints (basically the most pessimistic case for qsort vs std::sort) and the difference was like 2x. If this becomes a bottleneck then it's worth investigating how to take advantage of additional context to speed up the sorting much more than any generic sorting algorithm could do anyway. Simple example: bucket sort. (I'm 100% confident sorting performance hasn't ever been noticeable in my career so far, but I've done simple optimizations like that once in a while for fun).
> Both solutions are really bad.
Due to what I described above, I'm actually in favour of qsort - no new code is generated, just a simple library call that takes a pointer to the comparison function. Really really easy to use.
(C probably isn't great for DB interop in any case).
Even ignoring performance, it has no support for checking the types, which in C means it can easily mess up memory badly. For example, I can call `qsort(arrayOfInts, num, sizeof(float), funcThatComparesTwoStrings)` and I'll get a really bad time, with absolutely no way for the compiler to tell me I'm doing something obviously wrong.
> I can call `qsort(arrayOfInts, num, sizeof(float), funcThatComparesTwoStrings)`
Don't do this. Do "qsort(a, n, sizeof *a, compare)"
> with absolutely no way for the compiler to tell me I'm doing something obviously wrong.
In the event that it does not work, two things are very likely true. 1) it was a really dumb mistake. 2) you will notice immediately and can fix the mistake.
The idea that everything must be caught by the compiler is narrow-minded and ultimately can't be achieved. Stop worrying about hypothetical problems that aren't problems in practice. There are enough real problems to work on.
No, you won't notice immediately. You will only notice when you run your code, because it will crash. And it might not crash right away, because the bad code is not being run, so you have a crash waiting to happen at some time in the future, which might have been avoided with a competent type system.
Users of statically typed languages have a different understanding of "immediately" than you do. If the compiler knows my code will crash, it should simply refuse to compile it until I fix it.
> The idea that everything must be caught by the compiler is narrow-minded and ultimately can't be achieved.
Ah, the famous fallacy "We can't reach 100% so let's just be content with 0%".
That's not how the world works. Static types provide not just non crash guarantees but plenty of other advantages (automatic refactorings, performance, code that's easier to read and maintain, etc...).
You have just gotten used to a crappy developer experience because you are using a dynamically typed (or very badly typed) programming language. Get out of that boiling pot and be more exigent from your programming language, there are some very good ones available today which will make you go back to your statements above in a few years and think "Yeah... that was a pretty silly thing to say, but I know better now".
How did you infer that that's not immediately?
> If the compiler knows my code will crash, it should simply refuse to compile it until I fix it.
Sure but what if it doesn't know that, then I won't complain about the next best opportunity, which is pressing F5 once and seeing the code I just typed doesn't work as intended.
> Static types provide not just non crash guarantees
How about no?
> Ah, the famous fallacy "We can't reach 100% so let's just be content with 0%".
If using a void-pointer parameter once in a blue moon for some convenience (callback function pointer), how is that 0% and not 99%? I recognize I've written too many comments, seeing as the replies are starting to get extremely poor. Ignoring the rest.
To someone that said "Even ignoring performance, it has no support for checking the types, which in C means it can easily mess up memory badly." you replied "It does not matter. Your concerns are entirely academic. Simplicity wins.". Type safety is a real concern, and lack of it has conséquences in the real world, often in the form of bugs or vulnerablities, but you seem deaf to any arguments so I don't see the point of arguing with you. Instead, I've linked you something that you might like.
> Type safety is a real concern, and lack of it has conséquences in the real world, often in the form of bugs or vulnerablities
To me type safety is first and foremost a usability feature - already a primitive type system like C's saves tons of time when changing code. But is it a great concern with regards to bugs and vulnerabilities? Type safety is static, once you've run a particular section of code, you can be relatively sure that there are no type issues on that path. (Granted that to run all code sections even once can be lots of work). That is contrary to other types of bugs which might only show up on rare occasions, and possibly require malicious intent.
In particular because std::sort is templated you can use anything callable including a lambda or function pointer as the comparator. But if you already have operator< defined for the type you don’t even need to define a comparator.
It seems like std::sort is shorter and simpler to write, safer, faster and generic across container types (including c arrays).
Other than that, the STL is generally slower compiling compared to only including plain C headers, which is also taxing on the "ease of use" department.
Has worked in C++ for ~25 years as long as `foo` is a container of items with an `operator<`. It has never required defining a separate class. It will also optimize better than qsort when qsort fails to inline.
An example of which is Smalltalk, but could also include Dart 1, Python, Elixir, CLOS/Lisp, JavaScript, etc.
Smalltalk is an interesting exhibition of a similar principle though. If you did add types to Smalltalk, you'd likely solve this containment parameterization problem the same way you do nearly everything in Smalltalk: by binding some new behavior (adding a method) to some data (a class object). You'd add a message to the MetaClass types that could create flyweight class types parameterized on the fly. And when you compiled, you'd send messages to the instance of the class itself to manufacture that synthetic on-the-fly type. Hand wave, hand wave, hand wave.
The "let's see where naval gazing on a unifying principle goes?" that is employed in Zig is to use the same language itself to recurse on itself when defining itself, types included.
What happens in more traditional/mainstream/Algol derived languages, is that each part of the system gets a sort of sub department of the language. You have a set of keywords/syntax for expressing run time behavior. And then someone says, but how do actually bring data to life--a sort of "Creatio ex nihilo" problem--and the answer is we need a new department in the language, so we get keywords/syntax for constructors. When behavior/construction needs to be parameterized across compilation paths, we get another set of keywords/syntax. And another for type definition. And yet another for scope management. And then again with meta things. And maybe a preprocessor.
I do think there's a trick to finding a sweet spot in these "turtles all the way down" systems. In Smalltalk, I was happy with how the "don't know what's going on? just follow the message sends", but at the same time still providing enough structure/composition to have to be reflecting/introspecting all the time. Forth is event simpler, but I found I had to constant recompile things in my head to resolve. I'm relatively new on the Elixir curve, and am beginning to worry this happens with macros there. Figuring out how Plug works really messes with my brain. I haven't done enough with Zig to know where it's @comptime ends up in this balance.