Re: [racket-dev] TR's optimizer eventually going to unbox structs?
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 stamo...@ccs.neu.edu 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?
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 stamo...@ccs.neu.edu 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?
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?
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_USpli=1 On Mon, Aug 27, 2012 at 12:58 PM, Neil Toronto neil.toro...@gmail.comwrote: 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.githttps://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 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?
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 stamo...@ccs.neu.edujavascript:; 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
[racket-dev] TR's optimizer eventually going to unbox structs?
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
Re: [racket-dev] TR's optimizer eventually going to unbox structs?
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?
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?
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?
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
