Tcl Source Code

Here's a patch to cvs HEAD to speed up a lot of the
filesystem.  Please test (esp Unix), since I've only
tested on Windows.

File Deleted - 74149: 



File Added - 74359: file.bench

Logged In: YES 
user_id=32170

Attached the file.bench finally used, and updated the
summary to reflect the date of this patch (in case there are
future filesystem optimisation efforts).

File Added - 74303: fsOpt5.patch

Logged In: YES 
user_id=32170

Ok, sorry about that. A mess-up with unix-separators in two
edge-cases.  The patch-5 should fix it all.

Logged In: YES 
user_id=80530

$ make test TESTFLAGS="-verbose be"
...
fCmd.test

==== fCmd-6.19 CopyRenameOneFile: errno == EXDEV FAILED
==== Contents of test case:

    cleanup /tmp
    createfile tf1
    file rename tf1 /tmp
    glob tf* /tmp/tf1

---- Test generated error; Return code was: 1
---- Return code should have been one of: 0 2
---- errorInfo: no files matched glob patterns "tf* /tmp/tf1"
    while executing
"glob tf* /tmp/tf1"
    ("uplevel" body line 5)
    invoked from within
"uplevel 1 $script"
---- errorCode: NONE
==== fCmd-6.19 FAILED


==== fCmd-6.21 CopyRenameOneFile: copy/rename:
S_ISDIR(source) FAILED
==== Contents of test case:

    cleanup /tmp
    file mkdir td1
    file rename td1 /tmp
    glob td* /tmp/td*

---- Test generated error; Return code was: 1
---- Return code should have been one of: 0 2
---- errorInfo: no files matched glob patterns "td* /tmp/td*"
    while executing
"glob td* /tmp/td*"
    ("uplevel" body line 5)
    invoked from within
"uplevel 1 $script"
---- errorCode: NONE
==== fCmd-6.21 FAILED

==== fCmd-6.22 CopyRenameOneFile: copy/rename:
!S_ISDIR(source) FAILED
==== Contents of test case:

    cleanup /tmp
    createfile tf1
    file rename tf1 /tmp
    glob tf* /tmp/tf*

---- Test generated error; Return code was: 1
---- Return code should have been one of: 0 2
---- errorInfo: no files matched glob patterns "tf* /tmp/tf*"
    while executing
"glob tf* /tmp/tf*"
    ("uplevel" body line 5)
    invoked from within
"uplevel 1 $script"
---- errorCode: NONE
==== fCmd-6.22 FAILED


==== fCmd-6.29 CopyRenameOneFile: TclpCopyDirectory passed
FAILED
==== Contents of test case:

    cleanup /tmp
    file mkdir td1/td2/td3
    file rename td1 /tmp
    glob td* /tmp/td1/t*

---- Test generated error; Return code was: 1
---- Return code should have been one of: 0 2
---- errorInfo: no files matched glob patterns "td* /tmp/td1/t*"
    while executing
"glob td* /tmp/td1/t*"
    ("uplevel" body line 5)
    invoked from within
"uplevel 1 $script"
---- errorCode: NONE
==== fCmd-6.29 FAILED
fileName.test

==== filename-15.6 unix specific globbing FAILED
==== Contents of test case:

    global env
    set temp $env(HOME)
    set env(HOME) $env(HOME)/globTest/odd\\\[\]*?\{\}name
    set result [list [catch {glob ~} msg] $msg]
    set env(HOME) $temp
    set result

