How big is an object reference?

Question

What is the size that a reference in Android's Java VM consumes?

More info:

By that I mean, if we have

String str = "Watever";

I need what str takes, not "Watever". -- "Watever" is what's saved in the location to which the pointer (or the reference) that str is holding, is pointing to.

Also, if we have

String str = null;

how much memory does it consume? Is it the same as the other str?

Now, if we have:

Object obj[] = new object[2];

how much does obj consume and how much does obj[1] and obj[2] consume?

---

The reason for the question is the following: (in case someone can recommend something).

I'm working on an app that manages many pictures downloaded from internet. I started storing those pictures on a "bank" (that consists of a list of pictures).

When displaying those pictures on a gallery, I used to search for the picture in the list (SLOW) and then, if then picture wasn't there, I used to show a temporal downloading image until the picture was downloaded.

Since that happened on the UI Thread, the app became very slow, so I thought about implementing a hash table on the bank instead of the list I had.

As I explained before, this search occurs in the UI Thread (and I can't change that). Because of that, collisions can become a problem if they start slowing the thread.

I have read that "To balance time and space efficiency, the hash table should be around half full", but that makes collisions occur half of the time (Not practical for the UI Thread). That makes me think about having a very long hash table (compared to the amount of pictures saved) and use more RAM (having less free VMHeap).

Before determining the size of the hash table, I wanted to know how much memory would it consume in order not to exagerate.

I know that the size of the hash table might be very small compared to the memory that the pictures might consume, but I wanted to make sure I wasn't consuming more memory than necessary.

---

Before asking this question i searched, between other places, in

How big is an object reference in Java and precisely what information does it contain?

reference type size in java

Hashing Tutorial

(Yes, I know two of the places contradict each other, that's part of the reason for the question).

Solution 1

A object or array reference occupies one 32 bit word (4 bytes) on a 32 bit JVM or Davlik VM. A null takes the same space as a reference. (It has to, because a null has to fit in a reference-typed slot; i.e. instance field, local variable, etc.)

On the other hand, an object occupies a minimum of 2 32 bit words (8 bytes), and an array occupies a minimum of 3 32 bit words (12 bytes). The actual size depends on the number and kinds of fields for an object, and on the number and kind of elements for an array.

---

For a 64 bit JVM, the size of a reference is 64 bits, unless you have configured the JVM to use compressed pointers:

-XX:+UseCompressedOops Enables the use of compressed pointers (object references represented as 32 bit offsets instead of 64-bit pointers) for optimized 64-bit performance with Java heap sizes less than 32gb.

---

This is the nub of your question, I think.

Before determining the size of the hash table, I wanted to know how much memory would it consume in order not to exagerate.

If you allocate a HashMap or Hashtable with a large initial size, the majority of the space will be occupied by the hash array. This is an array of references, so the size will be 3 + initialSize 32 bit words. It is unlikely that this will be significant ... unless you get your size estimate drastically wrong.

However, I think you are probably worrying unnecessarily about performance. If you are storing objects in a default allocated HashMap or Hashtable, the class will automatically resize the hash table as it gets larger. So, provided that your objects have a decent hash function (not too slow, not hashing everything to a small number of values) the hash table should not be a direct CPU performance concern.

Solution 2

References are nearly free. Even more so when compared to images.

Having a few collisions in a Map isn't a real problem. Collisions can be resolved far quicker than a linear search through a list of items. That said, a Binary Search through a sorted list of items would be a good way to keep memory usage down (compared to a Map).

I can vouch for the effectiveness of a having smaller initial sizes for Maps - I recently wrote a program that makes a Trie structure of 170000 English words. When I set the initial size to 26, I would run out of memory by the time I got to words starting with R. Cutting it down to 5, I was able to create the maps without memory issues and can search the tree (with many collisions) in effectively no time.

[Edit] If a reference is 32 bit (4 bytes) and your average image is around 2 megabytes, you could fit 500000 references into the same space that a single image would take. You don't have to worry about the references.

Comments

[J-Rou]

Thank you verry much. I'm giving the answer to Stephen C because he answeres the exact question, but I'm giving you a +1 because you confirmed what I was thinking and gave me a good example on a Hash table (I've never created one). I think this question helps me just as much.

[J-Rou]

Also, my average image ize is 60k, so about 7500 references of 32 bit could fit. Its more than enought.

[J-Rou]

Thank you. That solves my problem. But just for understanding this better. Can you please explain a little more in the arrays. If I have an array, lets say Object[2], it would occupy 3 words + 2 words for each object (3 + 2 * 2 = 7 words)??

[Stephen C]

No. It will take 3 words for the array header + 1 word for each element; i.e. 5 words. (The array holds references to Objects not actual Objects.)

[J-Rou]

Thank you or the second part and the comment too, I've never used hash tables before so the second part really helped.

[HopefullyHelpful]

What about generic objects ? Do they also use 3 words ?

[HopefullyHelpful]

Ok, I think that generic objects also use only 2 words because of type erasure.

[Stephen C]

Generic objects have exactly the same runtime representation as non-generic objects ... including the size of object headers.

[Stephen C]

(Generic & non-generic objects do typically have 2 word headers though. The difference is that a non-array object does not have / need a length field.)