Opened 2 years ago

Closed 22 months ago

#14254 closed bug (fixed)

The Binary instance for TypeRep smells a bit expensive

Reported by: dfeuer Owned by:
Priority: normal Milestone: 8.4.1
Component: Compiler Version: 8.2.1
Keywords: Typeable Cc: bgamari, RyanGlScott
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Compile-time performance bug Test Case:
Blocked By: Blocking:
Related Tickets: #14337 Differential Rev(s): Phab:D3998, Phab:D4082, Phab:D4085
Wiki Page:

Description (last modified by dfeuer)

In particular, get uses getSomeTypeRep. getSomeTypeRep, in turn, calls typeRepKind through its recursion. But typeRepKind is itself recursive, fully inspecting the spine of its argument. That smells quadratic to me. The solution, I believe, is to change the type of getSomeTypeRep to BinHandle -> IO (SomeTypeRep, SomeTypeRep).

Attachments (1)

Big.hs (5.1 KB) - added by dfeuer 2 years ago.
Test case

Download all attachments as: .zip

Change History (19)

comment:1 Changed 2 years ago by dfeuer

Description: modified (diff)

comment:2 Changed 2 years ago by dfeuer

No, that may not quite solve it, because the Fun case has to calculate typeRepKind res.

comment:3 Changed 2 years ago by bgamari

Differential Rev(s): Phab:D3998
Milestone: 8.4.1
Status: newpatch

Very good observation. I think Phab:D3998 should greatly improve the situation. We also need to get a fix into binary when an approach has been decided.

comment:4 Changed 2 years ago by dfeuer

I have the feeling that typeRepKind is just too expensive, considering that it has to be called for dynApply, funResultTy, and deserialization. Just how bad would it be to expand the TrApp and TrFun constructors just enough to fit the result kind? Alternatively, would it make sense to add the kind representation to Dynamic and to the constraints on funResultTy and deserialization?

comment:5 Changed 2 years ago by bgamari

I think you need to define what your cost model is; it's not clear that anyone expects dynApply to be as cheap as a static application. The same goes for serialisation; it's going to be expensive even if you cache the kind. This is why packages like distributed-process go to some lengths to avoid serialising unnecessarily. On the other hand, packages like vault really don't care how expensive kind computation is, so optimizing for this case may be counterproductive from their perspective.

comment:6 Changed 2 years ago by dfeuer

Well no, but they probably also don't expect more than a constant overhead. My bet is that users split mostly into two groups: those who really just want a type-indexed fingerprint and those who want cheap typeRepKind.

comment:7 Changed 2 years ago by goldfire

We could, perhaps, consider a representation like I describe in comment:1:ticket:14263 for TypeRep to avoid these performance problems. Doing so would, at the least, be a nice stress test for TypeInType. :)

comment:8 Changed 2 years ago by RyanGlScott

Cc: RyanGlScott added

comment:9 Changed 2 years ago by dfeuer

Differential Rev(s): Phab:D3998Phab:D3998, Phab:D4078, Phab:D4082

I believe the simplest thing right now that will actually make deserialization linear is Phab:D4082. If at some point GHC allows unlifted types in kinds (which Richard thinks is probably not hard), then it will get even simpler and even cheaper.

Phab:D4078 implements Richard's idea of starting off by digging down to the constructor, and as a side effect reduces the number of tags needed to express deeply nested applications. But I very much doubt the complexity/benefit ratio supports that approach, unless we change the structure of TypeRep to match.

comment:10 Changed 2 years ago by simonpj

to avoid these performance problems

I would love to know what "these performance problems" actually are. The ticket description is opaque to me. Can someone offer a program that behaves badly, and an explanation of what is bad? It's hard for me to review a patch without knowing the problem that it seeks to solve.

comment:9 offers two patches. Are they alternatives? Or do we need them both? Do they solve two different problems? What are those two problems.

Finally, does this all have something to do with #14337?

Changed 2 years ago by dfeuer

Attachment: Big.hs added

Test case

comment:11 Changed 2 years ago by dfeuer

