Strings Fixed, Bounded, and Counted. Performance Inquiry.

Strings Fixed, Bounded, and Counted. Performance Inquiry.

[Freejack]

I'm currently tooling around with the various standard strings packages
And I began wondering if anyone has written a Counted strings package
for Ada.

Fixed strings are great in terms of performance. Bounded strings are
pretty good. However I havent seen anyone do a performance analysis of
Counted strings. I'm thinking in the Forth sense of the type.

i.e. The first element of the String is a number indicating the length of
the string. No null terminators needed. 
A bit more flexible than Fixed strings, a heck of a lot faster than Null 
terminated strings. Not sure how they stack up to Bounded strings.

Has anyone played with these in an Ada context?

I'm gonna write my own experimental package if nobody else has

Freejack

Re: Strings Fixed, Bounded, and Counted. Performance Inquiry.

[Marin David Condic]

It may depend on your implementation, but Bounded strings ought to give 
you basically what you are looking for. It has a fixed maximum 
allocation and it maintains some sort of counter to know how long the 
actual content is. They have the down side that all strings must have 
the same maximum size in order to be compatible, but unless you wanted 
something dynamic, this shouldn't be a really bad limitation.

Unbounded_String has got to do something similar - store a counter for 
the actual length. They have the advantage of growing as you need them 
to but would have a speed penalty.

Or you could just use a garden variety fixed size String and cobble 
something together for yourself. It would just be a record with a 
counter and possibly a pointer to an actual fixed length string. Its not 
as wonderful an answer as one of the built-in packages, but you might 
get the utility you want as a result. (Id est, allocating only the space 
you actually need to store the string, flexible upper bounds & whatever 
sort of comparison or other operations you want to support.) You'd 
probably make heavy use of Ada.Strings.Fixed in the process.

MDC


Freejack wrote:
> I'm currently tooling around with the various standard strings packages
> And I began wondering if anyone has written a Counted strings package
> for Ada.
> 
> Fixed strings are great in terms of performance. Bounded strings are
> pretty good. However I havent seen anyone do a performance analysis of
> Counted strings. I'm thinking in the Forth sense of the type.
> 
> i.e. The first element of the String is a number indicating the length of
> the string. No null terminators needed. 
> A bit more flexible than Fixed strings, a heck of a lot faster than Null 
> terminated strings. Not sure how they stack up to Bounded strings.
> 
> Has anyone played with these in an Ada context?
> 
> I'm gonna write my own experimental package if nobody else has
> 
> Freejack


-- 
======================================================================
Marin David Condic
I work for: http://www.belcan.com/
My project is: http://www.jsf.mil/NSFrames.htm

Send Replies To: m c o n d i c @ a c m . o r g

     "So if I understand 'The Matrix Reloaded' correctly, the Matrix is
     basically a Microsoft operating system - it runs for a while and
     then crashes and reboots. By design, no less. Neo is just a
     memory leak that's too hard to fix, so they left him in... The
     users don't complain because they're packed in slush and kept
     sedated"

         --  Marin D. Condic
======================================================================

Re: Strings Fixed, Bounded, and Counted. Performance Inquiry.

[Jeffrey Carter]

Freejack wrote:

> i.e. The first element of the String is a number indicating the length of
> the string. No null terminators needed. 
> A bit more flexible than Fixed strings, a heck of a lot faster than Null 
> terminated strings. Not sure how they stack up to Bounded strings.

How would you implement Bounded_String? I think you'll find it's what 
you're calling a counted string.

-- 
Jeff Carter
"We use a large, vibrating egg."
Annie Hall
44

Re: Strings Fixed, Bounded, and Counted. Performance Inquiry.

[Marin David Condic]

Two counted strings might not have to have the same allocated space. It 
may not have any excess space at all, depending on what one has in mind. 
Bounded strings pretty much have to have a fixed allocation - all of the 
same length if they come from the same instantiation.

MDC

Jeffrey Carter wrote:
> 
> How would you implement Bounded_String? I think you'll find it's what 
> you're calling a counted string.
> 

-- 
======================================================================
Marin David Condic
I work for: http://www.belcan.com/
My project is: http://www.jsf.mil/NSFrames.htm

Send Replies To: m c o n d i c @ a c m . o r g

     "So if I understand 'The Matrix Reloaded' correctly, the Matrix is
     basically a Microsoft operating system - it runs for a while and
     then crashes and reboots. By design, no less. Neo is just a
     memory leak that's too hard to fix, so they left him in... The
     users don't complain because they're packed in slush and kept
     sedated"

         --  Marin D. Condic
======================================================================

Re: Strings Fixed, Bounded, and Counted. Performance Inquiry.

[Stephen Leake]

Freejack <user@nospam.net> writes:

> Fixed strings are great in terms of performance. Bounded strings are
> pretty good. However I havent seen anyone do a performance analysis of
> Counted strings. I'm thinking in the Forth sense of the type.

Ah, Forth. Haven't done that in a while.

> i.e. The first element of the String is a number indicating the
> length of the string. 

If I recall correctly, Forth strings are all fixed, in the sense that
they cannot be modified in place. 

> No null terminators needed. 

Correct.

> A bit more flexible than Fixed strings, 

How?

> a heck of a lot faster than Null terminated strings. 

Depends on what you are doing. Copying the strings character by
character is the same speed for either construct. Block copy is faster
with a count on most machines. But most algorithms for processing
strings operate character by character, so it doesn't really matter.

Safety is another issue; with a count (or bounds) it is possible to
check array indices before fetching or storing.

> Not sure how they stack up to Bounded strings.

Since Ada fixed strings store the array bounds, that is essentially
the same as counted Forth strings.

Ada Bounded strings let you change the value in place, so they are
more flexible.

> Has anyone played with these in an Ada context?

Yes, all the time :).

> I'm gonna write my own experimental package if nobody else has

Be sure you define _precisely_ what you want the package to do, and
see if Ada already has it, before you spend time implementing it.

-- 
-- Stephe

Re: Strings Fixed, Bounded, and Counted. Performance Inquiry.

[Freejack]

On Mon, 27 Oct 2003 12:18:48 -0500, Stephen Leake wrote:

 
>> A bit more flexible than Fixed strings,
> 
> How?

It was my understanding(I could be wrong here) that a Fixed string is
unmodifiable without access to functions provided in the package. A
Counted string is modifiable outside the package provided functions and
procedures. No?

 
>> a heck of a lot faster than Null terminated strings.
> 
> Depends on what you are doing. Copying the strings character by
> character is the same speed for either construct. Block copy is faster
> with a count on most machines. But most algorithms for processing
> strings operate character by character, so it doesn't really matter.
> 
> Safety is another issue; with a count (or bounds) it is possible to
> check array indices before fetching or storing.

 So essentially, with a Fixed string, I can have the compiler generate
machine code to grab a block of length X, and shove it into an empty
block of length Y if Y > X? All on one I/O procedure? (Thinking of the
Linux "sendfile()" and "iovec()" functions here.)
I really want to avoid character by character transfer when it's not
necessary.
Also, if I can read the first element, and see that the string has twenty
characters, I can have the program inline a procedure x/20 times, rather
than using a Counter and loop structure. 
 
>> I'm gonna write my own experimental package if nobody else has
> 
> Be sure you define _precisely_ what you want the package to do, and see
> if Ada already has it, before you spend time implementing it.
 
I am definitely being specific in my package spec. You're right. Aside
from a couple quirks of my own design, bounded strings do the right
thing. As do Fixed Strings.

I'll keep playing with 'em and tell you what I come up with. Heh.

Thanks.

Freejack

Re: Strings Fixed, Bounded, and Counted. Performance Inquiry.

[Stephen Leake]

Freejack <user@nospam.net> writes:

> On Mon, 27 Oct 2003 12:18:48 -0500, Stephen Leake wrote:
> 
>  
> >> A bit more flexible than Fixed strings,
> > 
> > How?
> 
> It was my understanding(I could be wrong here) that a Fixed string is
> unmodifiable without access to functions provided in the package. A
> Counted string is modifiable outside the package provided functions and
> procedures. No?

If you mean an Ada Counted string, you get to define it. If that's
what you want, so be it.

I don't see why using "functions provided in the package" is a
problem; that's what they are for!

> >> a heck of a lot faster than Null terminated strings.
> > 
> > Depends on what you are doing. Copying the strings character by
> > character is the same speed for either construct. Block copy is faster
> > with a count on most machines. But most algorithms for processing
> > strings operate character by character, so it doesn't really matter.
> > 
> > Safety is another issue; with a count (or bounds) it is possible to
> > check array indices before fetching or storing.
> 
>  So essentially, with a Fixed string, I can have the compiler generate
> machine code to grab a block of length X, and shove it into an empty
> block of length Y if Y > X? 

With any Ada string, Fixed or not. Yes.

> All on one I/O procedure? (Thinking of the Linux "sendfile()" and
> "iovec()" functions here.) I really want to avoid character by
> character transfer when it's not necessary. 

Let the compiler worry about that.

> Also, if I can read the first element, and see that the string has
> twenty characters, I can have the program inline a procedure x/20
> times, rather than using a Counter and loop structure.

That's what 'Length is for. Or the Length function in the
Ada.Strings.* packages. They are all very fast functions; you should
not worry about how fast they are.

> >> I'm gonna write my own experimental package if nobody else has
> > 
> > Be sure you define _precisely_ what you want the package to do, and see
> > if Ada already has it, before you spend time implementing it.
>  
> I am definitely being specific in my package spec. You're right. Aside
> from a couple quirks of my own design, bounded strings do the right
> thing. As do Fixed Strings.
> 
> I'll keep playing with 'em and tell you what I come up with. Heh.

Ok, sounds good.

-- 
-- Stephe

Re: Strings Fixed, Bounded, and Counted. Performance Inquiry.

[Tarjei T. Jensen]

Stephen Leake  wrote:
> Depends on what you are doing. Copying the strings character by
> character is the same speed for either construct. Block copy is faster
> with a count on most machines. But most algorithms for processing
> strings operate character by character, so it doesn't really matter.

I don't buy that. There is a lot of character by character processing
because there is no access to the length of the string.

BTW. Counted strings was on the Want List for Ada95.

greetings,