Questions about isSubType

[Eugene Burmako]

Hi all,

As per Roland's request, I looked into isSubType and how to make it
lockless.

From what I can see, the subtype check makes use of the following
mutable state: subsametypeRecursions, pendingSubTypes,
skolemizationLevel and undoLog. Looks like a dire situation, but the
good news is that in runtime reflection we have a different set of
assumptions. So probably it'll be possible to get away with it, but I
don't know yet. Now, the questions.

1) Looks like subsametypeRecusions and pendingSubTypes guard against
infinite recusion during subtyping. There's quite a number of
recursive calls in isSubType, so I can't immediately see what cases
could lead to stack overflows when unguarded. Could you please show an
example?

2) skolemizationLevel and undoLog are about TypeVars. At first I
thought that since types in runtime reflection cannot have type vars,
we're fine and we can ignore those. But then I noticed
"te2.withTypeVars" in one of the branches of isSubType, which handles
the rhs of a <:< being an existential. In a nutshell, this means that
isSubType replaces existential skolems with type vars and then tries
to infer those type vars using mutable state described above. Is that
correct?

3) There's still good news, because this subtyping check still doesn't
need undoLog. From what I understand, undoLog is used to revert
inferences made to type vars during the checks. But in runtime
reflection the only way we get type vars is when we replace skolems in
existentials with freshly generated dummies. Therefore we don't care
about rolling back, right?

4) But we have this nasty skolemizationLevel, which seems necessary
for type var inference. From the code I can see that it's incremented
every time subtyping checks recur into existentials, but I can't
exactly figure out an example. Could you please provide one?

5) Any other comments? Maybe there's some sort of a doc for the type
var business? At a glance it looks quite opaque. Suspended type vars,
untouchables, etc - a lot to absorb.

upd. When I finished writing this email, I realized that solve, called
by withTypeVars, uses lub/glb, therefore there's another piece of
global state - lubResults and glbResults. But that's the thing to
investigate for tomorrow.

Cheers,
Eugene

[Rex Kerr]

Just a note: in situations where there is a low rate of writes, you can almost always use a STM-like lock avoidance on reads.  Instead of using java.util.concurrent.locks.ReentrantReadWriteLock, you guard the relevant structures with volatile var ints; it is the job of writers to obtain a lock, increment the var before writing anything, and increment it again when it's done.  Readers just read off the vars before they start (waiting for a read lock if the var is odd, as they've entered in the middle of a write), run blindly through whatever they're going to do, and then check the var again at the end.  If it has the same value at the end, great!  You're done.  If not, do it all again until the values stay stable.

I have used this to good effect in a few places where explicit locking was too slow.  (10x or more speedup in appropriate situations.)

  --Rex

--
You received this message because you are subscribed to the Google Groups "scala-internals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-interna...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Paul Phillips]

On Sun, Feb 3, 2013 at 10:26 AM, Eugene Burmako <eugene....@epfl.ch> wrote:

1) Looks like subsametypeRecusions and pendingSubTypes guard against
infinite recusion during subtyping. There's quite a number of
recursive calls in isSubType, so I can't immediately see what cases
could lead to stack overflows when unguarded. Could you please show an
example?

It should arise with f-bounds, something like A[T] expanding to A[A[A[A[A...]]]] while trying to instantiate T. I don't have an example at the ready. See SI-2251 for possible inspiration.

4) But we have this nasty skolemizationLevel, which seems necessary
for type var inference. From the code I can see that it's incremented
every time subtyping checks recur into existentials, but I can't
exactly figure out an example. Could you please provide one?

It should arise with gadt-style pattern matching. Make a polymorphic method which performs a pattern match and has case bodies which recurse on the method. The skolemization level goes up on each recursion - at least that's how I remember it.

 

5) Any other comments? Maybe there's some sort of a doc for the type
var business? At a glance it looks quite opaque. Suspended type vars,
untouchables, etc - a lot to absorb.

No offense to any of its authors, but it would be the crime of the century to be piling more code on top of this code. You should not be trying to understand it (that is, you should not be trying to follow its mutation path.) You should be trying - in fact, I would say you must - eliminate it.

There is zero chance of ever having threadsafe reflection if it is trying to navigate these waters. None of the mutation and undoing is necessary. Solving a set of type constraints should be a call to an immutable, threadsafe component with no exposed mutation.

[Adriaan Moors]

I agree mutation should be avoided.

However, retro-fitting context-tracking (the only alternative I cant think of) into methods like isSubtype (and all its callers) is no easy feat.

On the mutation front, there's also undoLog and restoreTypeBounds to look out for.

[Paul Phillips]

On Sun, Feb 3, 2013 at 6:28 PM, Adriaan Moors <adriaa...@typesafe.com> wrote:

I agree mutation should be avoided.

However, retro-fitting context-tracking (the only alternative I cant think of) into methods like isSubtype (and all its callers) is no easy feat.

Thinking small!

Let's take a method like isSubType. This has an obvious signature.

  (Type, Type) => Boolean

Types are immutable, there is an answer for any pairs of types, and that answer never changes. You don't need to know anything else.

