bugGNU Octave - Bugs: bug #59706, Avoid...

 
 

bug #59706: Avoid "canonicalize_file_name" for improved performance

Submitted by:  None
Submitted on:  Thu 17 Dec 2020 05:09:26 AM UTC  
 
Category:  Interpreter Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Performance
Status:  Fixed Assigned to:  None
Originator Name:  Originator Email:  -email is unavailable-
Open/Closed:  Closed Release:  dev
Operating System:  Any

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)

Mon 18 Jan 2021 03:22:04 PM UTC, comment #49: 

I re-titled the bug report since this turned out to be much bigger than just the Windows OS.

Rik <rik5>
Project Administrator
Mon 18 Jan 2021 01:02:07 PM UTC, comment #48: 

I'm happy (albeit also surprised) it is working for you now with better performance.

Closing as fixed.

We can re-open or start a new report if other performance issues are identified.

Markus Mützel <mmuetzel>
Project Member
Mon 18 Jan 2021 08:47:46 AM UTC, comment #47: 

Thanks, I ran the test case and the performance of the new build is comparable to Octave 5.2.0. It is even slightly (1%) faster.
Thank you very much!

Anonymous
Sun 17 Jan 2021 12:40:32 PM UTC, comment #46: 

I just pushed a change for bug #59711.

