Check-in [063b7588c9]

Login
Bounty program for improvements to Tcl and certain Tcl packages.
Tcl 2019 Conference, Houston/TX, US, Nov 4-8
Send your abstracts to tclconference@googlegroups.com
or submit via the online form by Sep 9.

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Added TIP 534
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256:063b7588c96b272119030e3b9a4549464b64cd566b385e687eb42fed5aa24613
User & Date: dkf 2019-03-02 16:21:49
Context
2019-03-04
00:10
TIP 527 accepted check-in: 2bf9a5745c user: kennykb tags: trunk
2019-03-02
16:21
Added TIP 534 check-in: 063b7588c9 user: dkf tags: trunk
2019-02-20
13:29
CFV for 527 by KBK check-in: b1a11fd5c7 user: dkf tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to index.json.

1

2
3
4
5
6
7
8
...
530
531
532
533
534
535
536
537
538
{"tip": {

	"533":{"url":"./tip/533.md","keywords":"Tk, menubutton","":"","[menu man page](https":"//www.tcl.tk/man/tcl/TkCmd/menu.htm).","state":"Final","type":"Project","tk-branch":"bug-70e531918e","author":["Marc Culler"],"three arguments":"two coordinates and an index.  That function uses the","[70e531918e](https":"//core.tcl-lang.org/tk/tktview/70e531918e6d99cbdd8b527386fec15872c64216).","created":"13-Jan-2019","by calling <b>":":tk::PostOverPoint</b> which, like the proposed extension, accepts","a method <b>[nsmenu popupmenupositioningitem":"atLocation:inView]</b> which draws the","title":"# TIP 533: Extension of the menu post command.","the [bug-70e531918e](https":"//core.tcl-lang.org/tk/timeline?r=bug-70e531918e)","post-history":"","vote":"Done","tcl-version":"8.6","is-jest":false},
	"532":{"url":"./tip/532.md","moreover the following issues have been solved":"","keywords":"Tk, bind, event, event loop","":"","[generic/tkbind.c](http":"//core.tcl.tk/tk/artifact/e41f45f7f6ac3447?ln=3287-3307).","this has been observed in applications [scid](http":"//scid.sourceforge.net), and","state":"Draft","branch [bug6e8afe516d-87](https":"//core.tcl-lang.org/tk/timeline?r=bug6e8afe516d-87)","type":"Project","tk-branch":"bug6e8afe516d","issue (1)":"Legacy implementation is computing the time difference of nth click with first click,","says (<code>man bind</code>)":"","author":["Gregor Cramer <gcramer@sourceforge.net>"],"(same with applications [scid](http":"//scid.sourceforge.net), and","[bind-33.13](https":"//core.tcl-lang.org/tk/artifact/6377cb0d762b7261?ln=6550-6566).","5. legacy implementation cannot handle homogeneous equal sequences properly, see this script":"","branch [bug6e8afe516d](https":"//core.tcl-lang.org/tk/timeline?r=bug6e8afe516d)","2. immediately after startup of application [scidb](http":"//scidb.sourceforge.net)","[bug6e8afe516d](https":"//core.tcl-lang.org/tk/timeline?r=bug6e8afe516d)","created":"09-Jan-2019","manual (<code>man bind</code>) says":"","[bind-32.2](https":"//core.tcl-lang.org/tk/artifact/6377cb0d762b7261?ln=6123-6143)).","title":"# TIP 532: Re-implementation of event loop processing.","how to choose the most specific binding, has to be changed":"","4. see following code":"","can be expressed in a different way":"","[bind-32.4](https":"//core.tcl-lang.org/tk/artifact/6377cb0d762b7261?ln=6158-6171).","this problem occurs often in application [scidb](http":"//scidb.sourceforge.net),","post-history":"","[bind-32.6](https":"//core.tcl-lang.org/tk/artifact/6377cb0d762b7261?ln=6172-6191).","vote":"Pending","tcl-version":"8.6 and 8.7","[severe bugs in binding (tkbind.c)](https":"//core.tcl-lang.org/tk/tktview/6e8afe516df85f6213f436ef7c2fab2ec2d11c76).","[scid vs pc](http":"//scidvspc.sourceforge.net).","the following problems, caused by event ring overflow, have been solved":"","is-jest":false},
	"531":{"url":"./tip/531.md","":"","keywords":"Tcl, stubs","created":"14-Dec-2018","post-history":"","state":"Draft","tcl-version":"8.7","vote":"Pending","type":"Project","title":"# TIP 531: Static Tcl Interpreter Creation Function","/usr/local/include/tcl8.6/tcldecls.h":"#define Tcl_CreateInterp \\","author":["Shannon Noe <shannon.noe@flightaware.com>"],"is-jest":false},
	"530":{"url":"./tip/530.md","tcl-ticket":"a09031e288","created":"13-Dec-2018","post-history":"","state":"Draft","tcl-version":"8.6, 8.7","vote":"Pending","type":"Project","title":"# TIP 530: Control over performance impact of TIP 280","author":["Leon Manukyan <leon.manukyan@gmail.com>"],"is-jest":false},
	"529":{"url":"./tip/529.md","keywords":"Tk, image","created":"07-Dec-2018","state":"Draft","tk-branch":"tip-529-image-metadata","tcl-version":"8.7","vote":"Pending","type":"Project","title":"# TIP 529: Add metadata dict property to tk photo image","author":["Harald Oehlmann <oehhar@users.sourceforge.net>"],"is-jest":false},
	"528":{"url":"./tip/528.md","created":"05-Dec-2018","post-history":"","state":"Draft","tk-branch":"offsetof","tcl-version":"8.7","vote":"Pending","type":"Project","title":"# TIP 528: Deprecate Tk_Offset()","author":["Jan Nijtmans <jan.nijtmans@gmail.com>"],"is-jest":false},
	"527":{"url":"./tip/527.md","created":"26-Nov-2018","post-history":"","state":"Draft","tcl-branch":"sebres-8-6-timerate","tcl-version":"8.7","vote":"In progress","type":"Project","title":"# TIP 527: New measurement facilities in TCL: New command timerate.","discussions-to":"news:comp.lang.tcl","author":["Sergey G. Brester <sebres@users.sourceforge.net>"],"is-jest":false},
................................................................................
	"5":{"url":"./tip/5.md","created":"17-Oct-2000","post-history":"","state":"Final","vote":"Done","tcl-version":"8.4","type":"Project","title":"# TIP 5: Make TkClassProcs and TkSetClassProcs Public and Extensible","author":["Eric Melski <ericm@ajubasolutions.com>"],"is-jest":false},
	"4":{"url":"./tip/4.md","created":"26-Oct-2000","post-history":"","state":"Draft","vote":"Pending","type":"Informative","title":"# TIP 4: Tcl Release and Distribution Philosophy","discussions-to":"news:comp.lang.tcl","author":["Brent Welch <welch@acm.org>","Donal K. Fellows <fellowsd@cs.man.ac.uk>","Larry W. Virden <lvirden@cas.org>","Larry W. Virden <lvirden@yahoo.com>"],"is-jest":false},
	"3":{"url":"./tip/3.md","created":"14-Sep-2000","post-history":"","state":"Accepted","vote":"Done","type":"Process","title":"# TIP 3: TIP Format","author":["Andreas Kupries <a.kupries@westend.com>","Donal K. Fellows <fellowsd@cs.man.ac.uk>"],"is-jest":false},
	"2":{"url":"./tip/2.md","created":"12-Sep-2000","post-history":"","state":"Draft","vote":"Pending","type":"Process","title":"# TIP 2: TIP Guidelines","author":["Andreas Kupries <a.kupries@westend.com>","Donal K. Fellows <fellowsd@cs.man.ac.uk>","Don Porter <dgp@users.sourceforge.net>","Mo DeJong <no@spam.com>","Larry W. Virden <lvirden@yahoo.com>","Kevin Kenny <kennykb@acm.org>"],"is-jest":false},
	"1":{"url":"./tip/1.md","created":"14-Sep-2000","post-history":"","state":"Active","vote":"No voting","type":"Informational","title":"# TIP 1: TIP Index","author":["TIP Editor <donal.fellows@cs.man.ac.uk>"],"is-jest":false},
	"0":{"url":"./tip/0.md","created":"11-Dec-2000","post-history":"","state":"Final","vote":"Done","type":"Process","title":"# TIP 0: Tcl Core Team Basic Rules","author":["John Ousterhout <ouster@pacbell.net>"],"is-jest":false},
	"@min": 0,
	"@max": 533
}, "@timestamp": 1550669332}

