6 ms·
Knapsack algorithm in PostgreSQL source code
- Veedrac 5y agoThis snippet is really getting held back by the Bitmapset, both interface (eg. the del_members/add_members dance) and the structure (eg. with the double indirection, and unnecessary implicit checks for reallocation). 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”.
- jamesfinlayson 5y agoAnd it's only used once in the code - dealing with GROUP BY in the query planner maybe?
- amerine 5y agoSeems close: https://github.com/postgres/postgres/blob/4d5f651f1d651c6fa79f9188e7b9a04654c7125a/src/backend/optimizer/plan/planner.c#L3944 https://github.com/postgres/postgres/blob/4d5f651f1d651c6fa7...
- jonbaer 5y agoRecursive queries ... https://aiven.io/blog/solving-the-knapsack-problem-in-postgresql https://aiven.io/blog/solving-the-knapsack-problem-in-postgr...
- ComodoHacker 5y agoThis has nothing to do with OP code.
- jimmyed 5y agoLow 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...
- deleted 5y ago[deleted]
- VHRanger 5y agoThe compiler can't really reason very well about the data layout - it can reason about the instructions
- jimmyed 5y agoIt can also reason about control flow. It does constant folding etc, is it at least theoretically possible to do alloc optimization?
- chakkepolja 5y agoYep 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.
- nextaccountic 5y agoC 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 https://www.youtube.com/watch?v=lTgERgPNTF8 a 5 minutes talk about llvm doing this * https://speice.io/2019/02/compiler-optimizations.html 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_745_Final_Report.pdf 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 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-compiler-optimize-from-heap-to-stack-allocation https://stackoverflow.com/questions/47075871/can-the-compile... asking if compilers are actually allowed to do that (they sometimes are, but not always)
- kaashmonee 5y agoWhy is this notable? In that same directory, there are lots of other data structures built in too (Bloom filters, binary heaps, etc.)