5 ms·

Note that the Python code is not limited to 32 bits and will automatically promote to bignum (aka long in py27). >>> l=[0xffffffff, 17] >>> sum(l)

Note that the Python code is not limited to 32 bits and will automatically promote to bignum (aka long in py27). >>> l=[0xffffffff, 17] >>> sum(l) 4294967312 C based code will silently overflow/truncate, giving 16 in the example above. The author handwaved all this away, but it does show the usual tradeoffs between right/robust answers and fast answers.

legulere 12y ago
Signed integer behaviour is undefined on overflow in C.
- anewhnaccount 12y ago
  But not on specific compilers with specific settings on specific machines like were used for the benchmarks results. Execution time is also undefined by the C standard.
  - MaulingMonkey 12y ago
    "Undefined behavior" is a specific term used by the C and C++ standards. What you're describing sounds more like "unspecified behavior", something entirely different. Undefined behavior allows for aggressive optimizations where the compiler assumes the integer overflow can never happen, leading to such wonderful bugs as this: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=30475 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=30475 Some compilers may offer specific settings, such as fwrapv, which give you a way to define the behavior of integer overflow. (Although last I read fwrapv was broken.) I see no mention of any such specific setting in the article. If you've spotted one I've missed, please call it out more specifically.
ebbv 12y ago
Obviously if this weren't a trivial example and were real code he'd account for this in his C code, and it would still be much faster than the Python code. He hand waved it away because it's not really relevant to the point.
- rogerbinns 12y ago
  The Python code was trivial to write and immediately correct and robust. Trying to get C code to do the right thing is considerably more difficult - for example even trying to detect overflow can result in code the compiler then removes - http://lwn.net/Articles/278137/ http://lwn.net/Articles/278137/ Robust, correct and fast are a hard combination to do. I do acknowledge the article is about the latter.
  - haberman 12y ago
    It's not hard if you use GMP.
    - lumpypua 12y ago
      The fancy library you're using in that other part of your project doesn't use GMP.
      - haberman 12y ago
        It likely doesn't need arbitrary precision arithmetic either. A lot of algorithms truly want modular arithmetic (hashes, checksums), many are dealing in domains that can't practically exceed a machine integer size (length of a string, number of vertices in a graph, etc). There is no reason that every library needs to deal in arbitrary precision.
        _delirium 12y ago
        > domains that can't practically exceed a machine integer size This assumption is common among authors of C code, but is sometimes also exploitably incorrect. Even if you really don't care about supporting things larger than a certain size, you do still have to correctly account for overflow, not just ignore it.
        haberman 12y ago
        Yes, overflow checks are critical, and tricky in the absence of language support. Yes, testing them is tricky, and often exploitably buggy in the absence of such tests. No, this does not mean that (for example) the Linux kernel should use arbitrary precision to represent pids (for example). Yes, this does mean that better approaches for more systematically dealing with overflow are a good idea.

legulere 12y ago

Signed integer behaviour is undefined on overflow in C.

anewhnaccount 12y ago
But not on specific compilers with specific settings on specific machines like were used for the benchmarks results. Execution time is also undefined by the C standard.
- MaulingMonkey 12y ago
  "Undefined behavior" is a specific term used by the C and C++ standards. What you're describing sounds more like "unspecified behavior", something entirely different. Undefined behavior allows for aggressive optimizations where the compiler assumes the integer overflow can never happen, leading to such wonderful bugs as this: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=30475 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=30475 Some compilers may offer specific settings, such as fwrapv, which give you a way to define the behavior of integer overflow. (Although last I read fwrapv was broken.) I see no mention of any such specific setting in the article. If you've spotted one I've missed, please call it out more specifically.

ebbv 12y ago

Obviously if this weren't a trivial example and were real code he'd account for this in his C code, and it would still be much faster than the Python code. He hand waved it away because it's not really relevant to the point.

rogerbinns 12y ago
The Python code was trivial to write and immediately correct and robust. Trying to get C code to do the right thing is considerably more difficult - for example even trying to detect overflow can result in code the compiler then removes - http://lwn.net/Articles/278137/ http://lwn.net/Articles/278137/ Robust, correct and fast are a hard combination to do. I do acknowledge the article is about the latter.
- haberman 12y ago
  It's not hard if you use GMP.
  - lumpypua 12y ago
    The fancy library you're using in that other part of your project doesn't use GMP.
    - haberman 12y ago
      It likely doesn't need arbitrary precision arithmetic either. A lot of algorithms truly want modular arithmetic (hashes, checksums), many are dealing in domains that can't practically exceed a machine integer size (length of a string, number of vertices in a graph, etc). There is no reason that every library needs to deal in arbitrary precision.
      - _delirium 12y ago
        > domains that can't practically exceed a machine integer size This assumption is common among authors of C code, but is sometimes also exploitably incorrect. Even if you really don't care about supporting things larger than a certain size, you do still have to correctly account for overflow, not just ignore it.
        haberman 12y ago
        Yes, overflow checks are critical, and tricky in the absence of language support. Yes, testing them is tricky, and often exploitably buggy in the absence of such tests. No, this does not mean that (for example) the Linux kernel should use arbitrary precision to represent pids (for example). Yes, this does mean that better approaches for more systematically dealing with overflow are a good idea.