Re: speed of octave symbol table code

[David Bateman]

John W. Eaton wrote:
> Note that with the table size of 32, the number of empty chains is
> often zero when the number of symbols reaches about 100.  Increasing
> the table size by 50% gives us more free chains, but the hash function
> doesn't seem to be spreading the symbols out to fill the additional
> chains and the maximum chain length (which affects lookup speed) ends
> up being about the same.  So it doesn't seem that 48 is much better
> than 32.  A chain length of N means that finding a symbol may require
> as many as N string compares after computing the hash value.  So if
> chain length is 10, that could mean a hit on performance for
> evaluating a function.  Overall, chain length will increase if the
> table is smaller since there are fewer chains, but how often do people
> write functions that have more than 200 or so symbols in them?  If
> that happens frequently, then maybe we should stay at 128 even though
> there is a penalty for clearing empty tables? Otherwise, I would say
> it is OK to cut the table size to 32.
>
>   
It really depends on the real life code and the number of symbol table
lookups per function, and as you say how many symbols per function. What
is the average number of symbols per function with your code for "make
check". From the table you sent for the 128, 48 and 32 hash table
entries I get 90.7, 102.833 and 101.767 symbols per hash table. However,
these are the top 30 entries in the hash table sort by the maximum
tables sorted by the max chain length and not all functions called by
make check.. On the assumption that "make check" is a reasonable
estimate of a real life  situation it would be interesting to know the
average number of symbol table entries...

Finally, why not just run /bin/time on octave in the "make check" target
to compare the execution speed overall, for various hash table sizes.
This might give a good indication whether we'll win here or not.. Its a
tough call, so if its too much hassle just forgot it and leave the hash
tables at 128 entries in size..

D.

-- 
David Bateman                                address@hidden
Motorola Labs - Paris                        +33 1 69 35 48 04 (Ph) 
Parc Les Algorithmes, Commune de St Aubin    +33 6 72 01 06 33 (Mob) 
91193 Gif-Sur-Yvette FRANCE                  +33 1 69 35 77 01 (Fax) 

The information contained in this communication has been classified as: 

[x] General Business Information 
[ ] Motorola Internal Use Only 
[ ] Motorola Confidential Proprietary