To avoid having to vacuum whole relations all the time there's the "visibility map", which keeps track of which blocks have no dirty rows; so they can be skipped during vacuum.
To understand which versions are visible postgres stores transaction-ids in the row headers; these are four byte wide. On systems with significant throughput, those don't last very long. So every now and then there's anti-wraparound vacuums; which replaces xids which are about to become "too old" with a special marker ("frozen").
The problem < 9.6 is that these anti-wraparound vacuums have to scan the whole table, thereby are a lot more expensive. These happen every 200 million xids by default (write transactions and/or savepoints), configurable up to ~2 billion. With the freeze map, that doesn't have to happen, only non-frozen pages have to be re-scanned.
..and the thing that's a killer feature for many larger databases, the freeze map. Not having to FREEZE things all the time is a godsend.