Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.postscript > #2051

Re: Sizing a dictionary

Show all headers | View raw

luser- -droog <mijoryx@yahoo.com> writes:

> On Tuesday, September 9, 2014 12:35:39 PM UTC-5, Scott Hemphill wrote:
>> jdaw1 <jdawiseman@gmail.com> writes:
>> 
>> > I'm now slightly puzzled. Assume that there are to be eight items in my dictionary. Would 8 dict automatically add enough space to keep the hash tables efficient? If so, 8 dict would be the right thing to do. Or do I have to guess the internal workings of the PS interpreter, and add something to the 8. In which it might be best to redefine dict to something like "{1.25 mul ceiling cvi dict} bind".
>> 
>> Yes, "8 dict" will automatically add enough space to keep the hash table
>> efficient.  However, "16 dict" would be slightly more time efficient
>> (collisions would be less likely) while becoming slightly less space
>> efficient.  For most purposes, it doesn't matter much.
>> 
>> Scott
>
> It appears ghostscript does not follow the same minimum size. And it exhibits
> a curious pattern of growth, settling into doubling after a few smaller 
> increments.
>
> $ gsnd
> GPL Ghostscript 9.10 (2013-08-30)
> Copyright (C) 2013 Artifex Software, Inc.  All rights reserved.
> This software comes with NO WARRANTY: see the file PUBLIC for details.
> GS>5 dict begin
> GS>currentdict maxlength
> GS<1>=
> 5
> GS>0 1 4 { dup def } for
> GS>currentdict maxlength =
> 5
> GS>5 5 def
> GS>currentdict maxlength =
> 15
> GS>6 1 15 { dup def } for
> GS>currentdict maxlength =
> 25
> GS>16 1 25 { dup def } for currentdict maxlength =
> 50
> GS>26 1 50 { dup def } for currentdict maxlength =
> 100
> GS>50 1 100 { dup def } for currentdict maxlength =
> 200
> GS>

This is a different thing.  When a dictionary fills up, it means the
original estimate was low, so you might want to allocate extra room for
growth.  The doubling strategy seems reasonable.  Also, "maxlength"
doesn't return the internal size of the dictionary, but the maximum size
that it is allowed to be before reallocation occurs.  In my LaserWriter
investigations, I inferred the internal size by studying the hash
function, to see in which order keys with different values showed up in
different size dictionaries.

Scott
-- 
Scott Hemphill	hemphill@alumni.caltech.edu
"This isn't flying.  This is falling, with style."  -- Buzz Lightyear

Back to comp.lang.postscript | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

Sizing a dictionary jdaw1 <jdawiseman@gmail.com> - 2014-09-03 03:57 -0700
  Re: Sizing a dictionary Scott Hemphill <hemphill@hemphills.net> - 2014-09-04 18:04 -0400
    Re: Sizing a dictionary luser- -droog <mijoryx@yahoo.com> - 2014-09-04 16:59 -0700
      Re: Sizing a dictionary jdaw1 <jdawiseman@gmail.com> - 2014-09-06 03:31 -0700
        Re: Sizing a dictionary Scott Hemphill <hemphill@hemphills.net> - 2014-09-09 13:35 -0400
          Re: Sizing a dictionary luser- -droog <mijoryx@yahoo.com> - 2014-09-13 01:11 -0700
            Re: Sizing a dictionary Scott Hemphill <hemphill@hemphills.net> - 2014-09-13 12:04 -0400

csiph-web