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

 
 

bug #43327: dir function is too slow

Submitted by:  Petr Belyaev <upcfrost>
Submitted on:  Mon 29 Sep 2014 09:54:13 PM UTC  
 
Category: Octave FunctionSeverity: 3 - Normal
Priority: 5 - NormalItem Group: Performance
Status: Need InfoAssigned to: None
Originator Name: Open/Closed: Open
Release: 3.8.2Operating System: GNU/Linux

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)

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
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 File(s):
   
   
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
  • -unavailable- added by jwe (Posted a comment)
  • -unavailable- added by mtmiller (Posted a comment)
  • -unavailable- added by upcfrost (Submitted the item)
  • -unavailable- added by upcfrost
  •  

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

    Date Changed By Updated Field Previous Value => Replaced By
    Thu 02 Oct 2014 02:39:33 PM UTCupcfrostAttached File-=>Added dir2.patch, #32213
    Thu 02 Oct 2014 04:01:26 AM UTCmtmillerStatusNone=>Need Info
    Mon 29 Sep 2014 09:54:13 PM UTCupcfrostCarbon-Copy-=>Added -unavailable-

    Back to the top


    Powered by Savane 3.1-cleanup1