5
\$\begingroup\$

After working on Van Emde Boas tree -based map in Java, I came up with this code. I managed to fix the bugs and improve the performance by using internally primitive integers instead of wrapped java.lang.Integers:

VanEmdeBoasTreeMap.java

package net.coderodde.util;

import java.util.Collection;
import java.util.Collections;
import java.util.ConcurrentModificationException;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.Random;
import java.util.Set;
import java.util.TreeMap;

/**
 * This class implements a van Emde Boas tree -based map that maps integer keys
 * to arbitrary satellite data.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.61 (Mar 16, 2017)
 * 
 * @param <E> the type of the satellite data.
 */
public class VanEmdeBoasTreeMap<E> implements Map<Integer, E> {

    /**
     * Holds the minimum universe size.
     */
    private static final int MINIMUM_UNIVERSE_SIZE = 2;

    /**
     * Used to denote the absence of an element.
     */
    public static final int NIL = -1;

    /**
     * This static inner class implements recursively the entire van Emde Boas-
     * tree.
     * 
     * @param <E> The type of the satellite data.
     */
    private static final class VEBTree<E> {

        /**
         * The universe size of this vEB-tree.
         */
        private final int universeSize;

        /**
         * The mask used to compute the low index.
         */
        private final int lowMask;

        /**
         * The shift length for computing the high index.
         */
        private final int highShift;

        /**
         * The minimum integer key in this tree.
         */
        private int min;

        /**
         * The maximum integer key in this tree.
         */
        private int max;

        /**
         * The summary vEB-tree.
         */
        private final VEBTree<E> summary;

        /**
         * The children vEB-trees of this tree.
         */
        private final VEBTree<E>[] cluster;

        VEBTree(int universeSize) {
            this.universeSize = universeSize;

            int universeSizeLowerSquare = lowerSquare(universeSize);

            this.lowMask = universeSizeLowerSquare - 1;
            this.highShift = Integer.numberOfTrailingZeros(
                                     universeSizeLowerSquare);

            // Set to "null" min and max:
            this.min = NIL;
            this.max = NIL;

            if (universeSize != MINIMUM_UNIVERSE_SIZE) {
                int upperUniverseSizeSquare = upperSquare(universeSize);
                int lowerUniverseSizeSquare = lowerSquare(universeSize);
                this.summary = new VEBTree<>(upperUniverseSizeSquare);
                this.cluster = new VEBTree[upperUniverseSizeSquare];

                for (int i = 0; i != upperUniverseSizeSquare; ++i) {
                    this.cluster[i] = new VEBTree<>(lowerUniverseSizeSquare);
                }
            } else {
                this.summary = null;
                this.cluster = null;
            }
        }

        int getUniverseSize() {
            return universeSize;
        }

        int getMinimumKey() {
            return min;
        }

        int getMaximumKey() {
            return max;
        }

        int getSuccessor(int x) {
            if (universeSize == 2) {
                if (x == 0 && max == 1) {
                    return 1;
                }

                return NIL;
            }

            if (min != NIL && x < min) {
                return min;
            }

            int maximumLow = cluster[high(x)].getMaximumKey();

            if (maximumLow != NIL && low(x) < maximumLow) {
                int offset = cluster[high(x)].getSuccessor(low(x));
                return index(high(x), offset);
            }

            int successorCluster = summary.getSuccessor(high(x));

            if (successorCluster == NIL) {
                return NIL;
            }

            int offset = cluster[successorCluster].getMinimumKey();
            return index(successorCluster, offset);
        }

        int getPredecessor(int x) {
            if (universeSize == 2) {
                if (min == NIL) {
                    return NIL;
                }

                if (x == 1 && min == 0) {
                    return 0;
                }

                return NIL;
            }

            if (max != NIL && x > max) {
                return max;
            }

            int minimumLow = cluster[high(x)].getMinimumKey();

            if (minimumLow != NIL && low(x) > minimumLow) {
                int offset = cluster[high(x)].getPredecessor(low(x));
                return index(high(x), offset);
            }

            int predecessorCluster = summary.getPredecessor(high(x));

            if (predecessorCluster == NIL) {
                if (min != NIL && x > min) {
                    return min;
                }

                return NIL;
            }

            int offset = cluster[predecessorCluster].getMaximumKey();
            return index(predecessorCluster, offset);
        }

