[RESOLVED] VB6: 100,000,000,000,000,000 Element array possible?

[Tontow]

While Playing around I managed to stumble across a way to create an abnormally large 2D array with the Long variable type.

My target was a 2D array with 1,000,000,000,000,000,000 elements, But that wasn't quite possible with this method.
I did however manage to achieve a close 100,000,000,000,000,000 elements.

I haven't coded reading/writing to the array, but this should give you an idea of how I plan on doing it.

Main form:

Private myvar(100000000) As New Class1

Class module:

Private LargArray(1000000000) As Long

This should give me a possible array size of 100,000,000 x 1,000,000,000 , where as a normal long array can only be 10,000 x 10,000 in size.


Opinions?
Dose anyone foresee any possible problems with this method?

[RobDog888]

Um, crashing some systems due to an extremely large memory overhead and usage. Why the heck would you need one so large? The larger the array the more memory will be in use.

[Tontow]

I really don't need on 'that' big; about 1/4 of that size would sute my needs.

Would this method be better/faster than http://www.vbforums.com/showthread.php?t=502078 (Code bank vershion: http://www.vbforums.com/showthread.php?t=504649 ).

[03myersd]

What on earth do you need an array with 25,000,000,000,000,000 elements for? Bear in mind that if each elements takes up 8 bytes then this array is 200,000,000,000,000,000 bytes, 195312500000000 KiloBytes, 190734863281.25 MegaBytes, 186264514.9 GigaBytes, 181898.9 TeraBytes, 177.6 PetaBytes.

Your not going to find a computer with that amount of memory for a long time yet.....

[Hack]

I don't think many mainframe computers have that kind of memory.

Even at a 1/4th of that size, you are still taking about a sizable chunk.

What is your end goal with this?

[03myersd]

Distributed servers (such as googles) have that sort of HDD space, but there is not way that array would fit into RAM? At this day in age it is impossible.

[RobDog888]

Are you trying to overflow a buffer or something with data?

[LaVolpe]

From previous posts by OP, I believe this post is in relation to an A* path finding algorithm. The OP appears to have a very large game board and is trying to figure out how to navigate it. I think the realization must come that one cannot use arrays for such large game boards and different methods should be used to reduce the area to sizes that can be used comfortably with/without A* in mind. Also, even if it were possible to generate such an array; navigating it with A* would take minutes to hours I would think; not to mention that A* requires yet additional arrays/trees to prevent path recursion and for lookups.

[RobDog888]

How did you get that out of the OP's posts? It only shows arrays and the links are not dealing with games or ???

[LaVolpe]

How did you get that out of the OP's posts? It only shows arrays and the links are not dealing with games or ???

Psychic I've replied to a couple of them. These should help in better understanding for any that can provide additional assistance.
http://www.vbforums.com/showthread.php?t=505188
http://www.vbforums.com/showthread.php?t=514975

[RobDog888]

Ah ok. I'm out of the loop.

I need more Psychic powers Thanks

[mendhak]

Even the tiny A* problems become large ones because it goes exponentially, but there's recursive best first search which is supposed to be more efficient.

http://cs.gettysburg.edu/~tneller/pa...FS_Example.htm

[Tontow]

Hmm. It looks like I will have to find another way of doing what I need.

But lets keep this going to see how big, with in reason, we can get a 2d array to go. Just for the fun of it.


Lets figure something more reasonable.

1 Gigabyte = 1073741824 bytes
1073741824 Bytes / 8 bytes per element = 134217728 Elements
134217728^.5 = 11585.237502960394639783434028726

So 1 Gigabyte would give me a 11,500 x 11,500 size array.
That isn't much bigger than the 10,000 x 10,000 that you can normally do.

And from what I can calculate a 10,000 x 10,000 long array will take up762.9395 MB?

Dose anyone know the guts of how arrays work?
When I run the code in the first post, the program only uses about 400k according to windows task manager (under a megabyte). That doesn’t seem to match up with the math we have been doing.

[mendhak]

They're stored with an index, each index item obviously pointing to one element. Two-dimensional arrays, though, may be either by each axis of the array matrix or by indexing the individual x-axis elements along the matrix, each as an array.

[LaVolpe]

I can help a little to understand the guts of an array, but the O/S memory management system really comes into play.

In VB, an array always has a 16+byte header that describes the array, its dimensions, LBound/UBound, data type, etc. 16 or so bytes is no big deal.

Now whenever you Dim or ReDim an array, VB must go and ask system for enough contiguous memory to fill the array. All items are initially filled with default values for the array variable type.

