[GHC] #4143: Data.Set can overflow Int on balance check

[GHC]

#4143: Data.Set can overflow Int on balance check
---------------------------------+------------------------------------------
Reporter:  japple                |          Owner:                   
    Type:  bug                   |         Status:  closed           
Priority:  normal                |      Component:  libraries (other)
 Version:  6.12.2                |     Resolution:  invalid          
Keywords:  containers, overflow  |             Os:  Unknown/Multiple 
Testcase:                        |   Architecture:  Unknown/Multiple 
 Failure:  Runtime crash         |  
---------------------------------+------------------------------------------
Changes (by guest):

  * status:  new => closed
  * resolution:  => invalid


Comment:

 With Jim on the #haskell channel, we worked out that this case can never
 actually occur.

 On a 32 bit machine, the size of a Bin node is at least 24 bytes, even
 discounting the size of the payload in the set which needs to be distinct.

 tag + forwarding pointer + size + value pointer + left pointer + right
 pointer

 The problem can only manifest itself when you are faced with more than ~
 500 million elements. But that requires more than the amount of address
 space available to store, even if you stored nothing else in memory, and
 didn't have to pay for the elements (which you might be able to avoid by
 using a free monad over Set)

 On a 64 bit machine, you don't even get that close, since no 64 bit
 machine extant actually has a 64 bit address bus (physical or virtual) and
 Haskell follows an ILP memory model with 64 bit ints on a 64 bit machine.

 -Edward Kmett

-- 
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/4143#comment:1>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler