Caching algorithm?

I have made a pretty fast (HTML-)template file scanner, which constructs template data using following steps:

1. load file into a safely padded string
2. scan for pairs of markup "delimiters" and construct variable fields and (recursively) sub-templates

This seems to work fast, loading a pretty complicated template takes less than 1 ms. But still, 1 ms is quite some time...

My component is an extension for PHP. I am not quite sure if it would be a good idea to introduce some caching, so that the constructed data structure could be stored and cloned on request, instead of scanning a file every time.

My idea is to have a memory limit for template cache, and do something like this when a template is loaded:

lookup in cache
if found
return a clone
else
load file
construct data
store in cache
while total memory used is greater than max allowed
delete "unpopular" templates from cache
return a clone of new data structure

Anybody knows an algorithm for finding cache entries, that are least frequently used? Or maybe some other caching approach?

Is it woth bothering, when the processing time that can be spared is less than 1 ms?