bugGNU Octave - Bugs: bug #50416, dir command is very slow with...

 
 

bug #50416: dir command is very slow with large directories

Submitter:  Avinoam Kalma <avinoam>
Submitted:  Tue 28 Feb 2017 05:22:11 AM UTC
 
Category:  Octave Function Severity:  3 - Normal
Priority:  3 - Low Item Group:  Performance
Status:  Fixed Assigned to:  None
Originator Name:  Open/Closed:  * Closed
Release:  * dev Operating System:  * Microsoft Windows
* Mandatory Fields

Add a New Comment (Rich Markup)
   

Comment Type & Canned Response:
       

 

( Jump to the original submission )

Sat 18 Mar 2017 05:22:19 PM UTC, comment #9: 

I don't know how to debug any further.  This works for me.  Since this is just an m-file I copied it over to my windows XP VM under the name dir5.m (just to have a different name).

>> tic; x = dir ('c:\windows'); toc
Elapsed time is 0.300204 seconds.
>> tic; y = dir5 ('c:\windows'); toc
Elapsed time is 0.0801261 seconds.

This is a 3.75X speedup.

Rik <rik5>
Project Administrator
Sat 18 Mar 2017 03:51:36 PM UTC, comment #8: 

@Rik:

I have used the installer available at http://www.octave.org,
for 4.2.0 and 4.2.1, and use it in Win-7 machine.

I did it a few times, to check that the results are repeatable.

Avinoam Kalma <avinoam>
Project Member
Thu 16 Mar 2017 09:52:19 PM UTC, comment #7: 

My benchmarking was done on Linux using the dev version of Octave.  I measured the results using the version of dir in the dev tree and then made two csets.  The first one gave me a 2.3X speedup and the second a 2X speedup on top of that one for a 4.6X speedup.  However, there was also a request to add the folder field to the output struct to make the function more Matlab compatible.  That added a 15% slowdown.

I just benchmarked on Linux and I don't see a slowdown between 4.2.0 and 4.2.1.

I switched to a Windows XP VM and I also don't see a slowdown.  Are you compiling your own versions of 4.2.0 and 4.2.1 with MXE or using the installer available at www.octave.org?

Also, did you try repeating the benchmark several times to make sure you didn't hit a period where the CPU was swapping memory or something like that?

Rik <rik5>
Project Administrator
Thu 16 Mar 2017 09:40:51 PM UTC, comment #6: 

I have checked the example from comment #0 again, in Win-7, 32 bit versions of Octave:

Octave 4.2.0 – 0.77 sec
Octave 4.2.1 – 1.17 sec
Octave 4.3.0+ - (hg_id 87b6f3606fd4) 0.50 sec

So octave 4.2.1 added 50% time relative to 4.2.0
(why? @Rik wrote somewhere else "Octave seems to have been getting slower over the years")
and the new version of dir reduced the time by factor of 2.3 wrt 4.2.1, as in comment #5.
(relative to 4.2.0 – only factor of 1.5).

A reduced version of dir which only returns the name field (without date, size etc…)
reduced to 0.12 sec.

Avinoam Kalma <avinoam>
Project Member
Mon 06 Mar 2017 07:24:25 PM UTC, comment #5: 

