Hacker News Reader

Comment by simias | Hacker News Reader

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 these optimizations, otherwise you might as well use inline ASM on compiler intrinsics since it won't be portable anyway.

There are certain features of the C standard that forces the compiler to generate non-optimal code by default in certain cases (like aliasing rules, as any FORTRAN proponent will remind you). I don't think it's the case in TFA.

So basically, blame the optimizer, not the language.

P.S.: I used this cached version since the site appears to be down: http://webcache.googleusercontent.com/search?q=cache:accu.or...

View on HN

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...

TBH, I have yet to see one which lacks CF.

Out of the top of my head, mips, Alpha, AM29000. There are plenty more.

Head? you mean wikipedia? :)

From 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.

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.

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.

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.

> 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.)

> What if the architecture doesn't have a carry? Then the compiler has to generate one when needed.

What is your point? If you want to do multiple precision arithmetic in assembly, then on the architectures which don't have a carry, you must indeed generate one, so what? If a language has some operations with carry, then it is up to the programmer to use them only when he needs them..

> C doesn't even mandate what happens in case of an integer overflow

That's for performance reasons, and I would say that it is the wrong default aka 'premature optimisation', a better language would have 'int' with overflow checks (which could be disabled by a compiler switch) and int_raw for the unsafe&fast behaviour.

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.

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).

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.

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-progr...

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.

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)

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.

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.

Reply on news.ycombinator.com