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

 
 

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

Submitter:  Dan Sebald <sebald>
Submitted:  Wed 31 Jul 2013 04:36:42 AM UTC
   
 
Category:  None Priority:  5 - Normal
Status:  Done Privacy:  Public
Assigned to:  None Open/Closed:  Closed
* Mandatory Fields

Add a New Comment Rich Markup
   

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:


fputs (fid, "3.1\t-7.2\t0\r\n0.012\t6.5\t128");


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).


fprintf (fid, "3.1\t-7.2\t0%c%c0.012\t6.5\t128", 0x0D, 0x0A);



fprintf (fid, "3.1\t-7.2\t0%c0.012\t6.5\t128", 0x0A);


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:


fprintf (fid, "3.1\t-7.2\t0%c0.012\t6.5\t128", 0x0D);


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>
Group 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:



%!test
%! ## Header text
%! A.data = [3.1 -7.2 0; 0.012 6.5 128];
%! A.textdata = {"This is a header row."; ...
%!               "this row does not contain any data, but the next one does."};
%! A.colheaders = A.textdata (2);


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:



%!test
%! ## Column headers, only last row is returned in colheaders
%! A.data = [3.1 -7.2 0; 0.012 6.5 128];
%! A.textdata = {"Label1\tLabel2\tLabel3";
%!               "col1\tcol2\tcol3"};


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:



%!test
%! ## Row headers
%! A.data = [3.1 -7.2 0; 0.012 6.5 128];
%! A.textdata = {"row1"; "row2"};
%! A.rowheaders = A.textdata;


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


%! assert (h, 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:



  # Final cleanup to satisfy output configuration
  if (all (cellfun ("isempty", output.textdata)))
    output = output.data;
  elseif (! isempty (output.rowheaders) && ! isempty (output.colheaders))
    output = struct ('data', {output.data}, 'textdata', {output.textdata});
  endif


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>
Group 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>
Group 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.


x = rand(10000, 4);
t = [1:length(x)]';
fid = fopen('foo.csv', 'wt');
fprintf(fid, "ONE,TWO,THREE,FOUR,FIVE\n");
fprintf(fid, "%d,%g,%g,%g,%g\n", [t x]');
fclose(fid);

tstart = cputime();
aa = importdata('foo.csv', ',');
cputime() - tstart
plot(aa.data(:,1), aa.data(:,2))

tstart = cputime();
bb = importdata_new('foo.csv');
cputime() - tstart
plot(bb.data(:,1), bb.data(:,2))


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:


3,5c3,5
< # Date 1375243418 18000
< # Node ID afff4df11e99ea9692554b4f90137d0a35558a1b
< # Parent  bb713af2e1d93ab781e24b91f95e59965ee2912e
---
> # Date 1377116023 18000
> # Node ID c37ca0b694db97ada8c87194b9d48f4c83b5b75e
> # Parent  8520c264619ccc9456134ea960594f650318b045
189c189
< -      file_content_rows = [file_content_rows(1:i-1), \
---
> -      file_content_rows = [file_content_rows(1:i-1), ...



(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:


octave:460> aa = importdata_new ('foo.csv');
ans =    1.0000e-03
ans =  0.029996
ans = 0


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


octave:461> aa = importdata_new ('foo_b.csv');
ans = 0
ans =  0.033995
ans =  0.18297


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:



%!test
%! # Header
%! A.data = [3.1 -7.2 0; 0.012 6.5 128];
%! A.textdata = {"This is a header row."; \
%!               "this row does not contain any data, but the next one does."};
%


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


TIME VOLTAGE DISPLACEMENT
0 3.3 0.137
0.25 3.4 0.148
0.5 3.6 0.150


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


%!test
%! # Missing values
%! A = [3.1 NaN 0; 0.012 6.5 128];


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?



%!test
%! # CR for line breaks
%! A = [3.1 -7.2 0; 0.012 6.5 128];
%! fn  = tmpnam ();
%! fid = fopen (fn, "w");
%! fputs (fid, "3.1\t-7.2\t0\r0.012\t6.5\t128");


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 Files:
   
   
Comment:
   

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

 

Depends on the following items: None found

Items that depend on this one: None found

 

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

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only logged-in users can vote.

     

    Follow 5 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2013-08-31 rik5 StatusNone Done
        Open/ClosedOpen Closed
    2013-08-25 sebald Attached File- Added octave-importdata_rework-2013aug25.patch, #28935
    2013-08-21 sebald Attached File- Added octave-importdata_rework-2013aug21.patch, #28904
    2013-07-31 sebald Attached File- Added octave-importdata_rework-2013jul30.patch, #28717

    Back to the top

    Powered by Savane 3.13-f8d8.
    Corresponding source code