3 ms·

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 C

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

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.