Fri 06 Feb 2009 06:28:32 AM UTC, comment #17:
>You need also to remove the references to SIGALRM in main.c and
>psppire.c
Thanks for noticing!
With that change, I pushed these changes, and so I'm closing the bug. Michel, if there is still a problem, please do re-open it (or file a new one).
|
Fri 06 Feb 2009 05:53:24 AM UTC, comment #16:
You need also to remove the references to SIGALRM in main.c and psppire.c
Other than that, I'm happy with these patches.
|
Fri 06 Feb 2009 05:32:13 AM UTC, comment #15:
>...less than 15 lines isn't "legally significant"...
OK. Here is take 2, then.
I'm also attaching an actual fix for this bug.
(file #17410, file #17411)
|
Thu 05 Feb 2009 10:45:12 PM UTC, comment #14:
The guidelines at http://www.gnu.org/prep/maintain/maintain.html#Legally-Significant say that less than 15 lines isn't "legally significant", so I don't think we need to worry about these 4.
In the interests of proper attribution, perhaps we should retain a comment indicating the original author.
|
Thu 05 Feb 2009 03:27:42 PM UTC, comment #13:
>As there's no longer any 3rd party code involved, there's no
>reason for it to stay in lib/misc. It can go in src/math.
I was assuming that the first few lines of LevelOfSignificanceWXMPSR() came from Rob van Son, e.g. this code:
Given that, I was staying on the safe side by leaving it in lib/misc.
Am I wrong?
|
Thu 05 Feb 2009 07:30:52 AM UTC, comment #12:
As there's no longer any 3rd party code involved, there's no reason for it to stay in lib/misc. It can go in src/math.
|
Thu 05 Feb 2009 06:56:23 AM UTC, comment #11:
Here is a proposed patch to fix the performance problem. I have not yet written up a patch to remove or change the timer code, but pushing this commit would enable that.
(file #17404)
|
Thu 05 Feb 2009 06:27:31 AM UTC, comment #10:
>a) if we end up using routines from a third party library, then
>this won't be available to us
longjmp() from a signal handler out of arbitrary third-party code seems to be courting disaster. At the very least it invites memory leaks.
>b) Executing the test condition would have slowed the system even
>more.
If you do it right then you don't put the test in your innermost loop and the test is only a pair of test-and-jump instructions that the CPU branch predictor always gets right.
The model checking code contains something like this.
|
Thu 05 Feb 2009 05:34:07 AM UTC, comment #9:
> Do we really need to use setjmp()/longjmp() to break out of the algorithm though? If we avoid that, by inserting occasional code sequences of the form "if (timed_out()) return ERROR_CODE;", then it would be easy to make it portable.
I did consider that when I first wrote this command. I decided not to because a) if we end up using routines from a third party library, then this won't be available to us; b) Executing the test condition would have slowed the system even more.
However, it might be the best option now that we have (possibly) a fast algorithm of our own.
|
Wed 04 Feb 2009 03:27:00 PM UTC, comment #8:
>Even if that's true for this case, there will be many algorithms
>in other (yet to be implemented) subcommands in NPAR TESTS which
>are intractable. We'll need the timer for those (and to be keep
>spss refugees happy).
Definitely.
Do we really need to use setjmp()/longjmp() to break out of the algorithm though? If we avoid that, by inserting occasional code sequences of the form "if (timed_out()) return ERROR_CODE;", then it would be easy to make it portable.
|
Wed 04 Feb 2009 03:24:18 PM UTC, comment #7:
Actually, here's a solution that is even better. A test program using it calculates (correctly) and prints all the values for 1 <= N <= 30, 1 <= W <= N(N+1)/2, in under .2 seconds total*.
The runtime of this algorithm is O(N*W) and it uses O(W) space.
|
Tue 03 Feb 2009 10:22:17 PM UTC, comment #6:
> there's a lot of redundant calculation in ranksum2(). But that's still a big improvement, and good enough to get rid of the timer entirely I think.
Even if that's true for this case, there will be many algorithms in other (yet to be implemented) subcommands in NPAR TESTS which are intractable. We'll need the timer for those (and to be keep spss refugees happy).
|
Tue 03 Feb 2009 10:18:15 PM UTC, comment #5:
This is certainly very interesting. I spent quite a lot of time searching the literature for a more efficient algorithm, and concluded that there wasn't one.
0. Can you demonstrate that the two algorithms are identical?
1. What is the complexity of your new algorithm? It's not clear to me.
2. I'd like to see a statistician comment on this. The original algorithm's author asked for improvements to be sent to him. His home page is http://www.fon.hum.uva.nl/rob/ ; perhaps it would be appropriate to ask for his comments.
3. If this works, you should publish a paper on it.
|
Tue 03 Feb 2009 07:59:45 AM UTC, comment #4:
>Unless anyone has any better ideas, I suggest that we just compile
>out support for the TIMER subcommand on platforms which don't have
>a SIGALRM.
The real problem, I think, is that LevelOfSignificanceWXMPSR is astoundingly inefficient. The core of it is essentially this:
But that can be reimplemented in a much more efficient fashion as:
For N=30, W=120 ranksum1() takes 6 minutes 9 seconds on my system, ranksum2() takes 0.4 seconds. And they both return the same result.
(Am I missing anything here? This seems too easy.)
With dynamic programming I think I can do even better; there's a lot of redundant calculation in ranksum2(). But that's still a big improvement, and good enough to get rid of the timer entirely I think.
I'm attaching a test program that can be used to verify that both functions return the same result and to benchmark.
(file #17392)
|
Tue 03 Feb 2009 01:03:01 AM UTC, comment #3:
A bigger problem is the lack of SIGALRM on mingw. Sadly there doesn't seem to be anything in gnulib which can help us either.
Unless anyone has any better ideas, I suggest that we just compile out support for the TIMER subcommand on platforms which don't have a SIGALRM.
|
Mon 02 Feb 2009 06:50:45 PM UTC, comment #2:
We should probably fall back to using setjmp instead of sigsetjmp on mingw. It ought to work fine.
|
Mon 02 Feb 2009 06:44:31 PM UTC, comment #1:
Im looking closer to this bug, and seems like mingw doesn't have the implementation of sigjmp_buf. I will search if it will be done in the future, but meanwhile we should find a workaround, because this problem doesn't let new versions of pspp be compiled to windows.
|
Mon 02 Feb 2009 06:35:48 PM UTC, original submission:
OS: Gentoo using mingw to cross-compile
PSPP version: git master branch
Get this compile error:
src/language/stats/wilcoxon.c:373: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘env’
src/language/stats/wilcoxon.c: In function ‘give_up_callback’:
src/language/stats/wilcoxon.c:378: warning: implicit declaration of function ‘siglongjmp’
src/language/stats/wilcoxon.c:378: error: ‘env’ undeclared (first use in this function)
src/language/stats/wilcoxon.c:378: error: (Each undeclared identifier is reported only once
src/language/stats/wilcoxon.c:378: error: for each function it appears in.)
src/language/stats/wilcoxon.c: In function ‘timed_wilcoxon_significance’:
src/language/stats/wilcoxon.c:401: warning: implicit declaration of function ‘sigsetjmp’
src/language/stats/wilcoxon.c:401: error: ‘env’ undeclared (first use in this function)
src/language/stats/wilcoxon.c:403: error: ‘SIGALRM’ undeclared (first use in this function)
src/language/stats/wilcoxon.c:404: warning: implicit declaration of function ‘alarm’
make[2]: ** [src/language/stats/wilcoxon.lo] Erro 1
make[2]: Saindo do diretório `/home/michel/pspp'
make[1]: ** [all-recursive] Erro 1
make[1]: Saindo do diretório `/home/michel/pspp'
make: ** [all] Erro 2
|