Introduction to the

Memory-bound functions can be called memory-bound functions, where the time to complete a given computation problem depends primarily on the amount of memory required to hold the working data. In contrast, there are compute-bound functions where the required steps are the determining factor.

In this article, we will look at memory constrained functions and their relationship to memory functions.

Memory function

Memory functions and memory limited functions have similar names, but they 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 although recursive algorithm is easy to use, but there is a disadvantage is that it will repeatedly calculate the function in the recursive process, such as the most classical Fibo 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)
 }
Copy the code

That’s easy, but let’s think about the calculation, F(3)=F(2)+F(1), and F(4)=F(3)+F(2), and we have to compute the value of F(2) twice in the process. If N is large enough, there will be more double-counting.

One solution is to store the result of the previous calculation 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 }Copy the code

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

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 cracking of passwords.

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

Use of memory-constrained functions

Using memory-constrained functions to prevent spam mainly uses the principle of POW, that is, you can spam me, but there is a price to pay.

Of course, the original anti-spam rationale was the use of CPU-restricted functions.

In 1992, IBM research scientists Cynthia Dwork and Moni Naor published a paper on CRYPTO entitled “Stopping spam through Pricing”, in which they proposed the possibility of using the capabilities of CPU-constrained functions to stop abusers from sending spam.

The idea is that if the cost of spamming is low, spam can flourish. Spam can be reduced if you can add additional computational costs to sending mail in the form of expensive CPU calculations. Using cpu-constrained functions, which consume CPU resources for each message, prevents a large amount of spam from being sent in a short period of time.

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

Because fast cpus can compute much faster than slow cpus. In addition, high-end computer systems also have complex pipelining and other computationally optimized features. Thus, spammers with high-end systems are hardly affected by this CPU-constrained function.

As a result, the performance of different user machines will lead to a very large difference in computing time. For example, an algorithm that takes a few seconds on a more advanced computer might take a minute on an older computer and a few minutes on a less powerful phone is definitely not acceptable to mobile users.

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

This approach is to use memory-constrained functions. A memory constrained function is one whose computation time is governed by the time that memory is accessed. Memory-constrained functions access the location of large memory areas in unpredictable ways, making caching unavailable to improve performance.

There are also industrial reasons for the limited use of memory rather than CPU, and while CPU computing speed has increased dramatically in recent years, relatively little progress has been made in developing faster main memory. Therefore, we can expect to see more and more applications of memory-constrained functions in the future.

This article is available at www.flydean.com/memory-boun…

The most popular interpretation, the most profound dry goods, the most concise tutorial, many tips you didn’t know waiting for you to discover!