Cracking DES with C++ is faster than Java?

Discussion in 'C++' started by Julie, Apr 25, 2004.

  1. Julie

    Julie Guest

    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.
     
    Julie, Apr 28, 2004
    #61
    1. Advertisements

  2. As opposed to an *accurate* idea of superset/subset?
     
    Douglas A. Gwyn, Apr 29, 2004
    #62
    1. Advertisements

  3. Julie

    Dez Akin Guest

    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.
    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.
     
    Dez Akin, Apr 29, 2004
    #63
  4. Julie

    Julie Guest

    Dez Akin wrote:
    [snip]
    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.
     
    Julie, Apr 29, 2004
    #64
  5. Julie

    Phil Carmody Guest


    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
     
    Phil Carmody, Apr 29, 2004
    #65
  6. 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 Puviani, Apr 29, 2004
    #66
  7. Julie

    Julie Guest

    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.
     
    Julie, Apr 29, 2004
    #67
  8. "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
     
    Claudio Puviani, Apr 30, 2004
    #68
  9. Julie

    Julie Guest

    Thank you for your apology.

    I entirely agree that optimization (in general terms) will always be necessary,
    regardless of processing performance improvements.
     
    Julie, Apr 30, 2004
    #69
  10. Julie

    Jerry Coffin Guest

    [ ... ]
    Oddly enough, I quite agree.
    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.
    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, Apr 30, 2004
    #70
  11. Julie

    Jerry Coffin Guest

    [ ... ]
    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.
    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.
    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.
     
    Jerry Coffin, Apr 30, 2004
    #71
  12. Julie

    Bryan Olson Guest

    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.
     
    Bryan Olson, Apr 30, 2004
    #72
  13. [snip]
    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
     
    Andrew Swallow, Apr 30, 2004
    #73
  14. Julie

    Jerry Coffin Guest

    [ ... ]
    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.
    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.
    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.
    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.
     
    Jerry Coffin, Apr 30, 2004
    #74
  15. 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.
    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.
    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.

    --
     
    Paul Schlyter, May 1, 2004
    #75
  16. Paul Schlyter wrote:
    [snip]
    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
     
    Mok-Kong Shen, May 1, 2004
    #76
  17. void f(int *a, int *b) {
    *a = 42;
    *b = 0;
    if (*a == 42) // cannot assume this is true
    *b = 1;
    }
     
    Douglas A. Gwyn, May 1, 2004
    #77
  18. Julie

    Jerry Coffin Guest

    (Paul Schlyter) wrote in message
    [ ... ]
    Yup -- but my phrasing was more fun. :)
    Either of these can be viewed as either an advantage or a
    disadvantage.

    [ ... ]
    [ ... ]

    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.

    [ ... ]
    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.
     
    Jerry Coffin, May 1, 2004
    #78
  19. Julie

    Shailesh Guest

    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.
     
    Shailesh, May 1, 2004
    #79
  20. 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.
     
    Douglas A. Gwyn, May 1, 2004
    #80
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.