Pruning is costly too, lazy pruning is easier - when you want to cache something, remove something else to the dirty laundry basket. There's no reason to prune O(1) cache if it is not full, that actually adds complexity.