Fog Creek Software
Discussion Board




C++ is faster than Java in the case of DES?

I am going to write a program cracking DES.
I have to try 2^56 possible keys.

One says that C++ (actually C) is faster than Jave.
Is this true?

Juri

Juri Yanase
Sunday, April 25, 2004

To answer your question, yes, C++ is almost always going to be faster than Java.  Java usually gets compiled to byte code, and then when it is run, your computer has to interpret the byte codes and then run the appropriate instructions.  C++ usually gets compiled directly to machine instructions, so your computer doesn't have to spend any time figuring out which instructions should be run.  There are some Java compilers are there that do native compilation, but as far as I know they're still not going to be as fast as C or C++.

Secondly, I'm not sure you realize what a big undertaking something like this is.  2^56 is a pretty big number, and even if you could check 1,000,000 keys every second, it would take you over 2000 years to check them all.

Emperor Norton
Sunday, April 25, 2004

When ever I think about these challenges it reminds me of Star Trek Voyager where a space ship is stranded very far away trying to get home. The voyager is always looking for a ways to shave a few light years off their trip. Using technical improvements and cosmic short cuts. If you are going to crunch DES (or any other interesting ciphers), you may do better getting a serious math education. That's how the NSA is hedging their bets anyway (they hire many many mathematicians and friends).

Li-fan Chen
Sunday, April 25, 2004

Actually I know the first two (of eight)  bytes of key.
So I need to try 2^42.
Also I have 20 computers ;)

Juri Yanase
Sunday, April 25, 2004

Java is faster.

No, C++ is faster.

No, Java is faster.

No, C++ is faster.

Write the damn code, run it, and find out!

Dan Maas
Sunday, April 25, 2004

Nice one Dan !

James
Sunday, April 25, 2004

Yes, I worte it with C++ and it is running. Already 3% of all work is done :)

Juri Yanase
Sunday, April 25, 2004

The fastest way to crack DES is using the "bitslice technique".  Basically, on a 32-bit machine, you store 32 keys in an array of 56 machine words, one key bit per word, and 32 keys in parallel.  Permutations are memory addressing, and the S-boxes are done using logical operations.

If you have a 64-bit CPU, you crack 64 keys at a time.

You can Google for this.  Use hand-coded assembler and schedule instructions correctly for your processor. With care, you can max out the instruction execution rate.

David Jones
Sunday, April 25, 2004

C is faster than Java in the case of EVERYTHING.

And smaller.

And (with the exception of external interfaces) more portable.

Java is a fraud on the IT industry.

HeWhoMustBeConfused
Sunday, April 25, 2004

"C is faster than Java in the case of EVERYTHING."

Everything - Hehehehe - your funny.

James
Monday, April 26, 2004

Assembler is smaller and faster than "C" so "C" must be a a fraud on the IT industry.

James
Monday, April 26, 2004

Assembler is (by definition) not portable.

Almost Anonymous
Monday, April 26, 2004

>"C is faster than Java in the case of EVERYTHING."

With the exception of development time I guess...

Patrik
Monday, April 26, 2004

You would have to be an absolute wizard to write better Assembler code than what a modern C++ compiler does.

Ignorant youth
Monday, April 26, 2004

You think?
Compilers generate code that will work as a best fit, this is after all the analysis which gives the structure of the code, yes there are assembly specific optimisations on particular instruction sets which can be used by compilers, but then those same optimisations can be used by people.

Depending on the size of the algorithm someone with a good knowledge of the assembler, the processor its implemented on, the supporting architecture both electronic and software would likely produce an optimal piece of code.

Simon Lucy
Monday, April 26, 2004

get code from http://www.distributed.net/source/ and compare.

Just me (Sir to you)
Monday, April 26, 2004

>optimisations [..] can be used by compilers, but then those same optimisations can be used by people.

This is basically untrue with modern compilers (and modern programmers ;-)). According to a book I read, most of the time a decent compiler outperform humans on optimizing code. Handwritten assembly is inefficient when run on modern CPUs.

Take the SPARC for example, it has delayed jumps, which means it performs the instruction after the jump before jumping. That leads to people  placing NOP after jumps. You could have that instruction do something useful, however you run the risk of messing up something for your routine that is getting jumped to.

Most modern processors have hardware tricks like this that is at best difficult to optimize for.

Ofcourse you can handwrite the same code, but the guys writing compilers usually know more about the low level processor specifics than your average assembly programmer guy.

Patrik
Monday, April 26, 2004

Forgot to add the book I refferred to:

http://www.amazon.com/exec/obidos/tg/detail/-/1558604286/002-9514046-1033656?v=glance

Computer Organization and Design : The Hardware/Software Interface

Patrik
Monday, April 26, 2004

If you had to write your whole program in assembly, the compiler wuold probably do a better job every single time.

But you don't have to do that. You only have to write the few crtitical inner loops in assembly.

In this case, the human will always at least break even, if not win every time. The reason being that the human can always start with the compiler generated code for the critical sections and work on improving it.

Sum Dum Gai
Monday, April 26, 2004

Simon, I agree with your premise that a human can do just as well as a compiler, after all, the compiler was written by humans.

But personally I don't consider myself capable of ingesting and memorizing the hundreds of pages of optimization guidelines for today's CPUs.

Lots of smart people with good memory have worked years to put that knowledge into their compilers, I'm not going to presume to beat that with just my one brain.

Yes, I was as assembly buff in high school, when shl ax, 2 was considered "a neat trick", but today that same trick actually slows down a P4.

Ignorant youth
Monday, April 26, 2004

"You would have to be an absolute wizard to write better Assembler code than what a modern C++ compiler does. "

I think many encryption algorithms are faster in assembler because C++ does not support a rotate operation, just a shift.  I think Java DOES support a rotate operation, but I don't know whether there are cases where java outperforms C++ on certain encryption algorithms.  I have no idea if DES is one of the algorithms that performs much better with a rotate.  C++ may be considered close to the metal, but it does neglect several aspects of assembly language, such as being able to use the carry flag, or getting the high word of a multiplication of two words.  Optimizing compilers probably manage to use some features, but they are only capable of so much.

My point is that encryption algorithms are exactly the type of thing you would want to try hand optimizing in assembly, should the encryption speed be a serious bottleneck.  (though why do it yourself, the encryption algorithms seem to be available in every major language, and several assemblers)

Keith Wright
Monday, April 26, 2004

I agree with Sum Dum Gai - most people don't hand write entire programs in assembly.  Typically, it's better to hand optimize the parts that need it.

In that case humans can often do better.  I remember getting a 36x speedup in section of code by doing extensive loop unrolling; another time I got a 9x speedup  for large array handling by using blocking.

You're probably not going to do as well as the compiler when it comes to handling structural, data, and control hazards (e.g., filling branch delay slots as Patrik mentioned).

But there are some optimization blockers inherent in code that a person can handle better because the compiler has to make certain assumptions.  For example, can you replace 2 calls to int foo() with 2 * foo()?  The compiler won't because foo() might have side effects.  Another optimization blocker is pointers.  If you have *a and *b, the compiler can't make certain optimizations because *a and *b may be pointing to the same memory space, whereas the programmer may know that they won't.

yet another anon
Monday, April 26, 2004

Oh, ok. So, I can't right?
Well, I bet them NAZIS used to optimize their assembler by hand. There is no historical reference to it, but them being NAZIS, you know, they look like the type of people who would do that.

I mean, they're NAZIS....

Someone Who Posts Here a Lot
Monday, April 26, 2004

Keith -- true. Try shifting a 64-bit integer in C. :)
(or a 128-bit on a 64-bit machine).

Ignorant youth
Monday, April 26, 2004

Actually, the NAZIs used SALAD CREAM. That's what speeds you up: NAZI SALAD CREAM!

.
Monday, April 26, 2004

Actually, the Nazis weren't very good at encryption.  The British Typex and the American SIGABA were much better encryption / decryption devices than the German Enigma.

An old, but good book I read ~20 years ago on the history of the NSA is "The Puzzle Palace" ( http://www.amazon.com/exec/obidos/tg/detail/-/0140067485/002-9768621-2598407?v=glance ) if anyone's interested.

This has nothing to do with assembly, of course, but I'm just fighting the "evil doers" who try to end threads by injecting the words NAZI and SALAD CREAM.

yet another anon
Monday, April 26, 2004

Since what you are doing is so compute intensive maybe this will help...

http://osnews.com/story.php?news_id=5602&page=3

Code Monkey
Monday, April 26, 2004

I thought with the Nazi's, the encryption was quite clever, but they misused the machines such as to enable their cracking, and we had some damn good mathematicians on the job.  The russians made some similar screw ups, for instance using one-time pads more than one time (because they ran out!).

Keith Wright
Monday, April 26, 2004

Yeah, I worded that poorly. It's kind of like saying such-and-such NBA player sucks - even though there's only ~300 men in the world good enough to be NBA players out of the ~3 billion men in the world.

So, theirs was good, but our was better from what I recall.

yet another anon
Monday, April 26, 2004

Code Monkey: Wow, Java is faster than C++ there...

Ignorant youth
Monday, April 26, 2004

I have written entire programs in assembler
I have written entire programs in 'C'
I have written entire programs in 'Java'

Horses for courses, but dont tell me that a 'C' compiler can generate better assembler than a human. Thats nonsense.
If you believe that, then post to http://www.masmforum.com/
and see the response you get from the experts !

James
Monday, April 26, 2004

Ignorant Youth wrote:

>Code Monkey: Wow, Java is faster than C++ there...

Yep. If you do not consider trig math where Java does horribly Java 1.4.2 runs actually neck to neck with the best of them all Visual C++.  In cases like I/O it is actually faster than C++.

With the new java release I am sure the times will be even more closely matched.

Code Monkey
Tuesday, April 27, 2004

I suppose it's a case of the JIT compiler doing better than the C++ compiler.

Ignorant youth
Wednesday, April 28, 2004

Anyone claiming that compilers are better than humans at writing "code" might like to look at http://www.azillionmonkeys.com/qed/asmexample.html


Friday, April 30, 2004

*  Recent Topics

*  Fog Creek Home