So those are lies, okay, but only because we have made them into lies. We have all these things which are sort of like types running around and pretending to be types. They pervert the whole process, turning what ought to be a referentially transparent question-and-answer into a carnival ride.

Pretend for a moment you aren't constrained by the current compiler.

You have inputs.

You have ouputs.

f(inputs) = outputs.

If you need to accumulate constraints, one of your outputs is the accumulated constraints.

If subtyping depends on the context, one of your inputs is the context, and the context is immutable.

If there are cycles, then use standard cycle recognition/avoidance techniques.

If the answer depends on some unavailable result, then produce T => Boolean instead of Boolean.

We don't have to live like we do.

"... is no easy feat."

I can promise you this: we are not smart enough or skilled enough to retrofit thread safety onto the compiler, especially not in "react to the threading bugs as they are reported" fashion, or where the scope of thread-safety concern somehow grew all the way from non-consideration to trying to harden typevars and the undoLog. Let's not pile up the bodies too deeply before it is recognized: this cannot be done. If only it were so easy as "no easy feat!" It is literally impossible.

We must have an internal model about which we can reason, deterministic execution, reproducibility from start to finish. Every day we deny it is another lost day.

[Paolo G. Giarrusso]

Il giorno lunedì 4 febbraio 2013 03:28:10 UTC+1, Adriaan Moors ha scritto:

I agree mutation should be avoided.

However, retro-fitting context-tracking (the only alternative I cant think of) into methods like isSubtype (and all its callers) is no easy feat.

You mean threading an extra parameter through all callers?

Then what about thread-locals, at least as a short/medium-term solution? From the description, skolemizationLevel, subsametypeRecusions and pendingSubTypes are completely independent among threads (since they guard against infinite recursion), so thread-locals seem quite appropriate. And the performance impact should be negligible.

And that's a very simple fix:

-var v: T = ...

+private val vTLS: ThreadLocal[T] = ...

+def v = vTLS.get()

+def v_=(newV: T) = vTLS.set(newV)

See below for an adaptation of ThreadLocal for Scala which would be convenient here.

Of course, it won't be optimal for all cases (you probably don't want that for lazily loaded caches, for instance - assuming you want to share work between threads).

For these caches:

  private val lubResults = new mutable.HashMap[(Int, List[Type]), Type]

  private val glbResults = new mutable.HashMap[(Int, List[Type]), Type]

you could just use Java's ConcurrentHashMap or Cliff Click's NonBlockingHashMap, which IIRC uses advanced forms of the scheme Rex Kerr described.

The annoying part is that on a cache miss, you could get two threads computing the result. But you can solve that if the first thread to get there places a Promise which it'll satisfy itself (http://code.google.com/p/concurrentlinkedhashmap/wiki/SelfPopulatingCache; I've implemented a similar idea before in Java with good results).

ThreadLocal for Scala:

class ScalaThreadLocal[T](v: => T) extends ThreadLocal[T] {

  override def initialValue() = v

  def modify(f: T => T) {

    set(f(get()))

  }

  def withValue[U](tempV: T)(toCompute: => U) = {

    val old = get()

    set(tempV)

    val res = toCompute

    set(old)

    res

  }

}

[Eugene Burmako]

I like the ThreadLocal idea. We could even introduce it only in runtime reflection by overridding corresponding getters and setters, which will be, as before, wired to an underlying var in compile-time universes.

The only question is how we make sure that compiler's performance isn't hurt by this change? Greg, since you were the last who worked on compiler's performance, maybe you could comment here?

Paul, I did hear your concerns. I'm definitely not interested in complicating subtyping even more. If no easy workarounds fit, I'll probably have to admit that the fix for lock performance has to wait.

[Paolo Giarrusso]

On Mon, Feb 4, 2013 at 8:14 AM, Eugene Burmako <eugene....@epfl.ch> wrote:
> I like the ThreadLocal idea. We could even introduce it only in runtime
> reflection by overridding corresponding getters and setters, which will be,
> as before, wired to an underlying var in compile-time universes.

That's a good idea. This way the compiler would not be affected, right?

> The only question is how we make sure that compiler's performance isn't hurt
> by this change? Greg, since you were the last who worked on compiler's
> performance, maybe you could comment here?

I have to retract a bit on the performance impact, it's not so
negligible, though still probably OK for reflection.

On a JVM a ThreadLocal read is an unsynchronized hashmap read, so
10-20x slower than a heap read, as measured by Aleksandar Prokopec
[1]. Since isSubType itself is a hotspot (though those variables might
not be), better keep this to runtime reflection as you suggested.

