Early eviction is fine for performance if the average eviction you get is good enough that any improvement in eviction you get from a more optimal choice of distance is outweighed by the effort in picking the insertion point.
You really need to measure, because this will depend on your workload, how fast your implementation is relative to the cost of a miss, what the ratio of "likely to never be requested again" to potentially long-lived objects are, etc.
You really need to measure, because this will depend on your workload, how fast your implementation is relative to the cost of a miss, what the ratio of "likely to never be requested again" to potentially long-lived objects are, etc.