CL has an array-total-size-limit (as well as some other limits
on arrays). Indeed, the total size limit is allowed to be
astonishingly small (1024). But I can't find any limits on
hash tables. Does this mean that they, like lists, can be
arbitrarily large?
In any case, are there implementations in which it would be a
bad idea, in practice, to let a hash table grow very large
(say 10s of 1000s of elements)?
-- jd
In article <····@skye.ed.ac.uk> ····@aiai.ed.ac.uk (Jeff Dalton) writes:
>CL has an array-total-size-limit (as well as some other limits
>on arrays). Indeed, the total size limit is allowed to be
>astonishingly small (1024). But I can't find any limits on
>hash tables. Does this mean that they, like lists, can be
>arbitrarily large?
My guess is that the problem is that it's difficult to characterize hash
table limits, and it's relatively easy to implement hash tables without
arbitrary limits. Array accessing is generally assumed to be very
efficient, and this usually implies making use of the hardware's built-in
indexing mechanism, which usually have index register size limits. Hash
tables are expected to be much faster than search tables, but not
necessarily so fast that such concessions to hardware limits must be made.
There are well-known implementation techniques that satisfy these
requirements (e.g. implementing hash buckets as references to association
lists or secondary hash arrays).
>In any case, are there implementations in which it would be a
>bad idea, in practice, to let a hash table grow very large
>(say 10s of 1000s of elements)?
I can imagine that there are, but I don't know of any offhand. I would
definitely classify such an implementation as a "toy" and not worry too
much about it. Since packages are often implemented as hash tables, and
much of this code can be used for the user-visible hash tables,
implementors are usually motivated to implement hash tables well.
--
Barry Margolin
System Manager, Thinking Machines Corp.
······@think.com {uunet,harvard}!think!barmar
In article <············@early-bird.think.com> ······@think.com (Barry Margolin) writes:
>In article <····@skye.ed.ac.uk> ····@aiai.ed.ac.uk (Jeff Dalton) writes:
>>CL has an array-total-size-limit (as well as some other limits
>>on arrays). Indeed, the total size limit is allowed to be
>>astonishingly small (1024). But I can't find any limits on
>>hash tables. Does this mean that they, like lists, can be
>>arbitrarily large?
>
>My guess is that the problem is that it's difficult to characterize hash
>table limits, and it's relatively easy to implement hash tables without
>arbitrary limits. Array accessing is generally assumed to be very
>efficient, and this usually implies making use of the hardware's built-in
>indexing mechanism, which usually have index register size limits.
You mean there are still computers out there that we care about
and that have index registers that aren't big enough for a full
pointer? Ok, there are some segmented machines... but then all
pointer deref will be slow (in the "huge" model).
>>In any case, are there implementations in which it would be a
>>bad idea, in practice, to let a hash table grow very large
>>(say 10s of 1000s of elements)?
>
>I can imagine that there are, but I don't know of any offhand. I would
>definitely classify such an implementation as a "toy" and not worry too
>much about it. Since packages are often implemented as hash tables, and
>much of this code can be used for the user-visible hash tables,
>implementors are usually motivated to implement hash tables well.
Excellent.
-- jeff
In article <····@skye.ed.ac.uk> ····@aiai.ed.ac.uk (Jeff Dalton) writes:
>You mean there are still computers out there that we care about
>and that have index registers that aren't big enough for a full
>pointer? Ok, there are some segmented machines... but then all
>pointer deref will be slow (in the "huge" model).
I don't know the exact reason for it, but Lucid CL/SPARC's
ARRAY-TOTAL-SIZE-LIMIT and ARRAY-DIMENSION-LIMIT are only 2^24-1.
--
Barry Margolin
System Manager, Thinking Machines Corp.
······@think.com {uunet,harvard}!think!barmar