Effective cache in Delphi

Question

I am creating a cache that will contain entries in Delphi 2007.

Each entry contains a string, 2 dates and a value.

Type MyRecord = Record Location : String; Date1 : TDateTime; Date2 : TDateTime; Value : Double; End; 

There is no guarantee what the maximum cache size will be.

It is very likely that Location will have multiple entries for different dates.
There are only 13 locations.

The cache must be searchable and will be in a performance critical location.

I was thinking of creating a 2-dimensional array for this structure with a sorted list of strings as an index. Therefore, when searching, I get access to Stringlist to find the index that I need in an array with pairs of name values. (Location = Index) Then I need to loop through the elements for each location to see if the value in the cache matches both Date1 and Date2. If the value is not in the cache, I need to go and get it from the database and add it to the cache.

Sort of

 Type MyRecord = Record Date1 : TDateTime; Date2 : TDateTime; Value : Double; End; ... Cache: Array[1..13] of Array of MyRecord Locations: TStringList; 

as the location will be in the list of strings.

Would this be an effective caching framework?

Answer 1

Your structure is efficient enough for caching, but I would not use it in a place critical for performance. If your cache grows and you have 5,000 items in one place, you are still doing a linear search on 5,000 items.

I think it's better to sort the list and use binary search to find items in the cache.

If I implemented something like this, I would take a TList with pointers to records. A list to be sorted with TList.Sort, which I provide to sort the list according to the data containing the records. Sorting will be performed in the field with the highest "selectivity", then in the fields with the second higher selectivity, etc.

If you want to find a record, you perform a binary search in the list and get the value, if it does not exist, you get it from the database and add it to the cache.

Of course, all this would be beautifully wrapped in a class that takes care of this and memory allocation problems.

A hash file is also possible, but you need to do tests to find out which is faster.

Answer 2

Your idea seems sound and should work efficiently. Essentially, you would use a simple database table with an index. It separates index information from data, so the cost of updating the index is "small" relative to moving data around in a sorted structure.

Another possibility is to use the database in memory. There are several available for Delphi. They will do a lot for you and possibly provide more flexibility.

Answer 3

If performance is a problem, avoid string matching as much as possible. Instead, I would sort the cache array in any search order and perform a binary search on the raw data.

If the value of the string is most important, use something like the soundex algorithm to split the string into one character and number and encode both a word and an integer (a simple hash). sort the array by this and by any collision sorting by location bar. Thus, your line does not match lines with obvious inconsistencies.