Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #36615 > unrolled thread

Where can I find a good implementation of an IntMap similar to the one they used to have at org.cljp.*?

Back to article view | Back to comp.lang.java.programmer

Contents

  Where can I find a good implementation of an IntMap similar to the one they used to have at org.cljp.*? latencyfighter@mail.com - 2017-05-13 20:21 -0700
    Where can I find a good implementation of an IntMap similar to the one they used to have at org.cljp.*? lewbloch@gmail.com - 2017-05-14 08:48 -0700
      Re: Where can I find a good implementation of an IntMap similar to the one they used to have at org.cljp.*? J Crawford <latencyfighter@mail.com> - 2017-05-14 10:55 -0700
        Re: Where can I find a good implementation of an IntMap similar to the one they used to have at org.cljp.*? Arne Vajhøj <arne@vajhoej.dk> - 2017-05-16 20:56 -0400
          Re: Where can I find a good implementation of an IntMap similar to the one they used to have at org.cljp.*? Arne Vajhøj <arne@vajhoej.dk> - 2017-05-17 15:35 -0400
      Re: Where can I find a good implementation of an IntMap similar to the one they used to have at org.cljp.*? v_borchert@despammed.com (Volker Borchert) - 2017-05-14 17:09 +0000

#36615 — Where can I find a good implementation of an IntMap similar to the one they used to have at org.cljp.*?

Back in the early 2000's I remember coming across a Hashtable implementation that used primitive ints as keys and any Java object as the value. I believe it was done by Jon Skeet. It was very simple, fast and used Entry objects inside a data array. I belonged to org.cljp.* or comp.lang.java.programmer. Does anyone have or know where I could find that?

Thanks!

-JC

[toc] | [next] | [standalone]

#36617

What's wrong with `HashMap<Integer, Object>`?

[toc] | [prev] | [next] | [standalone]

#36618

On Sunday, May 14, 2017 at 10:48:54 AM UTC-5, lewb...@gmail.com wrote:
> What's wrong with `HashMap<Integer, Object>`?

This is for real-time development so I need a data-structure that does not produce any garbage for the GC and it is very fast/efficient. HashMap is not for real-time development. There are many open source projects out there (Trove, GS Collections, etc.) but the IntMap I've seen from Jon Skeet was the best.

Thanks!

-JC

[toc] | [prev] | [next] | [standalone]

#36640

On 5/14/2017 1:55 PM, J Crawford wrote:
> On Sunday, May 14, 2017 at 10:48:54 AM UTC-5, lewb...@gmail.com
> wrote:
>> What's wrong with `HashMap<Integer, Object>`?
>
> This is for real-time development so I need a data-structure that
> does not produce any garbage for the GC and it is very
> fast/efficient.

My assumption would be that Map is only one out of many
disturbances. Other things like: other GC, JIT compiler running,
multi-tasking OS scheduling could also intervene. Java in general
is not that good at real time.

But you probably have that covered.

>                 HashMap is not for real-time development. There are
> many open source projects out there (Trove, GS Collections, etc.) but
> the IntMap I've seen from Jon Skeet was the best.

It does not seem to available on the internet.

Just for the fun of it I tried writing a Map implementation
with no allocation in put ever. It is not nice code. And
I have not tested it. But just in case - it is attached below.

Arne

import java.util.AbstractMap;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

