Tagging Tags: Inferring the presence of pointer tags at compile time.
GHC utilizes tagged pointers to efficiently encode information about evaluated objects, , like a constructor’s tag or a function’s arity.
In general checking for the presence of a tag is redundant for evaluated objects, as these are usually represented by a tagged pointer. This is especially true for strict fields of constructors which can only contain pointers to evaluated objects.
However, some rare edge cases in GHC prevent guaranteeing the presence of tags for known evaluated objects, both in strict fields and otherwise. This necessitates a check for the tag at runtime; reentering an object’s closure to obtain a tag if none is present.
This is semantically safe, but negatively impacts performance. In this talk, we explain what these edge cases are, how to eliminate them and the consequences of doing so.
Early experiments reveal that changing this can have a surprisingly large performance impact; especially when strict fields are involved. Our branch (WIP) of GHC already demonstrates a speedup of 4% for the benchmark suite of the containers package overall. With many lookup/membership operations showing a speedup of 10-20%.
We will also discuss issues which cause a naive implementation to cause significant performance regressions under specific circumstances, and how these issues can be addressed using an analysis to infer ‘taggedness’ of pointers at compile time. Such an analysis has the added benefit that it allows us to infer ‘taggedness’ in certain cases even for non-strict code, further improving performance. For this purpose, we present our ‘taggedness’ analysis which is based on the STG representation of programs.
As this is work in progress we also hope for a discussion and feedback on our approach.
Fri 23 Aug
|10:30 - 10:53|
|10:53 - 11:16|
|11:16 - 11:40|
|11:40 - 12:00|