[tarantool-patches] [PATCH 0/2] Fix border case in float-int comparison in SQL

[tarantool-patches] [PATCH 0/2] Fix border case in float-int comparison in SQL

[Nikita Pettik]

Branch: https://github.com/tarantool/tarantool/tree/np/sql-fix-float-int-cmp

This patch makes SQL utilize the same routine to compare integers
with floating point values as in NoSQL.

Nikita Pettik (2):
  Move mp_compare_double_uint64() to trivia.h
  sql: use double_compare_uint64() for int<->float cmp

 src/box/sql/vdbeaux.c    | 74 ++++++++++----------------------------------
 src/box/tuple_compare.cc | 80 ++----------------------------------------------
 src/lib/core/util.c      | 63 ++++++++++++++++++++++++++++++++++++++
 src/trivia/util.h        | 14 +++++++++
 test/sql/types.result    |  2 +-
 5 files changed, 97 insertions(+), 136 deletions(-)

-- 
2.15.1

[tarantool-patches] [PATCH 1/2] Move mp_compare_double_uint64() to trivia.h

[Nikita Pettik]

This function implements common way of precise comparison between
unsigned integer and floating point values (doubles). Currently, it is
used in tuple comparators, but we need the same thing in SQL. Hence,
let's move it to header containing set of utilities.
---
 src/box/tuple_compare.cc | 80 ++----------------------------------------------
 src/lib/core/util.c      | 63 ++++++++++++++++++++++++++++++++++++++
 src/trivia/util.h        | 14 +++++++++
 3 files changed, 80 insertions(+), 77 deletions(-)

diff --git a/src/box/tuple_compare.cc b/src/box/tuple_compare.cc
index b7b54e21a..e9951eaa0 100644
--- a/src/box/tuple_compare.cc
+++ b/src/box/tuple_compare.cc
@@ -90,8 +90,6 @@ static enum mp_class mp_classes[] = {
 	/* .MP_BIN     = */ MP_CLASS_BIN
 };
 
-#define COMPARE_RESULT(a, b) (a < b ? -1 : a > b)
-
 static enum mp_class
 mp_classof(enum mp_type type)
 {
@@ -137,77 +135,6 @@ mp_compare_integer_with_type(const char *field_a, enum mp_type a_type,
 	}
 }
 
-#define EXP2_53 9007199254740992.0      /* 2.0 ^ 53 */
-#define EXP2_64 1.8446744073709552e+19  /* 2.0 ^ 64 */
-
-/*
- * Compare LHS with RHS, return a value <0, 0 or >0 depending on the
- * comparison result (strcmp-style).
- * Normally, K==1. If K==-1, the result is inverted (as if LHS and RHS
- * were swapped).
- * K is needed to enable tail call optimization in Release build.
- * NOINLINE attribute was added to avoid aggressive inlining which
- * resulted in over 2Kb code size for mp_compare_number.
- */
-NOINLINE static int
-mp_compare_double_uint64(double lhs, uint64_t rhs, int k)
-{
-	assert(k==1 || k==-1);
-	/*
-	 * IEEE double represents 2^N precisely.
-	 * The value below is 2^53.  If a double exceeds this threshold,
-	 * there's no fractional part. Moreover, the "next" float is
-	 * 2^53+2, i.e. there's not enough precision to encode even some
-	 * "odd" integers.
-	 * Note: ">=" is important, see next block.
-	 */
-	if (lhs >= EXP2_53) {
-		/*
-		 * The value below is 2^64.
-		 * Note: UINT64_MAX is 2^64-1, hence ">="
-		 */
-		if (lhs >= EXP2_64)
-			return k;
-		/* Within [2^53, 2^64) double->uint64_t is lossless. */
-		assert((double)(uint64_t)lhs == lhs);
-		return k*COMPARE_RESULT((uint64_t)lhs, rhs);
-	}
-	/*
-	 * According to the IEEE 754 the double format is the
-	 * following:
-	 * +------+----------+----------+
-	 * | sign | exponent | fraction |
-	 * +------+----------+----------+
-	 *  1 bit    11 bits    52 bits
-	 * If the exponent is 0x7FF, the value is a special one.
-	 * Special value can be NaN, +inf and -inf.
-	 * If the fraction == 0, the value is inf. Sign depends on
-	 * the sign bit.
-	 * If the first bit of the fraction is 1, the value is the
-	 * quiet NaN, else the signaling NaN.
-	 */
-	if (!isnan(lhs)) {
-		/*
-		 * lhs is a number or inf.
-		 * If RHS < 2^53, uint64_t->double is lossless.
-		 * Otherwize the value may get rounded.	 It's
-		 * unspecified whether it gets rounded up or down,
-		 * i.e. the conversion may yield 2^53 for a
-		 * RHS > 2^53. Since we've aready ensured that
-		 * LHS < 2^53, the result is still correct even if
-		 * rounding happens.
-		 */
-		assert(lhs < EXP2_53);
-		assert((uint64_t)(double)rhs == rhs || rhs > (uint64_t)EXP2_53);
-		return k*COMPARE_RESULT(lhs, (double)rhs);
-	}
-	/*
-	 * Lhs is NaN. We assume all NaNs to be less than any
-	 * number.
-	 */
-	return -k;
-}
-
 static int
 mp_compare_double_any_int(double lhs, const char *rhs, enum mp_type rhs_type,
 			  int k)
