#9675: Unreasonable memory usage on large data structures -------------------------------------+------------------------------------- Reporter: Polarina | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.3 Resolution: | Keywords: Operating System: Linux | Architecture: x86_64 (amd64) Type of failure: Compile- | Difficulty: Unknown time performance bug | Blocked By: Test Case: | Related Tickets: Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by nomeata): Did some GHC profiling, and the problem is clearly the huge number of useless variables in the pattern match in the Core for the record selector functions, here for a three-field-record (I’ll spare us the 3000-field- record): {{{ Test.field3 :: Test.Foo -> GHC.Types.Int -> GHC.Types.Int [GblId[[RecSel]], Arity=1, Caf=NoCafRefs, Str=DmdType] Test.field3 = \ (ds_dm2 :: Test.Foo) -> case ds_dm2 of _ [Occ=Dead] { Test.Foo ds1_dm3 ds2_dm4 ds3_dm5 -> ds3_dm5 } }}} See the attached heap profile, `IdInfo`, `Var`, `IntMap` and `[]` are the biggest chunks. The problem is that a data type declaration like {{{ data R = R { field1 :: T1, field2 :: T2 } }}} generates Haskell code of the form {{{ field3 (R {field3 = x}) = x }}} which is then turned in to the form above by general code that also handles multiple fields, field puns, and further patterns in the field. While the submitter’s code above may or may not be reasonable it migth be worth improving the situation for the benefot of modules with medium-sized records (including GHC’s own DynFlags module). I see a two approaches: 1. Avoid generating actual Core for these selector. Make them implicitly availailbe, and only generated them in STG or later. I am not sure if there is precedence for such implicit things. 2. Extend the this code somehow: {{{ AltCon = DataAlt DataCon | LitAlt Literal | DEFAULT }}} I have two ideas here. Either special-case the single-field-match, i.e. a new constructor {{{ | FieldSelAlt DataCon Int }}} which binds only one variable, the field indicated by the `Int` variable. This would get rid of the quadraticness of the representation. But quite a bit of code would have to handle two cases, and there would be no unique representation of the same match. The other one is to extend `DataAlt` by a bit field: {{{ = DataAlt DataCon [Bool] }}} (with a more suitable data structure for `[Bool]`, e.g. some kind of `BitField`). The idea is that this field specifies what fields of the constructor are actually used by the match. The number of variables bound by such an alternative would equal to the number of `True`s in the list. This would improve every alternative where not all variables are used. It might make some code more complicated – I could imagine that some compiler phases expect that within a case alternative, there is a locally bound name for every field – but maybe it’s not too bad. This would still be quadratic (but with a much lower factor – one bit instead of whatever `Id` + `IdInfo` + `(:)` + whatnot use). We can even get rid of that by making the `BitField` a data type like {{{ data BitField = Empty | Singleton Int | ManyBits ByteString | All }}} (`Empty` would be useful for `Con {}` patterns. Not sure if `All` is useful. Maybe `data BitField = Empty | Singleton Int | All` is actually enough, if few-but-more-than-one-field-patterns are rare.) At this point I’m hoping for someone experienced (e.g. SPJ, of course) to tell us which of these ideas are totally whacky, and which are worth pursuing, and if so, what problems to expect. But this is not a promise that I’ll implement it :-) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9675#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler