Work at SourceForge, help us to make it a better place! We have an immediate need for a Support Technician in our San Francisco or Denver office.
Close
From: <lutz.euler@fr...>  20070322 21:47:58

Hi, looking at "sbcl.core" with a hex editor I noticed largish areas consisting of zeroes sparsely interrupted by nonzero bytes or words. It turns out that many of these are the arrays that implement package hash tables, each hash table consisting of one byte array and one word array, both containing zeroes in empty slots. Lots of these tables are way too sparse, some even completely empty, for example: * (inspect (findpackage :sbsys)) [...] 5. INTERNALSYMBOLS: #<SBIMPL::PACKAGEHASHTABLE :SIZE 1733 :FREE 1730 :DELETED 0> [...] or * (inspect (findpackage :sbext)) [...] 5. INTERNALSYMBOLS: #<SBIMPL::PACKAGEHASHTABLE :SIZE 1812 :FREE 1812 :DELETED 0> [...] In sum, there are about 21500 symbols in SBCL stored in about 115500 pairs of array slots. Populating the package hash tables more densely, for example using a density of 0.5, reduces the core size by 2 percent (750 KB on x8664) and could reduce cache usage in the reader. (For reference: when interning symbols INTERN doubles the size of the tables and rehashes the entries when the density gets larger than 0.75.) If this is considered a reasonable improvement to SBCL, may I ask for some advice on how best to implement it? As far as I understand, the sizes of the hash tables currently get into sbcl.core as follows: The package hash tables grow as large as needed while SBCL compiles itself and interns lots of symbols from the source code. When writing the cold core only the symbols listed in *COLDPACKAGESYMBOLS* are saved but the hash table sizes are calculated from all symbols in the corresponding packages (see FINISHSYMBOLS). Later during maketarget2load.lisp !UNINTERNINITONLYSTUFF is called and uninterns symbols with funny names. It doesn't touch the package hash table sizes which get into sbcl.core when finally SAVELISPANDDIE is called. I can think of the following options: 1. Shrink package hash tables during SAVELISPANDDIE. Advantage: Not only SBCL itself benefits but also usersaved cores, provided the user uninterns unneeded symbols before calling SAVELISPANDDIE. 2. In FINISHSYMBOLS, count the symbols saved for each package and base the calculation of the sizes of the package hash tables on these counts. Disadvantage: This only helps for packages whose symbol count is approximately the same in the cold and the final core. 3. Make UNINTERN check whether the package hash tables get too sparse and rehash them if so. Personally, I prefer option 1 as it provides the most control over the space used by the hash tables in sbcl.core. Any comments? Yours Lutz Euler 
From: <william.newman@ai...>  20070323 13:03:17

On Thu, Mar 22, 2007 at 10:46:08PM +0100, Lutz Euler wrote: > In sum, there are about 21500 symbols in SBCL stored in about 115500 > pairs of array slots. Populating the package hash tables more densely, > for example using a density of 0.5, reduces the core size by 2 percent > (750 KB on x8664) and could reduce cache usage in the reader. Hmm, that *is* quite a lot. > If this is considered a reasonable improvement to SBCL, may I ask for > some advice on how best to implement it? > 1. Shrink package hash tables during SAVELISPANDDIE. > 2. In FINISHSYMBOLS, count the symbols saved for each package and base > the calculation of the sizes of the package hash tables on these > counts. > 3. Make UNINTERN check whether the package hash tables get too sparse > and rehash them if so. > Personally, I prefer option 1 as it provides the most control over the > space used by the hash tables in sbcl.core. > Any comments? I think #3 is worth doing whether or #1 and #2 are done. An application programmer can reasonably expect an exported deletefromtable operation to be implemented efficiently. It also looks relatively easy to test #3, which should tend to make it easier to set up and maintain. #1 and #2 could still be improvements worth doing, but in trying to determine how much they improve things, I think the best baseline would be relative to #3.  William Harold Newman <william.newman@...> PGP key fingerprint 85 CE 1C BA 79 8D 51 8C B9 25 FB EE E0 C3 E5 7C Ubi saeva indignatio ulterius cor lacerare nequit.  Jonathan Swift's epitaph 
From: <lutz.euler@fr...>  20070401 18:00:33
Attachments:
patchpackagehash

Hi, I wrote: > I can think of the following options: > > 1. Shrink package hash tables during SAVELISPANDDIE. > > 2. In FINISHSYMBOLS, count the symbols saved for each package and base > the calculation of the sizes of the package hash tables on these > counts. > > 3. Make UNINTERN check whether the package hash tables get too sparse > and rehash them if so. William Newman answered: > I think #3 is worth doing whether or #1 and #2 are done. An > application programmer can reasonably expect an exported > deletefromtable operation to be implemented efficiently. It also > looks relatively easy to test #3, which should tend to make it easier > to set up and maintain. > > #1 and #2 could still be improvements worth doing, but in trying to > determine how much they improve things, I think the best baseline > would be relative to #3. Thanks for the feedback! I have implemented all three variants and tested their effects (on x8664). It turns out that #3 alone gains nothing, that is, the size of "sbcl.core" is slightly larger with it than without it. Also, most package hash tables are exactly as sparse as before. With hindsight this is easy to explain: While saving the cold core no symbols are uninterned and while saving the warm core only a few, say, 100 in total, for instance in SBIMPL some 30 out of some 3000. This does not suffice to trigger the downsizing rehashing. #1 alone shrinks "sbcl.core" by 737 KB (with a target load factor of 0.5), or by 807 KB (load factor: 0.6). #2 alone shrinks "sbcl.core" by 778 KB. I left the parameters in FINISHSYMBOLS that determine the load factor at their current values, which amounts to a load factor of 0.6. In summary, I still like #1 best because it helps not only SBCL itself but also custom cores. #3 is nice to have in addition, as it will help at runtime in cases where lots of symbols are uninterned. Once #1 is in effect, #2 doesn't affect the final core size any longer, but can nevertheless be added: I measured a slight speedup of the warm build phase with it. All of these changes amount to only a few lines of code, as the common code (resizing and rehashing a package hash table) is easily factored out. So I suggest to simply implement all three parts. This is what the attached patch does. Apart from the changes necessary to this end there are some gratuitous ones:  In ADDSYMBOL, if the table is full and needs rehashing, I changed the calculation of the new size to disregard deleted entries. This way, if the table contains deleted entries, the resized hash table will not be too sparse.  In MAKEORREMAKEPACKAGEHASHTABLE I changed the calculation of the actual package hash table size to start with CEILING instead of TRUNCATE of the number of entries asked for and the rehash threshold. This way the table will in all cases be able to hold the asked for number of entries without rehashing. (The current version, when asked for a table to hold 10 entries, for example, will use a vector of length 13 that can hold only 9 entries.) Kind regards Lutz Euler 
From: Juho Snellman <jsnell@ik...>  20070412 19:22:30

lutz.euler@... (Lutz Euler) writes: > All of these changes amount to only a few lines of code, as the common > code (resizing and rehashing a package hash table) is easily factored > out. So I suggest to simply implement all three parts. This is what the > attached patch does. Thanks, that looks good. Committed.  Juho Snellman 