I checked in the a change that speeds things up by 2.3X (http://hg.savannah.gnu.org/hgweb/octave/rev/529c6d0c6684).  That hit the easy issues of fullfile and fileparts.  I checked in another more complicated change that arranges to call datenum just once, rather than in every iteration of the for loop, which gives another ~2X speed up (http://hg.savannah.gnu.org/hgweb/octave/rev/21fc54e4bb7b).  Overall, the function is now about 5X faster.

I think that's probably good enough.  The original reporter's time will go from 728 milliseconds to 145 milliseconds.  That is still well slower than a compiled C++ function, but well within what a human can tolerate.

Rik <rik5>
Project Administrator
Wed 01 Mar 2017 12:12:22 AM UTC, comment #4: 

Attached is the beginnings of a cset for testing.  It tackles the first two slow function calls (fullfile, fileparts) and is 2.3X faster.  The remaining slowdown is the call to datenum which may be harder to replace (given how many quirks and corner cases I see in datenum.m). 

(file #39856)

Rik <rik5>
Project Administrator
Tue 28 Feb 2017 11:50:48 PM UTC, comment #3: 

Unfortunately, fullfile is 10X slower than strcat.

y = repmat ({"Hello World"}, 200, 1);
tic; x = fullfile ("/usr/bin", y); toc
Elapsed time is 0.0909159 seconds.
tic; z = strcat (["/usr/bin" filesep], y); toc
Elapsed time is 0.00851393 seconds.

Rik <rik5>
Project Administrator
Tue 28 Feb 2017 10:41:47 PM UTC, comment #2: 

> Looking in dir.m I see a loop (bad) that uses fullfile.
> Since the directory portion 'fn' is always being pre-pended it would be faster to use strcat here.
> [...]
> This was only a quick test, you might need to actually convert 'fn' to a proper directory using fullfile just once, and then use strcat, but the result is basically sound.


Actually, fullfile can take a cell array of filenames directly.

Carnë Draug <carandraug>
Project Member
Tue 28 Feb 2017 05:34:25 PM UTC, comment #1: 

I think the first thing to do is try to optimize the m-file, and only if necessary convert it to C++.

The way to optimize is to run the profiler.  I tried

profile on
x = dir ('/usr/bin')
profile off
profexport ('profdata')

As expected, the runtime results follow the Pareto principle or 80/20 rule where most of the slowdown is caused by just a small number of function calls.  According to the hierarchical results in profdata

Function        Total (s)        Self (s)        Calls
dir        3.012        0.610        1
display        0.000        0.000        1
profile        0.000        0.000        1

And if I explore the dir function itself

Function        Total (s)        Self (s)        Calls
fullfile        1.005        0.254        2901
fileparts        0.841        0.295        2901
datenum        0.455        0.380        2901
lstat        0.033        0.033        2901
localtime        0.027        0.027        2901
strftime        0.020        0.020        2901
readdir        0.007        0.007        1
stat        0.006        0.006        578
S_ISDIR        0.002        0.002        2902
S_ISLNK        0.002        0.002        2901
binary +        0.002        0.002        5802
binary <        0.001        0.001        2902

The first three functions (1.005 + 0.841 + 0.455 = 2.301) explain 2.3/3.0 = 77% of the delay.

Looking in dir.m I see a loop (bad) that uses fullfile.

      for i = 1:nf
        flst{i} = fullfile (fn, flst{i});
      endfor

Since the directory portion 'fn' is always being pre-pended it would be faster to use strcat here.

  flst = strcat ([fn filesep], flst);

If I do that, the run time decreases from 3.012 to 1.922 seconds or -36% which is definitely the right direction.

This was only a quick test, you might need to actually convert 'fn' to a proper directory using fullfile just once, and then use strcat, but the result is basically sound.

  fn = fullfile (fn, filesep);
  flst = strcat ([fn filesep], flst);

After that, the next thing would be to optimize how fileparts and datenum are used since they are the other two large slowdowns.  Fileparts might be replaced with a call to regexp; datenum might be replaced by the direct calculation of the datenum since you know the exact format and input.  You could look inside datenum.m and see which calculation mode is actually being used and then just perform that one.

Rik <rik5>
Project Administrator
Tue 28 Feb 2017 05:22:11 AM UTC, original submission:  

For example:

base = 'C:\Temp\test';  ## 1740 files
N = 20;
S = 0;
for i=1:N
  tic
  fnames = dir(fullfile(base,'*.png'));
  len = length (fnames);
  S = S + toc;
end

disp (S/N);

Running on Win-7

in Matlab: 0.0045
in Octave: 0.728

Octave is 160 times slower.
Indeed, there is a fixme line in dir.m:

## FIXME: This is quite slow for large directories.
##        Perhaps it should be converted to C++?

Avinoam Kalma <avinoam>
Project Member

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #39856:  dir.cset added by rik5 (1KiB - 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 avinoam (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 project members can vote.

     

     

     

     

    Follow 7 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2017-03-06 rik5 StatusPatch Submitted Fixed
        Open/ClosedOpen Closed
        Release4.2.1 dev
    2017-03-01 rik5 Attached File- Added dir.cset, #39856
        StatusConfirmed Patch Submitted
    2017-02-28 rik5 Priority5 - Normal 3 - Low
        StatusNone Confirmed

    Back to the top


    Powered by Savane 3.9