0

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:

  1. 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.
  2. 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.
  3. 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:

  1. about O(n*log(n)).
  2. about O(n*log(n)), but faster.
  3. about O(log(n)).

closed as too broad by gnat, David Arno, amon, 17 of 26, user22815 Dec 9 '16 at 20:00

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    Are you constrained by a minimum amount of RAM you have to support? How much RAM are we talking about (e.g. 5MB or 16GB)? Should your program behaves nicely with other programs, or it doesn't matter if the user's computer is clogged by yours? 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? – Vincent Savard Dec 9 '16 at 16:16
  • How different would the implementation of the algorithm be if you decide to implement memoization? I'm not exactly sure what the issue would be. If you haven't even implemented your algorithms, you should do so, then profile them and add memoization if need be. But as of right now, it seems you have too many unknown variables. You don't even know how much RAM you would need. Will the OS allow a program to use that much memory? Will the VM support it as well? If it requires more RAM than what you have, how will you invalidate your cache to prevent swapping? – Vincent Savard Dec 9 '16 at 16:44
  • @VincentSavard: Changing the algorithm would be substantial work - otherwise I wouldn't need to ask ;-). Please read my edits: I wrote about the profiling. Also: Rewriting and such costs months of work. I can't "just" rewrite stuff. Regarding the other questions from "Will the OS...": I consider them software engineering problems - so they need to be solved buy other guys. However, they are known to be solvable (e.g. in Apache Spark, which can cache in-memory, and written is written in JVM-Scala). – Make42 Dec 9 '16 at 16:57
  • I did read your update, but it didn't explain why it would be so hard to add memoization after the fact. It can often be made completely transparent using the decorator pattern. I also never talked about a rewrite. The reality in software engineering is that software changes and you should be able to write it in a manner that makes it possible to augment it later on. I fail to see how your case is different, but maybe there's something I don't understand here. – Vincent Savard Dec 9 '16 at 17:05
  • 1
    @rwong: Depends how much one is allowed to short-cut. In research one can say with a couple of words what would require pages of explaining, if the other one does not know the pseudo-code behind it (usually we do). My last prototype had about 5761 lines of code. It is written very "protypy" in Matlab and could be considered pseudocode. (I have written enterprise code in my previous day job, so I can tell a little.) This is the "simple" version. The "smart" version would be considerably longer. – Make42 Dec 9 '16 at 17:53
3

What is more expensive, RAM or processing power?

That's a false dichotomy, for many reasons.

If your target audience is the average user, your constraint is probably going to be the memory that he already has installed in his machine; you're not going to ask him to buy more memory just to run your application, are you?

If you are your own audience, and you're contemplating the hypothetical of buying a new machine (what it usually takes to get more processor horsepower) versus buying more memory, the answer should be obvious: more RAM is almost always cheaper.

If you're trying to solve this problem by the way you write your software, the best course of action is to write a prototype in the most straightforward and sensible way possible, and then decide where to optimize by measurement and profiling. This will maximize your use of development resources, because it will focus the problem where it belongs: on that small percentage of code in your system where performance considerations really matter.

If you need better flexibility, consider virtual machines/cloud computing. You can configure those any way you want (on a processor core + memory basis), and mix and match configurations until you find a sweet spot you like.

  • As mentioned, it would run distributed on many machine (Big Data), so... it would run on servers, not on consumer laptops. A first profiling has been done (see my edits). – Make42 Dec 9 '16 at 16:35
  • "Cheap commodity hardware" suggests that the hardware decisions have already been made, so this is essentially a software optimization problem, right? – Robert Harvey Dec 9 '16 at 16:36
  • I am a researcher at university. This is not backed by any company. Nobody bought anything. There is not enterprise customer. So no, no hardware decision has been made. I am making educated guesses in what kind of future my algorithms might find themselves in - let's say e.g. 2 years. – Make42 Dec 9 '16 at 16:41
  • I see. Will you write the software before you buy the hardware, or at least prototype it? – Robert Harvey Dec 9 '16 at 16:44
  • Of course. I am have been designing the math until now and are further improving. However, I have to develop prototypes to show the stuff works. Additionally I am already writing (parts) in a professional software engineering manner. Buying hardware will be happening much later. – Make42 Dec 9 '16 at 16:49
