Why java is slow

The Real World

The moment you start using objects in your program, Java looses the potential
for optimization. This section lists some of the reasons why.

1. All Objects are Allocated on the Heap

Java only allocates primitive data types like int and double and object
references on the stack. All objects are allocated on the heap.

For large objects which usually have identity semantics, this is not a handicap.
C++ programmers will also allocate these objects on the heap.
However, for small objects with value semantics, this is a major performance killer.

What small objects? For me these are iterators. I use a lot of them in my designs.
Someone else may use complex numbers. A 3D programmer may use a
vector or a point class. People dealing with time series data will use a time class.
Anybody using these will definitely hate trading a zero-time stack
allocation for a constant-time heap allocation. Put that in a loop and that becomes
O (n) vs. zero. Add another loop and you get O (n^2) vs. again, zero.

2. Lots of Casts

With the advent of templates, good C++ programmers have been able to avoid casts
almost completely in high-level programs. Unfortunately, Java doesn’t have templates,
so Java code is typically full of casts.

What does that mean for performance? Well, all casts in Java are dynamic casts,
which are expensive. How expensive? Consider how you would implement a dynamic cast:

The fastest thing you could do is assign a number to each class and then have a
matrix that tells if any two classes are related, and if they are, what is the
offset that needs to be added to the pointer in order to make the cast.
In that case, the pseudo-code for the cast would look something like this:

DestinationClass makeCast (Object o, Class destinationClass) {
Class sourceClass = o.getClass (); // JIT compile-time
int sourceClassId = sourceClass.getId (); // JIT compile-time

int destinationId = destinationClass.getId ();

int offset = ourTable [sourceClassId][destinationClassId];

if (offset != ILLEGAL_OFFSET_VALUE) {
return ;
}
else {
throw new IllegalCastException ();
}
}
Quite a lot of code, this little cast! And this here is a rosy picture
-using a matrix to represent class relationships takes up a lot of memory and no
sane compiler out there would do that. Instead, they will either
use a map or walk the inheritance hierarchy – both of which will slow things down even further.

3. Increased Memory Use

Java programs use about double the memory of comparable C++ programs
to store the data. There are three reasons for this:

Programs that utilize automatic garbage collection typically use
about 50% more memory that programs that do manual memory management.
Many of the objects that would be allocated on stack in C++ will
be allocated on the heap in Java.
Java objects will be larger, due to all objects having a virtual table
plus support for synchronization primitives.
A larger memory footprint increases the probability that parts of the
program will be swapped out to the disk. And swap file usage kills the
speed like nothing else.

4. Lack of Control over Details

Java was intentionally designed to be a simple language. Many of the
features available in C++ that give the programmer control over details were
intentionally stripped away.

For example, in C++ one can implement schemes that improve the locality
of reference. Or allocate and free many objects at once. Or play pointer
tricks to make member access faster. Etc.

None of these schemes are available in Java.

5. No High-Level Optimizations

Programmers deal with high-level concepts. Unlike them, compilers deal
exclusively with low-level ones. To a programmer, a class named Matrix
represents a different high-level concept from a class named Vector.
To a compiler, those names are only entries in the symbol table.
What it cares about are the functions that those classes contain,
and the statements inside those functions.

Now think about this: say you implement the function exp (double x, double y)
that raises x to the exponent y. Can a compiler,
just by looking at the statements in that function, figure out that exp (exp (x, 2), 0.5)
can be optimized by simply replacing it with x? Of course not!

All the optimizations that a compiler can do are done at the statement level,
and they are built into the compiler.
So although the programmer might know that two functions are symmetric and
cancel each other now, or that the order of some function calls is irrelevant
in some place,
unless the compiler can figure it out by looking at the statements,
the optimization will not be done.

So, if a high-level optimization is to be done, there has to be a way
for the programmer to specify the high-level optimization rules for the compiler.

No popular programming language/system does this today. At least not
in the totally open sense, like what the Microsoft’s Intentional
Programming project promises.
However, in C++ you can do template metaprogramming to implement
optimizations that deal with high-level objects. Temporary elimination,
partial evaluation,
symmetric function call removal and other optimizations can be implemented
using templates. Of course, not all high-level optimizations can be done this way.
And implementing some of these things can be cumbersome. But a lot can be done,
and people have implemented some snazzy libraries using these techniques.

