Java vs C version of same algorithm

Question

I implemented one program in Java, which surprising took 177M memory for particular test-cases (I do not have since program are tested by one website).

The problem was to find out all the characters of string S2, which are present in string S1. And there are N such cases.

public static void main(String[] args) throws Exception {
    BufferedReader bin = new BufferedReader (new InputStreamReader (System.in));
    String jewel, stone;
    int t = Integer.parseInt (bin.readLine());
    int count;
    int i;

    while (t-->0) {
        count = 0;
        jewel = bin.readLine();
        stone = bin.readLine();
        for (i=0; i<stone.length(); i++) {
            if (jewel.indexOf(stone.charAt(i)) !=-1) {
                count++;
            }
        }
        System.out.println(count);
    }
}

I also do not understand, how it is taking 177M of ram. Even if they are testing a huge file then also only 2 strings are there. However code was perfectly working and test-cases passed.

Since java program was taking huge amount of memory, so I planned to write a C version of same program. which is following:

int main ()
{
  char * pch;
    char jewel[100], stone[100];
    int n;
    scanf("%d",&n);
    int len;    
    int tp;
    int count = 0;
    getchar(); // remove trailing '\n'
    while (n-->0) {

        gets(jewel);
        pch = gets(stone);
        count = 0;

        while(*pch ) {
            if (strchr(jewel, *pch)) {
                count++;
            }
            pch++;
        }
        printf("%d\n", count);
    }
  return 0;
}

On few existing cases, it is working. Program seems to be correct too. But I am unable to understand why it is passing all test cases correctly.

All the strings buffer are long enough to hold the incoming strings, which are separated by new lines.

EDIT: Changing ""+stone.charAt(i)) to stone.charAt(i)) did not help and took same amount of memory. Also why this C code is not able to pass all the test cases ?

Answer 1

""+stone.charAt(i) creates a short-lived string object. This occupies a small amount of memory, and will eventually be freed by the garbage collector[*].

Your C code, on the other hand, doesn't allocate any memory at all.

Java's garbage collector doesn't necessarily do work until it needs to. If you have more than 177MB of memory available to your program, and the program churns through creating 177MB of short-lived objects, then so be it. If you start to run out of memory, or if the garbage collector notices that there's idle time it could be running in, then it will free some of that memory. So your program's memory use might well grow to fit what is available.

Alternatively, the GC might run even while there's still memory available. If the GC were forced to run (for example) every 10MB of allocations, then you'd expect the memory use of this code to be around 10MB, so I guess that in this case it doesn't. On another JVM maybe it would.

[*] There's a theoretical optimization the Java implementation could perform, to notice that no reference to the object escapes the loop, and then allocate/free it differently to avoid churning the GC. I'm guessing that hasn't happened in this case, but it's worth knowing that different JVMs, or the same JVM with different options, might have very different garbage-collection strategies.

Answer 2

The Java code creates a buffered reader, and a input stream reader. Both of these are guaranteed to use large chunks of memory, which won't be free'd until the garbage collector runs (which might not be until the program exits!).

jewel = bin.readLine();

In the java, each call to .readline will create a new string on the heap, the assignment will mark the previous string as 'free-able', but it'll hang around in memory until GC gets rid of it.

C does very little in the way of memory management. The only line which may allocate a chunk of memory is gets but that probably just uses the console input buffer which doesn't count to the programs memory usage.

I think you are comparing apples with oranges to make fruit juice. Re-write the C code to use a garbage collection and buffered read classes and you might have an equivalent program.