Increase Performance of Bin-Packing

[bwagner5]

Tell us about your request
What do you want us to build?

Tell us about the problem you're trying to solve. What are you trying to do, and why is it hard?
What outcome are you trying to achieve, ultimately, and why is it hard/impossible to do right now? What is the impact of not having this problem solved? The more details you can provide, the better we'll be able to understand and solve the problem.

Increase the performance of the current bin-packing algorithm to pack at least 20,000 pods onto 200 instance type options (soft numbers to start with, may revise up or down, but some kind of goal). The first step of the performance optimizations is to setup unit tests around packing and a benchmark to ensure we have today's performance metrics and then iterate on driving the latencies down.

Are you currently working around this issue?
How are you currently solving this problem?

The current bin-packing algorithm works well for relatively small packings, but the latency jumps quite significantly as pod packings and instance type options increase.

Additional context
Anything else we should know?

Attachments
If you think you might have additional information that you'd like to include via an attachment, please do - we'll take a look. (Remember to remove any personally-identifiable information.)

Community Note

• Please vote on this issue by adding a 👍 reaction to the original issue to help the community and maintainers prioritize this request
• Please do not leave "+1" or "me too" comments, they generate extra noise for issue followers and do not help prioritize the request
• If you are interested in working on this issue or have submitted a pull request, please leave a comment

[ellistarn]

I think we should be driving towards 10,000 nodes at 30 pod density, but we should also do what we can to make sure the packing algorithm doesn't scale linearly with the number of pods, so this should be moot :)