Re: [julia-users] Perhaps stupid question: Method type stability and throws

[Cedric St-Jean]

On Sat, May 7, 2016 at 2:19 PM, Yichao Yu  wrote:

> On Sat, May 7, 2016 at 1:21 PM, Cedric St-Jean 
> wrote:
> > Thank you for the detailed explanation!
> >
> > Would it make sense to run the catch blocks/finalizers before unwinding
> the
> > stack? I.e. each `try` pushes its catch/finally block as a "closure"
> onto a
> > separate stack, to be run when an exception occurs, then the stack is
> only
> > unwound once regular control flow is resumed, or collected if no handler
> was
> > found. I was wondering how Common Lisp was able to provide restarts, this
> > seems like a reasonable implementation strategy.
>
> Possibly related [1].
>

Yeah, that's the same idea. I don't care about restarts either, but in SBCL
(and... Python?) it made for a really nice debugger, since the stack isn't
unwound, and the debugger can just be a top-level `catch` block that
inspects the stack. I wonder how Gallium handles this.


> You probably want to do that **after** unwind the stack. Especially
> when you are throwing a stack overflow error for example =)
>

Judging by how undebuggable/unstable stack overflows in SBCL were, my
uneducated guess is that they ran the exception handlers *before* unwinding
the stack!


> The info you need should all be in the closure anyway.
>
> I think this would be mainly useful (avoiding a setjmp) for the try
> blocks with only finally (or a catch block that does not return) since
> otherwise you'll still need to restore the machine state in order to
> continue execution.
>
> Whether this can be implemented efficiently will also depend on if
> capture variable in closure can be implemented efficiently. (In
> general it's probably harder than issue 3 below)
>

Agreed. It may add an extra cost for every try block even on normal
execution...


> P.S. this is exactly how automatic unlocking of julia runtime locks
> are implemented[2]. Implemented for general julia code will be harder
> though.
>
> [1]
> https://groups.google.com/forum/#!searchin/julia-dev/Mason$20Bially/julia-dev/uTeuPv-DVKU/6T4JK3udAgAJ
> [2] https://github.com/JuliaLang/julia/pull/14451
>
> >
> > On Saturday, May 7, 2016 at 10:28:18 AM UTC-4, Yichao Yu wrote:
> >>
> >> On Sat, May 7, 2016 at 8:46 AM, Cedric St-Jean 
> >> wrote:
> >> >> mostly due to various technical reason
> >>
> >> In arbitrary order, the ones I can think of now.
> >>
> >> 1. We collect backtrace
> >>
> >> There are many cases where we don't actually need this info, but
> >> we need better code analysis to be able to figure that out.
> >>
> >> 2. We don't have zero cost exception frame so we need to spill many
> >> registers.
> >>
> >> It's hard for us to have zero cost exception frame unless all the
> >> C libraries are compiled with unwind info. Also note that zero cost
> >> exception frame means even more expensive exception throwing since the
> >> registers are not explicitly saved and we need to unwind the call
> >> stack to restore them. This is a trade off after all.
> >>
> >> 3. Preserving local variables across an exception requires spilling it
> >> to stack and this adds some hidden cost.
> >>
> >> It's a little hard to say how much cost this have, probably not
> >> THAT much unless you have a lot of variables that is modified in try
> >> and used after the exception is caught. Very likely strongly depending
> >> on the code pattern.
> >>
> >> 4. The GC frame allocation is global (well, per-function) instead of
> >> control flow local.
> >>
> >> This cause allocation in not-taken branch to affect the
> >> performance on the taken branch. This is not specific to exceptions
> >> but is particularly bad for exceptions since throwing one sometimes
> >> requires allocation that otherwise doesn't exist in the function (e.g.
> >> `ArgumentError("My error message with $variable spliced in")`) and
> >> these branches are meant to be not taken most of the time (if the
> >> error can happen most of the time, you'd be better off with a error
> >> code return, since exceptions are not designed for that).
> >>
> >> >
> >> > Could you please go into those? I'd like to understand why unwinding
> the
> >> > stack is costlier than returning from a function.
> >> >
> >> > On Saturday, May 7, 2016 at 8:38:03 AM UTC-4, Yichao Yu wrote:
> >> >>
> >> >> On Sat, May 7, 2016 at 6:58 AM, Ben Ward 
> wrote:
> >> >> > Hi,
> >> >> >
> >> >> > I have a question which may be laughable to CS people (be gentle,
> I'm
> >> >> > a
> >> >> > Biologist), but we know from guidelines that Julia performs best,
> >> >> > when a
> >> >> > method always returns the same type of value.
> >> >> > So the Julia type inference knows - ok, use this method with an
> Int,
> >> >> > it
> >> >> > will
> >> >> > always return a bool say. How does throws fit into this? To my mind
> >> >> > this
> >> >> > means the method used with an Int may return a bool, but it also
> may
> >> >> > result
> >> >> > 

