Workqueues in Ada

Workqueues in Ada

[Wiktor Moskwa]

Hello,

Few months ago I wrote about a distributed protocol simulator that
I was writing in Ada. I followed an advice to stop using a thread per
node and to implement a worker thread pool.
With the new architecture things improved a lot, all the overhead
of context switching has gone.

I defined a unit of work as one iteration of one node (checking if
new messages have come, processing messages, sending responses,
checking if it's time to run a periodic job, updating statistic).
I have a workqueue of above units and a pool of tasks that service
nodes.

The problem is that my poor implementation of workqueue is a 
bottleneck. A task takes a unit of work from a queue, processes it 
and puts it back at the and of the queue. Because the queue is 
Ada.Containers.Doubly_Linked_Lists there are lots of memory
allocations and deallocations - that's a performance problem.

I consider making a circular list of nodes with "Next_To_Service"
pointer going around as nodes are processed. I'll have to make
sure that one node can be served by only one task at the time
(probably by marking nodes as being served at the moment).
New nodes joining and old leaving the system will be more
difficult to implement correctly, I suppose.

What can you suggest?
I'm probably missing something obvious. 
Thanks in advance!

-- 
Wiktor Moskwa

Re: Workqueues in Ada

[Dmitry A. Kazakov]

On Sat, 28 Jul 2007 17:00:57 +0000 (UTC), Wiktor Moskwa wrote:

> The problem is that my poor implementation of workqueue is a 
> bottleneck. A task takes a unit of work from a queue, processes it 
> and puts it back at the and of the queue. Because the queue is 
> Ada.Containers.Doubly_Linked_Lists there are lots of memory
> allocations and deallocations - that's a performance problem.

I thought Ada.Containers.Doubly_Linked_Lists can move elements between
lists without copying. Have you checked that?

You could also try an alternative implementation of doubly-linked lists and
webs:

http://www.dmitry-kazakov.de/ada/components.htm#Generic_Doubly_Linked_Web

> I consider making a circular list of nodes with "Next_To_Service"
> pointer going around as nodes are processed. I'll have to make
> sure that one node can be served by only one task at the time
> (probably by marking nodes as being served at the moment).
> New nodes joining and old leaving the system will be more
> difficult to implement correctly, I suppose.

Make it a protected object. A worker task calls to an entry of, requesting
an item of work. The entry removes the first item from the list and returns
it to the task via pointer. When the worker task finishes dealing with the
item it calls to a protected object's procedure to queue the item back.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Workqueues in Ada

[Jeffrey R. Carter]

Wiktor Moskwa wrote:
> The problem is that my poor implementation of workqueue is a 
> bottleneck. A task takes a unit of work from a queue, processes it 
> and puts it back at the and of the queue. Because the queue is 
> Ada.Containers.Doubly_Linked_Lists there are lots of memory
> allocations and deallocations - that's a performance problem.

A simple thing to do would be to replace Doubly_Linked_Lists with a 
protected, bounded queue, such as PragmARC.Queue_Bounded[_Blocking]. 
This will also serve to validate that it's the dynamic nature of 
Doubly_Linked_Lists that is causing the problem.

The PragmAda Reusable Components are available at

http://pragmada.home.mchsi.com/

-- 
Jeff Carter
"C's solution to this [variable-sized array parameters] has real
problems, and people who are complaining about safety definitely
have a point."
Dennis Ritchie
25

Re: Workqueues in Ada

[Wiktor Moskwa]

On 28.07.2007, Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote:
> I thought Ada.Containers.Doubly_Linked_Lists can move elements between
> lists without copying. Have you checked that?

I think the problem is that each time a task takes a unit from the queue
Delete is called and just after it Append - without a custom storage
pool malloc and free are called very often.

> You could also try an alternative implementation of doubly-linked lists and
> webs:
>
> http://www.dmitry-kazakov.de/ada/components.htm#Generic_Doubly_Linked_Web

It looks promising, especially with an ability to pass a storage pool
as a generic parameter. I'll check it out.

> Make it a protected object. A worker task calls to an entry of, requesting
> an item of work. The entry removes the first item from the list and returns
> it to the task via pointer. When the worker task finishes dealing with the
> item it calls to a protected object's procedure to queue the item back.

That's how it works now - I forgot to mention that my list is wrapped in 
a protected object, otherwise it wouldn't work :)
My idea of using a circular list is to call Delete and Append only when
new node joins the system or an old one leaves. During normal operations
a task will request new unit of work without deleting it from the queue.
It will be only marked as "currently in use". Other tasks will skip
this node - Next_To_Service pointer will move clockwise skipping nodes
that are serviced at the moment.

Thanks for your reply Dmitry.

-- 
Wiktor Moskwa

Re: Workqueues in Ada

[Wiktor Moskwa]

On 28.07.2007, Jeffrey R. Carter <spam.jrcarter.not@acm.nospam.org> wrote:
> A simple thing to do would be to replace Doubly_Linked_Lists with a 
> protected, bounded queue, such as PragmARC.Queue_Bounded[_Blocking]. 
> This will also serve to validate that it's the dynamic nature of 
> Doubly_Linked_Lists that is causing the problem.
>
> The PragmAda Reusable Components are available at
>
> http://pragmada.home.mchsi.com/

If this queue is not dynamic but initially allocates a buffer to
store elements - it should solve my problem.
I'll try it and let you know.

Thanks!

-- 
Wiktor Moskwa

Re: Workqueues in Ada

[Simon Wright]

Wiktor Moskwa <wiktorDOTmoskwa@gmail.com> writes:

> My idea of using a circular list is to call Delete and Append only
> when new node joins the system or an old one leaves. During normal
> operations a task will request new unit of work without deleting it
> from the queue.  It will be only marked as "currently in use". Other
> tasks will skip this node - Next_To_Service pointer will move
> clockwise skipping nodes that are serviced at the moment.

Sounds very complicated & fragile to me, it no longer resembles
anything one would recognise as a 'queue'.

Would it help to have a queue of pointer-to-work-item? (depends on how
big a work-item is, because (I have a strong impression that)
Ada.Containers containers allocate/deallocate on Append/Delete).

It's hard to see how to avoid this with unbounded containers. You
could look at alternative container packages? (I normally wouldn't
suggest this, given Ada.Containers, but a BC.Comtainers.Queues.Bounded
from http://booch95.sf.net doesn't allocate .. but you have to know
the maximum number of elements you are going to need.)

Re: Workqueues in Ada

[Wiktor Moskwa]

On 28.07.2007, Jeffrey R. Carter <spam.jrcarter.not@acm.nospam.org> wrote:
> A simple thing to do would be to replace Doubly_Linked_Lists with a 
> protected, bounded queue, such as PragmARC.Queue_Bounded[_Blocking]. 
> This will also serve to validate that it's the dynamic nature of 
> Doubly_Linked_Lists that is causing the problem.

There is a little problem with using PragmAda components...
It seems to be incompatible with Ada 2005, that my program uses.

GNAT GPL 2007 outputs:
======
(Ada 2005) cannot copy object of a limited type (RM-2005 6.5(5.5/2))
consider switching to return of access type
=====

-- 
Wiktor Moskwa

Re: Workqueues in Ada

[Dmitry A. Kazakov]

On Sat, 28 Jul 2007 17:52:29 +0000 (UTC), Wiktor Moskwa wrote:

>> Make it a protected object. A worker task calls to an entry of, requesting
>> an item of work. The entry removes the first item from the list and returns
>> it to the task via pointer. When the worker task finishes dealing with the
>> item it calls to a protected object's procedure to queue the item back.
> 
> That's how it works now - I forgot to mention that my list is wrapped in 
> a protected object, otherwise it wouldn't work :)
> My idea of using a circular list is to call Delete and Append only when
> new node joins the system or an old one leaves. During normal operations
> a task will request new unit of work without deleting it from the queue.

Why? What I don't understand is why removing from a queue should deallocate
anything. It might be an artefact of Ada.Containers, but in general case it
is not unnecessary. Removing just means that it is the task who will hold
the item. Technically the item will be either in no list or in the list of
one item long owned by the task. You have one list of items waiting for
service and n lists of items being serviced, where n = number of worker
tasks. Interlocking is only necessary when you move an item from list to
list.

> It will be only marked as "currently in use". Other tasks will skip
> this node - Next_To_Service pointer will move clockwise skipping nodes
> that are serviced at the moment.

If you do this you would not need any lists, just a ring buffer of items.
With a relatively small number of worker tasks the overhead of skipping
items in use is not that big, but you will have another potential problem:
unbalanced servicing. When an item was serviced a bit longer than its
neighbours, it might miss its train of servicing. What is worse it could
become a systematic problem for some items with a huge impact in result.
Doubly-linked lists do not have this problem, while removing and inserting
overhead is just negligible. You can shuffle items between lists very
efficiently.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Workqueues in Ada

[Robert A Duff]

Wiktor Moskwa <wiktorDOTmoskwa@gmail.com> writes:

> There is a little problem with using PragmAda components...
> It seems to be incompatible with Ada 2005, that my program uses.
>
> GNAT GPL 2007 outputs:
> ======
> (Ada 2005) cannot copy object of a limited type (RM-2005 6.5(5.5/2))
> consider switching to return of access type
> =====

I would be very interested in seeing the code that causes this.

- Bob

Re: Workqueues in Ada

[Wiktor Moskwa]

On 28.07.2007, Robert A Duff <bobduff@shell01.TheWorld.com> wrote:
> Wiktor Moskwa <wiktorDOTmoskwa@gmail.com> writes:
>> GNAT GPL 2007 outputs:
>> ======
>> (Ada 2005) cannot copy object of a limited type (RM-2005 6.5(5.5/2))
>> consider switching to return of access type
>> =====
>
> I would be very interested in seeing the code that causes this.

Here you are:
======
procedure Sample is

   generic
      type Element is limited private;
   package Pkg is
      function Get return Element;
   end Pkg;
	     
   package body Pkg is
      Item : Element;
      
      function Get return Element is
      begin
         return Item;
      end Get;
   end Pkg;
						    
   package P
     is new Pkg (Integer);
						       
   X : Integer := P.Get;

begin
   null;
end Sample;
======

-- 
Wiktor Moskwa

Re: Workqueues in Ada

[Wiktor Moskwa]

On 28.07.2007, Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote:
> Why? What I don't understand is why removing from a queue should deallocate
> anything. It might be an artefact of Ada.Containers, but in general case it
> is not unnecessary. Removing just means that it is the task who will hold
> the item. Technically the item will be either in no list or in the list of
> one item long owned by the task. You have one list of items waiting for
> service and n lists of items being serviced, where n = number of worker
> tasks. Interlocking is only necessary when you move an item from list to
> list.

In GNAT GPL 2007 implementation of Doubly_Linked_Lists an Element is kept
in a limited record called Node. When Append is called, new Node is
created and when Delete - Free(Node) is called. Everything happens in
a default storage pool and is transpated to malloc and free.

Could you elaborate the concept of having an additional list of items
per task? When it can be useful? I'm interested.

> If you do this you would not need any lists, just a ring buffer of items.

That's the name I was looking for :)

> With a relatively small number of worker tasks the overhead of skipping
> items in use is not that big, but you will have another potential problem:
> unbalanced servicing. When an item was serviced a bit longer than its
> neighbours, it might miss its train of servicing. What is worse it could
> become a systematic problem for some items with a huge impact in result.

I agree, I haven't consider balancing yet.

> Doubly-linked lists do not have this problem, while removing and inserting
> overhead is just negligible. You can shuffle items between lists very
> efficiently.

If you could write more about using more lists... thanks!

-- 
Wiktor Moskwa

Re: Workqueues in Ada

[Wiktor Moskwa]

On 28.07.2007, Simon Wright <simon.j.wright@mac.com> wrote:
> Sounds very complicated & fragile to me, it no longer resembles
> anything one would recognise as a 'queue'.
>

It seems that my 'circular queue' idea was a blind alley.

> It's hard to see how to avoid this with unbounded containers. You
> could look at alternative container packages? (I normally wouldn't
> suggest this, given Ada.Containers, but a BC.Comtainers.Queues.Bounded
> from http://booch95.sf.net doesn't allocate .. but you have to know
> the maximum number of elements you are going to need.)

I think it can be done with unbounded containers provided that
a custom storage pool can be used. The pool would allocate memory
in chunks for i.e. 100 items and thus only 1 call in 100 would
result in malloc call. Deleted items would make place for new ones
and so on.

-- 
Wiktor Moskwa

Re: Workqueues in Ada

[Robert A Duff]

Wiktor Moskwa <wiktorDOTmoskwa@gmail.com> writes:

> On 28.07.2007, Robert A Duff <bobduff@shell01.TheWorld.com> wrote:
>> Wiktor Moskwa <wiktorDOTmoskwa@gmail.com> writes:
>>> GNAT GPL 2007 outputs:
>>> ======
>>> (Ada 2005) cannot copy object of a limited type (RM-2005 6.5(5.5/2))
>>> consider switching to return of access type
>>> =====
>>
>> I would be very interested in seeing the code that causes this.
>
> Here you are:

Well, thanks, but I really meant I'd like to see which part of PragmARC
is causing trouble.  I assume the following is a cut-down example,
right?

What about it, Jeff?  Do you plan to update your components to be Ada
2005 compatible?

> ======
> procedure Sample is
>
>    generic
>       type Element is limited private;
>    package Pkg is
>       function Get return Element;
>    end Pkg;
>
>    package body Pkg is
>       Item : Element;
>       
>       function Get return Element is
>       begin
>          return Item;

Right, this is illegal in Ada 2005.  The fix is probably to remove
"limited" from Element, above, but I'd have to see the actual code to be
sure.  The compiler suggests, "consider switching to return of access
type", but I think that's bogus.

Note that in Ada 95, the above "return" has some rather strange
behavior in some cases.  Still, the fact that it was legal Ada, and is
now illegal, is rather annoying.

- Bob

P.S. I was one of the people who worked on implementing the new Ada 2005
limited-types stuff in GNAT.

Re: Workqueues in Ada

[Robert A Duff]

Wiktor Moskwa <wiktorDOTmoskwa@gmail.com> writes:

> The problem is that my poor implementation of workqueue is a 
> bottleneck. A task takes a unit of work from a queue, processes it 
> and puts it back at the and of the queue. Because the queue is 
> Ada.Containers.Doubly_Linked_Lists there are lots of memory
> allocations and deallocations - that's a performance problem.

I'm not clear on exactly what you're trying to do, but it sounds like
"units of work" get created and destroyed a lot less often than they get
added to and removed from the queue.  Consider using a doubly-linked
list with the links threaded through the units of work, so
adding/removing doesn't need to allocate/free anything -- just stir a
few pointers around.

> I consider making a circular list of nodes with "Next_To_Service"
> pointer going around as nodes are processed. I'll have to make
> sure that one node can be served by only one task at the time
> (probably by marking nodes as being served at the moment).
> New nodes joining and old leaving the system will be more
> difficult to implement correctly, I suppose.

I think the "marking nodes" thing is probably not a good idea.
It's complicated, and it doesn't scale well.

But if you have a max number of items in the queue at any time,
a circular buffer of pointers to units-of-work would do just fine.
The max number could be calculated at run time, and you could
even make it growable, if you wanted to (in which case "max" is a
misnomer.  ;-))