>







 







|
|
1
2
3
4
5
6
7
8
9
...
531
532
533
534
535
536
537
538
539
{"tip": {
	"534":{"url":"./tip/534.md","keywords":"Tcl","created":"02-March-2019","post-history":"","state":"Draft","tcl-branch":"dkf-experimental-fast-number-hash","tcl-version":"8.7","vote":"Pending","type":"Project","title":"# TIP 534: Faster Hashing of Small Integers","author":["Donal K. Fellows <donal.k.fellows@manchester.ac.uk>"],"is-jest":false},
	"533":{"url":"./tip/533.md","keywords":"Tk, menubutton","":"","[menu man page](https":"//www.tcl.tk/man/tcl/TkCmd/menu.htm).","state":"Final","type":"Project","tk-branch":"bug-70e531918e","author":["Marc Culler"],"three arguments":"two coordinates and an index.  That function uses the","[70e531918e](https":"//core.tcl-lang.org/tk/tktview/70e531918e6d99cbdd8b527386fec15872c64216).","created":"13-Jan-2019","by calling <b>":":tk::PostOverPoint</b> which, like the proposed extension, accepts","a method <b>[nsmenu popupmenupositioningitem":"atLocation:inView]</b> which draws the","title":"# TIP 533: Extension of the menu post command.","the [bug-70e531918e](https":"//core.tcl-lang.org/tk/timeline?r=bug-70e531918e)","post-history":"","vote":"Done","tcl-version":"8.6","is-jest":false},
	"532":{"url":"./tip/532.md","moreover the following issues have been solved":"","keywords":"Tk, bind, event, event loop","":"","[generic/tkbind.c](http":"//core.tcl.tk/tk/artifact/e41f45f7f6ac3447?ln=3287-3307).","this has been observed in applications [scid](http":"//scid.sourceforge.net), and","state":"Draft","branch [bug6e8afe516d-87](https":"//core.tcl-lang.org/tk/timeline?r=bug6e8afe516d-87)","type":"Project","tk-branch":"bug6e8afe516d","issue (1)":"Legacy implementation is computing the time difference of nth click with first click,","says (<code>man bind</code>)":"","author":["Gregor Cramer <gcramer@sourceforge.net>"],"(same with applications [scid](http":"//scid.sourceforge.net), and","[bind-33.13](https":"//core.tcl-lang.org/tk/artifact/6377cb0d762b7261?ln=6550-6566).","5. legacy implementation cannot handle homogeneous equal sequences properly, see this script":"","branch [bug6e8afe516d](https":"//core.tcl-lang.org/tk/timeline?r=bug6e8afe516d)","2. immediately after startup of application [scidb](http":"//scidb.sourceforge.net)","[bug6e8afe516d](https":"//core.tcl-lang.org/tk/timeline?r=bug6e8afe516d)","created":"09-Jan-2019","manual (<code>man bind</code>) says":"","[bind-32.2](https":"//core.tcl-lang.org/tk/artifact/6377cb0d762b7261?ln=6123-6143)).","title":"# TIP 532: Re-implementation of event loop processing.","how to choose the most specific binding, has to be changed":"","4. see following code":"","can be expressed in a different way":"","[bind-32.4](https":"//core.tcl-lang.org/tk/artifact/6377cb0d762b7261?ln=6158-6171).","this problem occurs often in application [scidb](http":"//scidb.sourceforge.net),","post-history":"","[bind-32.6](https":"//core.tcl-lang.org/tk/artifact/6377cb0d762b7261?ln=6172-6191).","vote":"Pending","tcl-version":"8.6 and 8.7","[severe bugs in binding (tkbind.c)](https":"//core.tcl-lang.org/tk/tktview/6e8afe516df85f6213f436ef7c2fab2ec2d11c76).","[scid vs pc](http":"//scidvspc.sourceforge.net).","the following problems, caused by event ring overflow, have been solved":"","is-jest":false},
	"531":{"url":"./tip/531.md","":"","keywords":"Tcl, stubs","created":"14-Dec-2018","post-history":"","state":"Draft","tcl-version":"8.7","vote":"Pending","type":"Project","title":"# TIP 531: Static Tcl Interpreter Creation Function","/usr/local/include/tcl8.6/tcldecls.h":"#define Tcl_CreateInterp \\","author":["Shannon Noe <shannon.noe@flightaware.com>"],"is-jest":false},
	"530":{"url":"./tip/530.md","tcl-ticket":"a09031e288","created":"13-Dec-2018","post-history":"","state":"Draft","tcl-version":"8.6, 8.7","vote":"Pending","type":"Project","title":"# TIP 530: Control over performance impact of TIP 280","author":["Leon Manukyan <leon.manukyan@gmail.com>"],"is-jest":false},
	"529":{"url":"./tip/529.md","keywords":"Tk, image","created":"07-Dec-2018","state":"Draft","tk-branch":"tip-529-image-metadata","tcl-version":"8.7","vote":"Pending","type":"Project","title":"# TIP 529: Add metadata dict property to tk photo image","author":["Harald Oehlmann <oehhar@users.sourceforge.net>"],"is-jest":false},
	"528":{"url":"./tip/528.md","created":"05-Dec-2018","post-history":"","state":"Draft","tk-branch":"offsetof","tcl-version":"8.7","vote":"Pending","type":"Project","title":"# TIP 528: Deprecate Tk_Offset()","author":["Jan Nijtmans <jan.nijtmans@gmail.com>"],"is-jest":false},
	"527":{"url":"./tip/527.md","created":"26-Nov-2018","post-history":"","state":"Draft","tcl-branch":"sebres-8-6-timerate","tcl-version":"8.7","vote":"In progress","type":"Project","title":"# TIP 527: New measurement facilities in TCL: New command timerate.","discussions-to":"news:comp.lang.tcl","author":["Sergey G. Brester <sebres@users.sourceforge.net>"],"is-jest":false},
................................................................................
	"5":{"url":"./tip/5.md","created":"17-Oct-2000","post-history":"","state":"Final","vote":"Done","tcl-version":"8.4","type":"Project","title":"# TIP 5: Make TkClassProcs and TkSetClassProcs Public and Extensible","author":["Eric Melski <ericm@ajubasolutions.com>"],"is-jest":false},
	"4":{"url":"./tip/4.md","created":"26-Oct-2000","post-history":"","state":"Draft","vote":"Pending","type":"Informative","title":"# TIP 4: Tcl Release and Distribution Philosophy","discussions-to":"news:comp.lang.tcl","author":["Brent Welch <welch@acm.org>","Donal K. Fellows <fellowsd@cs.man.ac.uk>","Larry W. Virden <lvirden@cas.org>","Larry W. Virden <lvirden@yahoo.com>"],"is-jest":false},
	"3":{"url":"./tip/3.md","created":"14-Sep-2000","post-history":"","state":"Accepted","vote":"Done","type":"Process","title":"# TIP 3: TIP Format","author":["Andreas Kupries <a.kupries@westend.com>","Donal K. Fellows <fellowsd@cs.man.ac.uk>"],"is-jest":false},
	"2":{"url":"./tip/2.md","created":"12-Sep-2000","post-history":"","state":"Draft","vote":"Pending","type":"Process","title":"# TIP 2: TIP Guidelines","author":["Andreas Kupries <a.kupries@westend.com>","Donal K. Fellows <fellowsd@cs.man.ac.uk>","Don Porter <dgp@users.sourceforge.net>","Mo DeJong <no@spam.com>","Larry W. Virden <lvirden@yahoo.com>","Kevin Kenny <kennykb@acm.org>"],"is-jest":false},
	"1":{"url":"./tip/1.md","created":"14-Sep-2000","post-history":"","state":"Active","vote":"No voting","type":"Informational","title":"# TIP 1: TIP Index","author":["TIP Editor <donal.fellows@cs.man.ac.uk>"],"is-jest":false},
	"0":{"url":"./tip/0.md","created":"11-Dec-2000","post-history":"","state":"Final","vote":"Done","type":"Process","title":"# TIP 0: Tcl Core Team Basic Rules","author":["John Ousterhout <ouster@pacbell.net>"],"is-jest":false},
	"@min": 0,
	"@max": 534
}, "@timestamp": 1551543693}

