[geos-devel] Re: Portable Quadtree
strk
strk at keybit.net
Tue Oct 21 20:43:22 EDT 2003
I've added an autoconf check to find 64bit integer definition.
Inserted in platform.h ifdef-switced typedef of int64 to long int
or long long int. long int will be the default but if that is not really
64bits a INT64_IS_REALLY32 macro is defined and a warning issued.
When (and if) we'll work out an alternative scheme we'll be able to use
that define to switch between the fast/portable way.
--strk;
mbdavis wrote:
> > used by bintree/Key.cpp. We might want to go for alternative
> > implementation of these two functions... what do you think ?
>
> Yep, that should work. I don't think those functions are intrinsically dependent on IEEE-754 - they just use knowledge of that format to speed up their performance.
>
> > that since they are guaranteed to be 64bits. What about defining
> > INT64 somewhere in the includes ?
>
> Sounds like a good idea. Again, the use of long is only because that's how Java gives you access to the bit pattern of floating-point. C++ might be able to use a union (but this would still be implementation dependent, so I guess that doesn't solve the problem)
>
> > Is there any test that would fail in case of a non IEEE-754 compiled
> > GEOS ?
>
> The one thing that *might* fail in non-IEEE-754 is the RobustDeterminant computation. However, I've taken a quick look at the original paper and it doesn't mention any such dependency, so I think we can just plunge ahead and not worry about it.
>
> Martin Davis, Senior Technical Architect
> Vivid Solutions Inc.
> Suite #1A-2328 Government Street Victoria, B.C. V8T 5G5
> Phone: (250) 385 6040 Fax: (250) 385 6046
>
>
>
> > -----Original Message-----
> > From: strk [mailto:strk at keybit.net]
> > Sent: Tuesday, October 21, 2003 10:47 AM
> > To: Martin Davis
> > Cc: Paul Ramsey
> > Subject: Re: Portable Quadtree
> >
> >
> > I've checked actual usage of bogus methods (powerOf2,biasedExponent).
> > While biasedExponent is only used by Quadtree.cpp, powerOf2 is also
> > used by bintree/Key.cpp. We might want to go for alternative
> > implementation of these two functions... what do you think ?
> >
> > Actually I don't know about IEEE-754 popularity. GCC have few
> > command line switches to modify its support but It looks like
> > defaulting to that format. My concern was only about shifting
> > amount bigger then number of bits in data type. It seems that
> > microsoft environment have no problems in 52-shifting long
> > integers, while gcc would like to use 'long long integers' for
> > that since they are guaranteed to be 64bits. What about defining
> > INT64 somewhere in the includes ? postgresql-7.3.4 typedefs int64
> > using autoconf checks. Excerpt from configure.in:
> >
> > dnl Check to see if we have a working 64-bit integer type.
> > dnl This breaks down into two steps:
> > dnl (1) figure out if the compiler has a 64-bit int type with working
> > dnl arithmetic, and if so
> > dnl (2) see whether snprintf() can format the type correctly.
> > (Currently,
> > dnl snprintf is the only library routine we really need for
> > int8 support.)
> > dnl It's entirely possible to have a compiler that handles a
> > 64-bit type
> > dnl when the C library doesn't; this is fairly likely when
> > using gcc on
> > dnl an older platform, for example.
> > dnl If there is no native snprintf() or it does not handle
> > the 64-bit type,
> > dnl we force our own version of snprintf() to be used instead.
> > dnl Note this test must be run after our initial check for
> > snprintf/vsnprintf.
> >
> > PGAC_TYPE_64BIT_INT([long int])
> >
> > if test x"$HAVE_LONG_INT_64" = x"no" ; then
> > PGAC_TYPE_64BIT_INT([long long int])
> > fi
> >
> >
> > Later on, ifdef HAVE_LONG_INT_64 ... typedefs int64 type.
> >
> > This might be the first step to take. Then we'll have to make sure
> > IEEE-754 is supported or find a (maybe slower) alternative
> > implementation.
> >
> > Is there any test that would fail in case of a non IEEE-754 compiled
> > GEOS ?
> >
> > --strk;
> >
> > mbdavis wrote:
> > > uh-oh... The current quadtree implementation in JTS is
> > highly dependent on the IEEE-754 double-precision floating
> > point format. This obviously isn't very portable to other
> > architectures. We may have to think of an alternative
> > implementation to Quadtree that uses a different scheme to
> > determine the sizes of the quads.
> > >
> > > Alternatively, for all internal GEOS uses it is possible to
> > use a STRtree instead of a Quadtree. strk, can you try this fix?
> > >
> > > Martin Davis, Senior Technical Architect
> > > Vivid Solutions Inc.
> > > Suite #1A-2328 Government Street Victoria, B.C. V8T 5G5
> > > Phone: (250) 385 6040 Fax: (250) 385 6046
> > >
> > >
> > >
> > > > -----Original Message-----
> > > > From: strk [mailto:strk at keybit.net]
> > > > Sent: Tuesday, October 21, 2003 12:13 AM
> > > > To: Paul Ramsey
> > > > Cc: Martin Davis
> > > > Subject: Re: Portable Quadtree
> > > >
> > > >
> > > > pramsey wrote:
> > > > > Ah, OK. I should turn on our old Ultra10 and see if GEOS
> > > > works at all :/
> > > > > P.
> > > >
> > > > Simple test on my architecture (i686):
> > > > Size of short: 2
> > > > Size of int: 4
> > > > Size of long: 4
> > > > Size of long long: 8
> > > >
> > > > Type 'long long' is a GNU extension. I don't know what
> > those Quadtree
> > > > methods are supposed to do, but I'm really not sure about
> > > > whether or not
> > > > it is really working here and now. G++ warning is:
> > > >
> > > >
> > > > index/quadtree/DoubleBits.cpp: In function `double
> > > > geos::DoubleBits::powerOf2 (int)':
> > > > index/quadtree/DoubleBits.cpp:12: warning: left shift count
> > > > >= width of type
> > > > index/quadtree/DoubleBits.cpp: In method `int
> > > > geos::DoubleBits::biasedExponent ()':
> > > > ../index/quadtree/DoubleBits.cpp:60: warning: right shift
> > > > count >= width of type
> > > >
> > > > powerOf2(int) and biasedExponent() might be broken. Or
> > they might know
> > > > exacly what they are doing ...
> > > > Martin, can you tell what you think about this ?
> > > >
> > > > --strk;
> > > >
> > > > >
> > > > > On Monday, October 20, 2003, at 12:48 PM, strk wrote:
> > > > >
> > > > > > pramsey wrote:
> > > > > >>
> > > > > >> Explain? We have a non portable qtree right now?
> > > > > >
> > > > > > There is a bitwise shift of 52 positions on a long integer
> > > > > > which is guaranteed to be at least 32 bit. Compiler issues
> > > > > > a warning so I thought it was a portability issue. Yury
> > > > > > does not get a warning there, I think we should inspect this.
> > > > > >
> > > > > > --strk;
> > > > > >
> > > >
> >
More information about the geos-devel
mailing list