CODEWITHSUNDEEP
javaperformancearraylisthashtable
B.Gen.Jack.O.Neill
B.Gen.Jack.O.Neill

Reputation: 8397

Java Iterated HashTable vs ArrayList speed

I am writing a simple 3D SW rendering engine. I have a default ArrayList<Object3D> containing the whole scene. Now, I want to be able to add, remove and select objects by name, like 3D editors do (because its MUCH more simple than mouse select, but still looking good in homework :) ).

So, the first thing I thought is to have Hashtable for name and index to scene ArrayList. But, then I thought I could just simply save the scene using Hashtable directly, and go through it to render using iterator.

So I want to ask, in a 3D engine, what is speed-preferable? Because I will for-loop the scene many times per second, compared to selecting object. Is ArrayList any faster than iterated Hashtable? Thanks.

Upvotes: 5

Views: 8413

Answers (6)

Wojciech Owczarczyk
Wojciech Owczarczyk

Reputation: 5735

Use java.util.HashMap instead of java.util.Hashtable if you don't need retrieval synchronization.

Upvotes: 0

Ted Hopp
Ted Hopp

Reputation: 234795

First, I suggest you use a HashMap instead of a Hashtable, for the same reason that ArrayList is a better choice than a Vector: less overhead due to useless synchronization.

My guess is that iterating through an ArrayList will be faster than iterating through the Set returned by a Hashtable's (or HashMap's) entrySet() method. But the only way to know is to profile.

Obviously, changes to the display list (other than appending or chopping off the last element) are going to be faster for a HashMap than for an ArrayList.

EDIT So I followed my own advice and benchmarked. Here's the code I used:

import java.util.*;

public class IterTest {
    static class Thing {
        Thing(String name) { this.name = name; }
        String name;
    }

    static class ArrayIterTest implements Runnable {
        private final ArrayList<Thing> list;
        ArrayIterTest(ArrayList<Thing> list) {
            this.list = list;
        }
        public void run() {
            int i = 0;
            for (Thing thing : list) {
                ++i;
            }
        }
    }

    static class ArraySubscriptTest implements Runnable {
        private final ArrayList<Thing> list;
        ArraySubscriptTest(ArrayList<Thing> list) {
            this.list = list;
        }
        public void run() {
            int i = 0;
            int n = list.size();
            for (int j = 0; j < n; ++j) {
                Thing thing = list.get(j);
                ++i;
            }
        }
    }

    static class MapIterTest implements Runnable {
        private final Map<String, Thing> map;
        MapIterTest(Map<String, Thing> map) {
            this.map = map;
        }
        public void run() {
            int i = 0;
            Set<Map.Entry<String, Thing>> set = map.entrySet();
            for (Map.Entry<String, Thing> entry : set) {
                ++i;
            }
        }
    }

    public static void main(String[] args) {
        final int ITERS = 10000;
        final Thing[] things = new Thing[1000];
        for (int i = 0; i < things.length; ++i) {
            things[i] = new Thing("thing " + i);
        }
        final ArrayList<Thing> arrayList = new ArrayList<Thing>();
        Collections.addAll(arrayList, things);
        final HashMap<String, Thing> hashMap = new HashMap<String, Thing>();
        for (Thing thing : things) {
            hashMap.put(thing.name, thing);
        }
        final ArrayIterTest t1 = new ArrayIterTest(arrayList);
        final ArraySubscriptTest t2 = new ArraySubscriptTest(arrayList);
        final MapIterTest t3 = new MapIterTest(hashMap);
        System.out.println("t1 time: " + time(t1, ITERS));
        System.out.println("t2 time: " + time(t2, ITERS));
        System.out.println("t3 time: " + time(t3, ITERS));
    }

    private static long time(Runnable runnable, int iters) {
        System.gc();
        long start = System.nanoTime();
        while (iters-- > 0) {
            runnable.run();
        }
        return System.nanoTime() - start;
    }
}

And here are the results for a typical run:

t1 time: 41412897
t2 time: 30580187
t3 time: 146536728

Clearly using an ArrayList is a big win (by a factor of 3-4) over a HashMap, at least for my style of iterating through a HashMap. I suspect the reason the array iterator is slower than array subscripting is all the iterator objects that need to be created and then garbage-collected.

For reference, this was done with Java 1.6.0_26 (64-bit JVM) on an Intel 1.6GHz quad-core Windows machine with plenty of free memory.

Upvotes: 6

Stas
Stas

Reputation: 1725

As already said, it's better to use HashMap. Regarding to iteration, in theory, ArrayList has to be faster for two reasons. First is that data structure is simpler, which gives less access time. The second is that ArrayList can be iterated by index without creating Iterator object, which, in case of intense use, produce less garbage and therefore less gc. In practice - you may not notice difference, depends how heavy you are going to use it.

Upvotes: 0

Sean Patrick Floyd
Sean Patrick Floyd

Reputation: 298818

A) don't use Hashtable, use HashMap. Hashtable is informally deprecated

B) That depends on the application. Lookup will be faster in the HashMap, Iteration will likely be the same as both use arrays internally. (but the arrays in a HashMap have gaps, so that might give a slight advantage to the ArrayList). Oh, and if you want to maintain a fixed order of iteration, use LinkedHashMap (sorted by insertion) or TreeMap (sorted by natural ordering)

Upvotes: 0

rfeak
rfeak

Reputation: 8204

Actually, I looked at the current HashMap implementation (preferred over Hashtable as everyone points out). Iterating over the values looks like it's simply iterating through an underlying array.

So, speed will probably be comparable to iterating an ArrayList, though there may be some time skipping over gaps in the HashMaps underlying array.

All said, profiling is king.

Upvotes: 0

Hot Licks
Hot Licks

Reputation: 47699

I'm fairly sure that iterating through the ArrayList will be faster than iterating over the Hashtable. Not sure how significant the difference is, though -- maybe (thumb suck) 2x in the actual internal logic, but that's not much.

But note that, unless you need multithread synchronization, you should use a HashMap rather than a Hashtable. There's some performance to be gained there.

Upvotes: 1

Related Questions