Learning C

I spent the last 20 23 days (I just had to optimize some stuff) learning C and completing Advent of Code (AoC) year 2017 with it. Apart from the import file and print functions, I didn’t use any libraries. This is more of a personal log than anything else. Still, feel free to read it. See the unrefined code here

Resources

My friend polomi helped me set up the coding environment. I’d been using Visual Studio Code before, but apparently it’s not recommended for C because of it’s lackluster debugger. I used the regular Visual Studio instead. The Project/Solution system feels obfuscated for now. Maybe it’ll prove useful on more complex endeavours.

polomi advised me to use the Kernighan and Ritchie. Overall, this was a very good recommendation. The material is presented clearly and concisely. The authors focus on performance, rarely mentioning style, leaving it as a matter of taste when they do.

C vs Python

Using C was a big change coming from Python. If I were to describe the differences to a layman, I’d say programming in Python vs programming in C is like ordering your apprentice to do a report versus doing it yourself.

You give them instructions, and because you’ve taught them well they’ll get the job done while minimizing your effort. However, in most cases the report isn’t going to be like you want it done. If you really know what you’re doing, there’s little chance the quality will match what you’d have produced. A lot of times the difference doesn’t matter, otherwise I don’t think Python would be used as much. But when something really matters, wouldn’t you always do the job yourself?

C gets you much closer “to the metal” as they say. In Python, you simply declare a list and trust that the language will find space for it. In C, you need to decide how much space you’ll need. This means you need to get some sense of what memory is and how it works.

I haven’t gotten deep into it yet, but the prospect of learning about the finer points of memory management and how C is translated to assembly is appealing. This was brought on while making use of SIMD for the first time (briefly, SIMD is a trick to do multiple operations in a single CPU instruction) and seeing that my first attempt at it was slower than the naive approach.

I like doing things with limited resources. Both for the challenge and because it’s easier to get a complete understanding of the whole program. I remembered playing KOHCTPYKTOP (original, more recent) and having a blast. Resources are extremely limited there, and I really enjoyed it back then (and present me has absolutely no idea how past me managed to finish it).

Even without any libraries, Python has a lot of powerful tools already at the programmer’s disposal. Sets and dictionaries can be immensely valuable, but you don’t have those in C!
Learning how to make them was a fun challenge. Overall, coding in C helped me appreciate why some things in Python are slow. List slicing on large arrays is a performance killer in my experience. Seeing how it happens C, it being slow makes a lot of sense.

C is incredibly fast. There was one task I encountered where I just knew brute-forcing in Python would be useless (slicing and inserting in a list of 50M integers, I’d ballpark at least 15 minutes?) and it took under 10 seconds in C even with the dumbest algorithm. If you thought this x100 speedup was impressive, how about a x50000 speedup? (from Computer Organization and Design, courtesy of polomi).

All four optimizations add only 21 lines of C code yet speedup matrix multiply by almost 50000, cutting it from nearly 6 hours in Python to less than 1 second in optimized C.

Rudimentary optimization

When I started writing this article, I timed my programs so I could get a nice screenshot at the top of the article.

Initially, the screenshot showed a total time of about 5 seconds in debug mode. Compiling with optimizations brought it down to 2.2 seconds, with most of the run-time on 4 days.
I couldn’t resist the urge to go for under a second, so I improved the worst 3 days (15, 21, 24). Most of it was non-pessimization (removing unnecessary work), but I also did some actual optimization in day 15 using SIMD.

Briefly, this puzzle is about doing multiplications and modulo operations on a set of 2 large numbers (up to 10^11 or so) about 450 million times. There was no way to do less operations. My initial solution took about half of my allotted time at .45 seconds so I had to find a way to improve it.
Modulo operations are slow, so it’s common to look for tricks to avoid them. Because Advent of Code is very well designed (I doubt it was simply luck), all modulo operations involved a Mersenne prime and there’s a trick to speed those up by using bitwise operations rather than modulo!

This trick almost halved the solution time. Using SIMD on the first part shaved a couple more centiseconds to bring the day down to about .22 seconds. Sadly, using SIMD on the second part was slower because there’s no way to avoid bringing the values in and out of the registers often.

It is tempting to go deep down the optimization rabbit hole, but it’s more sensible to move on for now.

Edit from april 13th 2023: Today, I learned that I hadn’t configured Visual Studio properly for a release build. The total time went from .98s or so to just under .7s on the same hardware and without modifying the code!
But I’m glad I missed that back then. I probably wouldn’t have used SIMD otherwise.

Closing thoughts

While I initially balked at the tediousness of some operations compared to Python, I quickly grew fond of using C.
Making my own functions and refining them over time had something to do with it. There’s something about building your own tools and using them successfully (“I made dis”).
Most importantly, I enjoyed the journey and how it lead to a better understanding of how things work.

What’s next? Probably a slightly more ambitious C project.
I’m also interested in a higher-level tangent that’s web-dev related, and a lower-level one. Time will tell!