[Haskell-cafe] Big Arrays

[John Millikin]

On Sun, Oct 3, 2010 at 19:09, Bryan O'Sullivan <bos at serpentine.com> wrote:
> On Sun, Oct 3, 2010 at 11:54 AM, Henry Laxen <nadine.and.henry at pobox.com>
> wrote:
>>
>> I am trying to create a (relatively) big array,
>> but it seems I cannot make anything larger
>> than 2^30 or so.  Here is the code:
>
> Use a 64-bit machine, where Int is 64 bits wide. Trying to create a larger
> array on a 32-bit machine doesn't make any sense.

Sure it does; a 32-bit system can address much more than 2**30
elements. Artificially limiting how much memory can be allocated by
depending on a poorly-specced type like 'Int' is a poor design
decision in Haskell and GHC.

OP: for this particular use case (unboxed Word64), an easily solution
is to have some structure like (data BigArray a = BigArray (UArray
Word32 a) ((UArray Word32 a) ((UArray Word32 a) ((UArray Word32 a)),
with each array containing 2^30 elements. You'll need to write custom
indexing and modification functions, to process the index and pass it
to the appropriate array. Something like:

idxBig :: BigArray a -> Word32 -> (UArray Word32 a, Word32)
idxBig (BigArray a0 a1 a2 a3) i
    | i < 2^30 = (a0, i)
    | i < 2^31 = (a1, i - 2^30)
    | i < 2^30 + 2^31 = (a2, i - 2^31)
    | i < 2^32 = (a3, i - 2^31 - 2^30)

Then wrap the existing array functions:

idx :: BigArray a -> Word32 -> a
idx arr i = let (arr', i') = idxBig arr i in arr' ! i'