From ok@atlas.otago.ac.nz  Wed May 17 04:56:36 2000
Received: from atlas.otago.ac.nz (atlas.otago.ac.nz [139.80.32.250])
	by swi.psy.uva.nl (8.9.3/8.9.3) with ESMTP id EAA20507
	for <prolog@swi.psy.uva.nl>; Wed, 17 May 2000 04:56:35 +0200 (MET DST)
Received: (from ok@localhost)
	by atlas.otago.ac.nz (8.9.3/8.9.3) id OAA27684;
	Wed, 17 May 2000 14:56:37 +1200 (NZST)
Date: Wed, 17 May 2000 14:56:37 +1200 (NZST)
From: "Richard A. O'Keefe" <ok@atlas.otago.ac.nz>
Message-Id: <200005170256.OAA27684@atlas.otago.ac.nz>
To: ok@atlas.otago.ac.nz, paul@inet.co.za
Subject: Re: String Representation
Cc: ino-waiting@gmx.net, prolog@swi.psy.uva.nl

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 <paul@inet.co.za> 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.

It's worth noting that the SNOBOL 4 programming language, whose whole
purpose was to process lots of strings in a pattern-matchy way, used
"unique strings".  That is, whenever it constructed a string, it looked
it up in a hash table to ensure that it had only one copy.

It's also worth noting that one of the things Dewar et al did in SPITBOL
(a SNOBOL compiler that generated considerably faster code) was to get
rid of the hash table...

It really all depends on what you are doing with strings.
If you are doing lots of splits and joins, lists of characters
are far more efficient than packed arrays of bytes, and of course than atoms.
But not _all_ applications of strings do that.