@@ -215,13 +142,12 @@ mp_compare_double_any_int(double lhs, const char *rhs, enum mp_type rhs_type,
 	if (rhs_type == MP_INT) {
 		int64_t v = mp_decode_int(&rhs);
 		if (v < 0) {
-			return mp_compare_double_uint64(-lhs, (uint64_t)-v,
-							-k);
+			return double_compare_uint64(-lhs, (uint64_t)-v, -k);
 		}
-		return mp_compare_double_uint64(lhs, (uint64_t)v, k);
+		return double_compare_uint64(lhs, (uint64_t)v, k);
 	}
 	assert(rhs_type == MP_UINT);
-	return mp_compare_double_uint64(lhs, mp_decode_uint(&rhs), k);
+	return double_compare_uint64(lhs, mp_decode_uint(&rhs), k);
 }
 
 static int
diff --git a/src/lib/core/util.c b/src/lib/core/util.c
index 4ca99e177..ffa1d2b51 100644
--- a/src/lib/core/util.c
+++ b/src/lib/core/util.c
@@ -30,6 +30,7 @@
  */
 #include "trivia/util.h"
 
+#include <math.h>
 #include <stdarg.h>
 #include <stdbool.h>
 #include <stdio.h>
@@ -324,3 +325,65 @@ fpconv_check()
 	 */
 	assert(buf[1] == '.');
 }
