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

This is a discussion on I thought C is faster than Java, it seems I was wrong within the C Programming forums, part of the General Programming Boards category; I was a Java programer, I start to learn C programming now. I thought C is faster than Java, and ...

  1. #1
    Registered User
    Join Date
    Oct 2010
    Posts
    14

    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.

  2. #2
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,164
    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.
    If you understand what you're doing, you're not learning anything.

  3. #3
    Registered User Swarvy's Avatar
    Join Date
    Apr 2008
    Location
    United Kingdom
    Posts
    195
    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'.

  4. #4
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    Like the other people have said: You were not wrong! You are wrong now, thinking that.
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  5. #5
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,592
    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 you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,307
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Registered User
    Join Date
    Oct 2010
    Posts
    14
    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;
    }
    Last edited by icoigo; 11-04-2010 at 12:50 AM.

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,794
    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);
    }
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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??

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,794
    Quote 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;
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    Registered User
    Join Date
    Oct 2010
    Posts
    14
    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.

  12. #12
    Registered User
    Join Date
    Jun 2005
    Posts
    6,341
    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.
    Right 98% of the time, and don't care about the other 3%.

  13. #13
    Registered User
    Join Date
    Oct 2010
    Posts
    14
    Quote Originally Posted by laserlight View Post
    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!

  14. #14
    Registered User
    Join Date
    Aug 2010
    Posts
    231
    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?

  15. #15
    C-no_Ob Bennie98's Avatar
    Join Date
    Oct 2010
    Location
    Ledeberg, Ghent, East-Flanders, Belgium
    Posts
    49
    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
    Because Tetris Is Unrealistic.

    "The fear of death is the most unjustified of all fears, for there's no risk of accident for someone who's dead." - Albert Einstein

    "The Edge... there is no honest way to explain it because the only people who really know where it is are the ones who have gone over." - Hunter S. Thompson

    "I never think of the future. It comes soon enough." - Albert Einstein

Page 1 of 3 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Java is 1000 times faster than c++ on my computer???
    By darin722 in forum C++ Programming
    Replies: 16
    Last Post: 06-13-2009, 12:48 AM
  2. Mats, the java answers
    By Jaqui in forum A Brief History of Cprogramming.com
    Replies: 1
    Last Post: 04-22-2008, 02:12 AM
  3. Java for Games
    By ElastoManiac in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 04-10-2006, 10:59 PM
  4. Floating point faster than fixed-point
    By VirtualAce in forum A Brief History of Cprogramming.com
    Replies: 5
    Last Post: 11-08-2001, 10:34 PM
  5. Visual J#
    By mfc2themax in forum A Brief History of Cprogramming.com
    Replies: 0
    Last Post: 10-08-2001, 02:41 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21