Subject: Re: String Representation

From: Paul Sephton <[email-masked]>
Date: Wed, 17 May 2000 12:47:18 +0200 (GMT+0200)

On Wed, 17 May 2000, Richard A. O'Keefe wrote:

> I wrote:
> > Using a *single* atom to hold a string has the advantage that if there
> > are several occurrences of exactly the same string, they will share the
> > representation, so you can get less than 1 byte per character.
> 	
> Paul Sephton <[email-masked]> wrote:
> 	Unless, of course, you are talking about single character atoms...
> 	
> Not even then.  Suppose for argument's sake that the space cost of
> an entry in the atom table is 16 + 4*ceiling(length/4) bytes, so that
> a single character atom costs 20 bytes.
> 
> If there are more than 20 references to that atom, the average cost
> of the representation is less than 1 byte per character.
> 
> With that space cost, a four-character string would only need 5 references
> to go below one byte per character.

Assuming that an atom is represented internally as a reference to a hash 
table entry, then a list of atoms would be represented internally as a 
variable size array of these references?  My point is, that the smallest 
size allocated per atom would be the size of the reference, which would 
be proscribed by the table size.  For a reference size of a byte, the 
hash table size would be 256.  For a two byte word, 65536.  For four 
bytes 0xffffffff (four billion or so) etc.   

Now, if I have a list of single character atoms, and assuming four byte 
hash keys, I am talking about four bytes per character in my list, 
regardless of the overheads for hash table management.

So, the size to represent an atom would be the size of the reference (for 
however many times the atom is referenced) + the hash table storage 
overhead.  This regardless of the actual size of the atom.

Regards
Paul
_____________________________________________________________________________
Paul Sephton ([email-masked])                               INET Development
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Ever wondered if jumping out of the frying pan might actually be refreshing?
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~