How to find the total memory used during the execution of the code?

To find the efficiency of my algorithm, I searched this site:

URL: https://www.kdnuggets.com/2022/09/calculate-algorithm-efficiency.html

After studying this site, I want to know how much memory is used by my algorithm fpa1 during execution. I have shared fpa1 along with supporting files in the attachment. One can run main to run the algorithm fpa1.

[Walter Roberson]

JK=randperm(n);

That can be improved to

JK=randperm(n, 2);

as you do not use more than two of the results.

[Walter Roberson]

Your simplebounds can be improved by using min() and max()

values = min(max(values, Lowerbounds), Upperbounds)

I keep getting the order confused for that, thinking that "surely" you should use min() to implement Lowerbounds but No, you need max() for Lowerbounds like I write above.

[Sadiq Akbar]

@Walter Roberson

Sorry I didn't see these statements before. I found the following line in fpa1:

JK=randperm(n);

and replaced it by yours. But I cannot locate the follwoing line in fpa1:

values = min(max(values, Lowerbounds), Upperbounds)

The function simplefounds is used in three different lines. In lines 29 and 34, it is like this:

S(i,:)=simplebounds(S(i,:),Lb,Ub); 

In line 53, it is like this:

function s=simplebounds(s,Lb,Ub)

Now which one are you talikg about? You mean that I shoud comment the whole function and use this:

values = min(max(values, Lowerbounds), Upperbounds)

or what should I do?

[Walter Roberson]

Replace

function s=simplebounds(s,Lb,Ub)
% Apply the lower bound
ns_tmp=s;
I=ns_tmp<Lb;
ns_tmp(I)=Lb(I);
% Apply the upper bounds
J=ns_tmp>Ub;
ns_tmp(J)=Ub(J);
% Update this new move
s=ns_tmp;
end

with

function s = simplebounds(s, Lb, Ub)
   s = min(max(s, Lb), Ub);
end

Answer 1

[Dinesh]

Hi Sadiq Akbar,

The profile function allows you to measure the execution time and memory usage of your code, both for individual functions and for the entire program. To use this function, simply type "profile on" in the command prompt, then run your code, and then type "profile viewer". This will open a graphical interface that displays the performance information.

In your case, I ran the "main.m" file which you mentioned also runs "fpa1.m".

I see the following results by using the profile function for the files that you have attached.

This method can help you find the memory used by the algorithm.

[Sadiq Akbar]

Thanks a lot dear Dinesh for your kind response. wehere can I see memory usage?

[Walter Roberson]

Historically

profile -memory on

The -memory option is not documented; I do not know if it still works

[Sadiq Akbar]

Thanks a lot for your kind response dear Walter Roberson. Yes, it works. But I don't understand how much memory is used by fpa1? How much time is taken by fpa1. When I run fpa1 whithout profile on, then with tic and toc commands, its time is less but when I run it with profile on, then it takes more time. Why? Or its me that doesn't understand it?

[Walter Roberson]

There is overhead required to measure execution counts and times for every line and function. That inherently results in profiled code taking longer than if profiling were not on.

Furthermore, when profiling is on, matlab executes the function pretty much as-written. Normally the execution engine is permitted to reorder statements and to substitute high-performance library calls for statements, so the executed code might not be exactly the same as what was written. As an example, a loop that does C(k) = 5*A(k) + 9 might be converted as a whole into a multicore library call that uses streaming hardware instructions. The replacement calls only occur once rather than once per element, but when you are profiling the substitution is not done and you get counted for each execution of the loop body. This is another reason why profiled code takes longer.

Answer 2

[Walter Roberson]

Asking how much memory matlab needs for an algorithm is the wrong question if you are trying to measure how much memory an FPGA would need.

For FPGA if you worrying about memory in the sense of trying to find the smallest FPGA that you can get away with, because larger FPGA "cost more", then although price is a valid concern, smallest is not always least expensive:

