GHC issueshttps://gitlab.haskell.org/ghc/ghc/-/issues2024-03-25T03:08:10Zhttps://gitlab.haskell.org/ghc/ghc/-/issues/22255Awkward design around pinned ByteArray# and compaction2024-03-25T03:08:10ZMatthew Cravenclyring@gmail.comAwkward design around pinned ByteArray# and compactionAccording to the documentation for `GHC.Compact`:
> Pinned `ByteArray#` objects cannot be compacted. This is for a good reason: the memory is pinned so that it can be referenced by address (the address might be stored in a C data struct...According to the documentation for `GHC.Compact`:
> Pinned `ByteArray#` objects cannot be compacted. This is for a good reason: the memory is pinned so that it can be referenced by address (the address might be stored in a C data structure, for example), so we can't make a copy of it to store in the `Compact`.
We also provide a primop `isByteArrayPinned#` to allow users to opportunistically exploit existing pinned-ness of `ByteArray#`s to avoid copying when using the FFI or `Storable`.
However, these features disagree about when a `ByteArray#` is pinned:
- Compaction considers a `ByteArray#` to be pinned only if it was explicitly pinned at creation-time with `newPinnedByteArray#` or `newAlignedPinnedByteArray#`.
- In addition to explicitly pinned `ByteArray#`s, `isByteArrayPinned#` considers `ByteArray#`s in large-object heap blocks or in compact regions to be pinned.
This mismatch can easily lead to memory-unsafety. Here's a small example program:
<details>
```haskell
import qualified Data.ByteString.Short as SBS
import qualified Data.ByteString.Char8 as BS
import GHC.Compact (compact, getCompact)
import Control.Monad (forM_)
import System.Mem (performMajorGC)
main :: IO ()
main = do
x <- compact (SBS.fromShort (SBS.replicate 8000 48))
let printCompact v = BS.putStrLn (BS.take 20 (getCompact v))
printCompact x
performMajorGC
forM_ [8000..9000] $ \i -> compact (SBS.fromShort (SBS.replicate i 49))
printCompact x
```
</details>
This program _seems_ innocent. But under the hood, `SBS.replicate 8000 48` creates a large pinned-but-not-_explicitly_-pinned `ByteArray#`, and `SBS.fromShort` (since `bytestring-0.11.1.0`) sees that it is pinned and opportunistically creates a non-GC reference into it instead of making a copy. Then the underlying buffer is copied into the compact region `x` without issue since it was not explicitly pinned, but the non-GC reference in the `ByteString` cannot be updated and becomes a dangling pointer. (The subsequent code tries to demonstrate this by making two calls to `printCompact x` produce different output, though of course this isn't truly guaranteed to work.)
Of course, `GHC.Compact` is not a "Safe Haskell" module and `ByteString`s are typically not compactible. But it's still a little unsatisfactory that this performs unsafe memory accesses instead of raising a `CompactionFailed` exception. Here are a few options:
2. Prevent compaction of these _implicitly_ pinned `ByteArray#`s.
1. Do nothing, and just document this infelicity.
3. Weaken `isByteArrayPinned#` to only consider _explicitly_ pinned `ByteArray#`s.
4. Provide a primop that makes an implictly pinned `ByteArray#` explicitly pinned, without copying its contents.
5. Distinguish between `ByteArray#` references (which may happen to refer to pinned objects) and `PinnedByteArray#` references, and only refuse to compact the latter. (This means the distinction must exist at runtime. Perhaps both can be references to `ARR_WORDS` heap objects, but with different pointer tags?)https://gitlab.haskell.org/ghc/ghc/-/issues/21373test-cabal-reinstall nightly job failing2022-05-25T11:01:09ZMatthew Pickeringtest-cabal-reinstall nightly job failingJob: https://gitlab.haskell.org/ghc/ghc/-/jobs/1007220
```
$ cabal update --index=$HACKAGE_INDEX_STATE --project-file=cabal.project-reinstall
index-state must be a unix-timestamps (e.g. '@1474732068'), a ISO8601 UTC timestamp (e.g. '20...Job: https://gitlab.haskell.org/ghc/ghc/-/jobs/1007220
```
$ cabal update --index=$HACKAGE_INDEX_STATE --project-file=cabal.project-reinstall
index-state must be a unix-timestamps (e.g. '@1474732068'), a ISO8601 UTC timestamp (e.g. '2016-09-24T17:47:48Z'), or 'HEAD'
CallStack (from HasCallStack):
error, called at src/Distribution/ReadE.hs:42:24 in Cabal-3.6.2.0-inplace:Distribution.ReadE
Running after_script
```Matthew PickeringMatthew Pickeringhttps://gitlab.haskell.org/ghc/ghc/-/issues/19897Long GC pauses while collecting compact regions2022-05-02T14:17:09ZMarcin RzeźnickiLong GC pauses while collecting compact regions## Summary
In one of our projects, we noticed very long GC pauses. We have been able to pin that down to cases where long-lived caches have become garbage. We keep these caches in the form of compact regions, and they can grow quite lar...## Summary
In one of our projects, we noticed very long GC pauses. We have been able to pin that down to cases where long-lived caches have become garbage. We keep these caches in the form of compact regions, and they can grow quite large (the largest are just around 128GB). While we realized that the release of compact regions is linear in the region's block list length, the timings we saw looked rather quadratic e.g.
| Cache size [b] | GC pause [s] |
|-----------------|--------------|
| 2_533_449_728 | 0.123 |
| 2_962_022_400 | 0.169 |
| 3_768_795_136 | 0.214 |
| 5_052_579_840 | 0.286 |
| 9_247_870_976 | 1.016 |
| 14_269_587_456 | 3.470 |
At this rate, we expect a pause of approx. 400s for 128 GB, and that's what happens. The problem seems to be that `free_mblock_list` can grow in proportion to the region's block list (please see the perf samples). This behavior can be reliably reproduced, so it's probably not just us. To do so I used the following program:
```haskell
#!/usr/bin/env stack
{- stack
--resolver lts-17.11
script
--optimize
--package base
--package ghc-compact
--package primitive
--ghc-options -threaded
--ghc-options "-with-rtsopts=-N -I0 -qg -S"
-}
{-# LANGUAGE NumericUnderscores #-}
import Control.Monad (replicateM)
import Data.IORef
import Data.Primitive.ByteArray
import GHC.Compact
import System.Environment (getArgs)
import System.Mem (performGC)
main :: IO ()
main = do
a <- getArgs
let x = read $ head a
compactStuffRef <- newIORef =<< allocCompactStuff x
stuffSize <- compactSize =<< readIORef compactStuffRef
putStrLn $ "Compact size [b]: " ++ show stuffSize
putStrLn "*************************"
putStrLn "Press any key to start GC"
putStrLn "************************* "
_ <- getChar
writeIORef compactStuffRef undefined
performGC
putStrLn "*************************"
putStrLn "After GC"
putStrLn "************************* "
return ()
allocCompactStuff n = do
region <- compact' =<< chunk
go 0 region
where
chunk = replicateM 512 $ allocBytes 3276 -- alloc just below LARGE_OBJECT_THRESHOLD
go m region
| m == n = pure region
| otherwise = go (m + 1) =<< addChunk region
-- adds a lot of fragmentation to the free_mblock_list
addChunk region = compactAdd region . getCompact . head =<< replicateM 64 (compact' =<< chunk)
allocBytes :: Int -> IO ByteArray
allocBytes x = unsafeFreezeByteArray =<< newByteArray x
compact' :: a -> IO (Compact a)
compact' = compactSized 1_032_192 False
```
The goal I had in mind here is to "grow" the `free_mblock_list` proportionally to the length of some compact region (governed by the argument passed to the program) - it seems that this can be reliably achieved by allocating many smaller compacts and keeping only some of them. This more or less agrees with what we have seen in the actual program. If you measure GC times after releasing the "big" compact, it looks like this:
| x | Compact size [b]| GC pause [s] |
|------|-----------------|--------------|
|1_000 | 2_099_015_680 | 0.222 |
|2_000 | 4_196_167_680 | 0.465 |
|4_000 | 8_390_471_680 | 1.067 |
|8_000 | 16_779_079_680 | 3.065 |
|10_000| 20_973_383_680 | 4.078 |
|16_000| 33_550_295_680 | 9.059 |
If you attach `perf` after "Press any key ...", the following picture emerges:
![perf-bench.svg](/uploads/64b1e00bda953608e97da9d87d702644/perf-bench.svg)
which seems to favor the explanation of quadratic behavior emerging from loops in `free_mega_group`.
## Steps to reproduce
Please run the attached program
## Expected behavior
Keep GC pause linear in the size of compact region (perhaps a data structure better than linked-list would do)
## Environment
* GHC version used: 8.10.4, also reproduced on 8.8.4
Optional:
* Operating System: Linux
* System Architecture: x86_649.4.1Ben GamariBen Gamarihttps://gitlab.haskell.org/ghc/ghc/-/issues/18757Compact Region allocator creates unexpectedly small blocks2021-09-29T14:15:37ZFabian ThorandCompact Region allocator creates unexpectedly small blocks## Summary
When adding a large object of size `X` to a compact region which has an even larger default block size `Y`
(as specified in the initial `compactSized` call), then the compact region allocator allocates a compact
region block ...## Summary
When adding a large object of size `X` to a compact region which has an even larger default block size `Y`
(as specified in the initial `compactSized` call), then the compact region allocator allocates a compact
region block just large enough for accomodating for `X`, even though it could also just allocate a block
of the larger size `Y`, under the assumption that there most likely will be more object to be added to the
compact region.
There are some issues with having a lot of small compact region blocks:
- If the small blocks are spread out across more megablocks than stricly needed in terms of size,
fragmentation can prevent the RTS from returning memory to the OS (similar to the situation in https://www.well-typed.com/blog/2020/08/memory-fragmentation/, as compact region blocks are pinned)
- A lot of small blocks in the linked list of blocks can slow down allocation, when the nursery is not the last block (see https://gitlab.haskell.org/ghc/ghc/-/issues/17640)
- Smaller blocks mean that the nursery will be exhausted more often, resulting in more calls to `allocateForCompact` from the compaction itself.
## Steps to reproduce
The following Haskell program creates a new compact region with a default block size of one megablock
and then fills it with a few hundred large objects.
```haskell
{-# LANGUAGE MagicHash #-}
{-# LANGUAGE UnboxedTuples #-}
import Control.Monad
import GHC.Compact
import GHC.Compact.Serialized
import GHC.IO
import GHC.Prim
main :: IO ()
main = do
let
blocksPerMBlock, blockSize, dataBytesInMegablock :: Integral a => a
blocksPerMBlock = 252
blockSize = 4096
dataBytesInMegablock = blocksPerMBlock * blockSize
-- Create a new compact region with the maximum possible block size
-- (1 megablock per compact region block)
region <- compactSized dataBytesInMegablock False ()
largeObject <- newLargeObject
-- Add the large object a few times to our compact region:
replicateM 510 $ void $ compactAdd region largeObject
-- Now check how many blocks were allocated, and how much data they each contain
blockSizes <- withSerializedCompact region $ \serialized ->
pure $ map snd $ serializedCompactBlockList serialized
-- We'll find that the first block is full with the first half of the large objects,
-- but then there's one new block for each of the remaining large objects.
putStrLn $ "Number of blocks: " <> show (length blockSizes)
print blockSizes
-- UTIL:
data LargeObject = LargeObject ByteArray#
-- | Create an object larger than the large object threshold
newLargeObject :: IO LargeObject
newLargeObject = IO $ \s ->
case newByteArray# 4000# s of
(# s', arr #) -> case unsafeFreezeByteArray# arr s of
(# s'', frozenArr #) -> (# s'', LargeObject frozenArr #)
```
Running it prints
```
Number of blocks: 256
[1032192,4088,4088,4088,4040,4040, ... 250 more ...]
```
indicating that the compact region consists of 256 blocks, and all but the first are a lot smaller than the desired default block size.
## Expected behavior
Ideally, the reproducer would just allocate two compact region blocks, each one megablock large.
That way, there would be less memory fragmentation, and fewer blocks in the linked list of compact region blocks.
### Proposed Fix
I think the fix for this could just be to delete the special case for objects larger than the large object threshold from the `allocateForCompact` function,
i.e. to delete https://gitlab.haskell.org/ghc/ghc/-/blob/a9ce159ba58ca7e8946b46e19b1361588b677a26/rts/sm/CNF.c#L492-501
No further change would be necessary, the function would still be correct due to the fallback allocation
(which incidentally does take the default compact region block size into account):
https://gitlab.haskell.org/ghc/ghc/-/blob/a9ce159ba58ca7e8946b46e19b1361588b677a26/rts/sm/CNF.c#L529-538
And as far as I can tell, there is no obvious reason why large objects need to be treated specially in the compact region allocator:
As long as there is space in the nursery, a large object would just be allocated there anyway.
## Environment
* GHC version used: 8.8.4https://gitlab.haskell.org/ghc/ghc/-/issues/17097Explore putting persistent data structures into compact region2021-04-09T11:01:03ZMatthew PickeringExplore putting persistent data structures into compact region@AndreasK and @bgamari and I (and Hanue) pondered whether it would be worthwhile putting the `ModDetails` into a compact region. The note explains that the information doesn't change and is essentially a cache. Putting it into a compact ...@AndreasK and @bgamari and I (and Hanue) pondered whether it would be worthwhile putting the `ModDetails` into a compact region. The note explains that the information doesn't change and is essentially a cache. Putting it into a compact region would reduce GC pressure.
It would also be potentially worthwhile to use fixed size arrays rather than lists for its fields.
There are probably other data structures which would benefit from the treatment, perhaps `ModIface`?
----------------------
Update: 2020-03-24
A proof of concept that compacting is possible is present on [this branch](https://gitlab.haskell.org/ghc/ghc/-/tree/wip/compact-iface)
# Roadmap to Compacting a `ModIface`.
* [x] Use a type for `FastString` backed by an unpinned ByteArray to implement FastString (!1675) (Owner @DanielG)
* [x] (Optional) Reduce allocations as a result of !1675 by using `ShortByteString` in more places rather than converting back to a pinned `ByteString`.
* [ ] (Optional) Remove use of `FastString` from code gen, in order to be able to remove the cached `length` field and cached Z-encoded string from `FastString`. (!2949, owner @sgraf812)
* [ ] Remove `TyThing` from `WiredIn` names, see (!2598, owner @mpickering )
* [ ] Introduce `IfaceLiteral` type to remove the use of `Type` in `Literal`. (https://gitlab.haskell.org/ghc/ghc/-/commit/aa293b8959cd27efe2e5146cb8d8f77d0dbb706a#bd4216a09ad2640db4a06e7b5a593a1a94e884fa_15_16, owner @mpickering)
* [ ] Separate cache fields from the `ModIface`, they are functions so can't be compacted (https://gitlab.haskell.org/ghc/ghc/-/commit/dbe6222995e583981a9c660c0935bf6141882a36, owner @mpickering )https://gitlab.haskell.org/ghc/ghc/-/issues/19095compact regions: Add a hash-consing variant2021-03-05T09:36:27ZMatthew Pickeringcompact regions: Add a hash-consing variantThere are currently two ways to compact an object.
1. Normal way, don't share anything.
2. Sharing preserving, preserve existing sharing
It has been discussed a few times about adding another variant which performs hash-consing when a...There are currently two ways to compact an object.
1. Normal way, don't share anything.
2. Sharing preserving, preserve existing sharing
It has been discussed a few times about adding another variant which performs hash-consing when adding closures into the compact. Typically there are can be a lot of identical allocated closures which are not shared so putting them into a compact and hash-consing them could be a good way to reduce the memory footprint of an application.
One particular example of this happening in GHC is there are many identical `TyConApp` nodes allocated in memory as no special effort is made to introduce sharing except for a some special cases.https://gitlab.haskell.org/ghc/ghc/-/issues/19454evacuate: strange closure type 20043649 (something to do with compact regions?)2021-03-01T22:22:57ZMatthew Pickeringevacuate: strange closure type 20043649 (something to do with compact regions?)I am getting the following error sometimes when using my branch of GHC to build Cabal which compacts modifaces. Seems to be something to do with `compactAddWithSharing`.
Branch is here, https://gitlab.haskell.org/ghc/ghc/-/commits/wip/...I am getting the following error sometimes when using my branch of GHC to build Cabal which compacts modifaces. Seems to be something to do with `compactAddWithSharing`.
Branch is here, https://gitlab.haskell.org/ghc/ghc/-/commits/wip/compact-modiface-new
The problem seems to happen quite late in the compilation so perhaps there is something overflowing. I would start looking in `evacuate_hash_entry` I think. It also doesn't always happen..
```
ghc: internal error: evacuate: strange closure type 20043649
Stack trace:
0x7f84eb1801b2 set_initial_registers (rts/Libdw.c:294.5)
0x7f84eacc1198 dwfl_thread_getframes (/nix/store/sv6f05ngaarba50ybr6fdfc7cciv6nbv-elfutils-0.176/lib/libdw-0.176.so)
0x7f84eacc0c5b get_one_thread_cb (/nix/store/sv6f05ngaarba50ybr6fdfc7cciv6nbv-elfutils-0.176/lib/libdw-0.176.so)
0x7f84eacc0f97 dwfl_getthreads (/nix/store/sv6f05ngaarba50ybr6fdfc7cciv6nbv-elfutils-0.176/lib/libdw-0.176.so)
0x7f84eacc1567 dwfl_getthread_frames (/nix/store/sv6f05ngaarba50ybr6fdfc7cciv6nbv-elfutils-0.176/lib/libdw-0.176.so)
0x7f84eb180879 libdwGetBacktrace (rts/Libdw.c:265.8)
0x7f84eb1888fd rtsFatalInternalErrorFn (rts/RtsMessages.c:170.6)
0x7f84eb188add barf (rts/RtsMessages.c:49.3)
0x7f84eb172681 evacuate1 (rts/sm/Evac.c:1061.5)
0x7f84eb1ad730 evacuate_hash_entry (rts/sm/Scav.c:176.5)
0x7f84eb17c2dc mapHashTable (rts/Hash.c:466.76)
0x7f84eb1ad900 scavenge_compact1 (rts/sm/Scav.c:196.9)
0x7f84eb1ae1c5 scavenge_one (rts/sm/Scav.c:1573.9)
0x7f84eb1aefcb scavenge_loop1 (rts/sm/Scav.c:2039.12)
0x7f84eb1a54ad scavenge_until_all_done (rts/sm/GC.c:1274.13)
0x7f84eb1a6c3b GarbageCollect (rts/sm/GC.c:1498.22)
0x7f84eb18bb09 scheduleDoGC (rts/Schedule.c:1892.9)
0x7f84eb18c7ca schedule (rts/Schedule.c:579.7)
0x7f84eb18df31 scheduleWaitThread (rts/Schedule.c:2657.11)
0x7f84eb18875d hs_main (rts/RtsMain.c:73.18)
0x436902 (null) (/home/matt/ghc-compact-iface/_build/stage1/bin/ghc)
0x7f84eae5bd8b __libc_start_main (/nix/store/xg6ilb9g9zhi2zg1dpi4zcp288rhnvns-glibc-2.30/lib/libc-2.30.so)
0x43694a _start (../sysdeps/x86_64/start.S:122.0)
(GHC version 9.1.20210226 for x86_64_unknown_linux)
Please report this as a GHC bug: https://www.haskell.org/ghc/reportabug
```https://gitlab.haskell.org/ghc/ghc/-/issues/15652SerializedCompact has a [(Ptr a, Word)] instead of a custom datatype2021-01-24T06:20:32ZchessaiSerializedCompact has a [(Ptr a, Word)] instead of a custom datatype```hs
data SerializedCompact a = SerializedCompact
{ serializedCompactBlockList :: [(Ptr a, Word)]
, serializedCompactRoot :: Ptr a
}
```
I'm not sure why the first member of `SerializedCompact` isn't something like
```hs
data Co...```hs
data SerializedCompact a = SerializedCompact
{ serializedCompactBlockList :: [(Ptr a, Word)]
, serializedCompactRoot :: Ptr a
}
```
I'm not sure why the first member of `SerializedCompact` isn't something like
```hs
data CompactBlock a = CompactBlock {-# UNPACK #-} (Ptr a) {-# UNPACK #-} Word
```
so the `Ptr` can unpack into the constructor, which isn't possible with `(,)`. `SerializedCompact` would then look like
```hs
data SerializedCompact a = SerializedCompact
{ serializedCompactBlockList :: [CompactBlock a]
, serializedCompactRoot :: Ptr a
}
```
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ------------------ |
| Version | 8.4.3 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | libraries/compact |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | andrewthad, ezyang |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"SerializedCompact has a [(Ptr a, Word)] instead of a custom datatype","status":"New","operating_system":"","component":"libraries/compact","related":[],"milestone":"8.8.1","resolution":"Unresolved","owner":{"tag":"OwnedBy","contents":"ezyang"},"version":"8.4.3","keywords":["compact","ghc-compact,","regions"],"differentials":[],"test_case":"","architecture":"","cc":["andrewthad","ezyang"],"type":"Bug","description":"{{{#!hs\r\ndata SerializedCompact a = SerializedCompact\r\n { serializedCompactBlockList :: [(Ptr a, Word)]\r\n , serializedCompactRoot :: Ptr a\r\n }\r\n}}}\r\n\r\nI'm not sure why the first member of {{{SerializedCompact}}} isn't something like\r\n\r\n{{{#!hs\r\ndata CompactBlock a = CompactBlock {-# UNPACK #-} (Ptr a) {-# UNPACK #-} Word\r\n}}}\r\n\r\nso the {{{Ptr}}} can unpack into the constructor, which isn't possible with {{{(,)}}}. {{{SerializedCompact}}} would then look like\r\n\r\n{{{#!hs\r\ndata SerializedCompact a = SerializedCompact\r\n { serializedCompactBlockList :: [CompactBlock a]\r\n , serializedCompactRoot :: Ptr a\r\n }\r\n}}}","type_of_failure":"OtherFailure","blocking":[]} -->Edward Z. YangEdward Z. Yanghttps://gitlab.haskell.org/ghc/ghc/-/issues/18283T16992 fails with debug runtime2021-01-07T05:09:26ZÖmer Sinan AğacanT16992 fails with debug runtime```
$ ghc-stage2 T16992.hs -O -fforce-recomp -debug
[1 of 1] Compiling Main ( T16992.hs, T16992.o )
Linking T16992 ...
$ ./T16992
T16992: internal error: ASSERTION FAILED: file rts/sm/Sanity.c, line 1018
(GHC version 8....```
$ ghc-stage2 T16992.hs -O -fforce-recomp -debug
[1 of 1] Compiling Main ( T16992.hs, T16992.o )
Linking T16992 ...
$ ./T16992
T16992: internal error: ASSERTION FAILED: file rts/sm/Sanity.c, line 1018
(GHC version 8.11.0.20200530 for x86_64_unknown_linux)
Please report this as a GHC bug: https://www.haskell.org/ghc/reportabug
zsh: abort (core dumped) ./T16992
```https://gitlab.haskell.org/ghc/ghc/-/issues/13165Speed up the RTS hash table2020-12-21T04:09:30ZdobenourSpeed up the RTS hash tableThe RTS hash table is rather slow. Every lookup involves at least one indirect call (to get a hash code). It also uses separate chaining, which is itself slow.
Until recently, this didn't really matter, since the RTS hash table wasn't u...The RTS hash table is rather slow. Every lookup involves at least one indirect call (to get a hash code). It also uses separate chaining, which is itself slow.
Until recently, this didn't really matter, since the RTS hash table wasn't used for anything particularly performance critical other than `StableName` operations. However, it has since become the bottleneck when compacting with sharing, to the point that compacting without sharing is around 10x faster and is thus the default.
Fortunately, there are easy ways to make the hash table faster. These include:
- Use linear probing instead of separate chaining.
- Specialize for the case of pointer keys
- Don't use indirect calls for hashing
- Use a fast, universal hash function for pointers.
- Use SSE instructions where available to do fast searches.
- Minimize the number of indirections in the use of the table.
In both the case of the StablePtr table and that of compact regions, the keys of the table are not GC pointers, but the values are, so there needs to be a way to ensure that the GC handles the table correctly8.6.1https://gitlab.haskell.org/ghc/ghc/-/issues/18706inCompact and isCompact don't seem to work2020-10-23T01:27:31ZDavid FeuerinCompact and isCompact don't seem to work## inCompact and isCompact always seem to return False
`inCompact` is supposed to indicate whether a certain value is in a
particular region. `isCompact` is supposed to indicate whether a
certain value is in any compact region. I have n...## inCompact and isCompact always seem to return False
`inCompact` is supposed to indicate whether a certain value is in a
particular region. `isCompact` is supposed to indicate whether a
certain value is in any compact region. I have not been able to
convince either of these to return `True` under any circumstances.
## Steps to reproduce
```haskell
import Data.Compact
import Control.Exception (evaluate)
import Control.DeepSeq
import System.Mem
main = do
p <- evaluate $ force [1..10000 :: Integer]
foo <- compact p
performMajorGC -- Even this doesn't do the trick.
isCompact p >>= print
inCompact foo p >>= print
print . sum $ getCompact foo
```
This prints `False` twice before successfully summing and printing the contents of `foo`.
Optimization level makes no difference.
## Expected behavior
I expect this to print `True` twice. Even if `isCompact` is too hard to implement, I would at least expect `inCompact` to work.
## Environment
* GHC version used: 8.10.1
Optional:
* Operating System:
* System Architecture:https://gitlab.haskell.org/ghc/ghc/-/issues/17640compactAdd run time grows linearly with compact region size for certain inputs2020-09-28T12:21:35ZFabian ThorandcompactAdd run time grows linearly with compact region size for certain inputs## Summary
For objects of certain sizes `compactAdd` is linear in the number of already added objects.
When adding multiple such objects, the total time for adding them all grows quadratically.
## Steps to reproduce
The following repr...## Summary
For objects of certain sizes `compactAdd` is linear in the number of already added objects.
When adding multiple such objects, the total time for adding them all grows quadratically.
## Steps to reproduce
The following reproducer adds the value of type `X` into a compact region `n` times, and then again `2n` times into a different compact region. The total time quadruples, even though the number of `compactAdd`s was only doubled.
```haskell
{-# OPTIONS_GHC -O2 #-}
import Control.Monad (replicateM_)
import GHC.Compact (compact, compactAdd, compactSize)
import System.CPUTime (getCPUTime)
import Data.Word (Word64)
import Text.Printf (printf)
import System.Environment (getArgs)
data X = X !Word64 !Word64 !Word64 !Word64 !Word64 !Word64 !Word64 !Word64
main :: IO ()
main = do
-- Use this in the object we put in the compact region,
-- in order to prevent GHC from making it a CAF
-- (which are not added to compact regions).
blackboxInput <- length <$> getArgs
let
-- Build a value that is larger than the allowed remaining free space
-- before a block is considered full.
obj = X (fromIntegral blackboxInput) 0 0 0 0 0 0 0
numAdd = 200000
c1 <- compact ()
c2 <- compact ()
-- Copy the above object multiple times in each compact region
-- and measure how long it takes.
printf "Calling compactAdd %d times\n" numAdd
start1 <- getCPUTime
replicateM_ numAdd (compactAdd c1 obj)
end1 <- getCPUTime
printf "Calling compactAdd %d times\n" (2 * numAdd)
start2 <- getCPUTime
replicateM_ (2 * numAdd) (compactAdd c2 obj)
end2 <- getCPUTime
-- Print the sizes of the compact regions as a sanity check
-- The 2nd should be twice as large as the first
putStrLn "Compact region sizes (sanity check)"
compactSize c1 >>= print
compactSize c2 >>= print
let
ps1 = end1 - start1
ps2 = end2 - start2
printf "1st: %d ps total, %f ps/obj\n" ps1 (realToFrac ps1 / realToFrac numAdd :: Double)
printf "2nd: %d ps total, %f ps/obj\n" ps2 (realToFrac ps2 / realToFrac (2 * numAdd) :: Double)
-- Note that the time per compactAdd for the second run is roughly
-- twice as large as for the first run.
-- The total time has quadrupled, even though the number of
-- compactAdd calls only doubled.
```
To me it looks like the cause is the linear search for a free block in `allocateForCompact` that is triggered when the object does not fit into the nursery block, but the nursery block isn't full either:
https://gitlab.haskell.org/ghc/ghc/blob/ghc-8.6.5-release/rts/sm/CNF.c#L516-524
Note that `-O2` is required so that the value of type `X` is actually a single heap
object. Otherwise, GHC doesn't seem to unpack the fields, and the small
boxed `Word64` fill up the nursery block eventually which prevents this
bug from triggering.
## Expected behavior
The time it takes for adding the objects to the compact region should grow linearly with the number of objects, not quadratically.
## Environment
* GHC version used: 8.8.1, 8.6.5
Optional:
* Operating System: Ubuntu 18.04.3 LTS
* System Architecture: x86_64https://gitlab.haskell.org/ghc/ghc/-/issues/18709Teach GHC about the evaluatedness of compacted things2020-09-17T21:02:40ZDavid FeuerTeach GHC about the evaluatedness of compacted things## Motivation
The result values of `compactAdd#` and `compactAddWithSharing#` are always in normal form. Unfortunately, the compiler doesn't know that.
## Proposal
Use the same trickery that `seq#` employs to teach GHC what's what. Be...## Motivation
The result values of `compactAdd#` and `compactAddWithSharing#` are always in normal form. Unfortunately, the compiler doesn't know that.
## Proposal
Use the same trickery that `seq#` employs to teach GHC what's what. Be sure to make the pointer field in `Compact` strict to take advantage of this.https://gitlab.haskell.org/ghc/ghc/-/issues/15653Both `Ptr a` in SerializedCompact are inaccurate because of the `a`2020-07-23T09:32:54ZchessaiBoth `Ptr a` in SerializedCompact are inaccurate because of the `a``SerializedCompactPtr` is defined as:
```hs
data SerializedCompact a = SerializedCompact
{ serializedCompactBlockList :: [(Ptr a, Word)]
, serializedCompactRoot :: Ptr a
}
```
But, these `Ptr a` values are a lie, because they don...`SerializedCompactPtr` is defined as:
```hs
data SerializedCompact a = SerializedCompact
{ serializedCompactBlockList :: [(Ptr a, Word)]
, serializedCompactRoot :: Ptr a
}
```
But, these `Ptr a` values are a lie, because they don't point to something of type 'a', which makes the documentation for `ghc-compact` sort of confusing to look at. A more accurate type would just be `Addr`.
The consequences of this being changes to `Addr` are
1: breaking API changes (though not many people use compact regions)
2: A dependency on primitive would be necessary, though I'm again unsure how big of a deal this is, given that ghc-compact already depends on bytestring. (`Addr` should probably be moved to base, and re-exported from primitive, which would avoid this issue.)
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ------------------ |
| Version | 8.4.3 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | libraries/compact |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | andrewthad, ezyang |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"Both `Ptr a` in SerializedCompact are inaccurate because of the `a`","status":"New","operating_system":"","component":"libraries/compact","related":[],"milestone":"8.8.1","resolution":"Unresolved","owner":{"tag":"OwnedBy","contents":"ezyang"},"version":"8.4.3","keywords":["compact","ghc-compact,","regions"],"differentials":[],"test_case":"","architecture":"","cc":["andrewthad","ezyang"],"type":"Bug","description":"{{{SerializedCompactPtr}}} is defined as:\r\n\r\n{{{#!hs\r\ndata SerializedCompact a = SerializedCompact\r\n { serializedCompactBlockList :: [(Ptr a, Word)]\r\n , serializedCompactRoot :: Ptr a\r\n }\r\n}}}\r\n\r\nBut, these {{{Ptr a}}} values are a lie, because they don't point to something of type 'a', which makes the documentation for {{{ghc-compact}}} sort of confusing to look at. A more accurate type would just be {{{Addr}}}.\r\n\r\nThe consequences of this being changes to {{{Addr}}} are\r\n1: breaking API changes (though not many people use compact regions)\r\n2: A dependency on primitive would be necessary, though I'm again unsure how big of a deal this is, given that ghc-compact already depends on bytestring. ({{{Addr}}} should probably be moved to base, and re-exported from primitive, which would avoid this issue.)","type_of_failure":"OtherFailure","blocking":[]} -->9.0.1Edward Z. YangEdward Z. Yanghttps://gitlab.haskell.org/ghc/ghc/-/issues/16992compactFixupPointers# fails if compact region blocks are more than 2 GiB apart2020-07-08T17:18:09ZFabian ThorandcompactFixupPointers# fails if compact region blocks are more than 2 GiB apart## Summary
Importing a compact region using `importCompact` from the `ghc-compact` package fails if the addresses of the compact region blocks span across more than 2 GiB.
## Steps to reproduce
The smallest Haskell example for reprodu...## Summary
Importing a compact region using `importCompact` from the `ghc-compact` package fails if the addresses of the compact region blocks span across more than 2 GiB.
## Steps to reproduce
The smallest Haskell example for reproducing the bug I could make is the following:
```haskell
import qualified Data.Compact as Compact
import qualified Data.Compact.Serialize as CompactSerialize
-- | Minimal test case for reproducing compactFixupPointers# bug for large compact regions.
main :: IO ()
main = do
let
large = 1024 * 1024 * 128
largeString = replicate large 'A'
region <- Compact.compact largeString
Compact.compactSize region >>= print
CompactSerialize.writeCompact "/tmp/bug.compact" region
deserialized <- CompactSerialize.unsafeReadCompact "/tmp/bug.compact"
case deserialized of
Left err -> putStrLn err
Right largeString' -> print (Compact.getCompact largeString' == largeString)
```
It uses the `compact` library, but I could also reproduce it with a hand-rolled deserializer calling `GHC.Compact.Serialized.importCompact` directly.
Compiling and running that file results in `Failed to import compact` being printed to stdout.
I traced that error message (which comes from the `compact` library) back to a call to `compactFixupPointers#` in the `ghc-compact` library.
I had a quick look at the corresponding source code of the RTS (in `rts/sm/CNF.c`) and I suspect a faulty order predicate passed to `qsort` in `build_fixup_table` is the root cause of the issue. It is implemented as
```c
static int
cmp_fixup_table_item (const void *e1, const void *e2)
{
const StgWord *w1 = e1;
const StgWord *w2 = e2;
return *w1 - *w2;
}
```
However, on a 64 bit system, `sizeof(int)` is still just 4 bytes while the difference of two `StgWord`s is 8 bytes in size.
If the two pointers being compared are too far apart, an overflow causes the returned order to be the reverse of the actual order.
The following self-contained C program demonstrates this behavior (if compiled on a 64 bit architecture):
```c
#include <stdio.h>
#include <stdint.h>
typedef uint64_t StgWord;
static int
cmp_fixup_table_item (const void *e1, const void *e2)
{
const StgWord *w1 = e1;
const StgWord *w2 = e2;
return *w1 - *w2;
}
static void
check (const StgWord *e1, const StgWord *e2)
{
printf("*e1 = %ld *e2=%ld\n", *e1, *e2);
printf("*e1 < *e2 == %d\n", (int)(*e1 < *e2));
printf("cmp_fixup_table_item(e1,e2) == %d\n\n", cmp_fixup_table_item(e1, e2));
}
int main() {
StgWord examplePointer1 = 1234567;
StgWord examplePointer2 = examplePointer1 + 1234;
StgWord bigOffset = (1L << 31) + 1234L;
StgWord examplePointer3 = examplePointer1 + bigOffset;
check(&examplePointer1, &examplePointer2);
check(&examplePointer1, &examplePointer3);
return 0;
}
```
The output is
```
*e1 = 1234567 *e2=1235801
*e1 < *e2 == 1
cmp_fixup_table_item(e1,e2) == -1234
*e1 = 1234567 *e2=2148719449
*e1 < *e2 == 1
cmp_fixup_table_item(e1,e2) == 2147482414
```
Note how for pointers that are close to each other, it returns a negative number (as it should),
but if the pointers are too far apart, the sign switches.
## Expected behavior
The Haskell program above should print `True`, not an error message.
## Environment
* GHC version used: 8.6.3
Optional:
* Operating System: Ubuntu 18.04
* System Architecture: x86-648.10.2Ömer Sinan AğacanÖmer Sinan Ağacanhttps://gitlab.haskell.org/ghc/ghc/-/issues/18046When importCompactByteStrings returns Nothing is unclear2020-04-13T15:00:44ZÖmer Sinan AğacanWhen importCompactByteStrings returns Nothing is unclearDocumentation of `GHC.Compact.Serialized.importCompactByteStrings`:
> Convenience function for importing a compact region that is represented by a list of strict 'ByteString's.
This says nothing about when it returns nothing. Type of t...Documentation of `GHC.Compact.Serialized.importCompactByteStrings`:
> Convenience function for importing a compact region that is represented by a list of strict 'ByteString's.
This says nothing about when it returns nothing. Type of the function:
```haskell
importCompactByteStrings :: SerializedCompact a -> [ByteString.ByteString] -> IO (Maybe (Compact a))
```
Looking at the code, this calls the function `sanityCheckByteStrings` and when it returns `False`, `importCompactByteStrings` returns `Nothing`. However it's also unclear what does `sanityCheckByteStrings` do.
We should document what does it mean for `importCompactByteStrings` to return `Nothing`.https://gitlab.haskell.org/ghc/ghc/-/issues/17937Runtime panic in CNF test 'compact_gc' when compacting GC is enabled2020-04-09T20:50:31ZÖmer Sinan AğacanRuntime panic in CNF test 'compact_gc' when compacting GC is enabledProgram:
```haskell
import Control.Monad
import GHC.Compact
import qualified Data.Map as Map
main = do
let m = Map.fromList [(x, show x) | x <- [1 .. (10000 :: Int)]]
c <- compactWithSharing m
print =<< compactSize c
c <- fol...Program:
```haskell
import Control.Monad
import GHC.Compact
import qualified Data.Map as Map
main = do
let m = Map.fromList [(x, show x) | x <- [1 .. (10000 :: Int)]]
c <- compactWithSharing m
print =<< compactSize c
c <- foldM (\c _ -> do c <- compactWithSharing (getCompact c)
print =<< compactSize c
return c)
c [1..10]
print (length (show (getCompact c)))
print =<< compactSize c
```
Run with `+RTS -c`:
```
$ ghc-stage2 test.hs -rtsopts
Linking test ...
$ ./test +RTS -c
test: internal error: scavenge_mark_stack: unimplemented/strange closure type 0 @ 0x420012d5c8
(GHC version 8.11.0.20200319 for x86_64_unknown_linux)
Please report this as a GHC bug: https://www.haskell.org/ghc/reportabug
zsh: abort (core dumped) ./test +RTS -c
```
Backtrace:
```
>>> bt
#0 __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:51
#1 0x00007f91e4de7801 in __GI_abort () at abort.c:79
#2 0x0000000000661757 in rtsFatalInternalErrorFn (s=0x23a8cd "invalid closure, info=%p", ap=0x7fffd25b8840) at rts/RtsMessages.c:186
#3 0x000000000066130e in barf (s=0x23a8cd "invalid closure, info=%p") at rts/RtsMessages.c:48
#4 0x000000000069fd5e in evacuate (p=0x7fffd25b89d0) at rts/sm/Evac.c:592
#5 0x000000000069550a in evacuate_hash_entry (dat=0x7fffd25b8a60, key=283469929872, value=0x42001e5c71) at rts/sm/Scav.c:172
#6 0x00000000006771a6 in mapHashTable (table=0x12b6810, data=0x7fffd25b8a60, fn=0x6954d3 <evacuate_hash_entry>) at rts/Hash.c:458
#7 0x00000000006955b2 in scavenge_compact (str=0x42001f5018) at rts/sm/Scav.c:192
#8 0x0000000000697a7b in scavenge_one (p=0x42001f5018) at rts/sm/Scav.c:1561
#9 0x00000000006983e8 in scavenge_large (ws=0x827d80 <the_gc_thread+320>) at rts/sm/Scav.c:2016
#10 0x0000000000698556 in scavenge_find_work () at rts/sm/Scav.c:2086
#11 0x000000000069861c in scavenge_loop () at rts/sm/Scav.c:2155
#12 0x0000000000691fe4 in scavenge_until_all_done () at rts/sm/GC.c:1175
#13 0x0000000000690990 in GarbageCollect (collect_gen=1, do_heap_census=false, deadlock_detect=false, gc_type=0, cap=0x826500 <MainCapability>, idle_cap=0x0) at rts/sm/GC.c:449
#14 0x0000000000668cbf in scheduleDoGC (pcap=0x7fffd25b8f78, task=0x1217db0, force_major=false, deadlock_detect=false) at rts/Schedule.c:1855
#15 0x00000000006681e6 in schedule (initialCapability=0x826500 <MainCapability>, task=0x1217db0) at rts/Schedule.c:565
#16 0x00000000006696b7 in scheduleWaitThread (tso=0x4200105388, ret=0x0, pcap=0x7fffd25b9080) at rts/Schedule.c:2600
#17 0x000000000067ad18 in rts_evalLazyIO (cap=0x7fffd25b9080, p=0x6cb338, ret=0x0) at rts/RtsAPI.c:530
#18 0x000000000067b4bd in hs_main (argc=1, argv=0x7fffd25b9278, main_closure=0x6cb338, rts_config=...) at rts/RtsMain.c:72
#19 0x0000000000254034 in main ()
```
This happens pretty reliably, every run.
If I also pass `-DS` I get the same panic. Assuming `-DS` checks compact regions
correctly, this means that the bug caught in the same GC that breaks the
invariants/data structures or causes heap corruption.Ömer Sinan AğacanÖmer Sinan Ağacanhttps://gitlab.haskell.org/ghc/ghc/-/issues/17960LitString, ByteString, FastString and ShortByteString with relevance to compa...2020-04-03T10:26:59ZMatthew PickeringLitString, ByteString, FastString and ShortByteString with relevance to compactingIn the `Literal` data type, `LitString` is used to represented string literals. In the old days this was just string literals which a user would write in the program, so usually quite short strings. These strings are currently
represent...In the `Literal` data type, `LitString` is used to represented string literals. In the old days this was just string literals which a user would write in the program, so usually quite short strings. These strings are currently
represented by a `ByteString`.
In recent times @hsyl20 has modified Template Haskell (!141) in order to directly construct a `LitString` from a `ByteString`. This means that you can now construct very big `LitString`s by embedding whole files into a `LitString`.
Now that we are trying to compact the `ModIface` (#17097), we have to change the `LitString` representation to something compactable, for now I changed it to `FastString`, but this isn't ideal as now @hsyl20 s big files will be loaded into memory rather than just existing as a pointer for the whole compilation pipeline. It is unlikely that any of his big strings would make it into
an interface file anyway because they are too big to include in an unfolding.
So the proposal is something like the following:
* Back a `LitString` by a `FastString`, `ShortByteString` or `Text` so it can be compacted. There is quite a lot of manipulation of `LitString` that happens so I went with `FastString` for now. Perhaps `Text` would be a better choice.
* Introduce a new form of literal, `LitBytes` which is not part of the `Literal` data type, and must exist only at the top-level. This way, the unfolding can never be exposed for something of `LitBytes`. This can be backed by a `ByteString`. This will also mean the `LitBytes` is not copied into an interface file.
* Use `LitBytes` as a target for the TH file embedding stuff rather than `LitString`.
This will mean that we can compact a `Literal`, but without having to copy the big `LitString`s created from embedding files into memory.
cc @hsyl20https://gitlab.haskell.org/ghc/ghc/-/issues/17734Functions in compact regions2020-03-31T07:47:02ZVladislav ZavialovFunctions in compact regions```
ghci> compact even
*** Exception: compaction failed: cannot compact functions
```
Why is that? Functions can be stored in compact regions as pointers to the code together with data captured in the closure.```
ghci> compact even
*** Exception: compaction failed: cannot compact functions
```
Why is that? Functions can be stored in compact regions as pointers to the code together with data captured in the closure.https://gitlab.haskell.org/ghc/ghc/-/issues/17297CNF.c:insertCompactHash doesn't correctly dirty regions2019-11-03T20:24:49ZBen GamariCNF.c:insertCompactHash doesn't correctly dirty regionsConsider `CNF.c:insertCompactHash`:
```c
void
insertCompactHash (Capability *cap,
StgCompactNFData *str,
StgClosure *p, StgClosure *to)
{
insertHashTable(str->hash, (StgWord)p, (const void*)to);
...Consider `CNF.c:insertCompactHash`:
```c
void
insertCompactHash (Capability *cap,
StgCompactNFData *str,
StgClosure *p, StgClosure *to)
{
insertHashTable(str->hash, (StgWord)p, (const void*)to);
const StgInfoTable *strinfo = &str->header.info;
if (strinfo == &stg_COMPACT_NFDATA_CLEAN_info) {
strinfo = &stg_COMPACT_NFDATA_DIRTY_info;
recordClosureMutated(cap, (StgClosure*)str);
}
}
```
At first glance this looks reasonable. However, note how we are dirtying the region:
```
strinfo = &stg_COMPACT_NFDATA_DIRTY_info;
```
This does not do at all what we want; it simply sets the local variable, not the info table pointer.
For this reason compact regions with sharing preservation enabled get added to the `mut_list` once for every object in the region. Terrible!8.8.2Ben GamariBen Gamari