5 ms·

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

> 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 ago
Which is my point. Compilers can't help here.
- alexhutcheson 8y ago
  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
- vmchale 8y ago
  Yes, that is correct, you missed the point. You don't understand what generics are.
  - deleted 8y ago
    [deleted]
  - jstimpfle 8y ago
    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.

deleted 8y ago

[deleted]

jstimpfle 8y ago

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

alexhutcheson 8y ago
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
vmchale 8y ago
Yes, that is correct, you missed the point. You don't understand what generics are.
- deleted 8y ago
  [deleted]
- jstimpfle 8y ago
  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.