- Bob

Re: Workqueues in Ada

[Wiktor Moskwa]

On 28.07.2007, Robert A Duff <bobduff@shell01.TheWorld.com> wrote:
>> On 28.07.2007, Robert A Duff <bobduff@shell01.TheWorld.com> wrote:
>>> Wiktor Moskwa <wiktorDOTmoskwa@gmail.com> writes:
>>>
>>> I would be very interested in seeing the code that causes this.
>>
>> Here you are:
>
> Well, thanks, but I really meant I'd like to see which part of PragmARC
> is causing trouble.  I assume the following is a cut-down example,
> right?

I just wanted to give "a simple reproductive test-case" :)
In PragmARC most packages get a limited private generic type (called
Element) as an argument. Above error arises in components' Get functions 
that return Element.

> Right, this is illegal in Ada 2005.  The fix is probably to remove
> "limited" from Element, above, but I'd have to see the actual code to be
> sure.  The compiler suggests, "consider switching to return of access
> type", but I think that's bogus.

It doesn't look easy to port such code to Ada 2005 without removing 
"limited". It would probably mean switching whole library to use a lot 
of access types instead of "implicit passing by reference" which is now.

> P.S. I was one of the people who worked on implementing the new Ada 2005
> limited-types stuff in GNAT.

Nice to hear :) Limited types idea seems quite difficult to me. I don't
understand why limited "in" arguments can be passed by reference to a 
procedure but "out" can't (probably because after passing object to
the caller that object can finish its life but it's still fuzzy).
I had lots of problems with tagged types too. I wonder if using 
access parameters everywhere is a remedy for all troubles in Ada 2005.

