3 ms·

In C it's possible (and, to some level, very much encouraged) to write your own things to replace whatever built in thing you don't like for whatever reason, be

by dzaima 5y ago

In C it's possible (and, to some level, very much encouraged) to write your own things to replace whatever built in thing you don't like for whatever reason, be it speed, size, portability. C not having fancy built-in structures means programmers are more careful about choosing simple ones, which dramatically cuts down the amount of completely pointless generated code. -O3 can optimize registers and maybe memory reads/writes, but it can't remove reallocation from each call to a vector push, remove a reference count from a whole object type, or do pretty much anything with any moderately complex heap data structure. Sure, that comes at the cost of more advanced things being horrible to write, but it's a trade-off. And I'll just disagree that UB must be unobvious. To me, it's one of the most useful optimization tools. You can check for it with sanitizers, and explicitly invoke it to convey information about hidden behavior to a compiler. It's not magic.

kaba0 5y ago
> C not having fancy built-in structures means programmers are more careful about choosing simple ones Resulting in linked lists everywhere which have pretty terrible performance characteristics. You should be worried about those way before the occasional vector push reallocation cause you any problem. (And you can specify initial capacity so there is that)
- dzaima 5y ago
  linked lists - true, but at least when you write them you'll be certain of what they do, and, coupled with knowledge of cache performance, precisely how bad they are. About reallocation I don't even mean the copying, but just the code needing to check for the chance overflow on every push. Besides the obvious waste of instructions to check for that, it also clobbers registers even if the branch isn't taken, and thus will easily result in a lot more unnecessary spilling to the stack. This kind of pointless thing happens in a ton of data structures.
  - kaba0 5y ago
    Branch prediction exists so the common case can be made very fast (much faster than jump to this remote pointer), and also, rust uses an optimizing compiler for a reason. Eg., you use a vector inside a for, the vector’s code can be inlined and the checking part be done only at the boundary. Also, one can also manually perform an unchecked push/get/whatever as well.
    - dzaima 5y ago
      The common case may be fast, but it's still slower than not having a rare case in the first place. The untaken branch will still affect register allocation (out of the ~15 x86-64 general-purpose registers, only 5 (6 if you count rbp) preserve data after a non-inlined function call in the System-V ABI (of which there will be at least one, ending in malloc somewhere), and the compiler has to accommodate both taken and untaken at the branch end) and will eliminate any hope of SIMD vectorization, among other wrecked optimizations. Unchecked operations are acceptable if your code has a single hot loop, but if you have a hundred small functions, each taking 1% of the time, you probably won't carefully examine every stdlib function each of them uses and write code to "work around" every unnecessary thing the stdlib does. Yes, that's a ton of micro-optimization, but micro-optimization can bring a ton of speedup, so I'll take whatever makes it simpler (or not needed in the case where you already know what will happen due to having written it)
      - kaba0 5y ago
        Feel free to wrap it into a repr(transparent) type which exposes the unsafe operations by default. But I seriously doubt that programs would benefit much from these micro-optimizations - there are rare and unfortunate cases where indeed there is no one single bottleneck for a program and thus there is no simple way to improve performance, but the vast majority of programs spend all their life in a tight hot loop, and anything else doesn’t matter in the slightest - hell, as mentioned C gets away with as many linked data structure as they want, but writing those in goddamn bash would suffice as well.
        dzaima 5y ago
- deeviant 5y ago
  I don't think I've ever used a linked list in 12 years of embedded C programming.

by dzaima 5y ago

kaba0 5y ago

> C not having fancy built-in structures means programmers are more careful about choosing simple ones Resulting in linked lists everywhere which have pretty terrible performance characteristics. You should be worried about those way before the occasional vector push reallocation cause you any problem. (And you can specify initial capacity so there is that)

dzaima 5y ago
linked lists - true, but at least when you write them you'll be certain of what they do, and, coupled with knowledge of cache performance, precisely how bad they are. About reallocation I don't even mean the copying, but just the code needing to check for the chance overflow on every push. Besides the obvious waste of instructions to check for that, it also clobbers registers even if the branch isn't taken, and thus will easily result in a lot more unnecessary spilling to the stack. This kind of pointless thing happens in a ton of data structures.
- kaba0 5y ago
  Branch prediction exists so the common case can be made very fast (much faster than jump to this remote pointer), and also, rust uses an optimizing compiler for a reason. Eg., you use a vector inside a for, the vector’s code can be inlined and the checking part be done only at the boundary. Also, one can also manually perform an unchecked push/get/whatever as well.
  - dzaima 5y ago
    The common case may be fast, but it's still slower than not having a rare case in the first place. The untaken branch will still affect register allocation (out of the ~15 x86-64 general-purpose registers, only 5 (6 if you count rbp) preserve data after a non-inlined function call in the System-V ABI (of which there will be at least one, ending in malloc somewhere), and the compiler has to accommodate both taken and untaken at the branch end) and will eliminate any hope of SIMD vectorization, among other wrecked optimizations. Unchecked operations are acceptable if your code has a single hot loop, but if you have a hundred small functions, each taking 1% of the time, you probably won't carefully examine every stdlib function each of them uses and write code to "work around" every unnecessary thing the stdlib does. Yes, that's a ton of micro-optimization, but micro-optimization can bring a ton of speedup, so I'll take whatever makes it simpler (or not needed in the case where you already know what will happen due to having written it)
    - kaba0 5y ago
      Feel free to wrap it into a repr(transparent) type which exposes the unsafe operations by default. But I seriously doubt that programs would benefit much from these micro-optimizations - there are rare and unfortunate cases where indeed there is no one single bottleneck for a program and thus there is no simple way to improve performance, but the vast majority of programs spend all their life in a tight hot loop, and anything else doesn’t matter in the slightest - hell, as mentioned C gets away with as many linked data structure as they want, but writing those in goddamn bash would suffice as well.
      - dzaima 5y ago
deeviant 5y ago
I don't think I've ever used a linked list in 12 years of embedded C programming.