[postgis-tickets] [SCM] PostGIS branch master updated. 3.3.0rc2-426-ge5947ca16
git at osgeo.org
git at osgeo.org
Sat Dec 31 19:03:43 PST 2022
This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "PostGIS".
The branch, master has been updated
via e5947ca1623392882c0dcf3acfcac77d4202726d (commit)
via bef8e1c5b93cdd099b5135ae52a5ee3816dd4da8 (commit)
via 108a0c2aba8b57787b7d5d9ee0836dd22bb1798a (commit)
from 36a749a5446827350af5e7151f0b860c6e4de0a3 (commit)
Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.
- Log -----------------------------------------------------------------
commit e5947ca1623392882c0dcf3acfcac77d4202726d
Author: Regina Obe <lr at pcorp.us>
Date: Sat Dec 31 20:34:07 2022 -0500
News for GH718.
Closes https://github.com/postgis/postgis/pull/718 for PostGIS 3.4.0
diff --git a/NEWS b/NEWS
index 8871a3072..2f2750c86 100644
--- a/NEWS
+++ b/NEWS
@@ -20,6 +20,7 @@ xxxx/xx/xx
- Honour --mandir (and --prefix) configure switch for man pages install path (Sandro Santilli)
- Speed up check of topology faces without edges (Sandro Santilli)
- Speed up coincident nodes check in topology validation (Sandro Santilli)
+ - GH718, ST_QuantizeCoordinates(): speed-up implementation (Even Rouault)
* Bug Fix *
commit bef8e1c5b93cdd099b5135ae52a5ee3816dd4da8
Merge: 36a749a54 108a0c2ab
Author: Regina Obe <lr at pcorp.us>
Date: Sat Dec 31 20:30:21 2022 -0500
Merge remote-tracking branch 'rouault/faster_quantize_coordinates'
commit 108a0c2aba8b57787b7d5d9ee0836dd22bb1798a
Author: Even Rouault <even.rouault at spatialys.com>
Date: Tue Dec 27 18:14:13 2022 +0100
ST_QuantizeCoordinates(): speed-up implementation
We can completely avoid any floating-point computation by directly using
the fact that the IEEE-754 representation of a floating point number
contains the integral part of log2(abs(number)).
The improved trim_preserve_decimal_digits() function is ~ 7x times
faster.
diff --git a/liblwgeom/lwgeom.c b/liblwgeom/lwgeom.c
index c7a1d1cd5..fd8d3ae55 100644
--- a/liblwgeom/lwgeom.c
+++ b/liblwgeom/lwgeom.c
@@ -2505,37 +2505,34 @@ lwgeom_is_trajectory(const LWGEOM *geom)
return lwline_is_trajectory((LWLINE*)geom);
}
-static uint8_t
-bits_for_precision(int32_t significant_digits)
-{
- int32_t bits_needed = ceil(significant_digits / log10(2));
-
- if (bits_needed > 52)
- {
- return 52;
- }
- else if (bits_needed < 1)
- {
- return 1;
- }
-
- return bits_needed;
-}
+#define STATIC_ASSERT(COND,MSG) typedef char static_assertion_##MSG[(COND)?1:-1]
+STATIC_ASSERT(sizeof(double) == sizeof(uint64_t),this_should_be_true);
static double trim_preserve_decimal_digits(double d, int32_t decimal_digits)
{
- if (d == 0)
- return 0;
-
- int digits_left_of_decimal = (int) (1 + log10(fabs(d)));
- uint8_t bits_needed = bits_for_precision(decimal_digits + digits_left_of_decimal);
- uint64_t mask = 0xffffffffffffffffULL << (52 - bits_needed);
uint64_t dint = 0;
- size_t dsz = sizeof(d) < sizeof(dint) ? sizeof(d) : sizeof(dint);
-
- memcpy(&dint, &d, dsz);
+ memcpy(&dint, &d, sizeof(double));
+ /* Extract the exponent from the IEEE 754 integer representation, which */
+ /* corresponds to floor(log2(fabs(d))) */
+ const int exponent = (int)((dint >> 52) & 2047) - 1023;
+ /* (x * 851 + 255) / 256 == 1 + (int)(x * log2(10)) for x in [0,30] */
+ int bits_needed = 1 + exponent + (decimal_digits * 851 + 255) / 256;
+ /* for negative values, (x * 851 + 255) / 256 == (int)(x * log2(10)), so */
+ /* substract one */
+ if (decimal_digits < 0)
+ bits_needed --;
+
+ /* This will also handle NaN and Inf since exponent = 1023, and thus for */
+ /* reasonable decimal_digits values bits_needed will be > 52 */
+ if (bits_needed >= 52)
+ {
+ return d;
+ }
+ if (bits_needed < 1 )
+ bits_needed = 1;
+ const uint64_t mask = 0xffffffffffffffffULL << (52 - bits_needed);
dint &= mask;
- memcpy(&d, &dint, dsz);
+ memcpy(&d, &dint, sizeof(double));
return d;
}
diff --git a/regress/core/quantize_coordinates.sql b/regress/core/quantize_coordinates.sql
index 02f21d742..fefa849c5 100644
--- a/regress/core/quantize_coordinates.sql
+++ b/regress/core/quantize_coordinates.sql
@@ -11,4 +11,14 @@ SELECT 't5', ST_X(ST_QuantizeCoordinates('POINT (1.2345678 1.2345678)', 7, 4)) !
-- Significant digits are preserved
WITH input AS (SELECT ST_MakePoint(1.23456789012345, 0) AS geom)
SELECT 't6', bool_and(abs(ST_X(geom)-ST_X(ST_QuantizeCoordinates(geom, i))) < pow(10, -i))
-FROM input, generate_series(1,15) AS i
+FROM input, generate_series(1,15) AS i;
+-- Test also negative precision
+WITH input AS (SELECT ST_MakePoint(-12345.6789012345, 0) AS geom)
+SELECT 't7', bool_and(abs(ST_X(geom)-ST_X(ST_QuantizeCoordinates(geom, i))) < pow(10, -i) AND abs(ST_X(geom)-ST_X(ST_QuantizeCoordinates(geom, i))) > pow(10, -i - 3))
+FROM input, generate_series(-4,10) AS i;
+-- Test NaN is preserved
+SELECT 't8', ST_X(ST_QuantizeCoordinates('POINT EMPTY', 7, 4)) IS NULL;
+-- Test that precision >= 18 fully preserves the number
+SELECT 't9', ST_X(ST_QuantizeCoordinates('POINT (1.234567890123456 0)', 18)) = ST_X('POINT (1.234567890123456 0)');
+-- Test very low precision
+SELECT 't10', abs(ST_X(ST_QuantizeCoordinates('POINT (1234567890123456 0)', -18)) - 1234567890123456) <= pow(10, 18);
diff --git a/regress/core/quantize_coordinates_expected b/regress/core/quantize_coordinates_expected
index 7c37d832b..05e6eafc1 100644
--- a/regress/core/quantize_coordinates_expected
+++ b/regress/core/quantize_coordinates_expected
@@ -4,3 +4,7 @@ t3|t
t4|t
t5|t
t6|t
+t7|t
+t8|t
+t9|t
+t10|t
-----------------------------------------------------------------------
Summary of changes:
NEWS | 1 +
liblwgeom/lwgeom.c | 49 ++++++++++++++----------------
regress/core/quantize_coordinates.sql | 12 +++++++-
regress/core/quantize_coordinates_expected | 4 +++
4 files changed, 39 insertions(+), 27 deletions(-)
hooks/post-receive
--
PostGIS
More information about the postgis-tickets
mailing list