        void treeInsert(int x) {
            if (min == NIL) {
                emptyTreeInsert(x);
                return;
            }

            if (x < min) {
                Integer tmp = x;
                x = min;
                min = tmp;
            }

            if (universeSize != 2) {
                int minimum = cluster[high(x)].getMinimumKey();

                if (minimum == NIL) {
                    summary.treeInsert(high(x));
                    cluster[high(x)].emptyTreeInsert(low(x));
                } else {
                    cluster[high(x)].treeInsert(low(x));
                }
            }

            if (max < x) {
                max = x;
            }
        }

        void treeDelete(int x) {
            if (min == max) {
                min = NIL;
                max = NIL;
                return;
            }

            if (universeSize == 2) {
                if (x == 0) {
                    min = 1;
                } else {
                    max = 0;
                }

                max = min;
                return;
            }

            if (min == x) {
                int firstCluster = summary.getMinimumKey();
                x = index(firstCluster, cluster[firstCluster].getMinimumKey());
                min = x;
            }

            cluster[high(x)].treeDelete(low(x));

            if (cluster[high(x)].getMinimumKey() == NIL) {
                summary.treeDelete(high(x));

                if (x == max) {
                    int summaryMaximum = summary.getMaximumKey();

                    if (summaryMaximum == NIL) {
                        max = min;
                    } else {
                        int maximumKey = 
                                cluster[summaryMaximum].getMaximumKey();
                        max = index(summaryMaximum, maximumKey);
                    }
                }
            } else if (x == max) {
                int maximumKey = cluster[high(x)].getMaximumKey();
                max = index(high(x), maximumKey);
            }
        }

        private void emptyTreeInsert(int x) {
            min = x;
            max = x;
        }

        private int high(int x) {
            return x >>> highShift;
        }

        private int low(int x) {
            return x & lowMask;
        }

        private int index(int x, int y) {
            return (x << highShift) | (y & lowMask);
        }
    }

    /**
     * The root tree.
     */
    private VEBTree<E> root;

    /**
     * This map serves two purposes: first, it allows us to keep track of all 
     * the integer keys in the van Emde Boas tree, second, it maps each present
     * integer key to its satellite data.
     */
    private final Map<Integer, E> map = new HashMap<>();

    /**
     * Counts the number of modifications made to this data structure since its
     * construction.
     */
    private int modCount;

    public VanEmdeBoasTreeMap(int requestedUniverseSize) {
        checkRequestedUniverseSize(requestedUniverseSize);
        requestedUniverseSize = fixUniverseSize(requestedUniverseSize);
        root = new VEBTree<>(requestedUniverseSize);
    }

    @Override
    public E put(Integer key, E value) {
        modCount++;

        if (map.containsKey(key)) {
            return map.put(key, value);
        } else {
            map.put(key, value);
            root.treeInsert(key);
            return null;
        }
    }

    @Override
    public E get(Object key) {
        return map.get(key);    
    }

    @Override
    public E remove(Object key) {
        if (map.containsKey((Integer) key)) {
            modCount++;
            E returnValue = map.remove(key);
            root.treeDelete((Integer) key);
            return returnValue;
        } else {
            return null;
        }
    }

    @Override
    public boolean containsKey(Object key) {
        return map.containsKey(key);
    }

    @Override
    public boolean containsValue(Object value) {
        throw new UnsupportedOperationException(
                "This " + getClass().getSimpleName() + 
                " does not implement 'containsValue'.");
    }

    @Override
    public boolean isEmpty() {
        return map.isEmpty();
    }

    @Override
    public int size() {
        return map.size();
    }

    @Override
    public void clear() {
        root = new VEBTree<>(root.universeSize);
        modCount += map.size();
        map.clear();
    }

