patchGNU Octave - Patches: patch #8140, Speed up importdata() ASCII CSV...

 
 

patch #8140: Speed up importdata() ASCII CSV processing using dlmread() as core

Submitted by:  Dan Sebald <sebald>
Submitted on:  Wed 31 Jul 2013 04:36:42 AM UTC  
 
Category: NonePriority: 5 - Normal
Status: DonePrivacy: Public
Assigned to: NoneOpen/Closed: Closed

Add a New Comment (Rich MarkupRich Markup):
   

You are not logged in

Please log in, so followups can be emailed to you.

 

(Jump to the original submission Jump to the original submission)

Sun 01 Sep 2013 11:31:00 PM UTC, comment #9:

I rolled back to a few days ago to compile octave and download the latest importdata.m. Looks nice. I'll have to look through some of the regexp, etc. mods to see the improvements at some other time.

The CR/LF case works, at least on Unix. I suspect you are worried that creating the test file:

will create a file on Windows systems in which the linebreaks are CR-CR-LF and the test will fail. However, we might be able to change the way in which the data file is generated by using explicit output data 0x0D (CR) and 0x0A (LF).

So we know we can generate files that are sure to have CR, or LF, or CR-LF. The question is whether these can all be handled properly on all platforms. If dlmread() can do so, then I see no problems with having these tests in place. If in the future dlmread() does not support these, then the tests can be removed. Both of the above pass the tests. This one:

fails. (We knew that.)

I looked at dlmread. It is using "getline (*input, line);" to get a line of the file. I think getline is a C or C++ library function. We could program a fix for the last case easy enough by searching for the first CR or LF and check whether the line delimiter is CR, LF or CRLF. Then we can use a delimiter as part of the getline() routine:

http://www.cplusplus.com/reference/string/string/getline/

I think if we support CR, LF and CRLF we are preserving compatibility whatever the case.

Dan Sebald <sebald>
Sat 31 Aug 2013 09:42:49 PM UTC, comment #8:

Dan,