Changes to index.md.

116
117
118
119
120
121
122








123
124
125
126
127
128
129
<th>Type</th>
<th>Tcl Version</th>
<th>Status</th>
<th>Title</th>
<th>Impl.</th>
</tr></thead><tbody>









<tr class='project projectfinal projectfinal86 project86'>
<td valign='top'><a href='./tip/533.md'>533</a></td>
<td valign='top'>Project</td>
<td valign='top'>8.6</td>
<td valign='top'>Final</td>
<td valign='top'># TIP 533: Extension of the menu post command.</td>
<td valign='top'><a href='/tk/timeline?r=bug-70e531918e'>Link</a></td>







>
>
>
>
>
>
>
>







116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
<th>Type</th>
<th>Tcl Version</th>
<th>Status</th>
<th>Title</th>
<th>Impl.</th>
</tr></thead><tbody>

<tr class='project projectdraft projectdraft87 project87'>
<td valign='top'><a href='./tip/534.md'>534</a></td>
<td valign='top'>Project</td>
<td valign='top'>8.7</td>
<td valign='top'>Draft</td>
<td valign='top'># TIP 534: Faster Hashing of Small Integers</td>
<td valign='top'><a href='/tcl/timeline?r=dkf-experimental-fast-number-hash'>Link</a></td>
</tr>
<tr class='project projectfinal projectfinal86 project86'>
<td valign='top'><a href='./tip/533.md'>533</a></td>
<td valign='top'>Project</td>
<td valign='top'>8.6</td>
<td valign='top'>Final</td>
<td valign='top'># TIP 533: Extension of the menu post command.</td>
<td valign='top'><a href='/tk/timeline?r=bug-70e531918e'>Link</a></td>

