> You might be wondering whether there is a runtime cost when you’re using generic type parameters. The good news is that Rust implements generics in such a way that your code doesn’t run any slower using generic types than it would with concrete types.
> Rust accomplishes this by performing monomorphization of the code that is using generics at compile time. Monomorphization is the process of turning generic code into specific code by filling in the concrete types that are used when compiled.
Let's assume for example you have a generic hash map where you just plug the type in, which must be hashable. Now if you plug in an integer type, monomorphization or whatever fancy compilation techniques will make that faster. But the best way to map an integer range is still a plain array.
To put it in simple terms, compilers can make shit run faster, but they can't make it not shit.
Furthermore template specialization is usually a bad idea. Think how we just LOVE std::vector<bool> (/s). Also std::unordered_map<int> is not specialized to an array implementation. Because you can't tell from the type whether it will map a contiguous range.
I've done my homework. Your turn.
But maybe you're right and I should have ignored it...
Eh, only if you know in advance that:
1. Your integer keys can only ever come from a contiguous range of values
2. Once populated, your map will have values for at least 25-50% of the integers in that range.
If either of these assumptions are false, using an array will force you to allocate way more memory than you need to hold the elements in your map, and the resulting map will be sparse, and therefore cache-unfriendly.
Arrays are not better than hash maps that use integer keys in the general case.
[update: I realized that I mistyped my conclusion sentence, and accidentally wrote the opposite of what I meant. Now updated]
And that is my point. I'm saying Sufficiently Smart Compilers do not exist.
Could you show a real world and readable example of this, using a language and compiler that actually exist?
Also, is it really better specifying all the information to possibly help the compiler come to the conclusion that it should choose an array, than simply typing "Array"?
> Also, is it really better specifying all the information to possibly help the compiler come to the conclusion that it should choose an array, than simply typing "Array"?
Obviously right? The end result (target code) is the same but now you have two advantages (1) your compiler will check if your assumptions are right i.e. your keys are dense where you think they're dense and if not you'll get a type error in compile time so that you're not wasting space at runtime had you were using Array<int> (2) now your code doesn't have specialized data structures (hashmap vs array for the same logic), it's generic, so it's more readable.
That's just another way of saying that my rebuttal was spot-on. I don't even need to ask if you have any code to show, because I know you haven't. Seriously consider http://wiki.c2.com/?SufficientlySmartCompiler
We could agree that the latter can be implemented relatively efficiently (given a few concrete examples to clarify what that means). But that does not mean that their use, or more generally, the use of generic code, is always the best and most efficient to do. It is not, by far.
A hashmap is not the generic version of an array.
Provided a hash function for the key type exists, the hash map is one valid implementation for a generic map from keys to values. An array is a more efficient map from keys to values if the key type is an integral type and the actual keys at runtime are contiguous. It's also efficient if the keys are only nearly contiguous, and we have a "N/A" sentinel in the value type.
Plus, I'm not sure what optimizing =<< and concatMap has to do regarding optimizing generics vs concrete behavior.