Update on Qhull for Octave and R

[Brad Barber]

Hi all,

[please let me know if you are not interested in this discussion]

It looks like a new release of Qhull is in order.   The gcc 4.4 build fails on 
64-bits with strict-aliasing.  With a debug build, I was able to identify the 
problem (writes swapping places in qset.c when the element pointer and the size 
pointer are the same).   Union types and a better understanding of 
strict-aliasing fixed the problem.  Although the binary code hasn't changed, 
there are many changes to the source.  It will need a thorough, low-level test 
of qset.c and mem.c.  

Your discussion of Octave and R and a better understanding of the Octave build 
made me realize that Octave and R uses the static version of  qhT (i.e., 
qh_QHpointer==0), while Qhull 2010 and 2011 use the dynamic version of qhT 
(i.e. qh_QHpointer==1).   Code written against qhull.lib will not work with 
qhull6.lib and vice versa.  Unfortunately, the linker considers the two 
instances of qh_qh (qhT and qhT*) as different entities, and thus does not 
report an error for the mismatch.

Here's a plan.  Let me know about errors, omissions, and suggestions.

1) Write a test program for qset.c and mem.c to validate the many changes to 
qset.c

2) Add qhull.lib/qhull.so to the builds.  It will use qh_QHpointer=0 and static 
qh_qh.  T.  This is the same configuration as used for Octave, R, qhull, 
qconvex, etc.  It produces the fastest code.   The library will be 
qhull.so.5.2.2

3) Keep qhull6.lib/qhull6.so as is.  It uses qh_QHpointer=1 and a 
heap-allocated qh_qh.  The library will be qhull6.so.6.2.2.  This is the same 
configuration as used for qhull 2010.1 through qhull 2011.2.  It makes it easy 
to swap instances of Qhull.  The C++ interface to Qhull uses this version.  
Note that the global pointer (qhT *qh_qh) makes the interface clumsy.  It hides 
much of the detail, but can't hide all of it.  Last I measured it, it was about 
4% slower than qhull 5.

4) Release qhull 2011.3 with these changes.  It will be two shared libraries 
(qhull.so and qhull6.so) and two static libraries (qhullstatic.a and 
qhullstatic_p.a).  Someone will need to update the Debian build, R integration, 
Octave integration, and Linux packages.

5) Over the next year, develop a new version of Qhull that passes qhT as a 
parameter.  Its library will be qhull7.so.7.n.n   Remove all global data.  This 
allows simultaneous execution of multiple Qhull instances.   Pete Klosterman at 
Flash Foto Inc. did the original work.   It will be slower than qhull 5 and 
qhull6.

6) Along with the development of qhull7,  define possible 64-bit data as 'long' 
(or 'long long' on windows 64-bit).   This will expand the size of memory 
supported by Qhull.  Qhull runs fine on 64-bit hosts, but it uses 'int' for the 
size of memory allocations, sets, and identifiers.   Eventually qhull 
overflows.    In qhull 2011.2 it reports an error.  It previous versions of 
qhull, it seg faults.  Note that qhull5 and qhull6 will not change.

7) Rework the C++ interface for qhull7 and abandon the C++ interface for 
qhull6.  Retain as much of the interface as is practical.  The interface ought 
to be clean because the qhT parameter is similar to an object pointer.

8) Continue to support the qhull5 and qhull6 libraries indefinitely.  The qhull 
executables (qhull, qconvex, etc) will continue to use the static library.   

9) Eventually, someone will rework qhull to make effective use of multiple 
cores for a single instance of qhull.  My guess is that it would be a C++ 
program that calls into qhull7 as needed.

                                --Brad