Re: String library with garbage collection?

[Craig Carey <research@ijs.co.nz>]

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