From e04883d448df6e622535020449903e2f2a0f32c9 Mon Sep 17 00:00:00 2001 From: Lukas Larsson Date: Tue, 26 Jul 2011 17:11:41 +0200 Subject: Update integer and floating point number comparisons For floating point values which are greater than 9007199254740990.0 or smaller than -9007199254740990.0, the floating point numbers are now converted to integers during comparison with an integer. This makes number comparisons transitive for large floating point numbers. --- erts/emulator/beam/utils.c | 59 +++++++++++++++++++++++++++++++++++++--------- 1 file changed, 48 insertions(+), 11 deletions(-) (limited to 'erts/emulator/beam/utils.c') diff --git a/erts/emulator/beam/utils.c b/erts/emulator/beam/utils.c index 3f6accba2d..e67a793b9a 100644 --- a/erts/emulator/beam/utils.c +++ b/erts/emulator/beam/utils.c @@ -2642,7 +2642,7 @@ tailrecur_ne: FloatDef f1, f2; Eterm big; #if HEAP_ON_C_STACK - Eterm big_buf[2]; /* If HEAP_ON_C_STACK */ + Eterm big_buf[16]; /* If HEAP_ON_C_STACK */ #else Eterm *big_buf = erts_get_scheduler_data()->cmp_tmp_heap; #endif @@ -2661,33 +2661,70 @@ tailrecur_ne: j = big_comp(big, bw); break; case SMALL_FLOAT: - f1.fd = signed_val(a); GET_DOUBLE(bw, f2); - j = float_comp(f1.fd, f2.fd); + if ((f2.fd < 9007199254740990.0 && f2.fd > -9007199254740990.0)) // Float is within the no loss limit + { + f1.fd = signed_val(a); + j = float_comp(f1.fd, f2.fd); + } else if (f2.fd > (double) (MAX_SMALL + 1)) { // Float is a positive bignum, i.e. bigger + j = -1; + } else if (f2.fd < (double) (MIN_SMALL - 1)) { // Float is a negative bignum, i.e. smaller + j = 1; + } else { // Float is a Sint but less precise it + j = signed_val(a) - (Sint) f2.fd; + } break; case BIG_SMALL: big = small_to_big(signed_val(b), big_buf); j = big_comp(aw, big); break; case BIG_FLOAT: - if (big_to_double(aw, &f1.fd) < 0) { + GET_DOUBLE(bw, f2); + if ((f2.fd < 9007199254740990.0 && f2.fd > -9007199254740990.0)) { + if (big_to_double(aw, &f1.fd) < 0) { + j = big_sign(a) ? -1 : 1; + } else { + j = float_comp(f1.fd, f2.fd); + } + } else if ((f2.fd < (double) (MAX_SMALL + 1)) && (f2.fd > (double) (MIN_SMALL - 1))) { // Float is a Sint + j = big_sign(a) ? -1 : 1; + } else if (big_arity(a) > ((1 << 10) / D_EXP)) { // If bignum size is larger than largest/smallest float j = big_sign(a) ? -1 : 1; } else { - GET_DOUBLE(bw, f2); - j = float_comp(f1.fd, f2.fd); + big = double_to_big(f2.fd, big_buf); + j = big_comp(aw, big); } break; case FLOAT_SMALL: GET_DOUBLE(aw, f1); - f2.fd = signed_val(b); - j = float_comp(f1.fd, f2.fd); + if ((f1.fd < 9007199254740990.0 && f1.fd > -9007199254740990.0)) // Float is within the no loss limit + { + f2.fd = signed_val(b); + j = float_comp(f1.fd, f2.fd); + } else if (f1.fd > (double) (MAX_SMALL + 1)) { // Float is a positive bignum, i.e. bigger + j = 1; + } else if (f1.fd < (double) (MIN_SMALL - 1)) { // Float is a negative bignum, i.e. smaller + j = -1; + } else { // Float is a Sint but less precise it + j = (Sint) f1.fd - signed_val(b); + } break; case FLOAT_BIG: - if (big_to_double(bw, &f2.fd) < 0) { + GET_DOUBLE(aw, f1); + if ((f1.fd < 9007199254740990.0 && f1.fd > -9007199254740990.0)) { + if (big_to_double(bw, &f2.fd) < 0) { + j = big_sign(b) ? 1 : -1; + } else { + j = float_comp(f1.fd, f2.fd); + } + } else if ((f1.fd < (double) (MAX_SMALL + 1)) + && (f1.fd > (double) (MIN_SMALL - 1))) { // Float is a Sint + j = big_sign(b) ? 1 : -1; + } else if (big_arity(b) > ((1 << 10) / D_EXP)) { // If bignum size is larger than largest/smallest float j = big_sign(b) ? 1 : -1; } else { - GET_DOUBLE(aw, f1); - j = float_comp(f1.fd, f2.fd); + big = double_to_big(f1.fd, big_buf); + j = big_comp(big, bw); } break; default: -- cgit v1.2.3 From b47a8245774ee1d57872d99015081e6307e037f1 Mon Sep 17 00:00:00 2001 From: Lukas Larsson Date: Wed, 27 Jul 2011 16:41:13 +0200 Subject: Optimise bugnum and small comparison As it is possible to assume that bignums are bigger than smalls, we can just check the sign of the bignum. --- erts/emulator/beam/utils.c | 10 ++++------ 1 file changed, 4 insertions(+), 6 deletions(-) (limited to 'erts/emulator/beam/utils.c') diff --git a/erts/emulator/beam/utils.c b/erts/emulator/beam/utils.c index e67a793b9a..5e22aa42c8 100644 --- a/erts/emulator/beam/utils.c +++ b/erts/emulator/beam/utils.c @@ -2657,8 +2657,10 @@ tailrecur_ne: switch(_NUMBER_CODE(a_tag, b_tag)) { case SMALL_BIG: - big = small_to_big(signed_val(a), big_buf); - j = big_comp(big, bw); + j = big_sign(bw) ? 1 : -1; + break; + case BIG_SMALL: + j = big_sign(aw) ? -1 : 1; break; case SMALL_FLOAT: GET_DOUBLE(bw, f2); @@ -2674,10 +2676,6 @@ tailrecur_ne: j = signed_val(a) - (Sint) f2.fd; } break; - case BIG_SMALL: - big = small_to_big(signed_val(b), big_buf); - j = big_comp(aw, big); - break; case BIG_FLOAT: GET_DOUBLE(bw, f2); if ((f2.fd < 9007199254740990.0 && f2.fd > -9007199254740990.0)) { -- cgit v1.2.3 From 1224324e4ee4526397725c4aaaf8885ec7da0c4e Mon Sep 17 00:00:00 2001 From: Lukas Larsson Date: Wed, 27 Jul 2011 16:46:08 +0200 Subject: Add heauristics bignum vs float checks These tests are useful when the difference between the bignum and float is larger than one bignum segment. --- erts/emulator/beam/utils.c | 67 +++++++++++++++++++++++++++++----------------- 1 file changed, 42 insertions(+), 25 deletions(-) (limited to 'erts/emulator/beam/utils.c') diff --git a/erts/emulator/beam/utils.c b/erts/emulator/beam/utils.c index 5e22aa42c8..91e4e50e15 100644 --- a/erts/emulator/beam/utils.c +++ b/erts/emulator/beam/utils.c @@ -2653,6 +2653,8 @@ tailrecur_ne: Eterm aw = a; Eterm bw = b; #endif +#define MAX_LOSSLESS_FLOAT ((double)((1L << 53) - 2)) +#define MIN_LOSSLESS_FLOAT ((double)(((1L << 53) - 2)*-1)) b_tag = tag_val_def(bw); switch(_NUMBER_CODE(a_tag, b_tag)) { @@ -2664,30 +2666,39 @@ tailrecur_ne: break; case SMALL_FLOAT: GET_DOUBLE(bw, f2); - if ((f2.fd < 9007199254740990.0 && f2.fd > -9007199254740990.0)) // Float is within the no loss limit - { - f1.fd = signed_val(a); + if (f2.fd < MAX_LOSSLESS_FLOAT && f2.fd > MIN_LOSSLESS_FLOAT) { + // Float is within the no loss limit + f1.fd = signed_val(aw); j = float_comp(f1.fd, f2.fd); - } else if (f2.fd > (double) (MAX_SMALL + 1)) { // Float is a positive bignum, i.e. bigger + } else if (f2.fd > (double) (MAX_SMALL + 1)) { + // Float is a positive bignum, i.e. bigger j = -1; - } else if (f2.fd < (double) (MIN_SMALL - 1)) { // Float is a negative bignum, i.e. smaller + } else if (f2.fd < (double) (MIN_SMALL - 1)) { + // Float is a negative bignum, i.e. smaller j = 1; - } else { // Float is a Sint but less precise it - j = signed_val(a) - (Sint) f2.fd; + } else { // Float is a Sint but less precise + j = signed_val(aw) - (Sint) f2.fd; } break; case BIG_FLOAT: GET_DOUBLE(bw, f2); - if ((f2.fd < 9007199254740990.0 && f2.fd > -9007199254740990.0)) { + if (f2.fd < MAX_LOSSLESS_FLOAT && f2.fd > MIN_LOSSLESS_FLOAT) { + // Float is within the no loss limit if (big_to_double(aw, &f1.fd) < 0) { - j = big_sign(a) ? -1 : 1; + j = big_sign(aw) ? -1 : 1; } else { j = float_comp(f1.fd, f2.fd); } - } else if ((f2.fd < (double) (MAX_SMALL + 1)) && (f2.fd > (double) (MIN_SMALL - 1))) { // Float is a Sint - j = big_sign(a) ? -1 : 1; - } else if (big_arity(a) > ((1 << 10) / D_EXP)) { // If bignum size is larger than largest/smallest float - j = big_sign(a) ? -1 : 1; + } else if ((f2.fd < (double) (MAX_SMALL + 1)) + && (f2.fd > (double) (MIN_SMALL - 1))) { + // Float is a Sint + j = big_sign(aw) ? -1 : 1; + } else if ( (( 1 << (big_arity(aw)*D_EXP))-1) > f2.fd) { + // If bignum size shows that it is bigger than the float + j = -1; + } else if ( (( 1 << (big_arity(aw)*D_EXP))-1)*-1 < f2.fd) { + // If bignum size shows that it is smaller than the float + j = 1; } else { big = double_to_big(f2.fd, big_buf); j = big_comp(aw, big); @@ -2695,31 +2706,37 @@ tailrecur_ne: break; case FLOAT_SMALL: GET_DOUBLE(aw, f1); - if ((f1.fd < 9007199254740990.0 && f1.fd > -9007199254740990.0)) // Float is within the no loss limit - { - f2.fd = signed_val(b); + if (f2.fd < MAX_LOSSLESS_FLOAT && f2.fd > MIN_LOSSLESS_FLOAT) { + // Float is within the no loss limit + f2.fd = signed_val(bw); j = float_comp(f1.fd, f2.fd); - } else if (f1.fd > (double) (MAX_SMALL + 1)) { // Float is a positive bignum, i.e. bigger + } else if (f1.fd > (double) (MAX_SMALL + 1)) { + // Float is a positive bignum, i.e. bigger j = 1; - } else if (f1.fd < (double) (MIN_SMALL - 1)) { // Float is a negative bignum, i.e. smaller + } else if (f1.fd < (double) (MIN_SMALL - 1)) { + // Float is a negative bignum, i.e. smaller j = -1; } else { // Float is a Sint but less precise it - j = (Sint) f1.fd - signed_val(b); + j = (Sint) f1.fd - signed_val(bw); } break; case FLOAT_BIG: GET_DOUBLE(aw, f1); - if ((f1.fd < 9007199254740990.0 && f1.fd > -9007199254740990.0)) { - if (big_to_double(bw, &f2.fd) < 0) { - j = big_sign(b) ? 1 : -1; + if (f1.fd < MAX_LOSSLESS_FLOAT && f1.fd > MIN_LOSSLESS_FLOAT) { + if (big_to_double(bw, &f1.fd) < 0) { + j = big_sign(bw) ? 1 : -1; } else { j = float_comp(f1.fd, f2.fd); } } else if ((f1.fd < (double) (MAX_SMALL + 1)) && (f1.fd > (double) (MIN_SMALL - 1))) { // Float is a Sint - j = big_sign(b) ? 1 : -1; - } else if (big_arity(b) > ((1 << 10) / D_EXP)) { // If bignum size is larger than largest/smallest float - j = big_sign(b) ? 1 : -1; + j = big_sign(bw) ? 1 : -1; + } else if ( (( 1 << (big_arity(bw)*D_EXP))-1) > f1.fd) { + // If bignum size shows that it is bigger than the float + j = 1; + } else if ( (( 1 << (big_arity(bw)*D_EXP))-1)*-1 < f1.fd) { + // If bignum size shows that it is smaller than the float + j = -1; } else { big = double_to_big(f1.fd, big_buf); j = big_comp(big, bw); -- cgit v1.2.3 From 5afcc1900d858984143c673aca5c1639d12f9e84 Mon Sep 17 00:00:00 2001 From: Lukas Larsson Date: Tue, 11 Oct 2011 17:18:15 +0200 Subject: Update heauristic to work on halfword --- erts/emulator/beam/utils.c | 45 ++++++++++++++++++++------------------------- 1 file changed, 20 insertions(+), 25 deletions(-) (limited to 'erts/emulator/beam/utils.c') diff --git a/erts/emulator/beam/utils.c b/erts/emulator/beam/utils.c index 91e4e50e15..85e8c86d53 100644 --- a/erts/emulator/beam/utils.c +++ b/erts/emulator/beam/utils.c @@ -2653,8 +2653,8 @@ tailrecur_ne: Eterm aw = a; Eterm bw = b; #endif -#define MAX_LOSSLESS_FLOAT ((double)((1L << 53) - 2)) -#define MIN_LOSSLESS_FLOAT ((double)(((1L << 53) - 2)*-1)) +#define MAX_LOSSLESS_FLOAT ((double)((1LL << 53) - 2)) +#define MIN_LOSSLESS_FLOAT ((double)(((1LL << 53) - 2)*-1)) b_tag = tag_val_def(bw); switch(_NUMBER_CODE(a_tag, b_tag)) { @@ -2682,23 +2682,20 @@ tailrecur_ne: break; case BIG_FLOAT: GET_DOUBLE(bw, f2); - if (f2.fd < MAX_LOSSLESS_FLOAT && f2.fd > MIN_LOSSLESS_FLOAT) { + if ((f2.fd < (double) (MAX_SMALL + 1)) + && (f2.fd > (double) (MIN_SMALL - 1))) { + // Float is a Sint + j = big_sign(aw) ? -1 : 1; + } else if ( (pow(2.0,(big_arity(aw)-1.0)*D_EXP)-1.0) > fabs(f2.fd)) { + // If bignum size shows that it is bigger or smaller than the float + j = big_sign(aw) ? -1 : 1; + } else if (f2.fd < MAX_LOSSLESS_FLOAT && f2.fd > MIN_LOSSLESS_FLOAT) { // Float is within the no loss limit if (big_to_double(aw, &f1.fd) < 0) { j = big_sign(aw) ? -1 : 1; } else { j = float_comp(f1.fd, f2.fd); } - } else if ((f2.fd < (double) (MAX_SMALL + 1)) - && (f2.fd > (double) (MIN_SMALL - 1))) { - // Float is a Sint - j = big_sign(aw) ? -1 : 1; - } else if ( (( 1 << (big_arity(aw)*D_EXP))-1) > f2.fd) { - // If bignum size shows that it is bigger than the float - j = -1; - } else if ( (( 1 << (big_arity(aw)*D_EXP))-1)*-1 < f2.fd) { - // If bignum size shows that it is smaller than the float - j = 1; } else { big = double_to_big(f2.fd, big_buf); j = big_comp(aw, big); @@ -2706,7 +2703,7 @@ tailrecur_ne: break; case FLOAT_SMALL: GET_DOUBLE(aw, f1); - if (f2.fd < MAX_LOSSLESS_FLOAT && f2.fd > MIN_LOSSLESS_FLOAT) { + if (f1.fd < MAX_LOSSLESS_FLOAT && f1.fd > MIN_LOSSLESS_FLOAT) { // Float is within the no loss limit f2.fd = signed_val(bw); j = float_comp(f1.fd, f2.fd); @@ -2722,21 +2719,19 @@ tailrecur_ne: break; case FLOAT_BIG: GET_DOUBLE(aw, f1); - if (f1.fd < MAX_LOSSLESS_FLOAT && f1.fd > MIN_LOSSLESS_FLOAT) { - if (big_to_double(bw, &f1.fd) < 0) { + if ((f1.fd < (double) (MAX_SMALL + 1)) + && (f1.fd > (double) (MIN_SMALL - 1))) { // Float is a Sint + j = big_sign(bw) ? 1 : -1; + } else if ((pow(2.0, (big_arity(bw) - 1.0) * D_EXP) - 1.0) > fabs(f1.fd)) { + // If bignum size shows that it is bigger than the float + j = big_sign(bw) ? 1 : -1; + } else if (f1.fd < MAX_LOSSLESS_FLOAT && f1.fd >MIN_LOSSLESS_FLOAT) { + // Float is within the no loss limit + if (big_to_double(bw, &f2.fd) < 0) { j = big_sign(bw) ? 1 : -1; } else { j = float_comp(f1.fd, f2.fd); } - } else if ((f1.fd < (double) (MAX_SMALL + 1)) - && (f1.fd > (double) (MIN_SMALL - 1))) { // Float is a Sint - j = big_sign(bw) ? 1 : -1; - } else if ( (( 1 << (big_arity(bw)*D_EXP))-1) > f1.fd) { - // If bignum size shows that it is bigger than the float - j = 1; - } else if ( (( 1 << (big_arity(bw)*D_EXP))-1)*-1 < f1.fd) { - // If bignum size shows that it is smaller than the float - j = -1; } else { big = double_to_big(f1.fd, big_buf); j = big_comp(big, bw); -- cgit v1.2.3 From f99fd21debc8274dbdecd595e1666436ec962ccd Mon Sep 17 00:00:00 2001 From: Lukas Larsson Date: Fri, 29 Jul 2011 15:47:06 +0200 Subject: Update size of tmp cmp bignum buffer This is needed for use on 32 bit with very large floats. --- erts/emulator/beam/utils.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'erts/emulator/beam/utils.c') diff --git a/erts/emulator/beam/utils.c b/erts/emulator/beam/utils.c index 85e8c86d53..5822b2e1d9 100644 --- a/erts/emulator/beam/utils.c +++ b/erts/emulator/beam/utils.c @@ -2642,7 +2642,7 @@ tailrecur_ne: FloatDef f1, f2; Eterm big; #if HEAP_ON_C_STACK - Eterm big_buf[16]; /* If HEAP_ON_C_STACK */ + Eterm big_buf[32]; /* If HEAP_ON_C_STACK */ #else Eterm *big_buf = erts_get_scheduler_data()->cmp_tmp_heap; #endif -- cgit v1.2.3 From 3b62e52f16ef72ce4224a61dc9e6bc7ab53234a1 Mon Sep 17 00:00:00 2001 From: Lukas Larsson Date: Mon, 8 Aug 2011 18:48:16 +0200 Subject: Optimize comparison of huge floats and smaller bignums --- erts/emulator/beam/utils.c | 14 ++++++++++---- 1 file changed, 10 insertions(+), 4 deletions(-) (limited to 'erts/emulator/beam/utils.c') diff --git a/erts/emulator/beam/utils.c b/erts/emulator/beam/utils.c index 5822b2e1d9..f296ccbadd 100644 --- a/erts/emulator/beam/utils.c +++ b/erts/emulator/beam/utils.c @@ -2686,9 +2686,12 @@ tailrecur_ne: && (f2.fd > (double) (MIN_SMALL - 1))) { // Float is a Sint j = big_sign(aw) ? -1 : 1; - } else if ( (pow(2.0,(big_arity(aw)-1.0)*D_EXP)-1.0) > fabs(f2.fd)) { - // If bignum size shows that it is bigger or smaller than the float + } else if ((pow(2.0,(big_arity(aw)-1.0)*D_EXP)-1.0) > fabs(f2.fd)) { + // If bignum size shows that it is bigger than the abs float j = big_sign(aw) ? -1 : 1; + } else if ((pow(2.0,(big_arity(aw))*D_EXP)-1.0) < fabs(f2.fd)) { + // If bignum size shows that it is smaller than the abs float + j = f2.fd < 0 ? 1 : -1; } else if (f2.fd < MAX_LOSSLESS_FLOAT && f2.fd > MIN_LOSSLESS_FLOAT) { // Float is within the no loss limit if (big_to_double(aw, &f1.fd) < 0) { @@ -2723,9 +2726,12 @@ tailrecur_ne: && (f1.fd > (double) (MIN_SMALL - 1))) { // Float is a Sint j = big_sign(bw) ? 1 : -1; } else if ((pow(2.0, (big_arity(bw) - 1.0) * D_EXP) - 1.0) > fabs(f1.fd)) { - // If bignum size shows that it is bigger than the float + // If bignum size shows that it is bigger than the abs float j = big_sign(bw) ? 1 : -1; - } else if (f1.fd < MAX_LOSSLESS_FLOAT && f1.fd >MIN_LOSSLESS_FLOAT) { + } else if ((pow(2.0,(big_arity(bw))*D_EXP)-1.0) < fabs(f1.fd)) { + // If bignum size shows that it is smaller than the abs float + j = f1.fd < 0 ? -1 : 1; + } else if (f1.fd < MAX_LOSSLESS_FLOAT && f1.fd > MIN_LOSSLESS_FLOAT) { // Float is within the no loss limit if (big_to_double(bw, &f2.fd) < 0) { j = big_sign(bw) ? 1 : -1; -- cgit v1.2.3 From f82d49ab3e65f52fd7b6dd7d9e8913543b7a1375 Mon Sep 17 00:00:00 2001 From: Lukas Larsson Date: Mon, 3 Oct 2011 19:09:55 +0200 Subject: Do small optimisation on platforms with 32 bit Eterm On 32 bit we know that a comparison with a lossfull double and a short will always give the float is being superior. So therefore we only have to check the sign on the double. --- erts/emulator/beam/utils.c | 14 ++++++++++++++ 1 file changed, 14 insertions(+) (limited to 'erts/emulator/beam/utils.c') diff --git a/erts/emulator/beam/utils.c b/erts/emulator/beam/utils.c index f296ccbadd..825cb140b2 100644 --- a/erts/emulator/beam/utils.c +++ b/erts/emulator/beam/utils.c @@ -2670,6 +2670,7 @@ tailrecur_ne: // Float is within the no loss limit f1.fd = signed_val(aw); j = float_comp(f1.fd, f2.fd); +#if ERTS_SIZEOF_ETERM == 8 } else if (f2.fd > (double) (MAX_SMALL + 1)) { // Float is a positive bignum, i.e. bigger j = -1; @@ -2679,6 +2680,12 @@ tailrecur_ne: } else { // Float is a Sint but less precise j = signed_val(aw) - (Sint) f2.fd; } +#else + } else { + // If float is positive it is bigger than small + j = (f2.fd > 0.0) ? -1 : 1; + } +#endif // ERTS_SIZEOF_ETERM == 8 break; case BIG_FLOAT: GET_DOUBLE(bw, f2); @@ -2710,6 +2717,7 @@ tailrecur_ne: // Float is within the no loss limit f2.fd = signed_val(bw); j = float_comp(f1.fd, f2.fd); +#if ERTS_SIZEOF_ETERM == 8 } else if (f1.fd > (double) (MAX_SMALL + 1)) { // Float is a positive bignum, i.e. bigger j = 1; @@ -2719,6 +2727,12 @@ tailrecur_ne: } else { // Float is a Sint but less precise it j = (Sint) f1.fd - signed_val(bw); } +#else + } else { + // If float is positive it is bigger than small + j = (f1.fd > 0.0) ? 1 : -1; + } +#endif // ERTS_SIZEOF_ETERM == 8 break; case FLOAT_BIG: GET_DOUBLE(aw, f1); -- cgit v1.2.3