develooper Front page | perl.perl6.internals | Postings from June 2001

RE: The internal string API

Thread Previous | Thread Next
From:
Hong Zhang
Date:
June 19, 2001 16:24
Subject:
RE: The internal string API
Message ID:
400CE9390E334A4393CEECDD6863120A289F25@ussccm003.corp.palm.com

This is the common approach of complicated text representation,
the implemetations I have seen includes IBM IText and SGI
rope. For "rope", each rope is represented by either of a simple 
immutable string, a simple mutable string, a simple immutable
substring of another rope, or a binary node of other two ropes.
We can even add user-defined node for things like memory-
mapped, or #include etc.

The basic string is just one of the rope type. We can build a
text package much like SGI rope. I don't think we should make
the basic string be rope-like, just for complexity and modularity.

Hong

> the simplest tree is one node with a raw block in it.  Only 
> when you start
> doing
> things to it
> 
> 
> 	substr($A, 27, 3, $B)
> 
> and suchlike
> does deferring the copying give a win.
> 
> Say $A is 35 megabytes long and $B is 23K.  Currently, and in any
> string representation that uses raw blocks, we have to do 
> these things:
> 
> 	copy substr($A,27,3) to return value if needed
> 	Allocate a new 36M block
> 	copy substr($A,0,27)
> 	copy $B
> 	copy substr($A,30)
> 
> 	set $A's data pointer to the new block
> 	free $A's old block
> 
> 
> With a tree representation, the assign-to-middle operation becomes:
> 
> 	Return Value if needed is substr($A,27,3)
> 	Create a new string-segment-list-node
> 	Segment 1: substr($A,0,27)
> 	Segment 2: $B (which might be another tree)
> 	Segment 3: substr($A,30)
> 	return $A's old top node to the node pool
> 	set $A's data pointer to the new top node
> 	set $B to copy-on-write mode, so future changes to $B 
> do not affect $A
> 
> no new allocations!
> 
> 
> 
> This kind of thing also allows us to do "live interpolation" in which
> 
> 	ql" this will $change "
> 
> might rewrite to a magic scalar that evaluates the join every time
> it is fetched instead of once when it is built.
> 
> Mixed-type?  Yes!  You could even have a value that is not a 
> string at all,
> hanging off your string tree.
> 

Thread Previous | Thread Next


nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About