[LISPWORKS][Common Lisp HyperSpec (TM)] [Previous][Up][Next]


Issue HASH-TABLE-REHASH-SIZE-INTEGER Writeup

Issue:		HASH-TABLE-REHASH-SIZE-INTEGER

Reference: Draft 8.81, p.19-3

Category: CLARIFICATION/CHANGE

Edit History: Version 1, 06/16/91, Kim Barrett

Version 2, 09/26/91, Steve Haflich, add Franz current practice

Version 3, 01/10/91, Steve Haflich, Lucid & Chestnut

current practice

Problem Description:

The semantics for the :REHASH-SIZE argument to MAKE-HASH-TABLE are unclear.

The description in the draft says it can be

"an integer greater than zero, which is the number of entries to add, or it

can be a floating-point number greater than 1, which is the ratio of the

new size to the old size."

When the :REHASH-SIZE argument is an integer, it is unclear whether it is

expected to be scaled as the size is increased or if it is supposed to

indicate an expected additional number of entries to add.

At issue is whether a programmer can use the type of value provided for the

:REHASH-SIZE argument to give the implementation a hint as to the expected

growth rate for the table, with an integer indicating an additive growth rate

and a float indicating a multiplicative growth rate.

Proposal:

Specify that if the :REHASH-SIZE argument is an integer then the

implementation may assume that the expected growth rate for the table is

additive, and that if the argument is a float then it may assume that the

expected growth rate is multiplicative.

Clarify that the value of the :REHASH-SIZE argument does not constrain the

implementation to use any particular method for computing the new size when

the hash table is enlarged. The actual method for computing the new size is

implementation dependent and the :REHASH-SIZE argument only provides hints

from the programmer to the implementation.

Editorial Impact:

An isolated change to MAKE-HASH-TABLE and HASH-TABLE-REHASH-SIZE.

Rationale:

Provides a means for the programmer to reliably provide to the implementor a

particular piece of information about the programmer's intent, without

constraining the implementor to any particular implementation technique.

Current Practice:

Symbolics Genera and IIM appear to use the :SIZE and integral :REHASH-SIZE

arguments to produce a ratio which is then used as the effective rehash size

in the same way as if a float with the same value had been specified for the

:REHASH-SIZE.

Lucid, Franz, and Chestnut conform to the interpretation of

:REHASH-SIZE here suggested.

Discussion:

Pitman:

Only the application programmer knows whether new elements are expected to

arrive in an additive or multiplicative way. All the implementation knows at

the time growth needs to occur is that there isn't room. It can't tell how

many extra elements are coming. And just because the computation on the size

is allowed to be slightly fuzzy, that doesn't mean it doesn't matter whether

the input to that computation should be allowed to be fuzzy.

Control of memory growth is a frequently cited reason for preferring C over

Lisp. In some places, fixing the problems that underlie this is virtually a

research topic because no one can even figure out what they'd want to write

down in order to advise the program about what to do. Controlled growth as

in vector-push-extend or hash-table-rehash-size is not in that camp. To the

extent that we have a linguistic facilities begging for the opportunity to be

properly expressive, I see no reason to be vague--even if we're going to let

implementations do something a little different than what was asked for, we

should still define the language in such a way that the implementation at

least knows what was asked for. Both of the possible values (integers and

floats) are potentially meaningful in distinct ways, and trivial to

implement, so why blur their intent?


[Starting Points][Contents][Index][Symbols][Glossary][Issues]
Copyright 1996-2005, LispWorks Ltd. All rights reserved.