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

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.

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);
}

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;

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.

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