21–30 of 215 posts
Earlier quoted context omitted.
The C language has provided the restrict keyword to solve these aliasing issues since the C99 standard. That is, 20 years ago.
I think this generally doesn't have much of an impact on performance.
Whether or not the compiler will be smart enough to autovectorize is a different question.
I’ve been thinking about this lately. Can you actually be faster than C? Like, in the sense that you can transpile any bit of Python or Lisp or Haskell or Rust or JS into C but the opposite isn’t necessarily true because not all those language support all the features exposed in C (such as goto, no bounds checking, pointer arithmetic, etc.), any algorithm for say parsing JSON can be expressed equally as efficiently i…
Sure, managed languages can beat C performance. IIRC, the JVM can reorder branches on the fly to avoid jumps.
What's much more important for good performance is memory layout and good use of CPU caches. And in this area managed languages struggle a lot. For instance, every object in Java has 16 bytes of overhead for an object header (on 64-bit openjdk jvm). Or you can't organize objects in a flat array. Or there are some guarantees about memory zeroing which often lead to needless memory writes. Or you have to live with GC, which often wastes a lot additional memory and regularly brings unused but reachable memory to caches. Project Valhalla is going to improve some of these limitations hopefully some day, but don't expect the level of C, C++ or Rust performance.
Earlier quoted context omitted.
The C language has provided the restrict keyword to solve these aliasing issues since the C99 standard. That is, 20 years ago.
I think this generally doesn't have much of an impact on performance.
I’ve been thinking about this lately. Can you actually be faster than C? Like, in the sense that you can transpile any bit of Python or Lisp or Haskell or Rust or JS into C but the opposite isn’t necessarily true because not all those language support all the features exposed in C (such as goto, no bounds checking, pointer arithmetic, etc.), any algorithm for say parsing JSON can be expressed equally as efficiently i…
Sure, in any language that provides more semantic information than C does. For example, D enables a "pointer to immutable data" type, while C does not. This can improve optimization.
On a pragmatic note, C makes it easy to use 0-terminated strings, and clumsy to use length-terminated strings. The natural result is people use 0-terminated strings.
0-terminated strings are inefficient because of the constant need to strlen them. When I look to optimize C, I find plenty of paydirt in all the strlen instances. D makes it easy to use length-terminated strings, and so people naturally prefer them.
I’ve been thinking about this lately. Can you actually be faster than C? Like, in the sense that you can transpile any bit of Python or Lisp or Haskell or Rust or JS into C but the opposite isn’t necessarily true because not all those language support all the features exposed in C (such as goto, no bounds checking, pointer arithmetic, etc.), any algorithm for say parsing JSON can be expressed equally as efficiently i…
This isn't true though. Just off the top of my head: C doesn't expose the carry flag directly, C doesn't let you write signed arithmetic using twos-complement overflow, C doesn't let you share a value between separate compilation units without allowing it to be mutated...
"faster" or "slower" is a pretty terrible metric anyway, given that most projects do not have infinite developer time available. But it's very hard to benchmark "equivalent developer effort" between two different languages.
I had something like a set or a set> (or map... I can't remember which) somewhere in my program a few years ago, and I was trying to improve the program's performance. I tried breaking into it several times and found it quite perplexing that the bottleneck appeared to be the set container. I mean, I get that cache locality and all has an effect, but it seemed to be having a little too much of an effect. Why did I find this odd? Because other languages (like C#) have tree-based sets and maps too, but I'd never felt they were quite as slow as I was seeing them in C++. So I felt something weird must be going on.
I tried to step through the program for a while and observe what's going on, and at some point, I realized (perhaps I hit the same breakpoint twice? I don't recall) that these functions were being called more often than I intuitively thought would be necessary. Which was obvious in hindsight, as less() needs to be called multiple times on the same objects (4 times at level 2). Now, this hadn't resulted in quadratic behavior, but that was only because my data structures weren't arbitrarily deep—the slowdown was nevertheless a significant constant factor at the core of my program, only linear because the data structure's depth was bounded.
So once I had realized the implications of this, including that constant-factor differences can actually turn into polynomial ones, I eventually decided to post an article about it on arXiv... hence this article. Aside from the complexity issue illustrated in the article, one of my (unexpected) higher-level takeaways was that you can't just take any utility function in a program and blindly put it into a library: even if it's correct, you probably have hidden assumptions about its use cases that won't hold true in general. You really need to think about how it could be used in ways you didn't initially expect, and this may well require a different kind of code review with an entirely different mindset than before. It really drove home the point for me that writing a library is quite a bit different (and in some ways more difficult) than writing an application.
It's possible there is more theory lying underneath this that I haven't touched on—it would be interesting if someone can take this and find more interesting consequences of it. For example, maybe when analyzing algorithms we need to consider something akin to a "recursive time complexity", too? Is there another useful notion of complexity that we can generalize here?
Anyway, hope people enjoy reading it and take something useful away from it. :)
I’ve been thinking about this lately. Can you actually be faster than C? Like, in the sense that you can transpile any bit of Python or Lisp or Haskell or Rust or JS into C but the opposite isn’t necessarily true because not all those language support all the features exposed in C (such as goto, no bounds checking, pointer arithmetic, etc.), any algorithm for say parsing JSON can be expressed equally as efficiently i…
Also tasks that can be moved to the GPU go a lot faster. You can interact with those programs in C, but not natively. But some languages, like Julia, can easily move calculations to/from the GPU. And also can transparently take advantage of parallelism.
Julia is in the process of growing rapidly for high performance computing. I don't know if it has officially passed C there. But if not yet, it will.
Earlier quoted context omitted.
If you use the normal toolchains for C vs another language, the other language still can be faster because it can dynamically generate bytecode based on runtime information. In the normal C toolchain, this is not possible. However, if you used an alterative toolchain that could also generate bytecode from C at runtime, then I would bet that C would stay on top or be equal.
You can literally emit runtime assembly in C in any C toolchain, what are you on about?
Earlier quoted context omitted.
C loses some optimization potential because of aliasing; it can't be guaranteed that some pointer operation isn't going to change a variable anywhere in memory so that limits certain reordering and loop optimizations. Languages without arbitrary pointers don't have this issue and safely assume they knows all the assignments done to values in memory allowing for optimizations.
The restrict keyword helps with this.
Earlier quoted context omitted.
I think this generally doesn't have much of an impact on performance.
It certainly does... it's the main reason fortran was often faster than C, isn't it? Aliasing prevents automatic vectorization, among other things. Whether or not the compiler will be smart enough to autovectorize is a different question.
C compilers don't validate correct use of restrict.