Thread: Complete newbie - problems with arrays

Originally Posted by SPowell42

p.s. forgot to give the error. Using codeblocks, the code seems to blow up when allocating the array - I don't see the first cout where it says the array is created. I see errors like the following:

Process terminated with status -1073741571 (0 minute(s), 4 second(s))

Figure out the name and version of your compiler.
Or, put the word static in front of the array declaration.
You are exceeding the stack size your compiler or OS defaults to using.

Tim S.

Tim, putting static in front of the array declaration:

Code:

const long long int arraySize = 1000000000;
int main()
{
    static int myArray [arraySize];
    long long int sum = 0;

works - but now I'm hitting another error (with the 32 bit compiler). When I increase the size to 1 billion, I'm getting a slightly different error:

=== Build: Debug in Compare array speed 32 bit (compiler: GNU GCC Compiler) ===|
C:\Users\m17xr4\Documents\C++ Programs\Compare array speed 32 bit\main.cpp||In function 'int main()':|
C:\Users\m17xr4\Documents\C++ Programs\Compare array speed 32 bit\main.cpp|9|error: size of array 'myArray' is too large|
...


When I try the same using the 64 bit compiler, I get a different error message (tried it in both "Debug" and "Release":

||=== Build: Release in Compare array speed 64 bit (compiler: GNU GCC Compiler 64bit) ===|
relocation truncated to fit||R_X86_64_PC32 against symbol `mingw_initltsdrot_force' defined in .bss section in d:/codeblocks/mingw64/bin/../lib/gcc/x86_64-w64-mingw32/4.8.2/../../../../x86_64-w64-mingw32/lib/../lib/libmingw32.a(lib64_libmingw32_a-tlssup.o)|
relocation truncated to fit||R_X86_64_PC32 against symbol `mingw_initltsdyn_force' defined in .bss section in d:/codeblocks/mingw64/bin/../lib/gcc/x86_64-w64-mingw32/4.8.2/../../../../x86_64-w64-mingw32/lib/../lib/libmingw32.a(lib64_libmingw32_a-tlssup.o)|
relocation truncated to fit||R_X86_64_PC32 against symbol `mingw_initltssuo_force' defined in .bss section in d:/codeblocks/mingw64/bin/../lib/gcc/x86_64-w64-mingw32/4.8.2/../../../../x86_64-w64-mingw32/lib/../lib/libmingw32.a(lib64_libmingw32_a-tlssup.o)|
relocation truncated to fit||R_X86_64_PC32 against symbol `mingw_initcharmax' defined in .bss section in d:/codeblocks/mingw64/bin/../lib/gcc/x86_64-w64-mingw32/4.8.2/../../../../x86_64-w64-mingw32/lib/../lib/libmingw32.a(lib64_libmingw32_a-charmax.o)|
relocation truncated to fit||R_X86_64_PC32 against symbol `mingw_app_type' defined in .bss section in d:/codeblocks/mingw64/bin/../lib/gcc/x86_64-w64-mingw32/4.8.2/../../../../x86_64-w64-mingw32/lib/../lib/libmingw32.a(lib64_libmingw32_a-mingw_helpers.o)|
relocation truncated to fit||R_X86_64_PC32 against symbol `_fmode' defined in .bss section in d:/codeblocks/mingw64/bin/../lib/gcc/x86_64-w64-mingw32/4.8.2/../../../../x86_64-w64-mingw32/lib/../lib/libmingw32.a(lib64_libmingw32_a-xtxtmode.o)|
relocation truncated to fit||R_X86_64_PC32 against symbol `__onexitend' defined in COMMON section in d:/codeblocks/mingw64/bin/../lib/gcc/x86_64-w64-mingw32/4.8.2/../../../../x86_64-w64-mingw32/lib/../lib/libmingw32.a(lib64_libmingw32_a-atonexit.o)|
relocation truncated to fit||R_X86_64_PC32 against symbol `__onexitbegin' defined in COMMON section in d:/codeblocks/mingw64/bin/../lib/gcc/x86_64-w64-mingw32/4.8.2/../../../../x86_64-w64-mingw32/lib/../lib/libmingw32.a(lib64_libmingw32_a-atonexit.o)|
relocation truncated to fit||R_X86_64_PC32 against symbol `__imp__fmode' defined in .idata$5 section in d:/codeblocks/mingw64/bin/../lib/gcc/x86_64-w64-mingw32/4.8.2/../../../../x86_64-w64-mingw32/lib/../lib/libmsvcrt.a(dqrgbs00220.o)|
relocation truncated to fit||R_X86_64_PC32 against symbol `_newmode' defined in .bss section in d:/codeblocks/mingw64/bin/../lib/gcc/x86_64-w64-mingw32/4.8.2/../../../../x86_64-w64-mingw32/lib/../lib/libmingw32.a(lib64_libmingw32_a-_newmode.o)|
d:\codeblocks\mingw64\bin\..\lib\gcc\x86_64-w64-mingw32\4.8.2\..\..\..\..\x86_64-w64-mingw32\lib\..\lib\crt2.o:crtexe.c|| additional relocation overflows omitted from the output|
||=== Build failed: 11 error(s), 0 warning(s) (0 minute(s), 0 second(s)) ===|



Obviously I need to get to the point where I understand how to read the errors. But searching on the web, I found several people quoting that the only limits on array size were the "max size of an integer". Even if the compiler is only using a 32 bit integer...that should hold 4+ billion (if unsigned) or 2+ billion if signed.

Thanks,
Scott

Originally Posted by SPowell42

But searching on the web, I found several people quoting that the only limits on array size were the "max size of an integer". Even if the compiler is only using a 32 bit integer...that should hold 4+ billion (if unsigned) or 2+ billion if signed.

I'd say that limit should be the maximum value of std::size_t, otherwise sizeof applied to the array cannot result in a valid value. There may also be a limitation due to std::ptrdiff_t, otherwise subtracting pointers to different elements in the array cannot result in a valid value. But practically, you have other limits imposed by the hardware, e.g., the amount of contiguous memory available to the process, though I believe this will only show up at run time. In your case, it seems you have a compile error and then a link error, so perhaps there are other limits imposed by the implementation. Realistically though, do you really need so much memory up front? There's also the option of say, using a std::vector (possibly with a custom allocator), but I would expect you to run into problems eventually too.

before you put static in front of it, you were probably running into the default stack size allocated by the compiler. on windows, with visual C++, it's 1MB, and on MinGW, it's 2MB, so your 4MB array was too big. now that you made it static, and you're trying to go to 1 billion elements, you're likely hitting a limit on the maximum amount of memory a 32-bit windows process can have allocated to it. normally this is 2GB, but with some tweaking of the compiler, and only on a 64-bit windows OS, you can get 4GB, but that's still probably not enough when you try to create a 4GB array of int, in addition to the code and other data in your program.

Summary:
The first example crashes because you create an array bigger than the stack (as noted, typically 1-2 MB).
The second example fails to compile because you are creating an array bigger than 4 GB (you cannot address more than 4 GB with a 32-bit address, which is the limit of 32-bit processors).
The third example fails due to some compiler limitations most likely. What it means is that the linker couldn't fit your array into your executable.

As for fixes... using std::vector is probably as good solution, given what we know so far. Use .push_back() to add items. Do not allocate memory up-front.

Well, I seem to be having more luck when using memory allocation with pointers than trying straight with arrays. Note this is all with the gnu g++ 64 bit compiler. I'm able to get the following code to compile and reserve 4 GB of memory:

Code:

#include <iostream>
using namespace std;int main()
{
    const long long int gigabytes = 1 * 1024 * 1024 * 1024;  // will be 4 GB because int = 4 bytes
    long long int sum = 0;
    int *ptr_memory = new int [gigabytes];
    cout << "I've got the memory!!!" << endl;
//      populate with 1s
    for (int i=0;i < gigabytes; i++)
        {
        ptr_memory[i] = 1;
        }
//      now sum them up
    for (int i=0;i < gigabytes; i++)
        {
        sum += ptr_memory[i];
        }
    cout << "The sum is " << sum << endl;
    delete[] ptr_memory;
    ptr_memory = NULL;
    return 0;
}

I can sometimes get it to work with 8 GB (i.e. 2 * 1024 * 1024 * 1024), but not always. However, high level I think this should take care of me - even if I have a fact table with a billion rows, I can handle them one column at a time, which should (???) take care of me (though I'd be worried about DOUBLES).

I appreciate the help everyone, hopefully I get on track and can start troubleshooting better for myself. Thanks for your input and ideas!

Thanks,
Scott

Originally Posted by SPowell42

I seem to be having more luck when using memory allocation with pointers than trying straight with arrays.

Then you should use std::vector.

Originally Posted by SPowell42

Note this is all with the gnu g++ 64 bit compiler.

but are you building a 64-bit program? even with the 64-bit compiler, the default is still to build a 32-bit executable. are you using the -m64 switch?

I agree with suggestions already made by Elysia and laserlight: use a std::vector rather than the two approaches you've tried so far (array or a pointer with dynamically allocating memory).


I'd also query why you need an array that large in the first place. While there are certainly occasions where a large array (or a std::vector with a lot of elements) is helpful, and a few occasions where it is necessary, many times using a large array is a sign of not having properly thought through the requirement (for example, a lot of people seem to default to reading a whole file into an array for processing and output, rather than reading, processing, and saving a small chunk at a time - which, with well-chosen techniques, can be at least as effective or efficient while consuming less memory).

I'll pretend I believe you're trying to solve a problem, rather than that you fished for an example that (you think) justifies what you're doing.


You might want to read up more on database design, such as the definitive text by Chris Date. There are plenty of great authors in the area.

Yes, joins can be expensive as database operations go, but there are various strategies for mitigating the costs (normalising, indexing, different join types, etc) that don't rely on loading a whole database into memory even when they touch a large part of a large database - and do not cause available physical or virtual memory to impose an upper bound on the size of the database.

Joins and sorts involving entire databases (or data warehouses) are pretty rare in practice anyway, and smart engines break them down into a sequence of smaller operations that add up to the whole.

It makes no sense to design a new database from scratch in an unfamiliar language. Why aren't you using existing databases out there which companies have spent thousands of hours improving, tweaking and optimizing?