This part is theory & others that know more can correct me. Now for these super-sized arrays, you might be able to bypass what memory is actually available because the system could use the system's swap file which consists of some unused disk space. The size of the swap file and size of ram will determine how much is too much -- out of memory along with other considerations too like heap/stack size. Anyway, even if you could use that much memory, the amount of swap file memory pages that must be moved in and out of ram as you access the array should prove to be very slow -- too slow for any game. Users will just uninstall & roll their eyes.

[Tontow]

Psychic I've replied to a couple of them. These should help in better understanding for any that can provide additional assistance.
http://www.vbforums.com/showthread.php?t=505188
http://www.vbforums.com/showthread.php?t=514975

That is correct.

I'm trying to keep ideas separate for those that might want to do something similar in the future. - Board organization and whatnot.


Edit: It is worth noting that the A* that I'm working on will not be used for any game; It will be used to help create, display, and explore documentation of complex tech trees for a game.

[Tontow]

After thinking about it, something is bugging me.

I can run and even compile and run:
Main form:

Private myvar(100000000) As New Class1

Class module:

Private LargArray(1000000000) As Long

And I don't crash or get any errors. - It can't be using 177.6 Peta-Bytes or it would be crashing or getting errors.

Why is it not crashing or coming up with an error?

[Doogle]

What happens when you try to assign a value to an element (eg the last one) of myvar?

[Tontow]

I had to shrink the array just a little bit, but the following works for me without error.
Form:

Private myvar(10000000) As New Class1

Private Sub Form_Load()
myvar(10000000).SetArray 100000000, 2
End Sub

Class:

Private LargArray(100000000) As Long

Public Sub SetArray(y As Long, num As Long)
LargArray(y) = num
End Sub

Still big though. 10,000,000 x 100,000,000


Edit: Still can use upto 5.3290705 petabytes.
And after playing with it, it seems that I have to shrink the array in order to use more of it at one time.

Private myvar(1000000) As New Class1

Private Sub Form_Load()
myvar(1000000).SetArray 1000000, 21
myvar(1000).SetArray 1000, 233
myvar(15).SetArray 10000, 24
myvar(1).SetArray 1, 20
End Sub

Private LargArray(1000000) As Long

Public Sub SetArray(y As Long, num As Long)
LargArray(y) = num
End Sub

Still is 1,000,000 by 1,000,000 with a possable 5.456968 terabytes.
I wonder how much of it I can use befor I get an error?

[Doogle]

Whilst you're conducting these experiments you should bear in mind the basic limitations of 32 bit architecture. With an address width of 32 bits the maximum address space is 4Gb (2^32) using 'standard' Virtual memory mapping.

However, with a 'normally' configured Windows Operating system, 2Gb is reserved for the System and only 2Gb is available for your program code, stack, heap, and data. So, the less code you have the more data you can address and vice versa. (Ignoring any additional limitations VB may implement)

It is possible to modify the 2/2 allocation (4-Gigabyte Tuning) through changing the boot.ini file such that the allocation becomes between 1 and 2Gb for system and the program can use addresses up to 3Gb. The Program's header also needs to be changed to support addressing above 2Gb which is achieved by setting the IMAGE_FILE_LARGE_ADDRESS_AWARE flag at Link time. (Not a particularly easy thing to do with VB as usually the Link process is hidden - we just see "Make project.exe" and it all happens behind the scenes)

Obviously by reducing the amount of memory that the operating system has available will have an overall performance impact since file caches, and the page pools will be smaller. Even with this tuning there are complications since some system DLLs load near the 2Gb boundary and will 'encroach' on some of the program's address space. This means that the application should be aware of the virtual address of alloacted variables and objects, which is something not usually of concern to VB programmers.

Another option you may wish to research is AWE, (Address Windowing Extensions) which allows applications to address more than 4Gb whilst still using 32 bit addressing. It does this by mapping and "windowing" the data in 4Gb 'chunks'. This requires that the physical pages are allocated and locked (ie not pagable -the user must have appropriate rights). Again, the allocating and locking of pages is not something a VB Programmer does, consciously, on a dialy basis.

There is a performance impact on everything else, if you've locked a page of real memory, then it is not available for release and re-allocation to another task. (ie the amount of Real memory available to the rest of the system is reduced by 4K for every page you lock)

Using AWE would mean that you would have to allocate the memory for your large array yourself (eg VirtualAlloc, AllocateUserPhysicalPages etc), manage the mapping and freeing the memory. (Just like implementing your own private paging sub-system) The array would just look like a contiguous number of bytes so you'd have to manage Indexing etc yourself.

[Tontow]

Is a bit array possable in VB6.0? Or is a Byte as small as VB6 can go?

