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

Groups > comp.lang.postscript > #2006 > unrolled thread

Sizing a dictionary

Back to article view | Back to comp.lang.postscript

Contents

  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

#2006 — Sizing a dictionary

At language level ≥2 dictionaries can created with length 0, as they grow automatically. But I always create them to be the correct length, to match the maximum value of currentdict length. 

These lengths are sometimes checked with:

	/dict {dup 1 add dict dup 3 -1 roll /DictionaryOriginalSize exch put} bind def

	/end {currentdict /DictionaryOriginalSize known {DictionaryOriginalSize currentdict length 1 sub lt {TypeOfPagesBeingRendered = DictionaryOriginalSize = currentdict length 1 sub = (###) =} if} if end} bind def



In https://groups.google.com/forum/#!topic/comp.lang.postscript/hc9-b2W5tY0 luser- -droog wrote:
> `10 dict` creates a dict with capacity for 10 elements 
> (rule of thumb: double the expected size needed for speedy hash lookups)

The quoted text advising aiming for double size. Oooh: that’s new to me. Please, is there evidence of this? It feels like messy programming, so I’d do it only reluctantly. Is there background that I should read? Please say more.

[toc] | [next] | [standalone]

#2017

jdaw1 <jdawiseman@gmail.com> writes:

> At language level ≥2 dictionaries can created with length 0, as they grow automatically. But I always create them to be the correct length, to match the maximum value of currentdict length. 
>
> These lengths are sometimes checked with:
>
> 	/dict {dup 1 add dict dup 3 -1 roll /DictionaryOriginalSize exch put} bind def
>
> 	/end {currentdict /DictionaryOriginalSize known {DictionaryOriginalSize currentdict length 1 sub lt {TypeOfPagesBeingRendered = DictionaryOriginalSize = currentdict length 1 sub = (###) =} if} if end} bind def
>
>
>
> In https://groups.google.com/forum/#!topic/comp.lang.postscript/hc9-b2W5tY0 luser- -droog wrote:
>> `10 dict` creates a dict with capacity for 10 elements 
>> (rule of thumb: double the expected size needed for speedy hash lookups)
>
> The quoted text advising aiming for double size. Oooh: that’s new to me. Please, is there evidence of this? It feels like messy programming, so I’d do it only reluctantly. Is there background that I should read? Please say more.

http://en.wikibooks.org/wiki/Data_Structures/Hash_Tables

When the Apple LaserWriter first came out, I bought the PostScript Red
Book and started figuring out how PostScript Level I was implemented.
In the case of dictionaries, I figured out (modulo my foggy memory) that
if you asked for a dictionary of size smaller than 10, it was promoted
to 10.  Also, whatever size you specified, the internal dictionary was
allocated to be 25% bigger than you asked.  I vaguely recall that hash
collisions were resolved by linear probing using a step of one location.
Collisions become more frequent as the dictionary fills up (or is
constructed) so a dictionary should never be allowed to become more than
80% full (this is the conventional figure, I don't know the original
source).  Note that the 25% premium allows the dictionary to be just 80%
full when you've filled it with the expected number of elements.

See also: Knuth, vol. 3 "Sorting and Searching" section 6.4 Hashing
Also: Google "hash table 80% full" (without the quotes).

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

[toc] | [prev] | [next] | [standalone]

#2020

On Thursday, September 4, 2014 5:04:15 PM UTC-5, Scott Hemphill wrote:
> jdaw1 <jdawiseman@gmail.com> writes:
> 
> > At language level ≥2 dictionaries can created with length 0, as they grow automatically. But I always create them to be the correct length, to match the maximum value of currentdict length. 
> >
> > These lengths are sometimes checked with:
> >
> > 	/dict {dup 1 add dict dup 3 -1 roll /DictionaryOriginalSize exch put} bind def
> >
> > 	/end {currentdict /DictionaryOriginalSize known {DictionaryOriginalSize currentdict length 1 sub lt {TypeOfPagesBeingRendered = DictionaryOriginalSize = currentdict length 1 sub = (###) =} if} if end} bind def
> >
> >
> >
> > In https://groups.google.com/forum/#!topic/comp.lang.postscript/hc9-b2W5tY0 luser- -droog wrote:
> >> `10 dict` creates a dict with capacity for 10 elements 
> >> (rule of thumb: double the expected size needed for speedy hash lookups)
> >
> > The quoted text advising aiming for double size. Oooh: that’s new to me. Please, is there evidence of this? It feels like messy programming, so I’d do it only reluctantly. Is there background that I should read? Please say more.
> 
> http://en.wikibooks.org/wiki/Data_Structures/Hash_Tables
> 
> When the Apple LaserWriter first came out, I bought the PostScript Red
> Book and started figuring out how PostScript Level I was implemented.
> In the case of dictionaries, I figured out (modulo my foggy memory) that
> if you asked for a dictionary of size smaller than 10, it was promoted
> to 10.  Also, whatever size you specified, the internal dictionary was
> allocated to be 25% bigger than you asked.  I vaguely recall that hash
> collisions were resolved by linear probing using a step of one location.
> Collisions become more frequent as the dictionary fills up (or is
> constructed) so a dictionary should never be allowed to become more than
> 80% full (this is the conventional figure, I don't know the original
> source).  Note that the 25% premium allows the dictionary to be just 80%
> full when you've filled it with the expected number of elements.
> 
> See also: Knuth, vol. 3 "Sorting and Searching" section 6.4 Hashing
> Also: Google "hash table 80% full" (without the quotes).
> 

Good stuff. That's the line of reasoning I followed. But I think I made up
the 50% margin that I recommended. 

If anyone ever does any programming for Xpost however, it may be better to
double the size. My hash function is not very well tuned.

[toc] | [prev] | [next] | [standalone]

#2027

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".

[toc] | [prev] | [next] | [standalone]

#2034

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
-- 
Scott Hemphill	hemphill@alumni.caltech.edu
"This isn't flying.  This is falling, with style."  -- Buzz Lightyear

[toc] | [prev] | [next] | [standalone]

#2048

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>

[toc] | [prev] | [next] | [standalone]

#2051

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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.postscript

csiph-web