I was curious about the issue the author called out with the baseline knapsack algorithm -- that it was running out of memory.

It looks like pytorch's various knapsack implementations (including the one contributed by the author) are here:

https://github.com/pytorch/pytorch/blob/31ba9a56657bc887c957...

appears to be used e.g. here

https://github.com/pytorch/pytorch/blob/31ba9a56657bc887c957...

One thing that jumps out at me while staring at the baseline dp_knapsack code is that it isn't very clear what the units used to measure memory are meant to be. The dp_knapsack code assumes that memory & max_memory (aka the memory budget) are floats. dp_knapsack internally multiplies these floating-point memory values by 10,000 & then rounds them to integers to quantise the memory values -- the quantised max_memory value defines the size of one dimension of the dynamic programming table. the other dimension is sized by the item count.

From reading patches of partitioners.py, it seems like the memory budget is meant to be a floating point number between 0.0 & 1.0, and presumably the memory of each item is normalised relative to that memory budget?

If so, & dp_knapsack is called with a max_memory of 1.0, then the a 2d array for n items is allocated and m=10,000 quantised memory values is allocated as shape (n+1, m+1). So for 100 items that'd be an array of shape (101, 10001) - it's filled with float32s, so 4 bytes per element, so the size required for the table would be ... about 4MB.

So it's not obvious why that would be running out of memory.

Another possible explanation of why the baseline dp knapsack could be using a bunch of memory -- speculation -- is that some code could be calling dp_knapsack with a different unit convention than what dp_knapsack expects --- suppose a caller passes in memory & max_memory values that are measured in floating-point GB. If the max_memory was passed in as 1024.0 then, for 100 items, the dp_knapsack code would allocate a float32 array of shape (101, 10240001) and this would require about 4GB.

Given the units of these inputs aren't documented (& certainly not enforced by the type system) & there aren't runtime range checks on the value of max_memory there's a lot of room for something like this to be happening.

Perhaps dp_knapsack could be reimplemented where it is responsible for rescaling input memory values relative to max_memory, where the rescaling always forces max_memory to be 1 before the memory values are quantised. Then there wouldn't be a way for the caller to get the undocumented calling convention wrong.

0/1 Knapsack Problem in PyTorch