cargo@CHERRY.CRAY.COM (David S. Cargo) (08/18/90)
I was thinking about the new table mechanisms in the latest version of Icon. I think that a change in the way that the tables are initially allocated could double the size of tables that can be handled effectively as well as improve space and time performance for handling small tables. As I understand it, minimum size tables are now composed of two parts, a table header, and a hash chain header. The table header contains "slots" for pointing to hash chain headers. The hash chain headers are sizes based on powers of two. The first hash chain header will be of size 8 (for example), the second will be of the same size, the third will be equal to the sum of the sizes of the first two, the fourth will be equal to the sum of the sizes of the first three, etc. I believe the current implementation also has 8 slots for pointing to hash chain headers. Therefore it can point to 8 + 8 + 16 + 32 + 64 + 128 + 256 + 512 = 1024 chains. An empty table has a table header that points to an empty hash chain header. What I think might be worth investigating is using the table header slots as hash chain headers for small tables. This still gives you 8 hash chain slots. Then, if the table load factor grows to the point where more hash chain slots are needed, allocate a hash chain header with 16 slots. Instead of starting the sizes of hash chain headers at 8, this would start them at 16, doubling the number of total slots that could be pointed to by the 8 slots in the table header. For small tables, this eliminates one level of indirection and reduces the space overhead for small and empty tables. It also reduces the time overhead for creating tables, since fewer memory allocations are required. This would be most noticable when many small tables are created. For large tables, this doubles the maximum number of potential hash chains. Certainly the semantics of tables require that more issues than just the space considerations be examined (e.g., element generation), but making this implementation change would further improve the benefit of dynamic tables. David S. Cargo (cargo@cray.com)