4 ms·
They're referring to monomorphization. Rust, for example: > You might be wondering whether there is a runtime cost when you’re using generic type parameters. T
by wild_preference 8y ago
They're referring to monomorphization. Rust, for example:
> 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.
- jstimpfle 8y agoWhere do you get that monomorphization reference from? 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.
- tathougies 8y agoHm... this seems like an incredibly poorly thought out example on your part. We've had C++ template specialization for decades. It is trivial to implement a map that uses hashes for non-integer types and an array for integer ones. This is 2018 after all.
- deleted 8y ago[deleted]
- jstimpfle 8y agoSpecialized code is... not generic code, right? 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.
- spenczar5 8y agoYikes, I have no dog in this fight, but the level of sarcasm and meanness in your post ("Your turn.") just seems over the top for this argument. You'd be more convincing if you were more level, at least for me.
- jstimpfle 8y ago> incredibly poorly thought out example on your part But maybe you're right and I should have ignored it...
- tathougies 8y agoIt's absolutely generic. The code that uses the map would be indifferent to the type of key. The code that implements it is obviously different, because they are two separate implementations. It seems unlikely that you could have automatic specialized implementations without substantial improvements in AI.
- alexhutcheson 8y ago> But the best way to map an integer range is still a plain array. 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.
- deleted 8y ago[deleted]
- jstimpfle 8y agoWhich is my point. Compilers can't help here.
- alexhutcheson 8y agoI don’t understand. In every language I’m familiar with, the hash map uses a hash function that’s appropriate for integers by default for integer keys. What else do you need the compiler to do for you? [update: I realized that I mistyped my conclusion sentence, and accidentally wrote the opposite of what I meant. Now updated]
- jstimpfle 8y agoAn Array<T> is so much faster than a Hashmap<int, T>, it's not even a competition. For contiguous integer key sequences, that is. Especially if you are iterating in order. The compiler does not know that you will expect a contiguous key sequence, so it cannot do the work of specializing from a generic container to an Array<T> for you. And that is my point. I'm saying Sufficiently Smart Compilers do not exist.
- gnulinux 8y agoYou can solve this problem using dependent types and encoding that information to your types (keys of the hashmap will be "dense") so that "Sufficiently Smart Compiler" will have enough information to optimize.
- vmchale 8y agoThat's a terrible example. You're using two different data structures. A hashmap is not the generic version of an array.
- jstimpfle 8y agoCan you clarify what's "terrible" about it? 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.