---- Result was:
0 {{/local/src/tcl/solaris/globTest/odd\[]*?{}name/}}
---- Result should have been (exact matching):
0 {{/local/src/tcl/solaris//globTest/odd\[]*?{}name}}
==== filename-15.6 FAILED

Logged In: YES 
user_id=32170

Can you provide the test results, please?

Vince.

Logged In: YES 
user_id=80530

oops!  Patch fsOpt4.patch
creates four new test failures.

fCmd-6.19,21,22 and filename-15.6

File Deleted - 74020:

File Deleted - 74113: 



File Added - 74269: fsOpt4.patch

Logged In: YES 
user_id=32170

One final patch to streamline 'glob' a bit more, and to
provide better documentation after some feedback from Zoran.
 Also ran this through purify to ensure no new memory leaks
are introduced.

Logged In: YES 
user_id=32170

I've run klist and don't see any issue, although I'm only
comparing tcl8.5+patch against 8.4.  It seems to average
about 50% faster (presumably due to some new optimisations
in 8.5 elsewhere).

E:\Programming\Tcl-source\tclbench>C:\Progra~1\Tcl\bin\tclsh85.exe
runbench.tcl
-paths "C:/Progra~1/Tcl/bin C:/ActiveTcl/bin
C:/ActiveTcl8.3/bin" -notk -pattern
 tclsh8?.exe tcl/klist.bench
000 VERSIONS:                     1:8.5a0 2:8.4.5 3:8.3.5
001 KLIST shuffle0 llength 1            9      16      20
002 KLIST shuffle0 llength 10          29      38      60
003 KLIST shuffle0 llength 100        244     315     644
004 KLIST shuffle0 llength 1000      3036    3762    6400
005 KLIST shuffle0 llength 10000    55285   59352   92100
006 KLIST shuffle1-s llength 1          8      10      20
007 KLIST shuffle1-s llength 10        40      59      60
008 KLIST shuffle1-s llength 100      505    1162    1240
009 KLIST shuffle1-s llength 1000   33309   76351   78210
010 KLIST shuffle1a llength 1           9      12      20
011 KLIST shuffle1a llength 10         41      64      80
012 KLIST shuffle1a llength 100       433     603     760
013 KLIST shuffle1a llength 1000     3988    6103    7410
014 KLIST shuffle1a llength 10000   41588   61837   77100
015 KLIST shuffle2 llength 1            9      12      21
016 KLIST shuffle2 llength 10          59      62     100
017 KLIST shuffle2 llength 100        511     637     880
018 KLIST shuffle2 llength 1000      5116    6967    9610
019 KLIST shuffle2 llength 10000    73507   87959  114200
020 KLIST shuffle3 llength 1            8      10      10
021 KLIST shuffle3 llength 10          33      43      60
022 KLIST shuffle3 llength 100        267     421     600
023 KLIST shuffle3 llength 1000      3071    6073    7720
024 KLIST shuffle3 llength 10000    79677  255728  273400
025 KLIST shuffle4 llength 1            8      11      20
026 KLIST shuffle4 llength 10          32      48      60
027 KLIST shuffle4 llength 100        285     431     680
028 KLIST shuffle4 llength 1000      3210    4315    6310
029 KLIST shuffle4 llength 10000    29701   43952   66100
030 KLIST shuffle5-s llength 1          4       5       0
031 KLIST shuffle5-s llength 10        25      35      40
032 KLIST shuffle5-s llength 100      261     483     520
033 KLIST shuffle5-s llength 1000   12037   23682   24540
034 KLIST shuffle5a llength 1           4       7      10
035 KLIST shuffle5a llength 10         27      40      40
036 KLIST shuffle5a llength 100       239     402     440
037 KLIST shuffle5a llength 1000     2813    5746    6210
038 KLIST shuffle5a llength 10000   85125  249802  259400
039 KLIST shuffle6 llength 1            1       2     -=-
040 KLIST shuffle6 llength 10          20      20     -=-
041 KLIST shuffle6 llength 100        152     186     -=-
042 KLIST shuffle6 llength 1000      1512    1925     -=-
043 KLIST shuffle6 llength 10000    16978   19372     -=-
043 BENCHMARKS                    1:8.5a0 2:8.4.5 3:8.3.5

Logged In: YES 
user_id=80530


Vince, could you try running
the klist.bench benchmarks
before and after this patch?

I see substantial slowdowns,
and the only theory I have is
that this patch really hurts
us in memory?  Can you at
least confirm/deny the slowdowns?

Logged In: YES 
user_id=80530


Aha!

Apply this patch to your
file.bench before
contributing it to
tclbench:

--- /home/dgp/file.bench        Tue Jan 20 14:45:52 2004
+++ file2.bench Tue Jan 20 17:45:56 2004
@@ -175,7 +175,11 @@

 # Make a dummy pkgIndex to test speed of pkg require when the
 # auto_path is changed on the fly
-contents [file join $dir pkgIndex.tcl] {lappend ::auto_path
$dir}
+contents [file join $dir pkgIndex.tcl] {
+    if {[lsearch -exact $::auto_path $dir] == -1} {
+       lappend ::auto_path $dir
+    }
+}

 contents $file {lappend ::auto_path [file dirname [info
script]] ;\
   catch {package require bogus-name}; package names; exit}


Tcl 8.3.5 had a bug in
[tclPkgUnknown] that
allowed for an infinite loop
as the same directory got
lappended again and again
to ::auto_path.  This patch
avoids triggering that bug.

Logged In: YES 
user_id=80530


ok, I'm clearly confused on
the benchmarks.  Don't know
why I can't run the final benchmark
in your file.bench in an 8.3 interp,
but I can't; let's
pursue that elsewhere.

Latest patch passes all tests.

Latest patch shows no
significant slowdowns
according to your file.bench.

Latest patch shows no 
significant slowdowns
according to the file.bench
already in tclbench.

Latest patch does produce
some compiler warnings
that should be corrected, but
that can be done post-commit.

I vote commit now.

Logged In: YES 
user_id=80530


just a note about file.bench

the benchmark named
"FILE standard directory 'package require'"
is pretty bogus.  Different tclsh versions
will point to different [info library] directories,
so different runtimes tell you more about
the differing contents of those directories
than anything about Tcl performance.
I wouldn't add that one to tclbench.

In particular on unforunate installations
where [info library] is very full, you might
retire before that benchmark completes.

File Added - 74149: fsopt3.patch

Logged In: YES 
user_id=32170

Cosmetic clean up for remaining issues.  No functional
changes, I think.

File Deleted - 74111: 



File Added - 74113: fsopt2.patch

File Deleted - 74023: 



File Added - 74111: fsopt2.patch

Logged In: YES 
user_id=32170

Sorry.  Fixed that and cleaned lots of things up.  This is
now pretty close to ready to commit.

Logged In: YES 
user_id=80530


Link failure:

tclUnixFile.c(.text+0x1108): undefined reference to
`TclFileDirOrTail'

File Added - 74023: fsopt2.patch

Logged In: YES 
user_id=32170

Here's a quick attempt to extend the optimisation to 'file
extension'.

Logged In: YES 
user_id=80530


New patch passes all tests.

The slowdowns of [file dirname]
and [file tail] are now big
speedups!

020 FILE glob / dirname                            1.00    0.25
031 FILE glob / tail                               1.00    0.36

Next biggest slowdowns (still
in this patch) are:

023 FILE glob / extension                          1.00    1.30
029 FILE glob / rootname                           1.00    1.33

File Deleted - 74009: 



File Added - 74020: fsopt.patch

File Deleted - 73395: 



File Added - 74009: fsopt.patch

Logged In: YES 
user_id=32170

Attached new patch, addressing all the issues below, except
that we need to rename variables to 'pathObj' in all files
except tclPathObj.c (which has now been done).

Logged In: YES 
user_id=32170

I see, your analysis of Tcl_FSConvertToPathType showed a bug
in there.  In the 'special' FsPathptr case, there's no point
in comparing the ->cwdPtr to the cwd, since it has nothing
to do with cwds.  So, that should fix the slowdown.

Will attach patch when sf-cvs starts to work again.

Logged In: YES 
user_id=32170

Ok, a follow-up on all your good comments and questions below:

(1) The documentation of FsPath is indeed behind the times
(since the first filesystem optimisation).  I've updated
that in my sources and will attach a patch as soon as sf's
cvs servers are up.  Comments/advice on how best to name
these multi-use object points would be appreciate.

(2) Indeed objPtr, pathPtr, pathObjPtr, filenamePtr are all
used all over the place and this is annoying and confusing.
 I think pathPtr is the best, so will begin to convert to that.

(3) I've factored the file dir/tail into a common function
in tclPathObj.c which should also allow it to be clever in
what it returns.

(4) For TclFSCwdPointerEquals and *objPtrPtr being set, yes
I believe you are right that this would be a sensible step
to take.  Added this to the next patch.

Thanks also for the detailed analysis of TclFSGetPathType
and friends.  I'll examine that more closely before proceeding.

Logged In: YES 
user_id=80530


TclFSGetPathType() especially
looks like it could use some attention.

It appears that TclGetPathType() is
fairly expensive and TclFSGetPathType()
is an attempt to avoid it.

However, if pathObjPtr is not already a
FSPathObj with cwdPtr NULL or up to date,
then the Tcl_FSConvertToPathType()
call will have to call TclGetPathType() to
attempt to make it so.

The last call to TclGetPathType is mysterious
too.  Don't we know when cwdPtr == NULL
that we have an absolute path?  Or is that
another example of the comments being
out of date?

Anyhow, it appears that in the slow operations,
TclGetPathType is getting called twice.  The
first time from within the patched 
Tcl_FSConvertToPathType() and the
second time when the cwdPtr of
the converted pathObjPtr turns out
to be NULL.

Logged In: YES 
user_id=80530


In the duplicated stanza
of code noted before, there
is a call to Tcl_FSSplitPath()
on the pathObj returned by [glob].

That pathObj was created by
TclNewFSPathObj() and has
the special structure you noted
before.

Tcl_FSSplitPath calls TclFSGetPathType()
which calls Tcl_FSConvertToPathType().
which was modified by this patch.

Prior to the patch, T_FSCTPT sees a
typePtr of &tclFsPathType and quickly
returns TCL_OK.

After the patch, there's a check of
fsPathPtr->cwdPtr and since it
holds the value of the directory
globbed and not the current working directory
of the process, the pathObj is reconstructed
by generating it's string rep, then re-parsing.
Appears that's where the time difference
comes from.

Seems that if either Tcl_FSSplitPath()
or TclFSGetPathType() were updated
to recognize the optimized form and
process it more efficiently without a
string rep re-parsing, this slowdown
might be avoided.

It might be, though, that the re-parsing
just has to happen at some point, so
you just have to pick where.

Logged In: YES 
user_id=80530


Just another optimization
suggestion.  Near the end
of TclFSCwdPointerEquals()
when string comparison
is done to verify that the
two cwdPtr values are 
different objects, but equal
values....

Couldn't you reset the value
of (*objPtrPtr) to be
tsdPtr->cwdPathPtr -- along
with appropriate refCount
housekeeping -- so that
subsequent checks could
use the fast pointer comparison
and avoid the repeated
string comparison?

Logged In: YES 
user_id=80530


I'm a bit confused on the FsPath
structure.  The normPathPtr
is documented to be
"Normalized, absolute path"

However, Tcl_NewFSPatchObj()
seems to be initializing it to the
relative name of a file?  And then
stashing the name of the containing
directory in the cwdPtr field?

Is this just a case of comments
falling behind?

Logged In: YES 
user_id=80530

still looking at this.  Just a note
while I'm thinking about it.

One of the recommendations in
the Tcl Engineering Manual is 
that the same thing gets the same
name throughout all the code.
For example,  it is always

    Tcl_Interp *interp

As I move from function to
tunction in the Tcl_FS code,
my sense is that there's not
as much naming consistency
as I would like.  Make the
code harder to follow than
it needs to be.

Maybe once we're through
bug fixing, an additional pass
for code cleanup ?

Logged In: YES 
user_id=32170

"yes" to your question below.  Note that the "path" object
results of 'glob' can be different to a normal path:

glob -dir $dir *

returns special path objects which know that they are '$dir'
plus a little bit.  It could be there is a slowdown just for
these special paths.  (We should add a separate 'file
dirname' benchmark on an ordinary path).

However: I really don't know what would be slower with this
patch (unless it introduces some subtle weirdness I haven't
thought about).  Here's what this patch does:

Tcl 8.4/8.5: spend lots of time with relative paths checking
if the 'cwd' has changed.  This involved calling the OS'es
getcwd, converting the encoding, normalizing, creating a
path object, comparing with the previous path object, and
then usually throwing it all away because no-one had called
chdir behind our backs to change the cwd anyway.

Tcl 8.5+patch: cache the native cwd and perform an immediate
comparison of the result of getcwd with that native cwd. If
it's the same, return the cached value which then
short-circuits everything else (no normalization, no
encoding conversion, no object being created).

There are a few other small changes beyond the above, which
could be to blame (some code paths have changed in
tclPathName, which helps to simplify everything, I think!).

Thanks for doing all this, and for pointing out the code
duplication -- I'll look into that, probably after we
understand this issue, since fixing this might lead
naturally do removing the duplication anyway...

Logged In: YES 
user_id=80530


No data yet, but I notice that
both slow operations share
a stanza of code in common.

Lines 2659-2674 of tclFileName.c
and lines 1402-1417 of tclCmdAH.c

I'd look at those operations first I think.

BTW duplicate code suggest a factoring
opportunity.

Logged In: YES 
user_id=80530


so looking at the benchmarks,
I should be looking for the
cause of slowdowns in the
[file dirname] and [file tail] 
commands?

Logged In: YES 
user_id=32170

In that case I'd be very interested to see some sort of
profiling (at least at the level of function calls) of those
two slow benchmarks (glob /dirname glob /tail), since it's
very hard to see how they could possibly get worse with this
patch....

Logged In: YES 
user_id=80530


My benchmarks tested HEAD
against HEAD+patch.

File Deleted - 72414: 



File Added - 73395: fsOpt2.patch

Logged In: YES 
user_id=32170

Thanks for fixing the patch!

I'm wondering what version of Tcl you're benchmarking
against?  Is it 8.4.5 or 8.3.4?  Could you perhaps upload
full results to:

http://mini.net/tcl/10582

I must say I'm not really sure what could cause the slowdown
in those two glob functions, and I don't really have the
experience (or access, given compilefarm never works) to do
profiling on Windows.

Logged In: YES 
user_id=80530


testing your benchmarks, it does seem
that most things are a bit faster.  There
appear to be especially big speedups
for:

009 FILE exists! absolute tmpfile (str)            1.00    0.70
010 FILE exists! relative tmpfile (obj)            1.00    0.68
011 FILE exists! relative tmpfile (str)            1.00    0.27
...
013 FILE exists! tmpfile (str)                     1.00    0.75
...
037 FILE recurse / cd                              1.00    0.62
...
039 FILE recurse+stat / cd                         1.00    0.68

On the other hand, I see substantial slowdowns for:

020 FILE glob / dirname                            1.00    1.41
...
031 FILE glob / tail                               1.00    1.56

Hope that helps...

Logged In: YES 
user_id=80530


After that change, `make test`
completes with no (new) failures.

Logged In: YES 
user_id=80530


uh, looks like I misread slightly.

Just need to add some safety NULL-checking
to line 606 of unix/tclUnixFile.c:

if ((clientData != NULL) && ...

After that change, the segfault is corrected.

Logged In: YES 
user_id=80530


The Unix implementation of 
TclpGetNativeCwd() is not happy
receiving a NULL ClientData -- at least
not if the system getwd() or getcwd() calls fail.

Logged In: YES 
user_id=80530

% source ./../tests/all.tcl

Program received signal SIGSEGV, Segmentation fault.
strcmp () at ../sysdeps/alpha/strcmp.S:41
41      ../sysdeps/alpha/strcmp.S: No such file or directory.
Current language:  auto; currently asm
(gdb) bt
#0  strcmp () at ../sysdeps/alpha/strcmp.S:41
#1  0x12010c080 in TclpGetNativeCwd (clientData=0x0)
    at ./../unix/tclUnixFile.c:606
#2  0x1200b5d60 in Tcl_FSGetCwd (interp=0x12025b818)
    at ./../generic/tclIOUtil.c:2360
#3  0x1200d8a84 in Tcl_FSGetNormalizedPath (interp=0x12025b818, 
    pathObjPtr=0x1202e0578) at ./../generic/tclPathObj.c:1356
#4  0x1200b4898 in Tcl_FSEvalFileEx (interp=0x12025b818,
pathPtr=0x1202e0578, 
    encodingName=0x0) at ./../generic/tclIOUtil.c:1556
#5  0x120044ab8 in Tcl_SourceObjCmd (dummy=0x0,
interp=0x12025b818, objc=2, 
    objv=0x12025c800) at ./../generic/tclCmdMZ.c:1128
#6  0x12002a704 in TclEvalObjvInternal (interp=0x12025b818,
objc=2, 
    objv=0x12025c800, command=0x0, length=0, flags=0)
    at ./../generic/tclBasic.c:3143
#7  0x12007baf0 in TclExecuteByteCode (interp=0x12025b818,
codePtr=0x1202e5828)
    at ./../generic/tclExecute.c:1548
#8  0x1200796e4 in TclCompEvalObj (interp=0x12025b818,
objPtr=0x1202a4ef8)
    at ./../generic/tclExecute.c:1005
#9  0x12002bdd8 in Tcl_EvalObjEx (interp=0x12025b818,
objPtr=0x1202a4ef8, 
    flags=131072) at ./../generic/tclBasic.c:3884
#10 0x12012c83c in Tcl_RecordAndEvalObj (interp=0x12025b818, 
    cmdPtr=0x1202a4ef8, flags=131072) at
./../generic/tclHistory.c:142
#11 0x1200bfb90 in Tcl_Main (argc=1, argv=0x11ffff4f8, 
    appInitProc=0x1200109a0 <Tcl_AppInit>) at
./../generic/tclMain.c:478
#12 0x12001097c in main (argc=1, argv=0x11ffff4f8) at
./../unix/tclAppInit.c:90

Logged In: YES 
user_id=80530


first test report:  this patch gives me
an immediate segfault when attempting
a `make test`.  Will look further.

File Added - 72415: file.bench

Logged In: YES 
user_id=32170

Added modified file.bench that I'm using.

File Added - 72414: fsOpt.patch