Bin packing and VM packing
Page 1 of 1

Author:  tepples [ Wed Jun 08, 2016 11:20 am ]
Post subject:  Bin packing and VM packing

I was inspired by tokumaru's question about algorithms for shortest common supersequence to share similar problems that I've experienced in my own NES projects.

Bin packing problem
The bin packing problem is to pack objects of various sizes into fixed-size bins. It's NP-hard, but the greedy algorithm of "first fit decreasing" (sort by decreasing size, then put each object in the lowest numbered bin where it will fit) is proven to be no worse than about 22% inefficient compared to an optimal solution.

I ran into this problem when developing the menu software for Action 53, as compressed CHR data and thumbnail screenshots need to be packed into the bins left by parts of games' PRG ROM that are marked unused, plus additional 32752-byte bins (32K minus the size of a reset stub) at the end.

VM packing problem
The related VM packing problem is to pack sets of distinct elements into fixed-size bins such that all elements of each set appear in a single bin. Sets in the same bin may share elements, but if sets appear in separate bins, they must be repeated. The optimal solution minimizes the number of bins. It is so named because of its application to deduplicating memory pages in virtual machine instances on one physical machine.

The MMC3 sprite tile packing problem is the VM packing problem with bins of size 32. It represents packing the 8x16 pixel tiles that make up each of several sprite cels into 1K banks, such that each cel can be displayed with one bank. NES mappers using 1K CHR banks include MMC3, MMC5, FME-7, and common Konami mappers (VRC2, VRC4, VRC6, VRC7).

According to Wikipedia, the VM packing problem is hard to even approximate. But I can calculate lower and upper bounds in polynomial time and use those to guide packing. The lower bound is the length of the union of all sets divided by the bin size and rounded up. The upper bound is the number of banks required by a greedy best fit algorithm that involves putting a set into the bin with which it shares the most elements, and creating a new bin if a set won't fit into any existing ones.

For the player character in my current project, I get 7 bins as the lower bound and 8 as the upper bound. Then I write out a CHR file with the upper bound packing. But I have a couple ideas to try:
  • See whether packing sets in decreasing order produces a better packing, that is, one that uses fewer bins or leaves the most space in the last bin free
  • The Monte Carlo approach suggested by calima in a reply to tokumaru's question: shuffle the cels a few times, run best fit decreasing on each such permutation, and see if any produce a better packing

Any other suggestions?

Page 1 of 1 All times are UTC - 7 hours
Powered by phpBB® Forum Software © phpBB Group