Understanding C by learning assembly | Hacker News Reader

Understanding C by learning assembly

recurse.com

147 pointsluu52 comments

There are two levels of deepening your understanding of C.

Level 1 is what this article describes: your eyes are opened when you see how various features of C map naturally onto things that are simple/efficient in hardware. You see a pointer dereference and in your head you think "aha! load instruction." You understand that there is a real difference between "char ch[10]" and "char ch[10] = {0}" -- the latter emits extra instructions to zero out the memory.

Level 2 is when you realize that the optimizer is free to screw with all your intuitive ideas about C -> hardware mapping that you learned about at level 1. You learn that writing correct C means that you need to think in terms of the abstract machine that C defines, and not assume that any specific C statement will translate to the assembly code you expect. You can't think "pointer dereference means load instruction", you have to think "pointer deference reads an object."

There's nothing wrong with level 1, as long as you don't stop there!

Great point. It's also worth remembering that optimizations such as floating point at O3 will trade away accuracy for speed. C compilers are willing to give you... the wrong result... but faster than ever! Undefined behavior is another fun line of inquiry. Best to learn about the dark corners and avoid them where possible.

No, you don't get inaccurate floating-point results just by using a higher level of optimization. For example, gcc requires an explicit -ffast-math option for that kind of optimization.

There's an explicit compiler flag to get fast but not accurate math and it isn't enabled in any of the -On presets in either gcc or clang.

My original source was wrong. Thanks for the correction you two!

This is doubly true when dealing with concurrency. You have to consider not only possible interleavings of side effects, but also possible reorderings of loads and stores by the compiler and the CPU.

I dunno where I picked it up, but my standard euphemism for writing lock-free code is “juggling knives”.

Seriously people would be so happy after investing in learning about interpreters and compilers. When you see a language as an object, data, abstract machine and mapping between them, it clears your mind for good.

Is there a level 3, where you spent enough time with particular compiler to understand and anticipate machine code it outputs?

Not these days, IMO. Optimizers are much too complex for anyone to be able to model them mentally.

this reminds me of this quote

"Before I learned the art, a punch was just a punch, and a kick, just a kick. After I learned the art, a punch was no longer a punch, a kick, no longer a kick. Now that I understand the art, a punch is just a punch and a kick is just a kick." -- Bruce Lee

Assembly has one huge advantage over C: no undefined behavior. What you see is what you get. There's none of the it-might-work-for-years-before-betraying-you worry when you deal with assembly. Even if you need to think about multiple machine types, you can think about the finite set of machine types you care about, and not worry about some abstract ideal of portability that will cause the C compiler to do strange things (http://blog.regehr.org/archives/213).

Unfortunately, this advantage means you can't understand all of C just by understanding assembly, even though C programs turn into just assembly at bottom.

Edit: after the responses below I've been (re)reading https://www.scss.tcd.ie/John.Waldron/3d1/arm_arm.pdf and http://www.intel.com/content/dam/www/public/us/en/documents/.... And marvelling.

> Assembly has one huge advantage over C: no undefined behavior.

Sadly it sure does. Grep through the ARM architecture reference manual for "UNPREDICTABLE" (helpfully typeset in all caps), for example…

Interesting.

Yeah I just hit a LLVM AArch64 codegen bug today. Ugly!

str x9, [x9], #8

Luckily it was fixed upstream. I don't like working in tablegen files. =)

https://github.com/llvm-mirror/llvm/commit/7f4f923aa57ad8d7e...

> There's none of the it-might-work-for-years-before-betraying-you worry when you deal with assembly.

That's not quite true. For example, in my blog post on assembly [0] one of the first points I make is that on x86-64, the stack must be aligned by 16 B when calling into libc. (Note: the point I'm making is invalid if we're talking assembly with no libc interop, but c'mon). That's actually not a hard and fast rule; it has more to do with requirements of the implementation of that function for alignment. For instance, I can invoke memset from x86-64 assembly with a misaligned stack without segfaulting on _my_ machine, _but_ that is because my implementation of memset I'm linking against doesn't require alignment. That might work for me today, but let's say the next upgrade to my libc suddenly has a new implementation of memset that requires alignment for whatever reason (I think vector register access requires stack alignment, for instance). Suddenly, my assembly program that worked the day before (possibly for years) has now betrayed me. And you just have to keep track of alignment in your head. Oh, someone pushed a 64b register on the stack? Misaligned by 8B!

I'm not arguing the point about undefined behavior (though I'm sure there's probably known bugs with certain instructions on certain families of processors [1]). My point is that it's very possible for assembly to betray you, and compiler warnings from C/C++ compilers are a god send compared to the usual seg faults and bus errors experienced when writing assembly. (honestly, I find pencil & paper very useful for debugging assembly; by sketching out the state of things and trying to reason about them, you find failed assumptions and mistakes).

