Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Herbie: Automatically improve imprecise floating point formulas

herbie.uwplse.org

Post reply on HN
Print view View original

21–30 of 47 posts

Re: Herbie: Automatically improve imprecise floating point formulas

#21

Post by FabHK »

lifthrasiir wrote: post #14
notpushkin wrote: post #13

Some trivial cases produce... interesting results. For x in [−1.79e308, 1.79e308]: Initial Program: 100.0% accurate, 1.0× speedup def code(x): return math.sqrt((x + 1.0)) Alternative 1: 67.5% accurate, 5.6× speedup def code(x): return 1.0

That does make sense, because a half of all available fp numbers are less than 1 in their magnitude. In particular there should be a plenty of numbers x such that |x| << 1 so x + 1 ~= 1; in fact, the proportion should be just shy of 50%.

Not really. 1+x/2, however, would be a good approximation to sqrt(1+x) for small (in absolute value) x.

Re: Herbie: Automatically improve imprecise floating point formulas

#22

Post by shiandow »

I wonder who decided to use a step function for the speed accuracy plot. They must have thought the convex hull would be wrong because you can't really make linear combinations of algorithms (you could, but you'd have to use time not speed to make it linear). So I get why you would use step functions, but the step is the wrong way around. The current plot suggests accuracy doesn't drop if you need higher speeds

Re: Herbie: Automatically improve imprecise floating point formulas

#23

Post by andrepd »

perching_aix wrote: post #20
andrepd wrote: post #18

I don't quite understand how they define "accuracy".

Could you substantiate that a bit more? I don't see what'd be hard to understand about it at a skim.

Is it an arithmetic average of relative error over the given range? Because if yes then it can be misleading, and potentially a bad meshes to rank alternatives (though the HTML report includes a graph over the input range, which is quite nice, so I'm talking only about the accuracy number).

In the limit, an alternative with 10x better accuracy when x>10^150 and 10x worse in 1Furthermore, floats have underflow to 0 and overflow to infinity, which screw all this up because it can lead to infinite relative error.

Because of this you have some of the funny cases reported elsewhere in this thread :p

I'm not sure what would be a better approach though. Weigh the scores with a normal distribution around 0? Around 1? Exponents around 0?

Re: Herbie: Automatically improve imprecise floating point formulas

#25

Post by Archit3ch »

summarity wrote: post #19

I posted this and it picked up steam over night, so I thought I'd add how I'm using it: I work on 3D/4D math in F#. As part of the testing strategy for algorithms, I've set up a custom agent with an F# script that instruments Roslyn to find FP and FP-in-loop hotspots across the codebase. The agent then reasons through the implementation and writes core expressions into an FPCore file next to the existing tests, runni…

> I work on 3D/4D math in F#. As part of the testing strategy for algorithms, I've set up a custom agent with an F# script that instruments Roslyn to find FP and FP-in-loop hotspots across the codebase.

I don't know if there is an equivalent in Roslyn, but in Julia you can have the agent inspect the LLVM output to surface problems in hot loops.

Re: Herbie: Automatically improve imprecise floating point formulas

#26

Post by pavpanchekha »

shiandow wrote: post #22

I wonder who decided to use a step function for the speed accuracy plot. They must have thought the convex hull would be wrong because you can't really make linear combinations of algorithms (you could, but you'd have to use time not speed to make it linear). So I get why you would use step functions, but the step is the wrong way around. The current plot suggests accuracy doesn't drop if you need higher speeds

It was me. Damn it you're right! Will fix!

Re: Herbie: Automatically improve imprecise floating point formulas

#27

Post by pavpanchekha »

cocoto wrote: post #15
lifthrasiir wrote: post #14

Earlier quoted context omitted.

That does make sense, because a half of all available fp numbers are less than 1 in their magnitude. In particular there should be a plenty of numbers x such that |x| << 1 so x + 1 ~= 1; in fact, the proportion should be just shy of 50%.

But I guess using the density distribution of floating points is rarely useful in a problem. Your actual distribution will almost surely be way different. Imo, the tool presented here should provide a way to manually provide a custom density function (with some common presets like uniform and normal distributions).

Author here! Yes, the float distribution isn't what you want in practice, but distribution selector isn't really the right thing either, because a low probability bad result can still be pretty bad! Hence the range selector; the float distribution is good at picking extreme values that trigger FP error.

We usually recommend looking for 90%+ accuracy or carefully examining the accuracy plot

Re: Herbie: Automatically improve imprecise floating point formulas

#28

Post by pavpanchekha »

LiamPowell wrote: post #12
yossi_peti wrote: post #4

Earlier quoted context omitted.

The precondition on the link you shared has -1 <= x && x <= 1, so 99 is way outside of that range. But even so, testing for x=1, which is supposed to be inside that range, 0.5 doesn't seem tolerably close to 0.4142.

I have a suspicion that the accuracy number is the mean of accuracies over all valid floats in the range (or something approximating that), which is going to be weighted towards zero where the accuracy is higher, and perhaps where sqrt near 1 has some artefacts.

It is, there's a page in the documentation about how errors are defined. Let me also add: Herbie generally gives the most accurate option it found first, and then the other stuff might be useful for speed (0.5x is way faster than two square roots and a divide!) but it's not as accurate

Re: Herbie: Automatically improve imprecise floating point formulas

#29

Post by pavpanchekha »

fluorinerocket wrote: post #6
hmpc wrote: post #3

Earlier quoted context omitted.

Check the specification at the top. The range for x is [-1, 1]. For the range you provided the accuracy of the 0.5x alternative is reported as only 33%: https://herbie.uwplse.org/demo/570b973df0f1f4a78fe791858038a...

You're right I misread the graph. That said though I have played around with Herbie before, trying it out on a few of the more gnarly expressions I had in my code (analytical partial derivatives if equations of motion if launch vehicle in rotating spherical frame) and didn't see much appreciable improvement over the expected range of values, but then again I didn't check every single one. What would be cool is if you…

Author here. I've got a few papers about this problem (including one in submission), but it is very very hard to do, especially with acceptable overhead. The state of the art is maybe 100x overhead.

Re: Herbie: Automatically improve imprecise floating point formulas

#30

Post by pavpanchekha »

bee_rider wrote: post #5

I wonder, is there a way to only request reformulations that don’t involve branches? The tool already seems quite nice, but that might be a good feature. Also, I’m not sure I understand the speedup. Is it latency or throughput?

Author here. The speed up is modeled throughput, though the model is relatively naive. It's possible to disable branches by turning off the regimes flag, see https://herbie.uwplse.org/doc/1.0/options.html
Post reply on HN