Hacker News Reader

>and even claimed to be faster than C for certain cases -a promise made for pretty much every language ever. Just need a couple of compiler tune ups. Not trying to be critical, that just gave me a chuckle.

I remember the days when C was just yet another systems programming language deemed too slow for any serious work.

EDIT: Always nice to be downvoted by hipsters that lack coding experience from the days C was UNIX only.

while true, that doesn't make it a bad comparison. Languages like Swift are one step up on the foodchain, they provide more abstraction. Comparing to a popular language one step down is a good way of showing the cost (or lack thereof). I'm sure 10 years from now we'll all be going "Language X is faster than Swift in certain cases!"

> I remember the days when C was just yet another systems programming language deemed too slow for any serious work.

I've heard that remark several times. Which languages were faster than C back then, except assembly? Fortran? Algol? BCPL?

Assembly of course. All higher level languages were still 2nd place to Assembly and had similar execution times across the board.

Most C/C++ compilers don't propagate `restrict` after inlining, so you lose a lot of optimization potential even if you use `restrict`.

I had no idea about this, I had mostly assumed that a decent compiler would do this. There is no reason this can't be implemented in the future, right?

It is difficult to implement correctly because the rules for `restrict` in the spec are quite nonintuitive; it doesn't simply mean that the two pointers don't alias each other.

The guarantee provided by owned pointers in Rust is stronger than that of `restrict` in C, so we should be able to propagate the must-not-alias constraints better upon inlining.

This is very interesting! Do you have some code examples or deeper explanation of this by any chance ?

Well, I'm not a C language lawyer myself, so I'm merely going off of what I have heard from people who are, but consider the following C function:

  bool f(int *restrict a, int *b, bool should_modify) {
    if (should_modify) {
      *a = b;
    }
    return a == b;
  }

Does this function have defined behavior? It turns out that the C spec says that the aliasing restrictions imposed by `restrict` only apply if the memory object pointed to by the restricted pointer has an intervening modification in the scope of the `restrict`; otherwise, the pointers are allowed to alias. Therefore, this function does not have defined behavior for all inputs. If a and b point to valid memory objects and a != b, then the behavior of f is defined regardless of the value of should_modify. If a == b, then f only has defined behavior if should_modify is false.

Yes, this is arguably insane, but it's also the spec.

In the interest of full disclosure, I should point out that the Rust compiler currently isn't conveying aliasing information to LLVM at all (or if it is, it's very minimal). If anyone's interested in implementing it, it would be both an interesting project and immediately catapult you into Rust godhood. :)

Can you describe in more details what you mean? An inlined function with restrict parameters is of course inlined as if the variables are restricted. Indeed, a test of an inline of an inline of an inline was still optimized (or rather, not guarded) per the restrict.

Consider the simple loop

  void f(int *a, const int *b, unsigned size) {
    for (unsigned i = 0; i < size; ++i) {
      a[i] = b[i] * 2;
    }
  }

This is the LLVM IR generated by `clang -Ofast -c -o - -emit-llvm -S`:

https://gist.github.com/zwarich/21cf3a0b2387302ea48b

Notice the `vector.memcheck` block, which is doing a dynamic aliasing check to decide whether to use the vectorized code. If I add `restrict`, e.g.

  void f(int *restrict a, const int *b, unsigned size) {
    for (unsigned i = 0; i < size; ++i) {
      a[i] = b[i] * 2;
    }
  }

then that dynamic check goes away:

https://gist.github.com/zwarich/48fd374becf5f891cb5a

However, if I put the vectorized loop in a function that gets inlined, e.g.

  static void f(int *restrict a, const int *b, unsigned size) {
    for (unsigned i = 0; i < size; ++i) {
      a[i] = b[i] * 2;
    }
  }

  void g(int *a, int *b, unsigned size) {
    f(a, b, size);
  }

the dynamic aliasing check reappears:

https://gist.github.com/zwarich/3e75f17de835dd9064ee

This is because LLVM's loop vectorizer runs after inlining and the standard optimization passes (which are run in a bottom-up traversal of the SCCs of the callgraph, interleaved with inlining). The `noalias` attribute on function parameters, which is what represents `restrict` in LLVM IR, disappears upon inlining. Many other compilers do something similar, although some like IBM's XLC can preserve `restrict` upon inlining.

> a promise made for pretty much every language ever. Just need a couple of compiler tune ups. Not trying to be critical, that just gave me a chuckle.

I was under the impression that C's qsort is often beaten by languages with support for templates / generics? I'm pretty sure they were talking about qsort.

If you compare standard library approaches between languages, yes, ones which let you inline calls will beat callback through pointers in thight loops, which is comparison function in qsort. Most of the time it is inconsequential. You could have used C preprocessor if you really wanted.

Yeah, but you can easily get C implementations of qsort which beat standard library one on most inputs by 2x/3x. For example here: http://www.ucw.cz/libucw/. Speed of sorting on modern machines depends mainly on what is in cache so even if you have some very clever implementation (like 3way split in qsort in recent Java) it won't help you if elements are not close to each other in memory. If you are sorting structs vs objects which are somewhere on the heap you already lost the performance battle so the compiler needs to very smart to make up for this.

so the compiler needs to very smart to make up for this

Since compilers don't control malloc, it's pretty hard for them to do any kind of optimization that relies on the physical locations of distinct objects in memory.

Not impossible, but even a very smart compiler would find it difficult to do things that an above average programmer could easily do up front, by using a better architecture/approach to begin with.

> and even claimed to be faster than C for certain cases

-a promise made for pretty much every language ever. Just need a couple of compiler tune ups. Not trying to be critical, that just gave me a chuckle.

It can be true although the "certain cases" may be quite a small set and there are likely to be many cases where C is faster than language X (where X includes Swift).

The whole aliasing bit was just weird and detracts from the piece. Anyone who is doing pointer-based-operations in base C is using restrict as appropriate.

Is that really true? Sure in highly optimised low level code it can be true. But in general code when can the compiler know that there is no aliasing. Isn't this the reason that Fortran can be faster than C in many cases?

Did you look at the aliasing examples beyond the memcpy reimplementation? It can affect perfectly normal code where you'd never think to use restrict.

Exactly. Yes you can use restrict. And, you probably will when writing benchmarks. But, this isn't about speeding up benchmarks. This is about speeding up real world production code with real world production deadlines. Are you really going to intelligently and correctly apply restrict to every function you write where it could help in your next commercial product? Do you really expect everyone on your team to do the same and never screw up?

Then there's the teeming masses of app developers who aren't quite as awesome as you. You don't care about them, but Apple does. Apple knows most of them couldn't restrict their way into a box ;) But, they still churned out a billion apps that are used by billions of users. Doing whatever we can to trick them into speeding up their code will literally save untold lifetimes of cumulative lag for the users.

I just want to say how much I enjoy the phrase "trick them into speeding up their code".