Opened 11 years ago

Closed 10 years ago

Last modified 9 years ago

#1131 closed bug (fixed)

newArray_ allocates an array full of garbage

Reported by: igloo Owned by:
Priority: high Milestone: 6.8.1
Component: libraries/base Version: 6.6
Keywords: Cc: iampure@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case: arr018
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

In http://www.haskell.org/pipermail/haskell-cafe/2006-December/020115.html Stefan O'Rear points out that newArray_ allocates an array full of garbage. For ST this violates referential transparency, and it presumably also means we are leaking information we shouldn't.

For example, running

import Control.Monad.ST
import Data.Array.ST
import Data.Array
import System.Mem

tickle :: Int
tickle = runST (do {
     x <- newArray_ (0,100) ;
     (readArray :: STUArray s Int Int -> Int -> ST s Int) x 3
   })

main :: IO ()
main = do print $ length (replicate 100000 'a')
          performGC
          print tickle

produced

$ ./q
100000
46912506425344

Change History (9)

comment:1 Changed 10 years ago by igloo

Priority: normalhigh

comment:2 Changed 10 years ago by iampure@…

Cc: iampure@… added

I wrote a program that _depends_ on this functionality and my program behaviour as a whole is referentially transparent. I don't mind if you rename it to something "unsafe", but otherwise this functionality is a must-have.

comment:3 Changed 10 years ago by neil

iampure: Please clarify. Are you saying that you rely on the fact that newArray_ returns random garbage, or that it reuses other memory? Either way, it sounds like you are making very delicate assumptions.

comment:4 Changed 10 years ago by iampure@…

I depend on the fact that it uses random garbage. It's the only way to write algorithms that use more space than time in the ST monad.

comment:5 Changed 10 years ago by guest

While I don't think it is good practice to rely on newArray_ returning random values, the documentation clearly states:

newArray
Ix i => (i, i) -> e -> m (a i e) Builds a new array, with every element initialised to the supplied value.
newArray_
Ix i => (i, i) -> m (a i e) Builds a new array, with every element initialised to undefined.

Possibly, newArray_ shouldn't be defined at all for unboxed arrays, but since it is, I think the current implementation is the only reasonable. (Presumably, newArray_'s raison d'être is that it is faster than newArray?)

I don't think this is a bug at all, and I don't understand at all why it is given a 'high' priority. Stefan should use newArray, and iampure should expect his programs to break without warning in the future :-)

-k

comment:6 Changed 10 years ago by simonmar

Resolution: fixed
Status: newclosed
Test Case: arr018

Fixed:

Wed Jul  4 11:20:20 BST 2007  Simon Marlow <simonmar@microsoft.com>
  * FIX #1131 (newArray_ allocates an array full of garbage)
  Now newArray_ returns a deterministic result in the ST monad, and
  behaves as before in other contexts.  The current newArray_ is renamed
  to unsafeNewArray_; the MArray class therefore has one more method
  than before.

comment:7 Changed 10 years ago by igloo

Milestone: 6.8 branch6.8.1

comment:8 Changed 9 years ago by simonmar

Architecture: UnknownUnknown/Multiple

comment:9 Changed 9 years ago by simonmar

Operating System: UnknownUnknown/Multiple
Note: See TracTickets for help on using tickets.