Drop NFData constraint from compact.
[ghc.git] / libraries / compact / Data / Compact.hs
1 {-# LANGUAGE BangPatterns #-}
2 {-# LANGUAGE CPP #-}
3 {-# LANGUAGE MagicHash #-}
4 {-# LANGUAGE UnboxedTuples #-}
5 {-# OPTIONS_GHC -Wno-redundant-constraints -Wno-name-shadowing #-}
6
7 -----------------------------------------------------------------------------
8 -- |
9 -- Module : Data.Compact
10 -- Copyright : (c) The University of Glasgow 2001-2009
11 -- (c) Giovanni Campagna <gcampagn@cs.stanford.edu> 2014
12 -- License : BSD-style (see the file LICENSE)
13 --
14 -- Maintainer : libraries@haskell.org
15 -- Stability : unstable
16 -- Portability : non-portable (GHC Extensions)
17 --
18 -- This module provides a data structure, called a 'Compact', for
19 -- holding immutable, fully evaluated data in a consecutive block of memory.
20 -- Compact regions are good for two things:
21 --
22 -- 1. Data in a compact region is not traversed during GC; any
23 -- incoming pointer to a compact region keeps the entire region
24 -- live. Thus, if you put a long-lived data structure in a compact
25 -- region, you may save a lot of cycles during major collections,
26 -- since you will no longer be (uselessly) retraversing this
27 -- data structure.
28 --
29 -- 2. Because the data is stored contiguously, you can easily
30 -- dump the memory to disk and/or send it over the network.
31 -- For applications that are not bandwidth bound (GHC's heap
32 -- representation can be as much of a x4 expansion over a
33 -- binary serialization), this can lead to substantial speed ups.
34 --
35 -- For example, suppose you have a function @loadBigStruct :: IO BigStruct@,
36 -- which loads a large data structure from the file system. You can "compact"
37 -- the structure with the following code:
38 --
39 -- @
40 -- do r <- 'compact' =<< loadBigStruct
41 -- let x = 'getCompact' r :: BigStruct
42 -- -- Do things with x
43 -- @
44 --
45 -- Note that 'compact' will not preserve internal sharing; use
46 -- 'compactWithSharing' (which is 10x slower) if you have cycles and/or
47 -- must preserve sharing. The 'Compact' pointer @r@ can be used
48 -- to add more data to a compact region; see 'compactAdd' or
49 -- 'compactAddWithSharing'.
50 --
51 -- The implementation of compact regions is described by:
52 --
53 -- * Edward Z. Yang, Giovanni Campagna, Ömer Ağacan, Ahmed El-Hassany, Abhishek
54 -- Kulkarni, Ryan Newton. \"/Efficient communication and Collection with Compact
55 -- Normal Forms/\". In Proceedings of the 20th ACM SIGPLAN International
56 -- Conference on Functional Programming. September 2015. <http://ezyang.com/compact.html>
57 --
58 -- This library is supported by GHC 8.2 and later.
59
60 module Data.Compact (
61 -- * The Compact type
62 Compact,
63
64 -- * Compacting data
65 compact,
66 compactWithSharing,
67 compactAdd,
68 compactAddWithSharing,
69
70 -- * Inspecting a Compact
71 getCompact,
72 inCompact,
73 isCompact,
74 compactSize,
75
76 -- * Other utilities
77 compactResize,
78 ) where
79
80 import Control.Concurrent
81 import GHC.Prim
82 import GHC.Types
83
84 import Data.Compact.Internal as Internal
85
86 -- | Retrieve a direct pointer to the value pointed at by a 'Compact' reference.
87 -- If you have used 'compactAdd', there may be multiple 'Compact' references
88 -- into the same compact region. Upholds the property:
89 --
90 -- > inCompact c (getCompact c) == True
91 --
92 getCompact :: Compact a -> a
93 getCompact (Compact _ obj _) = obj
94
95 -- | Compact a value. /O(size of unshared data)/
96 --
97 -- If the structure contains any internal sharing, the shared data
98 -- will be duplicated during the compaction process. This will
99 -- not terminate if the structure contains cycles (use 'compactWithSharing'
100 -- instead).
101 --
102 -- The object in question must not contain any functions or mutable data; if it
103 -- does, 'compact' will raise an exception. In the future, we may add a type
104 -- class which will help statically check if this is the case or not.
105 --
106 compact :: a -> IO (Compact a)
107 compact = Internal.compactSized 31268 False
108
109 -- | Compact a value, retaining any internal sharing and
110 -- cycles. /O(size of data)/
111 --
112 -- This is typically about 10x slower than 'compact', because it works
113 -- by maintaining a hash table mapping uncompacted objects to
114 -- compacted objects.
115 --
116 -- The object in question must not contain any functions or mutable data; if it
117 -- does, 'compact' will raise an exception. In the future, we may add a type
118 -- class which will help statically check if this is the case or not.
119 --
120 compactWithSharing :: a -> IO (Compact a)
121 compactWithSharing = Internal.compactSized 31268 True
122
123 -- | Add a value to an existing 'Compact'. This will help you avoid
124 -- copying when the value contains pointers into the compact region,
125 -- but remember that after compaction this value will only be deallocated
126 -- with the entire compact region.
127 --
128 -- Behaves exactly like 'compact' with respect to sharing and what data
129 -- it accepts.
130 --
131 compactAdd :: Compact b -> a -> IO (Compact a)
132 compactAdd (Compact compact# _ lock) a = withMVar lock $ \_ -> IO $ \s ->
133 case compactAdd# compact# a s of { (# s1, pk #) ->
134 (# s1, Compact compact# pk lock #) }
135
136 -- | Add a value to an existing 'Compact', like 'compactAdd',
137 -- but behaving exactly like 'compactWithSharing' with respect to sharing and
138 -- what data it accepts.
139 --
140 compactAddWithSharing :: Compact b -> a -> IO (Compact a)
141 compactAddWithSharing (Compact compact# _ lock) a =
142 withMVar lock $ \_ -> IO $ \s ->
143 case compactAddWithSharing# compact# a s of { (# s1, pk #) ->
144 (# s1, Compact compact# pk lock #) }
145
146 -- | Check if the second argument is inside the passed 'Compact'.
147 --
148 inCompact :: Compact b -> a -> IO Bool
149 inCompact (Compact buffer _ _) !val =
150 IO (\s -> case compactContains# buffer val s of
151 (# s', v #) -> (# s', isTrue# v #) )
152
153 -- | Check if the argument is in any 'Compact'. If true, the value in question
154 -- is also fully evaluated, since any value in a compact region must
155 -- be fully evaluated.
156 --
157 isCompact :: a -> IO Bool
158 isCompact !val =
159 IO (\s -> case compactContainsAny# val s of
160 (# s', v #) -> (# s', isTrue# v #) )
161
162 -- | Returns the size in bytes of the compact region.
163 --
164 compactSize :: Compact a -> IO Word
165 compactSize (Compact buffer _ lock) = withMVar lock $ \_ -> IO $ \s0 ->
166 case compactSize# buffer s0 of (# s1, sz #) -> (# s1, W# sz #)
167
168 -- | *Experimental.* This function doesn't actually resize a compact
169 -- region; rather, it changes the default block size which we allocate
170 -- when the current block runs out of space, and also appends a block
171 -- to the compact region.
172 --
173 compactResize :: Compact a -> Word -> IO ()
174 compactResize (Compact oldBuffer _ lock) (W# new_size) =
175 withMVar lock $ \_ -> IO $ \s ->
176 case compactResize# oldBuffer new_size s of
177 s' -> (# s', () #)