RefCount_SRCFLAE: Some questions

Hoang
Erstie
Erstie
Beiträge: 11
Registriert: 6. Nov 2013 15:02

RefCount_SRCFLAE: Some questions

Beitrag von Hoang » 2. Mär 2018 23:57

Hi,

I have some questions regarding the implementation of the Reference Counting approach for memory management:

- The heap (NoGCStore, implemented in SRCFLAE.scala) has a update function which takes a location and a value as inputs. It then replaces whatever is being stored at this location with that value. => Question: If the old value does contain reference(s) to other location(s), then we have to update the values stored at those location(s) as well. But the update function does not do this update => is this incorrect or intentionally made simpler?

Code: Alles auswählen

def update(index: Int, v: Val) = {
      memory.update(index, v)
      this
    }
- The LetRec case in RefCount_SRCFLAE.scala dereferences the value stored in newLoc before update the heap at that location. Is this redundant? Because at that location a dummy NumV(0) is stored. This dummy NumV(0) will be in short replaced by NamedVal, so why must we dereference it? Ok, one can say that we have to dereference the old value before calling the update function to make use of the recursively dereference nested values functionality. But that only happens when the old value is destroyed in this dereference (it has ref count of 1 => new ref count = 0). In case this old value is not destroyed in this dereference, so there might be values stored in the heap that are orphan after the old value is replaced by a new value. So is this implementation correct at this point?

Code: Alles auswählen

 case LetRec(boundId, namedExpr, boundBody) => {
      val (newLoc,s2) = store.malloc(stack, NumV(0))
      val extStack = stack.head + (boundId -> newLoc) :: stack.tail
      val (namedVal, bodyStore) = interp(namedExpr, extStack, s2)

      // deref and enref because of overwrite in `update`
      val st = deref(bodyStore.lookup(newLoc), bodyStore)
      enref(namedVal)
      val st2 = st.update(newLoc, namedVal)
      
      interp(boundBody, extStack, st2)
    }

Ragnar
Mausschubser
Mausschubser
Beiträge: 63
Registriert: 21. Okt 2009 19:15

Re: RefCount_SRCFLAE: Some questions

Beitrag von Ragnar » 3. Mär 2018 13:01

For the first part: I am not sure what you mean by updating the values stored at some locations as well? The update function is only supposed to change the value of a single location in the store, this is not supposed to have any effect outside of that location. However, the reference counting interpreter needs to make sure to correctly call deref any value that was stored at a location that is being updated. Which brings us to the second part, the deref is exactly called because of this assumption, if update is called, deref should be called prior to the update. However, I believe you are correct, that it is redundant in this case, because the value stored at newLoc is always NumV(0), which should not be used anywhere else (because it is just a place holder).

I am not sure if I completely understand this part:
Ok, one can say that we have to dereference the old value before calling the update function to make use of the recursively dereference nested values functionality. But that only happens when the old value is destroyed in this dereference
If I understand you correctly, you ask why it is enough to call deref before update, because deref only calls destroy if the reference count reaches 0, but the update function now removes the value from the store, making it unavailable? The answer to that question is a bit tricky to understand. If deref does NOT destroy the value, then we know the value is still in use somewhere else, so any references reachable from the value need to remain valid. This is the basic contract of deref. To convince yourself that this is correct, you have to check that all the deref and enref calls balance out, which is tricky.

Antworten

Zurück zu „Archiv“