Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses
 
PerlMonks  

Re^3: bigint == horrible performance?

by moodywoody (Novice)
on Nov 06, 2011 at 22:21 UTC ( #936355=note: print w/ replies, xml ) Need Help??


in reply to Re^2: bigint == horrible performance?
in thread bigint == horrible performance?

Ok .. to clear things up .. I am _not_ interested in better libraries or algorithms for that problem. I used bigint because I was not sure whether one of the Collatz chains would produce an intermediate number exceeding the int scope (probably my take on pessimation). Only after reading on the projecteuler forum that everyones solution was running in 1-5sec and mine taking 10min - while using the same algorithm as many others - made me suspicious. So I removed "use bigint" .. lo, and behold! It runs .. fast. Googling "perl bigint performance" didn't turn up anything useful, that's why I asked here.

PS. I used pastebin because I wasn't sure about the "post code" conventions ;-)


Comment on Re^3: bigint == horrible performance?
Re^4: bigint == horrible performance?
by BrowserUk (Pope) on Nov 07, 2011 at 15:04 UTC
    So I removed "use bigint" .. lo, and behold! It runs .. fast.

    Arbitrary precision math is, regardless of the language in which it is written, much, much slower than fixed precision. It is the nature of the beast. If you know how arbitrary precision math works it will not come as any surprise.

    It therefore falls to the developer to understand that and only use arbitrary precision when it is actually required.

    I have a tendency to get somewhat exasperated when I see people offering Math::Big* as a solution to problems where there is a perception of a "precision problem", when 95% of them have far simpler and more efficient solutions.


    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
      Of course you're right. I pray excuse that I come from java land where everything not totally foolproof comes with giant warning signs. One gets used to that.
      Arbitrary precision math is, regardless of the language in which it is written, much, much slower than fixed precision

      I didn't do any benchmarking but my hunch is that the real slowdown wrt the op's code (when used with bigint) came about as a result of the multiplication and division operators being replaced by function calls.

      But then ... replacement of "operators" with "function calls" is really part and parcel of how arbitrary precision math works, so I'm not sure that stating my "hunch" actually contributes anything terribly useful ... even if it *is* correct.

      Cheers,
      Rob

        The slowdown comes in (at least) three stages. Perhaps more depending upon which back-end is being used behind the bigint front of house.

        1. Overloading the operators adds one level of subroutine call to each math op.
        2. The call into the back-end library adds a second.
        3. A third level comes from getting access to the memory in which the numbers are actually stored.

          With native opcodes, the value is at a fixed offset and the actual operations are essentially a single assembler instruction (processor opcode).

          With the libraries, you have the XS to C wrapping layer, then the library call, then dereferenceing and casting to get access to the number hanging off the PV.

          And with arbitrary precision and larger-than-register fixed precision, you have the condition testing to see if the number has multiple elements and the loops needed to propagate carries etc.

        I was not laying any criticisms. If you need the precision, then the costs -- whatever they are -- simply have to be paid. But using bigint 'just in case', or as a 'cure' for perceived 'inaccuracies' in floating point is the wrong way to go.


        With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority".
        In the absence of evidence, opinion is indistinguishable from prejudice.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://936355]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (6)
As of 2014-12-25 18:00 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (161 votes), past polls