Re: string vs list processing

[Marius Vollmer]

Hi Sascha!

Sascha Ziemann <address@hidden> writes:

> Masao Uebayashi <address@hidden> writes:
> 
> | It seems to me that making a new string from two strings cost much in
> | any language because a memory allocation accompanies. If you want more
> | performance, it'd be better to consider to use other data structure
> | than ordinal string.
> 
> Any suggestions for a HTTP replay? ;-)

The Boehm collector contains "cords", which they say are designed for
making string concatenation fast:

/*
 * Cords are immutable character strings.  A number of operations
 * on long cords are much more efficient than their strings.h counterpart.
 * In particular, concatenation takes constant time independent of the length
 * of the arguments.  (Cords are represented as trees, with internal
 * nodes representing concatenation and leaves consisting of either C
 * strings or a functional description of the string.)
 *
 * The following are reasonable applications of cords.  They would perform
 * unacceptably if C strings were used:
 * - A compiler that produces assembly language output by repeatedly
 *   concatenating instructions onto a cord representing the output file.
 * - A text editor that converts the input file to a cord, and then
 *   performs editing operations by producing a new cord representing
 *   the file after echa character change (and keeping the old ones in an
 *   edit history)
 *
 * For optimal performance, cords should be built by
 * concatenating short sections.
 * This interface is designed for maximum compatibility with C strings.
 * ASCII NUL characters may be embedded in cords using CORD_from_fn.
 * This is handled correctly, but CORD_to_char_star will produce a string
 * with embedded NULs when given such a cord. 

I haven't looked at the implementation.  Maybe its simple enough that
you can just imitate it with native Scheme data types (a cons tree
with strings at the leafs), otherwise it may be a nice project for
someone to port the cords to Guile hint hint... :-)