// Map implementation not allocating objects in put
// not good code - very limited functionality and very old style
public class PrimitiveMap<TK,TV> implements Map<TK,TV> {
     private int maxsize;
     private Object[] keys;
     private Object[] values;
     private int[] next;
     private int scale;
     private int free;
     private int count;
     private void add(Object key, Object value, int ix) {
         keys[ix] = key;
         values[ix] = value;
         count++;
     }
     private void move(int target, int source) {
         if(source < scale) {
             keys[target] = null;
             values[target] = null;
             next[target] = 0;
         } else {
             keys[target] = keys[source];
             values[target] = values[source];
             move(source, next[source]);
         }
     }
     public void dump() {
         for(int i = 0; i < free; i++) {
             if(keys[i] != null) {
                 System.err.printf("%d : %s %s %d\n", i, 
keys[i].toString(), values[i].toString(), next[i]);
             }
         }
     }
     public PrimitiveMap(int maxsize) {
         this.maxsize = maxsize;
         keys = new Object[maxsize];
         values = new Object[maxsize];
         next = new int[maxsize];
         scale = maxsize / 2;
         free = scale;
         count = 0;
     }
     @Override
     public int size() {
         return count;
     }
     @Override
     public boolean isEmpty() {
         return (count == 0);
     }
     @Override
     public boolean containsKey(Object key) {
         return (get(key) != null);
     }
     @Override
     public boolean containsValue(Object value) {
         throw new RuntimeException("Not implemented yet");
     }
     @SuppressWarnings("unchecked")
     @Override
     public TV get(Object key) {
         if(key == null) {
             throw new RuntimeException("Key null not allowed");
         }
         int hsh = key.hashCode();
         int ix = hsh % scale;
         if(keys[ix] == null) {
             return null;
         } else {
             do {
                 if(keys[ix].equals(key)) {
                     return (TV)values[ix];
                 } else {
                     ix = next[ix];
                 }
             } while(ix >= scale);
             return null;
         }
     }
     @SuppressWarnings("unchecked")
     @Override
     public TV put(TK key, TV value) {
         if(key == null) {
             throw new RuntimeException("Key null not allowed");
         }
         int hsh = key.hashCode();
         int ix = hsh % scale;
         int oldix;
         if(keys[ix] == null) {
             add(key, value, ix);
             return null;
         } else {
             do {
                 if(keys[ix].equals(key)) {
                     Object res = values[ix];
                     values[ix] = value;
                     return (TV)res;
                 } else {
                     oldix = ix;
                     ix = next[ix];
                 }
             } while(ix >= scale);
             if(free >= maxsize) {
                 throw new RuntimeException("Maximum size exceeded");
             }
             add(key, value, free);
             next[oldix] = free;
             free++;
             return null;
         }
     }
     @SuppressWarnings("unchecked")
     @Override
     public TV remove(Object key) {
         if(key == null) {
             throw new RuntimeException("Key null not allowed");
         }
         int hsh = key.hashCode();
         int ix = hsh % scale;
         if(keys[ix] == null) {
             return null;
         } else {
             do {
                 if(keys[ix].equals(key)) {
                     Object res = values[ix];
                     move(ix, next[ix]);
                     count--;
                     while(free > scale && keys[free-1] == null) {
                         free--;
                     }
                     return (TV)res;
                 } else {
                     ix = next[ix];
                 }
             } while(ix >= scale);
             return null;
         }
     }
     @Override
     public void putAll(Map<? extends TK, ? extends TV> m) {
         Iterator<? extends Map.Entry<? extends TK, ? extends TV>> it = 
m.entrySet().iterator();
         while(it.hasNext()) {
             Map.Entry<? extends TK, ? extends TV> ent = it.next();
             put(ent.getKey(), ent.getValue());
         }
     }
     @Override
     public void clear() {
         for(int i = 0; i < maxsize; i++) {
             keys[i] = null;
             values[i] = null;
             next[i] = 0;
         }
         free = scale;
         count = 0;
     }
     @SuppressWarnings("unchecked")
     @Override
     public Set<TK> keySet() {
         Set<TK> res = new HashSet<>();
         for(int i = 0; i < free; i++) {
             if(keys[i] != null) {
                 res.add((TK)keys[i]);
             }
         }
         return res;
     }
     @SuppressWarnings("unchecked")
     @Override
     public Collection<TV> values() {
         List<TV> res = new ArrayList<>();
         for(int i = 0; i < free; i++) {
             if(keys[i] != null) {
                 res.add((TV)values[i]);
             }
         }
         return res;
     }
     @SuppressWarnings("unchecked")
     @Override
     public Set<Map.Entry<TK,TV>> entrySet() {
         Set<Map.Entry<TK,TV>> res = new HashSet<>();
         for(int i = 0; i < free; i++) {
             if(keys[i] != null) {
                 res.add(new AbstractMap.SimpleEntry<TK,TV>((TK)keys[i], 
(TV)values[i]));
             }
         }
         return res;
     }
}

[toc] | [prev] | [next] | [standalone]

#36641

On 5/16/2017 8:56 PM, Arne Vajhøj wrote:
> Just for the fun of it I tried writing a Map implementation
> with no allocation in put ever. It is not nice code. And
> I have not tested it. But just in case - it is attached below.

And below if you always want int key and can live with not
implementing Map.

Arne

package intmap;

import java.util.AbstractMap;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