• because of economy of scale, the most popular FPGA might be less expensive than the smallest number of gates
• manufacturers compete on speed as well as gates, so potentially an item with a higher number of gates might also have been manufactured with a denser die and run faster
• heat dissipation can reflect manufacturer's design care, so smallest number of gates is not necessarily the coolest running
• smallest number of gates does not necessarily mean highest quality materials
• in the semiconductor industry it has been common to manufacture batches of chips, scrap the ones that fail completely, and test the rest, with the highest performing ones being sold for the highest price, and the lower performing ones sold at lower prices. For systems with on-board memory such as FPGA, it is common for some of the gates to fail in manufacturing, leading the manufacturer to burn out the traces to those gates. The result can then be graded according to number of functioning gates. The FPGA sold as having the smallest capacity is not necessarily one designed around that small capacity: it might instead reflect a larger design that "failed down" to the lower grade. You have to decide whether that is good enough for your purposes. Are these broccoli flowers small because they are quality broccoli harvested young, or because they were what was left over from cutting out the bad parts of larger mediocre broccoli?

[Walter Roberson]

If you have a barely-big-enough FPGA, then if (say) sin(2*pi*t)is used several places in the code, should you use a memory register to store the result, or should you calculate it each time you need it? If the context includes code such as

total = 0;
for k=1:length(t) 
  total = total + A(k) * sin(2*pi*t(k));
end

and that kind of work happens multiple times with different A arrays, then if you have the available memory, compute and store the sin() and then the remaining times are just retrieving the vector and multiplying, which might even possibly be possible to "stream" through different computation stages. But if you are required to use the least memory you can, then you compute the values every time, to save on memory. Which is more important: smallest or more efficient?

[Walter Roberson]

When smallest memory is the goal then your algorithm should often clear variables as soon as they are no longer needed. Even if the cleared memory is only a single numeric location, that could potentially be the difference between being able to squeeze into a smaller FPGA or needing a larger one. Each simultaneous memory element needs hardware allocated to it. So you might need to think carefully about rearranging your code in ways that humans might find harder to understand but which saves one simultaneous memory element, because you are hardware bound. It's sort of like a boxer deliberately skipping a meal before weigh-in in order to qualify for a lower weight class.

[Sadiq Akbar]

Thanks a lot for your kind and detailed responses dear Walter Roberson. But truly speaking, I didn't understand what you have discussed. I ususally ask questions here in this forum and many give me good respons including you because I also remember you. But now one of my friends has asked me what is the efficiency of your algorithm? Then he added efficiency is determined by two factors and they are execution time and memory used in the execution. Then he give me this task. So I am able to find the execution time now with the help of this forum but this is the next question i.e., how much memory is used by the algorithm in its execution? I tried to find it with the help of "profile on" but in vain. So, again, I will ask how to find the used memory during the execution of fpa1?

[Walter Roberson]

You might be interested in https://www.mathworks.com/matlabcentral/fileexchange/50608-counting-the-floating-point-operations-flops

How much memory is used by an algorithm is not a precise question. Suppose you have

A = zeros(1,10);
B = A + 1;
C = B * B'

C = 10

After the assignment to B, A is no longer used. Can we declare that at that point, A is effectively released by the algorithm and no longer counts against the memory usage? With it no longer being used, then we could optimize the sequence in principle as saying that B will become an alias for the block of memory designated by A, with the incrementing by 1 happening "in-place".

How much memory does it take to implement the B * B' operation? The language model says that first you have to compute B' and then do an algebraic matrix multiplication, but it turns out that in practice B * B' is a computation that is specially recognized by MATLAB, and for large enough arrays, a high-performance computation library is called that does not need to explicitly form B' . The library computation is multi-core, so temporary storage on multiple cores is used -- potentially more memory than would be required using naive triple-nested loops. Do we count the memory on the multiple cores? Do we count the memory as-if the traditional triple-loop was being executed? Do we count the memory as-if underneath MATLAB was using one of the theoretical arrangements that can reduce the number of computations for a matrix multiplication from O(N^3) to O(N^2.8074) [Stressen algorithm] -- something that might require additional temporary memory ?