Would I run into the same problems if I used a C++ dll for the array? (Have the array written in C++.)

[szlamany]

This code bank article discusses how to create a pseudo-array (that pages memory off to disk) of any size you want (limited to the size of your disk of course). The array must be of fixed size datatypes (not strings for instance).

http://www.vbforums.com/showthread.p...ighlight=array

Is a bit array possable in VB6.0? Or is a Byte as small as VB6 can go?

Would I run into the same problems if I used a C++ dll for the array? (Have the array written in C++.)

Storing bit array is just a matter of you paging the bits in and out of the bytes of the actual array.

[Tontow]

That stores bytes, not bits.
Also note that I linked to the same topic in my second reply.

I really don't need on 'that' big; about 1/4 of that size would sute my needs.

Would this method be better/faster than http://www.vbforums.com/showthread.php?t=502078 (Code bank version: http://www.vbforums.com/showthread.php?t=504649 ).

But nice try , thanks.
------------------------------------------

The following seems to run quite nicely (at least it did during the 1 hour I let it run). A 50,000 x 5,000 array - 250,000,000 elements. A normal 10,000 x 10,000 array has 100,000,000 elements.

Private myvar(50000) As New Class1

Private Sub Form_Load()
Dim i As Long, m As Long
For m = 5000 To 0 Step -1
For i = 0 To 50000
Debug.Print i & "," & m
myvar(i).SetArray m, 21
Next i
Next m
End Sub

Private LargArray(5000) As Long

Public Sub SetArray(y As Long, num As Long)
LargArray(y) = num
End Sub

Conclusion: You can create abnormally large arrays using this method, but it dose have its limits. The larger the array, the less of it you can use.

[szlamany]

Sorry - didn't see that you linked to that post already...

That stores bytes, not bits.

Storing bits is just you putting a layer on top that extracts the 8 or 16 or 32 bits from whatever "word" size you are storing.

[Tontow]

How would I go about reading/writeing the 8 bits in one byte?

[LaVolpe]

The technique uses bit masking & shifting but this will slow down your procedures even more. For example if a byte = 255 then all 8 bits are set, they each have a value of 1. Bits will either be 0 or 1, nothing else.

255 as a byte = 1 or 2 or 4 or 8 or 16 or 32 or 64 or 128
So to get the bits from the bytes you would do it in reverse
1st bit is: (255\(2^0) And 1)
2nd bit is: (255\(2^1) and 1)
3rd bit is: (255\(2^2) and 1)

In a debug window, add this and change byteVal to values between 0 & 255 to play:

byteVal=255: for m=0 to 7:? (byteVal \(2^m) and 1); " ";:next:?

[szlamany]

The division is unnecessary

Since you are looping and determining the 2^x value simply do

If (ByteVal and 2^x)<>0 Then ' Bit is turned on

Basically AND checks the bit and OR sets the bit. AND NOT turns the bit off.

If (X and 1)<>0 ' sees if the bit is ON

X = X or 1 ' sets the first bit

X = X and not 1 ' clears the first bit

[LaVolpe]

Absolutely correct. Division and/or use of AND become necessary when wanting to check values of more than one bit (i.e., extracing RGB from a Long) -- but does not apply in this case since a single bit value is all that is requested.

[szlamany]

I'm not sure I follow you...

If (X and 2)<>0 Then ' 2nd bit is set
If (X and 4)<>0 Then ' 3rd bit is set
.
.
.
If (X and 32768)<>0 Then ' 15th bit is set

Doesn't seem to me like you need to bit shift down to the first position in order to see if the bit is set or not. Or to even set the bit (with OR) and clear the bit either.

[LaVolpe]

I was trying to say that if you need the value of more than one bit, then shifting may be necessary. Example: If I wanted to know the Green value (8 bits, not just 1) of vbWhite, I can do it a couple of ways:
1. green = (vbWhite \ &H100&) And 255
2. check all 8 bits individually and OR them together

But again, when wanting to check just one bit; shifting is not necessary as you pointed out.

[szlamany]

Ok - I misunderstood you

[Tontow]

50,000 x 5,000 is big enough for now. (Its big and fast. It takes up some memory, but thats the tradeoff I'm willing to make.)


But just for fun. How Big dose everyone think we could get a bit array?

[03myersd]

Well if each element was a bit then that is 30MB so you are looking at around 3000/30 = 100

So basically 100 times that.

By the way: I assumed the users have 4GB of RAM and is using a 32 bit OS. When the OS is running it would take up a few hundred MB. Leaving roughly 3GB of memory. Thats where I got the numbers from.