[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