Skip to main content

No Primitives in java Collection (boxing / unboxing)

17 replies [Last post]
oneguyks
Offline
Joined: 2008-04-28
Points: 0

<br />
import java.util.*;<br />
public class test {</p>
<p>    final static int SIZE = 5000000;<br />
    final static List list = new ArrayList (SIZE);<br />
    final static int[] alist = new int [SIZE];</p>
<p>    public static void main(String args[])  {</p>
<p>        int sum = 0;<br />
        long start = System.currentTimeMillis();</p>
<p>        for (int i = 0; i < SIZE; i++) {<br />
            alist[i] = i;<br />
        }<br />
        for (int i = 0; i < SIZE; i++) {<br />
            sum += alist[i];<br />
        }<br />
        long end = System.currentTimeMillis();</p>
<p>        System.out.println("Array Sum: " + sum + "\nTime: " + (end - start) + "ms");</p>
<p>        sum = 0;<br />
        assert(sum == 0);<br />
        start = System.currentTimeMillis();</p>
<p>        for (int i = 0; i < SIZE; i++) {</p>
<p>            list.add(i);<br />
        }</p>
<p>        for (int i = 0; i < SIZE; i++) {<br />
            sum += list.get(i);<br />
        }</p>
<p>        end = System.currentTimeMillis();</p>
<p>        System.out.println("List Sum:  " + sum + "\nTime: " + (end - start) + "ms");<br />
    }<br />
} 

Weird behavior: if I don't add -Xmx128m flag, the above code just prints the first print statement and exists, instead of throwing out of memory exception. Is this a bug?

Also, this example shows that Java collection is unusable if the performance is important. It would have been nice if Collection classes could use primitives directly instead of first converting them to wrapper classes.

Reply viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
oneguyks
Offline
Joined: 2008-04-28
Points: 0

>By the way, why does the original code I posted throw out memory exception?

That was a typo. What I meant was why does it NOT throw out memory exception.

It doesn't work without -Xmx128m, but if I don't add -Xmx128m it doesn't throw out memory exception.

Message was edited by: oneguyks

walterln
Offline
Joined: 2007-04-17
Points: 0

According to [url=http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4753347]4753347[/url] this should be fixed in 1.6 (and works with the test program in that report). But fails for your test case, though the exit code is 1.

cowwoc
Offline
Joined: 2003-08-24
Points: 0

+1000

I totally agree with mthornton on this one. I believe that cleaning up Generics should be a much higher priority. Currently there is a lot of infighting amongst the Java community about adding new features because of the negative experience that has resulted from Generics. If we clean it up, as mthornton suggests, we would be in a much better position to add new features with a strong consensus.

Please guys, vote for http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=5098163 and ask Sun to increase the priority of this bug as soon as possible!

oneguyks
Offline
Joined: 2008-04-28
Points: 0

By the way, why does the original code I posted throw out memory exception?

walterln
Offline
Joined: 2007-04-17
Points: 0

Because an Integer is bigger than an int.

Using [url=http://www.javaworld.com/javaworld/javatips/jw-javatip130.html?page=2]16 bytes[/url] for an Integer, you need 5000000 * 16 ~= 78Mb. I think think Java defaults to 64Mb, so you get an out of memory exception some where in the loop.

If int is [url=http://www.javaworld.com/javaworld/javaqa/2003-12/02-qa-1226-sizeof.html]32 bit[/url], you only need ~19.5Mb for that.

mthornton
Offline
Joined: 2003-06-10
Points: 0

Yes it would be nice if generics was extended to primitives. However, for consistency, we first need to reify generics (i.e. add classes which do not erase their type parameters). It is quite a bit of work and currently appears to have low priority.
I have checked out the OpenJDK compiler and have started hacking a change, but currently have very limited spare time (too much real work to do).

mthornton
Offline
Joined: 2003-06-10
Points: 0

In addition I think that a combination of reifying generics and extending them to primitives would allow much of the enormous generics FAQ to be relegated to an historical footnote. Many of the awkward cases that don't currently work, would work as expected. It would also significantly simplify libraries like the fork/join framework which is one of the poster cases for closures.

In practice erased types would be retained for the medium term, so the generics FAQ would still apply when using erasure, but most new code could use reified types.

oneguyks
Offline
Joined: 2008-04-28
Points: 0

Using Integer in a Collection class is over 80 times slower than just using ints in an array. I am not sure but the penalty for autoboxing double maybe even larger. autoboxing should have not been added to the language. I suspect that now for backward compatibility reasons, this "feature" cannot be removed.

Also, even if using custom collection classes that allow primitives, another performance flaw is that everything is passed by value.

For example, let's say there is custom Hashtable for primitives that takes . The int is a counter for String, i.e it's a basic word counting app to track the frequency of word. The counter is incremented every time same String is found. Since there is no pass by reference for primitives, incrementing the counter requires both put and get (and put and get are expensive in a Hashtable). For example, something like this can't be done..

int count = hashMap.get(someWord);
count++;

or maybe

hashMap.get(someWord)++;

an extra put is required...

int count = hashMap.get(someWord);
hashMap.put(someWord, count++);

That means twice slower than the first option since both get and put are used to increment the counter. Am I missing anything?

mthornton
Offline
Joined: 2003-06-10
Points: 0

If you want to update the value in a map the simplest way (in my opinion) is something like this:

class Counter { int value;}

...

Map map;
String key;
...

Counter count = map.get(key);
if (count == null) {
count = new Counter();
map.put(key, count);
}
count.value++;

Now the put happens only once for each key, so you gain provided the average count is greater than 2.

oneguyks
Offline
Joined: 2008-04-28
Points: 0

>class Counter { int value;}
>map.put(key, count);

The problem is creating a new counter object. It's not same as being able to increment primitive. Another way to keep count would be

[code]
Map map;
String key;
...
int[] count = map.get(key);
if (count == null) {
map.put(key, new int[]{1});
}
else count[0]++; [/code]

In both cases, if count == null, we have one get and one put. That's still two. If primitives could be passed by references, it would need just one put.

map.put(key)++;

Message was edited by: oneguyks

mthornton
Offline
Joined: 2003-06-10
Points: 0

> In both cases, if count == null, we have one get and
> one put. That's still two. If primitives could be
> passed by references, it would need just one put.
>
> map.put(key)++;
>

The closest we could get to that would be a map which had a special action invoked when there is no existing entry. java.util.concurrent.ConcurrentMap implementations have a putIfAbsent method. This could be used like so:

Counter absent = new Counter(1);
ConcurrentMap map;

...

Counter count = map.putIfAbsent(key, absent);
if (count == null)
absent = new Counter(1);
else
count.value++;

The number of map lookups is now exactly the same as you propose. This does take more memory, but if that matters you should write a special purpose map implementation. That map implementation could return an interface like:

interface Counter {
int getValue();
int incrementValue();
}

Use it enough and HotSpot might inline the interface invocations.

ijuma
Offline
Joined: 2005-10-19
Points: 0

> This does take more memory, but if that
> matters you should write a special purpose map
> implementation.

Or just use:

http://trove4j.sourceforge.net/javadocs/gnu/trove/TObjectIntHashMap.html#increment(K)

Ismael

oneguyks
Offline
Joined: 2008-04-28
Points: 0

>Or just use:

>http://trove4j.sourceforge.net/javadocs/gnu/trove/TObjectIntHashMap.html#increment(K)

That doesn't solve the lookup problem.

Edit: Not sure maybe it does.

Message was edited by: oneguyks

ijuma
Offline
Joined: 2005-10-19
Points: 0

> >Or just use:
>
> >http://trove4j.sourceforge.net/javadocs/gnu/trove/TOb
> jectIntHashMap.html#increment(K)
>
> That doesn't solve the lookup problem.
>
> Edit: Not sure maybe it does.

Yes it does. You can use increment, adjustValue or adjustOrPutValue depending on your use-case.

Ismael

oneguyks
Offline
Joined: 2008-04-28
Points: 0

>Yes it does. You can use increment, adjustValue or adjustOrPutValue depending on your use-case.

But first you need to check if the key is present before you adjustValue and/or increment. If not, can you post a short example that solves the above problem I posted?

ijuma
Offline
Joined: 2005-10-19
Points: 0

> >Yes it does. You can use increment, adjustValue or
> adjustOrPutValue depending on your use-case.
>
> But first you need to check if the key is present
> before you adjustValue and/or increment. If not, can
> you post a short example that solves the above
> problem I posted?

map.adjustOrPutValue(1, 1);

That will start the counter at 1 for a non-existing key and add 1 for an existing key. You can also start at any other number and increment by any other number. Internally the map only computes the hashCode and the insertionIndex once and either puts the value and key in the appropriate array buckets or increments the primitive int in the values array.

All of what I described can be easily verified by inspecting the source code. Trove is open-source and it is designed specifically to deal with cases where the Java collections are too slow and/or take too much space. This is usually only relevant when primitives are being used.

Ismael

ijuma
Offline
Joined: 2005-10-19
Points: 0

> map.adjustOrPutValue(1, 1);

I forgot to include the key in the call, instead it should be:

map.adjustOrPutValue("key", 1, 1);