Generating 0 and 1 sequences - Performance Issue

[dan07]

Hello all.

I did this code to generate all possible combinations of 0 and 1, for n elements. It works very well until around n=20, after that the application freezes and I have to restart Labview. Does somebody have a suggestion to do the same operation saving CPU work? I know that we are talking about billions of array elements, but I really need to do this.

Thanks

Dan07

[stevem181]

Hi Dan07,

You can get some improvement by pre-allocating the array (see example).

The program ran out of memory on my machine at n= 24 but did not crash.

steve

[stevem181]

Actually, the program I posted quits at n = 23 - out of memory. However, if you use a string of 23 (n) bytes when you initialize the array instead of an empty string, it will work for n = 23. But not for n = 24 (on my PC anyway).

Your PC memory and 32 bit vs 64 bit will impact how large arrays can get. My machine has 2GB RAM (about 1 GB free) and is 32 bit.

The next questions are: how far do you need to go (n=?)?  In what format do you need the data?
That will dictate what method would work for you.

For example you could:

o save the data to a file
o convert the result to numbers (strings use 8 bits of space for each bit of data)
o Look at ways to deal with large arrays (search the postings)

Extending Virtual Memory Usage for 32-bit Windows

http://zone.ni.com/reference/en-XX/help/371361E-01/lvhowto/enable_lrg_ad_aware/ 

Managing Large Data Sets:

https://forums.ni.com/t5/Example-Code/Managing-Large-Data-Sets-in-LabVIEW/ta-p/4100668

Hope this helps,
steve

[RavensFan]

I don't think your modification really changes much.  With the N wired to the For loop and the autoindexing at the tunnel, LabVIEW will know how large of an array to allocate even in the OP's original VI.

The real question is why do you need such a large string array of text characters of 0's and 1's?  What do you do with this string array?  Why can't you generate the string from the number on an as needed basis?

The problem is you are creating a memory hungry structure.  In order to represent each bit, you are using an entire byte.  So as N (number of bits gets larger) each array element uses N bytes.  (It might actually be larger since I think there is one or more size bytes associated with each string, but for now I'll ignore that.)  Where things really blow up is the number of array elements is 2^N.  So your total number of bytes to store the array is at least N * 2^N.  That number gets big really fast as N gets larger.

N=20 size of array is at least 20.9 MB.  (Not too bad). 

N=21 size=44MB

N=22 size=92.2MB

N=23 size = 192.9 MB

N=24 size = 402.6 MB  (now you are really talking some serious memory)

And I think those numbers might even double again because of storing them on the front panel as well as the wire.

And how long does it take to execute the VI at N=20 or N=24?

[RavensFan]

While I don't think LabVIEW is handling the two variations any differently due to the For loop with a preallocated array and a shift register vs. an autoindexing tunnel, I think you'd still have memory thrashing.  Why?  Because with string arrays, even though they are being preallocated with a fixed number of elements, there is no way to know what the final size of the array will be since each element of the array can vary in length.

[altenbach]

I agree with Ravens that the "preallocation" version makes no difference. It just clutters the diagram more for no added benefit. A FOR loop with an autoindexing output tunnel allocates the correct size automatically.

What are you actually trying to achieve with all this?

It does not seem to make a lot of sense to simply fill available memory just for fun. You can do that in many other ways. 😄

[altenbach]

---

dan07 wrote:

..., but I really need to do this.

---

Do what? How many digits do you want?? In what form do you need the output?

Since can can generate any binary combination from scratch in an instant, I don't see a reason to try to stuff them all into RAM.

Sooner or later you'll run out of resources. Maybe you can stream the strings to disk instead of keeping them all in memory? Maybe generate a relevant subset on demand?

Here's a way to go to 25, but you cannot go much higher no matter what you try.

Message Edited by altenbach on 12-02-2009 11:19 PM

[TCPlomp]

---

Ravens Fan wrote: The problem is you are creating a memory hungry structure.  In order to represent each bit, you are using an entire byte.  So as N (number of bits gets larger) each array element uses N bytes.  (It might actually be larger since I think there is one or more size bytes associated with each string, but for now I'll ignore that.)  Where things really blow up is the number of array elements is 2^N.  So your total number of bytes to store the array is at least N * 2^N.  That number gets big really fast as N gets larger.

---

Since a string is of dynamical lenght, the compiler cannot know the amount of data needed to store, it will only allocate an array of strings which is quite worthless unless you use a fixed size.

Moreover every element is preceded by a length INT (4 bytes). So the total footprint is even bigger.

Edit: I should have known altenbach was in... but hey mine is a snippet.

Ton

Message Edited by TCPlomp on 03-12-2009 11:44 AM

[altenbach]

---

TCPlomp wrote:

Edit: I should have known altenbach was in... but hey mine is a snippet.

---

Basically the same code, except that I set the format with about 30% of the effort .... 😮 😉

[dan07]

Hello all

Thanks for the help. I am working with a signal that has several peaks and I use a peak detector tool to detect them.  Next, I get the magnitude of all these peaks and calculate the standard deviation of these values. Nervetheless, sometimes I want to play with the peaks and use some of them and not all. Because of this I would like to generate a array of all possible combinations of 0 and 1, and use these sequences to use or not the peaks for the calculation of the standard deviation. The number of peaks is around 30 and 50 and I will use only the 0 and 1 sequences that use more than 50% of the peaks.

Example: If I have a signal with 38 peaks I will generate an array with 2^38 sequences of 0 and 1, and use the sequences that have at least 19 numbers 1 (use the peak) to generate a list of standard deviation values. After that I will sort the array of the standard deviations and get the lowest value.

Also, I tried to generate small arrays with the sequences. For example, if I want 2^8 sequences (256 sequences), I can run the VI the first time and get only the first 64 sequences. Next, run the vi again and get the next 64 sequences and so on. Doing this I can keep using arrays of 64 values and the only thing that I have to change is to sum the size of the sequence to the iteration of the for loop before it creates the 0 and 1 sequence. Next, instead of putting all these values to an array, I created several TXT files with them and later I merged all the files in a single one.

I  think that I can use this approach to solve the problem because even if we work with 2^30 sequences. If we generate only 500000 (for example) for each VI run, later we can merge all the TXT files with the sequences. Nevertheless, I don't know how time consuming will be the proccess of merging these files.

Thanks

Dan07