Merge Compacts into GHC

Authored by gcampax on Sep 20 2015, 9:05 PM.



Compacts are a new data structure that was illustrated at ICFP 2015.
It is an immutable NF data structure with no outgoing pointers,
which can be serialized and GCed quickly.

Simon Marlow had a preliminary review of this code during the
conference, but the code was not in a fully reviewable state
at the time. This is the cleaned up version.

Test Plan

(new test cases included)

Diff Detail

rGHC Glasgow Haskell Compiler
Automatic diff as part of commit; lint not applicable.
Automatic diff as part of commit; unit tests not applicable.
There are a very large number of changes, so older changes are hidden. Show Older Changes
gcampax added inline comments.Jan 25 2016, 11:35 AM

It was the case at some point that compact stored an Addr# instead of an a at the Haskell level (for easier serialization). This changed so I'll fix it.


Well, it only looks at the arguments, and given a pair of arguments the result is always the same, so it's a pure operation.

Furthermore, one could say it's non deterministic because it allows to observe sharing, but that's only the case for values obtained from a compactNew and compactAppend - who appropriately live in IO and where the programmer has to reason about sharing anyway. So it should be safe.

(If this explanation is acceptable I'll add it to the docs)


It's copied over to the receiving end when serializing a compact, so the receiving end can allocate the block at best as it can, and then verify if pointer adjustment is needed or not by comparing self with the actual address.
Admittely, the same data is sent over as SerializedCompact metadata, but having it there simplifies the fixup implementation significantly.


Well, the type says it's a StgCompactNFData, right?

bgamari requested changes to this revision.Jan 25 2016, 1:24 PM
bgamari edited edge metadata.

A request: Really there should be a great big note somewhere here describing how all of this hangs together.

Also, a question: how do compact regions show up in the profiler's heap census? Is this considered to be one giant heap object? If so, what do I do if I want to get a sense for what is inside?

If it is one giant heap object then perhaps we at least want to provide a way for the user to label these things with some sort of name so the user can get some visibility into their heap usage.


Perhaps this should be mentioned in a note.

90 ↗(On Diff #5615)

Also, documentation needed.

113–116 ↗(On Diff #5615)

+1 to that.

123 ↗(On Diff #5615)

Dangerous things are potentially acceptable, but they must be loudly marked as such with a description of how to use them safely.

151 ↗(On Diff #5615)

A comment explaining this would be useful.


I'm a bit unsure as well.

Also, perhaps this is obvious but why is the ghci way omitted? What would happen if the user tried to create a compact from within a GHCi session?


Around here you should include a reference to a Note where the general ideas behind the implementation of compacts is explained.


I'm afraid I don't understand the comment. What does str point to? Could you make it a bit more explicit?


I suppose this likely answers my previous question regarding profiling: compact objects will appear as a single heap object.


What does One mean?


This would probably be a good place to add a nice Note summarizing the RTS side of the implementation.


I think the suggestion wasn't necessarily to drop serialization but to instead break the introduction of this functionality out into another patch. This is a rather large diff to a rather sensitive part of the compiler. Anything we can do to break it up would be nice.


This is the sort of information that should also be found in the summarizing Note, which should be linked to from here.

gcampax added inline comments.Jan 25 2016, 10:50 PM

To be honest, I never quite understood why the tests fail under ghci. Manual testing works.

gcampax updated this revision to Diff 6437.Jan 25 2016, 10:54 PM
gcampax edited edge metadata.

Updated with more docs. Addressed review comments.

simonmar added inline comments.Jan 26 2016, 4:06 AM

The problem is that this operation returns non-zero after a compactAppend# for the given Compact# and value, but zero before. Therefore it depends on the state of the world, so it should take a State# and return one.

195–197 ↗(On Diff #5615)

That's true for lifted things, but State# is unlifted so it is never lazy. You can remove the unboxed singleton here.

bgamari requested changes to this revision.Jan 26 2016, 4:06 AM
bgamari edited edge metadata.

It would be lovely if you could mark the comments that you have addressed as "done".

Otherwise, there are a number of long lines that would be easy to fix.

Also, what do you think about splitting the fixup logic into a separate Diff (and perhaps place it in a separate source file)?

45 ↗(On Diff #6437)

Will Travis find this is it's not in the root of a repository?


It's not necessary to prefix the comment with the name of the function; we can look on the next line if we forget what we are reading ;)


I've created this component in Trac for you.


Let's make sure we don't lose track of this. When this gets merged please open a Trac ticket explaining that the tests should work and that we need to figure out why they fail. Then mark this as expect_broken with a reference to the ticket.


One small point: drop the : after Note.

Otherwise very good! Thanks for writing this down.


Ahh, I hadn't considered this. This is something that should be stated very loudly in the user documentation.


Again, drop the : (as people may be grepping for Note [Appending to a Compact]).


These long lines still need to be taken care of.


I would also argue that the fixup logic could easily be placed in a separate source file (e.g. CNFFixup.[ch]). This reduces the number of possible dependencies that the reader needs to reason about.


Please refer to the Note you wrote above here (e.g. just add See Note [Compact Normal Forms].).

This revision now requires changes to proceed.Jan 26 2016, 4:06 AM
simonmar added inline comments.Jan 26 2016, 4:10 AM

Sorry, I wasn't trying to be sarcastic, I think the tests are good.

Also what happened to fix-ups by symbol name as mentioned in the paper? This seems like a reason way to mitigate the need for static linking/disabling ASLR (although presumably at quite a cost; do you have numbers characterizing this effect?)

bgamari edited edge metadata.Jan 26 2016, 4:31 AM
bgamari updated the Trac tickets for this revision.

I have opened Trac #11493 to track progress in upstreaming this work.

Also what happened to fix-ups by symbol name as mentioned in the paper? This seems like a reason way to mitigate the need for static linking/disabling ASLR (although presumably at quite a cost; do you have numbers characterizing this effect?)

The fix-ups by symbol name was removed in one of the first iterations of the patch to reduce the size of the diff and the numbers of new features. It was ultimately dropped completely because it was not working reliably, and it had not been tested in the paper as far as I remember (it was tested in unit tests, but that wasn't sufficient I guess)

gcampax marked 45 inline comments as done.Jan 26 2016, 11:47 PM

I went through and marked as done what I fixed or will fix in the next iteration. Updated patch will be coming soon.


That's only half true.
It returns non-zero after a compactAppend# for the given Compact# and the value, but before compactAppend# you don't have the value at all, so you can't call it.
It does not depend on the state of the world, it only depends on the state of the argument.

The possible confusion comes from compactAppend# which looks like it's a mutable operation, but it's not, it creates a copy of the passed in argument, and that's the copy for which compactContains# will return true.
The fact that value is or is not in a compact never changes, and does not depend on the state of the world.

gcampax updated this revision to Diff 6465.Jan 27 2016, 1:09 AM
gcampax edited edge metadata.

Addressed more review comments

austin requested changes to this revision.Mar 25 2016, 11:49 AM
austin edited edge metadata.

(Note: I haven't looked closely at more stuff, but below is a minor complaint. This also bumps it off the review queue - we should revisit this work soon, though, so it doesn't linger on forever and ever now.)

45 ↗(On Diff #6437)

We should just delete this. There's no way Travis can do 'sub-builds' of a project AFAIK, and GHC already has its own Travis project.

If the intent is that this library get tested independently with multiple GHC versions, then it should be a submodule. But I don't think that's the case - the module code clearly deeply uses all the newly exposed machinery, so it is in practice, deeply ingrained into the exact GHC it is paired with.

TL;DR nuke.

This revision now requires changes to proceed.Mar 25 2016, 11:49 AM
erikd resigned from this revision.Mar 30 2016, 5:05 PM
erikd removed a reviewer: erikd.
gcampax updated this revision to Diff 7297.Apr 15 2016, 4:46 PM
gcampax edited edge metadata.

Removed .travis.yml

I think I addressed all previous comments (they are marked DONE or
have a response), so it would be great to have a final review.

Partial review. I'm getting there!


third argument, I think?


This doesn't need to be an unboxed singleton; just State# RealWorld would be fine.


Yes, ok.


Why might the new adjusted root address be different from the first argument? And couldn't it be obtained from the returned Compact#?


This doesn't need to be an unboxed singleton, just an Addr#.

However, it should be a State# operation, because it is non-deterministic. I'm not sure why I didn't notice this before, sorry! It looks like it shouldn't cause problems for your usage, though.


Great - could you put that in a comment?


We should track the list of imported-but-not-fixed compacts. The RTS likes to know where all the blocks are, so that it can find orphaned blocks in memInventory.


This is dubious because isCompact c x is different from isCompact c (id x). It should be an IO operation (sorry I didn't notice this before).


This also needs to be IO.

gcampax added inline comments.Apr 19 2016, 11:23 AM

The first argument is the root address in the original address space, while the return value is the root address in the new address space.
The compact might have moved (actually, is very likely to have moved, without the striped allocator patches) when imported from the other process, which means the root address is in a different position.

We cannot retrieve it from the Compact# because the root address can be anywhere in the compact: every time you append to a Compact you get a Compact with a different root address but the same Compact#

gcampax added inline comments.Apr 19 2016, 11:39 AM

Not really, because the value is forced by the bang pattern on compactContains.
But we had this conversation long enough - if I'm still not convincing you I'll make it IO.

gcampax marked 16 inline comments as done.Apr 19 2016, 12:24 PM
gcampax updated this revision to Diff 7334.Apr 20 2016, 1:11 PM
gcampax edited edge metadata.

I addressed all review comments, and I also realized that there
was no test case for serialization. We have one now (and of course
it passes)

vikraman added inline comments.Apr 20 2016, 7:11 PM

@gcampax the tests don't fail under ghci after rebasing to master.

clnx added a subscriber: clnx.Apr 24 2016, 5:26 AM
clnx removed a subscriber: clnx.
simonmar accepted this revision.Jul 18 2016, 3:33 AM
simonmar edited edge metadata.

I think the best way forwards with this is to commit it as is, and then iterate to improve it before the 8.2 release. So I'll work on making it validate (maybe it already does), and then commit it.

The biggest change I'd like to make before 8.2 is to make it possible to GC during compaction.


I don't think so. A function of type a -> Bool is an oracle for every a, but remember that the compiler is free to replace any expression by something semantically identical. Your oracle cannot return the same Bool for every semantically-identical pair of expressions, so we must conclude that it is non-deterministic and put it in IO.






say what RDMA is

@gcampax would you mind if I comandeered this diff and made the necessary changes to get it rebased and committed?

FYI, I've rebased and made a few fixes to get validate to go through, on my github branch here:

@gcampax would you mind if I comandeered this diff and made the necessary changes to get it rebased and committed?

Yes please, go ahead. I would not have commit access anyway.

This revision was automatically updated to reflect the committed changes.