1. A computer-implemented method operable on a device comprising hardware including memory and at least one processor, the method comprising: (A) maintaining, in a data structure, invalidation information for a service on said device, said invalidation information comprising a plurality of invalidation commands, wherein at least one of said plurality of invalidation commands specifies one or more resources that may or may not currently be in a cache associated with said service, wherein said data structure stores at least the oldest part of said invalidation commands into a crumple zone which the invalidation commands in the crumple zone can be crumpled together; and (B) selectively combining at least some of said invalidation commands in the crumple zone to form at least one other invalidation command, and replacing, in said data structure, said at least some of said invalidation commands in said invalidation information with said at least one other invalidation command, wherein said at least one other invalidation command is distinct from said at least some of said invalidation commands, wherein said selectively combining in (B) increases available space in the data structure.