How to Make a Computer Operating System in C/C++

I disagree. CompSci is mainly userland.

Most EE courses these days have the majority of a comp sci course built in. MIT actually blur the line between both. Pure comp sci will not help you understand why your RS485 bus drops have noise, why your serial wont sync and how to get stuff off an SPI bus by bit banging. It's all analogue at the bottom of the stack as well which is why embedded systems people still have scopes on their benches.

Comp sci only people shit a brick when you lug the scope onto the bench and crack out the probes.

The Arduino teaches you to do so many things wrong that its almost dangerous and requires a lot of unlearning. Build an AVR programmer and use gcc fine but lose all the arduino crap over the top and gain JTAG debugging, single step, more memory (!), full IRQ control, timers etc that aren't under a layer of crud. Oh an ISR that runs in under an hour as well, CMT. I could go on for a week.

For ref, you won't find a job writing software for or using an Arduino or a Pi either. FPGA yes, ARM SoC yes, AVR maybe, PIC maybe, x86/PC104 yes.

I disagree. Will reply later, too long mto reply on my phone.

To further prove the point about cache locality:

https://www.youtube.com/watch?v=0iWb_qi2-uI&t=44m50s

> 1: you care about ordering - often you don't care about ordering and in that case, there is no need for a linked list because you can achieve O(1) insertion & removal then too: insertion can always be at the end, removal can be a "swap with end element, remove end element" operation.

Whether you care about ordering or not, linked lists work great. Adding to an array is only amortized O(1). It is worst-case O(N). Why pay O(N) for the worst case when you can pay a cheap O(1) always?

> 2: inserting and/or removing from the middle of the list is a common operation, if it is not a common operation, then the added cost of doing so with a vector may still be outweighed by a vectors other advantages

Deleting from the middle of the list is an extremely common requirement, when you have objects that need to be enumerable in some order[s] and sometimes deleted.

> 3: you do not require random access - lists do not provide random access and lookup is O(n). At the expense of additional complexity in implementation and more memory overhead, you could reduce lookup to, OTOH, O(log n) by using a skip-list

Here is a false dichotomy dictated by the STL. With intrusive lists, you can have both your vector and lists of various orders. There is no contradiction.

When you need indexing, use a vector. When you need quick add/remove, use lists. When you need both, use both.

> 4: you do not iterate through the list often - if you do, you are likely going to blow the cache and mess up prefetching due to poor cache locality. Iterating through an array-based data structure can be much faster in this case.

Yes, if you want quick (repeated) enumeration, put it in a vector. Again, this doesn't contradict also putting it in lists.

> The biggest issue they seemed to mention, though, was cache locality - I fail to see how intrusive linked lists solve this.

Cache locality is based on your use pattern. When enumeration isn't your common operation, vectors don't have better locality than lists. For example, a sorted list of requests where you may want to time out the oldest one will only refer to the head and tail of the whole list. Cache locality is great.

> then you end up jumping around the preallocated nodes anyway and after a while will lose any cache-friendliness you may have had.

You don't need to jump around. Say you have a request object you found via a hash table. After handling it you decide to destroy it. You now want to delete it from various lists it is in. You can do it on all lists in O(1) for each list. This is relatively cache-local (only need 2 extra random accesses, potential misses, for each list).

> C programmers are trained to use linked lists. They are the first variable-length containers most programmers come into contact with and so C programmers tend to be imprinted on them like ducklings. Linked lists are a poor general purpose container.

I think the false premise here, espoused by the STL, is that a data structure is a "container" at all. Your data can be "contained" by anything (the stack, the heap, a vector, ...). The data structures involved (linked lists, hash tables, search trees) all do not contain the data. They organize the data.

When using vectors as containers STL-style -- you cannot really have your data organized by multiple data structures efficiently.

I regularly have my data objects within a hash table, a list, and a search tree simultaneously and efficiently, with no dynamic allocation to sustain any of that.

STL cannot do this because of the data-structure as "container" philosophy.

EDIT: Also read my other comment detailing why std::list is lacking the most fundamental properties expected of a linked list: https://news.ycombinator.com/item?id=6830526

std::list can be used in 2 ways:

* With an std::list::iterator in each of your data nodes that represents its own position in the list (this is called the "intrusive style")

* Without an std::list::iterator in each of your data nodes

If you use the (more common) latter form: whenever you have a reference to your own object, you cannot do any of the linked list operations without an O(N) penalty to go and re-find your element in the list!

i.e: Say you have a list of requests, and a timeout callback pops up with a pointer to your request, you cannot use a request pointer to do an O(1) deletion from the list. This kind of operation is what lists are for, and std::list canonically cannot do it.

Any other operation you might want to do relating to the list, given such a pointer is impossible (e.g: create a new request that is immediately between the old request and its next).

All this assumes your object is within just one list. If it is within 2 lists, you have to use an extra indirection: std::list <request * >, which makes the problem worse. Even if you do find your request via one of the lists, there is no way to get an iterator for the other list. That means you cannot do any of the list operations on the other list. Again: This is the canonical thing lists were designed for, and std::list cannot do it.

Say that to solve this, you use the intrusive style with std::list. i.e: for every list this object is a member of, you hold an iterator inside your object.

Now the onus is on your to maintain these iterators, in addition to the common list operations. i.e: If you add an element, you need to both call std::list::add, and update the iterator.

Additionally, instead of paying with 2 pointers for each node, as an ordinary doubly-linked list should cost, you have to pay with an extra pointer or two (depending on how the iterator is implemented)!

If you use multiple lists with std::list<request * >, you pay with an extra pointer yet!

So if your data structure is within 2 doubly-linked lists, instead of paying the ideal 4 pointers per item, you pay those 4 + 1(indirection) + (2 for two iterators). 75% memory overhead, ruining your cache lines.

The code will be a mess too, due to the duplicate maintenance.

The alternative is much simpler: http://www.cs.fsu.edu/~baker/devices/lxr/http/source/linux/i...

Use the intrusive approach exclusively. So that you don't need to use a list::add in addition to maintaining the two iterators. You only maintain the "iterators" (now called "list heads").

So your request would look like:

  struct request { struct list_head list1, list2; };

To add it to a list:

  list_add(&request->list1, &some_list_head);

Given a request, you can delete it in O(1) from both lists:

  list_del(&request->list1);
  list_del(&request->list2);

Easy to use and optimal memory use (exactly 2 pointers per list head).

Now, given some pointer from list2, to get back a request, you use:

  struct list_head *some_ptr = ...;
  struct request *req =
    containerof(some_ptr, struct request, list2);

This is slightly-boilerplatey, so I tend to write a little wrapper:

  struct request *request_of_list2(struct list_head *ptr) {
    return containerof(ptr, struct request, list2);
  }

EDIT: almost completely forgot that std::list also uses new to dynamically allocate elements. This effectively means the cost of adding to lists is many times greater than the simple list_add function. Even if you supply your own allocator, this is unnecessarily expensive and by default means that list::add, like remove, are both not O(1) like they ought to be.