[0] http://nickdesaulniers.github.io/blog/2014/04/18/lets-write-... [1] http://en.wikipedia.org/wiki/Pentium_FDIV_bug

Many processors have undefined behavior. The x86 manuals, for instance, specify (or rather, explicitly decline to specify) lots of it:

- Values of certain flags after certain instructions

- The result of bsf or bsr on 0.

- I think there are some floating point operations that can be undefined when the results fall off the edge of representability, but I don't remember off the top of my head.

These have behavior that differs from processor to processor.

This isn't to mention the various kinds of processor errata that pop up: loads being reordered with LOCK'd x86 instructions, or ARM memory reads that go backwards in time, both of which happen in real processors despite being architecturally forbidden.

> Assembly has one huge advantage over C: no undefined behavior.

In the olden days, maybe, but nowadays? No way. As the most extreme example: forget to use memory barriers when you should? Congratulations, the OOO nature of modern day CPUs means your code may not execute identically on all platforms. But even lesser things can impact you: instructions that were cheap become expensive, or suddenly registers that you know you weren't supposed to touch but did (and that happened to work) suddenly don't because a library got changed, or half a dozen other things.

With assembly on a modern CPU, congratulations: you have eliminated one level of abstraction. But there are still many, many turtles to go before you're really all the way down.

> instructions that were cheap become expensive

Agree.

At which point, C gives you a huge advantage. Sure, you can hand write assembly, but I bet the libc implementation you're linking against has optimized to death with intimate knowledge of timing sequences and inner state of the processor from the processor vendor. I would expect a company like Intel to contribute patches to glibc (GNU libc) based on running functions from the standard library on a very very expensive FPGA (or just expensive-software simulation of hardware).

Memory ordering operations are an advanced topic; I have a copy of C++ Concurrency in Action, currently sitting on my bookshelf, that has a chapter explaining the concepts. Should be a fascinating read!

Agreed. I think there's no clearer example of C giving you an advantage than integer division by a constant. Even on architectures where it's supported (x86), the divide instruction is really slow. The standard approach is to use the Hacker's Delight technique to convert the division into a fixed-point multiplication and shift. All production-quality compilers will do this for you by generating the magic number, but if you're doing it yourself in assembler you'd have to look up the magic number and shift. Lots of assembly language programmers won't even bother doing this and will just write "idiv" in x86 (or "bl __divsi3" on ARM), which slows down their programs.

I think you might be being optimistic about Intel there. They have their own compiler suite though, which can be a few percent faster than GCC and has better auto-vectorisation.

It's almost the other way round: they have a corpus of binaries to use when making processor design decisions.

"In the olden days, maybe"

Nope. I expect _all_ early processors had undefined behaviour, because they didn't have the transistor budget to make all instructions behave predictably. The 6502 certainly had (http://www.ffd2.com/fridge/docs/6502-NMOS.extra.opcodes), as did the Z80 (http://www.z80.info/z80undoc3.txt)

We can see in the replies that asm does in fact have undefined behavior. So what about Rust? Presumably the point of Rust's safety is that, assuming the (hopefully minimal) unsafe code you depend on is well debugged, there is no undefined behavior; either the program works, it fails fast and cleanly, or it doesn't compile.

I don't think the article is aptly titled, which is too bad, because literally "understanding C by learning assembly" is actually a terribly wrong-headed idea.

The article is rather about exploring a particular C run-time at the assembly language level, and a tutorial about stepping through programs at that level.

This is something useful that would-be developers need to learn, the main reason being that programs sometimes fail in ways such that uncovering the root cause requires a trip through that level. Other reasons are that in some situations we need to verify that programs believed to be correct at the source level are actually being translated in the way we expect.

I agree with the wrong title for that article,

But, why do you think that understanding C by learning assembly is a terribly wrong-headed idea?

Some professors tend to disagree and prefer a bottom up approach of learning. The main advantage is : you get rid of the "magic" of computing.

http://www.ncsu.edu/wcae/WCAE2/patt.pdf

https://www.youtube.com/watch?v=J926i6MwRpo

I definitely agree with this. I had "learned C" but not really (programmed small things in it). Then about a year later I ended up taking a course that involved a lot of reverse engineering and analysis of ELFs.

Later on I went back to C since I knew I had never really done a lot with it and everything was a breeze. I understood what was going on, loved it, and on top of that was able to easily knock out loads of exploitation stack-smashing puzzles I found on the internet.

