bugGNU Octave - Bugs: bug #43327, dir function is too slow

 
 

bug #43327: dir function is too slow

Submitter:  Petr Belyaev <upcfrost>
Submitted:  Mon 29 Sep 2014 09:54:13 PM UTC
 
Category:  Octave Function Severity:  2 - Minor
Priority:  3 - Low Item Group:  Performance
Status:  Wont Fix Assigned to:  None
Originator Name:  Open/Closed:  * Closed
Release:  * dev Operating System:  * GNU/Linux
* Mandatory Fields

Add a New Comment (Rich Markup)
   

Comment Type & Canned Response:
       

 

( Jump to the original submission )

Fri 12 Nov 2021 04:54:41 AM UTC, comment #11: 

been two years without comment or concern. closing as suggested in comment #10. can reopen if someone has ideas to speed things up.

Nicholas Jankowski <nrjank>
Project Member
Thu 08 Aug 2019 02:14:08 AM UTC, comment #10: 

On my machine Octave 5.1.0:

>> system ('ls -al /usr/bin/ | wc -l'); tic; l = dir ('/usr/bin/'); toc
3254
Elapsed time is 0.63308 seconds.

Octave dev (728e4d99febb):

>> system ('ls -al /usr/bin/ | wc -l'); tic; l = dir ('/usr/bin/'); toc
3254
Elapsed time is 0.665946 seconds.

So I agree on your measurement Rik, about 6000 files per second.  And just for curiosity Matlab R2019a:

> system ('ls -al /usr/bin/ | wc -l'); tic; l = dir ('/usr/bin/'); toc
3254
Elapsed time is 0.016233 seconds.

This makes for Matlab roughly 200,000 files per second.

Regarding the original message, there is still no real improvement.  Assuming "100kk = 1e8 = 100,000,000" files, this still means

>> 1e8/6000/3600
ans =  4.6296

four hours of waiting.  Matlab

>> 1e8/2e5/60
ans =  8.3333

needs eight minutes.  I think my definition of "kk" differs from the OP.

Bottom line, the performance is good enough for the average user today and I suggest to close as won't fix.

Kai Torben Ohlhus <siko1056>
Project Member
Wed 07 Aug 2019 08:17:51 PM UTC, comment #9: 

This bug is very old, but there have been developments since 2014.  In particular, see bug #50416 from 2017 where there was another report about slow processing times for dir.  I recoded dir.m at that time to be ~4X faster.  I checked in another changeset today that improves performance by 10% (https://hg.savannah.gnu.org/hgweb/octave/rev/2c4759c8239c).

At this point, I don't believe there is much more that can be done at the m-file level.  Using the profiler, 2/3rds of the running time is associated with dir.m itself, which really means the for loop within dir.m.

Profiler results for all functions > 1% of run time.

Function  Time (s)  Time (%)  Calls
dir       0.329     66.64     1
regexprep 0.049     9.99      5575
lstat     0.023     4.60      2787
localtime 0.021     4.33      2787
readdir   0.016     3.21      1
stat      0.012     2.51      600
strftime  0.012     2.47      2787
horzcat   0.011     2.21      2787

On my machine, testing with

tic; l = dir ('/usr/bin/'); toc

shows that Octave requires 167 milliseconds per 1,000 entries.  Or put another way, about 6,000 filenames per second.  I believe that would generally be sufficient for most purposes.

If more performance is required then either a JIT accelerator for loops in m-files will be required, or the function will need to be converted to C++.

I tried the attached dir2 patch, but it no longer applies cleanly to the development branch.

Rik <rik5>
Project Administrator
Thu 02 Oct 2014 09:44:50 PM UTC, comment #8: 

It's a judgment call.  We could make all scripting language functions faster by converting them to built-in functions, but I think that would make Octave overall harder to maintain.

John W. Eaton <jwe>
Project Administrator
Thu 02 Oct 2014 09:37:49 PM UTC, comment #7: 

Is making some quite basic function built-in a bad thing? Like, what's the big difference in terms of being basic/complex between dir (script), stat and readdir (both built-in)? I just wonder - for example, sec(x) and cot(x) are both scripts, but the tan(x) and cos(x) are built-ins. Is it better to optimize only the already existing built-ins and to add all other functions using scripts?

Petr Belyaev <upcfrost>
Thu 02 Oct 2014 09:05:35 PM UTC, comment #6: 

I suspect that the loop and all the "scalar" functions are the problem.  Sorry for oversimplifying the problem by only mentioning the call to stat in my earlier comment.

