-
Notifications
You must be signed in to change notification settings - Fork 14
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Speed up local reification by storing Map Name
s in DsM
#130
Comments
One thing I omitted in #130 (comment) is that we'll need to update the definition of withLocalDeclarations :: DsMonad q => [Dec] -> DsM q a -> q a
withLocalDeclarations new_decs (DsM x) = do
env <- ask
let new_infos = ...
new_fixities = ...
new_types = ...
env' = DsEnv { dsEnvDecs = orig_decs ++ new_decs
, dsEnvDecMap = combine (dsEnvDecMap env) new_infos
, dsEnvFixityMap = combine (dsEnvFixityMap env) new_fixities
, dsEnvTypes = combine (dsEnvTypeMap env) new_types
}
runReaderT x env'
combine :: Map Name a -> Map Name a -> Map Name a
combine old_map new_map = ??? Question: how should combine old_map new_map = Map.union old_map new_map Or should it be this? combine old_map new_map = Map.union new_map old_map As it turns out, only the former version of |
This certainly looks like a good idea to me. It's kind of amazing that anyone has been hurt by this performance problem, but I guess people actually find |
I have pushed a working implementation of this idea to the {-# LANGUAGE TemplateHaskell #-}
module Bug where
import Language.Haskell.TH
import Language.Haskell.TH.Desugar
$(do [d| type A = Either B B
data A1
-- data A2 through data A1999 ...
data A2000
type G = Either () ()
type F = Either G G
type E = Either F F
type D = Either E E
type C = Either D D
type B = Either C C
|] >>= \decs -> do
t <- withLocalDeclarations decs (expand (DConT (mkName "A")))
runIO $ print t
return []) Here is the time it takes to compile this program using
And here is the time it takes to compile this program using
There's hardly any difference overall! I also tried compiling some lengthier test cases (e.g., the Given the lack of noticeable speedups and the fact that the code in the |
Reifying things in
Q
(e.g., withreify
orreifyFixity
) is quite cheap, as it essentially amounts to looking up what aName
maps to in anIntMap
. Reifying things inDsM
(i.e., local reification), on the other hand, is not nearly as cheap. A lookup inDsM
effectively requires scanning through the entire list of localDec
s until a match for theName
is found.This isn't so unbearable for one-off reifications, but for programs that repeatedly reify things, this can add up. As one data point, the
reifyWithLocals_maybe
function took up a significant portion of the time spent in the profiling report for the program in #123 (comment). Thesingletons
library also uses local reification extensively, and the amount of local reifications will only go up after goldfirere/singletons#432 lands. In light of this, it may be worthwhile to try and speed up the asymptotic complexity of local reification.One possibility is to trade space for time by storing extra information in
DsM
to speed up local reification. I'm envisioning something like this:The
dsEnvDecs
field ofDsEnv
would behave just as it does currently: wheneverwithLocalDeclarations
is invoked, the newDec
s would get added on. In addition, the newMap
fields would also gain new entries. TheseMap
fields would then become the engine that powers the new-and-improvedreifyWithLocals_maybe
,reifyFixityWithLocals
,reifyTypeWithLocals
functions, which constitute the heart ofL.H.T.Desugar.Reify
. This turns local reification from an O(n) operation to an O(log n) operation.The text was updated successfully, but these errors were encountered: