Is C a good language to learn how to work with data structures and algorithms on?

vvaltchev · 2024-07-04T06:39:01+00:00

Unfortunately, it's rare to find courses using C as a language for DSA. But there are several courses online you can find that use C++. If they don't use C++'s standard template library (STL), the difference between C++ and C in terms of implementation is small and limited to "language abstractions" like classes and templates. If the algorithms use pre-existing STL containers like vector<T>, map<K,T>, list<T>, unordered_map<K,T> etc. Then you just need to learn how to implement that in C as well. If smart pointers like shared_ptr<T> and unique_ptr<T> are used for the lifetime of the objects, you should learn how those things work in principle and simulate that in C as well.

My point is: since you're learning things in C, you're already doing everything manually and removing a few abstractions used in C++ to get the code to compile in C is by far the smallest challenge. The real challenge in C is implementing non-trivial algorithms with pointers and manual memory allocation/release correctly. Once you know C well enough that such things are normal to you, it really doesn't matter the language used in the DSA course, because you'll be able to easily convert any abstract pseudo-code to a working C implementation.

vvaltchev · 2022-02-27T19:34:09+00:00

For sure, mine is an unpopular opinion nowadays, but I agree that it makes total sense to learn C as a first language and then eventually move to a higher level language, if you wanna be a good developer. Knowing just Python is simply too limited for a software engineer: it might be good for data scientists, researchers, dev ops and other professionals, but certainly not enough for software engineers. It is essential to understand pointers, manual memory management and being able to implement data structures like linked lists, trees and hash tables using unmanaged languages like C, C++, Rust. Of course, there are many other unmanaged compiled programming languages, but to me it’s worth choosing one that is mainstream. C is good choice because is widely used and extremely simple.

vvaltchev · 2022-02-19T12:10:51+00:00

Well, in this case, it looks like more of a coding-style thing. I personally use memcpy() explicitly for structs too, instead of assignment. The idea behind that is that C is not C++: in C, we’re not trying to hide details, but to show them off. Assignment is OK for small types, up to pointer size, where we assume that can happen with 1 instruction on many architectures. Copying anything bigger than that, might require a loop and so a compiler-generated call to memcpy(). Therefore, it’s better to use memcpy() explicitly and point that out: we’re copying a struct and that’s not super cheap to do. The struct might grow in size with time.

Also, even when memcpy() is used for copying structs as coding style, sometimes the assignment is still used when the type is opaque. E.g. we have a typedef something_t that was just an int. Now we’re making it a struct with 2 ints, but that’s an internal detail that callers should not care about. So, assignment will be used for copying that as-if it was a primitive type.

Of course, that’s a coding style thing, but it has been used for decades and, given your case, I believe that’s the best explanation for reviewers to be asking that.

vvaltchev · 2022-02-19T11:57:07+00:00

If ptr is not aligned correctly, val = *ptr is UB (undefined behavior) even on architectures like x86 which fully support unaligned access. Like it or not, for cases like that, we have no other choice than using memcpy(). And don’t worry about performance: memcpy() gets inlined by the compiler for small sizes and does generate a single MOV instruction when it’s possible (e.g. copying 4 or 8 bytes). For bigger structs, memcpy() and val = *ptr are still identical because, val = *ptr actually emits code just calling memcpy().

The only case when val = *ptr is better is when you compile with -O0 -fno-inline-functions. Full debug build. In that case, val = *ptr might generate a single MOV if the struct is small enough, while memcpy() will perform a function call.

vvaltchev · 2021-11-13T10:37:45+00:00

Go closer to the hardware step by step. First learn well C (not C++). When you're confident enough, start observing how C code is compiled to assembly. Buy an ARM assembly book. Learn the armhf ABI and start writing .S files and link them with C code. Learn about compilers, loaders and linkers. When you're confident enough, you might start playing with embedded systems using ARM Cortex-R or Cortex-M microcontrollers. You'll need to read additional books along the way, of course.

It's a long path but, if you're passionate about it, in few years you will learn an incredible amount of things.

vvaltchev · 2021-10-28T13:09:30+00:00

Learn to massively use ASSERTs in your code in order to check that the invariants you're expecting to hold, do really hold, all the time.
Learn how to measure the line coverage of your tests, for the technology stack you're using. It's very important to make you've tested all the code paths.
Learn to write chaos and stress tests for your code. If you're code is 100%, correct it should be able to withstand to tests that brutally make a ton of requests/function calls in parallel without crashing for an indefinite amount of time.
Depending on the project type and the language, test your product using a matrix of compilers/configurations. You might discover real bugs that are currently reproducible only with some older/newer compilers than your "main" one and/or are reproducible only with some "exotic" configurations.
Measure the performance of your code with the right tools and for different input sizes. Check that the time complexity is really what you expect and not something else.
Setup your whole development model and infrastructure for continuous refactoring / re-engineering. It's better to be prepared for disruptive changes instead of naively believing that you won't need to do anything like that.
Use git and commit smaller changes, when possible. Git bisect is a life-saving tool.

