String library with garbage collection?

String library with garbage collection?

[I. Marks]

I'm looking for an open source dynamic string library with garbage 
collection for Ada95.

Any hints?

Thanks for anwers.
Regards,
Ingo

Re: String library with garbage collection?

[Grein, Christoph]

> I'm looking for an open source dynamic string library with garbage 
> collection for Ada95.
> 
> Any hints?

What about Ada.Strings.Unbounded RM A.4.5?

Re: String library with garbage collection?

[Craig Carey]

On Thu, 09 Jan 2003 11:33:56 +0100, Ingo "I. Marks" <nospam_adv@region-nord.de>
 wrote:

>I'm looking for an open source dynamic string library with garbage 
>collection for Ada95.
>
>Any hints?
>

I have a "faster than Unbounded Strings" strings package here:

   http://www.ijs.co.nz/code/ada95_strings_pkg.zip

   package StriUnli, 17KB, updated in Jan 2003, seems to run well.

That package does not implement garbage collecting. Also it is not 'dynamic'.
Each string has waste and a way of resolving that is to have the calling
program shift it into global variables if possible.


   type V_Str is private;                 --  tagged private is possible
   ...
   type V_Str is new Ada.Finalization.Controlled with
      record
         Len      : aliased Natural := 0;
         Str      :  --  pointer to a string on the heap
         ...
      end record;

