[Haskell-cafe] OS swapping and haskell data structures

Stefan O'Rear stefanor at cox.net
Wed Aug 1 01:59:01 EDT 2007

On Tue, Jul 31, 2007 at 10:45:56PM -0700, Alex Jacobson wrote:
> If you create a Data.Map or Data.Set larger than fits in physical memory, 
> will OS level swapping enable your app to behave reasonably or will things 
> just die catastrophically as you hit a memory limit?

Data.{Set,Map} uses balanced binary trees.  So if you have a 1 billion
element data set which is so large that no significant fraction of it
fits into cache, you can expect to access a random element in ~9 seeks,
which is less than a second...  good enough?

This is a lot worse than it could be because memory access is too
transparent.  When GHC triggers a page fault, the Right Thing to do is
for Linux to somehow put *that haskell thread* to sleep; but instead it
will put the entire capability (or your whole program on the
non-threading rts) to sleep.

Linux's filesystems (which use various kinds of trees internally) avoid
this issue by using asynchronous IO requests, but that's not an option
for VM since there's only so much room for callbacks in a MOV

There is much fertile territory for OS design space exploration here!

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20070731/7ad34934/attachment.bin

More information about the Haskell-Cafe mailing list