The impact on a JVM is bigger than I thought, because of an (IMHO)
suboptimal implementation (compared to what native applications do,
where a TLS read is still just one instruction -
http://stackoverflow.com/a/2459752/53974).

[1] "Summary: A thread local is around 10-20x that of the heap read.
It also seems to scale well on this JVM implementation [Sun Java 1.6]
and these architectures with the number of processors."
[http://stackoverflow.com/a/4756605/53974]

Paolo G. Giarrusso - Ph.D. Student, Philipps-University Marburg
http://www.informatik.uni-marburg.de/~pgiarrusso/

[Eugene Burmako]

At first I though that the compiler will be affected, because that'd require introducing non-final getters and setters. But currently those vars are non-private anyway, so probably the end result will be the same (minus the possible JIT magic that might be applied when JVM detects that we're not overriding those vars anywhere). 

[martin odersky]

Yes, go thread-local for reflection only is the right way IMO.

To understand some of the complexities involved with subtyping a must-read is:

On Decidability of Nominal Subtyping with Variance

by Benjamin Pierce and Andrew Kennedy.

http://repository.upenn.edu/cis_papers/671/

In the paper they demonstrate that C#, Java and original Scala all have subtype algorithms that loop or stackoverflow. After that paper appeared, Scala's algorithm was modified to avoid the infinite recursion. To do this we needed to add a global well-formedness check on the allowable subtype hierarchies in Namers (forgot what it was called), and also needed to track pending subtype requests. The pendingSubtypes chain is a direct reflection of that. The subtypeRecursions counter is an optimization, to avoid constructing the costly pendingSubtypes log until an unusually deep recursion depth has been reached. The rest of the mutable state deals with type variables, which, as you have noted, get introduced by existentials. Replacing these by constraints is an interesting alternative, which we should try out. I have currently no good intuition on the performance impact of doing this, so it's all up to experimentation.

Cheers

 - Martin

Martin Odersky
Prof., EPFL and Chairman, Typesafe
PSED, 1015 Lausanne, Switzerland
Tel. EPFL: +41 21 693 6863
Tel. Typesafe: +41 21 691 4967

[Mark Harrah]

On Sun, 3 Feb 2013 23:03:30 -0800 (PST)

"Paolo G. Giarrusso" <p.gia...@gmail.com> wrote:

> Il giorno lunedì 4 febbraio 2013 03:28:10 UTC+1, Adriaan Moors ha scritto:
>
> > I agree mutation should be avoided.
> > However, retro-fitting context-tracking (the only alternative I cant think
> > of) into methods like isSubtype (and all its callers) is no easy feat.
> >
>
> You mean threading an extra parameter through all callers?
>
> Then what about thread-locals, at least as a short/medium-term solution?
> From the description, skolemizationLevel, subsametypeRecusions and
> pendingSubTypes are completely independent among threads (since they guard
> against infinite recursion), so thread-locals seem quite appropriate. And
> the performance impact should be negligible.
>
> And that's a very simple fix:
>
> -var v: T = ...
> +private val vTLS: ThreadLocal[T] = ...
> +def v = vTLS.get()
> +def v_=(newV: T) = vTLS.set(newV)

To avoid classloader leaks, don't set an initial value on ThreadLocals and only expose these operations:

def get: Option[S]
def withValue[S](v: T)(f: => S): S = {
val old = local.get()
local.set(v)
try f finally local.set(old)
}

-Mark

> > On Sun, Feb 3, 2013 at 10:58 AM, Paul Phillips <pa...@improving.org<javascript:>
> > > wrote:
> >
> >>
> >> On Sun, Feb 3, 2013 at 10:26 AM, Eugene Burmako <eugene....@epfl.ch<javascript:>

> >> email to scala-interna...@googlegroups.com <javascript:>.

[√iktor Ҡlang]

On Mon, Feb 4, 2013 at 2:05 PM, Mark Harrah <dmha...@gmail.com> wrote:

On Sun, 3 Feb 2013 23:03:30 -0800 (PST)

"Paolo G. Giarrusso" <p.gia...@gmail.com> wrote:

> Il giorno lunedì 4 febbraio 2013 03:28:10 UTC+1, Adriaan Moors ha scritto:
>
> > I agree mutation should be avoided.
> > However, retro-fitting context-tracking (the only alternative I cant think
> > of) into methods like isSubtype (and all its callers) is no easy feat.
> >
>
> You mean threading an extra parameter through all callers?
>
> Then what about thread-locals, at least as a short/medium-term solution?
> From the description, skolemizationLevel, subsametypeRecusions and
> pendingSubTypes are completely independent among threads (since they guard
> against infinite recursion), so thread-locals seem quite appropriate. And
> the performance impact should be negligible.
>
> And that's a very simple fix:
>
> -var v: T = ...
> +private val vTLS: ThreadLocal[T] = ...
> +def v = vTLS.get()
> +def v_=(newV: T) = vTLS.set(newV)

To avoid classloader leaks, don't set an initial value on ThreadLocals

+1!

 

and only expose these operations:

def get: Option[S]
def withValue[S](v: T)(f: => S): S = {
  val old = local.get()
  local.set(v)
  try f finally local.set(old)
}

… or reuse grand-dads wheel: http://www.scala-lang.org/api/current/index.html#scala.util.DynamicVariable

Cheers,

√

--

Viktor Klang
Director of Engineering

Typesafe - The software stack for applications that scale
Twitter: @viktorklang

[Mark Harrah]

Yes. However, I'd rather see one used that doesn't allow an initial value and doesn't expose 'set'.

-Mark

> *Viktor Klang*
> *Director of Engineering*
> *
> *
> Typesafe <http://www.typesafe.com/> - The software stack for applications
> that scale
> Twitter: @viktorklang
>

[√iktor Ҡlang]

Yep, well, there's always the option of deprecation.

--

Viktor Klang
Director of Engineering

Typesafe - The software stack for applications that scale
Twitter: @viktorklang

[Eugene Burmako]

How would you rewrite something like [1] to be correct?

We don't have the luxury of imposing only get and withValue on the clients. Tons of pre-existing code in the compiler need getters and setters. Maybe I'm misunderstanding something, though.

[1] https://github.com/scalamacros/kepler/blob/650f1feae15753cfde5f6ecd95b546c4f356684e/src/reflect/scala/reflect/runtime/SynchronizedTypes.scala#L43

[Paolo Giarrusso]

Other approaches seem possible, though they are somewhat annoying
(http://stackoverflow.com/a/11826736/53974).

To recap the problem: the ThreadLocal, by default, will outlive the
compiler run and keep a reference to the value, its implementing class
and classloader; having a subclass of ThreadLocal makes things worse
because the variable itself keeps around the classloader. So it won't
be GCed even when it should, for instance because a new version of the
application is loaded with a new classloader, and the old one is
supposed to disappear.

So you can either use the interface that Mark proposes, just for
runtime reflection, or remove the variable when done with it in a
finally block - not something we can easily ask the user to do, so we
should do it ourselves. Is there a single entry path to typechecking
where this could be done? The slow path of isSubtype is such a
location, but the overhead might still be too big.

If that doesn't work, we might want to give up ThreadLocals.

Potentially, you can have a ThreadLocal[WeakReference[MutableBox[T]]]
and ensure that your instance keeps a strong reference to each
MutableBox. These references must be set in a threadsafe structure:
MutableBox allows to set that reference only at the first access and
never update it again. The ThreadLocal would allow "fast"
unsynchronized access. It's not clear whether this is worth it.

But instead of all that, given that ThreadLocals use a map anyway, it
might be faster to map variable ID and thread ID to value with a
Click's NonBlockingHashMap (either one for variable, from thread IDs
to values, or a global one using both keys). The cost there, in the
best/average case, is a volatile operation, which IIRC is equivalent
to a cache miss.

On Wed, Feb 6, 2013 at 5:33 PM, Eugene Burmako <eugene....@epfl.ch> wrote:
> How would you rewrite something like [1] to be correct?
>
> We don't have the luxury of imposing only get and withValue on the clients.
> Tons of pre-existing code in the compiler need getters and setters.

Is that code in scala-reflect? All of this is only needed for runtime
reflection, so the compiler and macros could have access to a more
extensive interface (with a non-ThreadLocal-based implementation, as
discussed).

[√iktor Ҡlang]

How about creating the TL, then using "set" with the value. (of course you'll also have to make sure you null it out "at the end".

Cheers,

√

On Wed, Feb 6, 2013 at 5:33 PM, Eugene Burmako <eugene....@epfl.ch> wrote:

--

Viktor Klang
Director of Engineering

Typesafe - The software stack for applications that scale
Twitter: @viktorklang

[Eugene Burmako]

Thanks for the detailed explanation. Now it looks like I understand
the problem. Luckily, all our stuff comes from scala-library.jar and
scala-reflect.jar, so we're only going to prevent the classloader that
works with those from being collected. Is that such big of a problem?

As for API, a big chunk of code in scala-reflect is shared between
reflection and the compiler, so we need a uniform API for those
things.

If we do "set" with the value, how do we make sure that we use that
value (or a closure producing that value) for all threads: present
ones and future ones?

Also, we can't null the value out at the end, because runtime
reflection doesn't have an end. It stems from the same reason that
leads to memory leaks - unlike the compiler, we don't have runs.
scala.reflect.runtime.universe is supposed to be usable from the very
start and till the very end of the application life.

> On Wed, Feb 6, 2013 at 5:33 PM, Eugene Burmako <eugene.burm...@epfl.ch> wrote:
> > How would you rewrite something like [1] to be correct?
>
> > We don't have the luxury of imposing only get and withValue on the clients.
> > Tons of pre-existing code in the compiler need getters and setters.
>
> Is that code in scala-reflect? All of this is only needed for runtime
> reflection, so the compiler and macros could have access to a more
> extensive interface (with a non-ThreadLocal-based implementation, as
> discussed).
>
>
>
>
>
>
>
> > Maybe
> > I'm misunderstanding something, though.
>
> > [1]

> >https://github.com/scalamacros/kepler/blob/650f1feae15753cfde5f6ecd95...

>
> > On 4 February 2013 15:18, Mark Harrah <dmhar...@gmail.com> wrote:
>
> >> On Mon, 4 Feb 2013 14:10:32 +0100

> >> √iktor Ҡlang <viktor.kl...@gmail.com> wrote:

>
> >> > On Mon, Feb 4, 2013 at 2:05 PM, Mark Harrah <dmhar...@gmail.com> wrote:
>
> >> > > On Sun, 3 Feb 2013 23:03:30 -0800 (PST)

> >> > > "Paolo G. Giarrusso" <p.giarru...@gmail.com> wrote:

[Eugene Burmako]

Mark, would be great if you could comment today. Would scalalib and
scalareflect classloader leak be a problem for SBT? To be honest, I
still have a desire to merge he threadlocal-based implementation into
2.10.1 to help Roland, so it'd be great if we could reach the
consensus before the weekend.

[Roland Kuhn]

Hi Eugene,

as far as I can see there are two kinds of variables involved in supporting runtime reflection

– depth counters like skolemizationLevel
– caches

The first kind starts out at zero for each new call into isSubType and friends, correct? In this case it is easy: do not set an initialValue on the TL and have the getter implicitly set it to 0 if it is null; then just before returning from isSubType reset it to null (or zero where appropriate).

The second kind is not yet clear to me: if these mutable.HashMaps are supposed to be shared somehow between threads, then putting them into ThreadLocals is not the right thing to do. Is this what you mean below with “how do we make sure that we use that value (or a closure producing that value) for all threads: present ones and future ones?” ThreadLocals give you one map per thread in this case. If the algorithm can run with that (i.e. upon entering isSubType the map is always empty) then do the same thing as for the depth counters. If that means that we’re doing some part of the calculation repeatedly then it is a matter of expectation management. I could well imagine caching these isSubType results within the actor if that gives me perfect scalability (due to no synchronization), depending on how large the memory footprint is and how long the calculations take in practice.

But the initialValue problem can be solved as outlined without subclassing ThreadLocal and leaking ClassLoaders.

Thanks for all your efforts spent on this, Eugene!


Roland

> --
> You received this message because you are subscribed to the Google Groups "scala-internals" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to scala-interna...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>

Dr. Roland Kuhn
Akka Tech Lead
Typesafe – Empowering professional developers to build amazing apps.
twitter: @rolandkuhn

[√iktor Ҡlang]

On Thu, Feb 7, 2013 at 8:38 AM, Eugene Burmako <eugene....@epfl.ch> wrote:

Thanks for the detailed explanation. Now it looks like I understand
the problem. Luckily, all our stuff comes from scala-library.jar and
scala-reflect.jar, so we're only going to prevent the classloader that
works with those from being collected. Is that such big of a problem?

As for API, a big chunk of code in scala-reflect is shared between
reflection and the compiler, so we need a uniform API for those
things.

If we do "set" with the value, how do we make sure that we use that
value (or a closure producing that value) for all threads: present
ones and future ones?

Also, we can't null the value out at the end, because runtime
reflection doesn't have an end. It stems from the same reason that
leads to memory leaks - unlike the compiler, we don't have runs.
scala.reflect.runtime.universe is supposed to be usable from the very
start and till the very end of the application life.

Hanging onto scala-reflect.jar will probably also retain scala-library.jar, and leaking that much memory will severely hamper usability in app servers.

I think we need to find alternative solutions.

Cheers,

√

 

--
You received this message because you are subscribed to the Google Groups "scala-internals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-interna...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

--

Viktor Klang
Director of Engineering

Typesafe - The software stack for applications that scale
Twitter: @viktorklang

[Eugene Burmako]

I don't think it's that easy. How do you tell apart an entry-point call to isSubType and a recursive call? Both skolemizationLevel and, say, lubResults are supposed to be shared across the entire tree of calls. mutable.HashMaps aren't supposed to be shared between threads, so we're fine here.

[Eugene Burmako]

I see. Will do that.

[Eugene Burmako]

Okay what do you think of [1]?

[1] https://github.com/scalamacros/kepler/commit/fa52abdbe7f0c7a5d37b718a8bf0a8d09b0cc211#L1R42

On Feb 7, 4:17 pm, Eugene Burmako <eugene.burm...@epfl.ch> wrote:
> I see. Will do that.
>

> On 7 February 2013 13:28, √iktor Ҡlang <viktor.kl...@gmail.com> wrote:

> >> For more options, visithttps://groups.google.com/groups/opt_out.

>
> > --
> > *Viktor Klang*
> > *Director of Engineering*
> > *
> > *

> > Typesafe <http://www.typesafe.com/> - The software stack for applications

[Eugene Burmako]

Another attempt :)

https://github.com/scalamacros/kepler/blob/a1517ac5929ec58aae71cb3ad91af2f7157625da/src/reflect/scala/reflect/runtime/Tls.scala

[Paul Phillips]

On Thu, Feb 7, 2013 at 7:17 AM, Eugene Burmako <eugene....@epfl.ch> wrote:

I don't think it's that easy. How do you tell apart an entry-point call to isSubType and a recursive call?

It depends on what you're counting as a recursive call, but for a given call to isSubType, all the recursive calls have a "depth" parameter. That's why there are two signatures.

  def isSubType(tp1: Type, tp2: Type): Boolean

  def isSubType(tp1: Type, tp2: Type, depth: Int): Boolean

> Both skolemizationLevel and, say, lubResults are supposed to be shared across the entire tree of calls

Well, lubResults is. What do you mean by the entire tree of calls? Isn't the multi-threaded aspect of all this that say two unrelated type tags might be being resolved at the same time, and by extension, there might be two independent subtype tests and two skolemization levels? Within a single thread it's more of a "stack" of calls.

Also, I just noticed in an earlier message you said "From the description, skolemizationLevel, subsametypeRecusions and pendingSubTypes are completely independent among threads (since they guard against infinite recursion)" but skolemizationLevel is not a recursion guard. (The other two are.) It is for correctness: you can't use a typevar solution if it involves types at a higher skolemization level than the typevar started at.

[√iktor Ҡlang]

On Thu, Feb 7, 2013 at 5:46 PM, Eugene Burmako <eugene....@epfl.ch> wrote:

Another attempt :)

https://github.com/scalamacros/kepler/blob/a1517ac5929ec58aae71cb3ad91af2f7157625da/src/reflect/scala/reflect/runtime/Tls.scala

What's the rationale behind this solution?

Cheers,

√

--

Viktor Klang
Director of Engineering

Typesafe - The software stack for applications that scale
Twitter: @viktorklang

[Eugene Burmako]

Providing the required thread-local semantics for selected parts of the global state, not leaking classloaders, because results of calls to mkTls are now rooted in the enclosing universe and will be garbage collected together with it.

[√iktor Ҡlang]

But you aren't ever removing any values from it.

[Eugene Burmako]

Because I cannot. Runtime reflection doesn't know when it should shut down. Do you think that's going to be a problem?

[√iktor Ҡlang]

On Thu, Feb 7, 2013 at 7:19 PM, Eugene Burmako <eugene....@epfl.ch> wrote:

Because I cannot. Runtime reflection doesn't know when it should shut down. Do you think that's going to be a problem?

I would be surprised if it is't going to be a problem.

[Paul Phillips]

It can time itself out, right?

--

Viktor Klang
Director of Engineering

Typesafe - The software stack for applications that scale
Twitter: @viktorklang

[√iktor Ҡlang]

On Thu, Feb 7, 2013 at 7:49 PM, Paul Phillips <pa...@improving.org> wrote:

It can time itself out, right?

In what sense?

[Rex Kerr]

If you're doing this for performance, you shouldn't seek through the map more often than needed:

    val v = values.get(currentThread)
    if (v.asInstanceOf[AnyRef] == null) { ... }
    else v

Also, the way you've done it now will leak nulls if at any point in the future someone changes it to remove keys (if the removal is done after the test and before the get).  The way above is safe.

  --Rex

[√iktor Ҡlang]

On Thu, Feb 7, 2013 at 8:04 PM, Rex Kerr <ich...@gmail.com> wrote:

If you're doing this for performance, you shouldn't seek through the map more often than needed:

    val v = values.get(currentThread)
    if (v.asInstanceOf[AnyRef] == null) { ... }
    else v

Also, the way you've done it now will leak nulls if at any point in the future someone changes it to remove keys (if the removal is done after the test and before the get).  The way above is safe.

I'd also rather have ConcurrentHashMap[Long, T] and use Thread.currentThread.getId as the key, at least then Threads won't be hard-referenced in the map,

but this solutions still has the problem that long-running highly concurrent programs will accumulate garbage in this map. (think Akka)

--

Viktor Klang
Director of Engineering

Typesafe - The software stack for applications that scale
Twitter: @viktorklang

[Paul Phillips]

You'll have to make it multiple choice, because I only know one thing that could mean, at least in this context. 

