Hi!

What is the 16M limit on the array length for?
Recently I needed more space but when I declared a ~25M array of ubytes I
quickly ran into a compile error saying
> file.d(5): index 25000000 overflow for static array

An investigation got me to lines 1592-1593 of src/dmd/mtype.c stating
> if (n2 >= 0x1000000)    // put a 'reasonable' limit on it
>     goto Loverflow;
with the above message printed at Loverflow.

I wonder what's the 'reason' on that limit.

Eventually, I didn't give up and, with a bit of disassembly, lifted the limit in
the comparison to 768M (you know, there doesn't seem to be a way to just
recompile the code, since it's incomplete). At first, everything looked fine: my
program compiled and ran and the result of using that ~25M array was the same as
in C (by the way, there were no such problems with dmc compiler). But later, I
discovered that:
1. Trying to allocate a bigger static array (say, ~100M) just hangs the compiler
up;
2. Trying to allocate even a ~25M array of bits (which should consume less than
4M space) does the same - the compiler hangs up.
Could anyone explain what's the problem?

I'm new to D Programming Language. I discovered it only recently and decided to give it a try. Currently, I seem to like it's look and feel, although such undocumented misfeatures of dmd, the only compiler I know of, do present a bit of trouble.

Thanks in advance,
Ivan Kazmenko.

gassa@mail.ru wrote:
> Hi!
> 
> What is the 16M limit on the array length for?
> Recently I needed more space but when I declared a ~25M array of ubytes I
> quickly ran into a compile error saying
>> file.d(5): index 25000000 overflow for static array
> 
> An investigation got me to lines 1592-1593 of src/dmd/mtype.c stating
>> if (n2 >= 0x1000000)    // put a 'reasonable' limit on it
>>     goto Loverflow;
> with the above message printed at Loverflow.
> 
> I wonder what's the 'reason' on that limit.


I've put the same limit in my own array template I use for C++ projects.  My reasoning was that you shouldn't be using a dynamic array for such huge memory blocks because of the potential costly resize. The limit helped me catch some bugs where array were being used and caused a significant performance bottleneck. I rewrote those parts with a simple malloc/free or VirtualAlloc. In D there might be the added complexities of the garbage collector. Remember that it keeps scanning the allocated memory for pointers. For these huge blocks it's better to use some other memory allocation scheme.

L.

In article <e2m3ll$v0k$1@digitaldaemon.com>, gassa@mail.ru says...
>
>Hi!
>
>What is the 16M limit on the array length for?
>Recently I needed more space but when I declared a ~25M array of ubytes I
>quickly ran into a compile error saying
>> file.d(5): index 25000000 overflow for static array
>
>An investigation got me to lines 1592-1593 of src/dmd/mtype.c stating
>> if (n2 >= 0x1000000)    // put a 'reasonable' limit on it
>>     goto Loverflow;
>with the above message printed at Loverflow.
>
>I wonder what's the 'reason' on that limit.
>
>Eventually, I didn't give up and, with a bit of disassembly, lifted the limit in
>the comparison to 768M (you know, there doesn't seem to be a way to just
>recompile the code, since it's incomplete). At first, everything looked fine: my
>program compiled and ran and the result of using that ~25M array was the same as
>in C (by the way, there were no such problems with dmc compiler). But later, I
>discovered that:
>1. Trying to allocate a bigger static array (say, ~100M) just hangs the compiler
>up;
>2. Trying to allocate even a ~25M array of bits (which should consume less than
>4M space) does the same - the compiler hangs up.
>Could anyone explain what's the problem?
>
>I'm new to D Programming Language. I discovered it only recently and decided to give it a try. Currently, I seem to like it's look and feel, although such undocumented misfeatures of dmd, the only compiler I know of, do present a bit of trouble.
>
>Thanks in advance,
>Ivan Kazmenko.

Why the need for such a large static array? Can't a dynamic array be used in your code instead?

Hi again!

me:
>> What is the 16M limit on the array length for?
>> I wonder what's the 'reason' on that limit.

Lionello Lunesu:
>I've put the same limit in my own array template I use for C++ projects.
>  My reasoning was that you shouldn't be using a dynamic array for such
>huge memory blocks because of the potential costly resize. The limit helped me catch some bugs where array were being used and caused a significant performance bottleneck. I rewrote those parts with a simple malloc/free or VirtualAlloc. In D there might be the added complexities of the garbage collector. Remember that it keeps scanning the allocated memory for pointers. For these huge blocks it's better to use some other memory allocation scheme.

I definitely won't want to resize such a huge array, at least not too often. My array is static. For resizing, I usually use the technique of doubling the requested index when it exceeds the current limit.

If my too-many-M array is scanned for pointers, which I do not store there, do I have a way of forbidding it?

Dave:
>Why the need for such a large static array? Can't a dynamic array be used in your code instead?

I could use dynamic array, yes, but I don't see any benefit since its size is fixed. Please explain why it could be better.

The current problem which requires such a big array is related to prime numbers - it's a program for a programming contest at http://recmath.org/contest/ (you know, various contests are the best way to learn something new, if you have enough free time, of course). I use a sort of Eratosphenes sieve for prime numbers, and the larger the sieve, the faster the program runs (for large numbers, it uses Miller-Rabin primality test which is significantly slower than seeking a bit in an array, with paging, caching, and other modern RAM techniques included). I work with a teammate, we share ideas but write different implementations. He uses Delphi, and I decided to try D, but currently my implementation sucks 'cause I have no 'legal' way to use an array that big.

Current problem aside, there are many ways to use my current amount of RAM, which is 768M, indexing it with only a couple of arrays. It's not the first time I face the restriction even working on the current problem!

Ivan Kazmenko.

In article <e2nj5p$2nj4$1@digitaldaemon.com>, Ivan Kazmenko says...
>
>Hi again!
>
>me:
>>> What is the 16M limit on the array length for?
>>> I wonder what's the 'reason' on that limit.
>
>Lionello Lunesu:
>>I've put the same limit in my own array template I use for C++ projects.
>>  My reasoning was that you shouldn't be using a dynamic array for such
>>huge memory blocks because of the potential costly resize. The limit helped me catch some bugs where array were being used and caused a significant performance bottleneck. I rewrote those parts with a simple malloc/free or VirtualAlloc. In D there might be the added complexities of the garbage collector. Remember that it keeps scanning the allocated memory for pointers. For these huge blocks it's better to use some other memory allocation scheme.
>
>I definitely won't want to resize such a huge array, at least not too often. My array is static. For resizing, I usually use the technique of doubling the requested index when it exceeds the current limit.
>
>If my too-many-M array is scanned for pointers, which I do not store there, do I have a way of forbidding it?
>
>Dave:
>>Why the need for such a large static array? Can't a dynamic array be used in your code instead?
>
>I could use dynamic array, yes, but I don't see any benefit since its size is fixed. Please explain why it could be better.

Actually static arrays are fixed size and dynamic arrays are not.

>
>The current problem which requires such a big array is related to prime numbers - it's a program for a programming contest at http://recmath.org/contest/ (you know, various contests are the best way to learn something new, if you have enough free time, of course). I use a sort of Eratosphenes sieve for prime numbers, and the larger the sieve, the faster the program runs (for large numbers, it uses Miller-Rabin primality test which is significantly slower than seeking a bit in an array, with paging, caching, and other modern RAM techniques included). I work with a teammate, we share ideas but write different implementations. He uses Delphi, and I decided to try D, but currently my implementation sucks 'cause I have no 'legal' way to use an array that big.
>
>Current problem aside, there are many ways to use my current amount of RAM, which is 768M, indexing it with only a couple of arrays. It's not the first time I face the restriction even working on the current problem!
>
>Ivan Kazmenko.

An array is the wrong way to go if you need that much memory. Anyways, the Eratosphenes sieve is iterative so you could use a linked list instead. Since the extra 768M (*2 if doubly linked) links would increase the memory requirement by a large amount you could consider using a custom, hybrid collection. Maybe by having a linked list of arrays each with a size of 50000.

Ivan Kazmenko wrote:
> Hi again!
> 
> me:
>>> What is the 16M limit on the array length for?
>>> I wonder what's the 'reason' on that limit.
> 
> Lionello Lunesu:
>> I've put the same limit in my own array template I use for C++ projects.  My reasoning was that you shouldn't be using a dynamic array for such huge memory blocks because of the potential costly resize. The limit helped me catch some bugs where array were being used and caused a significant performance bottleneck. I rewrote those parts with a simple malloc/free or VirtualAlloc. In D there might be the added complexities of the garbage collector. Remember that it keeps scanning the allocated memory for pointers. For these huge blocks it's better to use some other memory allocation scheme.
> 
> I definitely won't want to resize such a huge array, at least not too often. My
> array is static. For resizing, I usually use the technique of doubling the
> requested index when it exceeds the current limit.
> 
> If my too-many-M array is scanned for pointers, which I do not store there, do I
> have a way of forbidding it?
> 
> Dave:
>> Why the need for such a large static array? Can't a dynamic array be used in
>> your code instead?
> 
> I could use dynamic array, yes, but I don't see any benefit since its size is
> fixed. Please explain why it could be better.
> 
> The current problem which requires such a big array is related to prime numbers
> - it's a program for a programming contest at http://recmath.org/contest/ (you
> know, various contests are the best way to learn something new, if you have
> enough free time, of course). I use a sort of Eratosphenes sieve for prime
> numbers, and the larger the sieve, the faster the program runs (for large
> numbers, it uses Miller-Rabin primality test which is significantly slower than
> seeking a bit in an array, with paging, caching, and other modern RAM techniques
> included). I work with a teammate, we share ideas but write different
> implementations. He uses Delphi, and I decided to try D, but currently my
> implementation sucks 'cause I have no 'legal' way to use an array that big.
> 
> Current problem aside, there are many ways to use my current amount of RAM,
> which is 768M, indexing it with only a couple of arrays. It's not the first time
> I face the restriction even working on the current problem!
> 
> Ivan Kazmenko.

Instead of

T[25_000_000] myarray;

just do

T[] myarray = new T[25_000_000];

and that will take care of the immediate problem you describe and let you get on with solving the problem.

Example:

import std.stdio, std.string;

int main(char[][] args)
{
    bool[] flags = new bool[25_000_000];
    int  count;

    count = 0;
    flags[] = 1;
    for(int i = 2; i < flags.length; i++)
    {
        if(flags[i])
        {
            // remove all multiples of prime: i
            for(int j = i + i; j < flags.length; j += i) flags[j] = 0;
            count++;
        }
    }

    writefln("Count: ",count);

    return 0;
}

- Dave

Ben Phillips:
>>>Why the need for such a large static array? Can't a dynamic array be used in your code instead?
>>I could use dynamic array, yes, but I don't see any benefit since its size is fixed. Please explain why it could be better.
>Actually static arrays are fixed size and dynamic arrays are not.
I meant that the thing fixed is the size of my array, not the size of dynamic array. Sorry for the ambiguity.

>An array is the wrong way to go if you need that much memory. Anyways, the Eratosphenes sieve is iterative so you could use a linked list instead. Since the extra 768M (*2 if doubly linked) links would increase the memory requirement by a large amount you could consider using a custom, hybrid collection. Maybe by having a linked list of arrays each with a size of 50000.
Well, lists are in no way related to the problem. Firstly, they are just too slow. Secondly, for any number N, say, 1 <= N <= 100_000_000, I need to have a fast way to check whether it is prime. When you need something to be done real fast, using heavy data structures such as lists and collections doesn't make sense.

The sieve is not the result of the algorithm; rather, it's an auxiliary table built at initialisation time and used ever since.

Ivan Kazmenko.

Dave:
>Instead of
>
>T[25_000_000] myarray;
>
>just do
>
>T[] myarray = new T[25_000_000];
>
>and that will take care of the immediate problem you describe and let you get on with solving the problem.
Thanks for the verbose reply! I'll check the performance of the suggested solution as soon as I get back home.

What I'm concerned of is the performance of the data structure. The simpler, the faster, the better. I have a feeling that using a dynamic array adds an extra CPU cycle or two since the additional pointer to the data is variable, not constant; I'll check that soon. That's why I'm trying to get a working static array solution. Languages such as C and D offer a comfortable and readable way of writing performance critical parts of the program; it's a shame when it does not work afterwards.

Besides, having such an undocumented feature as a 16M limit on an array length is IMHO no good and deserves at least an explanation by someone familiar with the dmd code.

Ivan Kazmenko.

In article <e2o1po$hm8$1@digitaldaemon.com>, Ivan Kazmenko says...
>
>Dave:
>>Instead of
>>
>>T[25_000_000] myarray;
>>
>>just do
>>
>>T[] myarray = new T[25_000_000];
>>
>>and that will take care of the immediate problem you describe and let you get on with solving the problem.
>Thanks for the verbose reply! I'll check the performance of the suggested solution as soon as I get back home.
>
>What I'm concerned of is the performance of the data structure. The simpler, the faster, the better. I have a feeling that using a dynamic array adds an extra CPU cycle or two since the additional pointer to the data is variable, not constant; I'll check that soon. That's why I'm trying to get a working static array solution. Languages such as C and D offer a comfortable and readable way of writing performance critical parts of the program; it's a shame when it does not work afterwards.
>
>Besides, having such an undocumented feature as a 16M limit on an array length is IMHO no good and deserves at least an explanation by someone familiar with the dmd code.

Are you sure it's undocumented?

See http://www.digitalmars.com/d/arrays.html, "Static Arrays" section

"The total size of a static array cannot exceed 16Mb. A dynamic array should be used instead for such large arrays."

jcc7

jcc7 wrote:
> In article <e2o1po$hm8$1@digitaldaemon.com>, Ivan Kazmenko says...
>> Dave:
>>> Instead of
>>>
>>> T[25_000_000] myarray;
>>>
>>> just do
>>>
>>> T[] myarray = new T[25_000_000];
>>>
>>> and that will take care of the immediate problem you describe and let you get on with solving the problem.
>> Thanks for the verbose reply! I'll check the performance of the suggested solution as soon as I get back home.
>>
>> What I'm concerned of is the performance of the data structure. The simpler, the faster, the better. I have a feeling that using a dynamic array adds an extra CPU cycle or two since the additional pointer to the data is variable, not constant; I'll check that soon. That's why I'm trying to get a working static array solution. Languages such as C and D offer a comfortable and readable way of writing performance critical parts of the program; it's a shame when it does not work afterwards.
>>
>> Besides, having such an undocumented feature as a 16M limit on an array length is IMHO no good and deserves at least an explanation by someone familiar with the dmd code.
> 
> Are you sure it's undocumented?
> 
> See http://www.digitalmars.com/d/arrays.html, "Static Arrays" section
> 
> "The total size of a static array cannot exceed 16Mb. A dynamic array should be used instead for such large arrays."

Would it be possible to write the static array part in C and link it with the rest of the code being D?

-- 
Jari-Matti