New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
FPU: Support platforms without round-towards-infinity #2791
Comments
I am unlikely to be at the next meeting. |
@mglisse did you already start a branch for option 1, I'd be curious to see the slow down in practice. |
@sloriot no, I haven't experimented with anything like that. For a quick try, I guess you could just redefine CGAL_IA_ADD, etc. |
LLVM 8, just released, has now an official WebAssembly target: |
I'm taking a look at option 1. But I'm not sure I understand how Interval_nt.h is supposed to be working. I see
These looks safe for round-to-nearest to me (please tell me if I am wrong)
But I don't understand
In is_same I see:
which does make sense -- why are we comparing inf with sub in compare, but inf with inf and sub with sub in is_same? |
Basically, the rounding mode only matters when you update the interval with |
|
We have For option 1, I think you want to look at macros like CGAL_IA_ADD since that's the operation that needs rounding. |
Ok, that makes sense -- I was worried that I'd misunderstood inf and sup. Looking at + I see
Based on
So this is really expressing
Which makes sense as it gives a conservative interval around the result. But I think it also means that it needs to be fixed at a higher level than CGAL_IA_ADD, since CGAL_IA_ADD doesn't know which way you want to round the result. Does that sound right to you? |
Actually, I believe CGAL_IA_ADD always needs to round towards +infinity. And then we use tricks like -CGAL_IA_ADD(-x,-y) to compute an addition rounded towards -infinity without changing the rounding mode. |
I think the key here is that -OP(-a, -b) only works with round towards +infinity, which we don't support here. I think that CGAL_IA_ADD_UP and CGAL_IA_ADD_DOWN would be a suitable abstraction for this case. I agree that inline functions would probably be a better choice than macros. I think that I was a bit off earlier, and it should effectively be
Although maybe we can get away with
What do you think? |
CGAL_IA_ADD_DOWN(a,b) and -CGAL_IA_ADD_UP(-a,-b) still look similar to me. |
Yes. I see what you mean, but don't you want We need the rounding to apply before the operation in order to get a conservative result, right? |
a.sup is an upper bound on a, b.sup is an upper bound on b, computing a.sup+b.sup with upwards rounding is an upper bound on a+b. Now, if n is x+y computed with the default to-nearest rounding and u is x+y computed with upwards rounding, either u is n or u is nextafter(n,+inf), and in all cases nextafter(n,+inf) is an upperbound on u. |
Let's imagine that both a and b were rounded down toward nearest, could we undershoot the result? e.g., (in an imaginary system) 10.1 + 10.1, rounded down to 10 + 10, giving 20 which we round up to 20.1, but ought to actually be 20.3? I think in general, at least it needs to be up(a) OP up(b) , at least with MUL and DIV -- but perhaps we could get away with it for ADD if we can be sure about it ... |
There is no such thing as "a and b were rounded down toward nearest". Let me use capital letters for the mathematical exact value (infinite precision). The invariant is that a.inf() <= A <= a.sup(). All we want is to preserve this invariant in operations. If A is 10.1, then there is no way a.sup() can be 10. |
Ok, providing a.inf() <= A <= a.sup() is initially true, then it should remain that way. Do we need to fix the constructor to be conservative? Or is it sufficient that <= for double on that system is consistent about it? |
They already are. The original value is assumed to be exact, whether it is an int, double, Gmpq or whatnot, and the conversion produces an interval that contains the original value. For int or double, an interval with inf==sup is sufficient. For Gmpq, the interval may be larger. |
Hmm, I don't see a constructor for Interval_nt from Gmpq or any exact non-integer value. I've started testing the What I've done so far is to split out a variant of Protect_FPU_rounding which enforces CGAL_FE_TONEAREST and have Interval_nt use this instead, and to force always setting and backing up mode to work around assumptions of inheriting the expected mode. I've also been trying to use values like Can you let me know if that sounds reasonable? I've been getting some exceptions still, so either I'm doing something fundamentally wrong, or I've missed something somewhere. |
Look for |
I tried this hack to see what happens diff --git a/Number_types/include/CGAL/FPU.h b/Number_types/include/CGAL/FPU.h
index 6d5f02a3075..693a92279dd 100644
--- a/Number_types/include/CGAL/FPU.h
+++ b/Number_types/include/CGAL/FPU.h
@@ -117,7 +117,7 @@ extern "C" {
#if defined(CGAL_HAS_SSE2) && (defined(__x86_64__) || defined(_M_X64))
# define CGAL_USE_SSE2 1
#endif
-
+#undef CGAL_USE_SSE2
#ifdef CGAL_CFG_DENORMALS_COMPILE_BUG
double& get_static_minimin(); // Defined in Interval_arithmetic_impl.h
#endif
@@ -347,16 +347,17 @@ inline double IA_bug_sqrt(double d)
// With GCC, we can do slightly better : test with __builtin_constant_p()
// that both arguments are constant before stopping one of them.
// Use inline functions instead ?
-#define CGAL_IA_ADD(a,b) CGAL_IA_FORCE_TO_DOUBLE((a)+CGAL_IA_STOP_CPROP(b))
-#define CGAL_IA_SUB(a,b) CGAL_IA_FORCE_TO_DOUBLE(CGAL_IA_STOP_CPROP(a)-(b))
-#define CGAL_IA_MUL(a,b) CGAL_IA_FORCE_TO_DOUBLE(CGAL_IA_STOP_CPROP(a)*CGAL_IA_STOP_CPROP(b))
-#define CGAL_IA_DIV(a,b) CGAL_IA_FORCE_TO_DOUBLE(CGAL_IA_STOP_CPROP(a)/CGAL_IA_STOP_CPROP(b))
+inline double CGAL_IA_UP(double d){return nextafter(d,std::numeric_limits<double>::infinity());}
+#define CGAL_IA_ADD(a,b) CGAL_IA_UP((a)+CGAL_IA_STOP_CPROP(b))
+#define CGAL_IA_SUB(a,b) CGAL_IA_UP(CGAL_IA_STOP_CPROP(a)-(b))
+#define CGAL_IA_MUL(a,b) CGAL_IA_UP(CGAL_IA_STOP_CPROP(a)*CGAL_IA_STOP_CPROP(b))
+#define CGAL_IA_DIV(a,b) CGAL_IA_UP(CGAL_IA_STOP_CPROP(a)/CGAL_IA_STOP_CPROP(b))
inline double CGAL_IA_SQUARE(double a){
double b = CGAL_IA_STOP_CPROP(a); // only once
- return CGAL_IA_FORCE_TO_DOUBLE(b*b);
+ return CGAL_IA_UP(b*b);
}
#define CGAL_IA_SQRT(a) \
- CGAL_IA_FORCE_TO_DOUBLE(CGAL_BUG_SQRT(CGAL_IA_STOP_CPROP(a)))
+ CGAL_IA_UP(CGAL_BUG_SQRT(CGAL_IA_STOP_CPROP(a)))
#if defined CGAL_SAFE_SSE2
@@ -476,6 +477,7 @@ inline
FPU_CW_t
FPU_get_cw (void)
{
+ return CGAL_FE_TONEAREST;
FPU_CW_t cw;
CGAL_IA_GETFPCW(cw);
return cw;
@@ -487,6 +489,7 @@ inline
void
FPU_set_cw (FPU_CW_t cw)
{
+ return;
CGAL_IA_SETFPCW(cw);
}
@@ -494,6 +497,7 @@ inline
FPU_CW_t
FPU_get_and_set_cw (FPU_CW_t cw)
{
+ return CGAL_FE_TONEAREST;
FPU_CW_t old = FPU_get_cw();
FPU_set_cw(cw);
return old;
diff --git a/Number_types/include/CGAL/Interval_nt.h b/Number_types/include/CGAL/Interval_nt.h
index 8a51e7cd860..80e0d0b07e5 100644
--- a/Number_types/include/CGAL/Interval_nt.h
+++ b/Number_types/include/CGAL/Interval_nt.h
@@ -1148,7 +1148,7 @@ namespace INTERN_INTERVAL_NT {
// - compute y = CGAL_IA_SQUARE(x)
// - if y==d.inf() use x, else use -CGAL_IA_SUB(CGAL_IA_MIN_DOUBLE,x)
FPU_set_cw(CGAL_FE_DOWNWARD);
- double i = (d.inf() > 0.0) ? CGAL_IA_SQRT(d.inf()) : 0.0;
+ double i = (d.inf() > 0.0) ? nextafter(std::sqrt(d.inf()), 0.) : 0.0;
FPU_set_cw(CGAL_FE_UPWARD);
#endif
return Interval_nt<Protected>(i, CGAL_IA_SQRT(d.sup())); The tests Interval_nt(_new).cpp fail in several places that assume that the computation of intervals is as tight as possible, which is obviously not going to be the case here, but that's something to handle in the tests. The precise tests need to be skipped when using sloppy intervals, and new relaxed tests need to be implemented. |
Yes, that's pretty much what I have -- thanks for the reference. :) However, I find that when I try to run corefinement_mesh_union.cpp with an Epeck kernel with these modifications, it starts to fail with
I've added CGAL_ALWAYS_ROUND_TO_NEAREST to control the modifications, and with this set false it works as expected -- so the basic kernel configuration seems sound. Which leads me to two theories. (a) Rounding mode requirements outside of Interval_nt are being violated, or To test (a) I've built out a second Protect_FPU_Rounding_2 class, and forced them to always set and reset on each operation. This should mean that the rest of the system continues rounding as per usual, and can be incrementally opted in to CGAL_ALWAYS_ROUND_TO_NEAREST. To test (b) I've changed the Interval_nt operations to return I hope this means that it falls back to the exact kernel for these operations, allowing us to effectively turn them on and off. Does my understanding in (b) seem correct? |
Having written that out, I realized that I can more directly test the Interval_nt ops by simply forcing the rounding mode inside each. This let me bisect the problem down to here:
So I guess CGAL_IA_DIV requires a bit more thought, although I'm not sure why the issue doesn't manifest on the other CGAL_IA_DIV paths -- perhaps they're just not sufficiently exercised. I'll take a closer look at it tomorrow -- but thought you might have some insight. :) |
"corefinement_mesh_union.cpp with an Epeck kernel": that doesn't even compile on master. It would be easier to understand your comments if they referred to some public branch, showed a command line, etc. |
Hmm, I can't see any reason that corefinement ought not work with Epeck -- isn't this essential for being able to produce non-self-intersecting meshes for incremental operation? Here is what I am using.
The build environment I have for wasm is not an easy fit to how cgal is normally set up, so it's not easy to share at the moment. -- Having investigated a bit further, it turns out that in some case cases a / b needs to be bumped upward by two steps in round-to-nearest to match what happens in round-upward. Having bumped the result up twice in this case, the example successfully completes. I'm not sure why this is so, but it should be straight-forward to investigate now that we have particular values. If you're interested, one set of example values is:
Perhaps it is due to something like excess precision. -- What I still don't understand is why returning largest() from INTERN_INTERVAL_NT's / operator doesn't cause it to fall back gracefully to the exact operation. Would you expect returning largest() to cause it to fall back to the exact operation, or am I confused about how intervals are supposed to work? |
When I tried yesterday, it failed because of a call to sqrt, which doesn't work with Epeck. |
This test passes here with the patch I posted. |
Before you start running that modified CGAL code in the WASM environment, you should first debug it in the usual host environment (probably using an x86_64 processor). |
Good advice. :) I rebuilt CGAL and the dependencies and made sure that the compilation options were aligned between the x86 and wasm builds. Having done that, I still had issues under wasm but was able to produce readable backtraces in the browser and track them down. I am still testing the results, but they seem plausible so far. There will need to be some additional work to eliminate the dependency on catching Uncertain_conversion_exception in Filtered_predicate.h, as this produces major overhead, but it is not necessary for correctness and can be handled independently. Thanks for all of your help -- CGAL internals made a good deal more sense to me now. |
Er, catching this exception there is a very important part of CGAL's filtering strategy, getting rid of it doesn't seem trivial. I understand that c++ exceptions are still a second class feature in wasm (https://github.com/WebAssembly/exception-handling/ indicates this may change eventually), but it looks like emscripten can handle them, at some cost. |
Yes -- it would require a different mechanism to coordinate the filters. The cost is pretty huge -- the wasm becomes about 160% of the size (3.2M to 5.2M) and the latency is only about 65% that with simple gmpq. Anyhow, we can worry about that independently of this. :) |
I've put together a PR, but suspect it needs restructuring. In particular I'm not sure what branch I should be targeting, and I'm not sure about the test organization. |
I'm re-opening this issue as I've found a possible problem. Using the following test program (under Surface_mesh/test/Surface_mesh) I've found some unexpected behavior with CGAL_ALWAYS_ROUND_TO_NEAREST.
This produces the following output for me with CGAL_ALWAYS_ROUND_TO_NEAREST true.
But with CGAL_ALWAYS_ROUND_TO_NEAREST false the values are unchanged. This shouldn't be happening, right? :) |
What is in the file Note that you use an ASCII precision of 20, but
Probably what you see is a strange effect of the algorithm that converts from binary to ASCII for floating point values, with |
For |
The effect remains with setprecision(17). Surface_mesh/test/Surface_mesh/sm_off_io_input.off used here contains
So I think this may be a real deviation. |
Sounds like what happens when we convert an interval (from Lazy_exact_nt) to double? |
... You are right! The kernel is |
Ok, so is the problem that it's not calling exact() before converting to double? |
Ok, so I've confirmed that calling exact() before converting to double addresses the problem. I think this means that it is due to converting an interval to a double, and this is not an issue with CGAL_ALWAYS_ROUND_TO_NEAREST. Thanks. |
The platform I have in mind is WebAssembly, which does not support non-default rounding modes. This platform may still be worth targeting, for small examples or demos where performance is not that important (or for applications where static filters are sufficient).
The text was updated successfully, but these errors were encountered: