At the moment I don't do smart caching.
In the first version, all data was read at once and kept in memory. This was very slow at startup.
In the second version, data is read from disk when needed and kept in memory. (this was the fastest way to adjust version 1.). This is fast in starting up, but slow when part of each datafile needs to extracted. This means all datafiles are read and kept in memory. So it works fine (but slow) until all memory is used.
I think in version 3, I need to do something that reads data when needed and delete data when not needed. So something needs to decide what is kept in memory.
Each datafile can stand on it's own, but it can also be part of a group of datafiles for which "something" is calculated. At the moment "something" is the average, but this will be extended at some point in the distant future.
I am willing to restart from ground up in the design to handle an efficient cache method.
It's not a method of speed, I think, but of memory footprint. Does NSNumber not have a larger footprint than a float for example?
If it's a matter of memory, whenever you are done with any piece of data it should be discarded. This could read to a lot of reads, though, if you need certain things frequently. The real issue with trying to cache here, it seems, is that you won't know how much memory is available to a process before things have to start swapping, etc. This means that you don't know when you're almost "full" so you can start discarding some older/less frequently used data.
In terms of the memory footprint, NSNumber will certainly be larger than a float. You know a float is 4 bytes, period. NSNumber is going to have some amount of overhead on the heap to store runtime information, as well as at least 8 bytes of "backing" storage, as it appears that it can store up to a long long or double.
By the same token using a C-style array will have no overhead since it only needs to store a pointer (4 or 8 bytes) to the base of the array then the actual storage needed for the elements. An NSArray or NSMutableArray will have a bit of extra overhead because it needs to store runtime information like current size, etc. It will only store pointers, so each element will be the size of a pointer. This may be a little more or a little less than the storage needed in a C-style array depending on the type and platform. You are sacrificing "easy" dynamicism using a C-style array for a pretty small amount of reduced memory usage. The real issue is that an NSArray can only store pointers to NSObjects, so you have to use a wrapper like NSNumber. You could make a small class that has a single float field, and store this in an NSArray, but you're probably not going to save that much over using NSNumber.
Unfortunately it doesn't sound like there is a magic bullet in this situation. If you have many gigabytes to process, and you might use any part of it at any time, you're in a tough spot. It sounds like your data is in a lot of separate files that are requested "on-demand". It may be too simplistic, but I'd probably try to have the data in each file abstracted by a new class. It would contain an NSArray of the data or C-style array of the data. You'd need a "master table" of these, perhaps stored in an NSDictionary. They key could be some unique identifier (set number, filename, etc.). The value would be this new object you've created. You can quickly check if the key is present in the table. If it is, the data is available, if it's not, you need to instantiate a new object of your new class, at which time it is assumed the data is needed, so the data is loaded from the file.
If you don't have an easy way to tell how many data points are in your file before they are read (i.e. the file is all floats, so you could take filesize in bytes/4 to get the number of items), you might use a dynamic type like NSMutableArray while you're reading in, then use -length and malloc a C-style array of float, then loop over the results unboxing from NSNumber to float. If you don't do it like this, you'll have to take a best guess, malloc your C-style float array to this size, then possibly have to manually realloc to a new larger size. This is doable, but is a bit messier and requires a lot more manual manipulation.
When you're done with a particular set of data (either because you just KNOW or you've determined you need to clean up based on the number of elements in your dictionary, etc.), you need to free your C-style array or release your NSArray, then release your object.
You may have all of that covered already, and you're wanting help designing the clean up algorithm. That's going to be a bit tougher. There're a ton of way to do this... the two simplest are time based (oldest data set is flushed first), in which case you just need to track the time (probably just seconds since epoch in a 4-byte value, as long as you know your code will not be used after 2038) that you read a value, then have a fast way to find that to flush. Alternatively, you could use an ordered list and delete from the beginning. To prevent log(N) time to access the elements by key, you could keep this list separate from your NSDictionary that provides you fast access. You'd just have to remember to delete from the dictionary when you remove from the beginning of the list.
The other option is least used being used to flush old data. This will be a bit tougher, because you'll have to keep a usage count. This could be done by extending NSDictionary so each data element has a usage count that's incremented whenever you use getObject, etc. If you didn't want to do that, you would have to track this manually... there's plenty of ways to do that, either keeping a count in your new data storage object, keeping another dictionary whose value is the count (though finding the item to flush becomes slower, you can mitigate this by keeping the list ordered, but this makes each reference a little slower).
This is only worth doing if you know you can do a better job of this than the system's virtual memory system.
-Lee
