Re: [racket] Optimization; converting 'Float' to 'Fixnum' in Typed Racket
At Sat, 18 Feb 2012 23:04:33 -0500, Vincent St-Amour wrote: > > The problem is that I can't find a way to convert a Float to a Fixnum, > > only to an Integer. None of fl->fx, unsafe-fl->fx, or > > fl->exact-integer work, as Type Checker tells me they're untyped > > identifiers. > > That should work. I'll look into that. Fixed. Thanks for the report. Vincent Racket Users list: http://lists.racket-lang.org/users
Re: [racket] Optimization; converting 'Float' to 'Fixnum' in Typed Racket
At Sat, 18 Feb 2012 21:47:52 -0600, Robby Findler wrote: > On Sat, Feb 18, 2012 at 9:39 PM, SF wrote: > > On Sat, Feb 18, 2012 at 9:18 PM, Robby Findler wrote: > >> I'm not sure of the precise answer, but I don't think that all floats > >> (even the integers) have a corresponding fixnum. > > > > My C brain wonders why I can't just cast it to get the lower bits, I > > don't care about overflow. > > I'm not sure if this will fit in with how Typed Racket works, but I > guess you could write an ffi-based function that actually fiddles with > the low-level representation to just get at the bits you want. > > But, actually, I think that maybe that won't work because Racket's > floats are usually boxed, unless the compiler can "see" everywhere > they go and can manage to pass around unboxed versions (something that > TR facilitates, I believe). So, if you were to pass them off to an > unknown (from the compiler & TR's perspective) function, then they'd > fall back to boxing and you'd lose all the efficiency gains. > > I guess there would have to be some new primitive added to make this work. > > Of course, I could be missing out on one of the existing prims. Maybe > one of the TR/runtime system experts'll fill us in. `fl->fx' does what he wants, but only if the input float actually represents an integer. Vincent Racket Users list: http://lists.racket-lang.org/users
Re: [racket] Optimization; converting 'Float' to 'Fixnum' in Typed Racket
At Sat, 18 Feb 2012 22:14:05 -0600, Robby Findler wrote: > What if his code used fx+ and friends instead of + and friends? `fx+' and friends are not as fast as `unsafe-fx+' and friends, but since they're guaranteed to return fixnums (or error), they're more TR-friendly. Good point. Vincent Racket Users list: http://lists.racket-lang.org/users
Re: [racket] Optimization; converting 'Float' to 'Fixnum' in Typed Racket
What if his code used fx+ and friends instead of + and friends? Robby On Sat, Feb 18, 2012 at 10:04 PM, Vincent St-Amour wrote: > At Sat, 18 Feb 2012 21:07:05 -0500, > SF wrote: >> I'm trying to optimize some code that processes a bunch of data, >> basically image pixels, which currently takes on the order of several >> seconds and seems like it should be much faster (important because >> it's an interactive application). Coming from C++ I have a good idea >> in my mind of how I'd write it with low-level operations. I read up on >> Racket optimization. It is still somewhat unclear to me how Racket >> deals with fixnums, flonums, unsafe operations, Typed Racket types, >> and how it all fits together. > > Racket's unsafe operations do not perform any checks and guide the > compiler's unboxing optimizations. Using them can lead to significant > speedups. > > Typed Racket performs type-driven optimization when it can guarantee > that doing so is safe. Most of its optimizations replace generic > arithmetic with specialized unsafe operations. The performance > benefits are equivalent to using unsafe operations manually. The > advantage of using TR is that it won't introduce bugs by optimizing > when it's not safe to do so. > > In practice, TR will optimize pretty much any floating-point > computation. In the case of fixnum operations, it optimizes only when > it can guarantee that no overflow will happen. This means that you may > need to help it a bit if you want to get fixnum optimizations. > > To see how TR optimizes your code (for example, to make sure that you > get all the optimizations you want), check out the "performance > report" DrRacket tool. > >> I chose to optimize my program (partly >> to learn how) incrementally, trying all the options, timing at every >> step with debugging info turned off. This worked until I wanted to >> convert Integers to Fixnums in Typed Racket (which has been giving me >> much faster results than anything in untyped Racket). > > You don't need to convert between integers and fixnums. Fixnums are > simply integers that are small enough to be represented as tagged > machine integers. If an operation on fixnums would cause an overflow, > the result is transparently promoted to a bignum instead. > > To use fixnums in TR, you can annotate your variables as being of > `Fixnum' type. However, due to the promotion semantics, fixnums have > pretty bad closure properties, which means that the result of, say, > adding two fixnums is not guaranteed to be a fixnum itself and has to > be given the `Integer' type. > > To help with this, TR provides an `Index' type which is for integers > bounded by the length of the longest possible vector (smaller than a > fixnum). Adding two of these is guaranteed to produce a `Fixnum'. > > The bottom line is that it's possible to get fixnum optimizations in > TR, but since TR has to be conservative in order to be safe, sometimes > you may have to use unsafe fixnum operations manually to get the > performance you want. > >> The problem is that I can't find a way to convert a Float to a Fixnum, >> only to an Integer. None of fl->fx, unsafe-fl->fx, or >> fl->exact-integer work, as Type Checker tells me they're untyped >> identifiers. > > That should work. I'll look into that. > > Vincent > > Racket Users list: > http://lists.racket-lang.org/users Racket Users list: http://lists.racket-lang.org/users
Re: [racket] Optimization; converting 'Float' to 'Fixnum' in Typed Racket
At Sat, 18 Feb 2012 21:39:33 -0600, Robby Findler wrote: > > Still, good to > > know. I didn't think of using Typed Racket like that. > > > > I should mention that this is the best method I've found so far: > > > > (: float->int (Float -> Integer)) > > (define (float->int x) > > (floor (inexact->exact (floor x ; both floors are necessary > > Why is the second floor necessary? Just for the type system or are > there inexact integers that become exact non-integers? Yes. The inner `floor' produces a float that represents an integer. TR doesn't distinguish them from other floats, so the result of `inexact->exact' is of type `Exact-Rational'. The outer floor takes it to the type `Integer'. From the type system's perspective, the inner floor is not necessary. However, leaving it out may cause `inexact->exact' to return fractions in some cases, which would be bad performance-wise. From Racket's point of view, the outer floor is not necessary, since `inexact->exact' will always return integers, on which `floor' is the identity. Vincent Racket Users list: http://lists.racket-lang.org/users
Re: [racket] Optimization; converting 'Float' to 'Fixnum' in Typed Racket
At Sat, 18 Feb 2012 21:07:05 -0500, SF wrote: > I'm trying to optimize some code that processes a bunch of data, > basically image pixels, which currently takes on the order of several > seconds and seems like it should be much faster (important because > it's an interactive application). Coming from C++ I have a good idea > in my mind of how I'd write it with low-level operations. I read up on > Racket optimization. It is still somewhat unclear to me how Racket > deals with fixnums, flonums, unsafe operations, Typed Racket types, > and how it all fits together. Racket's unsafe operations do not perform any checks and guide the compiler's unboxing optimizations. Using them can lead to significant speedups. Typed Racket performs type-driven optimization when it can guarantee that doing so is safe. Most of its optimizations replace generic arithmetic with specialized unsafe operations. The performance benefits are equivalent to using unsafe operations manually. The advantage of using TR is that it won't introduce bugs by optimizing when it's not safe to do so. In practice, TR will optimize pretty much any floating-point computation. In the case of fixnum operations, it optimizes only when it can guarantee that no overflow will happen. This means that you may need to help it a bit if you want to get fixnum optimizations. To see how TR optimizes your code (for example, to make sure that you get all the optimizations you want), check out the "performance report" DrRacket tool. > I chose to optimize my program (partly > to learn how) incrementally, trying all the options, timing at every > step with debugging info turned off. This worked until I wanted to > convert Integers to Fixnums in Typed Racket (which has been giving me > much faster results than anything in untyped Racket). You don't need to convert between integers and fixnums. Fixnums are simply integers that are small enough to be represented as tagged machine integers. If an operation on fixnums would cause an overflow, the result is transparently promoted to a bignum instead. To use fixnums in TR, you can annotate your variables as being of `Fixnum' type. However, due to the promotion semantics, fixnums have pretty bad closure properties, which means that the result of, say, adding two fixnums is not guaranteed to be a fixnum itself and has to be given the `Integer' type. To help with this, TR provides an `Index' type which is for integers bounded by the length of the longest possible vector (smaller than a fixnum). Adding two of these is guaranteed to produce a `Fixnum'. The bottom line is that it's possible to get fixnum optimizations in TR, but since TR has to be conservative in order to be safe, sometimes you may have to use unsafe fixnum operations manually to get the performance you want. > The problem is that I can't find a way to convert a Float to a Fixnum, > only to an Integer. None of fl->fx, unsafe-fl->fx, or > fl->exact-integer work, as Type Checker tells me they're untyped > identifiers. That should work. I'll look into that. Vincent Racket Users list: http://lists.racket-lang.org/users
Re: [racket] Optimization; converting 'Float' to 'Fixnum' in Typed Racket
On Sat, Feb 18, 2012 at 9:39 PM, SF wrote: > On Sat, Feb 18, 2012 at 9:18 PM, Robby Findler wrote: >> I'm not sure of the precise answer, but I don't think that all floats >> (even the integers) have a corresponding fixnum. > > My C brain wonders why I can't just cast it to get the lower bits, I > don't care about overflow. I'm not sure if this will fit in with how Typed Racket works, but I guess you could write an ffi-based function that actually fiddles with the low-level representation to just get at the bits you want. But, actually, I think that maybe that won't work because Racket's floats are usually boxed, unless the compiler can "see" everywhere they go and can manage to pass around unboxed versions (something that TR facilitates, I believe). So, if you were to pass them off to an unknown (from the compiler & TR's perspective) function, then they'd fall back to boxing and you'd lose all the efficiency gains. I guess there would have to be some new primitive added to make this work. Of course, I could be missing out on one of the existing prims. Maybe one of the TR/runtime system experts'll fill us in. Robby Racket Users list: http://lists.racket-lang.org/users
Re: [racket] Optimization; converting 'Float' to 'Fixnum' in Typed Racket
On Sat, Feb 18, 2012 at 9:35 PM, SF wrote: > On Sat, Feb 18, 2012 at 9:18 PM, Robby Findler wrote: >> I'm not sure of the precise answer, but I don't think that all floats >> (even the integers) have a corresponding fixnum. > > My C brain wonders why I can't just cast it to get the lower bits, I > don't care about overflow. > > Using fixnum? does indeed work, just far too slowly. I'm not sure what's really going on in your code, and this may not be possible, but probably you want to arrange things so you don't have to do that conversion inside any loops. > Still, good to > know. I didn't think of using Typed Racket like that. > > I should mention that this is the best method I've found so far: > > (: float->int (Float -> Integer)) > (define (float->int x) > (floor (inexact->exact (floor x ; both floors are necessary Why is the second floor necessary? Just for the type system or are there inexact integers that become exact non-integers? Robby Racket Users list: http://lists.racket-lang.org/users
Re: [racket] Optimization; converting 'Float' to 'Fixnum' in Typed Racket
On Sat, Feb 18, 2012 at 9:18 PM, Robby Findler wrote: > I'm not sure of the precise answer, but I don't think that all floats > (even the integers) have a corresponding fixnum. My C brain wonders why I can't just cast it to get the lower bits, I don't care about overflow. Using fixnum? does indeed work, just far too slowly. Still, good to know. I didn't think of using Typed Racket like that. I should mention that this is the best method I've found so far: (: float->int (Float -> Integer)) (define (float->int x) (floor (inexact->exact (floor x ; both floors are necessary Racket Users list: http://lists.racket-lang.org/users
Re: [racket] Optimization; converting 'Float' to 'Fixnum' in Typed Racket
I'm not sure of the precise answer, but I don't think that all floats (even the integers) have a corresponding fixnum. You could probably turn it into an integer and then use fixnum? to determine if it is a fixnum (signalling an error otherwise) and then inside the true branch of a test, you might find that you're all set. Meanwhile, I'm really replying because it sounds like your doing timing tests inside DrRacket. You should probably run your timing tests from the command-line, and use racket directly. DrRacket is doing lots of stuff behind the scenes that can mess up timing tests. Robby On Sat, Feb 18, 2012 at 8:07 PM, SF wrote: > I'm trying to optimize some code that processes a bunch of data, > basically image pixels, which currently takes on the order of several > seconds and seems like it should be much faster (important because > it's an interactive application). Coming from C++ I have a good idea > in my mind of how I'd write it with low-level operations. I read up on > Racket optimization. It is still somewhat unclear to me how Racket > deals with fixnums, flonums, unsafe operations, Typed Racket types, > and how it all fits together. I chose to optimize my program (partly > to learn how) incrementally, trying all the options, timing at every > step with debugging info turned off. This worked until I wanted to > convert Integers to Fixnums in Typed Racket (which has been giving me > much faster results than anything in untyped Racket). > > The problem is that I can't find a way to convert a Float to a Fixnum, > only to an Integer. None of fl->fx, unsafe-fl->fx, or > fl->exact-integer work, as Type Checker tells me they're untyped > identifiers. Strangely, it doesn't complain with other things from > racket/unsafe/ops and racket/fixnum. Ideally, it'd be nice to have a > function that works like a cast in C++, rounding down the float to get > an int efficiently. Should I not be trying to use Fixnums? Are they > just as efficient as Integers? Using a C module is one possible > solution, are there any others? Would love some light shed on this > topic. > > Racket Users list: > http://lists.racket-lang.org/users Racket Users list: http://lists.racket-lang.org/users