Unfortunately, Java doesn’t have any metaprogramming facilities, and thus high-level
optimizations are not possible in Java.

So…

Java, with the current language features, will never be as fast as C++. This pretty much means that it’s not a sensible choice for high-performance software and
the highly competitive COTS arena. But its small learning curve, its forgiveness, and its large standard library make it a good choice for some small and
medium-sized in-house and custom-built software.

Codechef : Prime Generator

Codechef Experience.

It is a medium scaled problem in Codechef. The task was to generate all prime numbers between two given numbers(M and N).

Constraints were N<=10^9  and N-M<=10^4.  Time:2 sec

Easy Part: We all know how we can tell whether any number is prime or not. By definition prime numbers are those numbers which have exactly 2 factors 1 and the number itself. 

There are many approaches to solve this problem.

Approach 1: We start with M and check whether it is divisible by any number between 2 and M-1. We do it until M==N.

Algo:

1. read M,N
2. if(m<=2) print 2 do m=m+1
3. i=2
4. check=( M%i)
5. if(check ==0)   do  M=M+1 up-to(M<= N)  and   jump to step 3
6. else do i=i+1  up-to (i<M) and  jump to step 4
7. if(i==m) print M else M=M+1 up-to(M<=N) and jump to step 3

Time Complexity: (From wiki)

primes          approach
up to           takes

100             .00100 sec
1000            .02800 sec
10000           1.6980 sec
100000          130.44 sec
1000000         10732  sec

As this algo is taking bruteforce approach so it is impossible to solve the asked problem within the specified time.

Even if you try to make changes like don’t check an even number  ,increase i upto sqrt(i),and check primality of any number with only previous prime numbers,then also time complexity is very high.

Approach2:

Sieve of Eratosthenes 

It is a very standard approach and very fast . This algorithm was created by a Greek mathematician by the name of Eratosthenes.

Algo:

Simply make a list of consecutive numbers from 2 up to the number n. Now, take each number from the front of the list (first 2, then 3 and so on) and remove the multiples of each of these numbers from the rest of the list starting from the square of the number.  At the end of this procedure, all remaining numbers are prime.

The above picture(taken from the wiki) is showing the method to find the prime numbers upto 120.

So in this specific problem what i did is the following.

I took a Boolean array of size 40000 and initialize the with false. I start with i=2 and initialize the value at index 2*i with true.

then I increase i by 2 again and    initialize the value at index i with true.

Then do same thing with i=3,i=5,i=7… increasing every time  i with 3,5,7.. respectively.

Then doing such thing upto i=srt( 40000).If the value at any index  is false then that index is prime otherwise false.

When any number in the range [M,N]<=40000 i can check in O(1) time. If that number is greater than  40000 then i start with the index=2 and do the primality testing upto sqrt(any number) .

When i submit my solution I realized that this algorithm worked out to be very efficient.Why? Because  I saw this!!!!. 🙂

Nested-Inner class in java

It is possible to define a class within another class.
The scope of the nested class is within the enclosing class.
There are two type of nested classes in Java.
The nested classes which are static are simply called the Nested classes
while the non-static ones are called Inner classes.
Example of Inner Classes.

class outer_class{
public static void main(String args[]){
outer_class outer_object=new outer_class();
}

inner_class inner_object=new inner_class();
int ffff=inner_object.z;

private int x;
public int y;
class inner_class{
void fn(){
x=10;
y=9;
}
private int z;
}

}

In inner classes even the private members of the enclosing class are
directly accessible to the enclosed class.And also the private members
of the enclosed class is accessable through the object of the enclosed class
in the enclosing class.
Note:Inner classes cannot have static members. Static declarations are
for top-level entities,or for the class as a whole, not an instance.
And also we cannot declare any static variable in any function.
Example of Static Classes.

class outer_class{

static class inner_class{

}

}

As it is the static class, we cannot access the members of the outer class directly.

So we have to access them using the object.

Note:There is no such modifier static for the class which is not enclosed
in another class

class dev{
public static void main(String args[])
{
deven.fn();//non-static variable this cannot be referenced
//from the static context
}
}

static class deven{ //Modifier static not allowed here

void fn(){
System.out.println("Deven");
}
}