I'm not sure I follow the second point. Array-based solutions are able to guarantee that an element is never relocated, it's just that std::vector doesn't offer this guarantee. The Boost libraries offer this though, they call it stable_vector.
> Array-based solutions are able to guarantee that an element is never relocated
This is an array of pointers, I mentioned it in the post you're replying to. It completely obliterates the "cache-friendliness" argument, making it worse than linked list (now you have same indirection overhead plus overhead of copying minus benefits of being able to CAS your value atomically into a list making it lock-free)
Yes you're right. Here's an alternative that behaves the way I had in mind but doesn't support deletions, as handling deletions the way std::vector does would naturally mean relocating elements. [0]
I figure it would be possible to add support for deletions, but it would cost us: we would lose guaranteed contiguous placement of elements with neighbouring indices, and (unless no deletions are made) we'd need a private data structure to correspond vector indices to addresses, and to determine where to locate new elements. This would of course bring us back to continually paying the price of indirection overhead, and simple lock-free modifications would not be possible.
My completely unsupported guess is the cache behaviour wouldn't be too bad unless deletions (of elements that aren't at the end of the vector) are common. I imagine the cache behaviour of a linked list must depend greatly on what the allocator gives you. Presumably using a pool, specific to that particular list, could help there.
Naturally the mind races to think of where linked lists are used.
The Linux kernel uses them, at least some of the time they're used with their lock-free RCU pattern. I'm not sure if it's for performance reasons though, I think they're using it in contexts where correctness requires the absence of blocking operations.
I'd expect a lock-free non-linked-list solution would also be possible, but I don't know enough to state that definitively.
Linux is definitely a mix of "It's a linked list because multiple CPUs are simultaneously doing swap operations on the list while it is still in use, with linked lists that's an atomic operation whereas if we did something else it would need a lock" and "C does not provide a growable array type, so I used a linked list 'cos that's easy to write in C"
My guess for the 0.x releases in particular is that there's a lot of the latter and as Linux goes from "Like Minix but I made it in my bedroom" to Serious Business™ more and more of the former.
> My guess for the 0.x releases in particular is that there's a lot of the latter and as Linux goes from "Like Minix but I made it in my bedroom" to Serious Business™ more and more of the former.
In the early releases of Linux, the cache locality argument wasn't as prominent an issue on the hardware of the day. So the computer science textbook argument of O(1) inserts and [if you have the node pointer already] removals was more compelling.
I'm not sure I can answer that about their malloc, now and in the past.
But your question reminded me of another aspect of linked lists in the Linux kernel: unlike a lot of high level languages, there isn't an extra allocation for a node structure. The node structure is a member of the structure being linked.
Often the structure being linked might be something like a reference counted heap object, so the question of adding an extra member to store the next pointer is not a big difference.
> unlike a lot of high level languages, there isn't an extra allocation for a node structure. The node structure is a member of the structure being linked.
That's good, but it seems like how-hanging fruit. Boost offers intrusive_prt for this. [0]
make_shared goes half way, and performs a single allocation to return a shared_ptr to a new object. It eventually made its way from Boost to the standard. [1][2]
See also [3] which contrasts the two. (As you can imagine, intrusive_prt is slightly more efficient.)
Linux uses linked lists because they can reserve a fixed amount of memory for the linked list cells inside the element itself (intrusive list) and they can be allocated non-continguously aka you can freely extend them as you like. This is useful if you want to reserve a chunk of memory statically. This guarantees that you can do work before your allocator is online and then when the allocator is online, you can transparently extend your memory with further allocations.
You can also take independent modules that provide their own statically allocated memory and chain them together using the reserved linked list cells. (think kernel modules)
This is a bit of a wishy washy explanation because I work on a highly adjacent project that has similar constraints but I never looked at the kernel source (strictly working with statically allocated memory during startup).
There's no mention of branch prediction, or context switching, or synchronisation. Depending on what you're doing, they could be very consequential. There's only very brief mention of parallelisation with threads and with SIMD.
High-performance programming is a big topic. The scope is far too broad for a single blog post, which naturally gives only cursory discussion of C++ and computer architecture. The article isn't bad considering, but I do think it's the wrong format. A blog series, or even a book, would be more fitting.
I've not read Fog's Optimizing software in C++ but I see it's freely available there as a PDF (182 pages). Looks like a great resource on these topics.
Learn which instructions SIMD nicely (sqrt / fabs, etc). Use ternaries in loops for masking. Use trig identities and lookup tables (don't recompute sin(3t) when you can use two vector multiples using a table of sin(t) eg. sin(t) * sin(t) * sin(t)). Use divisible constexpr constants in loops to eliminate the SIMD tail. Be careful with type casts and floats. `float x; x += 0.5` will introduce *cvt instructions even if the compiler statically knew better otherwise (use 0.5f). Compile with --fast-math and friends so errno doesn't invalidate your SIMD pipeline.
The compiler no longer guarantees to generate confirming code, so correctness could be affected. If this weren't the case, there would be no need for a flag, it would be GCC's default behaviour.
(I'm not creata, but I imagine this is what they had in mind.)
That has a similar problem to the article, it's trying to fit far too much into too small a format.
What you've written mostly makes sense to someone who already has a solid understanding of SIMD and of C++ (although I can't say I follow all of it), but the target audience is people who don't. For them, each point needs a much lengthier explanation.
Likely the best tip would to `objdump -d` and inspect the assembly then checking performance counters. Prepending (__attribute__((used)) will allow you to inspect your functions.
A quick restrict example:
#define fn __attribute__((used))
fn void copy1(int* to, const int* from, const int size)
{
for(int i = 0; i < size; i++)
to[i] = from[i];
}
fn void copy2(int* to, const int* from)
{
constexpr int size = 1024;
for(int i = 0; i < size; i++)
to[i] = from[i];
}
fn void copy3(int* restrict to, const int* restrict from)
{
constexpr int size = 1024;
for(int i = 0; i < size; i++)
to[i] = from[i];
}
gcc test.c -c -O3 && objdump -d ./test.o
copy1 is 52 lines, copy2 is 28 lines, copy3 is 2 lines (just a call to memcpy).
This is a good starting point for self teaching. The impact of your TLB, L1, and overall instruction count (with IPC) can further be measured with `./perf stat -d -d -d ./a.out`. If you want a quick rule of thumb, no instructions are fast instructions.
creata's comment [0] mentions the works of Agner Fog, which seem very good, and are freely available.
I haven't read C++ High Performance [1] but it looks like it covers the sorts of topics you'd expect, although it looks like it doesn't cover computer architecture in detail e.g. branch prediction. There are books on that too, of course.
I have read 'C++ High Performance', and I recommend to avoid it unless you are interested in reading an STL reference guide with only minimum hints on performance sprinkled in left and right. Or unless you do not know that `std::move` will avoid a copy in some cases, etc.
> doesn't this highlight how mundane and rote teaching has become
The example questions given in the article do not assess wrote learning.
> It's been distilled to the point that the lowest of the lowest common denominators can pass.
Have pass rates been increasing? Unless I missed it, the article doesn't say so.
> forced to learn things they will never use
A computer science degree is not a coding academy, it's a basic grounding in an area of study. A computer science graduate should have some understanding of theoretical computer science and of computer architecture, say, even if they're unlikely to apply these topics directly in their careers.
> My hope is that this is a wake up call to teachers / professors to find a better way to evaluate students. To determine who has actually come away with a real understanding, vs those who were running around copying the assignments off of their peers anyway.
Academics are already aware of the importance of fair assessment, but it isn't easy, especially with LLMs in the mix.
> These same people are now just skipping the peers and going straight to the all knowing oracle. It's the same as it ever was, degree mills.
Students that cheat, and degree mills, are two different things.
I wasn't able to find a definitive account of why they're separated in Ada, but I believe the idea is this: functions are for where code behaves in a roughly functionally pure way and yields a value that should not be discarded by the caller, whereas procs are for functionality with 'deep' side-effects.
The SPARK subset of Ada comes pretty close to enforcing purity of Ada functions, although it still permits them to read globals. [0]
It's not just an oversight. The core of the Ada language was designed deliberately. [1]
> If they had a fire under their ass that made them realize if they don't study well, they will forever be locked into flipping burgers or being homeless, most of them would move their assess.
That strikes me as backward. The higher the expected monetary value of good grades, the more students will prioritise grades over deep learning.
> nobody really understands why a medication works.
But they work hard to try to understand it because the more they do the better the results for peoplea health. Also it goes without saying that if someone didn't understand many of the things that we do understand then things would be worse for us all.
I feel like we just don't understand a lot about the human body still. Only a century and a half ago we had a US president die because a doctor rummaged around and damaged internal organs (with unwashed hands, because germ theory was still not uniformly accepted) to try to find a bullet on the wrong side of his body. We've come a long way since then, but it's not like we've been doing the field of medicine rigorously for all that long. The best strategy we have seems like pretty much the same as any other scientific field; come up with ideas based on what we know, try them out, and see if they work. That doesn't necessarily give us any actual insight into why it works though.
> The medical field as a whole isn’t generally interested in understanding how medication, only in empirical measuring and qualify the effects.
I don't think this is quite correct. I mean many practitioners of medicine will have the attitude of ... "if it works, it works". And that's perfectly reasonable.
But if you understand the mechanism of action of a drug (or other treatment), it (often) makes it easier to improve a drug.
So ... some sectors of the "medical field" understandably care only about empirical results. But other sectors would prefer to understand what's going on.
>The medical field as a whole isn’t generally interested in understanding how medication, only in empirical measuring and qualify the effects.
This is nonsense. Most, if not all professionals are interested in mechanism of action, but without Ms Frizzle, it is extremely difficult and expensive (time and money wise) to figure that out. So while the labs run the experiments with the very limited funding they have, we make do with using the second best thing we have, which are statistics.
We don’t really understand how NSAIDs reduce pain, as a concrete example. In contrast we have a pretty good understanding of the pharmacology of caffeine.
It’s not like magnets, some things really are gaps.
Some medications are designed for one purpose, then other effects are discovered in practice. Gabapentin, for example, was designed as an anti-seizure medication structurally similar to the inhibitory neurotransmitter GABA.
Now it is primarily used to treat neuropathic pain, and the mechanism for that is not well understood. The GABA receptor is not involved. This effect is just a happy accident, and nobody really understands why it works.
reply