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

 
 

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

Submitted by:  Avinoam Kalma <avinoam>
Submitted on:  Tue 28 Feb 2017 05:22:11 AM UTC  
 
Category: Octave FunctionSeverity: 3 - Normal
Priority: 3 - LowItem Group: Performance
Status: FixedAssigned to: None
Originator Name: Open/Closed: Closed
Release: devOperating System: Microsoft Windows

Add a New Comment(Rich 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)

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

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 http://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.

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

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

And if I explore the dir function itself

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.

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

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.

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:

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:

Avinoam Kalma <avinoam>
Project Member

 

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

Attach File(s):
   
   
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
  • -unavailable- added by rik5 (Posted a comment)
  • -unavailable- added by avinoam (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 project members can vote.

     

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

     

     

    Follow 7 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Mon 06 Mar 2017 07:24:25 PM UTCrik5StatusPatch Submitted=>Fixed
      Open/ClosedOpen=>Closed
      Release4.2.1=>dev
    Wed 01 Mar 2017 12:12:22 AM UTCrik5Attached File-=>Added dir.cset, #39856
      StatusConfirmed=>Patch Submitted
    Tue 28 Feb 2017 05:34:25 PM UTCrik5Priority5 - Normal=>3 - Low
      StatusNone=>Confirmed

    Back to the top


    Powered by Savane 3.1-cleanup1