Could you please check with a nightly build from tomorrow 2021 Jan 18 or later if that makes a notable difference for the test case here? (I'm not certain if it will...)

Markus Mützel <mmuetzel>
Project Member
Fri 15 Jan 2021 02:47:38 PM UTC, comment #45: 

There are stacks in the profile that look like this:

ZN6octave9load_path12package_info22add_to_private_fcn_mapERKNS0_8dir_infoE        liboctinterp-8        [unknown]        0        0x1157a2b
ZNK6octave9load_path3addERKNS0_8dir_infoEbRKNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEEb        liboctinterp-8        [unknown]        0        0x11586de
ZNK6octave9load_path6updateEv        liboctinterp-8        [unknown]        0        0x115d2ef
ZN6octave8fcn_info12fcn_info_rep4findERKNS_12symbol_scopeERK17octave_value_list        liboctinterp-8        [unknown]        0        0xfdcd38
ZN6octave12symbol_table14fcn_table_findERKNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEERK17octave_value_listRKNS_12symbol_scopeE        liboctinterp-8        [unknown]        0        0x129fd8f
ZN6octave12symbol_table13find_functionERKNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEERK17octave_value_listRKNS_12symbol_scopeE        liboctinterp-8        [unknown]        0        0x129fec0
ZN14octave_builtin7executeERN6octave14tree_evaluatorEiRK17octave_value_list        liboctinterp-8        [unknown]        0        0xdabcfd
ZN15octave_function4callERN6octave14tree_evaluatorEiRK17octave_value_list        liboctinterp-8        [unknown]        0        0xde1f9e
ZN6octave15tree_identifier10evaluate_nERNS_14tree_evaluatorEi        liboctinterp-8        [unknown]        0        0xeaead3
ZN6octave15tree_identifier8evaluateERNS_14tree_evaluatorEi        liboctinterp-8        [unknown]        0        0x1427f95
ZN6octave14tree_evaluator15visit_statementERNS_14tree_statementE        liboctinterp-8        [unknown]        0        0xea9295
ZN6octave14tree_evaluator20visit_statement_listERNS_19tree_statement_listE        liboctinterp-8        [unknown]        0        0xe9b629
ZNK6octave14tree_evaluator12at_top_levelEv        liboctinterp-8        [unknown]        0        0xea14f4
ZN6octave14tree_evaluator4evalERSt10shared_ptrINS_19tree_statement_listEEb        liboctinterp-8        [unknown]        0        0xe9ccad
ZN6octave11interpreter9main_loopEv        liboctinterp-8        [unknown]        0        0x1143b02
ZN6octave11interpreter7executeEv        liboctinterp-8        [unknown]        0        0x1147a69
ZN6octave15cli_application7executeEv        liboctinterp-8        [unknown]        0        0x9f1857
main        octave-cli        [unknown]        0        0x402c19

I'm not sure if this is the case. But I was assuming that this means that that function wasn't inlined and would appear in the other (slow) stacks, too.

Markus Mützel <mmuetzel>
Project Member
Fri 15 Jan 2021 02:06:43 PM UTC, comment #44: 

The call stack is :

sys::canonicalize_file_name
load_path::package_info::add_to_private_fcn_map
load_path::package_info::add
load_path::add (const dir_info& di, bool at_end,const std::string& pname, bool updating) const
load_path::update

looking at the definition of 'add_to_private_fcn_map' in file libinterp/corefcn/load-path.cc line:1968

private_fcn_map[sys::canonicalize_file_name (di.dir_name)]
  = private_file_map;

Anonymous
Fri 15 Jan 2021 10:10:34 AM UTC, comment #43: 

Most stacks in which most of the time is spent as recorded by the Very Sleepy profile you submitted in comment #38 look similar to this one:

ZN6octave3sys22canonicalize_file_nameERKNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEERS6_        liboctave-8        [unknown]        0        0x6d006f93
ZN6octave3sys22canonicalize_file_nameERKNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE        liboctave-8        [unknown]        0        0x6d0078d7
ZNK6octave9load_path3addERKNS0_8dir_infoEbRKNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEEb        liboctinterp-8        [unknown]        0        0x11586de
ZNK6octave9load_path6updateEv        liboctinterp-8        [unknown]        0        0x115d2ef
ZN6octave8fcn_info12fcn_info_rep4findERKNS_12symbol_scopeERK17octave_value_list        liboctinterp-8        [unknown]        0        0xfdcd38
ZN6octave12symbol_table14fcn_table_findERKNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEERK17octave_value_listRKNS_12symbol_scopeE        liboctinterp-8        [unknown]        0        0x129fd8f
ZN6octave12symbol_table13find_functionERKNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEERK17octave_value_listRKNS_12symbol_scopeE        liboctinterp-8        [unknown]        0        0x129fec0
ZN14octave_builtin7executeERN6octave14tree_evaluatorEiRK17octave_value_list        liboctinterp-8        [unknown]        0        0xdabcfd
ZN15octave_function4callERN6octave14tree_evaluatorEiRK17octave_value_list        liboctinterp-8        [unknown]        0        0xde1f9e
ZN6octave15tree_identifier10evaluate_nERNS_14tree_evaluatorEi        liboctinterp-8        [unknown]        0        0xeaead3
ZN6octave15tree_identifier8evaluateERNS_14tree_evaluatorEi        liboctinterp-8        [unknown]        0        0x1427f95
ZN6octave14tree_evaluator15visit_statementERNS_14tree_statementE        liboctinterp-8        [unknown]        0        0xea9295
ZN6octave14tree_evaluator20visit_statement_listERNS_19tree_statement_listE        liboctinterp-8        [unknown]        0        0xe9b629
ZNK6octave14tree_evaluator12at_top_levelEv        liboctinterp-8        [unknown]        0        0xea14f4
ZN6octave14tree_evaluator4evalERSt10shared_ptrINS_19tree_statement_listEEb        liboctinterp-8        [unknown]        0        0xe9ccad
ZN6octave11interpreter9main_loopEv        liboctinterp-8        [unknown]        0        0x1143b02
ZN6octave11interpreter7executeEv        liboctinterp-8        [unknown]        0        0x1147a69
ZN6octave15cli_application7executeEv        liboctinterp-8        [unknown]        0        0x9f1857

This is a different code path than the one discussed in bug #59711.

IIUC, your proposal might work to improve the performance for the use case described in the other bug (but less so this one).
Please, repeat it there. (If the comments are spread over different reports, it might be difficult to retrace in the future what was done [and why] for that specific bug.)

Markus Mützel <mmuetzel>
Project Member
Fri 15 Jan 2021 09:51:44 AM UTC, comment #42: 

According to the result of APi Monitor the only occurrence of canonicalize_file_name is when a path folder contains a 'private' sub-folder.
I assume that all path folders are already canonicalized. They can be canonicalized on Octave startup or when a user use 'cd' or when they use 'addpath'. A private path is just path + sep + "private". Does this private path need to be canonicalized again and agian? NO.
In bug #59711 comment #13 a patch is submitted that eliminates canonicalize_file_name calls related to private folders. If I correctly understand it uses uid instead of canonicalized name in private_fcn_map that possibly increases the performance of Octave 7 relative to Octave 5.2.0.
But a fix for the stable branch is just not using canonicalize_file_name because the path is already canonicalized.
My suggested patch for Octave 6 to preserve the speed of Octave 5.2.0:

-private_fcn_map[sys::canonicalize_file_name (full_dir_name)] = private_file_map;
+private_fcn_map[full_dir_name] = private_file_map;
...
-private_fcn_map.find (sys::canonicalize_file_name (dir));
+private_fcn_map.find (dir);

Please correct me If I'm in a wrong way.

Anonymous
Thu 14 Jan 2021 05:04:05 PM UTC, comment #41: 

From comment #40

> * Check if we really need to call `load_path::add` so often (100s of times if I read the data in the Very Sleepy profile correctly).
>
> * Check if it is possible to use something else than the canonical path as the unique identifier when managing the load-path.


I agree with this ordering for priority.  First, reduce the number of function calls, and if that is still not enough then do the second part and come up with a different identifier.  As mentioned earlier the device_id + inode_id is unique and could be an easy substitute.

The coding work for item #1 doesn't need to be done on Windows.  We could put in a static variable COUNT in load_path::add and see how many times it gets incremented for a given script (one that changes directories or executes a few simple actions).  This number becomes the baseline and then we can try modifications to the code to see whether this number is reduced or not.

Rik <rik5>
Project Administrator
Thu 14 Jan 2021 01:09:57 PM UTC, comment #40: 

Re comment #38: Thank you for that information.

IIUC, most of the time seems to be spent in ZN6octave3sys22canonicalize_file_nameERKNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE. That is most likely `std::string canonicalize_file_name (const std::string& name)`:
https://hg.savannah.gnu.org/hgweb/octave/file/b73ddb964093/liboctave/system/file-ops.cc#l693

The compiler seems to have inlined a lot of functions because the immediate parent in all stacks appears to be ZNK6octave9load_path3addERKNS0_8dir_infoEbRKNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEEb. That is most likely `void load_path::add (const dir_info& di, bool at_end, const std::string& pname, bool updating) const`:
https://hg.savannah.gnu.org/hgweb/octave/file/b73ddb964093/libinterp/corefcn/load-path.cc#l1225

But the function that calls `canonicalize_file_name` is probably `maybe_canonicalize` in the same file:
https://hg.savannah.gnu.org/hgweb/octave/file/b73ddb964093/libinterp/corefcn/load-path.cc#l58

I added that function to resolve bug #56267:
https://hg.savannah.gnu.org/hgweb/octave/rev/51d26dd80828

IIRC, that bug boils down again to the fact that we use the canonical path as a unique identifier. We can't use the (not canonicalized) path directly because different strings might identify the same path in the file system. Much more so on Windows with its long and short file names, different directory separators ('/' and '\'), and case-insensitive file system.

There are two strategies I currently see to improve the performance here:

  • Check if we really need to call `load_path::add` so often (100s of times if I read the data in the Very Sleepy profile correctly).
  • Check if it is possible to use something else than the canonical path as the unique identifier when managing the load-path.
Markus Mützel <mmuetzel>
Project Member
Thu 14 Jan 2021 12:50:52 PM UTC, comment #39: 

Setting API Monitor to capture liboctave and libinterp calls in addition to file system related WIN32 calls I attached three .cc files that shows function calls related to 'find_function', 'canonicalize_file_name' and 'file_stat'.

(file #50719, file #50720, file #50721)

Anonymous
Thu 14 Jan 2021 12:07:20 PM UTC, comment #38: 

I attached three screen captures as .png files that are three call stacks out of 1096 call stacks. I also attached a .sleepy file that is the result of profiling. Please open it in Very Sleepy.

file #50718)

Anonymous
Thu 14 Jan 2021 10:12:19 AM UTC, comment #37: 

I'm still not sure which function in Octave is "responsible" for calling the Win API functions that were identified as slowing down Octave (see comment #32). Tbh, that is mainly because Anonymous is refusing to obtain or show any (complete) call stacks (or I don't understand how the files they've attached could be useful in identifying those functions).

It's ok with me to close this report.

Markus Mützel <mmuetzel>
Project Member
Thu 14 Jan 2021 04:20:20 AM UTC, comment #36: 

This has been marked Ready for Test for a week.  Is it okay to close now?

Rik <rik5>
Project Administrator
Tue 05 Jan 2021 05:47:05 AM UTC, comment #35: 

"I can't tell from comment #32 whether Octave already does this, or only the first time the path is built."

I called 'find_function' twice with two non-cached names. The list of API functions that are called is attached. Line 781 is where the second 'find_function' begins. The same process as noted in comment #32 is repeated for both functions.

"If we want to be fancy, when we detect a directory exists we need to populate the cache with the m-files that it contains."

It may require the path folders to be monitored for any changes in their contents such as addition or deletion of .m, .oct or .mex files or private directories. Windows has such a capability that is discussed under Obtaining Directory Change Notifications [1].

[1] https://docs.microsoft.com/en-us/windows/win32/fileio/obtaining-directory-change-notifications

(file #50655)

Anonymous
Tue 05 Jan 2021 05:04:22 AM UTC, comment #34: 

It seems that call stack files aren't attached. I attached them again.

(file #50653, file #50654)

Anonymous
Mon 04 Jan 2021 06:54:15 PM UTC, comment #33: 

Octave is required to check for private folders as they form part of the namespace that is created by the loadpath.  However, there is probably a way to be more efficient about it.

First, we shouldn't need to check for private directories every time.  The existence, or non-existence, of a private directory should be cached.  I can't tell from comment #32 whether Octave already does this, or only the first time the path is built.

Second, we shouldn't need to form the combination "dirname" + "/private" and call canonicalize_file_name on the result.  Presumably we already have "dirname" in canonical form and so can just add "/private" using string manipulation and call stat() to see if the resulting directory exists.

If we want to be fancy, when we detect a directory exists we need to populate the cache with the m-files that it contains.  Since we are looping over the contents of the directory at that point we could put in a little extra code to see if a "private/" directory already exists.  That would avoid the call to stat() above.

Rik <rik5>
Project Administrator
Mon 04 Jan 2021 06:01:40 PM UTC, comment #32: 

The reason that I didn't use Very Sleepy to get the call stack is that it samples function calls and generates multiple call stacks that aren't precise enough and call stacks for the same function calls are different. So I used API Monitor to capture most important Win32 API calls for just one invocation of 'find_function' .
The most important difference that I can see between 5.2.0 and 6.1.1 is when a path folder contains a private sub-folder. In this case Octave tries to canonicalize that path.

In other words to find a function 'foo' Octave traverses all folders on the path. For each folder the Win32 API functions like the following is called internally:

GetCurrentDirectoryW
FindFirstFileW
GetFullPathNameW

Following that for each folder a private sub folder is assumed and again those API functions are called for those possibly non existent private sub-folders. If such private sub-folders are actually exist 'canonicalize_file_name' is called that is very expensive and depending on the length of a path it invokes near 25 API functions.
If function 'foo' is found it is cached to prevent the cost.
Again for function 'bar' if it has not been cached the above mentioned process is repeated.

I argue that functions such as 'canonicalize_file_name' and even 'make_absolute_filename' should only be called on user provided paths. Other [system provided] paths by default should be full and normalized.

I believe the patch related to bug #59711 is great specially that it removes 'canonicalize_file_name' calls for private folders. Thanks!

Unfortunately I don't set up the build and possibly we should wait for 7.1.0.

I attached the API calls mentioned in comment #30 as separate two text files.

Anonymous
Mon 04 Jan 2021 10:30:34 AM UTC, comment #31: 

I don't know how to interpret the files you attached. They don't look like call stacks at all to me. (Also, please attach simple text files individually instead of as compressed archives.)

I'm not sure. But the point about the sub-folder "private" might mean that the issue identified in bug #59711 might be related.

I just submitted a patch there.
Are you set up to build Octave for Windows? If so, could you try if the change there makes any difference?

Markus Mützel <mmuetzel>
Project Member
Sun 03 Jan 2021 05:30:42 PM UTC, comment #30: 

Note that during some tests I have found that 'find_function' is slow only if a name is searched for the first time. When the function name is found it is cached to speed up the search.

For the call stack I used API Monitor [1]. Only the file system related function are monitored. Results for Octave 5.2.0 and 6.1.1 are in the attached zip file.

Some observations:

  • On Octave 5.1.0 paths are shorten by tilde but on 6.1.1 full names are used.
  • It appears that Octave assumes a private sub-directory for all directories that are parts of the Octave path and tries to find the function in the private sub-directories. Which is an excessive work and possibly is incorrect.
  • When a path directory actually contains a private sub-directory on Octave 6.1.1 we can see near 25 extra function calls that I think is invoked by gnulib.

[1] http://www.rohitab.com/apimonitor

(file #50633)

Anonymous
Sun 03 Jan 2021 11:09:24 AM UTC, comment #29: 

Re comment #28: Could you please show the call stack with the bottle neck after these changes (e.g. using Very Sleepy CS)?

Markus Mützel <mmuetzel>
Project Member
Sun 03 Jan 2021 08:10:25 AM UTC, comment #28: 

I tested the attached example. While on Octave 6.1.0 the performance is 7.5 times worse than Octave 5.2.0, on Octave 6.1.1 (hg id: 0180eaf55fd0) it is two times worse than 5.2.0.

Anonymous
Tue 22 Dec 2020 06:51:36 PM UTC, comment #27: 

I pushed the additional change to stable here: http://hg.savannah.gnu.org/hgweb/octave/rev/0180eaf55fd0.

Rik <rik5>
Project Administrator
Tue 22 Dec 2020 05:48:00 PM UTC, comment #26: 

I think I remember from somewhere that a function local, static variable should always be const for some reason. But I can't remember why...
Given that `pat` is basically const anyway, there is probably little reason to not make it static...

Markus Mützel <mmuetzel>
Project Member
Tue 22 Dec 2020 04:06:39 PM UTC, comment #25: 

One last thought on optimization.  On the development branch the regular expression is now static and const so it is calculated only once.  Even thought we can't make it 'const' on stable, we could declare it static which I believe would mean it is only calculated and initialized once as well.

Here's a diff to show what I mean.

diff -r 45abff4199d8 liboctave/system/file-stat.cc
--- a/liboctave/system/file-stat.cc        Mon Dec 21 19:24:58 2020 +0100
+++ b/liboctave/system/file-stat.cc        Tue Dec 22 07:51:57 2020 -0800
@@ -206,7 +206,7 @@ namespace octave
           // trailing backslash.
           // FIXME: This pattern does not match all possible UNC roots:
           //        https://docs.microsoft.com/en-us/openspecs/windows_protocols/ms-dtyp/62e862f4-2a51-452e-8eeb-dc4ff5ee33cc
-          regexp pat (R"(^\\\\[\w.-]+\\[\w\$-]+$)");
+          static regexp pat (R"(^\\\\[\w.-]+\\[\w\$-]+$)");
           if ((full_file_name.length () == 2 && full_file_name[1] == ':')
               || (full_file_name.length () > 4  && full_file_name[0] == '\\'
                   && full_file_name[1] == '\\' && pat.is_match (full_file_name)))

The current solution is good in that it doesn't call is_match() unless it absolutely has to.  But, it does call the regexp parser every time stat() is called to construct an internal regexp object from the string specifying the pattern, and that can't be quick either.

Rik <rik5>
Project Administrator
Tue 22 Dec 2020 08:53:15 AM UTC, comment #24: 

OoOH. I got Rik's comment #19 the wrong way round. gnulib's `canonicalize_file_name` replacement is definitely calling their `stat` replacement on Windows. So some kind of of `stat` was indeed called at least twice.

Markus Mützel <mmuetzel>
Project Member
Tue 22 Dec 2020 08:48:12 AM UTC, comment #23: 

Oops. I forgot: We don't use gnulib's `stat` replacement on Windows but use the WinAPI directly (because gnulib doesn't consistently handle non-ASCII characters on Windows).
So `canonicalize_file_name` is definitely gone from this code path now...

Markus Mützel <mmuetzel>
Project Member
Tue 22 Dec 2020 08:43:50 AM UTC, comment #22: 

I pushed a change with Rik's suggestions to stable here:
https://hg.savannah.gnu.org/hgweb/octave/rev/45abff4199d8

I don't think gnulib uses its `canonicalize_file_name` replacement for its `stat` replacement on Windows. It would be much more performant if they used Windows API calls instead for their `stat` replacement (at least I hope they do).
If this is the case, the slow `canonicalize_file_name` replacement might be eliminated from this code path completely after the recent changes.

That doesn't mean that there won't be more places where we could replace `canonicalize_file_name` by something more efficient (on Windows!) in our own code. It might be that a new `normalize_file_name` will be a good replacement in some occasions. But that decision must be made on a per case basis.

Markus Mützel <mmuetzel>
Project Member
Mon 21 Dec 2020 09:07:41 PM UTC, comment #21: 

@jwe: The change proposed was to make_absolute_filename() which only deals with the text of the path and not with the actual file system.  It should be okay to find occurrences of "/./" and replace with "/" for example. 

Rik <rik5>
Project Administrator
Mon 21 Dec 2020 08:59:28 PM UTC, comment #20: 

Rik: To get the correct answer, canonicalize_file_name can't just replace /foo/bar/../baz.txt with /foo/baz.txt without checking whether /foo/bar is a symbolic link.

John W. Eaton <jwe>
Project Administrator
Mon 21 Dec 2020 06:31:46 PM UTC, comment #19: 

It will be interesting to see how much this helps.  Given that canonicalize_file_name was probably calling the library function stat() internally to check on the existence of the file name, the octave::stat function inadvertently was calling the stat() library function twice.  I would hope we get at least a 2X speedup, and maybe more if we don't call the regexp parser as frequently either.

Rik <rik5>
Project Administrator
Mon 21 Dec 2020 06:19:16 PM UTC, comment #18: 

@Rik: Thanks for the suggestions.
I'll try those in my next cross-build.

Markus Mützel <mmuetzel>
Project Member
Mon 21 Dec 2020 05:57:21 PM UTC, comment #17: 

I forgot to refresh before I pushed the change. Here the missing parts of the previous change:
https://hg.savannah.gnu.org/hgweb/octave/rev/397d043bb2ff

Markus Mützel <mmuetzel>
Project Member
Mon 21 Dec 2020 05:47:52 PM UTC, comment #16: 

It was necessary to add `const` qualifiers to the used `regexp` member functions to make that object a `static const`.
IIUC, this is a change to the ABI that we cannot do on the stable branch. So, I pushed the following change to the default branch:
https://hg.savannah.gnu.org/hgweb/octave/rev/cf059093ffbc

In case adding the `const` qualifier to member functions doesn't break ABI compatibility, we could graft that change to stable.

IIUC, the patterns in comment #13 are ok as an input for `stat` and `lstat` (that we call through the wrappers).

Markus Mützel <mmuetzel>
Project Member
Mon 21 Dec 2020 05:22:17 PM UTC, comment #15: 

In terms of performance, and possibly clarity, would it be better to use push_back() rather than += operator for strings in this context:

          if ((full_file_name.length () == 2 && full_file_name[1] == ':')
              || pat.is_match (full_file_name))
            full_file_name += '\\';

It is true that the '+' operator has an overload for the prototype operator + (string, char) so maybe there is no performance difference.

Also, performing a regular expression search is always going to be slow, and most of the time it will be unnecessary.  Maybe add a quick test to check whether the first two characters are `\` which is a requirement for a UNC name before looking for the full pattern.  For example

if (full_file_name.length () > 4 && full_file_name[0] == '``' && full_file_name[1] == '``' && pat.is_match (full_file_name))
  full_file_name += '\\';

There is also a FIXME note in the code

          // FIXME: Does this pattern match all possible UNC roots?

I don't think it does capture everything.  For one thing, it appears that the text between backslashes is not optional.  There must be at least one character which means that '*' is not appropriate and '+' should be used.

Also, the servername is allowed to be specified as an IP address which means a form like "10.1.1.1" is allowed.  The '\w' character lass does not include the period '.' character so that should be added.  I am using documentation for the UNC format from https://docs.microsoft.com/en-us/openspecs/windows_protocols/ms-dtyp/62e862f4-2a51-452e-8eeb-dc4ff5ee33cc.

The definition of the UNC format is

 UNC                = "\\" host-name "\" share-name  [ "\" object-name ]
host-name          = "[" IPv6address "]" / IPv4address / reg-name
    ; IPv6address, IPv4address, and reg-name as specified in [RFC3986]
share-name         = 1*80pchar
pchar              = %x20-21 / %x23-29 / %x2D-2E / %x30-39 / %x40-5A / %x5E-7B / %x7D-FF
object-name        = *path-name [ "\" file-name ]
path-name          = 1*255pchar
file-name          = 1*255fchar [ ":" stream-name [ ":" stream-type ] ]
fchar              = %x20-21 / %x23-29 / %x2B-2E / %x30-39 / %x3B / %x3D / %x40-5B / %x5D-7B / %x7D-FF
stream-name        = *schar
schar              = %x01-2E / %x30-39 / %x3B-5B /%x5D-FF
stream-type        = 1*schar

So, a modest improvement to the regexp would be

regexp pat (R"(^\\\\[\w.-]+\\[\w\$-]+$)")

This would catch IP4 addresses, but still not IP6 addresses.  It would also catch common share names such as "admin$".

Rik <rik5>
Project Administrator
Mon 21 Dec 2020 04:42:22 PM UTC, comment #14: 

@Markus: I think of resolving symbolic links as being part of either making the path absolute, or checking whether the file exists.  I believe we are in complete agreement.

Since it is going to be a long while before C++17 is supported by Octave we might look at improving Octave's own functions in this regard.  These are located in liboctave/utils/oct-env.[h|cc].

In particular, it's likely that Octave is just taking a shortcut and scanning for '.' or '..' only at the front of the string.  We could extend the algorithm to search through the entire string and eliminate all such instances.

Rik <rik5>
Project Administrator
Mon 21 Dec 2020 02:47:25 PM UTC, comment #13: 

Just one more thing to point out that "make_absolute" cannot correct this pattern:

 

C:\foo\bar\..\d.txt

but can correct this pattern:

..\d.txt

If this behavior of "make_absolute" isn't sufficient a path normalization function should be used ,as suggested in comment #1 or comment #2 ,instead.

Anonymous
Mon 21 Dec 2020 02:06:53 PM UTC, comment #12: 

No problem. Please commit with your name.

Anonymous
Mon 21 Dec 2020 02:00:35 PM UTC, comment #11: 

Good point.
Would you like to be attributed with that change? We usually have a real life name and a valid email address for the author of a change.
If you prefer to stay anonymous, I could also commit that change under my name...

Markus Mützel <mmuetzel>
Project Member
Mon 21 Dec 2020 01:55:10 PM UTC, comment #10: 

Thanks! I will test it ASAP. I expect it improves the overall performance of Octave specially in .m files that contains multiple function calls.

I attached a minimal patch that I think improves the performance of file-stat::update_internal.

(file #50538)

Anonymous
Mon 21 Dec 2020 10:59:04 AM UTC, comment #9: 

"make_absolute" seems to work just as well in that case (and I hope it will be more performant).

I pushed the change on stable because I hope it is save and might improve overall performance on Windows:
https://hg.savannah.gnu.org/hgweb/octave/rev/e8819aa30715

Marking as ready for test.

@anonymous: A nightly build from tomorrow 2020/Dec/22 or later should include that change. You could download it from Kai's buildbot:
https://buildbot.octave.space/#/download

Does that improve the performance for you?

Markus Mützel <mmuetzel>
Project Member
Mon 21 Dec 2020 09:07:41 AM UTC, comment #8: 

@Rik: I agree with most of your comment.
But `canonicalize_file_name` does more than just normalizing the file name and checking whether it exists. Among other things it also resolves symbolic links.
If the result of `canonicalize_file_name` is used as a key to identify a physical file, that (or some other step this function does) might (or might not) be relevant.
Gnulib's implementation for `canonicalize_file_name` on Windows is slow. We've already seen that in the past. So it might be best to avoid it (on Windows) where possible(!).

I didn't come around to analyzing the call stack of the slow code path here until now.
If I understand the call stack in comment #5 correctly, it is in `file_stat` where `canonicalize_file_name` is called.
I added calling this function with the change here:
https://hg.savannah.gnu.org/hgweb/octave/rev/372f42f122bd

I don't remember now if using that function was strictly necessary or I just didn't know (or didn't remember) that it was slow on Windows back then.

I'll try whether Octave's file_stat will still work on Windows with a change similar to this:

diff -r 403a9f626ba2 liboctave/system/file-stat.cc
--- a/liboctave/system/file-stat.cc        Sun Dec 20 18:48:41 2020 +0100
+++ b/liboctave/system/file-stat.cc        Mon Dec 21 09:40:43 2020 +0100
@@ -194,12 +194,7 @@
           std::string full_file_name = sys::file_ops::tilde_expand (file_name);

#if defined (OCTAVE_USE_WINDOWS_API)
-          std::string canon_file_name
-            = sys::canonicalize_file_name (full_file_name);
-
-          // Might have failed for files with non-ASCII characters in name
-          if (! canon_file_name.empty ())
-            full_file_name = canon_file_name;
+          full_file_name = sys::env::make_absolute (full_file_name);

           // Remove trailing slashes
           while (full_file_name.length () > 1

If this works, that would have the additional benefit that it renders the fallback for non-ASCII strings unnecessary.

Markus Mützel <mmuetzel>
Project Member
Mon 21 Dec 2020 01:27:17 AM UTC, comment #7: 

@Markus: Since there is already a function to normalize a file path, and it is fast, can we re-title and re-position this report to be about performance?

canonicalize_file_name should be fast because it is a library call.  On some platforms, where the implementation is broken, we use gnulib to swap in our own compiled version of the function.  That might be the case with the reporter's computer.  I can't really tell because the Operating System is marked as "Any".

I can see several things to do that might result in a solution.

1) Look at whether canonicalize_file_name is slow on a particular platform, such as Windows, and substitute something faster for that particular OS

2) Substitute our own version which is make_absolute_filename() combined with a try/catch block around and existence test for the object.  Benchmark it and see if this is faster.

If the problem is really just that the function is slow then the way out seems to be to call it fewer times.  That's simple to state, but the devil is in the details.

canonicalize_file_name does two things: 1) it expands a relative or path fragment to a fully qualified path, and 2) checks for the existence of the named object (file or directory).

Unfortunately, it would require looking at each instance where we call the function to see whether we are making use of one or both features.  I do know that a fair number of the instances we are using the function to test for the existence of a file so substituting make_absolute_filename() will not work.

That leaves re-architecting to reduce the number of function calls.  I can think of a few opportunities

A) Octave needs to check whether functions have been modified before calling them.  However, it only needs to do this each time it returns to the prompt.  We should make sure that Octave, while executing a script, isn't trying to check for updates after every line is executed.

B) The load_path is cached and the function location and other ancillary information is also cached.  Is this system somehow not working and a lookup in the symbol table is causing an overly frequent search of the disk rather than just a search in memory of the cache?

C) Perhaps a small thing, but the caching is done with C++ standard maps which are O(log2(N)) in performance.  Now that Octave supports C++11 we could move to a hash-based map from the standard library and get O(1) lookup performance.

Rik <rik5>
Project Administrator
Fri 18 Dec 2020 06:12:40 PM UTC, comment #6: 

Re comment #3. I personally don't use canonicalize_file_name but Octave does!
I agree with the suggestion in comment #1 :

""
it might be possible to replace some uses of `canonicalize_file_name` with that new function
""

Anonymous
Fri 18 Dec 2020 05:49:29 PM UTC, comment #5: 

I attached a zip file that contains a minimal example. It is source of .oct file that loads a .txt file containing some names and calls octave::symbol_table::find_function multiple times. Please compile it separately for Octave 5.2.0 and 6.1.0 and you can see performance slowdown in Octave 6.1.0.
In the zip file There is also a screen capture that shows one of call stacks.

(file #50512)

Anonymous
Fri 18 Dec 2020 08:07:11 AM UTC, comment #4: 

Re comment #2: Could you please show the call stack that Very Sleepy shows to be this much slower in Octave 6?
Calling `canonicalize_file_name` might still be slow (especially on Windows). The other bug #57439 was resolved by not relying on that function for the respective code paths...

Markus Mützel <mmuetzel>
Project Member
Thu 17 Dec 2020 10:33:41 PM UTC, comment #3: 

You might take a look at the Octave function make_absolute_filename().  It produces an absolute path without verifying that the file exists.  It doesn't do tilde expansion, but is about 3X faster in a quick test that I just did.

Rik <rik5>
Project Administrator
Thu 17 Dec 2020 07:08:31 PM UTC, comment #2: 

Thanks for reply!

I have developed a function that calls octave::symbol_table::find_function multiple times. The function in Octave 5.2.0 completes in 2-3 seconds while in Octave 6.1.0 it takes sometimes near 60 seconds. I independently used Very Sleepy profiler that shows that 73% of the running time is related to canonicalize_file_name.
However the slowdown by canonicalize_file_name may be compensated by recent improvements in other places.

Anonymous
Thu 17 Dec 2020 05:11:31 PM UTC, comment #1: 

`canonicalize_file_name` in Octave is designed to do essentially the same as the Linux function of the same name:
https://man7.org/linux/man-pages/man3/canonicalize_file_name.3.html

Among other things, it must resolve symbolic links. For this to work as expected it has to access the file system (which might be slow).

IIUC, you are proposing to add a new function that normalizes a file path (without actually checking the file system layout).

When Octave starts to adopt C++17, this could be realized with `std::filesystem::path::lexically_normal`:
https://en.cppreference.com/w/cpp/filesystem/path/lexically_normal

If that function should be added, it might be possible to replace some uses of `canonicalize_file_name` with that new function.

Fwiw, the slow down discussed in bug #57439 no longer occurs and that report has been closed as fixed.

Markus Mützel <mmuetzel>
Project Member
Thu 17 Dec 2020 05:09:26 AM UTC, original submission:  

As discussed in bug #57439 a notable performance slowdown has been imposed by canonicalize_file_name so I opened a separate thread to draw more attention to this issue.
It appears that canonicalize_file_name results in multiple system calls some of witch are related to the file system.

Here https://stackoverflow.com/questions/28659344/alternative-to-realpath-to-resolve-and-in-a-path are some implementations that do the task regardless of whether the directories/files actually exist.

Anonymous

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #50719:  find_function_API_calls.cc added by None (89KiB - application/octet-stream)
file #50720:  canonicalize_file_name_API_calls.cc added by None (3KiB - application/octet-stream)
file #50721:  file_stat_API_calls.cc added by None (276B - application/octet-stream)
file #50718:  6.1-capture.sleepy added by None (84KiB - application/octet-stream - sleepy profile and 3 call stacks)
file #50715:  callstack1.png added by None (15KiB - image/png - sleepy profile and 3 call stacks)
file #50716:  callstack2.png added by None (14KiB - image/png - sleepy profile and 3 call stacks)
file #50717:  callstack3.png added by None (16KiB - image/png - sleepy profile and 3 call stacks)
file #50655:  callstack-611-find_function_called_twice.cc added by None (130KiB - application/octet-stream - API for find_function called twice)
file #50653:  callstack520.cc added by None (15KiB - application/octet-stream)
file #50654:  callstack611.cc added by None (65KiB - application/octet-stream)
file #50633:  callstacks-520vs611.zip added by None (3KiB - application/x-stuffit - callstacks 5.2.0 vs 6.1.1)
file #50538:  file-stat.patch added by None (598B - application/octet-stream)
file #50512:  bug59706.zip added by None (19KiB - application/x-stuffit)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by jwe (Posted a comment)
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by mmuetzel (Posted a comment)
  •  

    Do you think this task is very important?
    If so, you can add your encouragement to it.
    This task has 0 encouragements so far.

    Only project members can vote.

     

     

     

    Follow 25 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2021-01-18 rik5 Operating SystemMicrosoft Windows => Any
        SummaryAvoid "canonicalize_file_name" on Windows => Avoid "canonicalize_file_name" for improved performance
    2021-01-18 mmuetzel StatusIn Progress => Fixed
        Open/ClosedOpen => Closed
    2021-01-14 mmuetzel StatusReady For Test => In Progress
    2021-01-14 None Attached File- => Added find_function_API_calls.cc, #50719
        Attached File- => Added canonicalize_file_name_API_calls.cc, #50720
        Attached File- => Added file_stat_API_calls.cc, #50721
    2021-01-14 None Attached File- => Added callstack3.png, #50717
        Attached File- => Added 6.1-capture.sleepy, #50718
    2021-01-14 None Attached File- => Added callstack1.png, #50715
        Attached File- => Added callstack2.png, #50716
    2021-01-05 None Attached File- => Added callstack-611-find_function_called_twice.cc, #50655
    2021-01-05 None Attached File- => Added callstack520.cc, #50653
        Attached File- => Added callstack611.cc, #50654
    2021-01-03 None Attached File- => Added callstacks-520vs611.zip, #50633
    2020-12-21 None Attached File- => Added file-stat.patch, #50538
    2020-12-21 mmuetzel StatusIn Progress => Ready For Test
    2020-12-21 mmuetzel Severity1 - Wish => 3 - Normal
        Priority3 - Low => 5 - Normal
        Operating SystemAny => Microsoft Windows
    2020-12-21 mmuetzel Item GroupFeature Request => Performance
        StatusNone => In Progress
        SummaryAdd function that normalizes a file path => Avoid "canonicalize_file_name" on Windows
    2020-12-18 None Attached File- => Added bug59706.zip, #50512

    Back to the top


    Powered by Savane 3.5