    @Override
    public void putAll(Map<? extends Integer, ? extends E> m) {
        for (Map.Entry<? extends Integer, ? extends E> entry : m.entrySet()) {
            put(entry.getKey(), entry.getValue());
        }
    }

    @Override
    public Collection<E> values() {
        throw new UnsupportedOperationException(
                "This " + getClass().getSimpleName() + " does not implement " +
                "'values'.");
    }

    @Override
    public Set<Entry<Integer, E>> entrySet() {
        throw new UnsupportedOperationException(
                "This " + getClass().getSimpleName() + " does not implement " +
                "'entrySet'.");
    }

    public int getMinimumKey() {
        if (map.isEmpty()) {
            throw new NoSuchElementException(
            "Asking for minimum integer key in empty VanEmdeBoasTreeMap.");
        }

        return root.getMinimumKey();
    }

    public int getPredessorKey(int x) {
        if (map.isEmpty()) {
            throw new NoSuchElementException(
            "Asking for predecessor integer key in empty VanEmdeBoasTreeMap.");
        }

        checkIntegerWithinUniverse(x, root.getUniverseSize());
        return root.getPredecessor(x);
    }

    public int getSuccessorKey(int x) {
        if (map.isEmpty()) {
            throw new NoSuchElementException(
            "Asking for successor integer key in empty VanEmdeBoasTreeMap.");
        }

        checkIntegerWithinUniverse(x, root.getUniverseSize());
        return root.getSuccessor(x);
    }

    public int getMaximumKey() {
        if (map.isEmpty()) {
            throw new NoSuchElementException(
            "Asking for maximum integer key in empty VanEmdeBoasTreeMap.");
        }

        return root.getMaximumKey();
    }

    @Override
    public Set<Integer> keySet() {
        return new KeySet();
    }

    private final class KeySet implements Set<Integer> {

        @Override
        public int size() {
            return map.size();
        }

        @Override
        public boolean isEmpty() {
            return map.isEmpty();
        }

        @Override
        public boolean contains(Object o) {
            return map.containsKey(o);
        }

        @Override
        public Iterator<Integer> iterator() {
            return new TreeIterator();    
        }

        private final class TreeIterator implements Iterator<Integer> {

            private Integer lastReturned;
            private int iterated;
            private final int expectedModCount = modCount;

            @Override
            public boolean hasNext() {
                checkModificationCount();
                return iterated < size();
            }

            @Override
            public Integer next() {
                checkModificationCount();

                if (!hasNext()) {
                    throw new NoSuchElementException("No next element.");
                }

                if (lastReturned == null) {
                    lastReturned = root.min;
                } else {
                    lastReturned = getSuccessorKey(lastReturned);
                }

                iterated++;
                return lastReturned;
            }

            private void checkModificationCount() {
                if (expectedModCount != modCount) {
                    throw new ConcurrentModificationException();
                }
            }
        }

        @Override
        public Object[] toArray() {
            throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
        }

        @Override
        public <T> T[] toArray(T[] a) {
            throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
        }

        @Override
        public boolean add(Integer e) {
            throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
        }

        @Override
        public boolean remove(Object o) {
            throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
        }

        @Override
        public boolean containsAll(Collection<?> c) {
            throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
        }

        @Override
        public boolean addAll(Collection<? extends Integer> c) {
            throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
        }

        @Override
        public boolean retainAll(Collection<?> c) {
            throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
        }

        @Override
        public boolean removeAll(Collection<?> c) {
            throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
        }

        @Override
        public void clear() {
            throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
        }

    }

    private void checkIntegerWithinUniverse(int x, int universeSize) {
        if (x < 0) {
            throw new IllegalArgumentException(
                    "This VanEmdeBoasTreeMap supports only non-negative " +
                    "keys. Received " + x + ".");
        }

        if (x >= universeSize) {
            throw new IllegalArgumentException(
                    "The input integer is too large: " + x + ". " +
                    "Must be at most " + (universeSize - 1) + ".");
        }
    }

