Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

C Is Not a Low-Level Language

queue.acm.org

Post reply on HN
Print view View original

221–230 of 326 posts

Re: C Is Not a Low-Level Language

#221

Post by dragontamer »

jstimpfle wrote: post #219
dragontamer wrote: post #203

Earlier quoted context omitted.

> Access memory sequentially Except memory is virtual. Memory location 0x1000 might be forward, or backwards compared to 0xFFF, depending on the state of the Translation-lookaside buffer (TLB). Ever notice how (when ASLR is disabled), programs all start at the same location?? ( https://stackoverflow.com/questions/14795164/why-do-linux-pr... ) Hint: Virtual address 0x0804800 doesn't belong at physical address 0x080480…

> Except memory is virtual. Memory location 0x1000 might be forward, or backwards compared to 0xFFF, depending on the state of the Translation-lookaside buffer (TLB). Does that matter though? I would assume that the "prefetcher" (or whatever it's called) can make its predictions in terms of virtual memory. Regarding the linked list, it has been common wisdom for a long time that one should prefer sequential memory in…

> Does that matter though?

Yeah. Meltdown means that the OS (as a security measure) wipes away the TLB whenever you make a system call. So all of those cached TLB entries disappear every syscall due to Kernel Page-Table Isolation.

And then the CPU core has to start from scratch, rebuilding the TLB-cache again.

So last year (when we didn't know about Meltdown), a system-call was fast and efficient. This year, on Intel and ARM systems (vulnerable to Meltdown), system-calls are now forced to wipe TLB. (But not on AMD-systems, which happened to be immune to the problem)

Both AMD and Intel implement x86 instruction set, and now the performance characteristics is different between the two boxes for something as simple as "blah = blah->next".

-------------

The important bit is that C is still quite "high level", and indeed, even Assembly language "lies" to the programmer through virtual memory. The OS (specifically page-tables) can interject and have some magic going on even as assembly-code looks up specific addresses.

The simple pointer-dereference *blah is actually incredibly complicated. There's no real way to know its performance characteristics from a C-level alone. It depends on the machine, the OS, the configuration of the OS (ie: MMap, Swap, Huge Page support, Meltdown...) and more.

Re: C Is Not a Low-Level Language

#222

Post by EvilTerran »

dragontamer wrote: post #203
jstimpfle wrote: post #181

Earlier quoted context omitted.

> But the language doesn't show you those costs in any way. I think it's pretty clear. Access memory sequentially, and you can expect to hit the cache. Access more memory than the cache size in a random order, and you can expect to pay memory access latencies (100s of CPU cycles). I doubt you would be willing to manage the cache yourself in every line of code. That would be a lot of code. Some programmers might want…

> Access memory sequentially Except memory is virtual. Memory location 0x1000 might be forward, or backwards compared to 0xFFF, depending on the state of the Translation-lookaside buffer (TLB). Ever notice how (when ASLR is disabled), programs all start at the same location?? ( https://stackoverflow.com/questions/14795164/why-do-linux-pr... ) Hint: Virtual address 0x0804800 doesn't belong at physical address 0x080480…

And all that's without even getting into things like swap, or memory-mapped files. Or, to really go all-out, mmap() an NFS file - and you could find your mere pointer dereference waiting for the network.

Re: C Is Not a Low-Level Language

#223

Post by robochat »

munificent wrote: post #93

I really really liked this article, and reading the comments here is blowing my mind. Did we read the same thing? I think it's a strong insight that insight that chip designers and compiler vendors have spent person-millenia maintaining the illusion that we are targeting a PDP-11-like platform even while the platform has grown less and less like that. And, it turns out, with things like Spectre and the performance co…

I also really liked the article and found it thought provoking. This is all way above my pay grade but I like to think that there is a more optimal cpu design and language pairing that we will eventually reach and it's fun to imagine what that might look like.

Obviously, it would be very hard to shift the incumbent model in reality. We just have to look at the lack of prosperity for the Itanium and Cell processors to see how hard it is to achieve success. But imagine if new computer languages had been created just for these processors. Commercially this would make little sense but it might be possible to create languages that fully used these processors yet retained simplicity for developers. Or maybe it isn't possible to beat the clarity of sequential instructions for human developers or maybe Out Of Order processing is the optimal algorithm. There are other changes coming too such as various replacements for DRAM that either integrate more closely with the CPU (such as 3d chips) [1,2] that by reducing the latency of main memory, could actually bring us back closer to the C model of the computer? or just change computing entirely...

[1] https://www.extremetech.com/computing/252007-mit-announces-b... [2] https://news.ycombinator.com/item?id=16894818

Re: C Is Not a Low-Level Language

#224

Post by gpderetta »

admax88q wrote: post #178
pvg wrote: post #167

Earlier quoted context omitted.

Right, and the point I'm trying to make is this is a pretty lousy analogy. For one thing, an x86 CPU is not nearly as VM-y as you make it out - renamed registers are very much real registers, big piles of the most common instructions execute in 1 or 2 uOps. For another, the VM you've picked as an example is singularly uncpu-like. C also exposes an abstract machine, would you use that as an analogy? Probably not. 'An…

I don't know I think you're getting caught up too much on the specifics of what they're doing. CPU's are adopting JIT like tendencies in order to increase performance. Instruction reorder, register renaming, branch prediction, etc. > if you squint but offers somewhere between zero and negative insight. The insight I bring from this is that we should look moving those features out of the hardware and into the software…

OoO, renaming, branch prediction, microcode have existed for a long time. If anything, more modern CPUs (x86 included) are RISCer than the older generations which had extensive microcode expansion for each instruction.

Even ignoring the fact that the JVM is typed, memory safe and with builtin GC (all things that were tried architecturally in the past and abbandoned), there is still a large difference between the scope and variety of non-local optimizations perfomed by any non-toy VM and the local, strictly realtime, constrained to a small window, set of reordering done by an OoO engine. Even tracing, which is used by some JITs, has been largely abbandoned in the CPU world.

Transmeta and Denver-like dynamic translation is closer to the behaviour of a software JIT and it is certainly considered drastically different from mainstream OoO.

Re: C Is Not a Low-Level Language

#225

Post by lowbloodsugar »

Shikadi wrote: post #122
munificent wrote: post #93

I really really liked this article, and reading the comments here is blowing my mind. Did we read the same thing? I think it's a strong insight that insight that chip designers and compiler vendors have spent person-millenia maintaining the illusion that we are targeting a PDP-11-like platform even while the platform has grown less and less like that. And, it turns out, with things like Spectre and the performance co…

Actually, the author's argument about PDP-11 is interesting because C would have never been considered a low level language back then, for any platform. Wiki definition, also what I was taught in my first CS class: "A low-level programming language is a programming language that provides little or no abstraction from a computer's instruction set architecture—commands or functions in the language map closely to proces…

Heh. Yeah. Was programming ARM assembly in 1988. C compiler was far too high level. Look how its always saving these registers to memory! Meanwhile I'm dropping into FIQ mode just for the banked R8-R14.

Now, sure, people say C is low level, and compared to Java it sure is. But it isn't low-level.

Re: C Is Not a Low-Level Language

#226

Post by [deleted] »

mattnewport wrote: post #149
drbawb wrote: post #133

Earlier quoted context omitted.

>the argument made was that predicting likely-parallelizable code is actually a lot harder to do at compile time So don't do it at compile time? That's really a very weak argument against the Itanium ISA, and honestly more of an argument against the AOT complication model. Take a runtime with a great JIT, like the JVM or V8, and teach it to emit instructions for the Itanium ISA. (As an added advantage these runtimes…

There's not that much overlap between the kind of optimizations that JITs do and the optimizations that modern CPUs do. The promise of JITs outperforming AoT compiled code has never really materialized. The performance advantages of OoO execution, speculative execution, etc. are very real and all modern high performance CPUs do them. Attempts to shift some of that work onto the compiler like Itanium and Cell have lar…

[deleted]

Re: C Is Not a Low-Level Language

#227

Post by sytelus »

Interesting tidbits from article:

A modern Intel processor has up to 180 instructions in flight at a time (in stark contrast to a sequential C abstract machine, which expects each operation to complete before the next one begins). A typical heuristic for C code is that there is a branch, on average, every seven instructions. If you wish to keep such a pipeline full from a single thread, then you must guess the targets of the next 25 branches.

The Clang compiler, including the relevant parts of LLVM, is around 2 million lines of code. Even just counting the analysis and transform passes required to make C run quickly adds up to almost 200,000 lines (excluding comments and blank lines).

Re: C Is Not a Low-Level Language

#228

Post by jeffffff »

Baeocystin wrote: post #185
Tobba_ wrote: post #176

Earlier quoted context omitted.

It might still be possible. The JVM and .NET both have their speed annihilated by their awful choice of memory model.

What's wrong with their memory model? Honest question.

the jvm lacks structs and more specifically arrays of structs as a way to allocate memory. this causes extreme bloat due to object overhead as well as a ton of indirections when using large collections. the indirections destroy any semblance of locality you may have thought you had which is the absolute worst thing you can do from a performance perspective on modern processors. what people end up doing instead is making parallel arrays of primitives where there is an array for each field. this is also not ideal for locality but it's better than the alternative since there isn't a data dependency between the loads (they can all be done in parallel).

i am not that familiar with the C# runtime and i know C# has user definable value types, but i'm not sure what their limitations are.

Re: C Is Not a Low-Level Language

#229

Post by gpderetta »

proverbialbunny wrote: post #195
skybrian wrote: post #174

Earlier quoted context omitted.

It seems like the article is mostly useful for inspiring research; that is, most of us aren't the target audience. I'm wondering what will happen as GPU's become more general-purpose. What's next after machine learning? Would it be possible to make a machine where all code runs on a GPU? How would GPU's have to change to make that possible, and would it result in losing what makes them so useful? What would the OS an…

I think it is going the opposite direction, where cpus get more powerful graphics cards integrated more and more into them. This allows for matrix math to become a bit more standard in day to day programming. However, in the opposite direction where a gpu becomes more like a cpu, if streams could do some level of limited branching without slowing the whole thing down, it opens the door to threading frameworks and des…

> cpus get more powerful graphics cards integrated more and more into them.

Actually the wheel of reincarnation seems to have stopped at least for the time being. It seems that there is a fundamental, hard to reconcile, disconnect between a latency optimised engine like a CPU and a throughput engine like a GPU. Hybrids CPUs like larrabee or extensions like AVX512 do not seem to be enough.

Short term, probably the best we are going to see is separate CPU and GPU cores in the same die (or more likely jus the same package), but even that is likely suboptimal.

Re: C Is Not a Low-Level Language

#230

Post by andrewflnr »

verall wrote: post #200
munificent wrote: post #177

Earlier quoted context omitted.

> the same kind of pattern matching used by (e.g.) LLVM to find optimizable sequence of statements also could be used by any assembler. Some of the simpler optimizations, sure. But modern backends do many incredibly sophisticated optimizations that are way beyond any kind of simple pattern-matching-and-substitution model. Even fundamental "optimizations" like register allocation use quite sophisticated algorithms. Op…

The K-graph coloring problem for register allocation is NP-complete, but in SSA form is actually linear. The tougher problem isn't the coloring but rather where to optimally place spills and fills around loops and calls. https://llvm.org/devmtg/2011-11/Olesen_RegisterAllocation.pd...

Yeah, the number of "registers" needed isn't really NP-complete the way that the number of colors in a graph is. It's just the maximum number of live values, which, while not exactly trivial, is not that hard to figure out.
Post reply on HN