tcl-core — Tcl Core Team discussions about Tcl development

Re: [TCLCORE] Upgrade of Tcl's String Hash Algorithm

[Alexandre F. <ale...@gm...>]

Attaching inline since the mailing list apparently torn the attachment off.
Thanks Clif for telling me !

-Alex


On 2/11/10, Alexandre Ferrieux <ale...@gm...> wrote:
> Since it appears that timings are tricky, and that worst-case
>  (including malevolent) performance is at least as interesting as the
>  average, here is a small pure-Tcl function that computes the buckets'
>  contents for a given array. It yields a list of {size bucket} pairs,
>  where size==[llength bucket], sorted by decreasing size. You can
>  verify its honesty by comparing the sizes with what [array statistics]
>  says.
>
>  Hope this tool will let somebody discover the
>  killing-HTTP-header-attack we are all dying to see.
>
>  -Alex
>
>


proc nbuck va {
    upvar $va a
    regexp {, ([0-9]+) buckets} [array statistics a] -> n
    return $n
}

proc next {e l} {
    set pos [lsearch $l $e]
    if {$pos<0} {error "not found: $e in [list $l]"}
    incr pos
    return [lindex $l $pos]
}

proc bucketeer var {
    upvar $var ar
    array set x [array get ar]
    array unset x *
    set nb [nbuck x]
    foreach {k v} [array get ar] {
	set x($k) $v
	set n [nbuck x]
	if {$n==$nb} {
	    set k2 [next $k [array names x]]
	    lappend buck($k2) $k
	    set buck($k) $buck($k2)
	    unset buck($k2)
	} else {
	    set buck($k) [list $k]
	    set nb $n
	}
    }
    set out {}
    foreach {k b} [array get buck] {
	lappend out [list [llength $b] $b]
    }
    return [lsort -integer -decreasing -index 0 $out]
}

Re: [TCLCORE] inconsistant #include in tcl-8.5.8

[Donald G P. <dg...@ni...>]

Karl Koehler wrote:
> I have a question regarding a possible inconsistency between tcl.h and
> libtommath/tommath.h on 64-bit unix systems:
> tommath.h defines mp_digit as "unsigned long" ( line 76 ), whereas tcl.h
> defines it as "int" ( line 2200 ).

tcl.h also sets:

#define MP_DIGIT_DECLARED

so that the definition it sets will be the one that controls and
the tommath.h distributed with Tcl will not override or conflict with
it.

Code using mp_ints with Tcl need to agree on 32-bit size for mp_digit,
with MP_28BIT active indicating 28 bits of numeric value per mp_digit.

As noted in the release notes for Tcl 8.5.8, this means a potential
binary incompat for extensions on 64-bit systems.  See
http://wiki.tcl.tk/24693 for more details.


-- 
| Don Porter          Mathematical and Computational Sciences Division |
| don...@ni...             Information Technology Laboratory |
| http://math.nist.gov/~DPorter/                                  NIST |
|______________________________________________________________________|

Re: [TCLCORE] inconsistant #include in tcl-8.5.8

[Kevin K. <kev...@gm...>]

