Garbage collectors

Author
Posts
Zoxc
Participant
July 18, 2015 at 1:02 am
Post count: 7
#1927 |
Are there any features targeted at garbage collectors in the Mill? I heard there were some bits.
Ivan Godard
Keymaster
July 18, 2015 at 9:09 am
Post count: 689
#1931
Yes, there are. A pointer has three bits which, in conjunction with some mask registers can be used to detect and trap on up-level references in generational or concurrent GC. The details are in the Memory talk; MillComputing.com/docs/memory.
Zoxc
Participant
July 18, 2015 at 9:17 pm
Post count: 7
#1932
I did not see any details on this in any of the talks. I may have skipped some question sections though.
Can stack barriers be made efficient on the Mill? Sometimes playing with return pointers is useful…
- Ivan Godard
  Keymaster
  July 18, 2015 at 10:11 pm
  Post count: 689
  #1933
  The Mill has separate operations for pointers, distinct from those that would be used for integral operands of the same length. There are three masks, under application control. Two are eight bits and are used by normal load and store operations; the three-bit GC field in the address indexes a bit in the mask and traps if set. For storep (store pointer), the GC bits from the address and the bits in the pointer being stored are concatenated and index a bit in a 64 bit mask, again trapping if the bit is set.
  Explicitly coded stack barriers are unnecessary on a Mill given this support; the hardware does the barrier checking. We not have measurements of the resulting gain yet, but expect it to be significant given the frequency with which GC language store pointers.
  - Zoxc
    Participant
    July 19, 2015 at 1:36 am
    Post count: 7
    #1936
    I have rarely seen GCs use tag on pointers, besides Azul Systems’ GCs (which trap based on pointers loaded), can you refer to some literature on this?
    I think you may have confused stack barriers with read/write barriers. Stack barriers causes halts if the thread returns past a point on the stack. This is used so that another thread can safely scan the earlier portion of the stack; which will reduce the time the thread has to be halted for stack scanning.
    What will the best way to do state points? My current plot is a store to a thread local byte for which can get its permission removed when the thread should be halted. This is not ideal since it would require a 1-cycle delay for the case of a function immediately calling another.
    - Ivan Godard
      Keymaster
      July 19, 2015 at 10:31 am
      Post count: 689
      #1939
      Both Azul and Mill were from-scratch hardware designs, unconstrained by prior literature. It’s interesting that we independently came up with similar solutions for GC barriers. Of course GC was critical for Azul as a Java machine, while it’s a minor feature for the more generalist Mill.
      You are right that I answered about our read/write barrier. Those barriers are the only GC-specific part of the Mill. There is no specific support for a stack barrier, and none needed; the return sequence is controlled by the spiller, and suitably privileged software can alter that sequence, including altering the return point to a trap, using the API that is intended for debuggers. We are not GC experts, but be thought that was sufficient; we may learn better when we port a GC language 🙂
    - Zoxc
      Participant
      July 21, 2015 at 9:05 am
      Post count: 7
      #1944
      There is a suspicious lack of loadp, which would correspond to Azul’s hardware barrier, is that because it’s patented?
      My new plot for statepoints is storep None, which would avoid trashing the cache, but would it trap?
Ivan Godard
Keymaster
July 21, 2015 at 2:52 pm
Post count: 689
#1945
There is no loadp. It would require checking the loaded value after it came in, which is difficult in hardware. In our conversations with GC builders they have not indicated a need for it, given what else is there. If we found we needed the ability to check then it would be an idiom, with a normal load (checked like any plain load), followed by a trap-check of the value on the belt. Such an op would be easy to define and implement.
As for storep of a None (or of normal store and a non-pointer), that’s a really good question and I had to go look at the sim code to see what it does. It’s more complicated even than a None issue, c.f. the following comment in the code:
```
                    /*  There's some question about where to do barrier
                        checking. We don't want to throw a barrier trap
                        on a store that won't actually store (because something
                        was a NaR), so it should be after we have vetted all
                        the arguments. However, we should only trap once even
                        if the store is unaligned, and should deal with the
                        possibility that the trap result is unaligned. Here
                        seems the best place. */
```
So the answer in the present sim is that we trap even if everything is a None (note that vectors can be part None), and don’t trap on a NaR because the NaR has already aborted the store.
This means that a GC can get a barrier trap on an empty store, and will just have to figure it out. It also must deal with storep with a vector of pointers, where some elements would trap and some would not.
I’m reasonably certain that this area will be rethought before it appears in hardware 🙂
Author
Posts

You must be logged in to reply to this topic.