+
+#define EXP2_53 9007199254740992.0      /* 2.0 ^ 53 */
+#define EXP2_64 1.8446744073709552e+19  /* 2.0 ^ 64 */
+
+int
+double_compare_uint64(double lhs, uint64_t rhs, int k)
+{
+	assert(k==1 || k==-1);
+	/*
+	 * IEEE double represents 2^N precisely.
+	 * The value below is 2^53.  If a double exceeds this threshold,
+	 * there's no fractional part. Moreover, the "next" float is
+	 * 2^53+2, i.e. there's not enough precision to encode even some
+	 * "odd" integers.
+	 * Note: ">=" is important, see next block.
+	 */
+	if (lhs >= EXP2_53) {
+		/*
+		 * The value below is 2^64.
+		 * Note: UINT64_MAX is 2^64-1, hence ">="
+		 */
+		if (lhs >= EXP2_64)
+			return k;
+		/* Within [2^53, 2^64) double->uint64_t is lossless. */
+		assert((double)(uint64_t)lhs == lhs);
+		return k*COMPARE_RESULT((uint64_t)lhs, rhs);
+	}
+	/*
+	 * According to the IEEE 754 the double format is the
+	 * following:
+	 * +------+----------+----------+
+	 * | sign | exponent | fraction |
+	 * +------+----------+----------+
+	 *  1 bit    11 bits    52 bits
+	 * If the exponent is 0x7FF, the value is a special one.
+	 * Special value can be NaN, +inf and -inf.
+	 * If the fraction == 0, the value is inf. Sign depends on
+	 * the sign bit.
+	 * If the first bit of the fraction is 1, the value is the
+	 * quiet NaN, else the signaling NaN.
+	 */
+	if (!isnan(lhs)) {
+		/*
+		 * lhs is a number or inf.
+		 * If RHS < 2^53, uint64_t->double is lossless.
+		 * Otherwize the value may get rounded.	 It's
+		 * unspecified whether it gets rounded up or down,
+		 * i.e. the conversion may yield 2^53 for a
+		 * RHS > 2^53. Since we've aready ensured that
+		 * LHS < 2^53, the result is still correct even if
+		 * rounding happens.
+		 */
+		assert(lhs < EXP2_53);
+		assert((uint64_t)(double)rhs == rhs || rhs > (uint64_t)EXP2_53);
+		return k*COMPARE_RESULT(lhs, (double)rhs);
+	}
+	/*
+	 * Lhs is NaN. We assume all NaNs to be less than any
+	 * number.
+	 */
+	return -k;
+}
diff --git a/src/trivia/util.h b/src/trivia/util.h
index 1e01013db..ebfe0c392 100644
--- a/src/trivia/util.h
+++ b/src/trivia/util.h
@@ -500,6 +500,20 @@ json_escape(char *buf, int size, const char *data);
 	}									\
 } while(0)
 
+#define COMPARE_RESULT(a, b) (a < b ? -1 : a > b)
+
+/**
+ * Compare LHS with RHS, return a value <0, 0 or >0 depending on the
+ * comparison result (strcmp-style).
+ * Normally, K==1. If K==-1, the result is inverted (as if LHS and RHS
+ * were swapped).
+ * K is needed to enable tail call optimization in Release build.
+ * NOINLINE attribute was added to avoid aggressive inlining which
+ * resulted in over 2Kb code size for mp_compare_number.
+ */
+int
+double_compare_uint64(double lhs, uint64_t rhs, int k);
+
 #if !defined(__cplusplus) && !defined(static_assert)
 # define static_assert _Static_assert
 #endif
-- 
2.15.1

[tarantool-patches] [PATCH 2/2] sql: use double_compare_uint64() for int<->float cmp

[Nikita Pettik]

To compare floating point values and integers in SQL functions
compare_uint_float() and compare_int_float() are used. Unfortunately,
they contain bug connected with checking border case: that's not correct
to cast UINT64_MAX (2^64 - 1) to double. Proper way is to use exp2(2^64)
or predefined floating point constant. To not bother fixing function
which in turn may contain other tricky places, let's use instead already
verified double_compare_uint64(). So that we have unified way of
integer<->float comparison.
---
 src/box/sql/vdbeaux.c | 74 +++++++++++----------------------------------------
 test/sql/types.result |  2 +-
 2 files changed, 17 insertions(+), 59 deletions(-)

diff --git a/src/box/sql/vdbeaux.c b/src/box/sql/vdbeaux.c
index e7accc745..2654f5c7a 100644
--- a/src/box/sql/vdbeaux.c
+++ b/src/box/sql/vdbeaux.c
@@ -2886,52 +2886,6 @@ sqlBlobCompare(const Mem * pB1, const Mem * pB2)
 	return n1 - n2;
 }
 
-/**
- * Do a comparison between a 64-bit unsigned/signed integer and a
- * 64-bit floating-point number.  Return negative, zero, or
- * positive if the first (integer) is less than, equal to, or
- * greater than the second (double).
- */
-static int
-compare_uint_float(uint64_t u, double r)
-{
-	if (r > (double) UINT64_MAX)
-		return -1;
-	if (r < 0.0)
-		return +1;
-	uint64_t y = (uint64_t) r;
-	if (u < y)
-		return -1;
-	if (u > y)
-		return +1;
-	double s = (double) u;
-	if (s < r)
-		return -1;
-	if (s > r)
-		return +1;
-	return 0;
-}
-
-static int
-compare_int_float(int64_t i, double r)
-{
-	if (r < (double) INT64_MIN)
-		return +1;
-	if (r >= 0.0)
-		return -1;
-	int64_t y = (int64_t) r;
-	if (i < y)
-		return -1;
-	if (i > y)
-		return +1;
-	double s = (double) i;
-	if (s < r)
-		return -1;
-	if (s > r)
-		return +1;
-	return 0;
-}
-
 /*
  * Compare the values contained by the two memory cells, returning
  * negative, zero or positive if pMem1 is less than, equal to, or greater
@@ -2997,16 +2951,16 @@ sqlMemCompare(const Mem * pMem1, const Mem * pMem2, const struct coll * pColl)
 		}
 		if ((f1 & MEM_Int) != 0) {
 			if ((f2 & MEM_Real) != 0) {
-				return compare_int_float(pMem1->u.i,
-							 pMem2->u.r);
+				return double_compare_uint64(-pMem2->u.r,
+							     -pMem1->u.i, 1);
 			} else {
 				return -1;
 			}
 		}
 		if ((f1 & MEM_UInt) != 0) {
 			if ((f2 & MEM_Real) != 0) {
-				return compare_uint_float(pMem1->u.u,
-							  pMem2->u.r);
+				return double_compare_uint64(pMem2->u.r,
+							     pMem1->u.u, -1);
 			} else if ((f2 & MEM_Int) != 0) {
 				return +1;
 			} else {
@@ -3015,11 +2969,11 @@ sqlMemCompare(const Mem * pMem1, const Mem * pMem2, const struct coll * pColl)
 		}
 		if ((f1 & MEM_Real) != 0) {
 			if ((f2 & MEM_Int) != 0) {
-				return -compare_int_float(pMem2->u.i,
-							  pMem1->u.r);
+				return double_compare_uint64(-pMem1->u.r,
+							     -pMem2->u.i, -1);
 			} else if ((f2 & MEM_UInt) != 0) {
-				return -compare_uint_float(pMem2->u.u,
-							   pMem1->u.r);
+				return double_compare_uint64(pMem1->u.r,
+							     pMem2->u.u, 1);
 			} else {
 				return -1;
 			}
@@ -3188,7 +3142,8 @@ sqlVdbeCompareMsgpack(const char **key1,
 				else if (mem1.u.u > pKey2->u.u)
 					rc = +1;
 			} else if ((pKey2->flags & MEM_Real) != 0) {
-				rc = compare_uint_float(mem1.u.u, pKey2->u.r);
+				rc = double_compare_uint64(pKey2->u.r,
+							   mem1.u.u, -1);
 			} else {
 				rc = (pKey2->flags & MEM_Null) ? +1 : -1;
 			}
@@ -3205,7 +3160,8 @@ sqlVdbeCompareMsgpack(const char **key1,
 					rc = +1;
 				}
 			} else if (pKey2->flags & MEM_Real) {
-				rc = compare_int_float(mem1.u.i, pKey2->u.r);
+				rc = double_compare_uint64(-pKey2->u.r,
+							   -mem1.u.i, 1);
 			} else {
 				rc = (pKey2->flags & MEM_Null) ? +1 : -1;
 			}
@@ -3219,9 +3175,11 @@ sqlVdbeCompareMsgpack(const char **key1,
 			mem1.u.r = mp_decode_double(&aKey1);
  do_float:
 			if ((pKey2->flags & MEM_Int) != 0) {
-				rc = -compare_int_float(pKey2->u.i, mem1.u.r);
+				rc = double_compare_uint64(-mem1.u.r,
+							   -pKey2->u.i, -1);
 			} else if (pKey2->flags & MEM_UInt) {
-				rc = -compare_uint_float(pKey2->u.u, mem1.u.r);
+				rc = double_compare_uint64(mem1.u.r,
+							   pKey2->u.u, 1);
 			} else if (pKey2->flags & MEM_Real) {
 				if (mem1.u.r < pKey2->u.r) {
 					rc = -1;
diff --git a/test/sql/types.result b/test/sql/types.result
index 83820af53..c95d21e0f 100644
--- a/test/sql/types.result
+++ b/test/sql/types.result
@@ -1286,7 +1286,7 @@ box.execute("SELECT 18446744073709551615.0 > 18446744073709551615")
   - name: 18446744073709551615.0 > 18446744073709551615
     type: boolean
   rows:
-  - [false]
+  - [true]
 ...
 box.execute("SELECT 18446744073709551615 IN ('18446744073709551615', 18446744073709551615.0)")
 ---
-- 
2.15.1

[tarantool-patches] ***UNCHECKED*** Re: [PATCH 1/2] Move mp_compare_double_uint64() to trivia.h

[Vladislav Shpilevoy]

Hi! Thanks for the patch!

> diff --git a/src/trivia/util.h b/src/trivia/util.h
> index 1e01013db..ebfe0c392 100644
> --- a/src/trivia/util.h
> +++ b/src/trivia/util.h
> @@ -500,6 +500,20 @@ json_escape(char *buf, int size, const char *data);
>  	}									\
>  } while(0)
>  
> +#define COMPARE_RESULT(a, b) (a < b ? -1 : a > b)
> +
> +/**
> + * Compare LHS with RHS, return a value <0, 0 or >0 depending on the
> + * comparison result (strcmp-style).
> + * Normally, K==1. If K==-1, the result is inverted (as if LHS and RHS
> + * were swapped).
> + * K is needed to enable tail call optimization in Release build.
> + * NOINLINE attribute was added to avoid aggressive inlining which

I guess, NOINLINE does not make sense anymore. But you can keep a
comment, that inlining should not be added in future for the sake
of tail call optimization.

> + * resulted in over 2Kb code size for mp_compare_number.
> + */
> +int
> +double_compare_uint64(double lhs, uint64_t rhs, int k);
> +
>  #if !defined(__cplusplus) && !defined(static_assert)
>  # define static_assert _Static_assert
>  #endif
> 