-- 
Wiktor Moskwa

Re: Workqueues in Ada

[Robert A Duff]

Wiktor Moskwa <wiktorDOTmoskwa@gmail.com> writes:

> In PragmARC most packages get a limited private generic type (called
> Element) as an argument. Above error arises in components' Get functions 
> that return Element.

I presume they are intended to return a COPY of the element,
so "limited" doesn't seem appropriate on the formal type.

>> Right, this is illegal in Ada 2005.  The fix is probably to remove
>> "limited" from Element, above, but I'd have to see the actual code to be
>> sure.  The compiler suggests, "consider switching to return of access
>> type", but I think that's bogus.
>
> It doesn't look easy to port such code to Ada 2005 without removing 
> "limited".

Agreed.

 It would probably mean switching whole library to use a lot 
> of access types instead of "implicit passing by reference" which is now.

Well, it's just function returns that would have to change,
but that would probably be an earthquake.


> Nice to hear :) Limited types idea seems quite difficult to me.

A limited type is a type where it doesn't make sense to copy objects.

>...I don't
> understand why limited "in" arguments can be passed by reference to a 
> procedure but "out" can't

All limited parameters are passed (implicitly) by reference.
Same for all tagged types.  This applies to "in", "out"
and "in out".

The interesting case (new to Ada 2005) is function returns,
which are "build in place" for limited types (except for
limited types whose full type is nonlimited).

