I am developing data analytics algorithms that are supposed to process large amounts of data.
Thus I am aiming to develop my mathematics already in such a way that it is possible to distribute the algorithm later on many machines (Big Data).
I am able to develop my algorithms in such ways that it calculates some intermediate meta-data and pre-computed values that it saves - meta-data of the actual original data. This might increase the total amount of data that is stored by quite a bit (actually by hundreds of percent), but this should also decrease the processing time considerable (also by hundreds, if not thousands of percent).
This opens up the question whether it is a good idea to build smart algorithms and implementations that trade RAM for processing power.
This in turns opens up the question: What is more expensive RAM or processing power?
This question is of course not possible to answer precisely without implemented everything and making the appropriate comparative calculations.
However, development time (my time) is also worth something ;-), so I want to make good decision during the development process. I already have my different algorithms in my head, but they are not implemented - which will take a couple of months (hopefully not years - which would not be surprising as I am working in academic research).
I can make educated guesses how much RAM I will need (times xyz) and how less time will be spend (as in big-O notation).
After all this intro: Is there a rule of thumb when it is worth it to spend RAM for computational speed?
Details regarding the Hardware
In the first place I am developing the algorithm. The implementation is only following from that and is not my main concern at this point. Designing my algorithm (math), I am already trying to keep the guy in mind who has to order the servers one far away day. (Ain't I nice?! ;-)) That means, that I do not know all the implementation details, but I try to guess what I think might be the case:
- My algorithms would run on cheap commodity server hardware. Both CPU and GPU are options (actually combining them in my current design). RAM is in the area of GB per machine. How much GB of RAM, that is what my question is aiming at. The entire data would have to be in RAM, so if you will it would be like an in-memory database (only without being a database).
- I hope it will be implemented in such a way that it plays nicely with other programs. Consider a JVM-languages (Scala, Java) being used, so I guess that makes this part easier, right? It would be great, if the implementation could run in Mesos etc. and I guess that should be possible, but I personally have not idea how to do anything like that. Using Akka actors comes to mind though - it seems right for my algorithm so far.
- "Is there any reason you can't implement your algorithms, profile them then decide afterward if it is worth adding a cache at that point?" The issue is not just the implementation phase, but already the time proving that my algorithms are correct mathematically. It is nice that I have them in my head, but that does not mean that they are sound. That requires a lot of work.
- I already did some profiling with earlier prototypes, that's why I thought of calculating this meta-data. Some function calls are rather expensive. In order to make them less expensive I have to do some mayor changes to not only my implementation, but also my math algorithm itself. The idea for this stands, the time consuming proof that his is sound is still missing.
Details regarding the algorithm
First of: "Algorithm" does not mean the software implementation (I get the feeling, some people might mistake that). An algorithm is the mathematical description of which steps to take in order to get my mathematical model.
Here is the deal:
- The part that is expensive to calculate is a sum of values. Those values need to be calculated as well and this takes a lot of time.
- I am able to approximate the final result from 1. by not having all those values calculated, but only some and ignore values that are very small (implicitly setting them to zero). I am able to calculate which values are going to be small without calculating them themselves. This calculation is cheaper than calculating the values, but it is also expensive.
- However, I developed a (very smart and complex) mechanism to even speed um 2., however this mechanism requires a lot of memory.
The implementation of the mechanism from 3. is what we are taking about. It is not exactly meta-data, but the mechanism requires memory consumption. So it is not something most people here have in mind hearing "cache" I guess. It is not even really pre-computed values that would be stored in a rainbow table or something like that. What would take the memory is the meta-data of the mechanism itself, because the mechanism has state.
I hope it is clearer now what is happening.
Computational complexity in Big-O notation
For above algorithms (1. to 3.), with n being the amount of input data:
- about O(n*log(n)).
- about O(n*log(n)), but faster.
- about O(log(n)).