Argh. Sorry about the quoting in my last reply. Some of "my" text was actually supposed to be quotes.

No, that C code was not optimal.

If you want to see about the fastest bubble sort you'll see, here's a rather fast and simple implementation of Knuth's Bubble Sort:

/* T is a typedef to basically whatever you want, but unsigned int (size_t) would be best */void sort(T* array, size_t count){ size_t i, end = count - 1, swap_idx; T temp; double start_tick; if(array == NULL || count == 0) return; do { swap_idx = 0; for(i = 0; i < end; ++i) if(array[i] > array[i + 1]) { temp = array[i]; array[i] = array[i + 1]; array[i + 1] = temp; swap_idx = i; } end = swap_idx; } while(swap_idx != 0);}

An even faster bubble sort is the bi-directional variant:

void sort(T* array, size_t count){ long i, start = 0, end = count - 1, swapped; T temp; if(array == NULL || count == 0) return; for( ; start < end; ++start, --end) { swapped = 0; for(i = start; i < end; ++i) { if(array[i] > array[i + 1]) { temp = array[i]; array[i] = array[i + 1]; array[i + 1] = temp; swapped = 1; } if(swapped == 0) return; swapped = 0; for(i = end - 1; i >= start; --i) { if(array[i] > array[i + 1]) { temp = array[i]; array[i] = array[i + 1]; array[i + 1] = temp; swapped = 1; } if(swapped == 0) return; } } // for}

Now, people damn the Bubble Sort a lot, but it has its place. For a handful of items, it kicks ass over just about anything else, particularly in the case of the Bi-Directional Bubble Sort. Also, it's important to consider that if your array has a relatively small number of items, coding the extra few lines required for a selection, insertion, or merge sort is just not worth the trouble. Finally, it's noteworthy that most of the fastest Quick Sort implementations actually use Bubble Sort of some variety when the number of items left to sort is under some amount. So, Bubble Sort has its place, just like goto; don't let anybody tell you that anything is "evil."

Edited by - merlin9x9 on March 30, 2001 5:43:19 PM

I didn''t say it was *optimal*, just that it was *fair*. The exact same code was used for the C and Java version.

***Anonymous Poster Said:***
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.


***Stoffel Said:***
- 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.


***I SAY:***
Anonymous, can''t you see ... Stoffel''s statment is about COMPILED vs. INTERPRETED languages ... and is 100% correct until you see that there are NEW software techniques being developed and used which involve DYNAMIC compilation of code. This is NOT in any way related to JAVA vs. C because it is still true that the same algorithm using the same level of compiler techniques would always be the same or faster in ASM over C and C over Java, because ALL that a computer language can do beyond ASM and C is IMPOSE RULES ... for speedier development, or less buggy code, or whatever end purpose .. in the end, all code is executed in machine language (which might as well be ASM for our purposes) ... the best a language can do is choose good ASM commands. You cannot get better performance by following OO rules, or garbage collection, or any other such artificial rules ... all optimization rules apply solely at the PROCEDURAL level .. because the chip only understands DATA and CODE.

Therefore ... the fact that IBM and other companies are using their new advanced technique in Java tools is coincedental, reflecting the direction they see as the future of their bottom lines ... DYNAMIC compilation can exist even at the OPERATING SYSTEM level and be language independent .. or even the CHIP level .. as it already does in terms of branch prediction and on chip caches.

So ... the language Java is forever doomed to have no greater performance potential than the C language ... because if the market exists (and it does) ... these cutting edge techniques will soon be standard for all important compilers in all languages. Just as there already existed even before Java garbage collection, networking, and windowing libraries in C++.

That program is no where near optimal. With my 500 Mhz CPU, I can sort 10,000 items in under 20 ms. 500Mhz = 500,000,000 "pulses" per second (in Hz). That means ~0.0001 pulses per item. This is like comparing apples to oranges. Bad code in a "faster" language isn''t going to be faster than good code in a "slower" language.

BTW: Java was written in C++, that limits its speed to what someone could write in C++. You could rewrite the Java VM in C++. Go figure.

"Finger to spiritual emptiness underlying everything." -- How a C manual referred to a "pointer to void." --Things People Said

http://druidgames.cjb.net/

Xai: I honestly don''t understand what you''re on about. Runtime compilers have more information about there current environment, and can make decisions based on it. The same optimization *CAN NOT* be done at the OS level because tot he OS the VM is just another chunk of machine code being executed. A VM can make decisions and inline code (and other things) because it''s specifically written for the bytecode format it is executing.

Stating that Java (or any other language) cannot be faster than C is just plain wrong. It depends on the level at which the CPU instructions are, the level of the byte code, and so on. For example, if the byte code is at a higher level, it may be possible to do certain optimization that are extremely hard to do otherwise, because given raw machine code you''d have to extraploate the intent of the original code by analizing the product.

Just like C can be faster than Java, Java can be faster than C.

Null and void: Why aren''t you listening? No one *SAID* it was an optimal implementation. It''s just the *SAME* implementation in both C and Java. Don''t accuse anybody of comparing apples and oragnes, when they are comparing oranges and oranges. If you used some optimized version for one language but not the other - THAT would be comparing apples and oranges.

And btw, the statement:

quote:

---

BTW: Java was written in C++, that limits its speed to what someone could write in C++. You could rewrite the Java VM in C++. Go figure.

---

Is again, false.

First of all, Java wasn''t written in *anything*. It''s a platform. JVM:s are written in languages. And there are multiple JVM:s written in multiple languages (such as IBM''s JVM, which is mostly written in Java itself, with only 1000 lines of C code - look up Jalapeno).

Secondly, just bcause the VM is written in C++, it doesn''t mean the Java code is somehow limited by the speed of that language, just like a C++ program wouldn''t be limited to the language of the JVM that ran the C++ compiler.

Modern VM:s don''t interpret Java bytecode.

And another thing:

quote:

---

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.

---

1) It was his own code. Again, the exact same code as the C one, except for the timing and the System.out.println stuff.

2) Almost all of the Java API is written in Java, not native code. In fact, Sun have been moving from native code to Java code for performance reasons due to the overheard in invoking native methods.

3) Native methods can be in any language, although javah produces C headers, so I suppose C functions are most common and easiset to use.

quote:

---

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".

---

No, it was gcc -O6. We did several comparisons. Sun''s JVM beat gcc with no optimization; IBM''s JVM just about beat gcc -O6.

Why is it so hard for you people to believe that Java was comparable to C?

Just a note; when I said "IBM''s JVM" above, I didn''t mean their production JVM, which is a Sun JVM derivative. But they do have an experimental JVM called Jalapeno, which is the one I was referring to.