Let's start Scheme

2016-08-29

Ephemeron and reference barrier

Recently, there's the post on SRFI-124 ML about reference barrier. The SRFI doesn't require reference-barrier procedure due to the non-trivial work to implement. Now, there's a post which shows how to implement portably, like this:
(define last-reference 0)
(define (reference-barrier x)
  (let ((y last-reference))
    (set! last-reference x)
    y))
It seems ok, but is it? The SRFI says like this:
This procedure ensures that the garbage collector does not break an ephemeron containing an unreferenced key before a certain point in a program. The program can invoke a reference barrier on the key by calling this procedure, which guarantees that even if the program does not use the key, it will be considered strongly reachable until after reference-barrier returns.
Due to the lack of knowledge and imagination, I can't imagine how it should work precisely on like this situation:
(let loop ()
  (when (some-condition)
    (reference-barrier key1)
    (reference-barrier key2)
    (do-something-with-ephemerons)
    (loop)))
Should key1 and key2 be guaranteed not to be garbage collected or only the last one (key2 in this case)? If the first case should be applied, then the proposed implementation doesn't work since it can only hold one reference. To me, it's rather rational to hold multiple reference since it's not always only one key needs to be preserved. However if you extend to hold multiple values, then how do you release the references without calling explicit release procedure? If the references would not be released, then ephemerons would also not release its keys. Thus calling reference-barrier causes eternal preservation.

Suppose this assumption is correct, then reference-barrier should work like alloca with automated push so that the pushed reference is on the location where garbage collector can see them as live objects. In this sense, allocated references are released automatically once caller of reference-barrier is returned and multiple references can be pushed. Though, it's indeed non-trivial task to implement. I hope there's no errata which says reference-barrier is *not* optional, otherwise it would be either a huge challenge or dropping the support...

4 comments:

Shiro Kawai said...

reference-barrier guarantees the argument is alive until it returns;

(let loop ()
(when (some-condition)
;; here, key1 and key2 are guaranteed to be alive
(reference-barrier key1)
;; here, key2 are guaranteed to be alive
(reference-barrier key2)
;; here, reference-barrier doens't have effect for key1 and key2
(do-something-with-ephemerons)
(loop)))

So, in this case, the effect of reference-barrier is how (some-condition) is compiled, not (do-something-with-ephemerons) part.

Probably it might be easier to understand reference-barrier to be a directive for the compiler to suppress aggressive optimization. It prevents the compile to move around certain expressions across the call of reference-barrier.

kei said...

Ah ha! That's how it should work. Then I'm still wondering if key1 and key2 should be guaranteed to be alive before some-condition or not.

1. what/where would be the condition/location to be guaranteed?
2. can it also be like (unless #f (reference-barrier key1)) or so? (this expression might be eliminated completely by compiler or should it be prevented because of reference-barrier?)

Anyway, I still think it's not trivial to implement...

Shiro Kawai said...

The only required function reference-barrier should have is to hide what it does with key from the compiler, hence the compiler cannot make assumption about key and move the expressions around. The reason "portable" one uses global variable is not because the global variable holds the reference to the key, but the fact that the effect is globally visible so that the compiler can't "cheat".

If your implementation does not do sophisticated optimizations, reference-barrier can be just as simple as an empty function. It's not trivial only if you write it portably.

(Actually, what if the compiler does whole-program analysis? Then the global variable solution may not be enough. Opening /dev/null and write the key to it, maybe?)

key1 and key2 should be alive from the point when it is bound to the last point it is referenced. Local variable reference is side-effect free so the last reference point is a pure function the compiler may move it around. reference-barrier is not pure so it "anchors" the last point of reference.

kei said...

So as long as it can be an implementation specific feature, then like this would also be fine:

(define reference-barrier
(let ((v #f))
(lambda (key)
(set! v key)
key)))

If the compiler is smart enough, then this does nothing. But some compilers (at least current Sagittarius) can be deceived.

Post a Comment