Re: [racket-dev] TR's optimizer eventually going to unbox structs?

[Robby Findler]

Oh, okay. And so if you have a function that accepts a struct, does some
work with it, and then returns a new version of it (and you wanted to
optimize the body of the function), then you could get away with doing
something like 'struct-copy' to make the final version that gets returned.

Robby

On Monday, August 27, 2012, Vincent St-Amour wrote:

> I don't think it would be necessary.
>
> For the optimization to trigger, the only thing a step in the chain can
> do with its argument is use its components. Anything else (e.g. checking
> whether it's a substruct) would require the argument to be boxed, and
> would prevent the optimization from happening.
>
> Each step of the chain is very limited in what it can do to its
> argument, which works fine for complex numbers (most operations on them
> only use the components), but I'm not sure it would work well for
> structs.
>
> Vincent
>
>
> At Mon, 27 Aug 2012 10:15:04 -0500,
> Robby Findler wrote:
> >
> > Would you need a "and is not a substruct?" predicate to make such things
> work?
> >
> > Robby
> >
> > On Mon, Aug 27, 2012 at 10:11 AM, Vincent St-Amour 
> > >
> wrote:
> > > TR's complex number optimizations eliminate repeated boxing and
> unboxing
> > > in chains of operations that each consume and produce complex numbers.
> > >
> > > Similar optimizations for structs would eliminate structs for
> > > intermediate results in chains of operations that each consume and
> > > produce that same (single) kind of struct.
> > >
> > > If your code has such chains of operations, then these optimizations
> > > could apply.
> > >
> > > Do you have code that you think would benefit that I could look at?
> > >
> > > Vincent
> > >
> > >
> > > At Sat, 18 Aug 2012 12:40:21 -0600,
> > > Neil Toronto wrote:
> > >>
> > >> Is TR's optimizer eventually going to unbox structs in the same way it
> > >> unboxes rectangular flonums?
> > >>
> > >> I have a design choice right now: how to represent probabilities.
> Floats
> > >> are good because of their speed, but because of floating-point
> > >> limitations, *four different representations* are typically used. (For
> > >> the curious: p, 1-p, log(p), and log(1-p).) I'd like to make functions
> > >> that accept any one of these representations, denoted by this type:
> > >>
> > >>(define-type Probability
> > >>  (U probability 1-probability log-probability log-1-probability))
> > >>
> > >> The types are simply struct types that tag Float.
> > >>
> > >> Of course, manually boxing flonums ruins any chance of the compiler
> > >> emitting code that keeps the flonums unboxed. If TR's optimizer
> unboxed
> > >> structs, though, everything could be speedy.
> > >>
> > >> FWIW, by "eventually," I mean "within the next n years", where "n" is
> a
> > >> smallish number.
> > >>
> > >> Neil ⊥
> > >> _
> > >>   Racket Developers list:
> > >>   http://lists.racket-lang.org/dev
> > >
> > > _
> > >   Racket Developers list:
> > >   http://lists.racket-lang.org/dev
>
_
  Racket Developers list:
  http://lists.racket-lang.org/dev

Re: [racket-dev] TR's optimizer eventually going to unbox structs?

[Ray Racine]

FWIW, the Scala folks have done something along these lines, Value Classes,
originally aka Inline Classes.

https://docs.google.com/document/d/10TQKgMiJTbVtkdRG53wsLYwWM2MkhtmdV25-NZvLLMA/edit?hl=en_US&pli=1


On Mon, Aug 27, 2012 at 12:58 PM, Neil Toronto wrote:

> On 08/27/2012 09:11 AM, Vincent St-Amour wrote:
>
>> TR's complex number optimizations eliminate repeated boxing and unboxing
>> in chains of operations that each consume and produce complex numbers.
>>
>> Similar optimizations for structs would eliminate structs for
>> intermediate results in chains of operations that each consume and
>> produce that same (single) kind of struct.
>>
>> If your code has such chains of operations, then these optimizations
>> could apply.
>>
>> Do you have code that you think would benefit that I could look at?
>>
>
> Not yet. I've given up on a union of different probability representation
> types for now.
>
> For arrays, I could. An array is just a function with a finite,
> rectangular domain (a "shape"). Think of the type like this:
>
>   (struct: (A) array ([shape : (Vectorof Index)]
>   [proc : ((Vectorof Index) -> A)]))
>
> (This is a bit simplified.) So
>
>   (array-exp (array-abs arr))
>
> doesn't actually compute (log (abs x)) for any `x', it just creates an
> array that would if you asked it for an element. IOW, it's equivalent to
>
>   (array-map (compose exp abs) arr)
>
> which itself is equivalent to
>
>   (array (array-shape arr) (compose exp abs (array-proc arr)))
>
> If I made functions like `array-exp' and `array-map' into macros, and if
> array structs were unboxed, Racket's optimizer could inline the
> compositions. I imagine this eventual lovely outcome:
>
>   (let ([proc  (array-proc arr)])
> (array (array-shape arr)
>(lambda (x) (unsafe-flexp (unsafe-flabs (proc x))
>
> There are also FlArray and FCArray, which are subtypes of Array that store
> their elements (unboxed in flvectors and fcvectors). FlArray-specific
> operations are currently about 5x faster than Array's. But Array's ops
> don't allocate stores for intermediate results, so with the right
> optimizations, Array's could be the faster ones.
>
> If you want to have a look right now, checkout
>
>   
> https://github.com/ntoronto/**racket.git
>
> and try this program:
>
> #lang typed/racket
>
> (require math/array)
>
> (define arr (array [[1.2 4.0] [3.2 -1.8]]))
> (inline-array-map exp (inline-array-map abs arr))
>
>
>
> Neil ⊥
>
> _
>  Racket Developers list:
>  http://lists.racket-lang.org/**dev 
>
_
  Racket Developers list:
  http://lists.racket-lang.org/dev

Re: [racket-dev] TR's optimizer eventually going to unbox structs?

[Neil Toronto]

On 08/27/2012 09:11 AM, Vincent St-Amour wrote:

TR's complex number optimizations eliminate repeated boxing and unboxing
in chains of operations that each consume and produce complex numbers.

Similar optimizations for structs would eliminate structs for
intermediate results in chains of operations that each consume and
produce that same (single) kind of struct.

If your code has such chains of operations, then these optimizations
could apply.

Do you have code that you think would benefit that I could look at?


Not yet. I've given up on a union of different probability 
representation types for now.


For arrays, I could. An array is just a function with a finite, 
rectangular domain (a "shape"). Think of the type like this:


  (struct: (A) array ([shape : (Vectorof Index)]
  [proc : ((Vectorof Index) -> A)]))

(This is a bit simplified.) So

  (array-exp (array-abs arr))

doesn't actually compute (log (abs x)) for any `x', it just creates an 
array that would if you asked it for an element. IOW, it's equivalent to


  (array-map (compose exp abs) arr)

which itself is equivalent to

  (array (array-shape arr) (compose exp abs (array-proc arr)))

If I made functions like `array-exp' and `array-map' into macros, and if 
array structs were unboxed, Racket's optimizer could inline the 
compositions. I imagine this eventual lovely outcome:


  (let ([proc  (array-proc arr)])
(array (array-shape arr)
   (lambda (x) (unsafe-flexp (unsafe-flabs (proc x))

There are also FlArray and FCArray, which are subtypes of Array that 
store their elements (unboxed in flvectors and fcvectors). 
FlArray-specific operations are currently about 5x faster than Array's. 
But Array's ops don't allocate stores for intermediate results, so with 
the right optimizations, Array's could be the faster ones.


If you want to have a look right now, checkout

  https://github.com/ntoronto/racket.git

and try this program:

#lang typed/racket

(require math/array)

(define arr (array [[1.2 4.0] [3.2 -1.8]]))
(inline-array-map exp (inline-array-map abs arr))


Neil ⊥

_
 Racket Developers list:
 http://lists.racket-lang.org/dev

Re: [racket-dev] TR's optimizer eventually going to unbox structs?

[Vincent St-Amour]

I don't think it would be necessary.

For the optimization to trigger, the only thing a step in the chain can
do with its argument is use its components. Anything else (e.g. checking
whether it's a substruct) would require the argument to be boxed, and
would prevent the optimization from happening.

Each step of the chain is very limited in what it can do to its
argument, which works fine for complex numbers (most operations on them
only use the components), but I'm not sure it would work well for
structs.

Vincent


At Mon, 27 Aug 2012 10:15:04 -0500,
Robby Findler wrote:
> 
> Would you need a "and is not a substruct?" predicate to make such things work?
> 
> Robby
> 
> On Mon, Aug 27, 2012 at 10:11 AM, Vincent St-Amour  
> wrote:
> > TR's complex number optimizations eliminate repeated boxing and unboxing
> > in chains of operations that each consume and produce complex numbers.
> >
> > Similar optimizations for structs would eliminate structs for
> > intermediate results in chains of operations that each consume and
> > produce that same (single) kind of struct.
> >
> > If your code has such chains of operations, then these optimizations
> > could apply.
> >
> > Do you have code that you think would benefit that I could look at?
> >
> > Vincent
> >
> >
> > At Sat, 18 Aug 2012 12:40:21 -0600,
> > Neil Toronto wrote:
> >>
> >> Is TR's optimizer eventually going to unbox structs in the same way it
> >> unboxes rectangular flonums?
> >>
> >> I have a design choice right now: how to represent probabilities. Floats
> >> are good because of their speed, but because of floating-point
> >> limitations, *four different representations* are typically used. (For
> >> the curious: p, 1-p, log(p), and log(1-p).) I'd like to make functions
> >> that accept any one of these representations, denoted by this type:
> >>
> >>(define-type Probability
> >>  (U probability 1-probability log-probability log-1-probability))
> >>
> >> The types are simply struct types that tag Float.
> >>
> >> Of course, manually boxing flonums ruins any chance of the compiler
> >> emitting code that keeps the flonums unboxed. If TR's optimizer unboxed
> >> structs, though, everything could be speedy.
> >>
> >> FWIW, by "eventually," I mean "within the next n years", where "n" is a
> >> smallish number.
> >>
> >> Neil ⊥
> >> _
> >>   Racket Developers list:
> >>   http://lists.racket-lang.org/dev
> >
> > _
> >   Racket Developers list:
> >   http://lists.racket-lang.org/dev

_
  Racket Developers list:
  http://lists.racket-lang.org/dev

Re: [racket-dev] TR's optimizer eventually going to unbox structs?

[Robby Findler]

Would you need a "and is not a substruct?" predicate to make such things work?

Robby

On Mon, Aug 27, 2012 at 10:11 AM, Vincent St-Amour  wrote:
> TR's complex number optimizations eliminate repeated boxing and unboxing
> in chains of operations that each consume and produce complex numbers.
>
> Similar optimizations for structs would eliminate structs for
> intermediate results in chains of operations that each consume and
> produce that same (single) kind of struct.
>
> If your code has such chains of operations, then these optimizations
> could apply.
>
> Do you have code that you think would benefit that I could look at?
>
> Vincent
>
>
> At Sat, 18 Aug 2012 12:40:21 -0600,
> Neil Toronto wrote:
>>
>> Is TR's optimizer eventually going to unbox structs in the same way it
>> unboxes rectangular flonums?
>>
>> I have a design choice right now: how to represent probabilities. Floats
>> are good because of their speed, but because of floating-point
>> limitations, *four different representations* are typically used. (For
>> the curious: p, 1-p, log(p), and log(1-p).) I'd like to make functions
>> that accept any one of these representations, denoted by this type:
>>
>>(define-type Probability
>>  (U probability 1-probability log-probability log-1-probability))
>>
>> The types are simply struct types that tag Float.
>>
>> Of course, manually boxing flonums ruins any chance of the compiler
>> emitting code that keeps the flonums unboxed. If TR's optimizer unboxed
>> structs, though, everything could be speedy.
>>
>> FWIW, by "eventually," I mean "within the next n years", where "n" is a
>> smallish number.
>>
>> Neil ⊥
>> _
>>   Racket Developers list:
>>   http://lists.racket-lang.org/dev
>
> _
>   Racket Developers list:
>   http://lists.racket-lang.org/dev

_
  Racket Developers list:
  http://lists.racket-lang.org/dev

Re: [racket-dev] TR's optimizer eventually going to unbox structs?

[Vincent St-Amour]

TR's complex number optimizations eliminate repeated boxing and unboxing
in chains of operations that each consume and produce complex numbers.

Similar optimizations for structs would eliminate structs for
intermediate results in chains of operations that each consume and
produce that same (single) kind of struct.

If your code has such chains of operations, then these optimizations
could apply.

Do you have code that you think would benefit that I could look at?

Vincent


At Sat, 18 Aug 2012 12:40:21 -0600,
Neil Toronto wrote:
> 
> Is TR's optimizer eventually going to unbox structs in the same way it 
> unboxes rectangular flonums?
> 
> I have a design choice right now: how to represent probabilities. Floats 
> are good because of their speed, but because of floating-point 
> limitations, *four different representations* are typically used. (For 
> the curious: p, 1-p, log(p), and log(1-p).) I'd like to make functions 
> that accept any one of these representations, denoted by this type:
> 
>(define-type Probability
>  (U probability 1-probability log-probability log-1-probability))
> 
> The types are simply struct types that tag Float.
> 
> Of course, manually boxing flonums ruins any chance of the compiler 
> emitting code that keeps the flonums unboxed. If TR's optimizer unboxed 
> structs, though, everything could be speedy.
> 
> FWIW, by "eventually," I mean "within the next n years", where "n" is a 
> smallish number.
> 
> Neil ⊥
> _
>   Racket Developers list:
>   http://lists.racket-lang.org/dev

_
  Racket Developers list:
  http://lists.racket-lang.org/dev

Re: [racket-dev] TR's optimizer eventually going to unbox structs?

[Robby Findler]

Oh right! A generalized version of that strategy might work for Neil's
program too.

On Saturday, August 18, 2012, Matthias Felleisen wrote:

>
> Vincent got TR to 'split' complex numbers, if that's what you mean by
> 'wide enough' arguments, and he did so w/o changing R. So perhaps there is
> a way to get the computation on floats and the tag for their meaning.
>
>
>
> On Aug 18, 2012, at 4:13 PM, Robby Findler wrote:
>
> One could, concievably, still do that without boxing/unblocking by passing
> "wide enough" arguments. And it does seem like TR could help with that, but
> IIUC the untyped portion of the compiler needs significant work to support
> that before TR's knowledge of the program would help (But doing a better
> job with structs is, iiuc, a long standing "something could be much better
> here" type of thing.)
>
> On Saturday, August 18, 2012, Matthias Felleisen wrote:
>
>>
>> But don't you need the 'tag' from the struct to distinguish .4 in p from
>> .4 in 1-p? They may be the same number but they denote distinct ideas. --
>> Matthias
>> '
>>
>>
>> On Aug 18, 2012, at 2:40 PM, Neil Toronto wrote:
>>
>> > Is TR's optimizer eventually going to unbox structs in the same way it
>> unboxes rectangular flonums?
>> >
>> > I have a design choice right now: how to represent probabilities.
>> Floats are good because of their speed, but because of floating-point
>> limitations, *four different representations* are typically used. (For the
>> curious: p, 1-p, log(p), and log(1-p).) I'd like to make functions that
>> accept any one of these representations, denoted by this type:
>> >
>> >  (define-type Probability
>> >(U probability 1-probability log-probability log-1-probability))
>> >
>> > The types are simply struct types that tag Float.
>> >
>> > Of course, manually boxing flonums ruins any chance of the compiler
>> emitting code that keeps the flonums unboxed. If TR's optimizer unboxed
>> structs, though, everything could be speedy.
>> >
>> > FWIW, by "eventually," I mean "within the next n years", where "n" is a
>> smallish number.
>> >
>> > Neil ⊥
>> > _
>> > Racket Developers list:
>> > http://lists.racket-lang.org/dev
>>
>>
>
_
  Racket Developers list:
  http://lists.racket-lang.org/dev

Re: [racket-dev] TR's optimizer eventually going to unbox structs?

[Matthias Felleisen]

Vincent got TR to 'split' complex numbers, if that's what you mean by 'wide 
enough' arguments, and he did so w/o changing R. So perhaps there is a way to 
get the computation on floats and the tag for their meaning. 



On Aug 18, 2012, at 4:13 PM, Robby Findler wrote:

> One could, concievably, still do that without boxing/unblocking by passing 
> "wide enough" arguments. And it does seem like TR could help with that, but 
> IIUC the untyped portion of the compiler needs significant work to support 
> that before TR's knowledge of the program would help (But doing a better job 
> with structs is, iiuc, a long standing "something could be much better here" 
> type of thing.) 
> 
> On Saturday, August 18, 2012, Matthias Felleisen wrote:
> 
> But don't you need the 'tag' from the struct to distinguish .4 in p from .4 
> in 1-p? They may be the same number but they denote distinct ideas. -- 
> Matthias
> '
> 
> 
> On Aug 18, 2012, at 2:40 PM, Neil Toronto wrote:
> 
> > Is TR's optimizer eventually going to unbox structs in the same way it 
> > unboxes rectangular flonums?
> >
> > I have a design choice right now: how to represent probabilities. Floats 
> > are good because of their speed, but because of floating-point limitations, 
> > *four different representations* are typically used. (For the curious: p, 
> > 1-p, log(p), and log(1-p).) I'd like to make functions that accept any one 
> > of these representations, denoted by this type:
> >
> >  (define-type Probability
> >(U probability 1-probability log-probability log-1-probability))
> >
> > The types are simply struct types that tag Float.
> >
> > Of course, manually boxing flonums ruins any chance of the compiler 
> > emitting code that keeps the flonums unboxed. If TR's optimizer unboxed 
> > structs, though, everything could be speedy.
> >
> > FWIW, by "eventually," I mean "within the next n years", where "n" is a 
> > smallish number.
> >
> > Neil ⊥
> > _
> > Racket Developers list:
> > http://lists.racket-lang.org/dev
> 



smime.p7s
Description: S/MIME cryptographic signature
_
  Racket Developers list:
  http://lists.racket-lang.org/dev

Re: [racket-dev] TR's optimizer eventually going to unbox structs?

[Robby Findler]

One could, concievably, still do that without boxing/unblocking by passing
"wide enough" arguments. And it does seem like TR could help with that, but
IIUC the untyped portion of the compiler needs significant work to support
that before TR's knowledge of the program would help (But doing a better
job with structs is, iiuc, a long standing "something could be much better
here" type of thing.)

On Saturday, August 18, 2012, Matthias Felleisen wrote:

>
> But don't you need the 'tag' from the struct to distinguish .4 in p from
> .4 in 1-p? They may be the same number but they denote distinct ideas. --
> Matthias
> '
>
>
> On Aug 18, 2012, at 2:40 PM, Neil Toronto wrote:
>
> > Is TR's optimizer eventually going to unbox structs in the same way it
> unboxes rectangular flonums?
> >
> > I have a design choice right now: how to represent probabilities. Floats
> are good because of their speed, but because of floating-point limitations,
> *four different representations* are typically used. (For the curious: p,
> 1-p, log(p), and log(1-p).) I'd like to make functions that accept any one
> of these representations, denoted by this type:
> >
> >  (define-type Probability
> >(U probability 1-probability log-probability log-1-probability))
> >
> > The types are simply struct types that tag Float.
> >
> > Of course, manually boxing flonums ruins any chance of the compiler
> emitting code that keeps the flonums unboxed. If TR's optimizer unboxed
> structs, though, everything could be speedy.
> >
> > FWIW, by "eventually," I mean "within the next n years", where "n" is a
> smallish number.
> >
> > Neil ⊥
> > _
> > Racket Developers list:
> > http://lists.racket-lang.org/dev
>
>
_
  Racket Developers list:
  http://lists.racket-lang.org/dev

Re: [racket-dev] TR's optimizer eventually going to unbox structs?

[Matthias Felleisen]

But don't you need the 'tag' from the struct to distinguish .4 in p from .4 in 
1-p? They may be the same number but they denote distinct ideas. -- Matthias
'


On Aug 18, 2012, at 2:40 PM, Neil Toronto wrote:

> Is TR's optimizer eventually going to unbox structs in the same way it 
> unboxes rectangular flonums?
> 
> I have a design choice right now: how to represent probabilities. Floats are 
> good because of their speed, but because of floating-point limitations, *four 
> different representations* are typically used. (For the curious: p, 1-p, 
> log(p), and log(1-p).) I'd like to make functions that accept any one of 
> these representations, denoted by this type:
> 
>  (define-type Probability
>(U probability 1-probability log-probability log-1-probability))
> 
> The types are simply struct types that tag Float.
> 
> Of course, manually boxing flonums ruins any chance of the compiler emitting 
> code that keeps the flonums unboxed. If TR's optimizer unboxed structs, 
> though, everything could be speedy.
> 
> FWIW, by "eventually," I mean "within the next n years", where "n" is a 
> smallish number.
> 
> Neil ⊥
> _
> Racket Developers list:
> http://lists.racket-lang.org/dev



smime.p7s
Description: S/MIME cryptographic signature
_
  Racket Developers list:
  http://lists.racket-lang.org/dev