12 ms·
Apart from those benchmark games a lot of real world C is a lot less performant than people think it might be. I spent a fair amount of time reviewing C code in
by Matthias247 6y ago
Apart from those benchmark games a lot of real world C is a lot less performant than people think it might be. I spent a fair amount of time reviewing C code in the last 5 years - and things that pop up in nearly every review are costly string operations. Linear counts due to the use of null terminated strings and extra allocations for substrings to attach null terminators, or just deep copies because ownership can’t be determined are far more common than exceptional. This happens because null terminated strings feel like idiomatic C to most people.
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.
- martincmartin 6y agoAlso lack of generics can make it slow, e.g. qsort() requires a function call for each comparison. So C++'s std::sort() can be significantly faster on an array of integers.
- mh7 6y agoIt's more to do with the fact that std::sort's definition is visible to the compiler and qsort() is not. Put qsort() code in stdlib.h, make it static and write a static intcmp() and you'll see the compiler inline that no problem.
- ryanianian 6y agoSure you can hard-code intcmp into qsort but then it would only work for arrays of ints. 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.
- marvy 6y agoI think mh7 did not mean to hard-code intcmp into qsort. The idea is to move the definition of qsort directly into the stdlib.h header file. That way, the compiler can see the definition of qsort and intcmp at the same time. In that case, the compiler could make a specialized qsort using intcmp automatically.
- TheNewAndy 6y agoThe poster you are replying to didn't suggest hardcoding intcmp into qsort - just making it so the implmentation of qsort is available to the compiler when the comparison function is known (i.e. just like with C++). 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.
- bluGill 6y agoOnly if inlining qsort is best. Sometimes it is sometimes it isn't, based on complex rules that I trust the compiler to know.
- deleted 6y ago[deleted]
- deleted 6y ago[deleted]
- jjgreen 6y agoI've done this a few times using http://www.corpit.ru/mjt/qsort.html http://www.corpit.ru/mjt/qsort.html
- steerablesafe 6y agoI'm skeptical. I doubt that the whole of qsort gets inlined (it's big), and the best the compiler can do is to clone qsort to const-propagate the function pointer for it to get inlined. In my similar experiments with std::sort with a function pointer only gcc does this with -O3.
- bluecalm 6y agoI benchmarked it several times in the past and couldn't replicate std::sort being faster (GCC with high optimization settings). Anyway both are slow. If you need fast sort you need an implementation without any function calls (no recursive calls) and both the pivot choice and the chunk size at which insert sort kicks in optimized to your data and hardware. My experience is that you can beat built in sort by 2x to 3x.
- lumost 6y agoHow would you perform this optimization? If it’s the same data getting sorted, why not put it in an ordered data structure?
- mhh__ 6y agoAndrei Alexanrescu has a talk on doing this - he calls them metaparameters e.g. where a hybrid sort chooses to change algorithm. 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; } This made-up (pointless) benchmark measures how insert a number of cpuid instructions into the loop of a summing function affects it's runtime. My library writes the code from your specification as above to generate the instantiations and loop to measure the performance. As you might guess, the answer is a lot (CPUID is slow and serializing). edit: https://github.com/maxhaton/chimpfella https://github.com/maxhaton/chimpfella - I haven't bothered to add pmc support yet
- jstimpfle 6y agoI love qsort! It's easy to use. 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.
- dan-robertson 6y agoThe reason that C programs often perform well 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. In many ways, modern CPUs are particularly designed to run the machine code generated by C compilers on typical C code like this. Pointers and memory allocation are often painful or fickle so use of pointer-heavy data structures like linked lists is quite uncommon. 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.
- littlestymaar 6y ago> 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 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. [1]: https://www.youtube.com/watch?v=HgtRAbE1nBM&t=43m15s https://www.youtube.com/watch?v=HgtRAbE1nBM&t=43m15s
- deleted 6y ago[deleted]
- jstimpfle 6y agoSo he's comparing the AVL tree he wrote himself to a B-tree optimized to death by someone else? Out of interest though, does he mention somewhere which actual implementation he used?
- frutiger 6y agoMostly agree with your comment but linear search through arrays of size less than a few hundred will typically beat more sophisticated structures such as red-black trees or hashtables. This is due to prefetching and avoidance of unpredictable pointer traversals. Asymptotic complexity is only that: asymptotic. In many programs in many domains the sizes of these data structures will rarely exceed this limit.
- vbezhenar 6y agoIt might be fast, but it'll load CPU caches with that data and it'll evict another useful data. Which means that while this particular code will be fast or at least not very slow, some other code will be slow because its data have to be fetched again. I have no idea whether that matters or even easy to measure...
- forrestthewoods 6y agoYou’re stretching there imho. 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.
- deleted 6y ago[deleted]
- naikrovek 6y ago> 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.
- michaelmior 6y ago> null terminated strings feel like idiomatic C to most people 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.
- rcoveson 6y agoNull terminated strings are often called cstrings. They’re beyond idiomatic; they’re part of the C standard library.
- lambda 6y agoNot just the standard library, but the core language. They are what you get if you write a string literal in your code.
- jacoblambda 6y agoYes but if we are being pedantic no. Of course the language does still greatly lean into the null terminated string concept. 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.
- akkartik 6y agoAlso Unix. Syscalls return null-terminated strings all over the place. So any language running on Unix has to deal with null-terminated strings. I know because I run a userland that uses length-prefixed strings as far as possible: https://github.com/akkartik/mu https://github.com/akkartik/mu
- michaelmior 6y agoTrue. I was skipping over that, but the fact that functions manipulating null terminated strings are part of the standard library is certainly a reason in itself to consider them idiomatic.
- fermienrico 6y agoForgive me for asking a stupid question: what does it mean when something is “idiomatic” in a programming language context? Is it just the best or recommended way to do something? Or is it something that’s supported by the language? Or something else?
- grzm 6y agoIdiomatic in a programming language means pretty much what it means in any other language: how would someone fluent in the language express it? In a programming context, that may also correspond to the most performant or otherwise "best" expression, but sometimes it's just a commonly used style or phrase.
- millstone 6y agoA programming language idiom is a pattern or technique that you expect your readers to know, even if it isn't obvious when encountered for the first time. Here's an idiom: for (int i=0; i < 10; i++) We all instantly know this means loop 10 times, from 0 through 9. But on first read it takes a little work to figure out what's happening.
- ClumsyPilot 6y agoI was struggling with that too initially - replace the word with 'standard' or 'natural' and it retains the same meaning.
- quotemstr 6y agoRight. As an industry, we need to get away from the simplistic "manual=fast" model. Logic does not automatically get faster when you write it in C or C++. It frequently gets slower, since your one-off "lean and mean" native code clumsily and slowly does the job that a managed runtime has been tuned for decades to do.
- WalterBright 6y agoD uses slices for strings, which also gives D a big performance boost over C whenever strings are in play.
- BruceEel 6y agoWalter, can you elaborate on this, are D's slices functionally equivalent to C++'s string_view? I.e. no copying as long no 'ASCIIZ-dependent' code is involved?
- WalterBright 6y agoD strings are a simply a pointer/length pair. Substrings can be extracted with no alloc/copying necessary. The length can be determined without loading the string into the cache and scanning it. Those two features make for big speed improvements.
- musicale 6y ago> real world C is a lot less performant than people think it might be 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.
- unethical_ban 6y agoI assume, since the submissions says is talking about something "faster in benchmarks", that he means "fast".
- musicale 6y agoYeah, I think you're right. "Less performant" seems like a less clear (so to speak) way of saying "slower" (or maybe "less efficient" or simply "worse" in some instances.)
- baybal2 6y ago> I spent a fair amount of time reviewing C code in the last 5 years - and things that pop up in nearly every review are costly string operations. Do not tie computational operations on string operations in C. Pick one of many string manipulation libraries to do any serious work with them.
- greyhair 6y agoIt is funny when I think of the hundreds of thousands of lines of code I have shipped in my long career (all embedded) and how little of it ever had to handle a string. 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.
- jstimpfle 6y agoSlow code bottlenecked by string operations is probably just bad, though - no matter which way you code your strings. Strings are not what computers like to do. Computers like integers and subscripting operations. Strings can make sense for inter-process scenarios (for example, file paths are usually the right thing and you don't want to reference files with inodes). 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.