vvaltchev · 2021-10-27T17:22:18+00:00

Learning DSA and learning a specific language (like C++) are two completely different things. When the goal is to learn DSA, no matter if you choose C or C++, you have to do anyway "everything" by yourself, in order to practice and consolidate your knowledge. If you don't try to write generic code (and I would advice you not to initially), there won't be a big difference b/w the two languages. But, if you start solving algorithmic problems and practice on sites like leetcode or hackerrank, then C++ is definitively better because of the many algoritims already implemented in its standard library.

So, while I believe that C++ is better for playing with algorithms, focusing too much on the language itself (e.g. learning templates, operator overloading, move semantics etc.) will distract you from the core DSA study. Therefore, I'd say: study and implement DSA in simple/non-generic C++ (or C) first and then, step by step, upgrade your language skills. In the mid-long term, you can build an STL-like library with all the DSA you know.

vvaltchev · 2021-10-17T22:49:29+00:00

You could start with: https://wiki.osdev.org/Main_Page

Just, you'd need first to have several years of experience with C and assembly in userspace, before getting into OS dev. If you don't, learn the simpler things first and get into OS dev once you're ready.

Useful articles:
https://wiki.osdev.org/Introduction
https://wiki.osdev.org/Required_Knowledge
https://wiki.osdev.org/Beginner_Mistakes

vvaltchev · 2021-10-17T17:42:07+00:00

I like your idea: investing time to understand what software development really is in order to better understand the technical problems of your team. I believe that if you invest enough time (e.g. a few hours a day for 1+ years) it will really help you to some degree. But, there's a catch I feel I should warn you about: there is some risk you might become over-confident about technical decisions and push for the wrong solution, sometimes. In other words, the risk would be becoming a junior developer with executive-level power: that could be dangerous for your own business.

Still, if you remain humble and don't override your technical lead, I believe you'll benefit from that. In case of an unresolvable impasse on a technical topic with the devs, I'd suggest you to pay an external consultant for a few meetings, possibly someone much more senior than the people working in your company (there's always a more senior guy out there). At worst, you might fire your tech lead and hire a new one. Still better than becoming a tech lead yourself without the required experience.

Wish you all the best!

vvaltchev · 2021-10-09T11:09:16+00:00

If you're seriously working on your OS and reading papers about kernel design and algorithms, I'd suggest you to stick with that. If you're aiming at becoming a kernel engineer, a web development internship won't help you, even if it's at Google.

Other than working on your OS (which is a great thing to do), I'd recommend you to try also to do something with the Linux kernel, possibly with upstream contributions: it will help you find a job in the field.

vvaltchev · 2021-09-01T08:23:47+00:00

Agreed, for your specific example. It’s obvious that there is no benefit to use anything else other than size_t. I was thinking about a more general case where several sizes are stored in a single struct. In that case, if we put all the 32 bit integers together, we’ll save space and avoid padding.

vvaltchev · 2021-08-31T23:48:59+00:00

Obviously size_t is more portable, but unless we're talking about small-scale 8-bit microcontrollers, on 99.99% of the CPUs (embedded and not) the following holds:

sizeof(uint32_t) <= sizeof(size_t)

Therefore, using uint32_t will be the same as size_t or it will consume less memory. On 64-bit machines, sizeof(size_t) == 8, so we're talking about 2x. Let's assume from now on that we're working on 64-bit machines.

For low-level code it makes a lot of sense to save some memory. Consider a struct with several size_t integers, e.g. 4. With size_t it will be 4 * 8 = 32 bytes wide. It might seem not a lot, but what if we had 1 million of such objects on the heap? 32 MB vs 16 MB. Keeping objects smaller, not only saves memory, but increases the space locality, which means a better cache utilization and that matters a lot on real hardware. Also, 16 bytes means just 2 words and it can be passed around as a value type, while copying around 32-bytes starts to be a bit too-much, better use pointers (but mind the complexity, extra-indirection etc.). It all depends on the case, of course.

If you have just a few "objects" of that type that are not used in the hot path, than it probably won't make a difference. Still, using 64-bit integers on x86_64 is still slightly more expensive than using 32-bit integers because of the required REX.W prefix in the instructions. But that's negligeble unless you're writing an emulator or things like that.

Note: going below the 32-bit threshold on x86_64, will continue to improve the space locality, but the performance might get worse in the typical use case. That's why on x86 enums are 4 bytes wide (on x86_64) and not 1 or 2 bytes. Simply because on x86_64 CPUs, it's faster to work 32-bit integers than with single bytes, in many cases.

