Knapsack algorithm in PostgreSQL source code | Hacker News Reader

Knapsack algorithm in PostgreSQL source code

github.com

89 pointsMaksadbek12 comments

This 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”.

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?

Seems close: https://github.com/postgres/postgres/blob/4d5f651f1d651c6fa7...

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...

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.

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)

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.

Why is this notable? In that same directory, there are lots of other data structures built in too (Bloom filters, binary heaps, etc.)

Reply on news.ycombinator.com