Introduction to the

A memory-bound function can be called a memory-bound function, which means that the time to complete a given computation problem depends primarily on the amount of memory required to save the working data. The corresponding function is compute-bound, in which the steps required to compute are the determining factor.

This article introduces memory-limited functions and their relationship to memory functions.

Memory function

Memory functions and memory-limited functions have very similar names, but they actually do different things. Let’s look at memory functions first.

In the learning algorithm, there is a very simple and easy to use algorithm called recursive algorithm. Friends familiar with recursive algorithm may know that recursive algorithm is easy to use, but it has a disadvantage that it will repeat the calculation of functions in the recursive process, such as the most classic Fibonach sequence in recursion:

 Recursive_Fibonacci (n)
 {
     if (n == 0)
         return 0
     if (n == 1)
         return 1

     return Recursive_Fibonacci (n-1) + Recursive_Fibonacci (n-2)
 }

It’s easy, but let’s think about the calculation, F(3)=F(2)+F(1), and F(4)=F(3)+F(2), and we’re going to evaluate F(2) twice in this process. If the value of N is large enough, there will be even more double calculations.

One solution is to store the results of previous calculations in memory. This method is called the memory function:

Fibonacci (n) { for i = 0 to n-1 results[i] = -1 // -1 means undefined return Fibonacci_Results (results, n); } Fibonacci_Results (results, n) { if (results[n] ! = -1) // If it has been solved before, return results[n] // look it up. if (n == 0) val = 0 else if (n == 1) val = 1 else val = Fibonacci_Results(results, n-2 ) + Fibonacci_Results(results, n-1) results[n] = val // Save this result for re-use. return val }

While the logic of direct recursion is simple and easy to write, it is more time intensive.

Memory constrained function

The memory-constrained function is primarily used to describe a function that uses XOR and consists of a series of computations, each of which depends on the previous one.

Because of this memory dependency, memory-constrained functions are mainly used in cryptography to prevent brute force cryptography.

Here is an example of a memory-limited function used to prevent spam.

Use of memory-limited functions

Using the memory-limited function to prevent spam, mainly using the principle of PoW, that is, you can send me spam, but only if there is a cost.

Of course, the original anti-spam rationale was to use CPU-constrained functions.

In 1992, IBM research scientists Cynthia Dwork and Moni Naor published a paper on Crypto titled “Block Spam by Pricing” in which they proposed the possibility of using the power of CPU-constrained functions to block spam from abusers.

The idea is that if the cost of spamming is low, spam can be rampant. If you can add additional computing costs to sending mail in the form of expensive CPU computations, you can reduce spam. CPU-constrained functions are used to prevent a large amount of spam from being sent in a short period of time by consuming a certain amount of CPU resources for each mail.

CPU-constrained functions are a breakthrough, but they also have their drawbacks.

Because fast CPUs can compute much faster than slow CPUs. In addition, high-end computer systems have complex pipelining and other computationally friendly optimizations. As a result, spammers with high-end systems are almost immune to this CPU-limited function.

This can result in very large computation time differences due to different machine performance of different users. For example, if an algorithm takes a few seconds on an advanced computer, it might take a minute on an older computer, and a few minutes on a less powerful phone, then it is definitely not acceptable to mobile users.

So what the researchers were interested in was finding a function that would run at roughly the same speed on most computer systems, faster on advanced computers, but only slightly faster, not geometrically faster, and then within tolerable limits.

This approach is to use memory-limited functions. A memory-constrained function is a function whose computation time is dictated by the amount of time it takes to access memory. Memory-constrained functions access the location of large memory regions in an unpredictable way, which prevents caching from being used to improve performance.

There are also industrial reasons for using memory constraints rather than CPU constraints, and while CPU computing speeds have increased dramatically in recent years, relatively little progress has been made in developing faster main memory. Therefore, it can be predicted that memory-limited functions will be used in more and more scenarios in the future.

This article has been included in http://www.flydean.com/memory-bound/

The most popular interpretation, the most profound dry goods, the most concise tutorial, many you do not know the tips to wait for you to discover!