[Haskell-cafe] Big Arrays

Ketil Malde ketil at malde.org
Tue Oct 5 16:06:59 EDT 2010


Hemanth Kapila <saihemanth at gmail.com> writes:

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

Bloom filters?

> At such sizes, I thought, the array would not have the expected array
> properties (constant access time) due to "thrashing".

Yes, but this is true for any array size, due to the cache hierarchy.
Accessing stuff in the same vector register is faster than accessing
things in L1 cache is faster than L2, then L3, then RAM, then swap (on
SSD), then (rotating) disk. :-)  Perhaps it's not /entirely/
unreasonable to consider array accesses to be log(N) cost - but I'm
fairly sure they're always faster than pointer chasing in tree
structures.

-k
-- 
If I haven't seen further, it is by standing in the footprints of giants


More information about the Haskell-Cafe mailing list