3 ms·

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 the

by 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
      That depends on the project. There definitely are projects in which micro-optimizations such as this wouldn't be beneficial for one reason or another, but there definitely also are ones where they're make-or-break. For those, C is pretty good, and you're not fighting against the language (or the core intent of the language at least). (I'd guesstimate that micro-optimizations would go a very long way in improving performance of nearly every program anywhere, but I don't have much data on that besides the couple projects where I've tried to care about performance, and having achieved pretty decent results)

by dzaima 5y ago

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
    That depends on the project. There definitely are projects in which micro-optimizations such as this wouldn't be beneficial for one reason or another, but there definitely also are ones where they're make-or-break. For those, C is pretty good, and you're not fighting against the language (or the core intent of the language at least). (I'd guesstimate that micro-optimizations would go a very long way in improving performance of nearly every program anywhere, but I don't have much data on that besides the couple projects where I've tried to care about performance, and having achieved pretty decent results)