2

Short answer: it is your job to figure it out, in the most professional and efficient way you could.

You could consult other researchers, computer scientists and software development practitioners, but nobody had the intimate knowledge with the system you have in mind.

Best case scenario is that every educated guess you made will be in the ballpark. Worst case scenario is that all of your guesses are wrong, and some of your early choices ended up being false leads that wasted your precious time, effort and funding.

I would recommend focusing on the art of doing research:

  • Train yourself to think more deeply and logically
  • Document your assumptions and reasoning process, every day
  • Keep old documentations so that you can revisit them. Sometimes you decided to throw out an idea, only to later realize that you still need them. Idea is not like source code, you can't keep your ideas clean.
  • Follow any other best practices that applies to computer science research. Well-designed, well-written, well-organized, documented, source-version-controlled, maintainable, etc.

You will need to assume that high-density, low-latency persistent memory such as 3D XPoint will come into fruition. You need to find ways to exploit that in your research, despite not having access to the actual hardware. Therefore, you will need to "simulate" the characteristics of that kind of hardware in your research.

Since such simulation requires assumptions that aren't necessarily correct, you may need to make multiple sets of assumptions (scenarios) and illustrate the impact of your research in each scenario. (Kind of like global warming research.)

Aside from pervasive persistent memory, you might also have to worry about GPU, Qualcomm Centriq, Movidius Myriad, FPGA (now on AWS), Custom ASIC, Tensor Processing Unit, optical interconnect, Arrival (2016), another tech bubble burst, etc.

  • What you say is what I do. I am not sure how this is helping me (except the link to 3D XPoint). You basically say "be a good researcher" (I try) and "you can't know anything unless you have build both projects completely". (I don't think anyone in industry works this way, right?). – Make42 Dec 9 '16 at 17:06
  • @Make42: People in industry, in general, don't need to do this kind of dreadful research. Industry abhors risk-taking. Agile encourages outsourcing the riskiest functionality to a third-party. (As I said, nobody had the intimate knowledge of your algorithm like you do.) – rwong Dec 9 '16 at 17:09
  • @Make42 there are several sites on Stack Exchange about Computer Science, Academia, Computational, etc., where you can provide more precise details to a different Q&A audience that will have the background knowledge to understand your questions. – rwong Dec 9 '16 at 17:14
  • I got an idea how to describe what is happening and edited my question - maybe that helps. – Make42 Dec 10 '16 at 19:44
1

If we assume for a second that you have an unlimited amount of RAM available, there is a simple answer to the question "when it is worth it to spend RAM for computational speed": when the time required to allocate, manage, and retrieve data from memory is less than the time required to (re)calculate it every time it is required.

There are a number of factors to consider with this:

  • The cost of allocation / management tends to have an increasing marginal cost. In other words, as the amount of memory increases, the cost of each additional megabyte tends to be higher. This is especially the case when garbage collection is involved.
  • The value of caching answers increases the more you use that value. For example, if you only need a value once, caching it will make things slower as well as waste memory.
  • There are financial costs associated with RAM. While the 64-bit age has opened up memory to point where the theoretical limits are beyond what can currently contemplate using, if you push beyond what is considered standard, you will pay a premium so the costs are not generally linearly proportional to the size of the RAM.

The only rule of thumb for this, in my experience, is caching results is highly effective in deeply recursive algorithms where the 'bottom' values are pulled in again an again to build 'higher' results. If you can predict which values are the most commonly needed, you can get the most bang for your buck by caching just those. Caching everything just in case it is needed again later will tend to harm performance.

Ultimately, I would start with no cache and then try adding them in. The common idiom I use for this is along the lines of this pattern:

def calculateFoo(bar):
  if bar in cache:
    return cache[bar]

  foo = complicatedCostlyCalculation()

  cache[bar] = foo

  return foo

It's easy to add this in later or comment it out to see the impact of the cache.

  • Yes, I have a setting where I reuse the calculated values a lot. It is not "I might use it later". I definitely will - and very many times (like millions of times). – Make42 Dec 9 '16 at 17:11
  • @Make42 So that would seem to indicate caching if the time to calculate is longer than a the time to read from memory which will generally be the case aside from trivial computations. The other consideration is how many values you are storing. If you have a very large number of items, the time to store and retrieve and manage the memory can start to overwhelm the savings of the caching. – JimmyJames Dec 9 '16 at 21:06
  • I edited my question, describing what is happening. The number of actually stored items is large. Loading and storing is definitely faster than recalculation. It's a monetary question though. – Make42 Dec 10 '16 at 19:47
  • It's not just the number of items that will matter, it's also the size of the storage associated with them. I just worked through a problem yesterday where eliminating the long term storage of pre-calculated items made the code run faster. The cost of keeping that creating that data on the heap and managing it (Java) was greater than the cost of calculation even though it was only a few GB. Instead I used a temporary cache of a subset of the values and kept it local to the stack. Trying to keep everything caused the processing to go more and more slowly as the cache grew. – JimmyJames Dec 12 '16 at 17:42
  • It seems to me, that quite important are the ratios time to calculate per item and time to calculate per byte compared to the cost of keeping the items/bytes. What makes my situation tricky, is that it's not really a classical cache I introduce but the described mechanism. Here I have an all-or-nothing situation: Either introduce the mechanism or I don't. I can't have a "little cache". – Make42 Dec 14 '16 at 9:28
0

RAM is cheap: as-of this writing, under $100 for 16 GB. Most "commodity" hardware maxes-out at 64 GB, which means that you're spending $400 for total RAM. Which will be less than the cost of CPU, motherboard, and disk.

In that light the tradeoff is simple: if you can reduce the number of physical machines by increasing RAM, you will save money.

Moreover, let's say that you spec 64 GB of RAM but only need 32. If we assume a base system cost of $1,000, then the "wasted" RAM represents 20% of your cost.

But consider using an AWS cluster (or Google Compute engine, or Azure whatever-it-is). As-of this writing, an r3.2xlarge instance (which provides 8 virtual CPUs, 61 GB RAM, and a 160 GB SSD) will cost you $0.665 per hour.

Which on an annualized basis (8766 hours) is far more expensive than physical hardware: $5829.39. But you can shut it down when you're not using it. So if you only need to use the machine for 4 hours a day to test your algorithm, you can get a year of use for less than you'd pay for physical hardware.

Better, you can scale your compute resources up or down as needed. If you only need a 32GB machine, that's half the price. If you find that you need 128 GB that's twice the price. Or you could trade-off CPU versus RAM on an as-needed basis.

  • Maybe the question is more "Will RAM be also be cheaper than additional cores?" Does your argument hold then? – Make42 Dec 9 '16 at 19:16
  • The general rule is that AWS charges you a lot more on RAM because this is an economically effective price discrimination, i.e. a good way to make well-off customers pay more. A second sidenote is that, on consumer-grade computer, modern CPU has so much bandwidth that it can "sweep" the entire RAM in mere seconds (single digit), or even subsecond. This is provided that the access is cache-friendly (memory-bus friendly), namely sequential. Or, non-sequential, but cacheline-width chunks with high spatial and temporal locality. – rwong Dec 9 '16 at 19:33
  • I guess the lesson is that use AWS for benchmarks, but don't use AWS pricing as a proxy for customer-owned hardware price. – rwong Dec 9 '16 at 19:35
  • @Make42 - I answered to give you a framework to think about these questions, not to build a pricing spreadsheet for you. Put bluntly, you're spending a lot of effort on something that shouldn't matter. – kdgregory Dec 9 '16 at 20:57

Not the answer you're looking for? Browse other questions tagged or ask your own question.