which collection to use?

Performance Tuning
#1

hey there :slight_smile:

The game I’m working on heavily depends on non-incremental numbers associated with objects (for many different purposes), and I can’t find a good type of collection for this. ArrayList, Vector and LinkedList all depend on incremental indices, all other collections associate Objects with Objects. Right now I’m using HashMap<Integer, Object>, but I guess that’s far from being the optimal solution.

Is there any int -> Object collection implementation which I simply overlooked? If that’s not the case, is HashMap<Integer, Object> a good enough solution or should I write my own collection for this purpose?

#2

You might be interested in the IntHashMap class in one of the Apache projects.

org.apache.commons.lang.IntHashMap

#3

Or you might take a look at the pcj ( http://pcj.sourceforge.net/ ) library and the IntKeyMap subclasses, which offer what you need.
Alternatively the apache commons primitive (http://jakarta.apache.org/commons/primitives/) might help. But I found that it’s always lacking the specific collection I needed (in your case there seems to be no HashMap).

@Riven: I couldn’t find IntHashMap in the current apache.commons.lang API docs. Can you post a link?

#4

I think HashMap<Integer, Object> is good enough. I think HashMap use Object.hashCode() as its key internally. The Integer class just returns its integer value in its hashCode() function. So you pretty much got exactly what you want. Although there is the overhead of wrapping the int in an Integer.

#5

http://trove4j.sourceforge.net/

updated in 2005, while the pcj’s last update was 2003 (prior to java 1.5).

thank you very much for your help :slight_smile:

#6

from what i’ve seen ArrayLists are pretty fast for general stuff and random access. However LinkedLists are a little faster when having a problem that require you to scroll through the list from begining to end. You may also want to look at FastList at http://javolution.org/

#7

As I said in my first post, I can’t use arraylist or the like because the indices aren’t incremental. anyways, thanks for the javolution link, I didn’t know about that before and it seems pretty nifty :smiley:

that whole page seems to be an advertisement for those libs, though. any experiences? o_O

#8

Use Map.

Yes, thats an interface not a class.

The right thing to do whenevr using collections is to design your code to use the interfaces. Then you can tune later as needed by swaping different implementations (eg HashMap, TreeMap, etc) or even writing your own.

Rule #1 of writing fast code:
First write clean, clear and well encapsulated code. Second profile. Thrid go back and fix bottlenecks.

#9

Yeash, but I couldn’t find an interface for which there was any implementation for int->object association, that’s why I asked in the first place :stuck_out_tongue:

#10

Map<Integer,Object>.

Map associates any two objects

With Java5 autoboxing you can treat int like an object if you so desire.

#11

I know, but still using a direct int->object association is faster (saves one boxing and two hash calls per get, and I need tons of gets) than using a boxed int, that’s why I asked if there was any specific implementation for that.

#12

Again: IntHashMap from Jakarta Commons

Here is the java2html page…

#13

I know, I just told Jeff why I asked for this in the first place. >_<

#14

Err, sorry, I confused krausest’s response with yours.

#15

Thats really your bottleneck? You’ve proved this with a profiler??

I would be astonished if the rest of your code was so beautifully tight that this was significant.

#16

The rest of the code normally doesn’t matter… only a few lines will be performance-critical.

It’s very easy to create a bottleneck in accessing Maps with autoboxed ints in tight loops. Very easy.
I’ve done a lot of pathfinding-stuff where the difference between HashMap<Integer, Object> and IntHashMap was significantly astonishing :slight_smile:

#17

[quote]Thats really your bottleneck? You’ve proved this with a profiler??
I would be astonished if the rest of your code was so beautifully tight that this was significant.
[/quote]
I wrote a spatial index where autoboxing was, at one point in time, a bottleneck in the index. (About ~50 million objects in the index, with query times running in the low milliseconds). I ended up creating my own special “GeometrySet” interface which enabled me to avoid most boxing/autoboxing at the expense of more complexity.

Of course, I wouldn’t randomly go around getting rid of all boxing, but it can be a bottleneck in tight loops that deal with many objects.

#18

50million objects = 1.5 gigabytees of object overhead and unnecessary garbage collection trawling too… autoboxing bad! Evil!

Cas :slight_smile:

#19

30 byte per object?! :o Really?

#20

You talk about minimum 2-3+ pointers + 1-0 identifier.
One pointer is on 32 bit computer 4 bytes, it’s 8 bytes on 64 bit CPU.
You could look at my old post about my memory problems (with something like patricia trie). 12 - 24 bytes + some aditional object info looks like real object overhead. Test it.

Dipper is superior to any autoboxing (with exception of computationally expensive types), and it alows to use rather nice (and FAST) abstractions with sliding window.