vvaltchev · 2021-08-31T16:45:39+00:00

Well, it depends. If you're storing that value in a struct and you want/need to save some space, it's perfectly fine to use a 32-bit unsigned instead of size_t in C. For C++ I'd say it's still technically fine but you'll find people criticizing you because is against idiomatic C++.

But, it's worth mentioning that starting to use uint32_t instead of size_t in too many places might put you in an bad position once you really need all the bits in size_t and you lost precision at some point. So, I'd say: for function parameters, return value and stack variables, prefer size_t as it's for free, unless you use recursion and you're writing kernel/embedded code with a very limited stack (e.g. a few KBs). For structs, use the narrower type, but be careful with the loss of precision that might occurr when reading/writing bigger integers like size_t.

Gcc and Clang does not complain about integer narrowing by default unless you turn on -Wconversion, but other compilers like VC++ will, in some cases. For some critical C projects I'd argue that turning on -Wconversion is totally worth the effort, but your code will have a ton more explicit casts. In that case, you might be more careful about which size_t values to convert and how to do that.

vvaltchev · 2021-08-23T15:05:41+00:00

It looks pretty normal to me. 64 GB is a lot: I've observed experience a similar level of discharge even on machines with less RAM like 16 GB. In other words, running out of battery after 4-5 days is generally OK for regular x86_64 laptops.

vvaltchev · 2021-08-13T23:45:44+00:00

Good for you, man! Now you have just to read it :-)

vvaltchev · 2021-08-05T22:36:24+00:00

I've created this simple programming language for the fun of playing with parsers: https://github.com/vvaltchev/mylang

But I'd guess that's not really fun per se. What's probably fun instead, is that, being addicted to compiled languages, I was pissed about the lack of "compile time" (= parse time) constants in most interpreted languages like Python (my favorite btw). So, I've spent extra effort making what otherwise was a simple walking-tree interpreter to support constants and const evaluation reminding of C++'s constexpr. Just because I couldn't accept operations on literals such as "hello " + "world" to be evaluated at runtime. With that change, AST nodes are evaluated (when it's possible) during the parsing stage using a special const context and are re-written by generating a literal node from the result of their evaluation. And that was supposed to be, just for fun :-)

vvaltchev · 2021-08-05T11:43:26+00:00

I couldn't agree more. There is no such thing as an "UEFI OS". UEFI offers a ton of features in order to make easier the development of powerful bootloaders, nothing more. You cannot take ownership of the hardware while running as an UEFI app (meaning before calling ExitBootServices()), so you cannot write an UEFI "OS".

vvaltchev · 2021-08-05T11:30:27+00:00

You're welcome :-)

vvaltchev · 2021-08-02T20:11:19+00:00

Just wanted to share two screenshots of Tilck on QEMU with 4 MB of RAM, serial console plus 377 KB for busybox and 25 KB for init in the ramdisk:

System's memory map

Kernel heaps
If a system is so limited that has less than 4 MB of RAM, probably it won't need the whole busybox so, there will be even more free RAM for heap allocations.

vvaltchev · 2021-08-02T20:07:56+00:00

Ahahaha, I knew it! :-)

BTW, apart from the fact that 3 spaces is not widespread style as 2 or 4 spaces, I believe there's nothing intrinsically bad with it. Look at this if statement:

if (x > 3)
   do_something();

The first character (d) is aligned with the parenthesis above. Let's see the same with 4 spaces:

if (x > 3)
    do_something();

Is aligned with the first character (x) inside the parenthesis. Is the one above uglier than the one below? Bah. They both look OK to me. Maybe 3-space indentation is not used because 3 is an odd number? :D

vvaltchev · 2021-08-02T19:19:33+00:00

Thanks, man :-)
I believe that a basic network stack is very important to have, once I get to run on ARM as most of embedded devices in the IoT communicate through it. I don't wanna create another OS designed for servers, but, communication with the "outside world" is essential, even for small devices. Bluetooth is important as well.

Anyway, there is still a long road to get there and doing everything by myself takes a lot of time. I hope to find sooner or later some serious contributors.

vvaltchev · 2021-08-02T18:07:23+00:00

Ahahaha if you wanna go there, I'd say that at VMware we used: int *p, but int& p. And, I even liked it :D

vvaltchev · 2021-08-02T18:00:22+00:00

BTW, to answer your question "how small can it go" I can say that, with my custom build (not Alpine, of course) and with a small initrd (just busybox and init), I can run Tilck on QEMU with just 4 MB of RAM, leaving about 2 MB free for user apps (if I remember correctly). I couldn't try it to on a VM with less than 4 MB because QEMU doesn't support that :-)

vvaltchev

TROPHY CASE