The reason that C programs often don’t perform as well as an equivalent rust program[1] is that it’s so incredibly hard to do anything at all in C (especially something reliable) that one can usually only do the simplest thing possible and this typically means simple data structures, simple algorithms and arrays
[1] suppose the programs are independently created at the same time by programmers of equal ability and are idiomatic in their languages. If a C program is rewritten in rust, it is likely to be faster, but that would likely also be true if it were rewritten in C.
Brian Cantrill talks[1] about exactly this: in his C version he was using AVL trees because they are easy to implement, while his Rust version was using B-trees just because he could. And as a result, his naive first attempt in Rust outperformed his long-optimized C code.
Out of interest though, does he mention somewhere which actual implementation he used?
If you really need a Btree (like, if you want to make a fair benchmark for a presentation) then you'll absolutely find a reasonable implementation in C. After all, why would you need dependency management for something that should have 0 dependencies?
As an example of library data structures implemented in C - if you want, check out my Red-black tree (not a Btree): https://github.com/jstimpfle/rb3ptr/blob/master/rb3ptr.h . It's really easy to integrate into your project. I think the API (found in rb3ptr.h) is totally usable, and it might also be faster than what you can get with safe Rust - unless you can easily use intrinsically linked data structures in safe Rust.
Reliability is very often the name of the game with C, and part of the reason you might see it written in such a simplistic fashion. In embedded systems, we often follow very strict code convention that has strict requirements on how a C program is to be written. This includes everything from how memory is to be allocated, the maximum number of local variables, the maximum number of the arguments, various limits on a function, constraints to handle errors, etc. We do this because it minimizes potential hazards especially when working with limited memory and system resources.
C is an unforgiving language in that mistakes can occur silently and on mission critical hardware these mistakes can cost more than just your project milestones. These programs are very specialized and often have complex algorithms associated with them. Most of the systems I've worked with include various kinds of feedback control systems, and accompanying algorithms. If you're familiar with control systems, you'll know these algorithms are certainly not trivial by any means.
The challenge with C is more as a developer your C code needs to be perfect. Bugs just aren't an option like they are in other environments. Once a specialized piece of hardware ships it needs to work as intended under a myriad of conditions without powering off for the next 30 years (not always the case but more often than you might think). Sometimes this kind of software is going to be put a position it may have never been designed for. The best we can do is try to add various check/support mechanisms both in software and in hardware, and maintain as safe and hazard free software as possible.
In terms of performance, again coming from an embedded environment, there is almost always a spec we are aiming for. It needs to do X tasks in N time for example. Of course high level design questions like whether to poll or wait for interrupt, or how to broker data from shared resources is decided long before you get to the question of how should I, or if I even should, compare two strings. It is nevertheless advised to go with a trivial solution if the ends satisfy the needs.
Is C time-consuming to write? Is C a "hard" language? These are subjective and depend on the nature of the project. I would certainly never use C with only libc to write a webserver that's going to be serving SaaS Co's backend API.
C is a tricky beast to tame.
``` bool b; if (b) printf("1 "); if (!b) printf("2 "); ```
might print `1 2 `.
To my knowledge there is no C compiler that promises to always handle all forms of UB consistently. The closest you could get would probably be something like Valgrind.
Use your brain and use your tools. C is not really that hard for a large number of problem sets.
If their salaries cannot find them, where are they?
Do we have a candidate to prove their secure reports as being wrong?
In an embedded context, such bugs may be extremely costly to fix, if it's even possible.
> modern compilers will flag uninitialized variables
Reading uninitialized variables is one of the more easily prevented forms of undefined behaviour. As pjmlp points out, undefined behaviour in C/C++ programs is one of the major sources of security vulnerabilities in today's software.
I assume most C++ programs heavily use more of these advanced data structures, correct?
Because of that, it is usually pretty easy to substitute an optimized algorithm or a container for another one with minimal code changes. In C, because there is no standard for how to do containers and algorithms, it is likely that every library does something a little different in terms of conventions making it harder to swap in implementations.
Every large scale C code base I have worked on has had these things, and they were used as you say all over the place. If I were to encounter a code base that didn't have these things I would wonder why it was written in C in the first place.
> Be kind. Don't be snarky.
> (…)
> When disagreeing, please reply to the argument instead of calling names.
> (…)
> Please don't post shallow dismissals, especially of other people's work. A good critical comment teaches us something.
You’re being downvoted because your comment doesn’t add to the discussion. You’re (rudely) telling the parent poster they are wrong while providing no basis for the assertion.
In many programs in many domains the sizes of these data structures will rarely exceed this limit.
I have no idea whether that matters or even easy to measure...
It is reasonably easy to measure, and the GP is about right. I've measured a crossover point of around a few hundred items too. (Though I'm sure it'll vary depending on use case and whatnot.)
I made a rope data structure a few years ago in C. Its a fancy string data structure which supports inserts and deletes of characters at arbitrary offsets. (Designed for text editors). The implementation uses a skip list (which performs similarly to a b-tree). At every node we store an array of characters. To insert or delete, we traverse the structure to find the node at the requested offset, then (usually) memmove a bunch of characters at that node.
Q: How large should that per-node array be? A small number would put more burden on the skip list structure and the allocator, and incur more cache misses. A large number will be linearly slower because of all the time spent in memmove.
Benchmarking shows the ideal number is in the ballpark of 100-200, depending on CPU and some specifics of the benchmark itself. Cache misses are extremely expensive. Storing only a single character at each node (like the SGI C++ rope structure does) makes it run several times slower. (!!)
Code: https://github.com/josephg/librope
This is the constant to change if you want to experiment yourself:
https://github.com/josephg/librope/blob/81e1938e45561b0856d4...
In my opinion, hash tables, btrees and the like in the standard library should probably swap to flat lists internally when the number of items in the collection is small. I'm surprised more libraries don't do that.
If I recall correctly, the STL provides guarantees that prevents it from taking advantage of flat lists. I think some containers (not arrays) guarantee that they don't move the address of whatever they're containing, even if you insert or remove elements. Even if they switched to flat lists, it would be a flat list of pointers, with all the incurred overhead.
Likewise, I believe I have heard of small string optimisation being impossible with std::string for similar reasons.
not impossible, SSO is implemented to some extent in most mainstream c++ compilers.
are you maybe thinking of iterators? you have to assume iterators are invalid after a move.
EDIT: seems I was wrong, and SSO is allowed for std::string. A similar optimization is illegal for std::vector, though, for the reasons I gave above.
When I changed the hardcoded node size from 136 to 1024 bytes, time went down from 3.6 secs to 2.6 secs on my laptop. It kind of plateaued at 1024 bytes. I didn't do more extensive testing.
What's the rationale for the choice of 136? A cache line is usually 64, so the CPU will always end up loading a multiple of that in any case.
When I did a rope implementation myself (I don't know how it compares in terms of performance) I think I ended up with nodes of 4096 or 8192 bytes size. That was based on a Red-black tree. When I load ~1Gig of data, even with a node size of 4096, there will still be 2^18 nodes, meaning each access requires sth. like 17 child traversals, which seems a lot to me. So I can't see myself going down to 200 bytes or less.
https://ridiculousfish.com/blog/posts/array.html
In the sense of swapping the underlying implementation as the number of items in the collection increases.
I suspect for this reason it'd be better in Rust to use a Go-like hash map implementation [1] that keeps all the key/value information (size, Hash and Eq implementations) in a vtable-like form rather than be monomorphized, except in really hot inner loops where the specialization is worth it. There was an interesting article and discussion on reddit relating to this [2] where someone made a toy type-erased map (though not as nice as Go's) to measure the difference in compilation times. Maybe some day I'll make a more production-ready attempt...
[1] https://dave.cheney.net/2018/05/29/how-the-go-runtime-implem...
[2] https://www.reddit.com/r/rust/comments/g1skz4/an_experiment_...
Would you maybe if there's any source discussing how this is solved in different languages and performance consequences of it?
* In many languages, monomorphization is impractical. Eg, in C it requires macros or external code generators. Java and Go don't even have macros. So it's rarely done. Instead, stuff uses type erasure, dynamic dispatch, more heap allocations, and tables like the ones described in that dave.cheney.net link. Maybe some JITs or even some ahead-of-time compilers do monomorphization internally in some cases, but I'm speculating rather than speaking from knowledge.
* In C++ and Rust, monomorphization is easy. You don't have to do it, but it's easy, so many people do. The containers in the standard library are monomorphized. This code can perform very well in any particular case, but in aggregate it's large enough that I have doubts about whether it's always worth it for the whole program.
L1 and L2 are per core. A cacheline is 64 bytes and per-core cache size is on the order of 32kb and 256kb for L1/L2.
Reading data from L1 is on the order of 1 nanosecond (or less) and RAM on the order of 50 nanoseconds.
If you’re scanning an array and load a dozen cachelines that’s almost certainly preferable to several cache-misses (and lines).
Memory access is very often an application’s bottleneck. The answer is almost always more arrays and fewer pointers.
The number of people who dismiss the lowly array is way too high. Arrays are fast. Keep your data in the cache and they're 10x or more faster than normal, and plain flat arrays are almost always faster than literally any OOP nonsense. By "almost always" I mean that I've never once encountered a situation where flat arrays weren't the fastest solution attempted, and I haven't seen everything, so I can't claim they're always fastest.
People really don't understand how fast their computers really are, thanks to developers not caring how fast their code is.
Linear arrays are often faster, not because they require fewer memory loads, but because the cache has intelligence built in (the prefetcher) that loads some memory in advance even before the code requests it. That intelligence works way better with linear array scans than with pointer chasing. (I'm not sure if these loads will count as cache misses or not).
Yes, for large enough N, a BST easily beats linear search.
You are shifting goalposts. What the parent poster said is that a linear scan will read more memory than a binary search, therefore it will cause more churn in the cache (assuming same cache policies, which I don't know is a safe assumption), therefore linear scan may actually be less cache friendly - given that you're not interested in the data in any other way besides for the scan - by way of putting other parts of the program whose data was pushed out of the cache at a disadvantage.
Implied was also that linear scan might actually result in a slower program, even if the scan itself might be faster than a binary search.
What you replied is "The CPU will load less cache data with linear searches", which I assume to be false, although I will be happy to learn that it's actually the case (for example because the CPU has a clever cache eviction policy, executing linear scans by streaming in memory into a small part of the cache instead of thrashing the whole cache).
Let's say we have an array of 200 4-byte ints. Let's do a linear array scan and on average will touch 100 of them (or about 7 cache lines). Now let's say we have each integer in its own linked node in a BST in a totally random memory location. We can expect to need about 7 steps as well (2^8 = 256 > 200), which is 7 cache lines. So about 200 is already a lower bound where BST is more efficient in terms of visited cache lines, even for a pessimistic inefficient data structure like this 4-byte integer example.
Doesn't that mean that null terminated strings is idiomatic C? That is, my understanding of the term idiomatic is that it is defined by whatever is most natural to users of a language regardless of whether it is the most performant.
It would be the equivalent of teaching people to write books without encouraging them to read anything.
To break myself of the habit I started reading some well regarded programs for fun. And oh boy, have I learned a lot from doing so. One of my first discoveries was this beauty in the Redis source code:
https://github.com/redis/redis/blob/3.0/src/sds.h
The idea is to have a string struct that stores its length and content. But the pointer passed around is a pointer to the (null terminated) contents field in the struct. The string is efficient for internal calls (the length can be queried by subtracting from the pointer). But the pointer is also an idiomatic null-terminated C string pointer, compatible with the standard library and everything else. (typedef char *sds;)
Dovecot is also a gem to read if you're looking for inspiration. The way it manages memory pools is delightful - and I'm sure much more performant than idiomatic rust. (That is, without reaching for arena allocator crates and alternate implementations of Box and Vec).
I have no problem doing that if I need to. But it feels like I'm fighting against the grain of rust more than I'd like.
In my experience most of the time you need arenas you’re using your own data structure anyway, but YMMV.
That makes sense for video games. Recently I was goofing with cyrus-imap. I wanted to parse the emails out of an mbox file into JSON (JMAP). Parsing an email with cyrus currently does about 5-10k calls to malloc, but the objects are all extremely short lived - they just have to live long enough to parse and then convert to JSON. This is a perfect case for a bump allocator - I'd love to allocate all the parsed email fields into an arena and then clear the whole thing when we move on to the next message.
Yes, Cyrus uses a ton of its own internal structs for emails, and they're littered with strings and vectors. (Eg for email headers, lists of email recipients, plain text / HTML message content, etc).
Looks like bumpalo will do the job, since it implements its own Box, Vector and String. I understand why, but it seems jarring that I'd need to replace the data types in order to change out the allocator like this. I'm definitely keen for GAT landing if it means bumpalo and friends don't need to reinvent the world to be able to change the allocation strategy.
Edit: Oooh Vec::new_in is in nightly! Exciting! https://doc.rust-lang.org/beta/std/vec/struct.Vec.html#metho...
https://rust-lang.github.io/rfcs/1398-kinds-of-allocators.ht...
I'd either start at a query entry point, or find the email delivery path or something. Or skim through the files and see if anything catches your eye. Or invent a question for yourself - how does X work (for some X), and see if you can find that part of the code.
Wherever you start, explore around a bit then go deep. See if you can understand for yourself how some small, interesting part works (by tracing out the various structs and function calls). Understanding how the whole program fits together is a separate skill - but don't worry too much about it.
Personally I fell in love with the code in src/lib/memarea and mempool. The way dovecot handles memory pools is super clever. There's also lots of src/lib-X directories, and they're reasonably self contained if you want to skim that list and find something more focussed.
If you haven't read much code before and dovecot feels too big and scary, start with something smaller. I can also recommend reading the sourcecode for git or the code for redis. Oh, and if you do, do yourself a favour and checkout one of the earlier versions of those projects. The lines added early in a project's life are usually more succinct and important compared to lines added later on. So earlier versions are usually better reads. When I read redis, I think I read the code for redis 2.0 or something.
I know because I run a userland that uses length-prefixed strings as far as possible: https://github.com/akkartik/mu
You get a null terminated char array but the length is actually available since arrays (as long as they haven't decayed into pointers) can still share their length at compile time.
You could do some macro magic instead of templates e.g. `DEFINE_QSORT(int, intcmp)` which could stamp out `qsort_int` but that's not a part of the stdlib.
C++ arguably gets this right since sort<int> and sort<string> will be separate functions, although templates are of course a footgun. And of course duping the logic for std::sort<T> for a bunch of different T impls increases the binary size.
When this is done, the compiler can inline qsort, and replace the indirect function call with an inlined version of intcmp, and then things are equivalent.
In that case, the compiler could make a specialized qsort using intcmp automatically.
In my similar experiments with std::sort with a function pointer only gcc does this with -O3.
One library I have exploits the fact that D templates are embarrassingly better than C++'s, so you can actually benchmark a template against it's parameters in a clean manner without overhead - that could be anything from a size_t parameter for a sort or a datastructure for example.
enum cpuidRange = iota(1, 10).map!(ctfeRepeater).array;
@TemplateBenchmark!(0, cpuidRange)
@FunctionBenchmark!("Measure", iota(1, 10), (_) => [1, 2, 3, 4])(meas)
static int sum(string asmLine)(inout int[] input)
{
int tmp;
foreach (i; input)
{
tmp += i;
mixin("asm { ", asmLine, ";}");
}
return tmp;
}
edit: https://github.com/maxhaton/chimpfella - I haven't bothered to add pmc support yet
When I once tested std::sort against qsort (sorting 4-byte integer) I measure a 2x difference. So yes, definitely non-trivial, but it won't get much worse than that.
Have you ever seen a program that was slow because of a slow sorting routine?
If you ever need a fast sort (~ never) then the last thing you should do is use std::sort anyway. You should figure out what your data looks like and hand roll an implementation. For example, a radix sort is often possible to use, easy to implement, and much faster than std::sort.
What is meant here? Fast? Reliable? Secure? Memory efficient? Power efficient? Easy to write? Easy to maintain? Quick to compile? Easy to debug?
I have no illusions about the reliability/security/correctness of real-world C code, especially since it's usually not compiled with a memory-safe compiler or run with memory-safe libraries and runtime environments (though it's often sandboxed to limit the damage.) It's relatively easy to introduce memory errors which are not detected by the compiler or runtime.
Certainly many algorithms and data structures (in C and other languages) exhibit tradeoffs including things like speed vs. memory use vs. code size vs. complexity, etc..
But C compilers are pretty fast, which I really like. Then there are/were environments like Turbo Pascal or Think C, which seem to have been amazingly compact while offering a rapid edit-compile-debug cycle as well as decent runtime speed and code size.
"Less performant" seems like a less clear (so to speak) way of saying "slower" (or maybe "less efficient" or simply "worse" in some instances.)
Those two features make for big speed improvements.
I agree, C is a really poor choice for string or other human readable content handling.
But if you have to read-shift-mask-write bytes to hardware control registers, it is a pretty easy language to use, and faster than assembly language in 90% of the cases, with modern compilers. That last note was less true in the mid 1980s, but by the mid-1990s, compiler optimization had gotten to be quite good.
Cellular modem code that runs on DSPs is written in C. Maybe someday that will be written in Rust. We'll see.
for (int i=0; i < 10; i++)
There is a culture of bad C code from the 90s - especially C code written in OOP-y ways where that was never necessary. Like, calling malloc() + free() for every little thing instead of more structured memory management. A lot of that code is written in C not with a efficiency or elegance mindset but simply because C was the language that you wrote programs in.
Do not tie computational operations on string operations in C.
Pick one of many string manipulation libraries to do any serious work with them.
Rust avoids those from the start by making slices idiomatic.
Another thing I commonly see is the usage of suboptimal containers (like arrays with linear search) - just because it’s there’s no better alternative at hand (standard library doesn’t offer ones and dependency management is messy). Which also makes it less surprising that code in higher level languages might perform better.