16 ms·

IMHO the problem here is the capabilities of the optimizing compiler, not the language itself. I would argue that it should be the compiler's job to figure thes

• mrich 13y ago
  You could argue that it is a fault of the C language that it does not expose the carry flag of the CPU. This makes the most optimal implementation of e.g. addition impossible without resorting to (inline) assembler. Of course not every CPU has a carry flag...
  • artificialidiot 13y ago
    TBH, I have yet to see one which lacks CF.
    • Tuna-Fish 13y ago
      Out of the top of my head, mips, Alpha, AM29000. There are plenty more.
      • sp332 13y ago
        Head? you mean wikipedia? :) From https://en.wikipedia.org/wiki/Status_register#CPU_architectures_without_arithmetic_flags https://en.wikipedia.org/wiki/Status_register#CPU_architectu... those architectures put the carry result in a general-purpose register, but you still can't access the result in C.
        • Tuna-Fish 13y ago
          They were the three architectures that immediately sprung to mind when I though of cpus without carry bits. I have only programmed in assembly for two of them -- I might well have read that wiki page before.
  • simias 13y ago
    Except that exposing too much hardware state to the coder might give less room for the compiler to optimize aggressively for all architectures. What if the architecture doesn't have a carry? Then the compiler has to generate one when needed. What if the architecture has better ways to do the addition anyway? What if the architecture is only 8bit and even regular "int" adds take several instructions anyway, so it makes so sense opmimizing for 128bit adds? C doesn't even mandate what happens in case of an integer overflow, it has no business exposing carry flags. If I ever write a C tutorial I'll title it "How I learned to stop worrying and love the compiler". EDIT: of course in this case you can't really "let the compiler handle it" if you care about bignum performances. The only solution here would be a/ expose much more hardware state to the language, which as I've already stated doesn't sound very convenient or C-ish enough for me, b/ modify the optimizer to better handle bignum code or c/ use a bignum library and possibly make it part of the standard. I wouldn't be opposed to a standard <bignum.h>, I think it would make some sense. In the meantime I just use gmp.h, it's faster than anything I could come up with anyway, asm or otherwise. Bignum is hard.
    • adr_ 13y ago
      Unsigned integer overflow is defined. I agree that the carry flag shouldn't be exposed directly, but the ability to express "add and check for overflow" would be useful and allow for these optimisations where the architecture supports it. Edit: But if you want to exploit the processor to its fullest, go with assembly. The compiler is good, but proving optimisations is a hard problem, and complex, single-instruction-specific optimisations aren't going to take off any time soon.
    • zvrba 13y ago
      > What if the architecture doesn't have a carry? Then the compiler has to generate one when needed. Adding two N-bit numbers produces N+1-bit result, and C gives you no direct means of accessing the full result. IMO, this is a language defect and has little to do with HW support. [This pertains also to multiplication: NxN bits -> 2N-bit result.] If the hardware actually returns the full result, excellent; if no, the compiler has to synthesize code to compute it, if needed. Whether it's needed is inferrable by the code that follows, e.g., the type of the variable the result is assigned to. IMO, inferring that only a partial result is used (e.g., carry is discarded) is much easier for the optimizer than inferring what some instruction sequence is supposed to do. (E.g., 4+ multiplications and few additions => single 32x32=>64 multiply.)
  • sanxiyn 13y ago
    I note here that while C does not expose carry flag, LLVM does, and at least on x86 "with overflow" intrinsics do compile to the right instruction.
• nly 13y ago
  Unless you convey information to them, via higher level language constructs or compiler directives, it's not really fair to blame a compiler for making poor or conservative choices. Compilers can only infer or guess at what your intentions are. The author is banging on about uint128_t for example, and bashing library approaches like boost, but uint128_t isn't even part of the C or C++ standards. Its apples and oranges.
• Tloewald 13y ago
  I think the article is pretty meticulous about differentiating between compiler issues (the compiler not recognizing an opportunity to use overflow bits, for example) and C problems (multiplication producing an output the same size as the inputs, which is broken for a large proportion of inputs -- which the writer calls out as an over-generalization).
• sharpneli 13y ago
  C99 fixed the aliasing issue by adding the restrict keyword. It's such an important addition that I'm bit surprised why it's still not common knowledge.
  • willvarfar 13y ago
    As an aside, its worth looking at the new Mill CPU architecture; its immune to aliasing bugs :) http://ootbcomp.com/topic/introduction-to-the-mill-cpu-programming-model-2/ http://ootbcomp.com/topic/introduction-to-the-mill-cpu-progr...
  • cliffbean 13y ago
    Few people actually know Fortran anymore, but in reality, C99's restrict covers only a narrow subset of what Fortran's aliasing rules covered. restrict's numerous limitations substantially reduce its usefulness, which is one reason it's not as common knowledge as one might guess.
    • sharpneli 13y ago
      Can you elaborate on what the limitations are? I have been under the impression that restrict makes it pretty much equivalent to fortran (restrict means that nothing aliases the pointer)
      • cliffbean 13y ago
        On some pointers, for example function return types, restrict is defined to be meaningless. Also, restrict pointers can be copies of other pointers, and copies can be made of restrict pointers, subject to certain rules. So it's more involved than just "nothing aliases the pointer". Here's another example: // C has pretty paltry array support, so it's common for // people to build their own stuff like this: struct Array { float *data; size_t len; }; // But then you use it: void foo(Array *a, Array *b) { for (i = ...) for (j = ...) a->data[i] = b->data[j]; } and there's nowhere you can put restrict to declare that the two array references here are independent. The data pointer is one of the contexts where restrict is defined to be meaningless. If you're a hyperactive squirrel, you might try rewriting all your code everywhere to do stuff like this: void foo(Array *a, Array *b) { for (i = ...) for (j = ...) { float *restrict x = a->data; float *restrict y = b->data; x[i] = y[i]; } but then you'll just discover that most compilers ignore restrict in block scopes like this, because the semantics for that are tricky for compilers to deal with, so you still won't win.