\documentclass[]{article}
\usepackage{amsmath,graphicx,supertabular,hyperref,tabularx,ifthen}
\title{TIP \#138: New TCL\_HASH\_KEY\_SYSTEM\_HASH option for Tcl hash tables}
\date{May 29, 2003}
\author{Kevin Kenny, Joe Mistachkin}
\urlstyle{sf}
\setlength{\parskip}{1ex}
\setlength{\parindent}{0pt}
\def\tipversion$#1${\texttt{\$#1\$}}
\def\tiplangle#1{\ensuremath{<}}
\def\tiprangle#1{\ensuremath{>}}
\def\tipbar#1{\ensuremath{|}}
\def\tipmail#1#2{\(\langle\){\small\expandafter\url{#1@#2}}\(\rangle\)}
\ifx\pdfoutput\undefined
\newcommand{\tipimage}[2]{\typeout{Make sure you download #1.eps}\ifthenelse{\lengthtest{0.8\textwidth>#2}\and\lengthtest{0pt<#2}}{\includegraphics{#1.eps}}{\includegraphics[width=0.8\textwidth]{#1.eps}}}
\newcommand{\tipxref}[1]{}
\newcommand{\tipxrefend}{}
\else
\newcommand{\tipimage}[2]{\typeout{Make sure you create #1.pdf}\ifthenelse{\lengthtest{0.8\textwidth>#2}\and\lengthtest{0pt<#2}}{\includegraphics{#1.pdf}}{\includegraphics[width=0.8\textwidth]{#1.pdf}}}
\pdfcatalog{/PageMode /UseOutlines}
\newcommand{\tipxref}[1]{\pdfannotlink attr {/C [0.5 0.5 1.0] /Border [0 0 1]} goto name {#1}}
\newcommand{\tipxrefend}{\pdfendlink}
\fi
\newenvironment{tipabstract}{\begin{abstract}}{\end{abstract}}
\begin{document}\maketitle
\begin{center}\begin{tabularx}{\linewidth}{|r@{: }X|}\hline
\textbf{TIP \#138}&\textbf{New TCL\_HASH\_KEY\_SYSTEM\_HASH option for Tcl hash tables}\\\hline
Author&

Kevin Kenny \tipmail{kennykb}{acm.org}
\par
Joe Mistachkin \tipmail{joe}{mistachkin.com}
\\
Created&Thursday, \(\text{29}^{\text{th}}\) May 2003\\
Type&Project\\
Tcl Version&\(8.5\)\\
State&Final\\
Vote&Done\\
Version&\tipversion$Revision: 1.5 $\\
Keywords&thread specific data, hash table, memory allocation\\
Post History&\\
\hline\end{tabularx}\end{center}
\thispagestyle{empty}\pagestyle{empty}
\begin{tipabstract}

This TIP proposes a new flag in the Tcl hash table API in support of a proposed rework of thread-specific data management.
\end{tipabstract}
\tableofcontents\setcounter{page}{0}\clearpage\pagestyle{plain}

\section{Introduction}

The Tcl hash table constructor, \textit{Tcl\_InitCustomHashTable}, provides a reasonably flexible means of creating a hash table that is managed by the application. It allows for custom procedures to calculate hash values for keys, to compare keys for equality, and to allocate and free hash table entries.

It always, however, allocates the hash table itself by means of \textit{ckalloc} and \textit{ckfree}. This use of Tcl's main allocator is normally not a problem, but a recent application of custom hash tables has exposed the need, from time to time, of using the system allocator (\textit{TclpSysAlloc} and \textit{TclpSysFree}) directly.

The motivating problem is that thread-specific data on certain versions of Windows is limited to only a small number of blocks per process (64 on at least one version). The proposed fix, which Joe Mistachkin is pursuing, involves replacing the system calls for managing thread-local storage with calls that manage the thread-specific data blocks in a per-thread hash table.

Reviewing and testing the change revealed an unfortunate circular dependency. A call to \textit{Tcl\_InitCustomHashTable} would attempt to allocate the array of hash buckets by a call to \textit{ckalloc} --- which translates to \textit{TclpAlloc}. On a threaded build, the first thing done in this routine is to retrieve the allocation cache via \textit{TclpGetAllocCache.} This in turn, once we avoid the use of \textit{TlsAlloc}, winds up trying to create a thread-specific data block to hold the allocation cache. The new thread-specific data manager in turn must allocate a hash table for the thread-specific data blocks. The outcome is endless recursion.

The fix for the problem is simple --- have either the allocation cache, the thread-specific data hash, or both, allocated off the system heap rather than the thread-specific allocation cache. Unfortunately, \textit{Tcl\_InitCustomHashTable} provides no way to accomplish this.

\section{Proposal}

The \textit{flags} word in the \textit{Tcl\_HashKeyType} data structure shall be augmented with an additional value, \textit{TCL\_HASH\_KEY\_SYSTEM\_HASH}. If this bit is set in the structure passed to \textit{Tcl\_InitCustomHashTable}, then all memory allocated internally to manage the hash keys shall be obtained via direct calls to \textit{TclpSysAlloc}, \textit{TclpSysRealloc}, and \textit{TclpSysFree} rather than \textit{Tcl\_Alloc}, \textit{Tcl\_Realloc} and \textit{Tcl\_Free.}

\section{Alternatives}

The authors considered and rejected the alternative of advancing \textit{TCL\_HASH\_KEY\_TYPE\_VERSION} and defining in the structure three new function pointers to allocate, reallocate, and free memory blocks. The additional complexity (and associated performance degradation) associated with dealing with two structure versions appeared to be unnecessary; it is difficult to imagine a situation where any allocator other than the system allocator or Tcl's own will be desired for the 'buckets' array, which varies widely in size. Custom small-block allocators make much more sense for the hash values than they do for the table of hash buckets.

\section{Implementation Notes}

An implementation of this change is available from the SourceForge patch manager as item 731356. It is part of a larger overhaul of the thread-specific data manager.

\section{Copyright}

This document is placed in the public domain.

\section{Colophon}

\textit{TIP AutoGenerator --- written by Donal K. Fellows}
\end{document}