I applied your changset for importdata here (http://hg.savannah.gnu.org/hgweb/octave/rev/44624eb20076) and then followed it with another changset (http://hg.savannah.gnu.org/hgweb/octave/rev/95412dcfa707). The second changeset overhauls the delimiter detection, speeds up the function by always using dlmread even in the case of the space delimiter, and generally reduces the length of the function.

One remaining issue is what to do about CSV files that are CR or CRLF line-delimited. We have %!tests for both of these cases, but I don't think that is quite right. The meaning of "\n" will change based on the platform (UNIX, Windows, Mac). If you are bringing a file from one platform to another it is usually required that the user themselves convert the file before further processing by using a utility such as dos2unix. Unless we can prove that Matlab is handling this case, I think this is the responsibility of the user and we can delete these %!tests.

Rik <rik5>
Project Administrator
Sun 25 Aug 2013 05:06:00 PM UTC, comment #7:

A lot of small changes from the previous patch:

  • The double ## appears more prevalent in the script files, so I went with that. (My preference may be for single quotes.)
  • I added some more tests to confirm that automatic detection of delimiter is working.
  • I changed one of the tests (Header text) to replicate the text data as column headers:

I think that is right, but not sure.

  • I changed one of the tests (Column headers, only last row is returned in colheaders) to have tabs between the ASCII characters of the textdata:

I think that is correct, at least what I would expect.

  • I changed one of the tests (Row headers) so that the text data matches the row headers:

because that seems consistent to me with behavior for the colheaders scenario. Also note above that I changed the orientation of cell entries to be a column rather than a row because that makes more sense to me. I also made the alteration that the value of h, i.e., number of HEADER_ROWS, is expected to be 0

because there are no header rows in the sample file. If that is supposed to be more generally just HEADERS, then we'll have to change the documentation. One further note about the row headers approach is that it uses the slower file access method after dlmread() is called, but in all likelihood there aren't going to be big data files having thousands or tens of thousands of row headers. (What use would they be?).

  • I programmed importdata to agree with the (Missing values) test. It's an easy cleanup at the end of the function:

but somehow I'd hope/wish that isn't the desired result. It's enough that someone using the routine has to test for the existence of the field names "textdata", "colheaders", "rowheaders", to create a general data importing scheme, and with this configuration it means the user also must test whether the returned output is a matrix or a structure. (Probably one of those cases where things were added over time and backward compatibility was preserved.)

With those changes, it is only the exponential test and the last test (CR for line breaks) that fails, and we'll leave that one active as a reminder to change dlmread().

(file #28935)

Dan Sebald <sebald>
Sat 24 Aug 2013 02:57:30 PM UTC, comment #6:

Multiple lines of header text are definitely supported by Matlab. See this page which has two examples of actual importdata usage (http://www.mathworks.com/help/matlab/import_export/import-numeric-data-and-header-text-from-a-text-file.html).

The "exceptional values" test shouldn't be running. It is introduced as '%!#test' which comments it out. Given that dlmread will read Inf and NaN values, I think this should work.

I agree that dlmread should probably be modified to accept different EOL characters. I think there may already be a bug report on that.

So, it doesn't seem too far from working, just some more attention for the corner cases.

Rik <rik5>
Project Administrator
Sat 24 Aug 2013 04:31:11 AM UTC, comment #5:

I suspected the existing headers weren't exactly right because it seemed like too much was assumed about spaces and multiple lines. Generally, I always think of CSV as having just one possible header, so in the patch as a first start I only handle one, barring any knowledge of how it is expected to behave more generally. This also hinges on how dlmread() handles headers as well--dlmread, or it core code, may need adjustment. Nonetheless, the current header behavior is obviated by what is in the patch.

I just ran the tests on the patched file. 6 of the 13 tests failed.

Two of the failed tests have to do with the multiple text lines for column headers. This probably shouldn't be too hard to fix, but I'm still wondering if multiple lines of header text should be supported.

The row headers example fails because the first column is being read as NaN instead of being skipped--since dlmread allows specifying a range to extract, I think I can fix that one easy enough.

The next fail is one that combines both column and row headers--no surprise there. The "exceptional values" test fails with some comment in there about not knowing whether exceptional values in CSV are supported.

The missing values fails, but the data is read properly--the only problem is that the return format isn't correct, conditioned on the number of output arguments.

The very last one is carriage return \r only for line breaks--dlmread() fails on that an is creating complex numbers. I think dlmread() should be modified to support just \r line breaks. If not, then it is an easy fix of replacing all \r by \n as a first step. I don't like that fix though because it necessitates scanning/processing the whole file in script code before letting dlmread() do the work. Right now, it is only if dlmread() creates NaNs that the patch resorts to script code to do much of anything.

I won't have time for a few days, but I'll create a patch that behaves according to the tests whether we know they are right or wrong, but I'm going to leave the \r test as is.

Dan Sebald <sebald>
Sat 24 Aug 2013 03:16:00 AM UTC, comment #4:

Well, this time I went ahead and wrote the tests first. I committed those tests here (http://hg.savannah.gnu.org/hgweb/octave/rev/8cfc28809a07). The current implementation, without your patch, doesn't handle rowheaders or colheaders correctly so I stopped.

Rik <rik5>
Project Administrator
Wed 21 Aug 2013 08:20:19 PM UTC, comment #3:

I'm including some sample code to test out this patch before and after ("importdata_new") applying the patch.

Dan Sebald <sebald>
Wed 21 Aug 2013 08:17:40 PM UTC, comment #2:

Update of patch because of hunk failing due to the following difference:

(file #28904)

Dan Sebald <sebald>
Mon 12 Aug 2013 07:32:16 PM UTC, comment #1:

Hello Dan,

Sorry about my late reply.

Nice performance improvement you've got there.
Here are my thoughts:

1. Column / Row header detection:
The detection of Column / Row headers is being done at line 296-301 in the code (tip version, i.e. non-patched). It is simply comparing the dimensions of the textdata cell array to the number of columns/rows. If you have exactly the same number of data columns as there are words in the header (and using space as delimiter) I think we have to assume that these are Column headers.

Wouldn't the header "TIME VOLTAGE DISPLACEMENT" in your example be interpreted as column headers by Matlab? I think so.

2. Missing values
I think it makes sense as you said to put the empty string in the output.textdata, but I think that Matlab is ignoring it since it's empty. I don't have access to Matlab at the moment, so I cant check it right now.

3. CR for line breaks
I agree, sounds like the change (to accept \r) should be made to dlmread ().

regards,
Erik

Erik Kjellson <erikiiofph7>
Wed 31 Jul 2013 04:36:42 AM UTC, original submission:

I reworked the importdata script to use dlmread() as the core. Last night I was working with a relatively small CSV file and thought the loading times were much greater than they should be.

Here are some CPU times for various parts of the importdata routine (the size of the data is 7383 x 5):

ans = 0.0099990
ans = 0.089986
ans = 0
ans = 0
ans = 0
ans = 0.097985
ans = 0.49592
ans = 3.6494

The main thing to note from this is basically that the first stages involving the regexp routine are rather efficient and the last stages which involve double looping are quite the opposite.

which I think has enough flexibility with its arguments to handle the importdata CSV ascii case. It is so efficient that I think a better approach is to

1) Just fscanf the first header lines of the file (as opposed to reading in the whole data file)

2) Use dlmread() to do all the work, which places NaN for the cases where the conversion failed

3) Look at the data matrix for any NaN and then retroactively read in the data file and then compute where the associated lines are. I think I've done it efficiently so that every entry of the file need not be extracted, just the lines where the NaN occurred.

The last step slows things down, but it is still pretty efficient. Here is the CPU consumption for stages of the revamped importdata:

Here are the results when I place a couple text strings amongst the data columns:

Having to pull the data back in and apply regexp adds some, but still compared to the current importdata.m it is rather minuscule.

There are three tests that fail after applying the patch. We can discuss those. Basically, I don't agree with some of the results:

I think that treating text with spaces rules out using space characters as delimiter and automatically recognizing column names. For example, if the first lines of my data file were

how can we tell that the first line should be data column titles or just some textdata?

The above test produces the correct data output.data, but while this expectation is just the data, the new routine is creating output.textdata for that NaN result which happens to be an empty string. Isn't that the proper result?

The new version of importdata fails on the above test, and it would be easy to correct as a first step by searching and replacing any \r with \n. However, I wonder if the proper fix for this would be a simple addition to dlmread(). So let's hold off on this test until we are certain where it should be fixed.

Dan Sebald <sebald>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach File(s):
   
   
Comment:
   

Attached Files
file #28935:  octave-importdata_rework-2013aug25.patch added by sebald (13kB - application/octet-stream)
file #28904:  octave-importdata_rework-2013aug21.patch added by sebald (9kB - application/octet-stream)
file #28717:  octave-importdata_rework-2013jul30.patch added by sebald (9kB - application/octet-stream)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -unavailable- added by rik5 (Posted a comment)
  • -unavailable- added by erikiiofph7 (Posted a comment)
  • -unavailable- added by sebald (Submitted the item)
  •  

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 5 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Sat 31 Aug 2013 09:42:49 PM UTCrik5StatusNone=>Done
      Open/ClosedOpen=>Closed
    Sun 25 Aug 2013 05:06:00 PM UTCsebaldAttached File-=>Added octave-importdata_rework-2013aug25.patch, #28935
    Wed 21 Aug 2013 08:17:40 PM UTCsebaldAttached File-=>Added octave-importdata_rework-2013aug21.patch, #28904
    Wed 31 Jul 2013 04:36:42 AM UTCsebaldAttached File-=>Added octave-importdata_rework-2013jul30.patch, #28717

    Back to the top


    Powered by Savane 3.1-cleanup