    /**
     * Returns the fixed universe size that is a power of two and no smaller
     * than {@code requestedUniverseSize}.
     * 
     * @param requestedUniverseSize the requested universe size.
     * @return the fixed universe size.
     */
    private int fixUniverseSize(int requestedUniverseSize) {
        int tmp = Integer.highestOneBit(requestedUniverseSize);
        return tmp == requestedUniverseSize ? 
                      requestedUniverseSize : 
                     (tmp << 1);
    }

    private void checkRequestedUniverseSize(int requestedUniverseSize) {
        if (requestedUniverseSize < MINIMUM_UNIVERSE_SIZE) {
            throw new IllegalArgumentException(
                    "The requested universe size is too small: " + 
                    requestedUniverseSize + ". Should be at least " +
                    MINIMUM_UNIVERSE_SIZE + ".");
        }
    }

    private static int upperSquare(int number) {
        double exponent = Math.ceil(Math.log(number) / Math.log(2.0) / 2.0);
        return (int) Math.pow(2.0, exponent);
    }

    private static int lowerSquare(int number) {
        double exponent = Math.floor(Math.log(number) / Math.log(2.0) / 2.0);
        return (int) Math.pow(2.0, exponent);
    }
}

Demo.java

import java.util.Map;
import java.util.Objects;
import java.util.Random;
import java.util.TreeMap;
import net.coderodde.util.VanEmdeBoasTreeMap;

public class Demo {

    public static void main(String[] args) {
        final int UNIVERSE_SIZE = 30_000;
        final int LOAD_SIZE = 3_000_000;
        final int QUERY_SIZE = 2_000_000;
        final int DELETE_SIZE = 2_000_000;

        Map<Integer, Integer> tree1 = new VanEmdeBoasTreeMap<>(UNIVERSE_SIZE);
        Map<Integer, Integer> tree2 = new TreeMap<>();

        Random random = new Random();

        // Warmup:
        for (int i = 0; i < LOAD_SIZE; ++i) {
            int key = random.nextInt(UNIVERSE_SIZE);
            tree1.put(key, 3 * key);
            tree2.put(key, 3 * key);
        }

        for (int i = 0; i < QUERY_SIZE; ++i) {
            int key = random.nextInt(UNIVERSE_SIZE);

            if (!Objects.equals(tree1.get(key), tree2.get(key))) {
                throw new IllegalStateException(
                        "Trees do not agree during warmup.");
            }
        }

        for (int i = 0; i < DELETE_SIZE; ++i) {
            int key = random.nextInt(UNIVERSE_SIZE);

            if (!Objects.equals(tree1.remove(key), tree2.remove(key))) {
                throw new IllegalStateException(
                        "Trees do not agree during warmup.");
            }
        }

        if (tree1.size() != tree2.size()) {
            throw new IllegalStateException("Size mismatch after warmup.");
        }

        // Benchmark:
        long seed = System.currentTimeMillis();
        System.out.println("Seed = " + seed);

        Random random1 = new Random(seed);
        Random random2 = new Random(seed);

        long totalTime1 = 0L;
        long totalTime2 = 0L;

        ///// VanEmdeBoasTreeMap /////
        long startTime = System.currentTimeMillis();

        tree1 = new VanEmdeBoasTreeMap<>(UNIVERSE_SIZE);

        for (int i = 0; i < LOAD_SIZE; ++i) {
            int key = random1.nextInt(UNIVERSE_SIZE);
            tree1.put(key, 3 * key);
        }

        long endTime = System.currentTimeMillis();

        System.out.println("VanEmdeBoasTreeMap.put in " + 
                (endTime - startTime) + " milliseconds.");

        totalTime1 += endTime - startTime;

        startTime = System.currentTimeMillis();

        for (Integer i : tree1.keySet()) {

        }

        endTime = System.currentTimeMillis();

        System.out.println("VanEmdeBoasTreeMap iteration in " + 
                (endTime - startTime) + " milliseconds.");

        startTime = System.currentTimeMillis();

        totalTime1 += endTime - startTime;

        for (int i = 0; i < QUERY_SIZE; ++i) {
            int key = random1.nextInt(UNIVERSE_SIZE);
            tree1.get(key);
        }

        endTime = System.currentTimeMillis();

        System.out.println("VanEmdeBoasTreeMap.get in " +
                (endTime - startTime) + " milliseconds.");

        totalTime1 += endTime - startTime;

        startTime = System.currentTimeMillis();

        for (int i = 0; i < DELETE_SIZE; ++i) {
            int key = random1.nextInt(UNIVERSE_SIZE);
            tree1.remove(key);
        }

        endTime = System.currentTimeMillis();

        System.out.println("VanEmdeBoasTreeMap.remove in " +
                (endTime - startTime) + " milliseconds.");

        totalTime1 += endTime - startTime;

        System.out.println("VanEmdeBoasTreeMap total time: " + totalTime1 +
                " milliseconds.");
        System.out.println();

        ///// TreeMap /////
        startTime = System.currentTimeMillis();

        tree2 = new TreeMap<>();

        for (int i = 0; i < LOAD_SIZE; ++i) {
            int key = random2.nextInt(UNIVERSE_SIZE);
            tree2.put(key, 3 * key);
        }

        endTime = System.currentTimeMillis();

        System.out.println("TreeMap.put in " + 
                (endTime - startTime) + " milliseconds.");

        totalTime2 += endTime - startTime;

        startTime = System.currentTimeMillis();

        for (Integer i : tree2.keySet()) {

        }

        endTime = System.currentTimeMillis();

        System.out.println("TreeMap iteration in " + 
                (endTime - startTime) + " milliseconds.");

        startTime = System.currentTimeMillis();

        totalTime2 += endTime - startTime;

        startTime = System.currentTimeMillis();

        for (int i = 0; i < QUERY_SIZE; ++i) {
            int key = random1.nextInt(UNIVERSE_SIZE);
            tree2.get(key);
        }

        endTime = System.currentTimeMillis();

        System.out.println("TreeMap.get in " +
                (endTime - startTime) + " milliseconds.");

        totalTime2 += endTime - startTime;

        startTime = System.currentTimeMillis();

        for (int i = 0; i < DELETE_SIZE; ++i) {
            int key = random1.nextInt(UNIVERSE_SIZE);
            tree2.remove(key);
        }

        endTime = System.currentTimeMillis();

        System.out.println("TreeMap.remove in " +
                (endTime - startTime) + " milliseconds.");

        totalTime2 += endTime - startTime;

        System.out.println("TreeMap total time: " + totalTime2 +
                " milliseconds.");
    }
}

