X-Received: by 10.66.252.6 with SMTP id zo6mr8633637pac.40.1410624299582; Sat, 13 Sep 2014 09:04:59 -0700 (PDT) Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.glorb.com!r10no1505714igi.0!news-out.google.com!ht4ni8213igb.0!nntp.google.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!news.giganews.com.POSTED!not-for-mail NNTP-Posting-Date: Sat, 13 Sep 2014 11:04:59 -0500 From: Scott Hemphill Newsgroups: comp.lang.postscript Subject: Re: Sizing a dictionary References: <53192ca2-9439-4cde-9e15-8b81ea651b9c@googlegroups.com> <83270c40-a170-4b50-b149-eca634e7a33b@googlegroups.com> <4ef9f5d2-a114-4904-890b-2ef795f53420@googlegroups.com> Reply-To: hemphill@alumni.caltech.edu Date: Sat, 13 Sep 2014 12:04:59 -0400 Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.1 (gnu/linux) Cancel-Lock: sha1:MPbj1qvp1Nrpu+RNfz0A8g2jEw0= MIME-Version: 1.0 Lines: 56 X-Usenet-Provider: http://www.giganews.com X-Trace: sv3-yO1FLhopHlPl+8FyOsylTLYSKPenkUn6/TXKdyALnMNDzLJDsiNtwUZvxLfYipncM7kZEJUO8KMez/1!zGJ55pATFM3iLAAPqEcaKiwyr++RSx35opE+H3warlhvDVFqNyjFyZM= X-Complaints-To: abuse@giganews.com X-DMCA-Notifications: http://www.giganews.com/info/dmca.html X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly X-Postfilter: 1.3.40 X-Original-Bytes: 3658 Content-Type: text/plain; charset=us-ascii Xref: csiph.com comp.lang.postscript:2051 luser- -droog writes: > On Tuesday, September 9, 2014 12:35:39 PM UTC-5, Scott Hemphill wrote: >> jdaw1 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