112 lines
6.9 KiB
HTML
112 lines
6.9 KiB
HTML
<!-- Common Lisp HyperSpec (TM), version 7.0 generated by Kent M. Pitman on Mon, 11-Apr-2005 2:31am EDT -->
|
|
<HTML>
|
|
<HEAD>
|
|
<TITLE>CLHS: Issue HASH-TABLE-REHASH-SIZE-INTEGER Writeup</TITLE>
|
|
<LINK HREF="../Data/clhs.css" REL="stylesheet" TYPE="text/css" />
|
|
<META HTTP-EQUIV="Author" CONTENT="Kent M. Pitman">
|
|
<META HTTP-EQUIV="Organization" CONTENT="LispWorks Ltd.">
|
|
<LINK REL=TOP HREF="../Front/index.htm">
|
|
<LINK REL=COPYRIGHT HREF="../Front/Help.htm#Legal">
|
|
<LINK REL=DISCLAIMER HREF="../Front/Help.htm#Disclaimer">
|
|
<LINK REL=PREV HREF="../Issues/iss188_w.htm">
|
|
<LINK REL=UP HREF="../Issues/iss189.htm">
|
|
<LINK REL=NEXT HREF="../Issues/iss190_w.htm">
|
|
</HEAD>
|
|
<BODY>
|
|
<H1><A REV=MADE HREF="http://www.lispworks.com/"><IMG WIDTH=80 HEIGHT=65 ALT="[LISPWORKS]" SRC="../Graphics/LWSmall.gif" ALIGN=Bottom></A><A REL=TOP HREF="../Front/index.htm"><IMG WIDTH=237 HEIGHT=65 ALT="[Common Lisp HyperSpec (TM)]" SRC="../Graphics/CLHS_Sm.gif" ALIGN=Bottom></A> <A REL=PREV HREF="../Issues/iss188_w.htm"><IMG WIDTH=40 HEIGHT=40 ALT="[Previous]" SRC="../Graphics/Prev.gif" ALIGN=Bottom></A><A REL=UP HREF="../Issues/iss189.htm"><IMG WIDTH=40 HEIGHT=40 ALT="[Up]" SRC="../Graphics/Up.gif" ALIGN=Bottom></A><A REL=NEXT HREF="../Issues/iss190_w.htm"><IMG WIDTH=40 HEIGHT=40 ALT="[Next]" SRC="../Graphics/Next.gif" ALIGN=Bottom></A></H1>
|
|
|
|
<HR>
|
|
|
|
|
|
|
|
<H2>Issue HASH-TABLE-REHASH-SIZE-INTEGER Writeup</H2>
|
|
|
|
<PRE><B>Issue:</B> <A HREF="iss189.htm">HASH-TABLE-REHASH-SIZE-INTEGER</A><P>
|
|
Reference: Draft 8.81, p.19-3<P>
|
|
<B>Category:</B> CLARIFICATION/CHANGE<P>
|
|
<B>Edit History:</B> Version 1, 06/16/91, Kim Barrett<P>
|
|
Version 2, 09/26/91, Steve Haflich, add Franz current practice<P>
|
|
Version 3, 01/10/91, Steve Haflich, Lucid & Chestnut<P>
|
|
current practice<P>
|
|
<P>
|
|
<B>Problem Description:<P>
|
|
</B><P>
|
|
The semantics for the :REHASH-SIZE argument to <A REL=DEFINITION HREF="../Body/f_mk_has.htm#make-hash-table"><B>MAKE-HASH-TABLE</B></A> are unclear.<P>
|
|
The description in the draft says it can be <P>
|
|
<P>
|
|
"an integer greater than zero, which is the number of entries to add, or it<P>
|
|
can be a floating-point number greater than 1, which is the ratio of the<P>
|
|
new size to the old size."<P>
|
|
<P>
|
|
When the :REHASH-SIZE argument is an integer, it is unclear whether it is<P>
|
|
expected to be scaled as the size is increased or if it is supposed to<P>
|
|
indicate an expected additional number of entries to add.<P>
|
|
<P>
|
|
At issue is whether a programmer can use the type of value provided for the<P>
|
|
:REHASH-SIZE argument to give the implementation a hint as to the expected<P>
|
|
growth rate for the table, with an integer indicating an additive growth rate<P>
|
|
and a float indicating a multiplicative growth rate.<P>
|
|
<P>
|
|
<B>Proposal:<P>
|
|
</B><P>
|
|
Specify that if the :REHASH-SIZE argument is an integer then the<P>
|
|
implementation may assume that the expected growth rate for the table is<P>
|
|
additive, and that if the argument is a float then it may assume that the<P>
|
|
expected growth rate is multiplicative.<P>
|
|
<P>
|
|
Clarify that the value of the :REHASH-SIZE argument does not constrain the<P>
|
|
implementation to use any particular <A REL=DEFINITION HREF="../Body/t_method.htm#method"><B>method</B></A> for computing the new size when<P>
|
|
the hash table is enlarged. The actual <A REL=DEFINITION HREF="../Body/t_method.htm#method"><B>method</B></A> for computing the new size is<P>
|
|
implementation dependent and the :REHASH-SIZE argument only provides hints<P>
|
|
from the programmer to the implementation.<P>
|
|
<P>
|
|
<B>Editorial Impact:<P>
|
|
</B><P>
|
|
An isolated change to <A REL=DEFINITION HREF="../Body/f_mk_has.htm#make-hash-table"><B>MAKE-HASH-TABLE</B></A> and <A REL=DEFINITION HREF="../Body/f_hash_2.htm#hash-table-rehash-size"><B>HASH-TABLE-REHASH-SIZE</B></A>.<P>
|
|
<P>
|
|
<B>Rationale:<P>
|
|
</B><P>
|
|
Provides a means for the programmer to reliably <A REL=DEFINITION HREF="../Body/f_provid.htm#provide"><B>provide</B></A> to the implementor a<P>
|
|
particular piece of information about the programmer's intent, without<P>
|
|
constraining the implementor to any particular implementation technique.<P>
|
|
<P>
|
|
<B>Current Practice:<P>
|
|
</B><P>
|
|
Symbolics Genera and IIM appear to use the :SIZE and integral :REHASH-SIZE<P>
|
|
arguments to produce a ratio which is then used as the effective rehash size<P>
|
|
in the same way as if a float with the same value had been specified for the<P>
|
|
:REHASH-SIZE.<P>
|
|
<P>
|
|
Lucid, Franz, and Chestnut conform to the interpretation of<P>
|
|
:REHASH-SIZE here suggested.<P>
|
|
<P>
|
|
<B>Discussion:<P>
|
|
</B><P>
|
|
Pitman:<P>
|
|
Only the application programmer knows whether new elements are expected to<P>
|
|
arrive in an additive or multiplicative way. All the implementation knows at<P>
|
|
the time growth needs to occur is that there isn't room. It can't tell how<P>
|
|
many extra elements are coming. And just because the computation on the size<P>
|
|
is allowed to be slightly fuzzy, that doesn't mean it doesn't matter whether<P>
|
|
the input to that computation should be allowed to be fuzzy.<P>
|
|
<P>
|
|
Control of memory growth is a frequently cited reason for preferring C over<P>
|
|
Lisp. In some places, fixing the problems that underlie this is virtually a<P>
|
|
research topic because no one can even figure out what they'd want to write<P>
|
|
down in order to advise the program about what to do. Controlled growth as<P>
|
|
in <A REL=DEFINITION HREF="../Body/f_vec_ps.htm#vector-push-extend"><B>vector-push-extend</B></A> or <A REL=DEFINITION HREF="../Body/f_hash_2.htm#hash-table-rehash-size"><B>hash-table-rehash-size</B></A> is not in that camp. To the<P>
|
|
extent that we have a linguistic facilities begging for the opportunity to be<P>
|
|
properly expressive, I see no reason to be vague--even if we're going to let<P>
|
|
implementations do something a little different than what was asked for, we<P>
|
|
should still define the language in such a way that the implementation at<P>
|
|
least knows what was asked for. Both of the possible values (integers and<P>
|
|
floats) are potentially meaningful in distinct ways, and trivial to<P>
|
|
implement, so why blur their intent?<P>
|
|
</PRE>
|
|
<HR>
|
|
|
|
<A REL=NAVIGATOR HREF="../Front/StartPts.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Starting Points]" SRC="../Graphics/StartPts.gif" ALIGN=Bottom></A><A REL=TOC HREF="../Front/Contents.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Contents]" SRC="../Graphics/Contents.gif" ALIGN=Bottom></A><A REL=INDEX HREF="../Front/X_Master.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Index]" SRC="../Graphics/Index.gif" ALIGN=Bottom></A><A REL=INDEX HREF="../Front/X_Symbol.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Symbols]" SRC="../Graphics/Symbols.gif" ALIGN=Bottom></A><A REL=GLOSSARY HREF="../Body/26_a.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Glossary]" SRC="../Graphics/Glossary.gif" ALIGN=Bottom></A><A HREF="../Front/X3J13Iss.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Issues]" SRC="../Graphics/Issues.gif" ALIGN=Bottom></A><BR>
|
|
|
|
<A REL=COPYRIGHT HREF="../Front/Help.htm#Legal"><I>Copyright 1996-2005, LispWorks Ltd. All rights reserved.</I></A><P>
|
|
</BODY>
|
|
</HTML>
|