Performance figures

Seed = 1489681783887
VanEmdeBoasTreeMap.put in 430 milliseconds.
VanEmdeBoasTreeMap iteration in 40 milliseconds.
VanEmdeBoasTreeMap.get in 155 milliseconds.
VanEmdeBoasTreeMap.remove in 77 milliseconds.
VanEmdeBoasTreeMap total time: 662 milliseconds.

TreeMap.put in 1335 milliseconds.
TreeMap iteration in 16 milliseconds.
TreeMap.get in 942 milliseconds.
TreeMap.remove in 127 milliseconds.
TreeMap total time: 2404 milliseconds.

As always, any critique is much appreciated.

\$\endgroup\$
2
\$\begingroup\$

Organization is very nice.

You mentioned there is a large test suite. Thank you, this somewhat puts my mind at ease as a reviewer, each line of code becomes a bit more believable. I assume you measured code coverage with jacoco or similar?

You made a design choice that an empty tree's min would be NIL rather than the conventional "positive infinity" of M. That's fine, but it seems like it warrants a comment.

It appears that here:

    int getSuccessor(int x) {
        if (universeSize == 2) {

you intended to test equality against MINIMUM_UNIVERSE_SIZE rather than the literal 2.

I would like to see some more DbC support in methods like getSuccessor (design by contract). There's a precondition the caller must obey - x must fall within a prescribed range. Passing in e.g. -1 would be bad. I would like to see a javadoc comment and/or validity checks, so we "fail fast" if a negative value is passed in. Elsewhere you use checkIntegerWithinUniverse(x, root.getUniverseSize()). (Which, BTW, offers nice diagnostic exception messages.)

    int getPredecessor(int x) {
        if (universeSize == 2) {

Same remark, there's a constant MINIMUM_UNIVERSE_SIZE you probably want to use.

There's no comments within these method bodies, and I'm OK with that. After all, "comments lie," bit-rot happens. It's a (somewhat) well-known algorithm, and the identifiers are clear and useful.

Kudos for breaking out the emptyTreeInsert helper function (which it turns out is used twice):

    void treeInsert(int x) {
        if (min == NIL) {
            emptyTreeInsert(x);

Boxing tmp seems unnecessary:

        if (x < min) {
            Integer tmp = x;
            x = min;
            min = tmp;
        }

I don't know exactly how a JIT handles that. But explicitly declaring int makes sense to me. No biggie.

        if (universeSize != 2) {

Same remark about the MINIMUM_UNIVERSE_SIZE constant. Also in treeDelete.

In treeDelete, the single entry case (min == max) seems a bit odd, as the caller could have literally passed in anything. Does the caller have an obligation to pass in x equal to min? Do we care to check that? Perhaps to log errors? We want to make it easy for callers to be able to use this package in an error-free way.

I don't understand this clause:

        if (universeSize == 2) {
            if (x == 0) {
                min = 1;
            } else {
                max = 0;
            }
            max = min;
            return;
        }

I favor deleting the max = min; return; assignment, and having the equal zero clause explicitly do max = min = 1; return;. That leaves me with the non-zero case. We assign zero to max, and then we overwrite max with another value? What? This is odd enough to warrant an explanatory comment. Or maybe the test suite does not yet exercise that? Does EclEmma color those source lines green?

In constructors, it is traditional to explicitly mention this, as I have added below:

public VanEmdeBoasTreeMap(int requestedUniverseSize) {
    checkRequestedUniverseSize(requestedUniverseSize);
    requestedUniverseSize = fixUniverseSize(requestedUniverseSize);
    this.root = new VEBTree<>(requestedUniverseSize);
}

I suppose you might elide the assignment, and just go with new VEBTree<>(fixUniverseSize(requestedUniverseSize)).

It surprised me a little that you chose not to cast to (Integer) here:

@Override
public boolean containsKey(Object key) {
    return map.containsKey(key);
}

If caller asked about containsKey("not a number") then the cast would blow up and he finds out sooner than later that he did the wrong thing.

In KeySet, same remark, consider casting o to (Integer) to support Fail Fast:

    @Override
    public boolean contains(Object o) {
        return map.containsKey(o);
    }

The name checkModificationCount() is perfectly nice, but consider moving up a level of abstraction and naming it checkDirty(), as it is essentially checking whether someone dirtied the data structure while an iteration is in progress. Or checkModified() if you prefer - the "count" aspect is just an implementation detail.

The identifier fixUniverseSize is perfectly nice, but maybe fixUniverseSizePowerOfTwo?

Please indent last line one additional space:

    return tmp == requestedUniverseSize ? 
                  requestedUniverseSize : 
                 (tmp << 1);

For the upper / lower signatures:

private static int upperSquare(int number) {

instead of number I would prefer to see size (or maybe universeSize). I think one can only call those methods with a power of 2, so the ceiling / floor is slightly distracting, it makes me consider other possibilities. They're called just once so they're hardly performance critical, but perhaps some bit twiddling would actually be clearer than using logarithms? Maybe their API is simpler to understand if caller passes in an int logarithm?

As I read the demo, it occurs to me that more than two thousand key values, from 30k to 32k, should not be handed in by (bug-free) caller code. Yet checkIntegerWithinUniverse() can only see the power-of-two value, not the caller's original value. No biggie, it's just being less helpful for debugging the calling code than it might be.

This code might verify that i is within expected range, or at least that LOAD_SIZE keys came back:

    for (Integer i : tree1.keySet()) {

    }

This might verify that stored value is triple the key:

    for (int i = 0; i < QUERY_SIZE; ++i) {
        int key = random1.nextInt(UNIVERSE_SIZE);
        tree1.get(key);
    }

After all the remove() calls, I was hoping you'd at least verify smaller .size().

The code following tree2 = new TreeMap<>(); is all copy-n-paste, which suggests an opportunity to break out a new benchmark(Map map) method.

That factor of six speedup for .get() is definitely impressive.

Overall, the code base is consistent and well thought out. You should be proud of it.

\$\endgroup\$
3
\$\begingroup\$

I am sorry, but regarding the performance figures, you are comparing apples to oranges.

Your so-called VanEmdeBoasTreeMap implementation actually uses a java.util.HashMap for virtually all off its tested operations (apart from iteration).

On the other hand, you compare to a java.util.TreeMap. Well, it is clear that your internal java.util.HashMap is considerably faster than the java.util.TreeMap you compare to.

This single fact fully explains the ostensible speedup of your VanEmdeBoasTreeMap.

A second methodical flaw is that you are not benchmarking the two data structures independently of each other. The benchmark of the second data structure always inherits the memory garbage of the first datastructure's benchmark and thus is artificially slowed down by its predecessor.

And third, do not believe in a single measurement. In the following figures, I took the median measurement of nine independent measurements.

If you replace in the VanEmdeBoasTreeMap class

private final Map<Integer, E> map = new HashMap<>();

by

private final Map<Integer, E> map = new TreeMap<>();

you receive the following realistic results, comparing your enriched TreeMap to the standard TreeMap:

Seed = 1511631843489
VanEmdeBoasTreeMap.put in 1223 milliseconds.
VanEmdeBoasTreeMap iteration in 18 milliseconds.
VanEmdeBoasTreeMap.get in 423 milliseconds.
VanEmdeBoasTreeMap.remove in 85 milliseconds.
VanEmdeBoasTreeMap total time: 1731 milliseconds.

Seed = 1511631930097
TreeMap.put in 795 milliseconds.
TreeMap iteration in 6 milliseconds.
TreeMap.get in 401 milliseconds.
TreeMap.remove in 77 milliseconds.
TreeMap total time: 1273 milliseconds.

Here, the two blocks of benchmarks figures were taken independently of each other, by commenting the benchmark code of the respective other data structure out.

As a result, you can see that your VanEmdeBoas implementation generates an average overhead of >35%.

Or, to have an alternative fair competition, replace in the demo code

tree2 = new TreeMap<>();

by

tree2 = new HashMap<>();

and you get the following results, comparing your enriched HashMap to the standard HashMap (which still is termed "TreeMap" here, because I did not edit the console message strings):

Seed = 1511632397148
VanEmdeBoasTreeMap.put in 260 milliseconds.
VanEmdeBoasTreeMap iteration in 17 milliseconds.
VanEmdeBoasTreeMap.get in 88 milliseconds.
VanEmdeBoasTreeMap.remove in 48 milliseconds.
VanEmdeBoasTreeMap total time: 396 milliseconds.

Seed = 1511632550587
TreeMap.put in 202 milliseconds.
TreeMap iteration in 8 milliseconds.
TreeMap.get in 80 milliseconds.
TreeMap.remove in 47 milliseconds.
TreeMap total time: 329 milliseconds.

Again, the two blocks of benchmarks figures were taken independently of each other, by commenting the benchmark code of the respective other data structure out. Every block is the median block of 9 measurements.

Still your VanEmdeBoas implementation generates an average overhead of >20%.

Obviously, the alleged speed up of your VanEmdeBoasTreeMap only attributes to the fact that you are indeed encapsulating a standard java.util.HashMap.

In terms of speed up, I cannot recognize any added value of your implementation (apart from the ordering in the iteration).

A nice programming exercise though.

If you are interested in true benchmark figures, please throw the java.util.HashMap out of your class VanEmdeBoasTreeMap and rework the benchmark code so that it only uses the actual VanEmdeBoas data structure.

\$\endgroup\$
  • \$\begingroup\$ The HashMap is used for storing the actual key/value pairs, and the actual van Emde Boas tree is there for bringing order to the keys; iteration over keySet() will always produce an increasing sequence of keys, so it is a sorted map as it should be. \$\endgroup\$ – coderodde Nov 30 '17 at 21:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.