Cracking DES with C++ is faster than Java?

[Julie]

[ ... ]

Review:

http://page.mi.fu-berlin.de/~prechelt/Biblio/jccpprt_computer2000.pdf

IMO, basing any decision about DES on this paper is a mistake.

Just posting information that is based on an empirical study. Looking over the
other respondents to this thread, I see a lot of anecdotal, conjecture, and
off-topic posts (I'm not excluding myself from that either).

Personally, I'd view this paper as more evidential (in general terms) about the
various performance characteristics between languages.

Naturally, the OP should use whatever language is appropriate depending on the
explicit formula for the attack.

 

[Douglas A. Gwyn]

... FWIW, my comments are based on the *conceptual* idea of
superset/subset.

As opposed to an *accurate* idea of superset/subset?

 

[Dez Akin]

Dez Akin wrote:
[snip]

Optimizers are getting smarter though, and I suspect in not too many
years it will be a waste of time to attempt to out-do the optimizer.
In a couple of decades at the most I suspect it will be impossible for
any human to outperform an optimizer. (Massalin's superoptimizer led
to Denali, which I imagine will lead to more generic optimal code
approximators)

I don't buy that.

If processing unit architecture stayed the same during that time, then you
would have an argument.

However, each time a processor is revved, new features, behaviors, opcodes,
etc. are added. At that point, the compiler writer must then decide on what
feature to incorporate, if at all, let alone optimizations.

Optimizing compiler technology has been relentlessly advancing for
years. Its much more difficult now to out do the optimizer at
'ordinary' control flow code than a decade or two ago. When you have
assembly implementations that are faster, they often take advantage of
processor supported operations that are supported only by rather
specialized algorithms (crypto and bignum math being rather notable
here)

Also with superoptimizer techniques, you can define the entirety of
the cpu machine model in a logical modeler that selects the actual
optimal instruction sequence for some metric (size, speed, cache
coherency) so long as the length of the code for the function being
generated is 'small' given that this is reducable to satisfiability
solving, which is NP complete. (see the paper on the Denali
superoptimizer)

And for larger pieces of code, its possible for the compiler to do
data dependency analysis to find easily parallelizable pieces of code.

We're getting better at abstracting processors in general, and
translating that to optimizing compilers. I expect we'll eventually
(20-30 years) have back-end optimizer generators from abstract
processor architecture descriptions that automatically generate
optimizers.

It will always be possible to out-do the optimizer, however the value of such
has been steadily decreasing as processor speeds have increased.

People said the same thing about chess. Don't expect people to have
the edge in the future just because we've done allright untill now.

 

[Julie]

Dez Akin wrote:
[snip]

People said the same thing about chess. Don't expect people to have
the edge in the future just because we've done allright untill now.

Yes, but the rules of chess have stayed the same.

Chip rules haven't, and won't.

I think that increases in speed will mitigate the need for most optimizations,
so my feeling is that hand optimization will die mainly due to lack of need,
rather than lack of ability.

 

[Phil Carmody]

TC++PL, Bjarne Stroustrup, Appendix
B.2 C/C++ Compatibility
With minor exceptions, C++ is a superset of C. ....
[summarising:]
Bjarne: "C++ is a superset of C"

Bzzzt!

Bjarne ~ C++ is not a superset of C due to the exceptions.



Would you agree with
"Except for the number 2, all primes are odd"
?

Would you agree with
"All primes are odd"
?


Do you see your mistake now?

Phil

 

[Claudio Puviani]

Dez Akin wrote:
[snip]

People said the same thing about chess. Don't expect people to have
the edge in the future just because we've done allright untill now.

Yes, but the rules of chess have stayed the same.

Chip rules haven't, and won't.

I think that increases in speed will mitigate the need for most optimizations,
so my feeling is that hand optimization will die mainly due to lack of need,
rather than lack of ability.

That naively fallacious argument has existed since the early days of computers,
and it's usually uttered by academics who have little contact with the real
world. No matter how fast a computer is, there will always be problems that take
extremely long to process and the volume of operations that need to be done per
unit time is growing faster than the hardware can keep up. A compiler that
performs worse optimizations (let alone none at all) will not be competitive with
one that performs better ones. Certainly, a company that uses slower code will be
at a disadvantage with respect to one that strives for efficiency. You can't
think in absolutes; it's relative performance that matters.

Claudio Puviani

 

[Julie]

Dez Akin wrote:
[snip]

It will always be possible to out-do the optimizer, however the value of such
has been steadily decreasing as processor speeds have increased.

People said the same thing about chess. Don't expect people to have
the edge in the future just because we've done allright untill now.

Yes, but the rules of chess have stayed the same.

Chip rules haven't, and won't.

I think that increases in speed will mitigate the need for most optimizations,
so my feeling is that hand optimization will die mainly due to lack of need,
rather than lack of ability.

That naively fallacious argument has existed since the early days of computers,
and it's usually uttered by academics who have little contact with the real
world. No matter how fast a computer is, there will always be problems that take
extremely long to process and the volume of operations that need to be done per
unit time is growing faster than the hardware can keep up. A compiler that
performs worse optimizations (let alone none at all) will not be competitive with
one that performs better ones. Certainly, a company that uses slower code will be
at a disadvantage with respect to one that strives for efficiency. You can't
think in absolutes; it's relative performance that matters.

Claudio Puviani

Claudio, please follow the context of the thread before making such responses.

The topic of discussion relates to HAND-OPTIMIZED ASSEMBLY, not optimizations
in general.

My feeling is that the need for hand-optimized assembly will diminish over time
as baseline performance increases over that same period of time. That is what
I was communicating, nothing more, nothing less.

 

[Claudio Puviani]

"Julie":

"Claudio":
"Julie":
Claudio, please follow the context of the thread before making such responses.

The topic of discussion relates to HAND-OPTIMIZED ASSEMBLY, not optimizations
in general.

My feeling is that the need for hand-optimized assembly will diminish over time
as baseline performance increases over that same period of time. That is what
I was communicating, nothing more, nothing less.

I apologize if I misinterpreted your intent, but even in context, the statement,
"I think that increases in speed will mitigate the need for most optimizations",
seemed to apply to compiler optimizations as well.

Claudio Puviani

 

[Julie]

"Julie":

I apologize if I misinterpreted your intent, but even in context, the statement,
"I think that increases in speed will mitigate the need for most optimizations",
seemed to apply to compiler optimizations as well.

Claudio Puviani

Thank you for your apology.

I entirely agree that optimization (in general terms) will always be necessary,
regardless of processing performance improvements.

 

[Jerry Coffin]

[ ... ]

Actually optimizer technology really is substantially better
these days.

Oddly enough, I quite agree.

Any such comparison needs to keep in mind that
Fortran has properties that allow tighter optimization than
is feasible for C on many platforms; for example, C pointer
parameters can alias whereas Fortran array parameters cannot
(acording to the language spec), which permits vectorization
that is not safe for C code. (We have addressed that in C99
by introducing "restrict" qualification.)

My opinions aren't based purely on looking at code produced by C
and/or C++ copmilers, but also by various other languages (including
Fortran). It's true that Fortran has changed since then as well, but
I'm not particularly convinced that the sub-optimal code is due to new
language features or anything like that.

Now, how do I, on one hand, say that the situation is worse today than
it was 20+ years ago, but also agree that optimizer technology has
gotten better during that time as well?

It's pretty simple really: optimizers have gotten better, but the
point of "optimum" has grown at a faster rate. I.e. while the code
that's produced has gotten better, the code that COULD be produced has
gotten better by an even larger margin.

Most reasonably current computers have SIMD instructions now, but very
few compilers even attempt to use them -- and those that do almost
universally produce code that's really _quite_ bad.

The result is that 20 years ago I had to plan on working fairly hard
to beat the compiler by more than 20%. Nowadays, I can frequently
just do an _obvious_ implementation, and still beat the compiler by
2:1.

Also, hardware has changed in many ways. RISC architectures
are usually harder to program optimally without machine
assistance in allocating registers, for example.

From my experience, I'd say rather the opposite: RISCy architectures
tend to have fairly large, mostly orthogonal register sets, which
makes register allocation quite easy.

The x86 (for example) makes life _substantially_ more difficult -- for
optimal usage, you often have to put initial values in non-obvious
places to produce final results where they can be used without further
movement. The floating point unit is substantially worse -- those of
us who've used HP calculcators for years do all right with it, but
others really struggle. Then again, quite a few compilers seem to
have similar problems; Borland's, for example, typically writes
intermediate values to memory far more than needed, and rarely uses
more than the top three (or so) stack locations.

 

[Jerry Coffin]

[ ... ]

Computers can access fixed locations in memory
faster that relative locations.

That's not necessarily true. In theory, it takes more work to
generate the absolute address from a relative address, but in fact
nearly all reasonably current computers have hardware dedicated to the
task.

With most modern computers, a cache miss causes a MUCH larger delay
than figuring an effective address.

Recursion requires
local variables to be stored on the stack, i.e. to
be accessed using relative locations. Data structures
on the heap are even more complicated to access.

Not so -- allocating and freeing data can be expensive, but at least
in C and C++, when you allocate memory on the heap/free store you get
the (absolute) address of the memory allocated. Once you have that,
the access is relatively direct. By contrast, access to the stack is
essentially always done relative to some register.

As noted above, however, this rarely means much. Accessing data on
the stack IS usually quite fast, but that's primarily because the page
at the top of the stack will nearly always be in the cache.

Dynamic storage is very bad, you can see the computer
stop for several thousand million clock cycles whilst the
garbage collector tries to find some more memory.

Only, for starters, when you actually use a garbage collector. Even
then, techniques to reduce waits during a collection cycle have been
well known for quite some time. I realize that many JVMs (for one
example) use GC that dates back to roughly the Lisp 1.5 era, but that
doesn't mean nothing better is known. Generataional scavenging,
incremental GC, etc., have been around for some time and can't be
summarily dismissed even for hard real-time systems.

 

[Bryan Olson]

My opinions aren't based purely on looking at code produced by C
and/or C++ copmilers, but also by various other languages (including
Fortran). It's true that Fortran has changed since then as well, but
I'm not particularly convinced that the sub-optimal code is due to new
language features or anything like that.

Now, how do I, on one hand, say that the situation is worse today than
it was 20+ years ago, but also agree that optimizer technology has
gotten better during that time as well?

Hey -- there are more important things to optimize than clock-
cycle counts. I too am old enough to have learned FORTRAN IV,
and let's not kid the kids: FORTRAN IV sucked! Wasting a few
machine cycles is one thing, but don't waste large amounts of my
time and claim to be doing me a favor.

How bad did FORTRAN IV suck? Well, my favorite example is that
a for-loop (actually a "DO" loop in FORTRAN IV) could not
execute its body zero times. Even if the condition was false at
the start, it would go through at least once. Is that as
awkward as it sounds? Absolutely! Why did they do it? Well,
the way most machine instruction sets work, one can save a cycle
or two by testing the condition at the end of the loop, and
using a conditional jump backwards.

We have much more *efficient* languages today. C and C++ are
far from top of the list. Java doesn't crash, but it's still
notably primitive. My hope for the future is with elegant,
polymorphic-type-safe languages, such as the ML family, or
perhaps even more purely functional languages such as Haskell.
They have yet to make a commercial splash comparable to C/C++ or
Java, but when tested in coding-competition, they romp.

In my own grad-school work with ML, I fought long and hard with
the type-checker. I could take an hour or more just to several
dozen lines of my code to compile. Still, I like ML; when
programs did compile, they worked. Logic errors are, or course,
still possible, and I cannot be certain my programs were
entirely correct. Nevertheless, I'm impressed: in about a year
of using ML, *every* known error in my code was caught at
compile-time.

 

[Andrew Swallow]

[snip]

Only, for starters, when you actually use a garbage collector. Even
then, techniques to reduce waits during a collection cycle have been
well known for quite some time. I realize that many JVMs (for one
example) use GC that dates back to roughly the Lisp 1.5 era, but that
doesn't mean nothing better is known. Generataional scavenging,
incremental GC, etc., have been around for some time and can't be
summarily dismissed even for hard real-time systems.

Stick to constructions that always produce the same
results given the same inputs. Designs that fail x%
of the time fail x% of the time.

Andrew Swallow

 

[Jerry Coffin]

[ ... ]

Hey -- there are more important things to optimize than clock-
cycle counts. I too am old enough to have learned FORTRAN IV,
and let's not kid the kids: FORTRAN IV sucked! Wasting a few
machine cycles is one thing, but don't waste large amounts of my
time and claim to be doing me a favor.

This was posted as a follow-up to my article, but seems to have been
based on entirely ignoring everything I wrote.

I have not at any point advocated Fortran as a cure for anything (at
least not in the last 20 years). While others in the thread have
claimed that if Fortran IV was still in use that optimization would be
improved, I have NOT done so, and in fact have specifically stated
that I believe this to be mostly wrong.

I've also stated that even though hand optimization makes a greater
difference percentage-wise than it did back then, that I no longer do
so nearly as often as I did then. I would have thought that made it
fairly obvious that I consider it less important than I did then.

How bad did FORTRAN IV suck? Well, my favorite example is that
a for-loop (actually a "DO" loop in FORTRAN IV) could not
execute its body zero times. Even if the condition was false at
the start, it would go through at least once. Is that as
awkward as it sounds? Absolutely! Why did they do it? Well,
the way most machine instruction sets work, one can save a cycle
or two by testing the condition at the end of the loop, and
using a conditional jump backwards.

IMO, in the pantheon of Fortran's shortcomings, this is one of the
lesser evils. Nonetheless, since I haven't advocated Fortran, arguing
against it is irrelevant.

We have much more *efficient* languages today. C and C++ are
far from top of the list. Java doesn't crash, but it's still
notably primitive. My hope for the future is with elegant,
polymorphic-type-safe languages, such as the ML family, or
perhaps even more purely functional languages such as Haskell.
They have yet to make a commercial splash comparable to C/C++ or
Java, but when tested in coding-competition, they romp.

I'd class functional programming right along with the verification it
enables: it's the future of programming; always has been and always
will be.

Seriously, while I _like_ a number of functional languages quite a
lot, none of them I've used yet really works particularly well for
most of the real work I do. Then again, I largely do system
programming, rather than typical applications.

Perhaps we're finally reaching the point at which the programming
world will start to recognize that there are differences between
system programming and application programming, and using system
programming languages like C and C++ for application programming isn't
particularly productive. To a limited extent that's already happened,
but it's still done on a regularly basis anyway.

Truthfully, I'm as much a culprit in this respect as anybody -- for
anything but a truly colossal task, my familiarity with C++ tends to
outweigh the advantages of other languages, I typically use it even in
situations where another language would provide some advantages.

Then again, C++ does have one advantage in this respect: it supports
enough different levels of abstraction that it can be used right down
to the metal, or in a fairly safe, high-level manner, and perhaps most
importantly, more or less seamlessly marrying the two, so even in my
system programming, much of what I write works at a fairly high level
of abstraction.

In my own grad-school work with ML, I fought long and hard with
the type-checker. I could take an hour or more just to several
dozen lines of my code to compile. Still, I like ML; when
programs did compile, they worked. Logic errors are, or course,
still possible, and I cannot be certain my programs were
entirely correct. Nevertheless, I'm impressed: in about a year
of using ML, *every* known error in my code was caught at
compile-time.

I'm afraid my experience with functional programming hasn't been quite
so positive. In the end, I think even if functional programming did
provide huge benefits, it _probably_ wouldn't take over any time soon
anyway.

I suspect that the majority of code in the world today is still
written in COBOL and Fortran, and if we can't even get the world
beyond them, the possibility of functional programming becoming
mainstream anytime soon seems remote indeed.

 

[Paul Schlyter]

I'd class functional programming right along with the verification it
enables: it's the future of programming; always has been and always
will be.

You're really saying here that you believe functional programming
always will be mostly just a vision and never will become mainstream
programming languages. Because if they would become mainstream
languages they'll switch from "the future of programming" to "the
present of programming", and you believe that will never happen.

Then again, C++ does have one advantage in this respect: it supports
enough different levels of abstraction that it can be used right down
to the metal, or in a fairly safe, high-level manner, and perhaps most
importantly, more or less seamlessly marrying the two, so even in my
system programming, much of what I write works at a fairly high level
of abstraction.

The disadvantage of using C++ at a high abstraction level is that
there are so many ways to do that -- it depends on which class or
template library you choose to use (or which one others have chosen
for you; sometimes you don't have a choice). If you instead use a
genuinely high-level language, there's only one way to learn how to
use that.

I suspect that the majority of code in the world today is still
written in COBOL and Fortran, and if we can't even get the world
beyond them, the possibility of functional programming becoming
mainstream anytime soon seems remote indeed.

The reason COBOL is still used is that there is so much COBOL code
out there which still runs, and it would just take too much time to
rewrite all that code in some other language. Thus the classic "keep
backwards compatiblity or throw away all that's old and redo
everything from scratch" problem).

The reason Fortran (now FORTRAN IV though, but a mixture of
Fortran-77 and Fortran-90/95) is still used is that it's still the
most machine efficient language for heavy number crunching problems.
While this won't matter much to software which have modest demands
for CPU cycles, it matters a lot if you're doing stuff like wind
tunnel simulations or numerical weather predictions. BTW Fortran as
a languare has evolved too, and Fortran-90/95 is a language very
different from FORTRAN IV - but it still focuses on generating
efficient code, and the language is designed such that aliasing
issues (which are so common in C and C++ and which makes optimization
of generated machine code much harder) does not exist in that
language.

There will always be several different languages, each one best for
one particular type of problem and none best for any kind of problem.

--

 

[Mok-Kong Shen]

Paul Schlyter wrote:
[snip]

BTW Fortran as
a languare has evolved too, and Fortran-90/95 is a language very
different from FORTRAN IV - but it still focuses on generating
efficient code, and the language is designed such that aliasing
issues (which are so common in C and C++ and which makes optimization
of generated machine code much harder) does not exist in that
language.

Sorry for a question of ignorance. What are the 'aliasing issues'
that exist in C and C++ but don't exist in Fortran? Thanks.

M. K. Shen

 

[Douglas A. Gwyn]

Sorry for a question of ignorance. What are the 'aliasing issues'
that exist in C and C++ but don't exist in Fortran? Thanks.

void f(int *a, int *b) {
*a = 42;
*b = 0;
if (*a == 42) // cannot assume this is true
*b = 1;
}

 

[Jerry Coffin]

(e-mail address removed) (Paul Schlyter) wrote in message
[ ... ]

You're really saying here that you believe functional programming
always will be mostly just a vision and never will become mainstream
programming languages.

Yup -- but my phrasing was more fun.

The disadvantage of using C++ at a high abstraction level is that
there are so many ways to do that -- it depends on which class or
template library you choose to use (or which one others have chosen
for you; sometimes you don't have a choice). If you instead use a
genuinely high-level language, there's only one way to learn how to
use that.

Either of these can be viewed as either an advantage or a
disadvantage.

[ ... ]

The reason COBOL is still used

[ ... ]

Anything that starts this way, assuming that there's only one reason
COBOL is still used, is guaranteed to be wrong. There are quite a few
reasons that COBOL is used, and likewise with Fortran.

[ ... ]

There will always be several different languages, each one best for
one particular type of problem and none best for any kind of problem.

I doubt that sentence is saying what you really intended -- I suspect
you intended to say something more like "each one best for one
particular kind of problem and none best for all kinds of problems."

In any case, we're wondering far afield from the original question.
At least personally I'm not particularly interested in a debate over
the relative qualities of languages in general, or anything like that
-- I recognize the names of most of the recent participants in this
sub-thread well enough that I think I can honestly say we all know
that's a debate that generates far more heat than light.

 

[Shailesh]

It can be. If you don't know why you really ought to take a step back
and learn some computer science...

Tom

No kidding. Trying to crack DES with a high bit-length is a fool's
endeavor (unless you are a researcher). If you do decide to try it,
the programming language choice is the least of your worries. Your
strategy should be to write your cracking algorithm on paper in
pseudo-code first, and then analyze its time requirements. Then you
might find out that you need thousands of computers:

http://www.distributed.net/des/

If you're just some script kiddie, then use Javascript and run your
program in a web browser for maximum speed.

 

[Douglas A. Gwyn]

true, technically speaking c/c++ is faster but only by a marging of less
than 1%.

That's simply not true. Have you *measured* the performance
of comparable implementations of the same algorithm in C vs.
Java? There are several reasons for the slowdown, one
being mandatory array bounds checking at run time, another
being treating everythings as an object, another being
dynamically allocating almost everything and relying on
garbage collection.