[tarantool-patches] ***UNCHECKED*** Re: [PATCH 1/2] Move mp_compare_double_uint64() to trivia.h

[Vladislav Shpilevoy]

Thanks for the patch!

> Move mp_compare_double_uint64() to trivia.h

I guess, it is 'trivia/util.h', not 'trivia.h'.

[tarantool-patches] Re: [PATCH 1/2] Move mp_compare_double_uint64() to trivia.h

[n.pettik]

> On 9 Aug 2019, at 00:37, Vladislav Shpilevoy <v.shpilevoy@tarantool.org> wrote:
> 
> Hi! Thanks for the patch!
> 
>> diff --git a/src/trivia/util.h b/src/trivia/util.h
>> index 1e01013db..ebfe0c392 100644
>> --- a/src/trivia/util.h
>> +++ b/src/trivia/util.h
>> @@ -500,6 +500,20 @@ json_escape(char *buf, int size, const char *data);
>> 	}									\
>> } while(0)
>> 
>> +#define COMPARE_RESULT(a, b) (a < b ? -1 : a > b)
>> +
>> +/**
>> + * Compare LHS with RHS, return a value <0, 0 or >0 depending on the
>> + * comparison result (strcmp-style).
>> + * Normally, K==1. If K==-1, the result is inverted (as if LHS and RHS
>> + * were swapped).
>> + * K is needed to enable tail call optimization in Release build.
>> + * NOINLINE attribute was added to avoid aggressive inlining which
> 
> I guess, NOINLINE does not make sense anymore. But you can keep a
> comment, that inlining should not be added in future for the sake
> of tail call optimization.

Thx, fixed:

diff --git a/src/trivia/util.h b/src/trivia/util.h
index ebfe0c392..8a3d22b38 100644
--- a/src/trivia/util.h
+++ b/src/trivia/util.h
@@ -508,8 +508,6 @@ json_escape(char *buf, int size, const char *data);
  * Normally, K==1. If K==-1, the result is inverted (as if LHS and RHS
  * were swapped).
  * K is needed to enable tail call optimization in Release build.
- * NOINLINE attribute was added to avoid aggressive inlining which
- * resulted in over 2Kb code size for mp_compare_number.
  */
 int
 double_compare_uint64(double lhs, uint64_t rhs, int k);