[Sadiq Akbar]

Thanks a lot for your kind and detailed responses dear Walter Roberson. You mean that the question, about how much memory, used is basless? You mean that one cannot say that how much memory is used by an algorithm during execution? If, so then why is this:

URL: https://www.kdnuggets.com/2022/09/calculate-algorithm-efficiency.html

[Walter Roberson]

The memory required to hold the code for the algorithm

MATLAB does not give you any way to calculate that. You can look at the size of the .m file, but that size will include whitespace and space for any comments, MATLAB tokenizes the code when it processes it, so for example

while t < 5

the while is probably going to be represented in some kind of binary code, and there would be some kind of tree data structure, and MATLAB generates machine code, and MATLAB stores debugging information... MATLAB is not a compiler where you could compile to machine code and strip the debugging information and then ask about the size of the output file.

The memory required to input the data

Compare

A = {}

A =

  0×0 empty cell array

B = 17.8

B = 17.8000

C = {B}

C = 1×1 cell array
    {[17.8000]}

whos A B C

  Name      Size            Bytes  Class     Attributes

  A         0x0                 0  cell                
  B         1x1                 8  double              
  C         1x1               112  cell                

We know that there must be a symbol table entry for A and that the symbol table must contain the name of the variable and contain information about the size and type of the variable, but whos does not tell us how much space those things take. We can then look at B and see that 8 bytes is recorded, which is exactly the size of one 64 bit double precision floating point number. Now we can look at C, which is a cell that contains a copy of the same number as in B -- in fact in this example, the cell entry will point to exactly the same memory that the data portion of B points to. So the data portion of C contains 8 bytes, leaving 112-8 = 104 bytes. That 108 bytes does not include storage to tell us how big or what type C itself is -- if it did then we would be seeing non-zero bytes for A. So those 104 bytes must be the storage required for the data portion of a symbol table: the data portion of C is a list of pointers to size-and-type-and-data-pointer blocks. We cannot deduce from this how much storage is required to store a variable name but we can deduce from this that 104 bytes is needed to store size and type and data pointers in MATLAB.

Question for you now: does that mean that if you have a scalar value like B in your code, that you should count 112 bytes as the amount of storage it needs? Plus 8 bytes for every additional double precision entry if B is an array? Or should we be counting only the 8 bytes of double precision data?

The memory required to output the data (some algorithms, such as sorting algorithms, do not need memory to output data and usually just rearrange the input data).

In MATLAB, if you have a function of the form

function outvalue = copy(invalue)
   outvalue = invalue;
end

then how much space is needed for output? MATLAB uses "copy-on-write" so the size-and-type-and-data-pointer block associated with invalue will be written associated with the symbol outvalue -- using a local symbol table entry but not taking any additional memory otherwise. But if you have

function outvalue = incr(invalue)
   outvalue = invalue + 1;
end

then MATLAB has to generate a temporary new size-and-type-and-data-pointer block in order to undertake the invalue + 1 operation (does not overwrite invalue ) and that size-and-type-and-data-pointer block gets associated with the local symbol outvalue so memory is needed for output. We will postpone for a moment the question of how much memory exactly.

Now suppose the code were

function invalue = incr(invalue)
   invalue = invalue + 1;
end

The MATLAB language model is to generate a temporary new size-and-type-and-data-pointer block in order to undertake the invalue + 1 operation (not overwriting invalue) and that new size-and-type-and-data-pointer block would be returned.

But... in some limited cases MATLAB can treat the above as an in-place modification, using the same input and output memory. It doesn't typically happen, but it can happen.

Now we have to ask: is the question how much memory MATLAB needs to store and execute this code? Or is the question how much memory would be required by C code generated by the MATLAB to HDL tool ??