[m-dev.] Re: pragma fact_table

[David Matthew OVERTON]

Hi Fergus,

Fergus Henderson wrote:
> 
> 
> There is also a potential problem if the compilers optimize these two
> versions differently.  For example, on many machines floating point
> registers may have more accuracy than floating point values stored
> in memory, so that the exact end result of a floating point computation
> may in fact depend on exactly how the compiler allocates registers.
> 
> The problem of the two hashing codes being inconsistent should be fixed
> by avoiding the code duplication and only having one piece of code for
> computing float hashes.
> 
> Hashing floats is something that is generally useful, and we already
> have string__hash_string in library/string.m, so it would make sense to
> define this float hashing function in library/float.m.  It is probably
> easiest if you use the C code version and define the Mercury version to
> call the C version using `pragma c_code'. The C code should be in a
> `:- pragma c_code("....")' block in library/float.m.
> (The alternative of using the Mercury code version and calling that
> from C using `pragma export' is also possible but the other way is
> likely to be more efficient.)
> 

Here are the changes to add the new `float__hash' predicate.  I thought
it would be easier to put the C function `hash_float' into the runtime
(as is done with `hash_string') because it is then available whenever
it is needed by the fact table lookup code rather than having to
import the float module.  Is that a good idea or not?  Should I add a
version to float.nu.nl as well?

Also it is a C function rather than a macro to reduce problems due to
the compiler optimising the code differently in different places.

Tom has suggested an alternative (much more efficient) method that
uses a union of Float and Word to convert the float's bit pattern to
an integer (the same as float_to_word() for UNBOXED_FLOATS).  However
I haven't used this method at the moment because (AFAIK) it can't be
implemented in prolog.


David.


Estimated hours taken: 2

Add new predicate `float__hash' to the standard library for computing a
non-negative integer hash value for a float.

Add a C function to the runtime to do the actual hashing.  This
function is in the runtime so that it can be called from both
the library and from C code generated for `pragma fact_table'
indexing.

library/float.m
        Add a new predicate `float__hash' that calls the runtime
	function `hash_float'.

runtime/misc.c
	Add a new function `hash_float' for hashing floats.

runtime/mercury_float.m
	Add an `extern' declaration for `hash_float'.

Index: library//float.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/library/float.m,v
retrieving revision 1.20
diff -u -r1.20 float.m
--- float.m	1996/07/26 06:00:14	1.20
+++ float.m	1997/02/26 03:07:51
@@ -156,6 +156,12 @@
 :- mode float__epsilon(out) is det.
 
 %---------------------------------------------------------------------------%
+% Create a non-negative integer hash value for a float.
+
+:- pred float__hash(float, int).
+:- mode float__hash(in, out) is det.
+
+%---------------------------------------------------------------------------%
 
 :- implementation.
 :- import_module int, require.
@@ -286,6 +292,14 @@
 
 	% Smallest x such that x \= 1.0 + x
 :- pragma(c_code, float__epsilon(Eps::out), "Eps = MERCURY_FLOAT_EPSILON;").
+
+%---------------------------------------------------------------------------%
+
+:- pragma c_code(float__hash(F::in, H::out), will_not_call_mercury, "
+
+	H = hash_float(F);
+
+").
 
 %---------------------------------------------------------------------------%
 %---------------------------------------------------------------------------%
Index: library/runtime//mercury_float.h
===================================================================
RCS file: /home/staff/zs/imp/mercury/runtime/mercury_float.h,v
retrieving revision 1.3
diff -u -r1.3 mercury_float.h
--- mercury_float.h	1997/02/12 02:15:50	1.3
+++ mercury_float.h	1997/02/25 23:59:09
@@ -72,4 +72,6 @@
 
 #endif /* not BOXED_FLOAT */
 
+extern Integer hash_float(Float);
+
 #endif /* not MERCURY_FLOAT_H */
Index: library/runtime//misc.c
===================================================================
RCS file: /home/staff/zs/imp/mercury/runtime/misc.c,v
retrieving revision 1.9
diff -u -r1.9 misc.c
--- misc.c	1997/02/12 07:41:12	1.9
+++ misc.c	1997/02/26 03:32:53
@@ -10,6 +10,7 @@
 #include	"misc.h"
 
 #include	<stdio.h>
+#include	<math.h>
 
 /*--------------------------------------------------------------------*/
 
@@ -490,4 +491,36 @@
 hash_string(Word s)
 {
 	HASH_STRING_FUNC_BODY
+}
+
+/*
+**  This function is used by the library predicate `float__hash/2' and also 
+**  for hashing floats for `pragma fact_table' indexing.
+**
+**  How it works:  first ensure f is positive by taking the absolute value
+**  and then adding 1e-15 if f == 0.0.  Next calculate the lowest power
+**  of e that is >= f (i.e. exp(ceil(log(f)))).  Divide f by this number to
+**  get a number in the range exp(-1) to 1.  Multiply this by 2^31-1 to
+**  get a number, g,  in the range 790015083 to  2147483647.
+**  To include the magnitude of f in the computation, add ceil(log(f)) to g
+**  and then truncate the result to an integer.  Return the absolute value
+**  of this integer to guarantee that the result is non-negative.
+**
+**  Note: this is a function rather than a macro to ensure that exactly the
+**  same code is executed each time it is called.  If a macro were used, it
+**  may get optimised differently in different places causing different
+**  results to be computed.
+*/
+
+Integer 
+hash_float(Float f)
+{
+	Float g, h;
+	Integer i;
+	if (f <= 0.0) f = -f;
+	if (f == 0.0) f = 1e-15;
+	h = ceil(log(f));
+	g = f / exp(h) * 2147483647.0; /* 2147483647 = 2^31 - 1 */
+	i = (Integer)(h + g);
+	return (i >= 0 ? i : -i);
 }