Re: [julia-users] Perhaps stupid question: Method type stability and throws

[Yichao Yu]

On Sat, May 7, 2016 at 1:21 PM, Cedric St-Jean  wrote:
> Thank you for the detailed explanation!
>
> Would it make sense to run the catch blocks/finalizers before unwinding the
> stack? I.e. each `try` pushes its catch/finally block as a "closure" onto a
> separate stack, to be run when an exception occurs, then the stack is only
> unwound once regular control flow is resumed, or collected if no handler was
> found. I was wondering how Common Lisp was able to provide restarts, this
> seems like a reasonable implementation strategy.

Possibly related [1].

You probably want to do that **after** unwind the stack. Especially
when you are throwing a stack overflow error for example =)
The info you need should all be in the closure anyway.

I think this would be mainly useful (avoiding a setjmp) for the try
blocks with only finally (or a catch block that does not return) since
otherwise you'll still need to restore the machine state in order to
continue execution.

Whether this can be implemented efficiently will also depend on if
capture variable in closure can be implemented efficiently. (In
general it's probably harder than issue 3 below)

P.S. this is exactly how automatic unlocking of julia runtime locks
are implemented[2]. Implemented for general julia code will be harder
though.

[1] 
https://groups.google.com/forum/#!searchin/julia-dev/Mason$20Bially/julia-dev/uTeuPv-DVKU/6T4JK3udAgAJ
[2] https://github.com/JuliaLang/julia/pull/14451

>
> On Saturday, May 7, 2016 at 10:28:18 AM UTC-4, Yichao Yu wrote:
>>
>> On Sat, May 7, 2016 at 8:46 AM, Cedric St-Jean 
>> wrote:
>> >> mostly due to various technical reason
>>
>> In arbitrary order, the ones I can think of now.
>>
>> 1. We collect backtrace
>>
>> There are many cases where we don't actually need this info, but
>> we need better code analysis to be able to figure that out.
>>
>> 2. We don't have zero cost exception frame so we need to spill many
>> registers.
>>
>> It's hard for us to have zero cost exception frame unless all the
>> C libraries are compiled with unwind info. Also note that zero cost
>> exception frame means even more expensive exception throwing since the
>> registers are not explicitly saved and we need to unwind the call
>> stack to restore them. This is a trade off after all.
>>
>> 3. Preserving local variables across an exception requires spilling it
>> to stack and this adds some hidden cost.
>>
>> It's a little hard to say how much cost this have, probably not
>> THAT much unless you have a lot of variables that is modified in try
>> and used after the exception is caught. Very likely strongly depending
>> on the code pattern.
>>
>> 4. The GC frame allocation is global (well, per-function) instead of
>> control flow local.
>>
>> This cause allocation in not-taken branch to affect the
>> performance on the taken branch. This is not specific to exceptions
>> but is particularly bad for exceptions since throwing one sometimes
>> requires allocation that otherwise doesn't exist in the function (e.g.
>> `ArgumentError("My error message with $variable spliced in")`) and
>> these branches are meant to be not taken most of the time (if the
>> error can happen most of the time, you'd be better off with a error
>> code return, since exceptions are not designed for that).
>>
>> >
>> > Could you please go into those? I'd like to understand why unwinding the
>> > stack is costlier than returning from a function.
>> >
>> > On Saturday, May 7, 2016 at 8:38:03 AM UTC-4, Yichao Yu wrote:
>> >>
>> >> On Sat, May 7, 2016 at 6:58 AM, Ben Ward  wrote:
>> >> > Hi,
>> >> >
>> >> > I have a question which may be laughable to CS people (be gentle, I'm
>> >> > a
>> >> > Biologist), but we know from guidelines that Julia performs best,
>> >> > when a
>> >> > method always returns the same type of value.
>> >> > So the Julia type inference knows - ok, use this method with an Int,
>> >> > it
>> >> > will
>> >> > always return a bool say. How does throws fit into this? To my mind
>> >> > this
>> >> > means the method used with an Int may return a bool, but it also may
>> >> > result
>> >> > in a type of (e.g.) ArgumentError getting thrown. So how do throws in
>> >> > functions affect performance and julian's ability to infer types and
>> >> > optimise code (if at all?)?
>> >>
>> >> While throwing or catching an error itself is slow (mostly due to
>> >> various technical reason) they shouldn't affect type stability.
>> >>
>> >> The type inference currently do not reason about what type of
>> >> exception can be thrown and even if it does, this won't affect what we
>> >> usually call the type stability of a function since it is only about
>> >> the **return type** of a function and throwing an error is not return
>> >> (in the sense that `a = cond ? error() : 1`, if the next statement is
>> >> executed, a is always a `Int`).
>> >>
>> >> >
>> >> > Thanks,
>> >> > Ben W.

Re: [julia-users] Perhaps stupid question: Method type stability and throws

[Cedric St-Jean]

Thank you for the detailed explanation!

Would it make sense to run the catch blocks/finalizers before unwinding the 
stack? I.e. each `try` pushes its catch/finally block as a "closure" onto a 
separate stack, to be run when an exception occurs, then the stack is only 
unwound once regular control flow is resumed, or collected if no handler 
was found. I was wondering how Common Lisp was able to provide restarts, 
this seems like a reasonable implementation strategy.

On Saturday, May 7, 2016 at 10:28:18 AM UTC-4, Yichao Yu wrote:
>
> On Sat, May 7, 2016 at 8:46 AM, Cedric St-Jean  > wrote: 
> >> mostly due to various technical reason 
>
> In arbitrary order, the ones I can think of now. 
>
> 1. We collect backtrace 
>
> There are many cases where we don't actually need this info, but 
> we need better code analysis to be able to figure that out. 
>
> 2. We don't have zero cost exception frame so we need to spill many 
> registers. 
>
> It's hard for us to have zero cost exception frame unless all the 
> C libraries are compiled with unwind info. Also note that zero cost 
> exception frame means even more expensive exception throwing since the 
> registers are not explicitly saved and we need to unwind the call 
> stack to restore them. This is a trade off after all. 
>
> 3. Preserving local variables across an exception requires spilling it 
> to stack and this adds some hidden cost. 
>
> It's a little hard to say how much cost this have, probably not 
> THAT much unless you have a lot of variables that is modified in try 
> and used after the exception is caught. Very likely strongly depending 
> on the code pattern. 
>
> 4. The GC frame allocation is global (well, per-function) instead of 
> control flow local. 
>
> This cause allocation in not-taken branch to affect the 
> performance on the taken branch. This is not specific to exceptions 
> but is particularly bad for exceptions since throwing one sometimes 
> requires allocation that otherwise doesn't exist in the function (e.g. 
> `ArgumentError("My error message with $variable spliced in")`) and 
> these branches are meant to be not taken most of the time (if the 
> error can happen most of the time, you'd be better off with a error 
> code return, since exceptions are not designed for that). 
>
> > 
> > Could you please go into those? I'd like to understand why unwinding the 
> > stack is costlier than returning from a function. 
> > 
> > On Saturday, May 7, 2016 at 8:38:03 AM UTC-4, Yichao Yu wrote: 
> >> 
> >> On Sat, May 7, 2016 at 6:58 AM, Ben Ward  wrote: 
> >> > Hi, 
> >> > 
> >> > I have a question which may be laughable to CS people (be gentle, I'm 
> a 
> >> > Biologist), but we know from guidelines that Julia performs best, 
> when a 
> >> > method always returns the same type of value. 
> >> > So the Julia type inference knows - ok, use this method with an Int, 
> it 
> >> > will 
> >> > always return a bool say. How does throws fit into this? To my mind 
> this 
> >> > means the method used with an Int may return a bool, but it also may 
> >> > result 
> >> > in a type of (e.g.) ArgumentError getting thrown. So how do throws in 
> >> > functions affect performance and julian's ability to infer types and 
> >> > optimise code (if at all?)? 
> >> 
> >> While throwing or catching an error itself is slow (mostly due to 
> >> various technical reason) they shouldn't affect type stability. 
> >> 
> >> The type inference currently do not reason about what type of 
> >> exception can be thrown and even if it does, this won't affect what we 
> >> usually call the type stability of a function since it is only about 
> >> the **return type** of a function and throwing an error is not return 
> >> (in the sense that `a = cond ? error() : 1`, if the next statement is 
> >> executed, a is always a `Int`). 
> >> 
> >> > 
> >> > Thanks, 
> >> > Ben W. 
>

Re: [julia-users] Perhaps stupid question: Method type stability and throws

[Yichao Yu]

On Sat, May 7, 2016 at 8:46 AM, Cedric St-Jean  wrote:
>> mostly due to various technical reason

In arbitrary order, the ones I can think of now.

1. We collect backtrace

There are many cases where we don't actually need this info, but
we need better code analysis to be able to figure that out.

2. We don't have zero cost exception frame so we need to spill many registers.

It's hard for us to have zero cost exception frame unless all the
C libraries are compiled with unwind info. Also note that zero cost
exception frame means even more expensive exception throwing since the
registers are not explicitly saved and we need to unwind the call
stack to restore them. This is a trade off after all.

3. Preserving local variables across an exception requires spilling it
to stack and this adds some hidden cost.

It's a little hard to say how much cost this have, probably not
THAT much unless you have a lot of variables that is modified in try
and used after the exception is caught. Very likely strongly depending
on the code pattern.

4. The GC frame allocation is global (well, per-function) instead of
control flow local.

This cause allocation in not-taken branch to affect the
performance on the taken branch. This is not specific to exceptions
but is particularly bad for exceptions since throwing one sometimes
requires allocation that otherwise doesn't exist in the function (e.g.
`ArgumentError("My error message with $variable spliced in")`) and
these branches are meant to be not taken most of the time (if the
error can happen most of the time, you'd be better off with a error
code return, since exceptions are not designed for that).

>
> Could you please go into those? I'd like to understand why unwinding the
> stack is costlier than returning from a function.
>
> On Saturday, May 7, 2016 at 8:38:03 AM UTC-4, Yichao Yu wrote:
>>
>> On Sat, May 7, 2016 at 6:58 AM, Ben Ward  wrote:
>> > Hi,
>> >
>> > I have a question which may be laughable to CS people (be gentle, I'm a
>> > Biologist), but we know from guidelines that Julia performs best, when a
>> > method always returns the same type of value.
>> > So the Julia type inference knows - ok, use this method with an Int, it
>> > will
>> > always return a bool say. How does throws fit into this? To my mind this
>> > means the method used with an Int may return a bool, but it also may
>> > result
>> > in a type of (e.g.) ArgumentError getting thrown. So how do throws in
>> > functions affect performance and julian's ability to infer types and
>> > optimise code (if at all?)?
>>
>> While throwing or catching an error itself is slow (mostly due to
>> various technical reason) they shouldn't affect type stability.
>>
>> The type inference currently do not reason about what type of
>> exception can be thrown and even if it does, this won't affect what we
>> usually call the type stability of a function since it is only about
>> the **return type** of a function and throwing an error is not return
>> (in the sense that `a = cond ? error() : 1`, if the next statement is
>> executed, a is always a `Int`).
>>
>> >
>> > Thanks,
>> > Ben W.