>... (probably because after passing object to
> the caller that object can finish its life but it's still fuzzy).
> I had lots of problems with tagged types too. I wonder if using 
> access parameters everywhere is a remedy for all troubles in Ada 2005.

No, I think it's better not to use access types "everywhere".

- Bob

Re: Workqueues in Ada

[Jeffrey R. Carter]

Wiktor Moskwa wrote:
> 
> There is a little problem with using PragmAda components...
> It seems to be incompatible with Ada 2005, that my program uses.
> 
> GNAT GPL 2007 outputs:
> ======
> (Ada 2005) cannot copy object of a limited type (RM-2005 6.5(5.5/2))
> consider switching to return of access type
> =====

The PragmARCs are Ada 95. There are a number of functions that return 
record components of a generic formal limited private type. I think the 
thing to do for Ada 07 is change places where they have something like

return Node.Value;

to

return Result : Element do
    Assign (To => Result, From => Node.Value);
end return;

That introduces a copy that isn't necessarily required in Ada 95.

-- 
Jeff Carter
"C's solution to this [variable-sized array parameters] has real
problems, and people who are complaining about safety definitely
have a point."
Dennis Ritchie
25

Re: Workqueues in Ada

[Jeffrey R. Carter]

Robert A Duff wrote:
> 
> What about it, Jeff?  Do you plan to update your components to be Ada
> 2005 compatible?

Once we have multiple compilers available, I will probably look into 
that. Some of the functionality is now duplicated in the standard 
library, and I may revise the data structure components to be more like 
Ada.Containers, and base the unbounded structures on 
Ada.Containers.Doubly_Linked_List.

> Note that in Ada 95, the above "return" has some rather strange
> behavior in some cases.  Still, the fact that it was legal Ada, and is
> now illegal, is rather annoying.

Indeed.

-- 
Jeff Carter
"C's solution to this [variable-sized array parameters] has real
problems, and people who are complaining about safety definitely
have a point."
Dennis Ritchie
25

Re: Workqueues in Ada

[Jeffrey R. Carter]

Robert A Duff wrote:
> 
> A limited type is a type where it doesn't make sense to copy objects.

Not necessarily, due to Ada 83 relating assignment and "=". A limited 
private generic formal type is the only way to formally specify that the 
generic does not use "=" for the type.

-- 
Jeff Carter
"C's solution to this [variable-sized array parameters] has real
problems, and people who are complaining about safety definitely
have a point."
Dennis Ritchie
25

Re: Workqueues in Ada

[Dmitry A. Kazakov]

On Sat, 28 Jul 2007 21:19:10 +0000 (UTC), Wiktor Moskwa wrote:

> On 28.07.2007, Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote:

>> Why? What I don't understand is why removing from a queue should deallocate
>> anything. It might be an artefact of Ada.Containers, but in general case it
>> is not unnecessary. Removing just means that it is the task who will hold
>> the item. Technically the item will be either in no list or in the list of
>> one item long owned by the task. You have one list of items waiting for
>> service and n lists of items being serviced, where n = number of worker
>> tasks. Interlocking is only necessary when you move an item from list to
>> list.
> 
> In GNAT GPL 2007 implementation of Doubly_Linked_Lists an Element is kept
> in a limited record called Node. When Append is called, new Node is
> created and when Delete - Free(Node) is called. Everything happens in
> a default storage pool and is transpated to malloc and free.

Doesn't it have "move X from the list A to the list B?" That should not
have any node allocation / deallocation overhead. In "simple components"
Append, Insert, Prepend have a version which takes the item from another or
same list and places it where required.

> Could you elaborate the concept of having an additional list of items
> per task? When it can be useful? I'm interested.

The concept is that interlocking of the items is list-based. So you have
lists:

   Waiting_For_Service               -- Nobody touches this
   Being_Serviced_By_Worker_1 -- Only the worker 1 has access
   Being_Serviced_By_Worker_2 -- Only the worker 2 has access
   ...

You create items of work only once and then just move them across the
lists. Nobody can do any harm to an item which is not in its list. This is
the standard way OS schedulers and I/O systems are designed.

>> Doubly-linked lists do not have this problem, while removing and inserting
>> overhead is just negligible. You can shuffle items between lists very
>> efficiently.
> 
> If you could write more about using more lists... thanks!

OK, I'll bite, here is a working implementation of. It uses simple
components, but I guess you could do something equivalent with
Ada.Containers, probably it would require adding a list to each worker and
using move-service-move instead of remove-service-append. Anyway:

with Ada.Finalization;
with Generic_Doubly_Linked;

package Scheduler is
--
-- Job -- Abstract piece of work
--
   type Job is
      abstract new Ada.Finalization.Controlled with
         null record;
   procedure Do_It (Work : in out Job) is abstract;
   
   package Job_List is new Generic_Doubly_Linked (Job'Class);
   use Job_List.Doubly_Linked;
--
-- Worker -- A task doing jobs
--
   task type Worker is
   end Worker;
--
-- Submit -- A new job for processing
--
   procedure Submit (Work : Item);
--
-- Print_Me -- A concrete job, prints some text
--
   type Print_Me (Length : Natural) is new Job with record
      Text : String (1..Length);
   end record;
   procedure Do_It (Work : in out Print_Me);
   function Have_To_Print (Text : String) return Item;   

end Scheduler;
---------------------------------
package body Scheduler is

   protected Waiting_Queue is
      entry Get_For_Service (Work : out Item);
      procedure Submit (Work : Item);
   private
      Queue : List;
   end Waiting_Queue;

   protected body Waiting_Queue is
      entry Get_For_Service (Work : out Item)
         when Queue /= null is
      begin
         Work := Item (Queue);  -- The first in the list
         Remove (Queue, Work); -- Remove it from there
      end Get_For_Service;
      
      procedure Submit (Work : Item) is
      begin
         Append (Queue, Work); -- Add to the end
      end Submit;
      
   end Waiting_Queue;

   task body Worker is
      This : Item;
   begin
      loop
         Waiting_Queue.Get_For_Service (This);
         -- Now we are holding This, so be careful with exceptions,
         -- the item must back to the queue in all cases
         begin
            This.Do_It;
               -- Item was serviced, return it back
            Waiting_Queue.Submit (This);
         exception
            when others =>
               Waiting_Queue.Submit (This);
               raise;
         end;
      end loop;
   end Worker;

   procedure Submit (Work : Item) is
   begin
      Waiting_Queue.Submit (Work);
   end Submit;

   procedure Do_It (Work : in out Print_Me) is
   begin
      Put_Line (Work.Text);
   end Do_It;

   function Have_To_Print (Text : String) return Item is
   begin
      return
         new Print_Me'
             (  Job
             with
                Length => Text'Length,
                Text   => Text
             );
   end Have_To_Print;

end Scheduler;
------------------------------
Now a test program:

with Scheduler;  use Scheduler;

procedure Test_Scheduler is
   W1 : Worker;
   W2 : Worker;
   W3 : Worker;
   W4 : Worker;
   W5 : Worker;

begin
   Submit (Have_To_Print ("The"));
   Submit (Have_To_Print ("quick"));
   Submit (Have_To_Print ("brown"));
   Submit (Have_To_Print ("fox"));
   Submit (Have_To_Print ("jumps"));
   Submit (Have_To_Print ("over"));
   Submit (Have_To_Print ("the"));
   Submit (Have_To_Print ("lazy"));
   Submit (Have_To_Print ("dog"));
   -- This will never end!
end Test_Scheduler;

Here 5 workers are printing 9 different texts. GNAT implementation of
Put_Line is interlocked, so you would not see a mess of characters, but
properly formed lines in some arbitrary order.

Observe that the program will never end. You should add some on-exiting
stuff, which I have omitted to simplify the program. Upon exiting you would
terminate workers and clean the queue up.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Workqueues in Ada

[Wiktor Moskwa]

On 29.07.2007, Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote:
>
> Doesn't it have "move X from the list A to the list B?" That should not
> have any node allocation / deallocation overhead. In "simple components"
> Append, Insert, Prepend have a version which takes the item from another or
> same list and places it where required.

Unfortunately it doesn't have such operation.
But I'm playing with your components at the moment.

>> Could you elaborate the concept of having an additional list of items
>> per task? When it can be useful? I'm interested.
>
> The concept is that interlocking of the items is list-based. So you have
> lists:
>
>    Waiting_For_Service               -- Nobody touches this
>    Being_Serviced_By_Worker_1 -- Only the worker 1 has access
>    Being_Serviced_By_Worker_2 -- Only the worker 2 has access
>    ...
>
> You create items of work only once and then just move them across the
> lists. Nobody can do any harm to an item which is not in its list. This is
> the standard way OS schedulers and I/O systems are designed.

Now I see, thanks for clarification.


>> If you could write more about using more lists... thanks!
>
> OK, I'll bite, here is a working implementation of. It uses simple
> components, but I guess you could do something equivalent with
> Ada.Containers, probably it would require adding a list to each worker and
> using move-service-move instead of remove-service-append. Anyway:
>
> [...]
>
> Here 5 workers are printing 9 different texts. GNAT implementation of
> Put_Line is interlocked, so you would not see a mess of characters, but
> properly formed lines in some arbitrary order.
>
> Observe that the program will never end. You should add some on-exiting
> stuff, which I have omitted to simplify the program. Upon exiting you would
> terminate workers and clean the queue up.

Thanks for your replies and an example. I'll implement a list per worker 
using your "webs" and see how it works.

-- 
Wiktor Moskwa

Re: Workqueues in Ada

[Niklas Holsti]

Wiktor Moskwa wrote:
> On 29.07.2007, Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote:
> 
>>Doesn't it have "move X from the list A to the list B?" That should not
>>have any node allocation / deallocation overhead. In "simple components"
>>Append, Insert, Prepend have a version which takes the item from another or
>>same list and places it where required.
> 
> 
> Unfortunately it doesn't have such operation.

Ada.Containers.Doubly_Linked_Lists has this operation:

    procedure Splice (Target   : in out List;
                      Before   : in     Cursor;
                      Source   : in out List;
                      Position : in out Cursor);

The description (in RM A.18.3(114/2)) says: "... the element designated 
by Position is removed from Source and moved to Target, immediately 
prior to Before, ...".

This seems to do what Dmitry suggested.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

Re: Workqueues in Ada

[Matthew Heaney]

On Jul 28, 1:00 pm, Wiktor Moskwa <wiktorDOTmos...@gmail.com> wrote:
>
> The problem is that my poor implementation of workqueue is a
> bottleneck. A task takes a unit of work from a queue, processes it
> and puts it back at the and of the queue. Because the queue is
> Ada.Containers.Doubly_Linked_Lists there are lots of memory
> allocations and deallocations - that's a performance problem.

You can work around that using the Splice operations, which move nodes
from one list container to another.  You could use one list as a kind
of free-store, from where you get new nodes.  Instead of Deleting a
node from a list, splice it onto the free-store list; this eliminates
deallocation.

Re: Workqueues in Ada

[Matthew Heaney]

On Jul 29, 4:36 am, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de>
wrote:

>
> Doesn't it have "move X from the list A to the list B?" That should not
> have any node allocation / deallocation overhead. In "simple components"
> Append, Insert, Prepend have a version which takes the item from another or
> same list and places it where required.

Yes, the standard list container has such an operation, called
Splice.  That operation can be used to solve the problem of allocation
and deallocation, by using a separate list as a free-store for nodes.

Re: Workqueues in Ada

[Matthew Heaney]

On Jul 29, 3:53 pm, Wiktor Moskwa <wiktorDOTmos...@gmail.com> wrote:

>
> Unfortunately it doesn't have such operation.

The standard container library has such an operation, called Splice.

Re: Workqueues in Ada

[Matthew Heaney]

On Jul 30, 2:47 am, Niklas Holsti <niklas.hol...@nospam.please> wrote:


> Ada.Containers.Doubly_Linked_Lists has this operation:

[Description of Splice snipped]

> This seems to do what Dmitry suggested.

Yes, that's the exact intent.  You can implement a queue or ring or
whatever using the standard list container.

Re: Workqueues in Ada

[Wiktor Moskwa]

On 30.07.2007, Matthew Heaney <mheaney@on2.com> wrote:
> On Jul 29, 3:53 pm, Wiktor Moskwa <wiktorDOTmos...@gmail.com> wrote:
>>
>> Unfortunately it doesn't have such operation.
>
> The standard container library has such an operation, called Splice.
>

Thanks for correction.
Of course Splice is what we were looking for.

-- 
Wiktor Moskwa

Re: Workqueues in Ada

[Wiktor Moskwa]

On 30.07.2007, Matthew Heaney <mheaney@on2.com> wrote:
> Yes, the standard list container has such an operation, called
> Splice.  That operation can be used to solve the problem of allocation
> and deallocation, by using a separate list as a free-store for nodes.
>

I've implemeted work queues as advised using Splice that I didn't 
notice for the first time (thanks for pointing it).
Everything works as its supposed to. No more memory allocations,
peformance has increased by around 8% and I could identify
other issues.

Using standard containers was the easiest solution for me.
Just a few thoughts about Jeffrey's and Dmitry's libraries:
 - PragmARC - it didn't compile with my Ada 2005 program but I liked its 
   bounded lists/queues idea and internal structure was very interesting
 - Simple Components - idea of "webs of lists" and a possibility to use
   a custom storage pool seem interesting but I just couldn't tame 
   access types there - Node is Web, List is Node, everything is access,
   I wasn't able to integrate it with my current code - too difficult
   at the moment

Thanks for all responses everyone! 

-- 
Wiktor Moskwa

Re: Workqueues in Ada

[Dmitry A. Kazakov]

On Tue, 31 Jul 2007 20:54:46 +0000 (UTC), Wiktor Moskwa wrote:

>  - Simple Components - idea of "webs of lists" and a possibility to use
>    a custom storage pool seem interesting but I just couldn't tame 
>    access types there - Node is Web, List is Node, everything is access,

Yes, for a doubly-linked list there is no difference between a list and an
item of. One can use them interchangeably. Two different types were
introduced to prevent leaks when an item being removed from the list is
also the current head of. All is access to prevent any copying.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de