// Map implementation not allocating objects in put and not requiring 
boxing of int key
// not good code - very limited functionality and very old style
public class IntMap<T> {
     private int maxsize;
     private int[] keys;
     private Object[] values;
     private int[] next;
     private int scale;
     private int free;
     private int count;
     private void add(int key, Object value, int ix) {
         keys[ix] = key;
         values[ix] = value;
         count++;
     }
     private void move(int target, int source) {
         if(source < scale) {
             keys[target] = 0;
             values[target] = null;
             next[target] = 0;
         } else {
             keys[target] = keys[source];
             values[target] = values[source];
             move(source, next[source]);
         }
     }
     public void dump() {
         for(int i = 0; i < free; i++) {
             if(keys[i] != 0) {
                 System.err.printf("%d : %d %s %d\n", i, keys[i], 
values[i].toString(), next[i]);
             }
         }
     }
     public IntMap(int maxsize) {
         this.maxsize = maxsize;
         keys = new int[maxsize];
         values = new Object[maxsize];
         next = new int[maxsize];
         scale = maxsize / 2;
         free = scale;
         count = 0;
     }
     public int size() {
         return count;
     }
     public boolean isEmpty() {
         return (count == 0);
     }
     public boolean containsKey(int key) {
         return (get(key) != null);
     }
     public boolean containsValue(Object value) {
         throw new RuntimeException("Not implemented yet");
     }
     @SuppressWarnings("unchecked")
     public T get(int key) {
         if(key == 0) {
             throw new RuntimeException("Key zero not allowed");
         }
         int ix = key % scale;
         if(keys[ix] == 0) {
             return null;
         } else {
             do {
                 if(keys[ix] == key) {
                     return (T)values[ix];
                 } else {
                     ix = next[ix];
                 }
             } while(ix >= scale);
             return null;
         }
     }
     @SuppressWarnings("unchecked")
     public T put(int key, T value) {
         if(key == 0) {
             throw new RuntimeException("Key zero not allowed");
         }
         int ix = key % scale;
         int oldix;
         if(keys[ix] == 0) {
             add(key, value, ix);
             return null;
         } else {
             do {
                 if(keys[ix] == key) {
                     Object res = values[ix];
                     values[ix] = value;
                     return (T)res;
                 } else {
                     oldix = ix;
                     ix = next[ix];
                 }
             } while(ix >= scale);
             if(free >= maxsize) {
                 throw new RuntimeException("Maximum size exceeded");
             }
             add(key, value, free);
             next[oldix] = free;
             free++;
             return null;
         }
     }
     @SuppressWarnings("unchecked")
     public T remove(int key) {
         if(key == 0l) {
             throw new RuntimeException("Key zero not allowed");
         }
         int ix = key % scale;
         if(keys[ix] == 0) {
             return null;
         } else {
             do {
                 if(keys[ix] == key) {
                     Object res = values[ix];
                     move(ix, next[ix]);
                     count--;
                     while(free > scale && keys[free-1] == 0) {
                         free--;
                     }
                     return (T)res;
                 } else {
                     ix = next[ix];
                 }
             } while(ix >= scale);
             return null;
         }
     }
     public void putAll(IntMap<? extends T> m) {
         Iterator<? extends Map.Entry<Integer, ? extends T>> it = 
m.entrySet().iterator();
         while(it.hasNext()) {
             Map.Entry<Integer, ? extends T> ent = it.next();
             put(ent.getKey(), ent.getValue());
         }
     }
     public void clear() {
         for(int i = 0; i < maxsize; i++) {
             keys[i] = 0;
             values[i] = null;
             next[i] = 0;
         }
         free = scale;
         count = 0;
     }
     public Set<Integer> keySet() {
         Set<Integer> res = new HashSet<>();
         for(int i = 0; i < free; i++) {
             if(keys[i] != 0) {
                 res.add(keys[i]);
             }
         }
         return res;
     }
     @SuppressWarnings("unchecked")
     public Collection<T> values() {
         List<T> res = new ArrayList<>();
         for(int i = 0; i < free; i++) {
             if(keys[i] != 0) {
                 res.add((T)values[i]);
             }
         }
         return res;
     }
     @SuppressWarnings("unchecked")
     public Set<Map.Entry<Integer,T>> entrySet() {
         Set<Map.Entry<Integer,T>> res = new HashSet<>();
         for(int i = 0; i < free; i++) {
             if(keys[i] != 0) {
                 res.add(new AbstractMap.SimpleEntry<Integer,T>(keys[i], 
(T)values[i]));
             }
         }
         return res;
     }
}

[toc] | [prev] | [next] | [standalone]

#36619

lewbloch@gmail.com wrote:

> What's wrong with `HashMap<Integer, Object>`?

16 bytes of overhead per entry.

-- 

"I'm a doctor, not a mechanic." Dr Leonard McCoy <mccoy@ncc1701.starfleet.fed>
"I'm a mechanic, not a doctor." Volker Borchert  <v_borchert@despammed.com>

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.java.programmer

csiph-web