[√iktor Ҡlang]

On Thu, Feb 7, 2013 at 8:18 PM, Paul Phillips <pa...@improving.org> wrote:

You'll have to make it multiple choice, because I only know one thing that could mean, at least in this context. 

Your context is clearly more elaborate/larger than mine, so please outline how that'd work and I'll chime in.

[Paul Phillips]

On Thursday, February 7, 2013, √iktor Ҡlang wrote:

Your context is clearly more elaborate/larger than mine, so please outline how that'd work and I'll chime in.

I think you are going to out-elaborate me by a lot here.

Eugene: "Runtime reflection doesn't know when it should shut down."

alarm(N seconds from last use of runtime reflection) { "Hey runtime reflection! Shut down." }

[√iktor Ҡlang]

Oh, I ruled that out since it needs some sort of timer thread running and updating some shared memory location with every reflection access..

 

--
You received this message because you are subscribed to the Google Groups "scala-internals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-interna...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Paul Phillips]

On Thursday, February 7, 2013, √iktor Ҡlang wrote:

Oh, I ruled that out since it needs some sort of timer thread running and updating some shared memory location with every reflection access..

Your understanding of the overhead is going to dominate mine, but I'd be pretty surprised if there's no way to do this with negligible overhead, unless the very existence of a timer thread is unacceptable overhead. Since timing accuracy is not particularly important, it must be possible to reduce the degree of sharing and/or frequency of update. But I freely admit this is your territory, so if it's best ruled out then rule it out.

[√iktor Ҡlang]

But the question is, when would you shut that thread down? And that Thread has a reference to reflection...

