On Sun, Oct 3, 2010 at 11:18 AM, Bulat Ziganshin wrote:

Hello Henry,

Sunday, October 3, 2010, 7:54:49 PM, you wrote:

...

It looks like array ranges can only be Ints, and not Int64 or Word64 types.

yes, it's Int internally got efficiency reasons. you can do your own implementation to override this limit :)

A good place to start when rolling your own is the primitive package[1] on Hackage. It is intimately tied to GHC, however. Antoine [1] http://hackage.haskell.org/package/primitive

On Sun, Oct 3, 2010 at 19:09, Bryan O'Sullivan wrote:

On Sun, Oct 3, 2010 at 11:54 AM, Henry Laxen 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'

Just out of curiosity, may I know a use case of such huge arrays? At such sizes, I thought, the array would not have the expected array properties (constant access time) due to "thrashing". thanks, Hemanth

Thanks Ketil. On Wed, Oct 6, 2010 at 1:36 AM, Ketil Malde wrote:

...

Just out of curiosity, may I know a use case of such huge arrays?

Bloom filters?

Am probably dense - I still did not get an idea of where would one use such a big array.

Let us say, we are using a bit-array of size 2^43 (that is, a byte array of size 2^40) to store a bloom filter. And let us further assume that we are interested in a false-positive probability of 0.01 That means, I will be able to use this array to represent a set of cardinality 9.18e11 ~ 10^12 I was curious to know what sort of programs would be dealing with sets of 10^12 elements. Am mainly curious about how one would decide that bloom filters are the best algorithm when dealing with this amount of data.What factors do we consider when deciding the algorithm or the data structure? The impact on GC would be taken into account, for example (am guessing there would be at least one copy from a younger generation to a permanent generation)? /Hemanth K

Thanks for the response. That sounds sequence comparison seems very impressive On Wed, Oct 6, 2010 at 2:23 PM, Ketil Malde wrote:

Hemanth Kapila writes:

...

Let us say, we are using a bit-array of size 2^43 (that is, a byte array of size 2^40) to store a bloom filter. And let us further assume that we are interested in a false-positive probability of 0.01

Since we are just making up numbers, let us instead say we are using a bit array of size 2^32 - still too large for Int indexing (which was the issue here) but "only" 500MB in size.

...

That means, I will be able to use this array to represent a set of cardinality 9.18e11 ~ 10^12

...bringing it down to less than 10^9, easily reached for building an indexing of k-words (tuples) in e.g. the human genome (3GB).

But: I'm about to start analyzing Illumina sequencing data, where we have sequences from two individuals of the same species. I'm interesting in the differences between these species, so I might want to index both data sets and screen the sequences of each against the other to identify bits that don't appear in the other. Since I'll have easily tens, maybe a hundred gigabytes of sequence from each, it's not impossible to get into the territory you describe.

(In practice, things will be limited by available RAM, sadly still some orders of magnitude less than 2^40 - although apparently SGI can deliver it. I guess I just need a bigger budget.)

...

I was curious to know what sort of programs would be dealing with sets of 10^12 elements.

Most likely a program using mutation, and probably not copying, multi-generation GC.

Other data sets that have considerable size are acoustics data (I understand a modern sonar deliver about a Gbit/sec continously), and seismic data.

Also, for more moderate bodies of data and more complex analysis, you might want to use less frugal data structure, like suffix arrays.

-k -- If I haven't seen further, it is by standing in the footprints of giants _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe