Hacker News Reader

Comment by wild_preference | Hacker News Reader

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.

View on HN

Where 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.

Hm... 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.

Specialized 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.

Yikes, 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.

> incredibly poorly thought out example on your part

But maybe you're right and I should have ignored it...

It'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.

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

Which is my point. Compilers can't help here.

I 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]

An 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.

You 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.

Now, who does that (and what languages support that anyway) and still gets the project finished?

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"?

Haskell, C++ and Rust support tiny amount of dependent type theory, enough to encode this information. I don't think any implementation would optimize given that though. But this is ok since you can implement this optimization yourself with no runtime cost and no change to the code using the datastructure. As far as full fledged dependent types go, we have agda if you're into Haskell ecosystem. I think your question is a bit badly formulated since dependent types are a new, and shiny thing so you won't find any industry-standard implementation of it. I was trying to express this problem is solvable.

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

> I think your question is a bit badly formulated since dependent types are a new, and shiny thing so you won't find any industry-standard implementation of it.

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

I don't think we're (in particular) disagreeing, you're just being weirdly defensive (in this whole thread). The part we're agreeing is: there is no such "Sufficiently optimizing compiler" yet so a HL won't be as fast as LL by default. (this is very easy to check, C always wins in compiler metrics). What I'm trying to express is: (1) this is a trade-off by getting that slight performance increase you're making code uglier/less-readable (2) with current technologies you'll get acceptable performance even if you use generics (3) theoretically there is no reason why such sufficiently smart compiler cannot exist, we know enough to express sufficient amount of information in our programs.

Yes, that is correct, you missed the point. You don't understand what generics are.

I think you are confusing "generic code" (which is a pretty generic term) with "Generics", which has a somewhat more defined meaning in programming languages.

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.

That's a terrible example. You're using two different data structures.

A hashmap is not the generic version of an array.

Can 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.

Reply on news.ycombinator.com