24 users logged in
Proud partner of GDC 2025
Before posting, review our community guidelines.
Support GameDev.net with a monthly GDNet+ subscription!
March 28, 2001 11:43 AM
Hi,
I don''t really know where to post this so I''m sorry if it can''t be here.
I don''t know very much about programming but a friend of mine showed me a comparation betwen how fast C and Java is. The test, which were to arrange a serie of number from 10000, 9999, 9998 etc in the order 1, 2, 3 etc using a medthod caled bublesort, showed that Java was about twice as fast as C.
Now the only problem is that my friend is very much for Java and against C so I''m wondering if the C code he used is optimal (see below)?
#include
#include
#define ELEMENTS 10000
#define false 0
#define true 1
int main (void)
{
int sortElements[ELEMENTS];
int countIndex = 0;
struct timeb timef;
int sortTemp;
int sortMore;
long startTime;
int nrTests = 0;
int sortElementsIndex;
sortMore = true;
for(sortElementsIndex = ELEMENTS-1; sortElementsIndex >=0 ;sortElementsIndex--)
{
countIndex++;
sortElements[sortElementsIndex] = countIndex;
}
ftime (&timef);
startTime = timef.time * 1000 + timef.millitm;
while(sortMore)
{
int index;
sortMore=false;
for(index = 0; index < ELEMENTS-1; index++)
{
if(sortElements[index] > sortElements[index+1])
{
sortTemp = sortElements[index];
sortElements[index] = sortElements[index+1];
sortElements[index+1] = sortTemp;
sortMore = true;
}
nrTests++;
}
}
ftime (&timef);
// startTime = timef.time * 1000 + timef.millitm;
#if 0
for (int counter = 0; counter < 1000; counter++)
{
printf ("%d\n", sortElements[counter]);
}
#endif
printf ("Tests: %d\n", nrTests);
printf ("Time: %d\n", timef.time * 1000 + timef.millitm - startTime);
}
Thanks in advance
Spearhawk
122
March 28, 2001 03:40 PM
A while ago (i ting last year) i wrote a faster version of a bubble sort. I don''t know if this is the first time that this meathod has been done or if it is the fastest possible, but here it is:
// FstSort.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "FstSort.h"
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif
/////////////////////////////////////////////////////////////////////////////
// The one and only application object
CWinApp theApp;
using namespace std;
#include // for getche()
#include // mostly for printf()
#include // for CString
int _tmain(int argc, TCHAR* argv[], TCHAR* envp[])
{
CString in; //the input string to be sorted
int len; // a variable to store the lenth of the input in
int a; // for a counter
char max; // for the maximum character value
char min=''z''; // for the minimum character value, (the real minimum will never be above ASCII 254)
char med; // the mid value
CString fir; // the first half of the semi sorted string
CString sec; // the second half of the semi sorted string
CString str; // the variable to put the semi sorted string inot and sort from
int change; // to record the number of changes in the vuvle sort
char tmp; // a temporary char to store a value in for the bubble sort.
in="nbsgwkgzka"; // put something in the input string for demo purposes
len=in.GetLength(); // the assigment of the lenth (CString::GetLenth() does not include the terminating cahracter)
a=0; // set to counter to zero;
printf("the unsorted string: %s\n\n", in); // show the user what the unsorted string is.
while(a if(in
if(str[a]>str[a+1]){
tmp=str[a];
str.SetAt(a, str[a+1]);
str.SetAt(a+1, tmp);
change+=1;}}
a++;}}
printf("the sorted string: %s", str); // there you''re done, str is the sorted string.
printf("\n\nPlease press any key to contine. ");
getche(); // so you can see the string before it terminates
return 0;
}
The above code was intended to sort characters, but can easily be chenged to sort numbers.
hope this helps
' Target=_Blank>Link
// FstSort.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "FstSort.h"
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif
/////////////////////////////////////////////////////////////////////////////
// The one and only application object
CWinApp theApp;
using namespace std;
#include
#include
#include
int _tmain(int argc, TCHAR* argv[], TCHAR* envp[])
{
CString in; //the input string to be sorted
int len; // a variable to store the lenth of the input in
int a; // for a counter
char max; // for the maximum character value
char min=''z''; // for the minimum character value, (the real minimum will never be above ASCII 254)
char med; // the mid value
CString fir; // the first half of the semi sorted string
CString sec; // the second half of the semi sorted string
CString str; // the variable to put the semi sorted string inot and sort from
int change; // to record the number of changes in the vuvle sort
char tmp; // a temporary char to store a value in for the bubble sort.
in="nbsgwkgzka"; // put something in the input string for demo purposes
len=in.GetLength(); // the assigment of the lenth (CString::GetLenth() does not include the terminating cahracter)
a=0; // set to counter to zero;
printf("the unsorted string: %s\n\n", in); // show the user what the unsorted string is.
while(a
if(str[a]>str[a+1]){
tmp=str[a];
str.SetAt(a, str[a+1]);
str.SetAt(a+1, tmp);
change+=1;}}
a++;}}
printf("the sorted string: %s", str); // there you''re done, str is the sorted string.
printf("\n\nPlease press any key to contine. ");
getche(); // so you can see the string before it terminates
return 0;
}
The above code was intended to sort characters, but can easily be chenged to sort numbers.
hope this helps
' Target=_Blank>Link
122
March 28, 2001 03:47 PM
Sorry about the above post, it got screwed up, i hope this one works
A while ago (i think last year) i wrote a faster version of a bubble sort. I don''t know if this is the first time that this meathod has been done or if it is the fastest possible, but here it is:
// FstSort.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "FstSort.h"
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif
/////////////////////////////////////////////////////////////////////////////
// The one and only application object
CWinApp theApp;
using namespace std;
#include // for getche()
#include // mostly for printf()
#include // for CString
int _tmain(int argc, TCHAR* argv[], TCHAR* envp[])
{
CString in; //the input string to be sorted
int len; // a variable to store the lenth of the input in
int a; // for a counter
char max; // for the maximum character value
char min=''z''; // for the minimum character value, (the real minimum will never be above ASCII 254)
char med; // the mid value
CString fir; // the first half of the semi sorted string
CString sec; // the second half of the semi sorted string
CString str; // the variable to put the semi sorted string inot and sort from
int change; // to record the number of changes in the vuvle sort
char tmp; // a temporary char to store a value in for the bubble sort.
in="nbsgwkgzka"; // put something in the input string for demo purposes
len=in.GetLength(); // the assigment of the lenth (CString::GetLenth() does not include the terminating cahracter)
a=0; // set to counter to zero;
printf("the unsorted string: %s\n\n", in); // show the user what the unsorted string is.
while(a if(in[ a ] > max)
max=in
if(str[ a ]>str[ a+1 ]){
tmp=str[ a ];
str.SetAt(a, str[a+1]);
str.SetAt(a+1, tmp);
change+=1;}}
a++;}}
printf("the sorted string: %s", str); // there you''re done, str is the sorted string.
printf("\n\nPlease press any key to contine. ");
getche(); // so you can see the string before it terminates
return 0;
}
The above code was intended to sort characters, but can easily be chenged to sort numbers.
hope this helps
' Target=_Blank>Link
A while ago (i think last year) i wrote a faster version of a bubble sort. I don''t know if this is the first time that this meathod has been done or if it is the fastest possible, but here it is:
// FstSort.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "FstSort.h"
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif
/////////////////////////////////////////////////////////////////////////////
// The one and only application object
CWinApp theApp;
using namespace std;
#include
#include
#include
int _tmain(int argc, TCHAR* argv[], TCHAR* envp[])
{
CString in; //the input string to be sorted
int len; // a variable to store the lenth of the input in
int a; // for a counter
char max; // for the maximum character value
char min=''z''; // for the minimum character value, (the real minimum will never be above ASCII 254)
char med; // the mid value
CString fir; // the first half of the semi sorted string
CString sec; // the second half of the semi sorted string
CString str; // the variable to put the semi sorted string inot and sort from
int change; // to record the number of changes in the vuvle sort
char tmp; // a temporary char to store a value in for the bubble sort.
in="nbsgwkgzka"; // put something in the input string for demo purposes
len=in.GetLength(); // the assigment of the lenth (CString::GetLenth() does not include the terminating cahracter)
a=0; // set to counter to zero;
printf("the unsorted string: %s\n\n", in); // show the user what the unsorted string is.
while(a
max=in
if(str[ a ]>str[ a+1 ]){
tmp=str[ a ];
str.SetAt(a, str[a+1]);
str.SetAt(a+1, tmp);
change+=1;}}
a++;}}
printf("the sorted string: %s", str); // there you''re done, str is the sorted string.
printf("\n\nPlease press any key to contine. ");
getche(); // so you can see the string before it terminates
return 0;
}
The above code was intended to sort characters, but can easily be chenged to sort numbers.
hope this helps
' Target=_Blank>Link
March 28, 2001 03:54 PM
what kind of sort was he using in java? One he wrote himself or one that was part of the api? If it was part of the api and did not require the use of objects of type comparable then it most likely wasn''t running java, but instead was secretly running native code, which I think is basically assembly or C.
However the whole issue isn''t significant. Java and C are both plenty fast for most game logic. Java has the clear advantage in that is is more readable and being object oriented, though sometimes it will limit you. Where speed is a concern, in graphics for example, Java will be outperformed by C.
However the whole issue isn''t significant. Java and C are both plenty fast for most game logic. Java has the clear advantage in that is is more readable and being object oriented, though sometimes it will limit you. Where speed is a concern, in graphics for example, Java will be outperformed by C.
March 28, 2001 03:59 PM
hey wing, you might want to try looking at the shell sort, it is an improved version of the selection sort, which is very similar to the bubble sort. You seem to be breaking your array into two halves, first and last right? (sorry don''t have time to read in detail). Instead mix them, so that the first is all the odd and the last is all the even. Sort them with a bubble or a selection sort. Then sort the elements again. Instead of breaking them into half though you might want to use a bigger number, like 5 or 13. Then each time cut the number in half and sort again. Try to sort by prime numbers not by powers of 2, it makes it work better.
250
March 28, 2001 04:43 PM
Couple of points:
- C and C++ are compiled languages. Java is an interpretted language. It is possible for Java to be as fast as C/C++ using the same optimization techniques. It is not possible for Java to be faster. The only way this would be possible is if Java compilers were somehow better than C or C++ compilers. They are not; the same optimization techniques are used in both.
- The main differences between Java and C++ are (as I see it) that Java has automatic garbage collection and stricter adherence to some object oriented constructs. Garbage collection is a double-edged sword, in that it removes the ability from the programmer to customize his memory allocation and deallocation schemes, but makes it impossible to accidentally leak memory. The different ways the languages use OO is a matter of taste (IMHO).
- Objects, OOP, whatever, have absolutely nothing to do with whether a sorting algorithm will run faster in a given system. Sorting algorithms are the most classically procedural algorithm in existence.
- As a side note, "quicksort" is the best all-around sorting method. Bubble-sort (aka insertion sort) is among the worst. Regardless it should be fair to compare one method of sorting on one system to the same method on another, especially since you use the same number pattern for both.
- If your times came out to be so radically different, I would suggest that the Java implementation does not match the C implementation: either a different number of points are used, a better algorithm is used (such as quicksort), or the order of the number to sort is different. The machines should also be exactly the same. You must compare apples to apples (no pun on choice of platform intended).
- This may be flame-bait, but....
From the 45 applicants I''ve interviewed over the last six months, those that listed Java as their strongest language showed the poorest problem-solving skills. Those that listed C showed the best. This is by no means scientific, but I did have a fairly large sampling segment.
If your friend is so pro-Java, he should have no problem finding employment in front-end database work or web design. However, if he would like to do any other kind of programming work at all, it would be in his best interest to find some additional languages in which to excel.
As a final note, I am not a Java-basher. Really. The truth behind the language is that it has grown from C++, and its language, libraries and many of its compilers are based on C++ predecessors. But Java knowingly sacrifices speed of execution for memory safety and platform independence at the binary level. It has a specific place in the industry, mostly internet-related and other cross-platform applications, but can be slower than its C++ dual. To argue otherwise is just silly.
- C and C++ are compiled languages. Java is an interpretted language. It is possible for Java to be as fast as C/C++ using the same optimization techniques. It is not possible for Java to be faster. The only way this would be possible is if Java compilers were somehow better than C or C++ compilers. They are not; the same optimization techniques are used in both.
- The main differences between Java and C++ are (as I see it) that Java has automatic garbage collection and stricter adherence to some object oriented constructs. Garbage collection is a double-edged sword, in that it removes the ability from the programmer to customize his memory allocation and deallocation schemes, but makes it impossible to accidentally leak memory. The different ways the languages use OO is a matter of taste (IMHO).
- Objects, OOP, whatever, have absolutely nothing to do with whether a sorting algorithm will run faster in a given system. Sorting algorithms are the most classically procedural algorithm in existence.
- As a side note, "quicksort" is the best all-around sorting method. Bubble-sort (aka insertion sort) is among the worst. Regardless it should be fair to compare one method of sorting on one system to the same method on another, especially since you use the same number pattern for both.
- If your times came out to be so radically different, I would suggest that the Java implementation does not match the C implementation: either a different number of points are used, a better algorithm is used (such as quicksort), or the order of the number to sort is different. The machines should also be exactly the same. You must compare apples to apples (no pun on choice of platform intended).
- This may be flame-bait, but....
From the 45 applicants I''ve interviewed over the last six months, those that listed Java as their strongest language showed the poorest problem-solving skills. Those that listed C showed the best. This is by no means scientific, but I did have a fairly large sampling segment.
If your friend is so pro-Java, he should have no problem finding employment in front-end database work or web design. However, if he would like to do any other kind of programming work at all, it would be in his best interest to find some additional languages in which to excel.
As a final note, I am not a Java-basher. Really. The truth behind the language is that it has grown from C++, and its language, libraries and many of its compilers are based on C++ predecessors. But Java knowingly sacrifices speed of execution for memory safety and platform independence at the binary level. It has a specific place in the industry, mostly internet-related and other cross-platform applications, but can be slower than its C++ dual. To argue otherwise is just silly.
226
March 30, 2001 11:03 AM
Took the words right out of my mouth (except I haven''t interviewed anybody recently and I doubt I will anytime soon 
), just one point: insertion sort != bubble sort.
Harry.
), just one point: insertion sort != bubble sort. Harry.
Harry.
122
March 30, 2001 11:16 AM
Point:
> Bubble-sort (aka insertion sort)
Wrong! Bubble Sort is not insertion sort. There are several important differences between sort bubble sort and insertion sort. Look on my website for the main differences.
Stay Lucky, Graham "Mournblade" Reeds,
ICQ: 30514803
http://homepage.dtn.ntl.com/grahamr
> Bubble-sort (aka insertion sort)
Wrong! Bubble Sort is not insertion sort. There are several important differences between sort bubble sort and insertion sort. Look on my website for the main differences.
Stay Lucky, Graham "Mournblade" Reeds,
ICQ: 30514803
http://homepage.dtn.ntl.com/grahamr
Stay Lucky, Graham "Mournblade" Reeds,ICQ: 30514803http://homepage.dtn.ntl.com/grahamr/
250
March 30, 2001 12:46 PM
My apologies, insertion sort != bubble sort.
Another thought I had on why the original poster might have had such a discrepancy: perhaps you compiled the C++ version of the program in Debug mode,i.e. with optimizations disabled? Make sure your program compiles with the flag "optimize for speed".
Another thought I had on why the original poster might have had such a discrepancy: perhaps you compiled the C++ version of the program in Debug mode,i.e. with optimizations disabled? Make sure your program compiles with the flag "optimize for speed".
March 30, 2001 04:13 PM
Ok, before I reply to the specific post, let me just say that I
was sort of involved in this test. Not in writing the source code, but in the argument that caused it to be written.
The idea was not to proove that Java was faster than C. The goal was to prove that all those people who keep saying "Java is dog slow, it can''t be used for any real apps.", or variations thereof, are just plain wrong and haven''t got a clue what they are talking about.
The test here simply shows that primitive operations are as fast in Java as in C (with variation), given the right VM.
Now for my reply to a specific post above:
This is untrue. The advantage static compiles have over JITs (or varies mixed mode engines) is that they can spend a lot of time on optimzation, because compilation time is not much of an issue when you''re doing your final build and need as much speed as possible.
However, a good VM will over time re-optimize certain section heavily so that the difference isn''t that great. And in any case, in Java and similar languages, the bottleneck isn''t fiddling with the instruction for a for loop, but to optimize method invokations.
Here''s where runtime compilation can beat static compilation (even if it doesn''t except in some cases *today*). During runtime an advanced VM can inline certain parts of code dynamically although it couldn''t be inlined statically (methods can be overrirden in Java, unless they are declared to be final). There was a good review on Ace Hardware that compared various C compilers with Java. On one test, Java absolutely *owned*, supposedly because of heavy recursive inlining.
In any case; theoretically dynamic compilation can do more because it knows more about it''s environment. It can optimize based on CPU, based on the number of CPUs, based on available memory, or based on other things in the context.
Here I''d like to add that a GC isn''t just about not getting segfaults (although it makes everything *ALOT* easier when you get a NullPointerException + a stack trace instead of segfault). Not having to manually free memory means that as a programmer, you don''t even have to know when you *would* have done so. Many design patterns and general types of program structure is made possible with ease thanks to garbage collectors. As I like to put it, it''s not just about being too lazy to type "delete myObject;".
For an example of an extremely ellegant language that would be made impossible without a GC, look at Smalltalk. The combination of it being 100% OO, reflective, and GC based makes for extremely expressive, short and flexible code.
[quote[
- Objects, OOP, whatever, have absolutely nothing to do with whether a sorting algorithm will run faster in a given system. Sorting algorithms are the most classically procedural algorithm in existence.
OO designs are often used to create abstraction layers for this kind of thing. So yes, OOP is relevant in the real world, except if you''re writing a very specific sorter for a very specific type of data.
Untrue. The test was completely fair. And I am getting tired of people having difficulty grasping the concept that Java isn''t always beaten down by C. People usually accuse me of rigging the tests when I proove them wrong.
I''m not surprised. Given the way schools seem to throw a bunch of applet problems at studens who haven''t got a clue what a method is, and how they tend to not deal with object oriented design methologies and so on - no wonder. I''ve encountered plenty of people who honestly didn''t know what they were doing. AND they were getting paid for it.
It''s easier to start off with Java. You can write down some junk from a book and get a nifty application (or applet) and so on. It''s easy to get in over your head before grasping the basic concepts.
That however, is not the fault of the language itself.
[quote[
As a final note, I am not a Java-basher. Really. The truth behind the language is that it has grown from C++, and its language, libraries and many of its compilers are based on C++ predecessors. But Java knowingly sacrifices speed of execution for memory safety and platform independence at the binary level. It has a specific place in the industry, mostly internet-related and other cross-platform applications, but can be slower than its C++ dual. To argue otherwise is just silly.
To argue that is *has* to be slower than C++ is equially silly however (not that you did; but I wanted to point that out).
And I also believe that the future of computing lies in dynamic languaes like Java, Smalltalk, and so on - and not in giving clients big fat chunks of machine code.
was sort of involved in this test. Not in writing the source code, but in the argument that caused it to be written.
The idea was not to proove that Java was faster than C. The goal was to prove that all those people who keep saying "Java is dog slow, it can''t be used for any real apps.", or variations thereof, are just plain wrong and haven''t got a clue what they are talking about.
The test here simply shows that primitive operations are as fast in Java as in C (with variation), given the right VM.
Now for my reply to a specific post above:
quote:
Original post by Stoffel
Couple of points:
- C and C++ are compiled languages. Java is an interpretted language. It is possible for Java to be as fast as C/C++ using the same optimization techniques. It is not possible for Java to be faster. The only way this would be possible is if Java compilers were somehow better than C or C++ compilers. They are not; the same optimization techniques are used in both.
This is untrue. The advantage static compiles have over JITs (or varies mixed mode engines) is that they can spend a lot of time on optimzation, because compilation time is not much of an issue when you''re doing your final build and need as much speed as possible.
However, a good VM will over time re-optimize certain section heavily so that the difference isn''t that great. And in any case, in Java and similar languages, the bottleneck isn''t fiddling with the instruction for a for loop, but to optimize method invokations.
Here''s where runtime compilation can beat static compilation (even if it doesn''t except in some cases *today*). During runtime an advanced VM can inline certain parts of code dynamically although it couldn''t be inlined statically (methods can be overrirden in Java, unless they are declared to be final). There was a good review on Ace Hardware that compared various C compilers with Java. On one test, Java absolutely *owned*, supposedly because of heavy recursive inlining.
In any case; theoretically dynamic compilation can do more because it knows more about it''s environment. It can optimize based on CPU, based on the number of CPUs, based on available memory, or based on other things in the context.
quote:
- The main differences between Java and C++ are (as I see it) that Java has automatic garbage collection and stricter adherence to some object oriented constructs. Garbage collection is a double-edged sword, in that it removes the ability from the programmer to customize his memory allocation and deallocation schemes, but makes it impossible to accidentally leak memory. The different ways the languages use OO is a matter of taste (IMHO).
Here I''d like to add that a GC isn''t just about not getting segfaults (although it makes everything *ALOT* easier when you get a NullPointerException + a stack trace instead of segfault). Not having to manually free memory means that as a programmer, you don''t even have to know when you *would* have done so. Many design patterns and general types of program structure is made possible with ease thanks to garbage collectors. As I like to put it, it''s not just about being too lazy to type "delete myObject;".
For an example of an extremely ellegant language that would be made impossible without a GC, look at Smalltalk. The combination of it being 100% OO, reflective, and GC based makes for extremely expressive, short and flexible code.
[quote[
- Objects, OOP, whatever, have absolutely nothing to do with whether a sorting algorithm will run faster in a given system. Sorting algorithms are the most classically procedural algorithm in existence.
OO designs are often used to create abstraction layers for this kind of thing. So yes, OOP is relevant in the real world, except if you''re writing a very specific sorter for a very specific type of data.
quote:
- If your times came out to be so radically different, I would suggest that the Java implementation does not match the C implementation: either a different number of points are used, a better algorithm is used (such as quicksort), or the order of the number to sort is different. The machines should also be exactly the same. You must compare apples to apples (no pun on choice of platform intended).
Untrue. The test was completely fair. And I am getting tired of people having difficulty grasping the concept that Java isn''t always beaten down by C. People usually accuse me of rigging the tests when I proove them wrong.
quote:
- This may be flame-bait, but....
From the 45 applicants I''ve interviewed over the last six months, those that listed Java as their strongest language showed the poorest problem-solving skills. Those that listed C showed the best. This is by no means scientific, but I did have a fairly large sampling segment.
I''m not surprised. Given the way schools seem to throw a bunch of applet problems at studens who haven''t got a clue what a method is, and how they tend to not deal with object oriented design methologies and so on - no wonder. I''ve encountered plenty of people who honestly didn''t know what they were doing. AND they were getting paid for it.
It''s easier to start off with Java. You can write down some junk from a book and get a nifty application (or applet) and so on. It''s easy to get in over your head before grasping the basic concepts.
That however, is not the fault of the language itself.
[quote[
As a final note, I am not a Java-basher. Really. The truth behind the language is that it has grown from C++, and its language, libraries and many of its compilers are based on C++ predecessors. But Java knowingly sacrifices speed of execution for memory safety and platform independence at the binary level. It has a specific place in the industry, mostly internet-related and other cross-platform applications, but can be slower than its C++ dual. To argue otherwise is just silly.
To argue that is *has* to be slower than C++ is equially silly however (not that you did; but I wanted to point that out).
And I also believe that the future of computing lies in dynamic languaes like Java, Smalltalk, and so on - and not in giving clients big fat chunks of machine code.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
Recommended Tutorials
Advertisement