Garbage collection associated with a cache with reduced complexity. In an embodiment, a relative rank is computed for each cache item based on relative frequency of access and relative non-idle time of cache entry compared to other entries. Each item having a relative rank less than a threshold is considered a suitable candidate for replacement. Thus, when a new item is to be stored in a cache, an entry corresponding to an identified item is used for storing the new item.