Background
Maps are used ubiquitously in almost all Java applications. There are several built-in implementations of the Map interface tailored for different purposes. All these Map implementations rely on calculating a hash value for the key, and using that hash value, we are able to put or get objects from a backing array. But sometimes we know more about the keys than that they are just Objects. In this post I will show how you can take advantage of that fact to write super-fast and super-efficient Map implementations. The implementation devised here is really nothing more than an offsetted array decorated with the Map interface methods. Since it does not have to deal with hashing, rehashing and hash collision, it is unsurprising that it is so fast. Its potential memory efficiency is however, something to elaborate on.Performance
When comparing one of the Map implementation depicted in this post (namely the IntArrayMap) we will see that it is substantially more memory efficient than any other of the built-in Map implementation.HashMap 5470 MB 54 bytes per entry TreeMap 5599 MB 55 bytes per entry LinkedHashMap 6271 MB 62 bytes per entry ConcurrentHashMap 5471 MB 54 bytes per entry IntArrayMap 400 MB 4 bytes per entry
(Bytes per entry is excluding size of value object itself.)
Applying the same comparative test but for get() method performance, we will also be able to conclude that the IntArrayMap is much faster than the other Maps.
HashMap 44864 ms, 111 MTPS TreeMap 364277 ms, 13 MTPS LinkedHashMap 74616 ms, 67 MTPS ConcurrentHashMap 62002 ms, 80 MTPS IntArrayMap(*) 29635 ms, 168 MTPS IntArrayMap(**) 9520 ms, 525 MTPS
All tests are made using a JIT warmup of 5 000 000 000 iterations and then an additional 5 000 000 000 iterations for actual testing.
So the IntArrayMap is potentially ten times more memory efficient and more than four times quicker than any other built-in Map.
IntArrayMap(*) using the get(Object) method.
IntArrayMap(**) using the get(int) method.
Restrictions
In this post, the keys in the Map implementations must be an Object that extends Number, for example Integer, Long or Byte. The Object must not be able to hold any decimals (excluding the classes Double, Float, BigInteger and BigDecimal). Furthermore the key space must be known in advance. This might first appear as an unacceptable restriction and I agree that this certainly is the case for many applications. However, there are, more often than one might think, times when we know the key space in advance. For example, when dealing with Enums or other static mappings or smaller dynamic maps. A final restriction in the solutions provided in this post is that the key set must be within the range of Integer.Overall Solution
Because the key space is know, the solutions can rely on direct mapping of the key onto an array that holds the values. So, when we create a Map, we also provide the minBound and maxBound index we want to use. If we, for example, create a Map with key space (10-14) we will create an array with 5 elements (maxBound-minBound+1) and when we get() from that map, we will take the key, subtract it with 10 (the minBound) and then get the value in that array position. The solution is related to the way EnumMap works.Benefits
- Much more memory efficient because the key is not stored in the Map. It is instead derived implicitly from the index.
- Deterministic behavior since we do not have to re-hash when the Map is too small and needs to be grown.
- Faster put() and get() operations because no hash code needs to be computed.
- Reduced object creation rate (no boxing/un-boxing) because the put() and get() methods can work directly with primitive classes (e.g. int instead of Integer)
Drawbacks
- Static key space that must be decided upon before map creation.
- Keys must extend Number.
- Less memory efficient for sparse maps (i.e. maps with few entries in the key space).
- Key space must be within Integer range.
- The Map implementations does not support null values.
Base Number Array Map
This is how the overall abstract base class NumberArrayMap looks like (yes, I know it it a big class. There are many things a Map has to do):public abstract class NumberArrayMap<K extends Number, V> extends AbstractMap<K, V> implements Map<K, V>, Serializable {
private static final long serialVersionUID = -2304239764179123L;
private int minBound;
private int maxBound;
//
private transient int size;
private transient int modCount;
private transient int capacity;
private transient V[] values;
private transient Set<Map.Entry<K, V>> entrySet;
protected NumberArrayMap(int minBound, int maxBound) {
if (minBound > maxBound) {
throw new IllegalArgumentException("Error: minBound (" + minBound + ") must not be greater than maxBound (" + maxBound + ")");
}
this.minBound = minBound;
this.maxBound = maxBound;
init();
}
private void init() {
initCapacity();
clear();
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean containsKey(Object key) {
if (key instanceof Number) {
return containsKey(((Number) key).intValue());
}
return false;
}
public boolean containsKey(int key) {
return isInRange(key) && values[index(key)] != null;
}
@Override
public boolean containsValue(Object value) {
for (final V v : values) {
if (v != null && v.equals(value)) {
return true;
}
}
return false;
}
@Override
public V get(Object key) {
if ((key instanceof Number)) {
return get(((Number) key).intValue());
}
return null;
}
public V get(int key) {
if (isInRange(key)) {
return values[index(key)];
}
return null;
}
@Override
public V put(K key, V value) {
return put(key.intValue(), value);
}
public V put(int key, V value) {
assertInRange(key);
Objects.requireNonNull(value, "This Map does not support null values");
final V oldValue = get(key);
if (oldValue == null) {
// A new value, increment size
size++;
}
values[index(key)] = value;
modCount++;
return oldValue;
}
@Override
public V remove(Object key) {
if (key instanceof Number) {
return remove(((Number) key).intValue());
}
return null;
}
public V remove(int key) {
final V oldValue = get(key);
if (oldValue != null) {
// An existing value, decrement size
size--;
}
values[index(key)] = null;
modCount++;
return oldValue;
}
@Override
public void putAll(Map<? extends K, ? extends V> m) {
for (final Entry<? extends K, ? extends V> e : m.entrySet()) {
put(e.getKey(), e.getValue());
}
}
@Override
public void clear() {
@SuppressWarnings("unchecked")
final V[] newValues = (V[]) new Object[capacity];
this.values = newValues;
size = 0;
modCount++;
}
@Override
public Set<Entry<K, V>> entrySet() {
Set<Entry<K, V>> es;
return (es = entrySet) == null ? (entrySet = new NumberArrayMap<K, V>.EntrySet()) : es;
}
final class EntrySet extends AbstractSet<Map.Entry<K, V>> {
@Override
public final int size() {
return size;
}
@Override
public final void clear() {
NumberArrayMap.this.clear();
}
@Override
public final Iterator<Map.Entry<K, V>> iterator() {
return new NumberArrayMap<K, V>.EntryIterator();
}
@Override
public final boolean contains(Object o) {
if (!(o instanceof Map.Entry)) {
return false;
}
final Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
final Object key = e.getKey();
final V valueCandidate = get(key);
return valueCandidate != null && valueCandidate.equals(e.getValue());
}
@Override
public final boolean remove(Object o) {
if (o instanceof Map.Entry) {
final Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
final Object key = e.getKey();
final V valueCandidate = get(key);
if (valueCandidate != null && valueCandidate.equals(e.getValue())) {
return NumberArrayMap.this.remove(key) != null;
}
}
return false;
}
@Override
public final void forEach(Consumer<? super Map.Entry<K, V>> action) {
Objects.requireNonNull(action);
if (size > 0) {
int mc = modCount;
for (int i = minBound; i <= maxBound; ++i) {
final V value = get(i);
if (value != null) {
action.accept(makeEntry(makeKeyFromInt(i), value));
}
if (modCount != mc) {
throw new ConcurrentModificationException();
}
}
}
}
}
private abstract class BucketIterator<N> implements Iterator<N> {
private Entry<K, V> next;
private Entry<K, V> current;
private int expectedModCount;
private int currentIndex;
public BucketIterator() {
expectedModCount = modCount;
currentIndex = 0;
if (size > 0) {
// advance to first entry
forwardToNext(minBound);
}
}
@Override
public final boolean hasNext() {
return next != null;
}
public final Entry<K, V> nextEntry() {
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
if (next == null) {
throw new NoSuchElementException();
}
current = next;
forwardToNext(currentIndex + 1);
return current;
}
@Override
public final void remove() {
final Entry<K, V> p = current;
if (p == null) {
throw new IllegalStateException();
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
current = null;
final K key = p.getKey();
NumberArrayMap.this.remove(key);
expectedModCount = modCount;
}
private void forwardToNext(int start) {
if (start <= maxBound) {
for (int i = start; i <= maxBound; ++i) {
final V value = get(i);
if (value != null) {
currentIndex = i;
next = makeEntry(makeKeyFromInt(i), value);
return;
}
}
}
// We have reached the end...
next = null;
}
}
final class KeyIterator extends BucketIterator<K> {
@Override
public final K next() {
return nextEntry().getKey();
}
}
final class ValueIterator extends BucketIterator<V> {
@Override
public final V next() {
return nextEntry().getValue();
}
}
final class EntryIterator extends BucketIterator<Map.Entry<K, V>> {
@Override
public final Map.Entry<K, V> next() {
return nextEntry();
}
}
protected abstract K makeKeyFromInt(int k);
private Entry<K, V> makeEntry(K key, V value) {
return new AbstractMap.SimpleImmutableEntry<>(key, value);
}
private int index(int key) {
return key - minBound;
}
private boolean isInRange(int key) {
return (key >= minBound && key <= maxBound);
}
private void assertInRange(int key) {
if (!isInRange(key)) {
throw new ArrayIndexOutOfBoundsException("Key " + key + " out of range. Key shoud be >= " + minBound + " and <= " + maxBound);
}
}
private void initCapacity() {
this.capacity = maxBound - minBound + 1;
}
private void writeObject(java.io.ObjectOutputStream s) throws IOException {
s.defaultWriteObject();
s.writeInt(minBound);
s.writeInt(maxBound);
s.writeInt(size);
for (final Entry<K, V> e : entrySet()) {
final V value = e.getValue();
if (value != null) {
s.writeObject(e.getKey());
s.writeObject(e.getValue());
}
}
}
private void readObject(java.io.ObjectInputStream s) throws IOException, ClassNotFoundException {
s.defaultReadObject();
minBound = s.readInt();
maxBound = s.readInt();
init();
final int noItems = s.readInt();
if (noItems < 0) {
throw new InvalidObjectException("Illegal noItems count: " + noItems);
}
if (noItems > 0) {
// Read the keys and values, and put the mappings in the NumberMap
for (int i = 0; i < noItems; i++) {
@SuppressWarnings("unchecked")
final K key = (K) s.readObject();
@SuppressWarnings("unchecked")
final V value = (V) s.readObject();
put(key, value);
}
}
}
@SuppressWarnings("unchecked")
@Override
public Object clone() throws CloneNotSupportedException {
NumberArrayMap<K, V> result;
try {
result = (NumberArrayMap<K, V>) super.clone();
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
result.init();
result.putAll(this);
return result;
}
}
All concrete implementing classes that inherit from this class must implement the K makeKeyFromInt(int k) method in order to be able to reproduce a key for any given index. This is due to the reason that we do not store the keys as the built-in Map implementations do. If, for example, the key type K is Byte, then we need to cast k to byte like this: return (byte)k; We will see how that works in the next chapter.
It is worth noticing that the normal contains(), get(), remove() and put() methods all have corresponding methods that works directly with int as key. This is important form a performance perspective because that way, we can avoid unnecessary boxing/un-boxing of keys.
By letting our class inherit from AbstractMap we get a number of methods for free, including the hashCode(), equals() and toString() methods. We also elect to override some of the AbstractMap methods for performance reasons.
Sub Classes
Now that the abstract NumberArrayMap class is implemented, it is very easy to create concrete Map implementations for different Number classes such as Integer and Long. Here is a list of the ones I have made:public class ByteArrayMap<V> extends NumberArrayMap<Byte, V> {
private static final long serialVersionUID = -2304239764179124L;
public ByteArrayMap() {
this(Byte.MIN_VALUE, Byte.MAX_VALUE);
}
public ByteArrayMap(byte minBound, byte maxBound) {
super(minBound, maxBound);
}
@Override
protected Byte makeKeyFromInt(int k) {
return (byte) k;
}
}
public class ShortArrayMap<V> extends NumberArrayMap<Short, V> {
private static final long serialVersionUID = -2304239764179125L;
public ShortArrayMap(short minBound, short maxBound) {
super(minBound, maxBound);
}
@Override
protected Short makeKeyFromInt(int k) {
return (short)k;
}
}
public class IntArrayMap<V> extends NumberArrayMap<Integer, V> {
private static final long serialVersionUID = -2304239764179126L;
public IntArrayMap(int minBound, int maxBound) {
super(minBound, maxBound);
}
@Override
protected Integer makeKeyFromInt(int k) {
return k;
}
}
public class LongArrayMap<V> extends NumberArrayMap<Long, V> {
private static final long serialVersionUID = -2304239764179127L;
public LongArrayMap(int minBound, int maxBound) {
super(minBound, maxBound);
}
@Override
protected Long makeKeyFromInt(int k) {
return (long) k;
}
}
// This class will erroneously map Numbers with equal integers (e.g. 1.2 and 1.3) to the same key
// The same goes for Double and Float, so use only integer Number implementations
@Depricated
public class BigDecimalArrayMap<V> extends NumberArrayMap<BigDecimal, V> {
private static final long serialVersionUID = -2304239764179128L;
public BigDecimalArrayMap(int minBound, int maxBound) {
super(minBound, maxBound);
}
@Override
protected BigDecimal makeKeyFromInt(int k) {
return new BigDecimal(k);
}
}
Working with Enums
Often, Enums comes with additional properties of some kind. Consider the following Enum class:public enum SomeEnum
ADAM(0, 4), BERT(1, 42), CHARLIE(2, 134), SOME_DUDE(10, 13);
private SomeEnum(int value, int luckyNumber) {
this.value = value;
this.luckyNumber = luckyNumber;
}
private final int value;
private final int luckyNumber;
public int getValue() {
return value;
}
public int getLuckyNumber() {
return luckyNumber;
}
}
By implementing a Map support class, we can very easily implement lookup methods (or "finders" as they sometimes are called). Here is the support class:
public class IntEnumArrayMap<E extends Enum<?>> extends IntArrayMap<E> {
private static final long serialVersionUID = -2304239764179128L;
public static <E extends Enum<?>> IntEnumArrayMap<E> fromEnums(E[] enums, ToIntFunction<E> function) {
final int min = Stream.of(enums).mapToInt(function).min().getAsInt();
final int max = Stream.of(enums).mapToInt(function).max().getAsInt();
final IntEnumArrayMap<E> result = new IntEnumArrayMap<>(min, max);
Stream.of(enums).forEach((e) -> result.put(function.applyAsInt(e), e));
return result;
}
public IntEnumArrayMap(int minBound, int maxBound) {
super(minBound, maxBound);
}
}
Now we can implement our finders like this:
public enum SomeEnum {
ADAM(0, 4), BERT(1, 42), CHARLIE(2, 134), SOME_DUDE(10, 13);
private SomeEnum(int value, int luckyNumber) {
this.value = value;
this.luckyNumber = luckyNumber;
}
private final int value;
private final int luckyNumber;
private final static IntEnumArrayMap<SomeEnum> valueMap =
IntEnumArrayMap.fromEnums(values(), SomeEnum::getValue);
private final static IntEnumArrayMap<SomeEnum> luckyNumberMap =
IntEnumArrayMap.fromEnums(values(), SomeEnum::getLuckyNumber);
public static SomeEnum findByValue(int value) {
return valueMap.get(value);
}
public static SomeEnum findByLuckyNumber(int value) {
return luckyNumberMap.get(value);
}
public int getValue() {
return value;
}
public int getLuckyNumber() {
return luckyNumber;
}
}
Very convenient and efficient! We know the key set of the Map we are creating so the NumberArrayMap seams like a perfect fit. Note how nice we just provide the method we want to use for mapping (e.g. SomeEnum::getValue) using Java 8's new function interface.
Future work
The implementation above relies on the inherited basic Spliterator from AbstractMap. It would be advantages to write a better Spliterator that can parallelize the entrySet(). Any one up to the challenge?Perhaps it would be possible to create other type of Map implementations that can handle other types of key sets (i.e other than Number) that can be mapped to int. Enum is one candidate (using the ordinal() as key) but there is already an EnumMap.
Grab the source code using "git clone https://github.com/minborg/javapot.git" and expand the code and also see how I made the performance tests.
Concusion
If you know your key space, you can create much more efficient Map implementations than the built-in Java ones. Enums are a perfect place where these Map implementations can live. Static maps and small maps that are created dynamically are also a perfect match.Let's Map the World!
interesting post, thanks
ReplyDelete