Mon 31 Jul 2017 11:30:17 PM UTC, comment #15:
I pushed your documentation fix on to the stable branch (http://hg.savannah.gnu.org/hgweb/octave/rev/d396866fa7d8) and then merged it to the development branch. I removed the reference to the limitation note from the first line of the function. The first line should be just a short description of the function and this would cause the documentation for regexp to differ from all other Octave functions.
|
Fri 28 Jul 2017 06:50:52 PM UTC, comment #14:
Changeset attached. The point of adding the extra sentence at the start of help is to hopefully avoid more bug reports.
(file #41367)
|
Fri 28 Jul 2017 05:29:42 PM UTC, comment #13:
Better documentation is always welcome. Do you want to make a cset to apply?
|
Fri 28 Jul 2017 05:05:04 PM UTC, comment #12:
Yeah, it's unfortunate this routine is so fragile. Should we put a note up front in the regexp help about this? Something like
A segfault/stack-overflow is such a bad thing because the session history is lost. I'm wondering if there is a way we could protect the stack from overflowing (doesn't sound like). One thing I've often wondered is if Octave processing could have a level of protection against this sort of thing, whether it is seg-faults or cntrl-C whereby it unwinds the stack or "local" memory. That is, something like
Big change of course, a bit OS-like, but perhaps more graceful.
|
Fri 28 Jul 2017 04:14:13 PM UTC, comment #11:
It seems like there have been enough suggestions offered that there is a way to code around this, and that the full issue lies upstream with PCRE. I'm going to close this report.
|
Fri 28 Jul 2017 05:42:29 AM UTC, comment #10:
@Dan
you are perfectly right assuming that I'm searching for everything that matches exponential notation numbers. The reason I am not searching for the string 'Step' is that it is rather special to this file and not general purpose. Imagin a similar file where the block headers are prety randomly formated text and there is no easy way to define a fitting mach on them. (Yes, that's ugly and I admitt that my example does not do a particularly good job at exposing this aspect of the problem.) But you guys just gave me the idea of searching for everything that does not match exponential notation numbers. This should come closer to the general aplicability I need and reduce the number of machtes.
@Rik
<<Neither Matlab nor Octave is exceptionally good at text processing.>>
I alwasy wondered why thats the case... ;-)
@ all
Thank you for your effort to look into this. You are doing a great job...
|
Fri 28 Jul 2017 04:57:21 AM UTC, comment #9:
The method that Rik suggests is often how I do processing on a formatted file of the sort you have.
However, one should still be able to make use of regexp() by thinking more in terms of parring down starting with bigger hunks. I think the issue is that the regexp construct you've used gets way too many hits and therefore the recursion is too high that stack overflow occurs. It looks like you are searching for everything that matches exponential notation numbers. Instead, try thinking of ways to reduce the number of "hits".
For example, this regexp() will first produce the blocks:
The SP should contain all the text between the "Step" in the file. Loop through the SP and then use regexp() again to find maybe all individual lines. Then toss out the line that doesn't have the exponential floating point numbers. Then pick the first and last exp-floating point lines.
There are probably a half dozen uses of expressions keeping and/or discarding content, etc. that should get what you want. Experiment a bit I guess.
|
Fri 28 Jul 2017 04:14:22 AM UTC, comment #8:
I've tried pcre_dfa_exec(). Unfortunately, it isn't 100% compatible with pcre_exec(), i.e., Perl. And probably one of the few spots they differ is the '+'. It's strange, for length 3 input buffer, i.e., "aaa", it works:
but anything larger produces
The reason is that the number of matches returned by pcre_dfa_exec() is zero (i.e., non-valid dimension).
The "(a)" pattern seems to produce the same result for large input buffer size, but I'm just noticing now that pcre_exec is slightly different than the above result:
Well, I have no faith in switching to the pcre_dfa_exec() given the differences.
|
Thu 27 Jul 2017 10:37:26 PM UTC, comment #7:
Stack overflow seems to fit the behavior. Here is some info on the stack usage:
http://pcre.org/original/doc/html/pcreapi.html#SEC22
http://pcre.org/original/doc/html/pcrestack.html
http://pcre.org/original/doc/html/pcretest.html
I don't see the pcretest utility on my system, so I can't test. But I think you are right, now that I read a little bit. The stack recursion is described in one of the above links. They use a "match()" recursion so that it can back out of where it was in some way. Because of all the a's, I suspect the recursion is going something like
and so on. I'm going to guess that match doesn't use much stack, but all it takes is to push as much as a return address and eventually the stack will overflow.
There is a comment in the documentation:
"
If PCRE has been compiled to use the heap instead of the stack for recursion, the value returned is the size of each block that is obtained from the heap.
"
Unfortunately, as I think PCRE is a library, that heap option is out of our control and instead done at the system level.
But, there may be an alternative function:
http://pcre.org/original/doc/html/pcrestack.html
pcre[16|32]_dfa_exec()
That might be the function we want, it only does recursion in limited circumstances... I'm about to leave for a few hours, perhaps you could investigate.
|
Thu 27 Jul 2017 10:26:23 PM UTC, comment #6:
@Mike: If you want to research how to tune PCRE I'm fine with that. Otherwise, I'm fine with calling this an upstream issue in PCRE.
@Marcin: Neither Matlab nor Octave is exceptionally good at text processing. If you have lots and lots of data, and several different block identifiers, it is probably better to select a different tool such as Perl to pre-process the data.
I will say that the normal paradigm when dealing with large data is to work on it in small chunks. It may have been only a demonstration program, but loading an entire file as the attached script does is always going to be a problem.
A better plan of attack would be something like this
This still isn't particularly fast, but it's not prone to segfaults.
|
Thu 27 Jul 2017 09:41:31 PM UTC, comment #5:
Dan - the segmentation fault looks to me to be due to excessively large number of stack frames, i.e. overflow due to recursion.
On my system, my example first errors out around a length of 7923. I say around because it is not deterministic, at 7925 it crashes 100% of the time, at 7923 it crashes maybe 20% of the time.
If I then decrease the maximum stack size soft limit (ulimit -s), it crashes at a much smaller subject string size. It's about proportional, decrease the stack size limit by half, the subject string crash limit also halves.
So this goes back to the PCRE implementation which uses stack recursion in some way to deal with match groups, and the library has internal variables to set limits on the number of matches and the maximum recursion limit, but I haven't fully looked into what these tunable parameters do. These things are referred to in the PCRE docs, so I wouldn't jump to calling it a bug, but a tunable parameter that might need to be adjusted in how Octave uses PCRE.
|
Thu 27 Jul 2017 09:31:46 PM UTC, comment #4:
Regardless of the application, this certainly looks like a bug. And best I can guess it is a PCRE bug. There are a few buffers constructed via OCTAVE_LOCAL_BUFFER and then passed into the prce_exec() routine:
but none of them are large working buffers, just small ones which accept returned offset values in the buffer.
Note some small variations on MM's example:
pattern = 'a+';
does not fail. And without the capture syntax (), the ovector size is one triple less, i.e.,
returns subpatters=0.
pattern = '(a)';
does not fail. It returns a very large number of cells, i.e., 'a', 'a', 'a', etc., but doesn't crash. To me, this seems more memory intensive than pattern '(a)+', which groups all the 'a's together in one string.
pattern = '(?:a)+'
surprisingly does fail. This is supposed to be non-remembering capture and is suggested if the capturing version has too much of a performance hit.
Also, the call to pcre_exec() fails immediately, with no jump in system memory.
MM's example fails at 8441 for the length of "aaaaa...a". That doesn't seem particularly large.
So there seems like a bug in PCRE, due to large array size, but not related to running out of memory.
Probably the best thing to do would be write a very short C program that replicates this "aaaa...a" example and submit to PCRE as a bug report.
|
Thu 27 Jul 2017 07:24:27 PM UTC, comment #3:
Well Rik, not entirelly...
...the file I need to parse is a bit more complicated. It consists of several blocks of data following one another in a single file. Each block has a header of serveral linse of text and many records of data. These are organized in several columns. Have a look at line 1505, 3008 or 4511 in oc.txt to see some of the other block headers.
The goal I am trying to achieve is to parse this type of file into some kind of data structure which octave can handle. As far as I know, neither octave nor Matlab has any kind of function, which would offer an easy way to parse a multi block file with arbitrary formated headers for each block. Please let me know if I'm wrong and there is such a way.
As the headers vary as well as the number of records (lines) per block vary as well, I figured that the most flexible way is to find the first and the last data point in every block and separate them tha way. This is what that regexp is supposed to do. It's the best I could come up with...
I am pretty aware that using regexp for this porpose is quite heavy handed (the data in oc.txt is only a really tiny example. Real data files have many more blocks whith each block having many more records with way more columns. Data file size can exceed 1GiB easily.) So if you know some better way to achieve this I'd be happy to know...
Thanks
|
Thu 27 Jul 2017 05:42:33 PM UTC, comment #2:
Yeah I can easily reproduce this crash with a pathological test case like the following:
It might be possible to experiment with the pcre settings on limiting recursion to see if that helps, to avoid a segfault, but I don't know what impact that has on performance or getting the results that the user wanted.
|
Thu 27 Jul 2017 05:25:02 PM UTC, comment #1:
Confirmed, but I used gdb to check and the segfault is coming from libpcre, rather than Octave. Is there a better pattern to use to accomplish what you want? The pattern
creates a capture-block which may or may not match because of the ending asterisk. The capture buffer has to be allocated out of dynamic memory because it doesn't know in advance what it will find in the text. In this case, it looks like there are over 80,000 matches and probably more than 1M of memory required. That is exceptionally large.
It seems like this is just a tab-separated data file with the first two lines being a text header. If you just want to read the data in to Octave this would be easier.
|
Thu 27 Jul 2017 12:08:33 PM UTC, original submission:
Octave crashes when executing grgexp(). To reproduce the problem, run script in attached archive. May by similar to bug #45031 and bug #29438 (both closed)
Marcin
|