An example of the sort of code the package allows:

   S   : V_Str
   Vssl (S) (Len (S) + 1 .. Vss (S)'Last) := Vss (S) (Z .. Len (S));

(Functions Vssl() and Vss() return pointers to the string on the heap.)

Increasing the use of pointers increases the safeness of the program
since slicing can causes SIGSEGV's in Windows 2000 when the number of
tasks is increased by reducing the stack size. It is nice how a pointer
can be dereferences on the left hand side of an assignment.

Anyway maybe garbage was not needed.

This argument might be one that is followed.

1. Program needs to run faster;

2. Timing tests pinpoint a problem with ":=" being slow (it is inevitable
 given the wording of RM7.6 which splits ":=" into 2 procedures (Finalize
 (which may deallocate) and Adjust (which may allocate))). 

3. The solution is replace ":=" with a call to a user defined
 "Assign(L,R)". Using ":=" is nice but it is not the best option. All
 ":=" can be changed into calls to an "Assign()" proc.

4. Strings are on the heap. RM7.6's Finalize() seems efficient enough that
 automatic deallocation can be done instead having plain pointers to strings
 on the heap.

5. Still calls to "new" and deallocations are slow. Rather than have
 user side garbage collecting (something done to avoid garbage collecting
 by the OS, perhaps), a trick is to make the strings be globals.

 For example, each procedure can get a package of temporary strings as a
 parameter (which may make it task safe (RM9.10(11)).
 The global strings are renamed so that they look like local variables.

   HTTP_Buffer   : V_Str renames Tmps.Str_1;

 If the number of globals is variable, then maybe a balanced binary tree
 could hold them (e.g. some code based on Booch's AVL binary tree code).

6. The strings have waste space that may diffuse throughout the global
 strings if fast swapping of strings was done. Modifying the algorithms
 could prevent a problem with that.

7. A task safe garbage collecting strings manager may be much slower than
 a scheme based on global variables if it uses protected objects to make
 it task safe. Anyway, if a garbage collecting scheme appears, it could
 be timed to see if it is any good. I presume it won't compare well in
 timing tests.


It is not shown by here (or in the previous message) that there was a
real need for a garbage collecting strings package. It could be quite
hard to get it running fast enough.





Craig Carey
Ada 95 mailing lists http://www.ijs.co.nz/ada_95.htm

Re: String library with garbage collection?

[Jeffrey Carter]

I. Marks wrote:
> I'm looking for an open source dynamic string library with garbage 
> collection for Ada95.
> 
> Any hints?

Try the GNAT implementation of Ada.Strings.Unbounded.

-- 
Jeff Carter
"Your mother was a hamster and your father smelt of elderberries."
Monty Python & the Holy Grail

Re: String library with garbage collection?

[Craig Carey]

On Fri, 10 Jan 2003 08:50:53 +1300, Craig Carey <research@ijs.co.nz> wrote:

>
>On Thu, 09 Jan 2003 11:33:56 +0100, Ingo "I. Marks" <nospam_adv@region-nord.de>
> wrote:
>
>>I'm looking for an open source dynamic string library with garbage 
...


>   http://www.ijs.co.nz/code/ada95_strings_pkg.zip
...

>Increasing the use of pointers increases the safeness of the program
>since slicing can causes SIGSEGV's in Windows 2000 when the number of
>tasks is increased by reducing the stack size.
...


Whoops, that should say: increasing the safety of the package, rather than the
safety of the 'program'.

E.g. with GNAT, these arguments can be supplied:
   "-gnato -gnata -funwind-tables -bargs -E -largs --stack=0x2000"
The 2000 bytes figure could be too small.

[No "-Xlinker" before the "--stack=..." for GNAT 3.15p in Linux.]

[To get GNAT's Symbolic tracebacks to return line numbers (excl. RedHat),
instead of an empty string, the "-bargs -E" option would be added. A question
about that was asked on 17-Dec-2002]


Mailing lists: http://www.ijs.co.nz/ada_95.htm

Re: String library with garbage collection?

[James S. Rogers]

"Craig Carey" <research@ijs.co.nz> wrote in message
news:u2ar1vcnuqia1j380gc3pk134rg87dgvba@4ax.com...
>
> On Thu, 09 Jan 2003 11:33:56 +0100, Ingo "I. Marks"
<nospam_adv@region-nord.de>
>  wrote:
>
> >I'm looking for an open source dynamic string library with garbage
> >collection for Ada95.
> >
> >Any hints?
> >
>
> I have a "faster than Unbounded Strings" strings package here:
>
>    http://www.ijs.co.nz/code/ada95_strings_pkg.zip
>
>    package StriUnli, 17KB, updated in Jan 2003, seems to run well.
>
> That package does not implement garbage collecting. Also it is not
'dynamic'.
> Each string has waste and a way of resolving that is to have the calling
> program shift it into global variables if possible.

Ada.Strings.Unbounded is not intended to be fast. It is intended
to be dynamic. Ada strings are fast and inflexible. The package
Ada.Strings.Unbounded allows you to instantiate fast and flexible
strings.

The placement of variables in global scope can cause severe problems
in a concurrent system. Be very careful when not to use global variables
with tasks.

Jim Rogers

Re: String library with garbage collection?

[Craig Carey]

On Thu, 09 Jan 2003 20:46:45 GMT, "James S. Rogers"
<jimmaureenrogers@worldnet.att.net> wrote:
>"Craig Carey" <research@ijs.co.nz> wrote in message
>news:u2ar1vcnuqia1j380gc3pk134rg87dgvba@4ax.com...
>> On Thu, 09 Jan 2003 11:33:56 +0100, Ingo "I. Marks"
><nospam_adv@region-nord.de>
>>  wrote:
>>
>> >I'm looking for an open source dynamic string library with garbage
>> >collection for Ada95.
...
>> I have a "faster than Unbounded Strings" strings package here:
>>
>>    http://www.ijs.co.nz/code/ada95_strings_pkg.zip
...
>Ada.Strings.Unbounded is not intended to be fast. It is intended
>to be dynamic. Ada strings are fast and inflexible. The package
>Ada.Strings.Unbounded allows you to instantiate fast and flexible
>strings.
>

That seems to be a seriously incomplete argument. Is there anything else
that a programmer might simply want that Ada's Unbounded Strings can't
deliver?. 

Since two major somewhat free implementations of Ada 95 have
Unbounded Strings that are noticeably slow, the intent may be something
that this message thread can fail to inquire into.

Also Unbounded Strings are not obviously "flexible" since there is no
true array slicing feature and also because of this...

If X:=Y is to be done, and Y is 500 MB big, and X has only got 10 KB
allocated for it, and also Y will never be used again, then it just can't
be done using swapping due to the inflexible design of the .. package and
the problem is that there is nothing in the package that is willing to
receive the information that variable Y won't be used again.

It is missing something, and if there was an AI to correct the problem
then based on some private e-mail I got, the AI might be voted against.


>The placement of variables in global scope can cause severe problems
>in a concurrent system. Be very careful when not to use global variables
>with tasks.


I meant global to each task. I did write that the globals were
parameters.  Anyway, the advice has to be ignored... since global
variables that do not change their value, and 'pragma Atomic()'
variables, can be safe to access. Also that strings package I mentioned
labels nodes in a simple global linked list, with Task_Id's which allows
safe erroneous simultaneous traversing and updating of the linked list,
which is faster than using protected objects. I tested the code and it
seems to run OK (and the definition of "erroneous" could be rechecked
at some future date).

RM 9.10 defines "erroneous":
   http://www.adaic.org/standards/95aarm/html/AA-9-10.html



Craig Carey

Re: String library with garbage collection?

[James S. Rogers]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 4124 bytes --]

"Craig Carey" <research@ijs.co.nz> wrote in message
news:501s1voa23mlkfu93dailpb04dh20u7b0n@4ax.com...
>
> On Thu, 09 Jan 2003 20:46:45 GMT, "James S. Rogers"
> <jimmaureenrogers@worldnet.att.net> wrote:
> >The placement of variables in global scope can cause severe problems
> >in a concurrent system. Be very careful when not to use global variables
> >with tasks.
>
>
> I meant global to each task. I did write that the globals were
> parameters.  Anyway, the advice has to be ignored... since global
> variables that do not change their value, and 'pragma Atomic()'
> variables, can be safe to access. Also that strings package I mentioned

It is true that global constants are safe to access.

pragma Atomic() is not guaranteed to work for all types.

Quoting from the Ada Reference Manual, Annex C section 6:

Legality Rules

It is illegal to apply either an Atomic or Atomic_Components pragma to an
object or type if the implementation cannot support the indivisible reads
and updates required by the pragma.

In general, atomic reads and updates are only possible for objects that fit
into a register. Furthermore, pragma Atomic() is really only useful on a
uniprocessor system. On multiprocessor systems it makes no difference
whether
or not a read or update is atomic if there is no memory locking during the
operation. You can still have overlapping updates and/or reads instigated
from different processors.

> labels nodes in a simple global linked list, with Task_Id's which allows
> safe erroneous simultaneous traversing and updating of the linked list,
> which is faster than using protected objects. I tested the code and it

There is no way to check Task_Id's and update or read a linked list
element atomically. This entails at least two reads, or a read and a write.
The only way to prevent race conditions and contention for resources
in this case it to provide a locking or blocking mechanism. This is what
protected objects are for.

> seems to run OK (and the definition of "erroneous" could be rechecked
> at some future date).

I recommend you try your tests in a multiprocessor environment.
You may be surprised by the results.

>
> RM 9.10 defines "erroneous":
>    http://www.adaic.org/standards/95aarm/html/AA-9-10.html

Read that definition again. "Erroneous" execution is not a desired
behavior. "Erroneous" execution implies that multiple accesses
are not sequential. Non-sequential accesses are exposed to race conditions.
I do not understand how access can be both safe and erroneous.
If you are testing in a uniprocessor environment then the accesses are
likely not erroneous because they are occuring in the same task.
However, that is much less likely in a multiprocessor environment.

From Ada Reference Manual section 9.10:

Erroneous Execution

Given an action of assigning to an object, and an action of reading or
updating a part of the same object (or of a neighboring object if the two
are not independently addressable), then the execution of the actions is
erroneous unless the actions are sequential. Two actions are sequential if
one of the following is true:

� One action signals the other;

� Both actions occur as part of the execution of the same task;

� Both actions occur as part of protected actions on the same protected
object, and at most one of the actions is part of a call on a protected
function of the protected object.

Note that the second bullet is only true if the task performing both
operations
is not interrupted between the two operations. If it is interrupted there is
a very
real possibility that another task can change one or more of the objects
being
"sequentially" accessed by the first task. This will lead to erroneous
execution.

The way to make all these things happen in the proper (sequential) order is
to make the operations be operations on a protected object. Protected
operations enforce synchronized access to a protected object. This
synchronized
access ensures the necessary sequential access to the internals of the
protected object.

If pragma Atomic() were sufficient there would be no protected objects.

Jim Rogers

Re: String library with garbage collection?

[Craig Carey]

On Fri, 10 Jan 2003 03:52:13 GMT, "James S. Rogers"
<jimmaureenrogers@worldnet.att.net> wrote:
>"Craig Carey" <research@ijs.co.nz> wrote:
>> On Thu, 09 Jan 2003 20:46:45 GMT, "James S. Rogers" wrote:
...

>It is true that global constants are safe to access.
>

E.g. constant pointers in linked list of nodes where each node is
 labelled with a Task_Id. Task can simultaneously traverse it safely.

To add a new node, some safer scheme is used.

If tasks correctly identify their own node and only write to that, then
parallel update also does not need to be protected.

Checks to see which nodes are no longer used, also do not need to be
protected.

An idea is that the function to find the Task_Id,
 "Ada.Task_Identification.Current_Task ()", is faster than protected
objects (and that is true of the GNAT 3.15_ implementation):

   RM C.7.1 The Package Task_Identification
     http://www.adaic.org/standards/95aarm/html/AA-C-7-1.html


>Furthermore, pragma Atomic() is really only useful on a uniprocessor system.

I notice the correction.

>There is no way to check Task_Id's and update or read a linked list
>element atomically. This entails at least two reads, or a read and a write.

Those words "is no way" seems to be inconsistent with these words:

 "global constants [that] are safe to access".

...
>> RM 9.10 defines "erroneous":
>>    http://www.adaic.org/standards/95aarm/html/AA-9-10.html
>
>Read that definition again. "Erroneous" execution is not a desired
>behavior.


That would be rejected using this argument.

RM 9.10, does not actually have extra words to differentiate between the
"updating" of, and the "reading" of, the "global constants" (may need to
add the constraint that the variables be genuinely 'volatile' (updates
are actually done before the next read).

RM9.10(11) uses the word "or" to have the same constraints on both the
idea of reading and writing ("updating"), be applied in an atomic action:

  "Given an action of assigning to an object, and an action of
   reading or updating a part of the same object ... is erroneous
   unless ...".

I thought Mr Rogers was trying to nail down this group as holding a
desire of preferring to avoid owning erroneous programs. To keep the
thread shorter, some corrective statement is appropriate.

[I didn't see text in the RM saying that Task_Id's should be uniquely
assigned over the life of the program.]


PS. Correction: 0x2000 bytes = 8192 bytes


Craig Carey

Some Ada 95 mailing lists: http://www.ijs.co.nz/ada_95.htm