Karl Koehler wrote:
> Hi,
> 
> I'd like to propose the following patch to generic/tclStrToD.c :
> 
> --- generic/tclStrToD.c.old     2010-02-11 17:53:35.000000000 -0800
> +++ generic/tclStrToD.c 2010-02-11 17:53:43.000000000 -0800
> @@ -26,7 +26,7 @@
>  #include <limits.h>
>  #include <math.h>
>  #include <ctype.h>
> -#include <tommath.h>
> +#include "tommath.h"
>  
>  /*
>   * Define KILL_OCTAL to suppress interpretation of numbers with leading
> zero

OK, makes sense.

> I have a question regarding a possible inconsistency between tcl.h and
> libtommath/tommath.h on 64-bit unix systems:
> tommath.h defines mp_digit as "unsigned long" ( line 76 ), whereas tcl.h
> defines it as "int" ( line 2200 ).

Right, that's a bug. The HEAD has it fixed.

> How do we get away with this if MP_64BIT gets defined because of
> libtommath/tommath.h:51 and 60 bits are actually used ?

We don't, but in the Tcl configuration, we should be MP_28BIT always.
MP_64BIT doesn't really work all that well; gcc's support for the 128
bit intermediate results is still pretty buggy. And with either 64BIT or
31BIT, you don't get the Comba multiplier, which is a big win for speed.

We also are still missing pieces for extension building with
tommath. Tcl doesn't build the whole thing, largely for export
control reasons. What I'd like to do is to have an extension library
(with its own Stubs table) that builds the rest, and installs some of
the additional functions (modular exponentiation, Jacobi symbol,
primality testing, totient, ...) into ::tcl::mathfunc as well as
having them at the C level.  So many projects, so little time.

Since I'm got going to get to your #include fix today, could I
trouble you to put the patch on SourceForge?

-- 

[TCLCORE] inconsistant #include in tcl-8.5.8

[Karl K. <ka...@ac...>]

Hi,

I'd like to propose the following patch to generic/tclStrToD.c :

--- generic/tclStrToD.c.old     2010-02-11 17:53:35.000000000 -0800
+++ generic/tclStrToD.c 2010-02-11 17:53:43.000000000 -0800
@@ -26,7 +26,7 @@
 #include <limits.h>
 #include <math.h>
 #include <ctype.h>
-#include <tommath.h>
+#include "tommath.h"
 
 /*
  * Define KILL_OCTAL to suppress interpretation of numbers with leading
zero


Reason: if you define an include-path, including <tommath.h> can pick up
the wrong one, e.g. from ../libtommath .
        "tommath.h" makes sure the one in the current directory is
picked up always, and ensures consistency with other usage.


I have a question regarding a possible inconsistency between tcl.h and
libtommath/tommath.h on 64-bit unix systems:
tommath.h defines mp_digit as "unsigned long" ( line 76 ), whereas tcl.h
defines it as "int" ( line 2200 ).

How do we get away with this if MP_64BIT gets defined because of
libtommath/tommath.h:51 and 60 bits are actually used ?

Thanks,

 - Karl

[TCLCORE] TCL/TK Developer and Math Guru/Java or .Net or C++ positions in Washington, DC

[Kelly C. <kel...@ta...>]

 

Hello, Eric-

 

I found your contact information on-line and was hoping you or someone you
know may be interest in a TCL/TK Developer position in Washington, DC.
Target Labs, Inc. is currently searching, on behalf of its client, for a
Junior and Senior Software Engineer for  positions in Arlington, VA. 

 

With over 20 Target Lab, Inc. employees on-site, our client has met with
great success!

 

Client: To be discussed
Location: Arlington, VA
Position: Software Engineer II & III
Duration: 6 months to start.  Assume 6 month contact to hire
____________________________________________________

Position requirements:
Ability to think in the abstract when designing programming  solutions

Strong technical foundation with the ability to follow-through and
investigate what needs to be done when given general guidelines.

Strong ability troubleshoot problems independently



Familiarity with writing code that relies on an Oracle DB foundation.  

 

Familiarity with Oracle and SQL is very important.

Strong communication skills - both oral and written.  I.e., able to write
and maintain technical documentation to describe what a program does

Ability to aggregate information from different sources and make sense out
if it without much guidance

Technical skills required:
Unix (esp. Sun Solaris) required; 
Web-based GUI development experience using XML, CSS, DOM/SAX, AJAX

Advanced Tcl/Tk, 

Shell Scripting 

Intermediate JavaScript

Advanced skills in ONE of the following:  Intermediate C/C++ or Perl.  

Familiarity with SGML or XML 

Familiarity with Oracle and SQL

 

Functional Skills Required:

Ability to work within a team environment 

Excellent problem identification, analysis and solving skills 

Strong communication skills

 

Desired Skills:

Linux or Windows 

XSLT desired

Oracle Experience using SQL required; XML DB's desired.



If you are interested in discussing these positions, please reply to this
message with a telephone number and convenient time when you can be reached
for a brief conversation.  Please attach a copy of your resume, in Word, to
your reply.  

If you are not interested in these positions, please consider friends and
colleagues who may benefit from receiving this announcement.

Thank you for considering Target Labs, Inc.  I look forward to working with
you soon.

Regards,

 

 

-- 
Kelly Collier

Senior Technical Recruiter
Target Labs, Inc. 
Direct: 202.422.8766 | Fax 703.891.9141
www.targetlabs.net
The Green IT Services Firm,

100% Wind Powered, Carbon Free IT Professionals

 

Please send me an invitation to link on LinkedIn:
<http://www.linkedin.com/in/kellybcollier>
http://www.linkedin.com/in/kellybcollier

 

 

Re: [TCLCORE] Upgrade of Tcl's String Hash Algorithm

[Alexandre F. <ale...@gm...>]

Since it appears that timings are tricky, and that worst-case
(including malevolent) performance is at least as interesting as the
average, here is a small pure-Tcl function that computes the buckets'
contents for a given array. It yields a list of {size bucket} pairs,
where size==[llength bucket], sorted by decreasing size. You can
verify its honesty by comparing the sizes with what [array statistics]
says.

Hope this tool will let somebody discover the
killing-HTTP-header-attack we are all dying to see.

-Alex

Re: [TCLCORE] TIP #361: Releasing Channel Buffers

[Alexandre F. <ale...@gm...>]

On 2/10/10, Joe English <jen...@fl...> wrote:
>
>  Alexandre Ferrieux wrote:
>  >
>  > Bottom line: I think your [chan clear] proposal, whatever the return
>  > value, covers all cases, as does the [fconfigure] approach. So now I'm
>  > listening to opinions about this "imperative vs fconfigure" question.
>  > I'm ready to implement either.
>
>
>
> I'm not entirely sure what "the [fconfigure] approach"
>  you mention is (did I miss an email somewhere?), but I
>  will probably express a strong preference for [chan clear].
>
>  Rationale: [chan clear] means "discard any unwritten data,
>  right now", which is specific and predictable.
>
>  If the proposed (?) [fconfigure $chan -<mumble> true] means
>  "this channel (is allowed to / is instructed to) discard pending data
>  at some (specific? arbitrary?) point in the future", that's
>  much less predictable; I don't want those semantics.
>
>  OTOH if it's intended to mean "discard any unwritten data, right now" --
>  well, that's a verb, not an adjective, and should be spelled
>  as one.

The semantics I had in mind was "this channel will discard its output
buffer on close". That's fully predictable, just less powerful since
it doesn't solve the short read case.

-Alex

Re: [TCLCORE] TIP #361: Releasing Channel Buffers

[<tc...@us...>]

On Wed, Feb 10, 2010 at 11:32:29PM +0100, Alexandre Ferrieux wrote:
> On 2/10/10, Alexandre Ferrieux <ale...@gm...> wrote:
> >
> > Bottom line: I think your [chan clear] proposal, whatever the return
> >  value, covers all cases, as does the [fconfigure] approach. So now I'm
> >  listening to opinions about this "imperative vs fconfigure" question.
> >  I'm ready to implement either.
> 
> Clarification: of course the [fconfigure] still doesn't allow for
> discarding in mid-life, so the question is more precisely, which one
> is preferred among:
> 
>   (a) Simplicity of [exit] with an [fconfigure -fastclose 1] at the
> beginning, no way to express short writes.
> 
>   (b) Expressivity of short writes with [puts;chan clear] at the cost
> of a slightly more complex loop over existing channels for a timely
> exit.
> 
> -Alex

I prefer (b) since it allows you to work with channels that may come
back to life without necessitating a close-open sequence. Yes, it is a
little more complex but that tends to be the case with additional
flexibility.

Ex.
- the other side stops reading for an extended period of time
- you clear the channel buffer and setup a writable handler
- when your handler is called you can reset the other devices state with a
  'sync' character(s) and continue with the conversation
- yes, it's not common but I have some serial devices that end
  pausing/freezing occasionally then spewing and/or consuming garbage
  but we can "reset" the conversation with a sync char

LOL, that's right I get to work with lots O buggy devices/software..
yay!

The simpler case is it stops reading, I clear the channel buffer and
send a sync char without needing to wait for my writable handler to be
called.

But I'll bet someone could persuade me choose (a) with good
justification.

Wayne

Re: [TCLCORE] TIP #361: Releasing Channel Buffers

[Joe E. <jen...@fl...>]

Alexandre Ferrieux wrote:
>
> Bottom line: I think your [chan clear] proposal, whatever the return
> value, covers all cases, as does the [fconfigure] approach. So now I'm
> listening to opinions about this "imperative vs fconfigure" question.
> I'm ready to implement either.


I'm not entirely sure what "the [fconfigure] approach"
you mention is (did I miss an email somewhere?), but I
will probably express a strong preference for [chan clear].

Rationale: [chan clear] means "discard any unwritten data,
right now", which is specific and predictable.

If the proposed (?) [fconfigure $chan -<mumble> true] means
"this channel (is allowed to / is instructed to) discard pending data
at some (specific? arbitrary?) point in the future", that's
much less predictable; I don't want those semantics.

OTOH if it's intended to mean "discard any unwritten data, right now" --
well, that's a verb, not an adjective, and should be spelled
as one.


--Joe English

  jen...@fl...

Re: [TCLCORE] TIP #361: Releasing Channel Buffers

[Alexandre F. <ale...@gm...>]

On 2/10/10, Alexandre Ferrieux <ale...@gm...> wrote:
>
> Bottom line: I think your [chan clear] proposal, whatever the return
>  value, covers all cases, as does the [fconfigure] approach. So now I'm
>  listening to opinions about this "imperative vs fconfigure" question.
>  I'm ready to implement either.

Clarification: of course the [fconfigure] still doesn't allow for
discarding in mid-life, so the question is more precisely, which one
is preferred among:

  (a) Simplicity of [exit] with an [fconfigure -fastclose 1] at the
beginning, no way to express short writes.

  (b) Expressivity of short writes with [puts;chan clear] at the cost
of a slightly more complex loop over existing channels for a timely
exit.

-Alex

Re: [TCLCORE] TIP #361: Releasing Channel Buffers

[Alexandre F. <ale...@gm...>]

On 2/10/10, tc...@us... <tc...@us...> wrote:
>
> So according to your interface above is the following true?
>
>  fconfigure $ch -blocking 0
>  puts -nonewline $ch "some big huge data string....."
>  set pending [chan pending output $ch]
>
> set discarded [chan clear $ch]

I assume a line is missing here, and you're asking whether
$pending==$discarded ?

As a matter of fact, yes. I admit I overlooked [chan pending], so
forget about my proposal of returning the same value. Thanks for the
simplification :}

> Assuming that would only be true in the case that the background writing
>  by the interpreter was unable to flush any bytes between the 2 [set]
>  calls.

There's no separate thread doing "background" writing, it's merely an
internal [fileevent writable]. So as long as we're not calling
[update] nor [vwait] between the two lines, we're safe.

> Additionally to be able to emulate what one can achieve with C, only if
>  one to if needed for some reason, this would not work as easily since
>  the semantics of how [puts] works would need be changed. You would need
>  to be able to instruct [puts] not to queue bytes that is cannot
>  immediately flush. Otherwise I'd assume you end up with a race condition
>  trying to determine how much data is pending and how much you need to
>  [puts]? IE, trying to determine your next offset in your output buffer.
>  Unless I'm missing something... which could very well be the case:)

Nope, see above, no race condition, all this is within the interp's
single thread.

>  But this is outside the scope of this TIP since the ability to clear and
>  close the channel could be achieved with this interface.

Bottom line: I think your [chan clear] proposal, whatever the return
value, covers all cases, as does the [fconfigure] approach. So now I'm
listening to opinions about this "imperative vs fconfigure" question.
I'm ready to implement either.

-Alex

Re: [TCLCORE] TIP #361: Releasing Channel Buffers

[<tc...@us...>]

On Wed, Feb 10, 2010 at 09:02:40AM +0100, Alexandre Ferrieux wrote:
> On 2/4/10, Wayne Cuddy <wc...@us...> wrote:
> >
> >   TIP #361: RELEASING CHANNEL BUFFERS
> >  =====================================
> 
> Now that the related bug 2946474 is under control, maybe we can
> proceed with the main TIP's subject.
> 
> So the only thing yet to be settled is the API style.
> Wayne suggests:
> 
> >
> >      * *chan clear* /channelId/
> >      * *close -noflush* /channelId/
> >
> 
> Initially I thought that an fconfigure option would be better, because
> we could set it in advance for many channels, simplifying the exit
> stage (esp. useful after an error).
> 
> However, I have since realized that another use case could benefit
> from the imperative API above: "true short writes".
> 
> Indeed, Tcl's nonblocking write is a high-level tool that lets the
> programmer "fire and forget" about what he's just written. In
> contrast, C-level nonblocking writes just report the number of bytes
> actually written, letting the caller resubmit the unwritten part later
> if he sees fit. Currently, Tcl always "sees fit", and does so in
> background with a hidden [fileevent writable].
> 
> This implies that it is currently impossible at script level to
> emulate the lower-level short write semantics. I do know of cases
> where it matters: I've been forced to do that in C :/
> 
> Now, the second of Wayne's proposals, slightly extended, does the job:
> 
>    set discarded [chan clear $ch]

So according to your interface above is the following true?

fconfigure $ch -blocking 0
puts -nonewline $ch "some big huge data string....."
set pending [chan pending output $ch]
set discarded [chan clear $ch]

Assuming that would only be true in the case that the background writing
by the interpreter was unable to flush any bytes between the 2 [set]
calls.

> 
> Indeed, knowing the number of discarded bytes is equivalent to getting
> back the number of bytes actually written from [puts] (which is not
> puts' job today).

Additionally to be able to emulate what one can achieve with C, only if
one to if needed for some reason, this would not work as easily since
the semantics of how [puts] works would need be changed. You would need
to be able to instruct [puts] not to queue bytes that is cannot
immediately flush. Otherwise I'd assume you end up with a race condition
trying to determine how much data is pending and how much you need to
[puts]? IE, trying to determine your next offset in your output buffer.
Unless I'm missing something... which could very well be the case:)

But this is outside the scope of this TIP since the ability to clear and
close the channel could be achieved with this interface.

Wayne

Re: [TCLCORE] TIP #361: Releasing Channel Buffers

[Alexandre F. <ale...@gm...>]

On 2/10/10, Lars Hellström <Lar...@re...> wrote:
> Alexandre Ferrieux skrev:
>
> > Indeed, Tcl's nonblocking write is a high-level tool that lets the
> > programmer "fire and forget" about what he's just written. In
> > contrast, C-level nonblocking writes just report the number of bytes
> > actually written, letting the caller resubmit the unwritten part later
> > if he sees fit. Currently, Tcl always "sees fit", and does so in
> > background with a hidden [fileevent writable].
> >
> > This implies that it is currently impossible at script level to
> > emulate the lower-level short write semantics. I do know of cases
> > where it matters: I've been forced to do that in C :/
> >
> > Now, the second of Wayne's proposals, slightly extended, does the job:
> >
> >   set discarded [chan clear $ch]
> >
>
>  Would that make $discarded the number of bytes that were discarded, or the
> actual material (bytearray) that was discarded?

Ah sorry, the number of bytes, both cheaper, safer, and sufficient for
the purpose.

-Alex

Re: [TCLCORE] TIP #361: Releasing Channel Buffers

[Lars H. <Lar...@re...>]

Alexandre Ferrieux skrev:
> Indeed, Tcl's nonblocking write is a high-level tool that lets the
> programmer "fire and forget" about what he's just written. In
> contrast, C-level nonblocking writes just report the number of bytes
> actually written, letting the caller resubmit the unwritten part later
> if he sees fit. Currently, Tcl always "sees fit", and does so in
> background with a hidden [fileevent writable].
> 
> This implies that it is currently impossible at script level to
> emulate the lower-level short write semantics. I do know of cases
> where it matters: I've been forced to do that in C :/
> 
> Now, the second of Wayne's proposals, slightly extended, does the job:
> 
>    set discarded [chan clear $ch]

Would that make $discarded the number of bytes that were discarded, or 
the actual material (bytearray) that was discarded?

Lars Hellström

Re: [TCLCORE] TIP #361: Releasing Channel Buffers

[Alexandre F. <ale...@gm...>]

On 2/4/10, Wayne Cuddy <wc...@us...> wrote:
>
>   TIP #361: RELEASING CHANNEL BUFFERS
>  =====================================

Now that the related bug 2946474 is under control, maybe we can
proceed with the main TIP's subject.

So the only thing yet to be settled is the API style.
Wayne suggests:

>
>      * *chan clear* /channelId/
>      * *close -noflush* /channelId/
>

Initially I thought that an fconfigure option would be better, because
we could set it in advance for many channels, simplifying the exit
stage (esp. useful after an error).

However, I have since realized that another use case could benefit
from the imperative API above: "true short writes".

Indeed, Tcl's nonblocking write is a high-level tool that lets the
programmer "fire and forget" about what he's just written. In
contrast, C-level nonblocking writes just report the number of bytes
actually written, letting the caller resubmit the unwritten part later
if he sees fit. Currently, Tcl always "sees fit", and does so in
background with a hidden [fileevent writable].

This implies that it is currently impossible at script level to
emulate the lower-level short write semantics. I do know of cases
where it matters: I've been forced to do that in C :/

Now, the second of Wayne's proposals, slightly extended, does the job:

   set discarded [chan clear $ch]

Indeed, knowing the number of discarded bytes is equivalent to getting
back the number of bytes actually written from [puts] (which is not
puts' job today).

Of course, the actual name of the subcommand can be any one of:

      chan clear
      chan discard
      chan drop
      chan unflush

Reactions ?

-Alex

Re: [TCLCORE] Upgrade of Tcl's String Hash Algorithm

[Donal K. F. <don...@ma...>]

On 09/02/2010 16:15, Gustaf Neumann wrote:
> The output of Donal showing the buckets indicates certainly
> that FNV leads to less collisions. However, since from my experience,
> we have in tcl many hash tables with only a few items.
> I would not be surprised if most programs run rather slower
> with FNV than with the old tcl hash function.

It depends critically on the operation mix, what keys are being used,
etc., and it's hard to test in situ because it's typically used in
conjunction with other (much more expensive) operations like memory
allocation. Given that, keeping bucket chains short is probably the best
metric of all.

For truly small tables, a Lisp-style alist would actually be cheaper.
Not that they scale...

> maybe, some handcoded inline assembly could speed up the function.

Maybe, but then we'd have to maintain it on all our supported platforms.
:-( The only time we've ever used assembly in Tcl's implementation was
because there was *no* other way to do it (and was for dealing with
particularly odd parts of Windows on x86 only).

Donal.

Re: [TCLCORE] Upgrade of Tcl's String Hash Algorithm

[Eric M. <er...@el...>]

000 VERSIONS:                             1:8.5.8+  2:8.5.8
001 ARRAY genKeys 50                         1.12     1.00
002 ARRAY genKeys 500                        0.93     1.00
003 ARRAY makeHash 500 50                    1.01     1.00
004 BASE64 decode 10                         1.11     1.00
005 BASE64 decode 100                        1.03     1.00
006 BASE64 decode 1000                       1.01     1.00
007 BASE64 decode 10000                      1.02     1.00
008 BASE64 decode2 10                        1.02     1.00
009 BASE64 decode2 100                       0.88     1.00
010 BASE64 decode2 1000                      1.03     1.00
011 BASE64 decode2 10000                     1.03     1.00
012 BASE64 decode3 10                        0.99     1.00
013 BASE64 decode3 100                       0.99     1.00
014 BASE64 decode3 1000                      1.00     1.00
015 BASE64 decode3 10000                     1.01     1.00
016 BASE64 encode 10                         0.98     1.00
017 BASE64 encode 100                        1.02     1.00
018 BASE64 encode 1000                       1.01     1.00
019 BASE64 encode 10000                      1.32     1.00
020 BASE64 encode2 10                        0.99     1.00
021 BASE64 encode2 100                       0.99     1.00
022 BASE64 encode2 1000                      1.02     1.00
023 BASE64 encode2 10000                     1.12     1.00
024 BASE64 encode3 10                        0.97     1.00
025 BASE64 encode3 100                       0.98     1.00
026 BASE64 encode3 1000                      1.00     1.00
027 BASE64 encode3 10000                     1.11     1.00
028 BIN bitset-v1 1000 chars                 1.00     1.00
029 BIN bitset-v1 5000 chars                 1.00     1.00
030 BIN bitset-v1 10000 chars                1.03     1.00
031 BIN bitset-v2 1000 chars                 0.99     1.00
032 BIN bitset-v2 5000 chars                 0.99     1.00
033 BIN bitset-v2 10000 chars                0.99     1.00
034 BIN bitset-v3 1000 chars                 1.00     1.00
035 BIN bitset-v3 5000 chars                 0.99     1.00
036 BIN bitset-v3 10000 chars                0.91     1.00
037 BIN c scan, 1000b                        1.00     1.00
038 BIN c scan, 5000b                        1.08     1.00
039 BIN c scan, 10000b                       1.11     1.00
040 BIN chars, 10000b                        1.02     1.00
041 BIN u char, 10000b                       0.98     1.00
042 CATCH error, complex                     1.01     1.00
043 CATCH no catch used                      0.95     1.00
044 CATCH return error                       0.92     1.00
045 CATCH return except                      0.97     1.00
046 CATCH return ok                          0.93     1.00
047 DATA access in a list                    1.01     1.00
048 DATA access in an array                  1.01     1.00
049 DATA create in a list                    1.22     1.00
050 DATA create in an array                  1.00     1.00
051 ENC iso2022-jp, gets                     0.95     1.00
052 ENC iso2022-jp, read                     0.95     1.00
053 ENC iso2022-jp, read & size              0.99     1.00
054 ENC iso8859-2, gets                      0.99     1.00
055 ENC iso8859-2, read                      1.10     1.00
056 ENC iso8859-2, read & size               1.00     1.00
057 EVAL cmd and mixed lists                 1.07     1.00
058 EVAL cmd eval as list                    1.00     1.00
059 EVAL cmd eval as string                  1.03     1.00
060 EVAL cmd eval in list obj var            1.00     1.00
061 EVAL list cmd and mixed lists            1.02     1.00
062 EVAL list cmd and pure lists             1.01     1.00
063 EXPR $a != $b int                        0.97     1.00
064 EXPR $a != $b str (!= len)               1.00     1.00
065 EXPR $a != $b str (== len)               1.02     1.00
066 EXPR $a == $b int                        0.96     1.00
067 EXPR $a == $b str (!= len)               1.02     1.00
068 EXPR $a == $b str (== len)               1.00     1.00
069 EXPR braced                              0.99     1.00
070 EXPR fifty operands                      0.99     1.00
071 EXPR incr with expr                      1.00     1.00
072 EXPR incr with incr                      1.00     1.00
073 EXPR inline                              0.96     1.00
074 EXPR one operand                         0.98     1.00
075 EXPR ten operands                        1.01     1.00
076 EXPR unbraced                            1.01     1.00
077 EXPR unbraced long                       0.99     1.00
078 FCOPY binary: 160K                       1.01     1.00
079 FCOPY encoding: 160K                     1.00     1.00
080 FCOPY std: 160K                          1.00     1.00
081 FILE exec interp                         1.00     1.00
082 FILE exec interp: pkg require            1.07     1.00
083 FILE exists tmpfile (obj)                1.02     1.00
084 FILE exists ~                            0.96     1.00
085 FILE exists! tmpfile (obj)               0.97     1.00
086 FILE exists! tmpfile (str)               0.95     1.00
087 FILE glob  tmpdir (60 entries)           1.02     1.00
088 FILE glob / all subcommands              1.01     1.00
089 FILE glob / atime                        1.01     1.00
090 FILE glob / attributes                   1.03     1.00
091 FILE glob / dirname                      1.00     1.00
092 FILE glob / executable                   1.01     1.00
093 FILE glob / exists                       1.00     1.00
094 FILE glob / extension                    1.00     1.00
095 FILE glob / isdirectory                  0.99     1.00
096 FILE glob / isfile                       1.00     1.00
097 FILE glob / mtime                        0.99     1.00
098 FILE glob / owned                        0.99     1.00
099 FILE glob / readable                     1.01     1.00
100 FILE glob / rootname                     1.01     1.00
101 FILE glob / size                         0.99     1.00
102 FILE glob / tail                         1.01     1.00
103 FILE glob / writable                     1.02     1.00
104 FILE recurse / -dir                      1.02     1.00
105 FILE recurse / cd                        0.98     1.00
106 GCCont_cpb::cGCC 50                      1.00     1.00
107 GCCont_cpb::cGCC 500                     0.99     1.00
108 GCCont_cpb::cGCC 5000                    0.99     1.00
109 GCCont_cpbre1::cGCC 50                   1.02     1.00
110 GCCont_cpbre1::cGCC 500                  0.99     1.00
111 GCCont_cpbre1::cGCC 5000                 1.06     1.00
112 GCCont_cpbre2::cGCC 50                   0.99     1.00
113 GCCont_cpbre2::cGCC 500                  0.99     1.00
114 GCCont_cpbre2::cGCC 5000                 1.05     1.00
115 GCCont_cpbrs2::cGCC 50                   1.00     1.00
116 GCCont_cpbrs2::cGCC 500                  1.02     1.00
117 GCCont_cpbrs2::cGCC 5000                 1.00     1.00
118 GCCont_cpbrs::cGCC1 50                   1.02     1.00
119 GCCont_cpbrs::cGCC1 500                  1.01     1.00
120 GCCont_cpbrs::cGCC1 5000                 0.98     1.00
121 GCCont_cpbrs::cGCC2 50                   1.00     1.00
122 GCCont_cpbrs::cGCC2 500                  1.01     1.00
123 GCCont_cpbrs::cGCC2 5000                 1.00     1.00
124 GCCont_cpbrs_trap::cGCC 50               1.03     1.00
125 GCCont_cpbrs_trap::cGCC 500              1.06     1.00
126 GCCont_cpbrs_trap::cGCC 5000             1.08     1.00
127 GCCont_expr::cGCC 50                     0.99     1.00
128 GCCont_expr::cGCC 500                    1.00     1.00
129 GCCont_expr::cGCC 5000                   1.01     1.00
130 GCCont_i::cGCC1 50                       1.00     1.00
131 GCCont_i::cGCC1 500                      0.88     1.00
132 GCCont_i::cGCC1 5000                     0.99     1.00
133 GCCont_i::cGCC2 50                       0.98     1.00
134 GCCont_i::cGCC2 500                      0.95     1.00
135 GCCont_i::cGCC2 5000                     1.00     1.00
136 GCCont_i::cGCC3 50                       1.01     1.00
137 GCCont_i::cGCC3 500                      0.97     1.00
138 GCCont_i::cGCC3 5000                     0.99     1.00
139 GCCont_r1::cGCC 50                       1.00     1.00
140 GCCont_r1::cGCC 500                      1.01     1.00
141 GCCont_r1::cGCC 5000                     1.01     1.00
142 GCCont_r2::cGCC 50                       1.22     1.00
143 GCCont_r2::cGCC 500                      0.95     1.00
144 GCCont_r2::cGCC 5000                     1.00     1.00
145 GCCont_r3::cGCC 50                       1.01     1.00
146 GCCont_r3::cGCC 500                      1.00     1.00
147 GCCont_r3::cGCC 5000                     1.00     1.00
148 GCCont_rsf1::cGCC 50                     1.01     1.00
149 GCCont_rsf1::cGCC 500                    1.01     1.00
150 GCCont_rsf1::cGCC 5000                   0.99     1.00
151 GCCont_rsf2::cGCC1 50                    1.01     1.00
152 GCCont_rsf2::cGCC1 500                   0.99     1.00
153 GCCont_rsf2::cGCC1 5000                  0.99     1.00
154 GCCont_rsf2::cGCC2 50                    1.00     1.00
155 GCCont_rsf2::cGCC2 500                   1.02     1.00
156 GCCont_rsf2::cGCC2 5000                  1.00     1.00
157 GCCont_rsf3::cGCC 50                     1.00     1.00
158 GCCont_rsf3::cGCC 500                    1.01     1.00
159 GCCont_rsf3::cGCC 5000                   1.04     1.00
160 GCCont_turing::cGCC 50                   1.01     1.00
161 GCCont_turing::cGCC 500                  0.98     1.00
162 GCCont_turing::cGCC 5000                 0.97     1.00
163 HEAPSORT size 10                         1.09     1.00
164 HEAPSORT size 50                         1.02     1.00
165 HEAPSORT size 100                        1.00     1.00
166 HEAPSORT2 size 10                        1.07     1.00
167 HEAPSORT2 size 50                        0.98     1.00
168 HEAPSORT2 size 100                       1.00     1.00
169 IF 1/0 check                             0.95     1.00
170 IF else true al                          0.93     1.00
171 IF else true numeric                     0.90     1.00
172 IF elseif true al                        0.89     1.00
173 IF elseif true numeric                   0.86     1.00
174 IF if false al/al                        0.80     1.00
175 IF if false al/num                       0.91     1.00
176 IF if false num/num                      0.92     1.00
177 IF if true al                            0.90     1.00
178 IF if true al/al                         0.92     1.00
179 IF if true num/num                       0.91     1.00
180 IF if true numeric                       0.91     1.00
181 IF multi 1st true                        0.91     1.00
182 IF multi 2nd true                        0.94     1.00
183 IF multi 9th true                        0.99     1.00
184 IF multi default true                    0.99     1.00
185 KLIST shuffle0 llength 1                 0.98     1.00
186 KLIST shuffle0 llength 10                0.91     1.00
187 KLIST shuffle0 llength 100               0.91     1.00
188 KLIST shuffle0 llength 1000              0.99     1.00
189 KLIST shuffle0 llength 10000             0.98     1.00
190 KLIST shuffle1-s llength 1               1.08     1.00
191 KLIST shuffle1-s llength 10              1.04     1.00
192 KLIST shuffle1-s llength 100             1.02     1.00
193 KLIST shuffle1-s llength 1000            0.98     1.00
194 KLIST shuffle1a llength 1                1.00     1.00
195 KLIST shuffle1a llength 10               1.00     1.00
196 KLIST shuffle1a llength 100              0.99     1.00
197 KLIST shuffle1a llength 1000             0.99     1.00
198 KLIST shuffle1a llength 10000            0.99     1.00
199 KLIST shuffle2 llength 1                 1.00     1.00
200 KLIST shuffle2 llength 10                0.99     1.00
201 KLIST shuffle2 llength 100               0.99     1.00
202 KLIST shuffle2 llength 1000              0.99     1.00
203 KLIST shuffle2 llength 10000             1.00     1.00
204 KLIST shuffle3 llength 1                 0.98     1.00
205 KLIST shuffle3 llength 10                1.00     1.00
206 KLIST shuffle3 llength 100               1.01     1.00
207 KLIST shuffle3 llength 1000              1.00     1.00
208 KLIST shuffle3 llength 10000             1.07     1.00
209 KLIST shuffle4 llength 1                 0.97     1.00
210 KLIST shuffle4 llength 10                0.99     1.00
211 KLIST shuffle4 llength 100               0.99     1.00
212 KLIST shuffle4 llength 1000              0.99     1.00
213 KLIST shuffle4 llength 10000             0.99     1.00
214 KLIST shuffle5-s llength 1               1.01     1.00
215 KLIST shuffle5-s llength 10              0.93     1.00
216 KLIST shuffle5-s llength 100             0.93     1.00
217 KLIST shuffle5-s llength 1000            0.99     1.00
218 KLIST shuffle5a llength 1                1.00     1.00
219 KLIST shuffle5a llength 10               1.02     1.00
220 KLIST shuffle5a llength 100              0.99     1.00
221 KLIST shuffle5a llength 1000             1.01     1.00
222 KLIST shuffle5a llength 10000            1.00     1.00
223 KLIST shuffle6 llength 1                 1.04     1.00
224 KLIST shuffle6 llength 10                0.97     1.00
225 KLIST shuffle6 llength 100               0.96     1.00
226 KLIST shuffle6 llength 1000              0.96     1.00
227 KLIST shuffle6 llength 10000             0.96     1.00
228 LIST append to list                      1.01     1.00
229 LIST concat APPEND 2x10                  0.86     1.00
230 LIST concat APPEND 2x100                 0.90     1.00
231 LIST concat APPEND 2x1000                0.92     1.00
232 LIST concat APPEND 2x10000               1.00     1.00
233 LIST concat CONCAT 2x10                  1.07     1.00
234 LIST concat CONCAT 2x100                 1.11     1.00
235 LIST concat CONCAT 2x1000                1.01     1.00
236 LIST concat CONCAT 2x10000               0.79     1.00
237 LIST concat EVAL/LAPPEND 2x10            0.95     1.00
238 LIST concat EVAL/LAPPEND 2x100           0.99     1.00
239 LIST concat EVAL/LAPPEND 2x1000          1.01     1.00
240 LIST concat EVAL/LAPPEND 2x10000         1.00     1.00
241 LIST concat FOREACH/LAPPEND 2x10         0.98     1.00
242 LIST concat FOREACH/LAPPEND 2x100        0.99     1.00
243 LIST concat FOREACH/LAPPEND 2x1000       1.13     1.00
244 LIST concat FOREACH/LAPPEND 2x10000      1.06     1.00
245 LIST concat SET 2x10                     1.00     1.00
246 LIST concat SET 2x100                    1.03     1.00
247 LIST concat SET 2x1000                   1.00     1.00
248 LIST concat SET 2x10000                  1.01     1.00
249 LIST exact search, first item            0.97     1.00
250 LIST exact search, last item             0.98     1.00
251 LIST exact search, middle item           0.98     1.00
252 LIST exact search, non-item              1.00     1.00
253 LIST exact search, typed item            0.99     1.00
254 LIST exact search, untyped item          0.99     1.00
255 LIST index first element                 0.98     1.00
256 LIST index last element                  0.98     1.00
257 LIST index middle element                0.98     1.00
258 LIST insert an item at "end"             1.00     1.00
259 LIST insert an item at middle            1.00     1.00
260 LIST insert an item at start             0.90     1.00
261 LIST iterate list                        1.00     1.00
262 LIST join list                           1.00     1.00
263 LIST large, early range                  0.96     1.00
264 LIST large, late range                   0.94     1.00
265 LIST length, pure list                   0.98     1.00
266 LIST list                                1.04     1.00
267 LIST lset foreach  l                     0.99     1.00
268 LIST lset foreach  list                  1.06     1.00
269 LIST lset foreach ""s l                  0.95     1.00
270 LIST lset foreach ""s list               0.90     1.00
271 LIST regexp search, first item           1.00     1.00
272 LIST regexp search, last item            0.99     1.00
273 LIST regexp search, non-item             0.95     1.00
274 LIST remove first element                1.02     1.00
275 LIST remove in mixed list                1.03     1.00
276 LIST remove last element                 1.00     1.00
277 LIST remove middle element               1.02     1.00
278 LIST replace first el with multiple      1.01     1.00
279 LIST replace first element               1.01     1.00
280 LIST replace in mixed list               1.00     1.00
281 LIST replace last el with multiple       1.05     1.00
282 LIST replace last element                1.03     1.00
283 LIST replace middle el with multiple     1.03     1.00
284 LIST replace middle element              1.02     1.00
285 LIST replace range                       0.99     1.00
286 LIST reverse core                        0.98     1.00
287 LIST reverse lappend                     0.98     1.00
288 LIST small, early range                  1.29     1.00
289 LIST small, late range                   0.97     1.00
290 LIST sort                                1.00     1.00
291 LIST sorted search, first item           0.99     1.00
292 LIST sorted search, last item            0.98     1.00
293 LIST sorted search, middle item          1.00     1.00
294 LIST sorted search, non-item             0.99     1.00
295 LIST sorted search, typed item           1.03     1.00
296 LIST typed sort                          1.02     1.00
297 LOOP for (to 1000)                       0.96     1.00
298 LOOP for, iterate list                   1.08     1.00
299 LOOP for, iterate string                 1.00     1.00
300 LOOP foreach, iterate list               0.99     1.00
301 LOOP foreach, iterate string             1.02     1.00
302 LOOP while (to 1000)                     0.99     1.00
303 LOOP while 1 (to 1000)                   1.00     1.00
304 MAP ([chars])-case regsub                0.99     1.00
305 MAP http mapReply                        1.01     1.00
306 MAP regsub -nocase, no match             1.00     1.00
307 MAP regsub 1 val                         1.00     1.00
308 MAP regsub 1 val -nocase                 1.02     1.00
309 MAP regsub 2 val                         1.04     1.00
310 MAP regsub 2 val -nocase                 1.00     1.00
311 MAP regsub 3 val                         1.01     1.00
312 MAP regsub 3 val -nocase                 0.92     1.00
313 MAP regsub 4 val                         1.01     1.00
314 MAP regsub 4 val -nocase                 0.94     1.00
315 MAP regsub short                         0.99     1.00
316 MAP regsub, no match                     0.97     1.00
317 MAP string -nocase, no match             1.00     1.00
318 MAP string 1 val                         1.19     1.00
319 MAP string 1 val -nocase                 1.02     1.00
320 MAP string 2 val                         1.05     1.00
321 MAP string 2 val -nocase                 0.99     1.00
322 MAP string 3 val                         1.02     1.00
323 MAP string 3 val -nocase                 1.00     1.00
324 MAP string 4 val                         0.99     1.00
325 MAP string 4 val -nocase                 0.99     1.00
326 MAP string short                         1.00     1.00
327 MAP string, no match                     1.00     1.00
328 MAP |-case regsub                        0.99     1.00
329 MAP |-case strmap                        0.98     1.00
330 MATRIX mult 5x5                          1.01     1.00
331 MATRIX mult 10x10                        1.00     1.00
332 MATRIX mult 15x15                        1.00     1.00
333 MATRIX transposition-0                   1.01     1.00
334 MATRIX transposition-1                   1.02     1.00
335 MD5 msg len 10                           1.02     1.00
336 MD5 msg len 100                          1.01     1.00
337 MD5 msg len 1000                         1.01     1.00
338 MD5 msg len 10000                        1.01     1.00
339 MTHD array stored proc call              0.99     1.00
340 MTHD call absolute                       0.99     1.00
341 MTHD call relative                       0.98     1.00
342 MTHD direct ns proc call                 1.01     1.00
343 MTHD imported ns proc call               0.99     1.00
344 MTHD indirect proc eval                  0.97     1.00
345 MTHD indirect proc eval #2               0.96     1.00
346 MTHD inline call                         1.04     1.00
347 MTHD interp alias proc call              0.98     1.00
348 MTHD ns lookup call                      0.97     1.00
349 MTHD switch method call                  1.01     1.00
350 NS alternating                           0.98     1.00
351 PARSE html form upload (7978)            0.90     1.00
352 PARSE html form upload (993570)          0.99     1.00
353 PROC do-nothing, no args                 1.03     1.00
354 PROC do-nothing, one arg                 1.00     1.00
355 PROC empty, no args                      1.09     1.00
356 PROC empty, use args                     1.09     1.00
357 PROC explicit return                     0.99     1.00
358 PROC explicit return (2)                 0.56     1.00
359 PROC explicit return (3)                 0.97     1.00
360 PROC heavily commented                   0.92     1.00
361 PROC implicit return                     0.98     1.00
362 PROC implicit return (2)                 1.04     1.00
363 PROC implicit return (3)                 1.01     1.00
364 PROC local links with global             1.04     1.00
365 PROC local links with upvar              1.00     1.00
366 PROC local links with variable           1.01     1.00
367 RE 1-char long-end                       1.01     1.00
368 RE 1-char long-end catching              0.98     1.00
369 RE 1-char long-middle                    1.03     1.00
370 RE 1-char long-middle catching           1.01     1.00
371 RE 1-char long-start                     1.03     1.00
372 RE 1-char long-start catching            1.01     1.00
373 RE 1-char short                          1.05     1.00
374 RE 1-char short catching                 0.92     1.00
375 RE basic                                 1.00     1.00
376 RE basic catching                        1.01     1.00
377 RE c-comment long                        1.00     1.00
378 RE c-comment long catching               1.00     1.00
379 RE c-comment long nomatch                1.00     1.00
380 RE c-comment long nomatch catching       1.00     1.00
381 RE c-comment long pmatch                 1.00     1.00
382 RE c-comment long pmatch catching        1.00     1.00
383 RE c-comment many *s                     1.00     1.00
384 RE c-comment many *s catching            1.00     1.00
385 RE c-comment nomatch                     1.00     1.00
386 RE c-comment nomatch catching            0.99     1.00
387 RE c-comment simple                      0.97     1.00
388 RE c-comment simple catching             1.00     1.00
389 RE count all matches                     1.02     1.00
390 RE extract all matches                   0.97     1.00
391 RE ini file                              0.99     1.00
392 RE ini file ng                           1.01     1.00
393 RE literal regexp                        1.01     1.00
394 RE n-char long-end                       0.98     1.00
395 RE n-char long-end catching              0.99     1.00
396 RE n-char long-middle                    0.99     1.00
397 RE n-char long-middle catching           1.07     1.00
398 RE n-char long-start                     1.06     1.00
399 RE n-char long-start catching            1.00     1.00
400 RE n-char short                          1.05     1.00
401 RE n-char short catching                 1.02     1.00
402 RE static anchored match                 1.02     1.00
403 RE static anchored match dot             1.04     1.00
404 RE static anchored nomatch               1.00     1.00
405 RE static anchored nomatch dot           1.05     1.00
406 RE static l-anchored match               1.04     1.00
407 RE static l-anchored nomatch             1.01     1.00
408 RE static long match                     1.01     1.00
409 RE static long nomatch                   1.00     1.00
410 RE static r-anchored match               1.03     1.00
411 RE static r-anchored nomatch             1.03     1.00
412 RE static short match                    1.01     1.00
413 RE static short nomatch                  1.04     1.00
414 RE var ***= directive match              1.00     1.00
415 RE var ***= directive nomatch            1.01     1.00
416 RE var . match                           1.06     1.00
417 RE var [0-9] match                       0.99     1.00
418 RE var \d match                          0.98     1.00
419 RE var ^$ nomatch                        1.01     1.00
420 RE var backtrack case                    1.01     1.00
421 RE var-based regexp                      0.93     1.00
422 READ 595K, cat                           1.00     1.00
423 READ 595K, gets                          1.01     1.00
424 READ 595K, glob-grep match               1.00     1.00
425 READ 595K, glob-grep nomatch             1.01     1.00
426 READ 595K, read                          1.00     1.00
427 READ 595K, read & size                   1.00     1.00
428 READ 595K, read dyn buf                  0.99     1.00
429 READ 595K, read small buf                0.99     1.00
430 READ 3050b, cat                          0.92     1.00
431 READ 3050b, gets                         1.04     1.00
432 READ 3050b, glob-grep match              1.00     1.00
433 READ 3050b, glob-grep nomatch            0.99     1.00
434 READ 3050b, read                         0.95     1.00
435 READ 3050b, read & size                  1.00     1.00
436 READ 3050b, read dyn buf                 1.00     1.00
437 READ 3050b, read small buf               0.99     1.00
438 READ bin 595K, cat                       0.98     1.00
439 READ bin 595K, gets                      1.00     1.00
440 READ bin 595K, glob-grep match           1.04     1.00
441 READ bin 595K, glob-grep nomatch         0.99     1.00
442 READ bin 595K, read                      1.00     1.00
443 READ bin 595K, read & size               1.01     1.00
444 READ bin 595K, read dyn buf              1.07     1.00
445 READ bin 595K, read small buf            0.99     1.00
446 READ bin 3050b, cat                      1.09     1.00
447 READ bin 3050b, gets                     1.01     1.00
448 READ bin 3050b, glob-grep match          1.00     1.00
449 READ bin 3050b, glob-grep nomatch        1.00     1.00
450 READ bin 3050b, read                     1.02     1.00
451 READ bin 3050b, read & size              0.98     1.00
452 READ bin 3050b, read dyn buf             1.00     1.00
453 READ bin 3050b, read small buf           1.00     1.00
454 SHA (A) msg len 10                       0.98     1.00
455 SHA (A) msg len 100                      0.93     1.00
456 SHA (A) msg len 1000                     1.02     1.00
457 SHA (A) msg len 10000                    1.03     1.00
458 SPLIT iter, 4000 uchars                  1.00     1.00
459 SPLIT iter, 4010 chars                   1.03     1.00
460 SPLIT iter, rand 100 c                   1.00     1.00
461 SPLIT iter, rand 1000 c                  0.89     1.00
462 SPLIT iter, rand 10000 c                 1.00     1.00
463 SPLIT on 'c', 4000 uchars                0.99     1.00
464 SPLIT on 'c', 4010 chars                 0.99     1.00
465 SPLIT on 'cz', 4000 uchars               0.97     1.00
466 SPLIT on 'cz', 4010 chars                0.99     1.00
467 SPLIT on 'cû', 4000 uchars               1.01     1.00
468 SPLIT on 'cû', 4010 chars                1.00     1.00
469 SPLIT, 4000 uchars                       0.99     1.00
470 SPLIT, 4010 chars                        0.98     1.00
471 SPLIT, rand 100 c                        1.01     1.00
472 SPLIT, rand 1000 c                       1.00     1.00
473 SPLIT, rand 10000 c                      0.96     1.00
474 STR append                               0.99     1.00
475 STR append (1KB + 1KB)                   0.98     1.00
476 STR append (1MB + (1b+1K+1b)*100)        0.98     1.00
477 STR append (1MB + 1KB)                   0.99     1.00
478 STR append (1MB + 1KB*20)                0.99     1.00
479 STR append (1MB + 1KB*1000)              0.99     1.00
480 STR append (1MB + 1MB*3)                 1.01     1.00
481 STR append (1MB + 1MB*5)                 1.03     1.00
482 STR append (1MB + 2b*1000)               0.99     1.00
483 STR append (10KB + 1KB)                  1.01     1.00
484 STR first (failure)                      0.99     1.00
485 STR first (failure) utf                  0.98     1.00
486 STR first (success)                      1.01     1.00
487 STR first (success) utf                  0.95     1.00
488 STR first (total failure)                1.00     1.00
489 STR first (total failure) utf            0.99     1.00
490 STR index 0                              1.00     1.00
491 STR index 100                            1.05     1.00
492 STR index 500                            1.04     1.00
493 STR info locals match                    1.01     1.00
494 STR last (failure)                       1.00     1.00
495 STR last (success)                       0.95     1.00
496 STR last (total failure)                 1.00     1.00
497 STR length (==4010)                      1.05     1.00
498 STR length growing (1000)                0.99     1.00
499 STR length growing uc (1000)             1.01     1.00
500 STR length of a LIST                     0.97     1.00
501 STR length static str                    0.99     1.00
502 STR match, complex (failure)             1.00     1.00
503 STR match, complex (success early)       1.03     1.00
504 STR match, complex (success late)        1.00     1.00
505 STR match, complex (total failure)       1.01     1.00
506 STR match, exact (failure)               1.04     1.00
507 STR match, exact (success)               1.03     1.00
508 STR match, exact -nocase (failure)       0.97     1.00
509 STR match, exact -nocase (success)       1.00     1.00
510 STR match, recurse (fail backtrack)      0.99     1.00
511 STR match, recurse (fail bt1)            1.08     1.00
512 STR match, recurse (fail bt2)            1.08     1.00
513 STR match, recurse (fail ranchor)        1.01     1.00
514 STR match, recurse (success bt2)         1.07     1.00
515 STR match, recurse2 (fail)               0.97     1.00
516 STR match, recurse2 (success)            1.07     1.00
517 STR match, simple (failure)              0.99     1.00
518 STR match, simple (success)              1.09     1.00
519 STR range, index 100..200 of 4010        1.02     1.00
520 STR repeat, 4010 chars * 10              0.97     1.00
521 STR repeat, 4010 chars * 100             1.00     1.00
522 STR repeat, abcdefghij * 10              0.97     1.00
523 STR repeat, abcdefghij * 100             1.00     1.00
524 STR repeat, abcdefghij * 1000            1.00     1.00
525 STR replace, equal replacement           0.99     1.00
526 STR replace, longer replacement          0.99     1.00
527 STR replace, no replacement              1.02     1.00
528 STR reverse core, 10 c                   1.01     1.00
529 STR reverse core, 10 uc                  1.05     1.00
530 STR reverse core, 100 c                  1.01     1.00
531 STR reverse core, 100 uc                 1.01     1.00
532 STR reverse core, 400 c                  1.00     1.00
533 STR reverse core, 400 uc                 0.97     1.00
534 STR reverse iter/append, 10 c            1.02     1.00
535 STR reverse iter/append, 10 uc           0.97     1.00
536 STR reverse iter/append, 100 c           0.95     1.00
537 STR reverse iter/append, 100 uc          1.00     1.00
538 STR reverse iter/append, 400 c           0.97     1.00
539 STR reverse iter/append, 400 uc          0.97     1.00
540 STR reverse iter/set, 10 c               1.01     1.00
541 STR reverse iter/set, 10 uc              1.00     1.00
542 STR reverse iter/set, 100 c              0.99     1.00
543 STR reverse iter/set, 100 uc             1.02     1.00
544 STR reverse iter/set, 400 c              1.00     1.00
545 STR reverse iter/set, 400 uc             1.02     1.00
546 STR reverse recursive, 10 c              1.01     1.00
547 STR reverse recursive, 10 uc             1.00     1.00
548 STR reverse recursive, 100 c             1.00     1.00
549 STR reverse recursive, 100 uc            1.00     1.00
550 STR reverse recursive, 400 c             0.99     1.00
551 STR reverse recursive, 400 uc            1.00     1.00
552 STR str $a eq $b                         1.04     1.00
553 STR str $a eq $b (same obj)              1.00     1.00
554 STR str $a equal ""                      1.00     1.00
555 STR str $a ne $b                         1.05     1.00
556 STR str $a ne $b (same obj)              1.03     1.00
557 STR str num == ""                        1.00     1.00
558 STR string compare                       1.00     1.00
559 STR string compare ""                    1.05     1.00
560 STR string compare long                  1.02     1.00
561 STR string compare long (same obj)       1.05     1.00
562 STR string compare mixed long            0.98     1.00
563 STR string compare uni long              1.01     1.00
564 STR string equal ""                      1.02     1.00
565 STR string equal long (!= len)           1.02     1.00
566 STR string equal long (== len)           0.99     1.00
567 STR string equal long (same obj)         1.04     1.00
568 STR string equal mixed long              1.02     1.00
569 STR string equal uni long                1.00     1.00
570 STR/LIST length, obj shimmer             0.97     1.00
571 SWITCH 1st true                          0.87     1.00
572 SWITCH 2nd true                          0.58     1.00
573 SWITCH 9th true                          0.95     1.00
574 SWITCH default true                      0.98     1.00
575 TRACE all set (rwu)                      0.99     1.00
576 TRACE no trace set                       0.99     1.00
577 TRACE read                               0.96     1.00
578 TRACE unset                              0.95     1.00
579 TRACE write                              1.05     1.00
580 UNSET catch var !exist                   1.00     1.00
581 UNSET catch var exists                   0.94     1.00
582 UNSET info check var !exist              1.11     1.00
583 UNSET info check var exists              1.05     1.00
584 UNSET nocomplain var !exist              1.08     1.00
585 UNSET nocomplain var exists              1.08     1.00
586 UNSET var exists                         0.97     1.00
587 UPLEVEL none                             1.12     1.00
588 UPLEVEL primed                           1.03     1.00
589 UPLEVEL to nseval                        0.98     1.00
590 UPLEVEL to proc                          1.12     1.00
591 VAR 'array set' of 100 elems             0.98     1.00
592 VAR 100 'set's in array                  0.98     1.00
593 VAR access global                        1.00     1.00
594 VAR access local proc arg                0.99     1.00
595 VAR access locally set                   1.00     1.00
596 VAR access upvar                         0.86     1.00
597 VAR incr global var 1000x                1.02     1.00
598 VAR incr local var 1000x                 0.99     1.00
599 VAR incr upvar var 1000x                 1.00     1.00
600 VAR mset                                 1.04     1.00
601 VAR mset (foreach)                       0.99     1.00
602 VAR ref absolute                         1.03     1.00
603 VAR ref local                            0.99     1.00
604 VAR ref variable                         1.01     1.00
605 VAR set array element                    1.01     1.00
606 VAR set scalar                           0.95     1.00
607 WORDCOUNT wc1                            0.98     1.00
608 WORDCOUNT wc2                            0.99     1.00
609 WORDCOUNT wc3                            1.00     1.00
609 BENCHMARKS                            1:8.5.8+  2:8.5.8

Re: [TCLCORE] Upgrade of Tcl's String Hash Algorithm

[Colin M. <co...@ch...>]

Larry McVoy wrote:
> Dear Colin,
>
> Thank you for your opinion, but the mail was addressed to the core,
> it concerns how they do work

Collaboratively.

Re: [TCLCORE] Upgrade of Tcl's String Hash Algorithm

[Gustaf N. <ne...@wu...>]

Am 09.02.10 02:47, schrieb Donal K. Fellows:
> On 08/02/2010 18:45, Eric Melski wrote:
>> That's very impressive, but with only three hash entries you can hardly
>> say that's a representative test case.
...
> FWIW, with a focussed test that *just* does comparison of the hashing
> speed (see attached; the contents of the two hashing functions were
> copied directly from HashStringKey in Tcl 8.5 and the HEAD) we find that
> on x86 the old algorithm is indeed faster. 
indeed,  the attached program shows me that the hashing speed of the
old function is constantly faster than FNV (when compiled with
-Os like Tcl, intel mac, 64bit, 10.6.2).

old: 2137177 us    (1517306493d)
new: 2296518 us    (3684793705d)

(i just added an outer loop with 500 iterations to obtain more
precise timings). By using the function in tcl 8.5.7 for HashStringKey(),
i could not get the 15% speedup, but i see a rather larger slowdown
for the first test.

proc foo {} {set x(foobar) [set x(barfoo) [set x(ballyhoo) 1]];return}
puts [time {time { foo } 10000} 1000]
proc foo {} {set x [set y [set z 1]]; return}
puts [time {time { foo } 10000} 1000]

# classic
# 9105.318082 microseconds per iteration
# 4686.419043 microseconds per iteration

# fnv
# 9367.280143 microseconds per iteration
# 4684.1961710000005 microseconds per iteration

Btw, the old function could be made slightly faster by avoiding one
incr operation

     for (c = *string ; c ; c = *++string) {
         result += (result<<3) + c;
     }

The output of Donal showing the buckets indicates certainly
that FNV leads to less collisions. However, since from my experience,
we have in tcl many hash tables with only a few items.
I would not be surprised if most programs run rather slower
with FNV than with the old tcl hash function.

maybe, some handcoded inline assembly could speed up the function.

-gn

Re: [TCLCORE] Upgrade of Tcl's String Hash Algorithm

[Larry M. <lm...@bi...>]

Dear Colin,

Thank you for your opinion, but the mail was addressed to the core,
it concerns how they do work, not how you do work, and I'm more 
interested in what they think.

Thank you.

Re: [TCLCORE] Upgrade of Tcl's String Hash Algorithm

[Colin M. <co...@ch...>]

Larry McVoy wrote:
> I wanted to (briefly) touch on process.  After a lovely discussion
> on #tcl it seems like it might be worthwhile to point out the 
> value of a review process.  I think that you especially may 
> appreciate the benefits.
>   

Reading your email, I'm moved to investigate the connection between 
'review' and 'review process'.  You argue cogently for code review, but 
nowhere for code review process.  You treat as synonyms what are clearly 
not.

Nobody would dissuade a person from reviewing open source code.  No 
'process' is required:  you get a copy, you study it, it's reviewed.  
But that's not what 'review process' means.

Half of your email, Larry, extols the virtues of code review.  The rest 
insinuates that since it's such a good thing, people should be forced to 
do it.

> Reviews are not for beating people up.  If people need beating that
> is best done in private.
> Reviews are somewhat good at catching problems.  That's what people
> think they are for.
> Reviews are for educating other people.  That's what people forget.
>   

Reviews are great, evidently, but what has this to do with process?  
Isn't what you call 'process' really just a nice way of saying 'obligation?'

> IMHO, if this sort of thing went through a review process
>   

See how the word 'process' creeps back into a discussion of the merits 
of review as if they were the same thing?

>     - you would get more strokes for taking on this problem
>     - at least the core would get educated about what you are doing
>     - maybe someone would have something useful to add
>   

That could all occur in any number of other ways.  Not merely from 
'review', and not demonstrably from any kind of 'process.'

> I agree with Colin (or anyone) if/when they say "don't slow down the
> people who are coding good stuff".  But I disagree with Colin et al
> that reviews do that.

Don't think I ever said reviews do that.  I think imposed processes do that.

> Good code reviews reward the guy doing the work,
> educate the people following along, there is pretty much no downside
> when it is done right.

If there were no downside it wouldn't have to be imposed or mandated, 
and to call coercion 'process' doesn't make it any more palatable.

Review is good when it's needed or desired and not when it's not.  And 
it's precisely when review is not needed or desired by those in the best 
position to know that 'process' reveals itself as obligation, resulting 
in wasted volunteer time and effort.

Bottom Line Time: the Tcl license explicitly states that there is no 
warranty.  This strongly implies that any onus to inspect the code for 
quality, suitability ir fitness for purpose is yours (the users.)  
Trying to foist that obligation onto the people who are giving you the 
code as a condition of your accepting it seems to me to be pretty grubby.

Colin.

Re: [TCLCORE] Upgrade of Tcl's String Hash Algorithm

[Larry M. <lm...@bi...>]

Thanks for this Donal, it helps.  And thanks for diving into this,
it helps make tcl better.

I wanted to (briefly) touch on process.  After a lovely discussion
on #tcl it seems like it might be worthwhile to point out the 
value of a review process.  I think that you especially may 
appreciate the benefits.

Reviews are not for beating people up.  If people need beating that
is best done in private.

Reviews are somewhat good at catching problems.  That's what people
think they are for.

Reviews are for educating other people.  That's what people forget.

IMHO, if this sort of thing went through a review process

    - you would get more strokes for taking on this problem
    - at least the core would get educated about what you are doing
    - maybe someone would have something useful to add

I agree with Colin (or anyone) if/when they say "don't slow down the
people who are coding good stuff".  But I disagree with Colin et al
that reviews do that.  Good code reviews reward the guy doing the work,
educate the people following along, there is pretty much no downside
when it is done right.

--lm

Re: [TCLCORE] Upgrade of Tcl's String Hash Algorithm

[Donal K. F. <don...@ma...>]

On 08/02/2010 18:45, Eric Melski wrote:
> That's very impressive, but with only three hash entries you can hardly
> say that's a representative test case.

Getting a properly representative evaluation of the hash function itself
is tricky (actually impossible in Tcl itself; too much noise from other
things). The attached program helps clarify (and shows also that speed
of hashing isn't the whole story).

> It would be nice to see comparisons on other platforms.  According to
> Wikipedia, OSX represents only about 5% of the total market share of
> computers
> (http://en.wikipedia.org/wiki/Usage_share_of_operating_systems).  By
> comparison, XP represents about 60%, and Vista about 25%.  Do you have
> comparison data on either of those platforms?  How about on any of the
> modern Linux distributions (Ubuntu, SUSE, etc)?

OTOH, those all are typically deployed with the same processor
architecture and none of the hashing requires *any* OS interaction. What
changes there are between the platforms will be due to compiler
differences (I'm using a reasonably recent gcc; I'm not about to acquire
either the Microsoft or Intel compilers just for this argument).

FWIW, with a focussed test that *just* does comparison of the hashing
speed (see attached; the contents of the two hashing functions were
copied directly from HashStringKey in Tcl 8.5 and the HEAD) we find that
on x86 the old algorithm is indeed faster. But that's not the whole
story. Comparing the statistics out of the two hash algorithms (not
speed, so easier to compare between builds) then the loading
distribution patterns for each of the words in /usr/share/dict/words is
very similar. If we take a table containing all integers from 0 to
999999 though, we see a clearer difference:

Classic algorithm (as reported by [array statistics]):
   1000000 entries in table, 1048576 buckets
   number of buckets with 0 entries: 502271
   number of buckets with 1 entries: 276353
   number of buckets with 2 entries: 168961
   number of buckets with 3 entries: 51585
   number of buckets with 4 entries: 31912
   number of buckets with 5 entries: 7806
   number of buckets with 6 entries: 6553
   number of buckets with 7 entries: 1340
   number of buckets with 8 entries: 1086
   number of buckets with 9 entries: 344
   number of buckets with 10 or more entries: 365
   average search distance for entry: 1.8

FNV algorithm:
   1000000 entries in table, 1048576 buckets
   number of buckets with 0 entries: 400740
   number of buckets with 1 entries: 388150
   number of buckets with 2 entries: 185898
   number of buckets with 3 entries: 58036
   number of buckets with 4 entries: 13146
   number of buckets with 5 entries: 2308
   number of buckets with 6 entries: 266
   number of buckets with 7 entries: 30
   number of buckets with 8 entries: 2
   number of buckets with 9 entries: 0
   number of buckets with 10 or more entries: 0
   average search distance for entry: 1.5

Feel free to reproduce these figures yourself.

> Please don't interpret my comments as advocacy for Bob's lookup3 hash.
> I have no preference for any particular hash function.  I do have
> concerns about changing a hash function that has worked quite well for
> 20 years, without sufficient consideration and experimentation to
> justify that change.

The figures above show that the FNV algorithm does *better* at
distributing integers over the hash table. On dictionary words, it does
slightly better (but only very slightly to be honest; it's only really a
hair's-width of difference). Better distribution properties mean faster
lookups, of course.

>> The changes I've made are purely internal to Tcl. No public interface is
>> impacted at all.
>>
> I don't believe that fact is at all relevant to the question of whether
> the change requires a TIP.

I'd say that the biggest problem left in the hash table implementation
following the switch is that we're using hash bucket array sizes that
are powers of 2. That's cheap, but discards a lot of information from
the higher-order bits of the hash value. (OTOH, mod is fairly expensive
so it would be nice to avoid it.)

Donal.

Re: [TCLCORE] Upgrade of Tcl's String Hash Algorithm

[Donal K. F. <don...@ma...>]

On 08/02/2010 19:56, Joe English wrote:
> Eric Melski wrote:
>> data to support that conclusion?  What are the specific scenarios in
>> which the existing hash is inadequate?
>
> One area that I'm aware of: Tcl's traditional hash function
> is more prone to collisions (and it's trivially easy to generate
> an arbitrary number of them).

That was what prompted me to act. It's been nagging at the back of my
mind for a good few years now too, ever since the thread that started
with http://groups.google.co.uk/group/comp.lang.tcl/msg/5d6888cd479cf583
way back in 2003. It doesn't *always* take me 6.5 years to act on
something. (NB: goal is to make sure that it is unlikely that we end up
in an pathological case, which isn't quite the same thing as ensuring a
minimal chain length is obtained in the normal case.)

> The FNV hash is one of three (that I'm aware of) that AFAIK
> are considered among the state-of-the-art.  (The other two
> I know of are Jenkins' hash, which you mentioned, and
> MurmurHash.)

Also, of the three you've just mentioned, only FNV is a simple slot-in
replacement for the old code. In particular, it's easy to compute over C
strings because it is strictly byte-at-a-time. Both Jenkins's and
MurmurHash really want to know the length of the data being hashed first
(which lets them be a bit faster, which in turn compensates for the fact
that they are much more complex; byte-at-a-time forms for these would be
excessively complex).

The other key point is that I've explicitly rejected taking any steps
that involved a change to *any* public structure (i.e., Tcl_HashTable
and Tcl_HashEntry; there are macros that point into these so we can't
change things around radically). The only thing that changed was the
hash algorithm. (We could do better if we had more freedom to change
things, but we don't. Breaking either binary compatibility or source
compatibility is not an option.)

Donal.

Re: [TCLCORE] Upgrade of Tcl's String Hash Algorithm

[Joe E. <jen...@fl...>]

Eric Melski wrote:
> Donal K. Fellows wrote:
> > Hi everyone
> > This is just a short note to let everyone know that I've just upgraded
> > Tcl 8.6's string (and Tcl_Obj) hash algorithm.
>
> I'm not much involved in the development of Tcl anymore, but shouldn't a
> change of this magnitude require a TIP?


I do not believe this requires a TIP.

This is not really that big of a change.  The only user-visible
change involves the order of results returned by [array get]
and others, which have always been explicitly specified to be
indeterminate.

> [...]
> data to support that conclusion?  What are the specific scenarios in
> which the existing hash is inadequate?

One area that I'm aware of: Tcl's traditional hash function
is more prone to collisions (and it's trivially easy to generate
an arbitrary number of them).

The FNV hash is one of three (that I'm aware of) that AFAIK
are considered among the state-of-the-art.  (The other two
I know of are Jenkins' hash, which you mentioned, and
MurmurHash.)


--Joe English