[GHC] #16406: Array code works with GHC 8.4.4, hangs with GHC 8.6.4
#16406: Array code works with GHC 8.4.4, hangs with GHC 8.6.4 -------------------------------------+------------------------------------- Reporter: arybczak | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: libraries | Version: 8.6.4 (other) | Keywords: array | Operating System: Unknown/Multiple Architecture: | Type of failure: None/Unknown Unknown/Multiple | Test Case: | Blocked By: Blocking: | Related Tickets: Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- Consider the following: ```haskell import Data.Array.IArray import Data.Bits import Data.Word loop :: Array Int Word32 loop = accumArray (curry snd) 0 (0,79) $ [(i, xxor i) | i <- [16..79]] where xxor :: Int -> Word32 xxor i = loop ! (i-16) `xor` loop ! (i-3) `xor` loop ! (i-8) `xor` loop ! (i-14) ``` When loaded into ghci-8.4.4, `loop` works fine: ``` GHCi, version 8.4.4: http://www.haskell.org/ghc/ :? for help Loaded GHCi configuration from /home/unknown/.ghci λ> :l array.hs [1 of 1] Compiling Main ( array.hs, interpreted ) Ok, one module loaded. λ> loop array (0,79) [(0,0),(1,0),(2,0),(3,0),(4,0),(5,0),(6,0),(7,0),(8,0),(9,0),(10,0),(11,0),(12,0),(13,0),(14,0),(15,0),(16,0),(17,0),(18,0),(19,0),(20,0),(21,0),(22,0),(23,0),(24,0),(25,0),(26,0),(27,0),(28,0),(29,0),(30,0),(31,0),(32,0),(33,0),(34,0),(35,0),(36,0),(37,0),(38,0),(39,0),(40,0),(41,0),(42,0),(43,0),(44,0),(45,0),(46,0),(47,0),(48,0),(49,0),(50,0),(51,0),(52,0),(53,0),(54,0),(55,0),(56,0),(57,0),(58,0),(59,0),(60,0),(61,0),(62,0),(63,0),(64,0),(65,0),(66,0),(67,0),(68,0),(69,0),(70,0),(71,0),(72,0),(73,0),(74,0),(75,0),(76,0),(77,0),(78,0),(79,0)] ``` However, when loaded into ghci-8.6.4, it hangs (with no CPU utilization): ``` GHCi, version 8.6.4: http://www.haskell.org/ghc/ :? for help Loaded GHCi configuration from /home/unknown/.ghci λ> :l array.hs [1 of 1] Compiling Main ( array.hs, interpreted ) Ok, one module loaded. λ> loop array ``` The definition of loop is a piece of code taken from Crypto library (https://hackage.haskell.org/package/Crypto-4.2.5.1/docs/src/Data-Digest- SHA1.html, `oneBlock` function) Granted, this library is pretty much dead (last update in 2012), but it's a bit suspect that code suddenly stops working in the worst way possible. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/16406 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#16406: Array code works with GHC 8.4.4, hangs with GHC 8.6.4 -------------------------------------+------------------------------------- Reporter: arybczak | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: libraries | Version: 8.6.4 (other) | Resolution: | Keywords: array Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Description changed by arybczak: Old description:
Consider the following:
```haskell import Data.Array.IArray import Data.Bits import Data.Word
loop :: Array Int Word32 loop = accumArray (curry snd) 0 (0,79) $ [(i, xxor i) | i <- [16..79]] where xxor :: Int -> Word32 xxor i = loop ! (i-16) `xor` loop ! (i-3) `xor` loop ! (i-8) `xor` loop ! (i-14) ```
When loaded into ghci-8.4.4, `loop` works fine:
``` GHCi, version 8.4.4: http://www.haskell.org/ghc/ :? for help Loaded GHCi configuration from /home/unknown/.ghci λ> :l array.hs [1 of 1] Compiling Main ( array.hs, interpreted ) Ok, one module loaded. λ> loop array (0,79) [(0,0),(1,0),(2,0),(3,0),(4,0),(5,0),(6,0),(7,0),(8,0),(9,0),(10,0),(11,0),(12,0),(13,0),(14,0),(15,0),(16,0),(17,0),(18,0),(19,0),(20,0),(21,0),(22,0),(23,0),(24,0),(25,0),(26,0),(27,0),(28,0),(29,0),(30,0),(31,0),(32,0),(33,0),(34,0),(35,0),(36,0),(37,0),(38,0),(39,0),(40,0),(41,0),(42,0),(43,0),(44,0),(45,0),(46,0),(47,0),(48,0),(49,0),(50,0),(51,0),(52,0),(53,0),(54,0),(55,0),(56,0),(57,0),(58,0),(59,0),(60,0),(61,0),(62,0),(63,0),(64,0),(65,0),(66,0),(67,0),(68,0),(69,0),(70,0),(71,0),(72,0),(73,0),(74,0),(75,0),(76,0),(77,0),(78,0),(79,0)] ```
However, when loaded into ghci-8.6.4, it hangs (with no CPU utilization): ``` GHCi, version 8.6.4: http://www.haskell.org/ghc/ :? for help Loaded GHCi configuration from /home/unknown/.ghci λ> :l array.hs [1 of 1] Compiling Main ( array.hs, interpreted ) Ok, one module loaded. λ> loop array ```
The definition of loop is a piece of code taken from Crypto library (https://hackage.haskell.org/package/Crypto-4.2.5.1/docs/src/Data-Digest- SHA1.html, `oneBlock` function)
Granted, this library is pretty much dead (last update in 2012), but it's a bit suspect that code suddenly stops working in the worst way possible.
New description: Consider the following: {{{#!haskell import Data.Array.IArray import Data.Bits import Data.Word loop :: Array Int Word32 loop = accumArray (curry snd) 0 (0,79) $ [(i, xxor i) | i <- [16..79]] where xxor :: Int -> Word32 xxor i = loop ! (i-16) `xor` loop ! (i-3) `xor` loop ! (i-8) `xor` loop ! (i-14) }}} When loaded into ghci-8.4.4, `loop` works fine: {{{ GHCi, version 8.4.4: http://www.haskell.org/ghc/ :? for help Loaded GHCi configuration from /home/unknown/.ghci λ> :l array.hs [1 of 1] Compiling Main ( array.hs, interpreted ) Ok, one module loaded. λ> loop array (0,79) [(0,0),(1,0),(2,0),(3,0),(4,0),(5,0),(6,0),(7,0),(8,0),(9,0),(10,0),(11,0),(12,0),(13,0),(14,0),(15,0),(16,0),(17,0),(18,0),(19,0),(20,0),(21,0),(22,0),(23,0),(24,0),(25,0),(26,0),(27,0),(28,0),(29,0),(30,0),(31,0),(32,0),(33,0),(34,0),(35,0),(36,0),(37,0),(38,0),(39,0),(40,0),(41,0),(42,0),(43,0),(44,0),(45,0),(46,0),(47,0),(48,0),(49,0),(50,0),(51,0),(52,0),(53,0),(54,0),(55,0),(56,0),(57,0),(58,0),(59,0),(60,0),(61,0),(62,0),(63,0),(64,0),(65,0),(66,0),(67,0),(68,0),(69,0),(70,0),(71,0),(72,0),(73,0),(74,0),(75,0),(76,0),(77,0),(78,0),(79,0)] }}} However, when loaded into ghci-8.6.4, it hangs (with no CPU utilization): {{{ GHCi, version 8.6.4: http://www.haskell.org/ghc/ :? for help Loaded GHCi configuration from /home/unknown/.ghci λ> :l array.hs [1 of 1] Compiling Main ( array.hs, interpreted ) Ok, one module loaded. λ> loop array }}} The definition of loop is a piece of code taken from Crypto library (https://hackage.haskell.org/package/Crypto-4.2.5.1/docs/src/Data-Digest- SHA1.html, `oneBlock` function) Granted, this library is pretty much dead (last update in 2012), but it's a bit suspect that code suddenly stops working in the worst way possible. -- -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/16406#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#16406: Array code works with GHC 8.4.4, hangs with GHC 8.6.4 -------------------------------------+------------------------------------- Reporter: arybczak | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: libraries | Version: 8.6.4 (other) | Resolution: | Keywords: array Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Description changed by arybczak: Old description:
Consider the following:
{{{#!haskell import Data.Array.IArray import Data.Bits import Data.Word
loop :: Array Int Word32 loop = accumArray (curry snd) 0 (0,79) $ [(i, xxor i) | i <- [16..79]] where xxor :: Int -> Word32 xxor i = loop ! (i-16) `xor` loop ! (i-3) `xor` loop ! (i-8) `xor` loop ! (i-14) }}}
When loaded into ghci-8.4.4, `loop` works fine:
{{{ GHCi, version 8.4.4: http://www.haskell.org/ghc/ :? for help Loaded GHCi configuration from /home/unknown/.ghci λ> :l array.hs [1 of 1] Compiling Main ( array.hs, interpreted ) Ok, one module loaded. λ> loop array (0,79) [(0,0),(1,0),(2,0),(3,0),(4,0),(5,0),(6,0),(7,0),(8,0),(9,0),(10,0),(11,0),(12,0),(13,0),(14,0),(15,0),(16,0),(17,0),(18,0),(19,0),(20,0),(21,0),(22,0),(23,0),(24,0),(25,0),(26,0),(27,0),(28,0),(29,0),(30,0),(31,0),(32,0),(33,0),(34,0),(35,0),(36,0),(37,0),(38,0),(39,0),(40,0),(41,0),(42,0),(43,0),(44,0),(45,0),(46,0),(47,0),(48,0),(49,0),(50,0),(51,0),(52,0),(53,0),(54,0),(55,0),(56,0),(57,0),(58,0),(59,0),(60,0),(61,0),(62,0),(63,0),(64,0),(65,0),(66,0),(67,0),(68,0),(69,0),(70,0),(71,0),(72,0),(73,0),(74,0),(75,0),(76,0),(77,0),(78,0),(79,0)] }}}
However, when loaded into ghci-8.6.4, it hangs (with no CPU utilization): {{{ GHCi, version 8.6.4: http://www.haskell.org/ghc/ :? for help Loaded GHCi configuration from /home/unknown/.ghci λ> :l array.hs [1 of 1] Compiling Main ( array.hs, interpreted ) Ok, one module loaded. λ> loop array }}}
The definition of loop is a piece of code taken from Crypto library (https://hackage.haskell.org/package/Crypto-4.2.5.1/docs/src/Data-Digest- SHA1.html, `oneBlock` function)
Granted, this library is pretty much dead (last update in 2012), but it's a bit suspect that code suddenly stops working in the worst way possible.
New description: Consider the following: {{{#!haskell import Data.Array.IArray import Data.Bits import Data.Word loop :: Array Int Word32 loop = accumArray (curry snd) 0 (0,79) $ [(i, xxor i) | i <- [16..79]] where xxor :: Int -> Word32 xxor i = loop ! (i-16) `xor` loop ! (i-3) `xor` loop ! (i-8) `xor` loop ! (i-14) }}} When loaded into ghci-8.4.4, `loop` works fine: {{{ GHCi, version 8.4.4: http://www.haskell.org/ghc/ :? for help Loaded GHCi configuration from /home/unknown/.ghci λ> :l array.hs [1 of 1] Compiling Main ( array.hs, interpreted ) Ok, one module loaded. λ> loop array (0,79) [(0,0),(1,0),(2,0),(3,0),(4,0),(5,0),(6,0),(7,0),(8,0),(9,0),(10,0),(11,0),(12,0),(13,0),(14,0),(15,0),(16,0),(17,0),(18,0),(19,0),(20,0),(21,0),(22,0),(23,0),(24,0),(25,0),(26,0),(27,0),(28,0),(29,0),(30,0),(31,0),(32,0),(33,0),(34,0),(35,0),(36,0),(37,0),(38,0),(39,0),(40,0),(41,0),(42,0),(43,0),(44,0),(45,0),(46,0),(47,0),(48,0),(49,0),(50,0),(51,0),(52,0),(53,0),(54,0),(55,0),(56,0),(57,0),(58,0),(59,0),(60,0),(61,0),(62,0),(63,0),(64,0),(65,0),(66,0),(67,0),(68,0),(69,0),(70,0),(71,0),(72,0),(73,0),(74,0),(75,0),(76,0),(77,0),(78,0),(79,0)] }}} However, when loaded into ghci-8.6.4, it hangs (with no CPU utilization): {{{ GHCi, version 8.6.4: http://www.haskell.org/ghc/ :? for help Loaded GHCi configuration from /home/unknown/.ghci λ> :l array.hs [1 of 1] Compiling Main ( array.hs, interpreted ) Ok, one module loaded. λ> loop array }}} The definition of loop is a piece of code taken from Crypto library (https://hackage.haskell.org/package/Crypto-4.2.5.1/docs/src/Data-Digest- SHA1.html, `oneBlock` function) Granted, this library is pretty much dead (last update in 2012), but it's a bit suspect that code suddenly stops working in the (almost) worst way possible. -- -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/16406#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#16406: Array code works with GHC 8.4.4, hangs with GHC 8.6.4 -------------------------------------+------------------------------------- Reporter: arybczak | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: libraries | Version: 8.6.4 (other) | Resolution: | Keywords: array Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by fredrikcarlen): Behaviour confirmed on macOS v10.14.3. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/16406#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#16406: Array code works with GHC 8.4.4, hangs with GHC 8.6.4 -------------------------------------+------------------------------------- Reporter: arybczak | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: libraries | Version: 8.6.4 (other) | Resolution: | Keywords: array Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by osa1): Confirmed on GHC HEAD on Linux. It fails with `<<loop>>` exception when compiled. Some commits that may be relevant: - "Harden fixST" 5a49651f3161473b383ec497af38e9daa022b9ac - "Index arrays more eagerly" e7678d6a0607013749e9ba4d88df949ad1192765 I think this is the commit that broke this example: - "Make accumArray and accum stricter" 08345bd0e8d237ec3929aaee7613c4f76e07e131 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/16406#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#16406: Array code works with GHC 8.4.4, hangs with GHC 8.6.4 -------------------------------------+------------------------------------- Reporter: arybczak | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: libraries | Version: 8.6.4 (other) | Resolution: | Keywords: array Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by osa1): * cc: dfeuer (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/16406#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#16406: Array code works with GHC 8.4.4, hangs with GHC 8.6.4 -------------------------------------+------------------------------------- Reporter: arybczak | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: libraries | Version: 8.6.4 (other) | Resolution: | Keywords: array Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): That's bad. We should not be changing Haskell's semantics, unless the library was somehow exploiting an undocumented (or perhaps even wrong) corner of the semantics. Worth investigating! -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/16406#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#16406: Array code works with GHC 8.4.4, hangs with GHC 8.6.4 -------------------------------------+------------------------------------- Reporter: arybczak | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: libraries | Version: 8.6.4 (other) | Resolution: | Keywords: array Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by dfeuer): That was an intentional change. As I recall: Haskell 98's reference implementation didn't match its spec. We followed the Result: `accumArray` was terribly inefficient. Is there real code in the wild that makes use of its former laziness? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/16406#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#16406: Array code works with GHC 8.4.4, hangs with GHC 8.6.4 -------------------------------------+------------------------------------- Reporter: arybczak | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: libraries | Version: 8.6.4 (other) | Resolution: | Keywords: array Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by bgamari): dfeuer, the code at the top of this ticket ties a knot and is from the Crypto library. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/16406#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#16406: Array code works with GHC 8.4.4, hangs with GHC 8.6.4 -------------------------------------+------------------------------------- Reporter: arybczak | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: libraries | Version: 8.6.4 (other) | Resolution: | Keywords: array Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by dfeuer): Ah, missed that. I tend think it's better to fix the crypto library. Make it use conversion from a list. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/16406#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#16406: Array code works with GHC 8.4.4, hangs with GHC 8.6.4 -------------------------------------+------------------------------------- Reporter: arybczak | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: libraries | Version: 8.6.4 (other) | Resolution: | Keywords: array Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by bgamari): The report has this to say about accumArray:
If the accumulating function is strict, then accumArray is strict in the values, as well as the indices, in the association list. Thus, unlike ordinary arrays built with array, accumulated arrays should not in general be recursive.
It does sound like we are within our rights to be strict here. However, perhaps we should document this strictness a bit better -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/16406#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC