Re: GNAT: Performance of String functions

[Mats Weber <Mats.Weber@elca-matrix.ch>]

> I'd be delighted if it is possible to write a portable bounded string
> package
> that does not copy blindly on assignment. So far everything I have
> seen leads
> me to believe that this is not possible. Perhaps if bounded strings
> were
> implemented with pointers to the actual strings, but that may just
> complicate
> matters.

In GNAT 3.09, bounded strings are implemented as 

      subtype Length_Range is Natural range 0 .. Max_Length;

      type Bounded_String is record
         Length : Length_Range := 0;
         Data   : String (1 .. Max_Length);
      end record;

an alternative implementation is

      subtype Length_Range is Natural range 0 .. Max_Length;

      type Bounded_String (Length : Length_Range := 0) is record
         Data : String (1 .. Length);
      end record;

both have their advantages and disadvantages:

GNAT's choice implies copying the whole record on assignment, whereas the
other approoach will probably only copy the storage occupied by the value. So
yes, bounded strings can be implemented without blind copying on assignment.

On the other hand, operations such as appending a single character to a string
can be done directly in the GNAT implementation, but involves re-assigning the
whole value in the alternative implementation, and can turn O(N) algorithms
into O(N**2).

Also, in the GNAT case, if you get into a situation where predefined "="
re-emerges, then your program is broken because you will be comparing the
whole records instead of just the slice 1 .. Length. This problem does not
occur with the alternative approach. I think an AI is about to be voted that
will require predefined "=" to behave correctly for these types, which will
almost force implementors to use the alternative approach.