Instead of just stat, we'd need to be able to vectorize all the operations that appear in the loop so that we can eliminate the interpreted loop and the N calls to functions that perform operations on single values.  Then we'd have a series of calls to vectorized functions.  It would probably still not speed things up as much as simply providing a built-in version of dir, but it might come reasonably close.  Plus it might be useful for those other functions to operate on arrays anyway.

John W. Eaton <jwe>
Project Administrator
Thu 02 Oct 2014 07:06:26 PM UTC, comment #5: 

I don't know that vectorizing stat/lstat would help much. The profiler tells me that dir.m itself accounts for about 18% of the runtime on a large directory, with other big contributors being datenum, strchr, strjoin, fileparts, fullfile, and repmat. I completely stubbed out the calls to lstat inside the file loop and there was no improvement at all. So unless you mean replacing the entire file loop with a single call that populates the entire info struct array formatted correctly, I don't see how pulling out stat/lstat alone would help much.

Mike Miller <mtmiller>
Project Administrator
Thu 02 Oct 2014 05:34:12 PM UTC, comment #4: 

Instead of rewriting dir as a built-in function, could we also fix the speed issue by simply vectorizing the stat function and having dir take advantage of that?  I.e., allow stat to take a cell array of file names and return a struct array of results.

John W. Eaton <jwe>
Project Administrator
Thu 02 Oct 2014 02:39:33 PM UTC, comment #3: 

I've fixed the help info text and added the statinfo member, so now it should look 1-to-1 like the original dir. Well, it became a bit slower because of stat, but it's still like 100 times faster compared to dir.

About attaching the file - i've tried doing it, and i'll try to do it again from the different browser, but it just fails to attach, i don't know why. But even if it fails to become attached again, i've updated the external one on pastebin.

About tests - sorry, but i didn't found any test for the original dir. There're some tests for readdir and mkdir/rmdir, but there's nothing about the dir in either 'test/' dir or the 'dir.m' file

Also, please, if there's a better way to use stat/Fstat/mk_stat_map/anything for statinfo inside the function - let me know. I didn't want to copy the whole mk_stat_map (which is static inside syscalls.cc), so it went in a quite ugly way, maybe

(file #32213)

Petr Belyaev <upcfrost>
Tue 30 Sep 2014 10:00:22 PM UTC, comment #2: 

Thanks for your bug report and possible contribution. I haven't looked at your patch yet, but can you please attach it to this bug report rather than as an external link? Did you have a reason for not implementing the statinfo member? Have you tried running any existing tests for dir against your version to make sure all cases are handled the same way?

Mike Miller <mtmiller>
Project Administrator
Mon 29 Sep 2014 10:08:34 PM UTC, comment #1: 

Link to the dir2.patch text

http://pastebin.com/vdxGeQEw

Petr Belyaev <upcfrost>
Mon 29 Sep 2014 09:54:13 PM UTC, original submission:  

Octave's 'dir' function is too slow. As it was suggested in the script's comment line (at scripts/miscellaneous/dir.m), i've tried to re-write it into the built-in function.

The output is similar to matlab's dir, so i didn't include the .statinfo element. In other ways i hope it's (almost) the same as the old one. I've named it dir2 to prevent any confusion.

The patch providing dir2 function is attached.

P.S. About being too damn slow

octave:1> tic; a=dir('/usr/lib'); toc
Elapsed time is 126.671 seconds.
octave:2> tic; a=dir2('/usr/lib'); toc
Elapsed time is 0.37321 seconds.

And the reason i began to rewrite it is because i've got a 100kk files dir (data from the university's machine learning course), and it was trying to go through it for almost half an hour. Well, 100kk files is definitely not a normal thing, but it was just a given in my task

P.P.S Any suggestions, criticisms, opinions are welcome - i'm not that good in coding, but i want to improve my skills.

Petr Belyaev <upcfrost>

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #32213:  dir2.patch added by upcfrost (6KiB - text/x-patch - Updated patch with full info and statinfo member)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by nrjank (Posted a comment)
  • -email is unavailable- added by siko1056 (Posted a comment)
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by jwe (Posted a comment)
  • -email is unavailable- added by upcfrost (Submitted the item)
  • -email is unavailable- added by upcfrost
  •  

    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 10 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2021-11-12 nrjank StatusPostponed Wont Fix
        Open/ClosedOpen Closed
    2019-08-07 mtmiller Carbon-CopyRemoved 80942 -
    2018-05-01 mtmiller Severity3 - Normal 2 - Minor
        Priority5 - Normal 3 - Low
        StatusNeed Info Postponed
        Release3.8.2 dev
    2014-10-02 upcfrost Attached File- Added dir2.patch, #32213
    2014-10-02 mtmiller StatusNone Need Info
    2014-09-29 upcfrost Carbon-Copy- Added -email is unavailable-

    Back to the top


    Powered by Savane 3.9