Re: Passing strings efficiently

On Sunday 09 Mar 2003 10:36 pm, you wrote:
> However, I was thinking that I could just pass the address of a
> special string structure, with some flags to indicate that it is
> read-only. Then, I would only have to make a copy of the string if
> foo() actually modified it. Of course, I'd have to be careful to free
> the copy when foo() completes.


One solution is to use reference counts: a string is implemented as a
pointer to a structure containing a reference count plus (a pointer
to) the string data. Each time you increase the number of variables
pointing at the string you increase the reference counter. Each time
you decrease the number of variables pointing at the string (including
when a variable goes out of scope) you decrease the reference
count. When the reference count reaches zero, you free the string.


Now the clever bit: when you want to modify the string, check the
reference count: if it is greater than one, take a copy of the string
(with reference count 1), decrease the reference count of the original
string, and modify the copy. If the refcount is one, you can freely
modify the string (since you are working on your own "private" copy).


> [I think you're reinventing garbage collection. -John]


Garbage collection would also work, but you would need to create a new
string each time you modified it: even if you just changed one
character. The refcount approach allows for efficient string
assignments and parameter passing, plus efficient partial update of
strings. Imagine two loops in your program, one passes a huge string
to a function which only examines the first character, the second loop
repeatedly modifies the first character of a huge string. The first
case requires no copies of the string, the second case requires at
most one copy.


--
Martin


Martin.Ward@durham.ac.uk http://www.cse.dmu.ac.uk/~mward/ Erdos number: 4

Return to the comp.compilers page.
Search the comp.compilers archives again.