I thought C is faster than Java, it seems I was wrong

I was a Java programer, I start to learn C programming now. I thought C is faster than Java, and the performance is much better because games are most likely written in C.

Last night I wrote a program, same methodology and algorithm, Java program gets the result under 60 seconds, and C program took 122 seconds. I am quite surprise about that huge different.

However, it could be my problem since I am new to C. The part takes significant time of the program is only one method, this method is recursively called by itself known as recursive method. And inside this method, I allocate memory to hold some data which its type is char **, it is 2D char array. Also memcpy data into this new allocated memory. And I have to free it after the recursive call. I am quite sure this takes a lot of time. In C, I do it manually. In Java, handled by garbage collection.

I just wonder if there is anyway to improve this C program performance so that it can beat the Java program. Any suggestion would be appreciated.

Without seeing your code it's hard to tell. I'd actually be interested in seeing both the C and Java versions.

The first thing that springs to mind is making sure your recursive function is written in a way that can take advantage of Tail Recursion.

C is faster than Java because Java is executed through a virtual machine. Unless you post some code we can't say anything about your program or it's running time of 122 seconds. Let alone why it is running slower than 'java equivalent'.

Like the other people have said: You were not wrong! You are wrong now, thinking that.

There's a pretty good chance that your experienced Java self can write a program that can beat your newbie C self.

But there is plenty of dumb stuff you can do in C that will cripple the code.

As others have said - POST YOUR CODE.

If I was to write the same program in Java, mine would probably take around 200 seconds.
Everything is faster when you know what you're doing. You don't know C well so you'll be doing stupid things.

Hi All,

This is the code of the recursive method. Thank you all for your reply and take time to help me improve my C programming skill.
Java code:

Code:

	
	public static boolean completePath(int[][] data) {
		for (int[] dataVal : data) {
			for (int value : dataVal) {
				if (value == 0) {
					return false;
				}
			}
		}
		return true;
	}
	
	public static int[][] cloneData(int[][] data) {
		int[][] cloneData = new int[data.length][data[0].length];
		for (int i = 0; i < data.length; i++) {
			for (int j = 0; j < data[0].length; j++) {
				cloneData[i][j] = data[i][j];
			}
		}
		return cloneData;
	}

public static long readyGo(int y, int x, int[][] grid) {
		long count = 0;

		if (y != 0) {
			if (grid[y - 1][x] == 3) {
				int[][] cloneGrid = cloneData(grid);
				cloneGrid[y][x] = 1;
				if (completePath(cloneGrid)) {
					return 1;
				}
			}
			if (grid[y - 1][x] == 0) {
				int[][] cloneGrid = cloneData(grid);
				cloneGrid[y][x] = 1;
				count += readyGo(y - 1, x, cloneGrid);
			}
		}
		if (y != grid.length - 1) {
			if (grid[y + 1][x] == 3) {
				int[][] cloneGrid = cloneData(grid);
				cloneGrid[y][x] = 1;
				if (completePath(cloneGrid)) {
					return 1;
				}
			}
			if (grid[y + 1][x] == 0) {
				int[][] cloneGrid = cloneData(grid);
				cloneGrid[y][x] = 1;
				count += readyGo(y + 1, x, cloneGrid);
			}
		}
		if (x != 0) {
			if (grid[y][x - 1] == 3) {
				int[][] cloneGrid = cloneData(grid);
				cloneGrid[y][x] = 1;
				if (completePath(cloneGrid)) {
					return 1;
				}					
			}
			if (grid[y][x - 1] == 0) {
				int[][] cloneGrid = cloneData(grid);
				cloneGrid[y][x] = 1;
				count += readyGo(y, x - 1, cloneGrid);
			}
		}
		if (x != grid[0].length - 1) {
			if (grid[y][x + 1] == 3) {
				int[][] cloneGrid = cloneData(grid);
				cloneGrid[y][x] = 1;
				if (completePath(cloneGrid)) {
					return 1;
				}
			}
			if (grid[y][x + 1] == 0) {
				int[][] cloneGrid = cloneData(grid);
				cloneGrid[y][x] = 1;
				count += readyGo(y, x + 1, cloneGrid);
			}
		}
		return count;
	}

And this is my C program codes:

Code:

// Global variable.
int width = 0, height = 0;
char **guide_ptr;

int complete_path(char **grid_graph) {
	for (int i = 0; i < height; i++) {
		char *char_ptr = strchr(grid_graph[i], '0');
		if (char_ptr != NULL) {
			return 0;
		}
	}
	return 1;
}

char **clone_data(char **grid_graph) {
	char **clone_grid = calloc(sizeof(char *), height);
	for (int i = 0; i < height; i++) {
		clone_grid[i] = malloc(width);
		memcpy(clone_grid[i], grid_graph[i], width);
	}
	return clone_grid;
}

void free_data(char **grid_graph) {
	for (int i = 0; i < height; i++) {
		free(grid_graph[i]);
	}
	free(grid_graph);
}

