map data structure specializing keys to ints, redux

[Lukas Stadler]

Hi Miguel,

the NodeMap is backed by an array spanning all possible node Ids - so it’s quite efficient in terms of run time.
Why is NodeMap not working for you? Are you looking for a NodeMap that is efficient in terms of space for sparsely populated maps?
I don’t think that a normal HashMap is so bad for the sparse Node -> Object case, since Node.hashCode is hardcoded to use System.identityHashCode - which is a quite efficient operation.

- Lukas

On 18 Apr 2014, at 11:44, Miguel Garcia Gutierrez <miguel.m.garcia at oracle.com> wrote:

> 
> I'm looking for a map data structure specializing keys to ints (context below).
> 
> What are the pros and cons of:
>  (1) http://lafo.ssw.uni-linz.ac.at/javadoc/graalvm/all/com/oracle/graal/graph/NodeMap.html
>  (2) http://www.goldmansachs.com/gs-collections/javadoc/5.0.0/com/gs/collections/impl/map/mutable/primitive/IntObjectHashMap.html
>  (3) other int-to-object map implementation you'd like to bring up
> 
> Regarding (2), the documentation mentions it relies on open addressing and quadratic probing.
> 
> This question is a follow-up to another question I made:
>  http://mail.openjdk.java.net/pipermail/graal-dev/2014-March/001774.html
> 
> Background, to recap:
>  Frequently one needs to map Nodes to something, where:
>  - the lifetime of such maps is limited to a single phase [1], and
>  - no field is accessed on the keys,
>  thus Node ids (which are ints) could be used as keys rather than Nodes themselves.
> 
> 
> Miguel