Also fixed commit subject according to your nit:

Move mp_compare_double_uint64() to trivia/util.h

[tarantool-patches] Re: [PATCH 1/2] Move mp_compare_double_uint64() to trivia.h

[Vladislav Shpilevoy]

LGTM.

On 14/08/2019 12:36, n.pettik wrote:
> 
> 
>> On 9 Aug 2019, at 00:37, Vladislav Shpilevoy <v.shpilevoy@tarantool.org> wrote:
>>
>> Hi! Thanks for the patch!
>>
>>> diff --git a/src/trivia/util.h b/src/trivia/util.h
>>> index 1e01013db..ebfe0c392 100644
>>> --- a/src/trivia/util.h
>>> +++ b/src/trivia/util.h
>>> @@ -500,6 +500,20 @@ json_escape(char *buf, int size, const char *data);
>>> 	}									\
>>> } while(0)
>>>
>>> +#define COMPARE_RESULT(a, b) (a < b ? -1 : a > b)
>>> +
>>> +/**
>>> + * Compare LHS with RHS, return a value <0, 0 or >0 depending on the
>>> + * comparison result (strcmp-style).
>>> + * Normally, K==1. If K==-1, the result is inverted (as if LHS and RHS
>>> + * were swapped).
>>> + * K is needed to enable tail call optimization in Release build.
>>> + * NOINLINE attribute was added to avoid aggressive inlining which
>>
>> I guess, NOINLINE does not make sense anymore. But you can keep a
>> comment, that inlining should not be added in future for the sake
>> of tail call optimization.
> 
> Thx, fixed:
> 
> diff --git a/src/trivia/util.h b/src/trivia/util.h
> index ebfe0c392..8a3d22b38 100644
> --- a/src/trivia/util.h
> +++ b/src/trivia/util.h
> @@ -508,8 +508,6 @@ json_escape(char *buf, int size, const char *data);
>   * Normally, K==1. If K==-1, the result is inverted (as if LHS and RHS
>   * were swapped).
>   * K is needed to enable tail call optimization in Release build.
> - * NOINLINE attribute was added to avoid aggressive inlining which
> - * resulted in over 2Kb code size for mp_compare_number.
>   */
>  int
>  double_compare_uint64(double lhs, uint64_t rhs, int k);
> 
> Also fixed commit subject according to your nit:
> 
> Move mp_compare_double_uint64() to trivia/util.h
> 

[tarantool-patches] Re: [PATCH 0/2] Fix border case in float-int comparison in SQL

[Kirill Yukhin]

Hello,

On 07 Aug 01:02, Nikita Pettik wrote:
> Branch: https://github.com/tarantool/tarantool/tree/np/sql-fix-float-int-cmp
> 
> This patch makes SQL utilize the same routine to compare integers
> with floating point values as in NoSQL.

I've checked the patch into 2.2 and master.

--
Regards, Kirill Yukhin