// recursive method
long readyGo(int x, int y, char **grid_graph) {
	long count = 0;
	if (y != 0) {
		if (*(grid_graph[y-1] + x) == '3') {
			char **clone_graph = clone_data(grid_graph);
			*(clone_graph[y] + x) = '1';
			if (complete_path(clone_graph)) {
				free_data(clone_graph);
				return 1;
			}
			free_data(clone_graph);
		}
		if (*(grid_graph[y-1] + x) == '0') {
			char **clone_graph = clone_data(grid_graph);
			*(clone_graph[y] + x) = '1';
			count += readyGo(x, y - 1, clone_graph);
			free_data(clone_graph);
		}
	}
	if (y != height - 1) {
		if (*(grid_graph[y+1] + x) == '3') {
			char **clone_graph = clone_data(grid_graph);
			*(clone_graph[y] + x) = '1';
			if (complete_path(clone_graph)) {
				free_data(clone_graph);
				return 1;
			}
			free_data(clone_graph);
		}
		if (*(grid_graph[y+1] + x) == '0') {
			char **clone_graph = clone_data(grid_graph);
			*(clone_graph[y] + x) = '1';
			count += readyGo(x, y + 1, clone_graph);
			free_data(clone_graph);
		}
	}
	if (x != 0) {
		if (*(grid_graph[y] + x - 1) == '3') {
			char **clone_graph = clone_data(grid_graph);
			*(clone_graph[y] + x) = '1';
			if (complete_path(clone_graph)) {
				free_data(clone_graph);
				return 1;
			}
			free_data(clone_graph);
		}
		if (*(grid_graph[y] + x - 1) == '0') {
			char **clone_graph = clone_data(grid_graph);
			*(clone_graph[y] + x) = '1';
			count += readyGo(x - 1, y, clone_graph);
			free_data(clone_graph);
		}
	}
	if (x != width - 1) {
		if (*(grid_graph[y] + x + 1) == '3') {
			char **clone_graph = clone_data(grid_graph);
			*(clone_graph[y] + x) = '1';
			if (complete_path(clone_graph)) {
				free_data(clone_graph);
				return 1;
			}
			free_data(clone_graph);
		}
		if (*(grid_graph[y] + x + 1) == '0') {
			char **clone_graph = clone_data(grid_graph);
			*(clone_graph[y] + x) = '1';
			count += readyGo(x + 1, y, clone_graph);
			free_data(clone_graph);
		}
	}
	return count;
}

For starters, you could try reducing the number of allocations, e.g.,

Code:

char **clone_data(char **grid_graph) {
	/* assume malloc always succeeds */
	char **clone_grid = malloc(height * sizeof(clone_grid[0]));
	char *data = malloc(height * width);
	int i;
	for (i = 0; i < height; ++i) {
		clone_grid[i] = data + (i * width);
	}
	memcpy(clone_grid[0], grid_graph[0], height * width);
	return clone_grid;
}

void free_data(char **grid_graph) {
	free(grid_graph[0]);
	free(grid_graph);
}

So your program is constantly calloc'ing memory, and then freeing it.

Eeegawds!

reminds me of that scene from "Gone With the Wind". Where the woman to assist in the imminent birth declares:

"I don't know nuffin' 'bout birffing babies!"

You WHAT??

Originally Posted by Adak

So your program is constantly calloc'ing memory, and then freeing it.

In many places that looks necessary because of the recursion, but in several places it is not, e.g., this:

Code:

char **clone_graph = clone_data(grid_graph);
*(clone_graph[y] + x) = '1';
if (complete_path(clone_graph)) {
	free_data(clone_graph);
	return 1;
}
free_data(clone_graph);

could be written as:

Code:

char original = grid_graph[y][x];
grid_graph[y][x] = '1';
if (complete_path(grid_graph)) {
	grid_graph[y][x] = original;
	return 1;
}
grid_graph[y][x] = original;

As my first post said, I know this should be the biggest time consuming.

And inside this method, I allocate memory to hold some data which its type is char **, it is 2D char array. Also memcpy data into this new allocated memory. And I have to free it after the recursive call. I am quite sure this takes a lot of time.

I just what to know how to improve it because I am new to C, that also mean I am new to memory management stuff.

A large part of the problem is that you've translated somewhat-optimised Java code literally to C, and the techniques don't really map well (a literal translation of efficient Java code to C often gives very inefficient C code - and vice versa).

An area where Java and C work very differently is memory management. Java implementations are typically optimised to ensure memory used by temporaries is reused reasonably efficiently (once the temporary is no longer needed) and your Java code exploits that. In C (and C++) on the other hand, the programmer who cares about efficiency will typically avoid writing code that repeatedly creates and releases temporary copies of large objects (or 2D arrays, in your case).

To illustrate, I'll have a stab at the first if block in your readyGo() function. I'm not going to tackle the whole function, as your version has lots of duplication of code, and my purpose is only to illustrate the idea ..... you can apply the same technique to the whole function if you wish to test (don't just replace the one if() block - rest of your function needs the same style of modification).

What you have is this;

Code:

       if (y != 0) {
		if (*(grid_graph[y-1] + x) == '3') {
			char **clone_graph = clone_data(grid_graph);
			*(clone_graph[y] + x) = '1';
			if (complete_path(clone_graph)) {
				free_data(clone_graph);
				return 1;
			}
			free_data(clone_graph);
		}
		if (*(grid_graph[y-1] + x) == '0') {
			char **clone_graph = clone_data(grid_graph);
			*(clone_graph[y] + x) = '1';
			count += readyGo(x, y - 1, clone_graph);
			free_data(clone_graph);
		}
	}

Here is my version.

Code:

	if (y != 0) {
                char  value = *(grid_graph[y-1] + x);
                char *element = grid_graph[y] + x;
                char temp = *element;
		if (value == '3') {
                        int retval;
                       *element = '1';
                        retval = complete_path(grid_graph);
                        *element = temp;
                         if (retval) return 1;
		}
		else if (value == '0') {
                        *element = '1';
			count += readyGo(x, y - 1, grid_graph);
			*element = temp;
		}
	}

Notably, my version will not call clone_data() at all, so does not need to call free_data(). It achieves this by temporarily modifying a single element of grid_graph array, rather than cloning the whole array, modifying an element of the copy, and then releasing it.

Note also that I have not tested this with a compiler, so I may have left some errors of logic or typos. You'll need to fix those to test. There is also scope to optimise my version even further and make it more readable, but what I've done is enough to illustrate my point.

Don't even get me started on the differences between accessing elements of 2D arrays between Java and C. I won't bother to describe the inefficiencies (yes, they're bad) of your clone_data() and free_data() functions - simply because my approach eliminates the need for them.

Originally Posted by laserlight

For starters, you could try reducing the number of allocations, e.g.,

Code:

char **clone_data(char **grid_graph) {
	/* assume malloc always succeeds */
	char **clone_grid = malloc(height * sizeof(clone_grid[0]));
	char *data = malloc(height * width);
	int i;
	for (i = 0; i < height; ++i) {
		clone_grid[i] = data + (i * width);
	}
	memcpy(clone_grid[0], grid_graph[0], height * width);
	return clone_grid;
}

void free_data(char **grid_graph) {
	free(grid_graph[0]);
	free(grid_graph);
}

After changing the codes as above, change the way to allocate and free memory, the C program only takes 33 seconds to get the result. Pretty cool!

Try this:

Code:

// recursive method
long readyGo(int x, int y, char **grid_graph) {
        char **clone = clone_data(grid_graph);
	long count = 0;
	if (y != 0) {
		if (*(grid_graph[y-1] + x) == '3') {
			char **clone_graph = clone;
			*(clone_graph[y] + x) = '1';
			if (complete_path(clone_graph)) {
				free_data(clone_graph);
				return 1;
			}
			//free_data(clone_graph);
		}
		else if (*(grid_graph[y-1] + x) == '0') {
			char **clone_graph = clone;
			*(clone_graph[y] + x) = '1';
			count += readyGo(x, y - 1, clone_graph);
			//free_data(clone_graph);
		}
	}
	if (y != height - 1) {
		if (*(grid_graph[y+1] + x) == '3') {
			char **clone_graph = clone;
			*(clone_graph[y] + x) = '1';
			if (complete_path(clone_graph)) {
				free_data(clone_graph);
				return 1;
			}
			//free_data(clone_graph);
		}
		else if (*(grid_graph[y+1] + x) == '0') {
			char **clone_graph = clone;
			*(clone_graph[y] + x) = '1';
			count += readyGo(x, y + 1, clone_graph);
			//free_data(clone_graph);
		}
	}
	if (x != 0) {
		if (*(grid_graph[y] + x - 1) == '3') {
			char **clone_graph = clone;
			*(clone_graph[y] + x) = '1';
			if (complete_path(clone_graph)) {
				free_data(clone_graph);
				return 1;
			}
			//free_data(clone_graph);
		}
		else if (*(grid_graph[y] + x - 1) == '0') {
			char **clone_graph = clone;
			*(clone_graph[y] + x) = '1';
			count += readyGo(x - 1, y, clone_graph);
			//free_data(clone_graph);
		}
	}
	if (x != width - 1) {
		if (*(grid_graph[y] + x + 1) == '3') {
			char **clone_graph = clone;
			*(clone_graph[y] + x) = '1';
			if (complete_path(clone_graph)) {
				free_data(clone_graph);
				return 1;
			}
			//free_data(clone_graph);
		}
		else if (*(grid_graph[y] + x + 1) == '0') {
			char **clone_graph = clone;
			*(clone_graph[y] + x) = '1';
			count += readyGo(x + 1, y, clone_graph);
			//free_data(clone_graph);
		}
	}
	return free(clone),count;
}

Where do you set height?

apparently it's possible by coding correctly to shorten the time it takes for your program to do it's thing.... does anyone have any pointers in how to optimalize your code to accomplish this?
please send me a personal message or leave your pointers here thx