<html><head></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">Wow, thanks for all the analysis on this, Daniel!<div><br></div><div>So, I think the summary of your evaluation is that realToFrac does just fine in almost all cases due to careful optimization and outperforms my floatToFloat trick (which answers the question I flagrantly begged... ;~) except that I can't access those optimizations because the OpenGL types are hidden behind newtypes and buried in a library.</div><div><br></div><div>I've confirmed your results to make sure I could.</div><div><br></div><div>I went a step further and typed convert for GLclampf expecting to see unoptimized performance, but it ran just as fast as Double-&gt;Float.<br><div><br></div><div><font class="Apple-style-span" face="'Courier New'">convert :: Double -&gt; GL.GLclampf</font></div><div><font class="Apple-style-span" face="'Courier New'">convert = realToFrac</font></div><div><br></div><div>And still ran faster than floatToFloat. &nbsp;However there's no denying that floatToFloat runs *much* faster than realToFrac in the larger application. &nbsp;Profiling shows floatToFloat taking about 50% of my CPU time, but the frame rate is close to (though not quite) 30 fps. &nbsp;Using realToFrac takes seconds just to display the first frame.&nbsp;</div><div><br></div><div>As it stands, floatToFloat is responsible for 50% of my CPU time which I think is mainly a tribute the OpenGL implementation, but still makes it the obvious target for optimization. &nbsp;Having gotten all excited about the new tool in my box, I wrote the following rule:</div><div><br></div><div><font class="Apple-style-span" face="'Courier New'">{-# RULES<br>"floatToFloat/id" floatToFloat=id<br>"floatToFloat x2" floatToFloat . floatToFloat = floatToFloat<br>&nbsp;#-}</font></div><div><br></div><div>Neither of which seems to fires in this application, but I did get the first one to fire by importing the same file into my benchmark.</div><div><br></div><div>The next obvious step is to optimize a level up in the call hierarchy, and rewrite coordToCoord2D since I know my original pair2vertex function was faster. &nbsp;So, I added this rule in the file where Vertex2 is made an instance of Coord2D:</div><div><br></div><div><font class="Apple-style-span" face="'Courier New'">{-# RULES<br>"coordToCoord2D/p2v2" &nbsp;coordToCoord2D = pair2vertex&nbsp;<br>&nbsp;#-}<br></font><br></div><div>which refers to two functions, each in different files (I don't think that matters, but mention it just in case)</div><div><br></div><div><font class="Apple-style-span" face="'Courier New'">pair2vertex :: (Num a) =&gt; (a,a) -&gt; GL.Vertex2 a<br>pair2vertex (x,y) = GL.Vertex2 x y&nbsp;<br><br></font></div><div><font class="Apple-style-span" face="'Courier New'">coordToCoord2D :: (Coord2D a, Coord2D b) =&gt; a -&gt; b<br>coordToCoord2D = fromCartesian2D . toCartesian2D<br></font><br></div><div><br></div><div>directly after my coordToCoord2D definition I have this rule as well:</div><div><br><font class="Apple-style-span" face="'Courier New'">{-# RULES<br>"coordToCoord2D/id" coordToCoord2D = id<br>"coordToCoord2D x2" coordToCoord2D . coordToCoord2D = coordToCoord2D<br>&nbsp;#-}<br></font><br></div><div><br></div><div>I get a compile time error that I can't make sense of. &nbsp;It's asking me to put a context on my rule, but I can't find any references on how to do that...</div><div><br></div><div>-----------</div><div><br></div><div><div>&nbsp;&nbsp; &nbsp;Could not deduce (Num a)</div><div>&nbsp;&nbsp; &nbsp; &nbsp;from the context (Coord2D (Vertex2 a), Coord2D (a, a))</div><div>&nbsp;&nbsp; &nbsp; &nbsp;arising from a use of `pair2vertex'</div><div>&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; at GCB/OpenGL/Geometry.hs:32:40-50</div><div>&nbsp;&nbsp; &nbsp;Possible fix:</div><div>&nbsp;&nbsp; &nbsp; &nbsp;add (Num a) to the context of the RULE "coordToCoord2D/p2v2"</div><div>&nbsp;&nbsp; &nbsp;In the expression: pair2vertex</div><div>&nbsp;&nbsp; &nbsp;When checking the transformation rule "coordToCoord2D/p2v2"</div></div><div><br></div><div><br></div><div>-----------</div><div><br></div><div>The file:line:column is the "pair2vertex" token in the rule I list above.</div><div><br></div><div>Cheers--</div><div>&nbsp;Greg</div><div><br></div><div><br><div><div>On Sep 15, 2010, at 3:36 PM, Daniel Fischer wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><div>On Wednesday 15 September 2010 20:50:13, Greg wrote:<br><blockquote type="cite">I hadn't come across rewrite rules yet. &nbsp;They definitely look like<br></blockquote><blockquote type="cite">something worth learning,<br></blockquote><br>Absolutely. GHC's optimiser is good, but there are a lot of cases where you <br>need to push it via rewrite rules if you write polymorphic code or if you <br>want to eliminate intermediate data structures (e.g. list fusion).<br><br><blockquote type="cite">though I'm not sure I'm prepared to start making custom versions<br></blockquote><blockquote type="cite">of OpenGL.Raw...<br></blockquote><br>Yes, if you can work around the issues without that, it's better to leave <br>it in peace :)<br>Though you might ask the maintainer for rewrite rules.<br><br><blockquote type="cite"><br></blockquote><blockquote type="cite">It looks like I managed to put that battle off for another day, however.<br></blockquote><blockquote type="cite">&nbsp;I did look at how realToFrac is implemented and (as you mention) it<br></blockquote><blockquote type="cite">does the fromRational . toRational transform pair suggested in a number<br></blockquote><blockquote type="cite">of sources, including Real World Haskell. &nbsp;Looking at what toRational is<br></blockquote><blockquote type="cite">doing, creating a ratio of integers out of a float it seems like a crazy<br></blockquote><blockquote type="cite">amount of effort to go through just to convert floating point numbers.<br></blockquote><br>I just did some benchmarking.<br><br>I benchmarked<br><br>foldl' (+) 0 [convert (1 / intToDoub k) | k &lt;- [1 .. 100000]]<br><br>where<br><br>intToDoub :: Int -&gt; Double<br>intToDoub = fromIntegral<br><br>for several functions<br><br>convert :: Double -&gt; Float (actually, the type has been<br>(RealFloat a, RealFloat b) =&gt; a -&gt; b, but it was used at a = Double,<br>b = Float).<br>Everything was compiled with -O2, so the rewrite rules fired, in particular <br>intToDoub was replaced by a primop (int2Double#), so that one's ultra <br>cheap.<br><br>For convert = realToFrac (hence by the rewrite rules the primop <br>double2Float# was used), I got pretty good times, mean was 6.76 ms.<br><br>For convert = floatToFloat from below, the times were not too bad, with a <br>mean of 26.3 ms.<br>A factor of roughly four for this benchmark (the factor for the conversion <br>itself will be higher, but not exorbitantly) means it's usable in many <br>situations, but not in performance critical situations where the conversion <br>takes a significant amount of the running time. If you're converting to <br>draw stuff with OpenGL (or some other graphics library), the conversion <br>will take only a relatively small part of the time, so it's fine.<br><br>For convert = fromRational . toRational (so no rewrite rules), the times <br>were rather appalling: mean was 3.34 seconds.<br>A factor of nearly 500 versus double2Float#.<br><br>toRational is bad. Looking at<br><br>instance &nbsp;Real Double &nbsp;where<br> &nbsp;&nbsp;&nbsp;toRational x &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;= &nbsp;(m%1)*(b%1)^^n<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;where (m,n) = decodeFloat x<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;b &nbsp;&nbsp;&nbsp;&nbsp;= floatRadix &nbsp;x<br><br>(same for Float), and the implementations of (^^) and (^),<br><br>{-# SPECIALISE (^) ::<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Integer -&gt; Integer -&gt; Integer,<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Integer -&gt; Int -&gt; Integer,<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Int -&gt; Int -&gt; Int #-}<br>(^) :: (Num a, Integral b) =&gt; a -&gt; b -&gt; a<br>x0 ^ y0 | y0 &lt; 0 &nbsp;&nbsp;&nbsp;= error "Negative exponent"<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;| y0 == 0 &nbsp;&nbsp;= 1<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;| otherwise = f x0 y0<br> &nbsp;&nbsp;&nbsp;where -- f : x0 ^ y0 = x ^ y<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;f x y | even y &nbsp;&nbsp;&nbsp;= f (x * x) (y `quot` 2)<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;| y == 1 &nbsp;&nbsp;&nbsp;= x<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;| otherwise = g (x * x) ((y - 1) `quot` 2) x<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-- g : x0 ^ y0 = (x ^ y) * z<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;g x y z | even y = g (x * x) (y `quot` 2) z<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;| y == 1 = x * z<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;| otherwise = g (x * x) ((y - 1) `quot` 2) (x * z)<br><br>-- | raise a number to an integral power<br>{-# SPECIALISE (^^) ::<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Rational -&gt; Int -&gt; Rational #-}<br>(^^) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;:: (Fractional a, Integral b) =&gt; a -&gt; b -&gt; a<br>x ^^ n &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;= &nbsp;if n &gt;= 0 then x^n else recip (x^(negate n))<br><br>together with the multiplication and recip for Rationals, I have to say <br>ouch!<br>There's no special implementation and rewrite rule for powers of Rationals, <br>so on each multiplication in (^), the gcd of numerator and denominator is <br>calculated, *although as powers of the original numerator and denominator <br>they are guaranteed to be coprime*. Considering how slow a division of <br>Integers is, awwwwwww noooooo.<br><br>So let's look at a better implementation of toRational:<br><br>toRat :: RealFloat a =&gt; a -&gt; Rational<br>toRat x = case decodeFloat x of<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(m,e) -&gt; case floatRadix x of<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;b -&gt; if e &lt; 0<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;then (m % (b^(negate e)))<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else (m * b^e) :% 1<br><br>(inlined a better implementation of powers for Rationals).<br><br>Benchmarking convert = fromRational . toRat show a significant improvement, <br>the mean dropped to 2.75 seconds.<br>Still appalling, but it's a nice improvement and I don't see any quick <br>opportunities to improve that conversion.<br><br>So let's come to the last, fromRational. That's a compicated function, and <br>unfortunately it has to be and I've no good idea to improve it.<br>fromRational is really evil (in terms of clock cycles).<br>Replacing fromRational with a dummy that just forces the evaluation of its <br>argument and returns NaN, ±Infinity, or 0 for all real Rational values,<br><br>dummy . toRational had a mean of 623.5 ms and<br>dummy . toRat had a mean of 200.7 ms.<br><br>So toRat is a jolly good improvement over toRational, but it's still <br>awfully slow. And since fromRational takes much much longer anyway, it's a <br>not too impressive gain for realToFrac.<br><br><blockquote type="cite"><br></blockquote><blockquote type="cite">Looking at the RealFloat class rather that Real and Fractional, it seems<br></blockquote><blockquote type="cite">like this is a much more efficient way to go:<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">floatToFloat :: (RealFloat a, RealFloat b) =&gt; a -&gt; b<br></blockquote><blockquote type="cite">floatToFloat = (uncurry encodeFloat) . decodeFloat<br></blockquote><br>Yes, that's much more efficient, as witnessed by the benchmark results.<br>But.<br><br><blockquote type="cite"><br></blockquote><blockquote type="cite">I substituted this in for realToFrac and I'm back to close to my<br></blockquote><blockquote type="cite">original performance. &nbsp;Playing with a few test cases in ghci, it looks<br></blockquote><blockquote type="cite">numerically equivalent to realToFrac.<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">This begs the question though--<br></blockquote><br>No. Sorry, but I can't bear that misuse: <br><a href="http://en.wikipedia.org/wiki/Begging_the_question">http://en.wikipedia.org/wiki/Begging_the_question</a><br><br>It raises/demands/invites the question, but it doesn't beg it.<br><br><blockquote type="cite">am I doing something dangerous here?<br></blockquote><br>Yes and no.<br><br><blockquote type="cite">&nbsp;Why isn't this the standard approach?<br></blockquote><br>Because it will wreak unspeakable havoc when someone creates a RealFloat <br>instance with a floatRadix &gt; 2. A floatRadix of 10 or some power of 2 (16, <br>256?) could be even reasonable.<br><br>But for conversions between RealFloat types with the same floatRadix, it's <br>sort of okay, only it clobbers NaNs and (for some conversions) Infinities.<br>However, realToFrac does that too.<br><br><blockquote type="cite"><br></blockquote><blockquote type="cite">If I understand what's happening, decodeFloat and encodeFloat are<br></blockquote><blockquote type="cite">breaking the floating point numbers up into their constituent parts--<br></blockquote><blockquote type="cite">presumably by bit masking the raw binary.<br></blockquote><br>Probably.<br><br><blockquote type="cite">That would explain the<br></blockquote><blockquote type="cite">performance improvement. &nbsp;I suppose there is some implementation<br></blockquote><blockquote type="cite">dependence here, but as long as the encode and decode are implemented as<br></blockquote><blockquote type="cite">a matched set then I think I'm good.<br></blockquote><br>Not entirely matched, for Float -&gt; Float and Double -&gt; Double, <br>NaN -&gt; -Infinity, maybe denormalized values break too.<br><br>±Infinity is mapped to a finite value at Float -&gt; Double<br><br>But since toRational uses decodeFloat and fromRational uses encodeFloat, <br>floatToFloat is in that respect no worse than realToFrac without rewrite <br>rules.<br><br><blockquote type="cite"><br></blockquote><blockquote type="cite">Cheers--<br></blockquote><blockquote type="cite">&nbsp;Greg<br></blockquote><br></div></blockquote></div><br></div></div></body></html>