Does Explicit nulling help garbage collection

Here I would be discussing whether explicit nulling of variables helps garbage collection in any significant way. For those who are not up to date with HotSpot GC, let me throw some light on that. The heap is divided into several spaces: Eden space, 2 survivor spaces and an old generation space. The Eden space and the 2 survivor spaces make up the young generation. When an object is created, it is created in the Eden space. Most objects die there (become out of scope) and are collected by the garbage collector. If an object  remains in the Eden space till the next minor GC runs, it is promoted to the 1st survivor space and then to the next survivor space. If an object becomes too old or the young generation becomes full, objects get promoted to the old generation space.

Now, lets get back on the topic: Does nulling variables explicitly help garbage collector ?
The answer is it depends. If the Eden space is full and an object is being created then if sufficient space could be created in Eden, then no more work is required. But if sufficient space can't be freed in Eden then existing objects in Eden space have to be promoted to the 1st survivor space before new objects can be created. There might be some objects in the Eden space that the application doesn't need now. But those objects have still not gone out of scope and hence can't be garbage collected. Explicitly nulling the variables holding the references to those objects would make a difference and those objects can now be garbage collected.

One thing that is to be noted here is that compiler can make object references null even if you don't make them null explicitly. Only in cases where the compiler can't prove that the object is no longer used, it doesn't make them null. Explicitly nulling can help GC in rare cases such as the one discussed above. All the following conditions should be true if you are explicitly nulling object references :

• The variable is the only weak reference to the object.
• The variable will stay in scope for an extended period of time.
• The compiler is not able to prove that the object is no longer used but you are able to prove that the object is no longer needed.

In general, explicitly nulling is not required because the Java compiler is smart enough to do that. One very important use case of explicitly nulling is when you have a map having some entries that you no longer need. The objects to which the map entries point to are not eligible for garbage collection. Making them null explicitly does help. But something like the following won't help since the object would anyhow go out of scope and would be garbage collected in the next GC run. We should never do this :

Bit Manipulation : Find 2 numbers which are repeated odd number of times in an array in which all other numbers are repeated even number of times

Today I would be sharing a problem which can be very efficiently solved using bit manipulations.

Problem :

Given an array containing integer numbers containing numbers which are repeated even number of times except two numbers which are repeated odd number of times. The range of integer numbers is not given. Find the two numbers which are repeated even odd number of time.

Solution :

It can be solved in O(n) time and O(1) space. The basic concept here is x ^ x = 0. Here's the algorithm :

1) XOR all the elements in the array. This would nullify all the elements which are repeated even number of times. So, we would get the XOR of elements which are repeated odd number of times.

2) Now divide the set of numbers into 2 sets such that numbers which are repeated odd number of times go into different sets. To divide the set in this way is quite easy given that the set bits in the XOR of two numbers are the bits in which the two numbers differ. From step 1, we got the XOR of the numbers which are repeated odd number of times. Divide all the elements of the array into 2 sets depending on any of the set bits in the XOR output of step 1.

3) XOR all the elements within each set and we would get the elements which are repeated odd number of times since the elements which are repeated even number of times would have nullified  each other.

Here is the code snippet :

Now result1 and result2 would hold the numbers which are repeated odd number of times.

There is a trick to find the lowest bit position set. Suppose x is a number and we wish to find the lowest bit position which is set. We can do so by :
x |= x & (x-1);
The above code snippet can be made more efficient by employing the above rule.