Added tip/534.md.



















































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# TIP 534: Faster Hashing of Small Integers
	Author:         Donal K. Fellows <donal.k.fellows@manchester.ac.uk>
	State:          Draft
	Type:           Project
	Vote:           Pending
	Created:        02-March-2019
	Post-History:   
	Keywords:       Tcl
	Tcl-Version:	8.7
	Tcl-Branch:     dkf-experimental-fast-number-hash
-----

# Abstract

This TIP proposes to change the Tcl hashing algorithm _slightly_ to allow integers to be used as hash keys without computing their string representation.

# Rationale

Tcl uses hashes of values in quite a few places. The ones that this TIP is concerned with are where we have associative arrays and dictionaries (where keys can be arbitrary `Tcl_Obj*` values). Sometimes in user code, we want to use “small” integers as keys (where “small” means that the value fits in a native 64-bit integer); this is highly useful for some algorithms where we have things indexed by number but don't have a dense collection of indices.

Right now, that means we have to calculate the string representation of that integer before we can hash it, a non-trivial cost (in both time and space) when many of these keys are in use. However, it is possible to create a hash function that can be computed from an integer in much less cost, so accelerating all code which uses normal integer keys in associative arrays and dictionaries.

# Specification

Because it is critical that the hashcode of a value be the same whether it is computed from the string version of the key or from the integer directly, we need to alter the computing of all hashcodes from `Tcl_Obj *` values. Fortunately, the adjustment is actually very trivial when applied to strings: we simply use the bytes of the string as we do now, but in reverse order. By doing this, we can avoid calculating the string representation for an integer and replace it instead with a series of calculations mod 10 that yield the digits of the number, which are trivial to map to the character representations they would have had had the string been created. This turns out to be an overall win in normal use.

Obviously, there's also a need to be a bit careful with the equality comparison used when checking the entries in the hash chain, but that is not semantics-altering. Indeed, the only way in which this alters the visible semantics of Tcl is in changing the iteration order of associative arrays, and other users of `Tcl_InitObjHashTable()` (of which only `encoding names` and the method introspection capabilities of TclOO should be user exposed at all; neither of those have ever made any order guarantees). Dictionary ordering is entirely unaffected; that uses a separate mechanism.

Mixing integer keys and other value-type keys (or integers with string representations) in the same hash table may result in the benefits being lessened, but only at most back to our current behaviour and cost of operation.

Note that string representations, if present, _must_ take precedence because we currently require, for example, `255` and `0xFF` to be different keys. String representations maintain that behaviour; the second value cannot be an integer-without-string-representation in Tcl (because then it would be `255`, and also equivalent to the syntactically different `0xff`, `0o377`, ...).

# Implementation

See the `dkf-experimental-fast-number-hash` branch.

The additional cost to non-integer keys is exactly one extra comparison (of a pointer) against a constant. The additional cost to integer keys with a string representation is two extra comparisons (once to determine that they are integers and once to determine that they have a string representation). These are comparatively cheap tests.

# Copyright

This document has been placed in the public domain.