5 ms·

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 els

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]

jstimpfle 8y ago
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.
- gnulinux 8y ago
  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.
  - jstimpfle 8y ago
    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"?
    - gnulinux 8y ago
      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.
      - jstimpfle 8y ago
        > 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 http://wiki.c2.com/?SufficientlySmartCompiler
        gnulinux 8y ago
        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.

jstimpfle 8y ago

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.

gnulinux 8y ago
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.
- jstimpfle 8y ago
  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"?
  - gnulinux 8y ago
    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.
    - jstimpfle 8y ago
      > 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 http://wiki.c2.com/?SufficientlySmartCompiler
      - gnulinux 8y ago
        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.