Knapsack algorithm in PostgreSQL source code(github.com)
github.com
Knapsack algorithm in PostgreSQL source code
https://github.com/postgres/postgres/blob/master/src/backend/lib/knapsack.c
5 comments
Recursive queries ... https://aiven.io/blog/solving-the-knapsack-problem-in-postgr...
This has nothing to do with OP code.
And it's only used once in the code - dealing with GROUP BY in the query planner maybe?
Low level code has to take extreme care of avoiding as many allocs as possible, wonder when the compiler will be smart enough to do these optimizations automatically...
C and C++ compilers can sometimes lower a small heap allocation into a stack allocation, at least in simpler cases.
Here's some links about it
* https://www.youtube.com/watch?v=lTgERgPNTF8 a 5 minutes talk about llvm doing this
* https://speice.io/2019/02/compiler-optimizations.html discusses this happening in Rust (the Rust compiler uses llvm)
* http://www.cs.cmu.edu/afs/cs.cmu.edu/user/jatina/www/CS_15_7... a 12 page paper, also on llvm (ps: gcc can do it too, it was just easier to find llvm sources)
* https://en.wikipedia.org/wiki/Escape_analysis#Optimizations (the optimization that enables this is called escape analysis: it tells whether the heap allocation "escapes" the current function, or if it's local enough that stack allocation is a good fit. inlining increases the likelihood that heap allocation won't escape)
* https://stackoverflow.com/questions/47075871/can-the-compile... asking if compilers are actually allowed to do that (they sometimes are, but not always)
Here's some links about it
* https://www.youtube.com/watch?v=lTgERgPNTF8 a 5 minutes talk about llvm doing this
* https://speice.io/2019/02/compiler-optimizations.html discusses this happening in Rust (the Rust compiler uses llvm)
* http://www.cs.cmu.edu/afs/cs.cmu.edu/user/jatina/www/CS_15_7... a 12 page paper, also on llvm (ps: gcc can do it too, it was just easier to find llvm sources)
* https://en.wikipedia.org/wiki/Escape_analysis#Optimizations (the optimization that enables this is called escape analysis: it tells whether the heap allocation "escapes" the current function, or if it's local enough that stack allocation is a good fit. inlining increases the likelihood that heap allocation won't escape)
* https://stackoverflow.com/questions/47075871/can-the-compile... asking if compilers are actually allowed to do that (they sometimes are, but not always)
Go doesn't even have a language-level distinction between heap and stack, everything is on the heap from the language standpoint. However, values that don't escape and that aren't too big are put on the stack by the compiler.
The compiler can't really reason very well about the data layout - it can reason about the instructions
It can also reason about control flow. It does constant folding etc, is it at least theoretically possible to do alloc optimization?
Yep but that would probably break predictability. In low level code I wouldn't rely on some malloc being optimized away, and rather write code explicitly without allocations.
In High level languages, Escape analysis exists.
In High level languages, Escape analysis exists.
[deleted]
Why is this notable? In that same directory, there are lots of other data structures built in too (Bloom filters, binary heaps, etc.)
You don't really want to rewrite the bit indexing, but it feels like you're paying a lot of cruft just to avoid a few “x / 8”.