I already knew how to program pretty well but didn't really know system programming and C. I can imagine the value of, instead of writing hello world, learning assembly first and writing programs that end with some exit status instead. It would probably be way more boring, but way more informative in the long run.

The thing is, C does contain quite a bit of "magic" built into the transformations a compiler is allowed to do to your constructs. A mental model of C built on the mapping to assembly is appealing, but leads to false intuition when reasoning about the language's rules, which occasionally has disastrous effects.

Just as an anecdote, I have seen a surprising number of C programmers assume that the language's type aliasing rules are related to or somehow governed by pointer alignment, when these are entirely separate. The former exists to facilitate analysis and optimization at the compiler level -- there is no "ground" reason. It's important not to get trapped in the portable assembler mindset and lose sight of an entire level of transformations that might not have an intuitive relationship with hardware.

Probably, the most succinct way to articulate this is that: a given piece of C can be translated in countless ways into just one assembly language, and not all those ways may behave the same as each other or as what someone expects. Then, it can also be translated into other assembly languages, including an unlimited supply of imaginary ones. None of the translations define the behavior.

Performance as well as correctness. Looking at generated asm tells you what was inlined, which variables are stored in registers, whether your common subexpressions were optimized, etc. You can often tweak your C code to generate the assembler you want, without needing to actually write asm.

This is especially important in C++, where you depend on the compiler's optimization ability a lot more.

Indeed, sometimes C++ is utterly incomprehensible without looking at assembler output. A subtle bug in C++ can be obvious in a split second in disassembler view.

Alternatively: Understanding C by writing a compiler.

Strong agree. Everyone should do this at least once in their career.

What resources would you recommend to get started with?

The "Dragon Book" is pretty solid and a widely accepted resource: http://en.wikipedia.org/wiki/Compilers:_Principles,_Techniqu...

One of the authors of the Rosalyn compiler has a different opinion: https://news.ycombinator.com/item?id=5149315. And he gives some examples of much better books.

It used to be good, but it is not any longer thought of that way.

I think you'll learn more from porting a simple C compiler than you will from any compiler book, at least given a fixed amount of time to do either task in.

This book, http://www.amazon.com/Compiler-Generator-Automatic-Computati..., which by today's standards is not a very good book, got me started in my compiler career.

And I agree with your basic point that building one is the only to gain true understanding.

If I was going academic and imperative language, I'd suggest this old paper written by The King of Simple Languages and Compilers:

http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf

Very easy: port c4.c to a new language.

This is great. I'll have to brush up on my C too to port. Two birds, one stone :) thank you!

http://compilers.iecc.com/crenshaw/

https://news.ycombinator.com/item?id=1727004

https://code.google.com/p/letsbuildacompiler/

(It looks like there are several more or less complete C versions.)

http://linker.iecc.com/

http://www.iecc.com/linker/

Write a C compiler in assemby?

Once done by the author of MicroEMACS when he was bringing up the C compiler on the pdp-11.

I agree with kazinator: the title doesn't reflect the work. I bet I got something that does: Write Great Code [1]. Hyde helps a programmer understand how the compiler converts most imperative language features to assembler if it's doing it in a direct, lightly optimized way. It often gives C code next to assembler code along with optimizations you can do in assembler but not C. He also wisely created a High Level Assembler that embeds 3GL-style constructs and libraries in assembler code to help beginners learn it piece by piece instead of all at once. Enjoy!

[1] http://www.plantation-productions.com/Webster/www.writegreat...

Another article by the same blog titled "Learning C with gdb" was posted 3 days ago with 24 comments:

https://news.ycombinator.com/item?id=9560708

Learning NIOS ASM was great for learning how to code functional languages too. When you see how much overhead is involved in languages like C for recursive functions that have a simple algorithm, then you start to appreciate the power of functional languages!

Did anyone encounter this error when trying to run gdb with the example progams written in this article?

The error: "Unable to find Mach task port for process-id 13942: (os/kern) failure (0x5). (please check gdb is codesigned - see taskgated(8))"

One nitpick here, if you want a generator style function, you need a struct to hold the state, not a static local variable. Otherwise you're limited to one global function. I can't think of a valid use case for static local variables.

they are nice if you want to switch the behavior of a function at runtime with a debugger. I use them a lot when tweaking the constants in GUI layout code. But I have them behind a macro that switches "static" to "const" in optimized builds.

This is actually how my school's ECE department teaches C and lower level hardware. Its quite nice, actually.

I started with assembly when I was 10. Self taught C at the age of 12. I learned that speed of development is more often the bottleneck than speed of execution...

Appreciating C by learning assembly

Reply on news.ycombinator.com