Re: [julia-users] Perhaps stupid question: Method type stability and throws

[Cedric St-Jean]

> mostly due to various technical reason

Could you please go into those? I'd like to understand why unwinding the 
stack is costlier than returning from a function.

On Saturday, May 7, 2016 at 8:38:03 AM UTC-4, Yichao Yu wrote:
>
> On Sat, May 7, 2016 at 6:58 AM, Ben Ward  > wrote: 
> > Hi, 
> > 
> > I have a question which may be laughable to CS people (be gentle, I'm a 
> > Biologist), but we know from guidelines that Julia performs best, when a 
> > method always returns the same type of value. 
> > So the Julia type inference knows - ok, use this method with an Int, it 
> will 
> > always return a bool say. How does throws fit into this? To my mind this 
> > means the method used with an Int may return a bool, but it also may 
> result 
> > in a type of (e.g.) ArgumentError getting thrown. So how do throws in 
> > functions affect performance and julian's ability to infer types and 
> > optimise code (if at all?)? 
>
> While throwing or catching an error itself is slow (mostly due to 
> various technical reason) they shouldn't affect type stability. 
>
> The type inference currently do not reason about what type of 
> exception can be thrown and even if it does, this won't affect what we 
> usually call the type stability of a function since it is only about 
> the **return type** of a function and throwing an error is not return 
> (in the sense that `a = cond ? error() : 1`, if the next statement is 
> executed, a is always a `Int`). 
>
> > 
> > Thanks, 
> > Ben W. 
>

Re: [julia-users] Perhaps stupid question: Method type stability and throws

[Yichao Yu]

On Sat, May 7, 2016 at 6:58 AM, Ben Ward  wrote:
> Hi,
>
> I have a question which may be laughable to CS people (be gentle, I'm a
> Biologist), but we know from guidelines that Julia performs best, when a
> method always returns the same type of value.
> So the Julia type inference knows - ok, use this method with an Int, it will
> always return a bool say. How does throws fit into this? To my mind this
> means the method used with an Int may return a bool, but it also may result
> in a type of (e.g.) ArgumentError getting thrown. So how do throws in
> functions affect performance and julian's ability to infer types and
> optimise code (if at all?)?

While throwing or catching an error itself is slow (mostly due to
various technical reason) they shouldn't affect type stability.

The type inference currently do not reason about what type of
exception can be thrown and even if it does, this won't affect what we
usually call the type stability of a function since it is only about
the **return type** of a function and throwing an error is not return
(in the sense that `a = cond ? error() : 1`, if the next statement is
executed, a is always a `Int`).

>
> Thanks,
> Ben W.

[julia-users] Perhaps stupid question: Method type stability and throws

[Ben Ward]

Hi,

I have a question which may be laughable to CS people (be gentle, I'm a 
Biologist), but we know from guidelines that Julia performs best, when a 
method always returns the same type of value.
So the Julia type inference knows - ok, use this method with an Int, it 
will always return a bool say. How does throws fit into this? To my mind 
this means the method used with an Int may return a bool, but it also may 
result in a type of (e.g.) ArgumentError getting thrown. So how do throws 
in functions affect performance and julian's ability to infer types and 
optimise code (if at all?)? 

Thanks,
Ben W.