summaryrefslogtreecommitdiff
path: root/devel
diff options
context:
space:
mode:
authorMikael Djurfeldt <djurfeldt@nada.kth.se>2000-08-26 20:55:21 +0000
committerMikael Djurfeldt <djurfeldt@nada.kth.se>2000-08-26 20:55:21 +0000
commit9b5477f6f615248bb4ed7660a3ac0192b55c587b (patch)
treeddd66e5116ccf7298b438993bd0eef85d1a10d36 /devel
parent92ccc1f1f326a7eddc3cb0ba4fca15741e51acf2 (diff)
downloadguile-9b5477f6f615248bb4ed7660a3ac0192b55c587b.tar.gz
* strings/sharedstr.text (sharedstr.text): New file.
Diffstat (limited to 'devel')
-rw-r--r--devel/strings/sharedstr.text143
1 files changed, 143 insertions, 0 deletions
diff --git a/devel/strings/sharedstr.text b/devel/strings/sharedstr.text
new file mode 100644
index 000000000..f568c3ebf
--- /dev/null
+++ b/devel/strings/sharedstr.text
@@ -0,0 +1,143 @@
+Implementation of shared substrings with fresh-copy semantics
+=============================================================
+
+Version: $Id: sharedstr.text,v 1.1 2000-08-26 20:55:21 mdj Exp $
+
+Background
+----------
+
+In Guile, most string operations work on two other data types apart
+from strings: shared substrings and read-only strings (which includes
+symbols). One of Guile's sub-goals is to be a scripting language in
+which string management is important. Read-only strings and shared
+substrings were introduced in order to reduce overhead in string
+manipulation.
+
+We now want to simplify the Guile API by removing these two data
+types, but keeping performance by allowing ordinary strings to share
+storage.
+
+The idea is to let operations like `symbol->string' and `substring'
+return a pointer into the original string/symbol, thus avoiding the
+need to copy the string.
+
+Two of the problems which then arise are:
+
+* If s2 is derived from s1, and therefore share storage with s1, a
+ modification to either s1 or s2 will affect the other.
+
+* Guile is supposed to interact closely with many UNIX libraries in
+ which the NUL character is used to terminate strings. Therefore
+ Guile strings contain a NUL character at the end, in addition to the
+ string length (the latter of which is used by Guile's string
+ operations).
+
+The solutions to these problems are to
+
+* Copy a string with shared storage when it's modified.
+
+* Copy a string with shared storage when it's being used as argument
+ to a C library call. (Copying implies inserting an ending NUL
+ character.)
+
+But this leads to memory management problems. When is it OK to free
+a character array which was allocated for a symbol or a string?
+
+Abstract description of proposed solution
+-----------------------------------------
+
+Definitions
+
+ STRING = <TYPETAG, LENGTH, CHARRECORDPTR, CHARPTR>
+
+ SYMBOL = <TYPETAG, LENGTH, CHARRECORDPTR, CHARPTR>
+
+ CHARRECORD = <PHASE, SHAREDFLAG, CHARS>
+
+ PHASE = black | white
+
+ SHAREDFLAG = private | shared
+
+ CHARS is a character array
+
+ CHARPTR points into it
+
+Memory management
+
+A string or symbol is initially allocated with its contents stored in
+a character array in a character record. The string/symbol header
+contains a pointer to this record. The initial value of the shared
+flag in the character record is `private'.
+
+The GC mark phases alternate between black and white---every second
+phase is black, the rest are white. This is used to distinguish
+whether a character record has been encountered before:
+
+During a black mark phase, when the GC encounters a string or symbol,
+it changes the PHASE and SHAREDFLAG marks of the corresponding
+character record according to the following table:
+
+ <white, private> --> <black, private> (white => unconditionally
+ <white, shared> --> <black, private> set to <black, private>)
+ <black, private> --> <black, shared> (SHAREDFLAG changed)
+ <black, shared> --> <black, shared> (no change)
+
+The behaviour of a white phase is quivalent with the color names
+switched.
+
+The GC sweep phase frees any unmarked string or symbol header and
+frees its character record either if it is marked with the "wrong"
+color (not matching the color of the last mark phase) or if its
+SHAREDFLAG is `private'.
+
+Copy-on-write
+
+An attempt at mutating string contents leads to copying if SHAREDFLAG
+is `shared'. Copying means making a copy of the character record and
+mutating the CHARRECORDPTR and CHARPTR fields of the object header to
+point to the copy.
+
+Substring operation
+
+When making a substring, a new string header is allocated, with new
+contents for the LENGTH and CHARPTR fields.
+
+Implementation details
+----------------------
+
+* We store the character record consecutively with the character
+ array and lump the PHASE and SHAREDFLAG fields together into one
+ byte containing an integer code for the four possible states of the
+ PHASE and SHAREDFLAG fields. Another way of viewing it is that
+ these fields are represented as bits 1 and 0 in the "header" of the
+ character array. We let CHARRECORDPTR point to the first character
+ position instead of on this header:
+
+ CHARRECORDPTR
+ |
+ V
+ FCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
+
+ F = 0, 1, 2, 3
+
+* We represent strings as the sub-types `simple-string' and
+ `substring'.
+
+* In a simple string, CHARRECORDPTR and CHARPTR are represented by a
+ single pointer, so a `simple-string' is an ordinary heap cell with
+ TYPETAG and LENGTH in the CAR and CHARPTR in the CDR.
+
+* substring:s are represented as double cells, with TYPETAG and LENGTH
+ in word 0, CHARRECORDPTR in word 1 and CHARPTR in word 2
+ (alternatively, we could store an offset from CHARRECORDPTR).
+
+Problems with this implementation
+---------------------------------
+
+* How do we make copy-on-write thread-safe? Is there a different
+ implementation which is efficient and thread-safe?
+
+* If small substrings are frequently generated from large, temporary
+ strings and the small substrings are kept in a data structure, the
+ heap will still have to host the large original strings. Should we
+ simply accept this?