5

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.

Improve this question

6 Answers 6

Reset to default
6

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

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.

Improve this answer

5 Comments

For most applications that require synchronization, the method-level synchronization of Hashtable is almost always wrong and you end up doing higher-level synchronization anyway. I wouldn't recommend Hashtable as a way to deal with multithreaded synchronization.
Hashtable is useful where the table is updated randomly from different threads. Not where you'd necessarily want to "synchronize" the threads with it, but to simply avoid getting a corrupted table such as would happen with HashMap.
Yes, that's one case that falls outside the "most" in my comment. I just think that it's uncommon that an application needs to share a map between threads but needs no synchronization other than that necessary to ensure the map isn't corrupted.
When I was maintaining the iSeries JVM we had multiple complaints from people (actually, banks, etc) that they were getting the "corrupted" errors from HashMap, when it turns out they were doing multi-thread stuff.
Switching from HashMap to Hashtable will eliminate corrupted data structure as a symptom of improper synchronization, but my guess is that a different symptom cropped up somewhere. When (if?) their app developers finally figured out how to synchronize their threads properly, the need to use Hashtable probably went away. Like I say, just a guess. :)
0

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.

Improve this answer

1 Comment

The array is an array of buckets. Each bucket contain a chain of entries that must be traversed as well. You'll have to use a LinkedHashMap anyway to preserve the order, and LinkedHashMap uses a chain of entries rather than an array to iterate.
0

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)

Improve this answer

Comments

0

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.

Improve this answer

Comments

0

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

Improve this answer

1 Comment

Perhaps you could elaborate a bit more on this answer?

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.