(Reservations for it being late here and I don't have the full picture of scala-reflect)

Cheers,

√

 

--
You received this message because you are subscribed to the Google Groups "scala-internals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-interna...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Rex Kerr]

If you want to clear the whole thing, you can just update a volatile var in addition to whatever it is that you're actually doing.  That will slow things down a little, but a small fraction of what's already being spent.  Then the watching thread pings that variable every second or whatever, and if it sees the values not changing for enough time, it sends the clear command to the hash map (if you want the whole thing cleared).  Overhead is close to zero for the thread that checks.

Partial clearing is slightly more fiddly.  You need to store the volatile var in a wrapper for the mapped value, and then have a second entry that the watcher thread updates as the previous value.  Then you need to figure out how to scan little enough (probably with an enumerator).

  --Rex

--

[Paul Phillips]

On Thu, Feb 7, 2013 at 12:03 PM, √iktor Ҡlang <viktor...@gmail.com> wrote:

But the question is, when would you shut that thread down? And that Thread has a reference to reflection...

That's the point, it shuts itself down. That is its only purpose. Reflection would start it again if it were loaded again.

[√iktor Ҡlang]

But now we have introduced a race between shutdown and startup. I'm not saying it's unsolvable, but it's enough complexity to warrant other possible solutions to be explored.

 

--
You received this message because you are subscribed to the Google Groups "scala-internals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-interna...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Rex Kerr]

On Thu, Feb 7, 2013 at 3:25 PM, √iktor Ҡlang <viktor...@gmail.com> wrote:

On Thu, Feb 7, 2013 at 9:16 PM, Paul Phillips <pa...@improving.org> wrote:

On Thu, Feb 7, 2013 at 12:03 PM, √iktor Ҡlang <viktor...@gmail.com> wrote:

But the question is, when would you shut that thread down? And that Thread has a reference to reflection...

That's the point, it shuts itself down. That is its only purpose. Reflection would start it again if it were loaded again.

But now we have introduced a race between shutdown and startup. I'm not saying it's unsolvable, but it's enough complexity to warrant other possible solutions to be explored.

@volatile var threadWatcher = ...

class ThreadWatcher {
  ...
    if (threadWatcher ne this)  shutdown()
  ...
}


  --Rex
 

[√iktor Ҡlang]

On Thu, Feb 7, 2013 at 9:32 PM, Rex Kerr <ich...@gmail.com> wrote:

On Thu, Feb 7, 2013 at 3:25 PM, √iktor Ҡlang <viktor...@gmail.com> wrote:

On Thu, Feb 7, 2013 at 9:16 PM, Paul Phillips <pa...@improving.org> wrote:

On Thu, Feb 7, 2013 at 12:03 PM, √iktor Ҡlang <viktor...@gmail.com> wrote:

But the question is, when would you shut that thread down? And that Thread has a reference to reflection...

That's the point, it shuts itself down. That is its only purpose. Reflection would start it again if it were loaded again.

But now we have introduced a race between shutdown and startup. I'm not saying it's unsolvable, but it's enough complexity to warrant other possible solutions to be explored.

@volatile var threadWatcher = ...

class ThreadWatcher {
  ...
    if (threadWatcher ne this)  shutdown()
  ...
}

Please post the complete sources, it's hard to discuss correctness of coordination without the full picture.

 

  --Rex
 

 

--
You received this message because you are subscribed to the Google Groups "scala-internals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-interna...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

--

Viktor Klang
Director of Engineering

Typesafe - The software stack for applications that scale
Twitter: @viktorklang

--

You received this message because you are subscribed to the Google Groups "scala-internals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-interna...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

--
You received this message because you are subscribed to the Google Groups "scala-internals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-interna...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Rex Kerr]

On Thu, Feb 7, 2013 at 3:41 PM, √iktor Ҡlang <viktor...@gmail.com> wrote:

On Thu, Feb 7, 2013 at 9:32 PM, Rex Kerr <ich...@gmail.com> wrote:

On Thu, Feb 7, 2013 at 3:25 PM, √iktor Ҡlang <viktor...@gmail.com> wrote:

On Thu, Feb 7, 2013 at 9:16 PM, Paul Phillips <pa...@improving.org> wrote:

On Thu, Feb 7, 2013 at 12:03 PM, √iktor Ҡlang <viktor...@gmail.com> wrote:

But the question is, when would you shut that thread down? And that Thread has a reference to reflection...

That's the point, it shuts itself down. That is its only purpose. Reflection would start it again if it were loaded again.

But now we have introduced a race between shutdown and startup. I'm not saying it's unsolvable, but it's enough complexity to warrant other possible solutions to be explored.

@volatile var threadWatcher = ...

class ThreadWatcher {
  ...
    if (threadWatcher ne this)  shutdown()
  ...
}

Please post the complete sources, it's hard to discuss correctness of coordination without the full picture.

 

I don't have complete sources since I'm making it up as I go, but I can describe more about what I thought.

Every time you call reflection (in Eugene's Tls class) and have to add something to a hash map you also

  if (threadWatcher eq null) threadWatcher = new ThreadWatcher

and if a dozen of these get created at the same time you don't care because the ThreadWatcher just shuts itself down if it doesn't find itself as the privileged one who sits in the var.  I'm not sure what shutdown() needs to do--probably nothing, just leave the run() method.

When a live watcher decides it's been too long, it sets threadWatcher to null and stops itself.

  --Rex

[√iktor Ҡlang]

WARNING: UNCOMPILED CODE AND IT'S PAST MIDNIGHT. HERE MIGHT BE DRAGONS

class ReaperThread(data: ConcurrentHashMap[_, _], reapingTime: Duration, reaperFlag: AtomicBoolean, count: AtomicLong) extends Thread {

@tailrec final def run: Unit = {

 val countAtStart = count.get

 Thread.sleep(reapingTime.toMillis)

 if (countAtStart == count.get) {

   //WARNING There is a race here between a silent period and someone accessing things again

        data.clear() // HARDCORE REAPING ACTION

        val allGud = reaperFlag.getAndSet(false)

        assert(allGud, "Something is broken in ur codez")

        // there is a race between the reaper exiting and a new reaper required,

        // but since counter.incrementAndGet HAPPENS BEFORE the reaper CAS, we make sure that either this reaper survives or another one was created

        if (countAtStart != count.get && reaper.compareAndSet(false, true)) run

        else ()

 } else run

}

}

val reaper = new AtomicBoolean(false)

val count = new AtomicLong(0)

val data = new ConcurrentHashMap[Long, T]

//On every access

{

    count.incrementAndGet() // must be done before the reaper check below

if (reaper.get == false && reaper.compareAndSet(false, true)) // CCAS to avoid LOCK CMPXCHG in the normal execution path

 new ReaperThread(data, 5 seconds, reaper, count).start()

}

In any case, this is not a path I think we should take.

Cheers,

√

 

  --Rex

--
You received this message because you are subscribed to the Google Groups "scala-internals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-interna...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Paolo Giarrusso]

What about making the maps concurrent weak hashmaps (as supported by
Google's Guava [1])? If Thread instances for dead threads are GC-ed
normally (an exception would not be surprising, but Googling doesn't
show anything), corresponding entries would disappear.

[1] http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/cache/CacheBuilder.html
A discussion of alternatives appears here, but CacheBuilder is the
only fitting one here I think:
http://stackoverflow.com/questions/264582/is-there-a-softhashmap-in-java

If that does not work and you want to remove old entries, Guava also
implements removal for stale entries after a timeout (I used it, works
quite well). It does start an extra timer thread on its own (through
java.util.Timer - but it's shared with other clients), which makes it
not really self-contained - but at least it's an existing supported
solution. I remember Josh's concerns over Google's OpenSource effort —
apparently, Google developers provide limited support for external
users — but I still think this solution is quite good.

Eugene: Unrelated to this correctness issue, the zero-initialized
counters could use plain ThreadLocals without needing to override
initialValue(). This is just an optimization, but possibly a
significant one: the overhead of ConcurrentHashMap is likely more
significant for integers.
Also, to avoid classloader leaks, one should ensure that integers are
boxed using Java wrappers and not Scala ones (I think this is already
fine).

Paolo G. Giarrusso - Ph.D. Student, Philipps-University Marburg
http://www.informatik.uni-marburg.de/~pgiarrusso/

[Jan Vanek]

Hi Eugene and co.,

would it be possible to make a piece of cake semi-detachable? Let's say
we have trait TypesApi, and TypesImpl extends TypesApi. The compiler
mixes the TypesImpl directly into its universe (or its extension of
TypesImpl). In the reflection there is another implementation
DelegateToLocalTypesImpl, which looks like:

trait DelegateToLocalTypesImpl extends TypesApi {
private val tl = new ThreadLocal[TypesImpl]

// and every method like
def foo(p: String) = withLocalTypes(_.foo(p))

@inline private withLocalTypes[T](body: TypesImpl => T): T = tl.match {
case null =>
val types = createTypesImpl
tl.set(types)
try body(types)
finally tl.set(null)
case types =>
body(types)
}

private def createTypesImpl: TypesImpl = new instance of class
derived from TypesImpl (and dragons)
}

The TypesImpl might have couple of field members, which might not be
necessary for every "type-call" from reflection. So there might be 2
extensions of TypesImpl, in compiler those fields are created
immediately, in reflection those are created lazily (not with lazy
keyword, but with null check, since the instance is used thread-locally).

I'm not sure it is possible, and it probably won't be "piece of cake"
because of other classes/types playing a role there, like TypesImpl
requiring other sub-cakes, and returned instances expected to be defined
within the master-cake.

My premise for this line of thinking was that this "state" in TypesImpl
is intrinsic for type-level calculations and it might be impossible to
rewrite the code to be without such "state" (of course it would be nicer
if possible). Apologies for entering internals discussion again, I'll
try to be economical with it.

Regards,
Jan

[Eugene Burmako]

Thanks! A promising idea would also be to factor state-dependent and mutually recursive operations such as isSubType/lub/... into a separate object, which could be instatiated on demand and then scrapped once the computation is completed.

[Roland Kuhn]

That will be the ideal solution if it is indeed possible: no ThreadLocals, no GC problems, just the caller pays, no extra synchronization … I like it! Would that not also be a first step towards making typer itself parallelizable in certain parts?

Regards,

Roland

10 feb 2013 kl. 04:31 skrev Eugene Burmako:

Thanks! A promising idea would also be to factor state-dependent and mutually recursive operations such as isSubType/lub/... into a separate object, which could be instatiated on demand and then scrapped once the computation is completed.

--
You received this message because you are subscribed to the Google Groups "scala-internals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-interna...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

Dr. Roland Kuhn
Akka Tech Lead
Typesafe – Empowering professional developers to build amazing apps.
twitter: @rolandkuhn