Segmentation fault

[bpradeep20]

in cpp/test/example.C if instead of generating random points data is read from a file than it is giving segmentation fault. Problem seems to be in Subspan.C void Subspan<Float, Pt, PointAccessor>::append_column() where SEB_ASSERT(r < dim); doesn't fail even when r and dim are equal. Problem might occur because of calling function void Subspan<Float, Pt, PointAccessor>::add_point(int index) which increase r after every iteration and when it is called with size() -1 then r is equal to dim and hence can cause problem.

Points used for testing were generated using rbox (http://www.qhull.org/html/rbox.htm) rbox 10000 n s D200 B1 10000 points in 200 dimension uniformly distributed on a sphere of radius 1

[polymesh]

I experienced the same problem today with my own dataset of points and tracked it down to that same function. Any luck working around it? I do have a txt file containing a point list if anyone is interested. http://sdrv.ms/1bwJnE9

It dies on point number 233 or therabouts, but as far as I can tell there's nothing too strange about that point. It's difficult for me to debug as even after reading the comments on these variables, I still am not quite sure what they are for or what they are doing.

[hbf]

@polymesh Thanks for a file to reproduce the problem.

I am using the fromfile.C program (see https://gist.github.com/hbf/7715996) to read in the points and compute their miniball. For this, I have added two lines (the number of points and the dimension) to your data file, see https://gist.github.com/hbf/7716006.

I then do

g++ -I../main fromfile.C -o fromfile -O3
./fromfile 14.data 

to compile the program with assertions enabled and run it. This gives:

=====================================================
Reads points from a file and computes their miniball.
The file is assumed to start with two integers, the
number of points and the dimension.  Then come the
n points, each in a line of d floating-point numbers.
=====================================================
Starting computation...
Squared radius = 1.66410067457418648e+02
Center = -2.26435441680732481e+01 -3.19121143269440832e+00 2.81840078311099784e+00 
=====================================================
Solution errors (relative to radius, nonsquared)
  final QR inconsistency     : 2.93747982172879320e-15
  minimal convex coefficient : positive
  maximal overlength         : 0.00000000000000000e+00
  maximal underlength        : 1.37702052663609110e-16
=====================================================
Took 2.58999993093311787e-04ms.

In other words, the program does not crash on my machine and I therefore need more information to tackle the problem.

This is on a MacBook Pro Intel Core i7.

Could you please confirm whether or not this runs on your machine?

[bpradeep20]

@hbf I have sent you a mail on kf@iaeth.ch dated October 29, 2013 with a sample file which was giving me segmentation fault. Can you try to run it on your machine and see whether problem replicate on your machine. (though you might need rbox to generate points)

[hbf]

@bpradeep20 I don't have rbox installed. Could you please just send me the pointset, preferably in the format that fromfile consumes? I'll take a look then.

[bpradeep20]

https://drive.google.com/folderview?id=0B7eE6-Hm1zdrdTRnQ1FmQkN4blk&usp=sharing this contains two files points.txt file contains points and is of 40MB. to run give filename i.e., points.txt as argument

[polymesh]

OK, tried your code. I had to comment a bunch of timer stuff out that is not compatible with windows, but after that it worked just fine with your main function. The first thing I changed however to match my implementation broke things in the same way. In particular, you were using "double" as a float type and I am using "float". Switch those and see if you get the same segfault. Note, I changed it in 2 places line 10 and 44.

[polymesh]

I also went back to my old code and changed it to double, and it works great! Curious why float would fail though...

[hbf]

@polymesh I am not surprised it fails when you replace double with float as the algorithm internally uses some thresholds to determine when the solution is "good enough" and the iteration process can be stopped (see Eps in Subspan.h). Currently, these constants is tailored to double; when you instantiate the code for float, the rounding errors accumulated during the computation will be much larger and Eps will simply be too small for some inputs.

I will add a warning to the README pointing out that that code should be used with Float=double only, at least for the time being.

[bpradeep20]

@hbf @polymesh so if it is breaking on ubuntu then is it system dependent problem?

[hbf]

Nope, if it crashes/loops forever on Linux with double then that is a bug and should be fixed (as part of this issue)!

[hbf]

@bpradeep20 I have just compiled your test.C program and run in on the point set you provided in your link above. I can reproduce the problem on a Mac. I am investigating what the cause is. What I see already is that the input is a bit particular in that there are less than d+1 points in your point set (n=200 in d=10,000). However, the code must not crash, so it's clearly a bug.

[bpradeep20]

@hbf dimension d = 200 and n = 10,000 in my code, please check in code first line of points.txt is d and second is n

[hbf]

Oh, yes, sorry for the confusion.

I think I have identified the problem. Can you please take a look at the change in https://github.com/hbf/miniball/pull/16 (which I merged already to master) and see whether this fixes the problem on your side?

When I run your point set using fromfile.C (which reads d and n in a different order than your test.C), it runs without problems and outputs a good result.

[bpradeep20]

@hbf thanks for the fix Ya now it worked correctly (though I do not know where fromfile.C is there but it worked for my file)

[hbf]

@bpradeep20 Glad to hear this fixed it.

(fromfile.C is in this gist, see comments above: https://gist.github.com/hbf/7715996)

[polymesh]

Thank you for your time and quick response and for the awesome algorithm!

[hbf]

Thank you, @polymesh, happy to help!