The attached test case (Big.hs) takes a third of a second to run and allocates half a gigabyte of memory. I went through several iterations of solutions, yes. The three that strike me as significant contenders at the moment are:

  1. Phab:D4082, which is a pretty simple way to make sure deserialization is never too bad. This cuts total time to 0.029s and allocation to 17.7MB.
  1. Phab:D4085, which caches TypeReps of kinds in each TrTyCon and TrApp constructor. This fixes the deserialization problem and also ensures that Data.Dynamic.dynApply is cheap. This has really been my preferred approach all along. There is some extra laziness I'd like to get rid of that is not entirely trivial to eliminate; bgamari may well know how to do so. This cuts total time to 0.023s and allocation to 15MB.
  1. Get rid of typeRepKind. This is definitely the most intrusive option, and I don't have a terribly clear sense of the consequences as yet, but I'm not sure we should dismiss it out of hand.

comment:12 Changed 2 years ago by dfeuer

One more thing: while I don't think it's a good idea, we could go with a version of Phab:D4085 that only caches kind typereps in TrTyCon constructors. That would eliminate the allocation problem and alleviate but not eliminate the time problem. The reason I favor the fully cached version is that it doesn't strike me as really that expensive to add one more pointer to a constructor that already has four words of payload (two for the Fingerprint, one for the function, and one for the argument). However, that's somewhat conditional on being able to eliminate the extra laziness. It seems there's a knot that needs tying for Type :: Type, which makes things a tad fussy.

comment:13 Changed 2 years ago by dfeuer

Differential Rev(s): Phab:D3998, Phab:D4078, Phab:D4082Phab:D3998, Phab:D4082, Phab:D4085

comment:14 Changed 2 years ago by simonpj

Re the loop, Type = TYPE Lifted. So the TypeRep for Type is a TrApp, with a cached kind. So

TYPE Lifted :: TYPE Lifted

But that kind has a cached kind:

TYPE Lifted :: TYPE Lifted :: TYPE Lifted

and if the cache field is strict you build an infinite data structure. The only way out of this I can see is to

  • define a top level definition the TypeRep for TYPE Lifted
  • in that definition, do not use mkTrApp; instead build an explicit loop
    trTYPELifted = TrApp fpr trTYPE trLifted trTYPELifted
    
    note that trTYPELifted mentions itself directly.
  • In mkTrApp spot that case, and return trTYPELifted.
Last edited 23 months ago by simonpj (previous) (diff)

comment:15 in reply to:  14 Changed 23 months ago by dfeuer

Replying to simonpj:

and if the cache field is strict you build an infinite data structure.

I don't need the cache field to be strict. I just need to force values before installing them in that field, except when constructing typeRep @Type. I think I need to know where in the solver we deal with the special case of typeRep @Type, which I think is already a special case somewhere or other.

comment:16 Changed 23 months ago by simonpj

All this is re Phab:D4085.

I don't need the cache field to be strict. I just need to force values before installing them in that field,

Right: and that happens in the "smart constructor", mkTrApp.

Doesn't the plan in comment:14 work? Just spot the special case in mkTrApp; and call mkTrApp whenever constructing a TrApp.

comment:17 Changed 22 months ago by David Feuer <David.Feuer@…>

In bc761ad/ghc:

Cache TypeRep kinds aggressively

Cache `TypeRep k` in each `TrApp` or `TrTyCon` constructor of
`TypeRep (a :: k)`. This makes `typeRepKind` cheap.

With this change, we won't need any special effort to deserialize
typereps efficiently. The downside, of course, is that we make
`TypeRep`s slightly larger.

Reviewers: austin, hvr, bgamari, simonpj

Reviewed By: bgamari, simonpj

Subscribers: carter, simonpj, rwbarton, thomie

GHC Trac Issues: #14254

Differential Revision: https://phabricator.haskell.org/D4085

comment:18 Changed 22 months ago by dfeuer

Resolution: fixed
Status: patchclosed

Fixed by bc761ad9c65c7aa62d38db39c59a6c0ae59c8ab8. We now cache the TypeRep of the kind in each TrTyCon and TrApp constructor.

Note: See TracTickets for help on using tickets.