* Workqueues in Ada @ 2007-07-28 17:00 Wiktor Moskwa 2007-07-28 17:28 ` Dmitry A. Kazakov ` (3 more replies) 0 siblings, 4 replies; 29+ messages in thread From: Wiktor Moskwa @ 2007-07-28 17:00 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Workqueues in Ada 2007-07-28 17:00 Workqueues in Ada Wiktor Moskwa @ 2007-07-28 17:28 ` Dmitry A. Kazakov 2007-07-28 17:52 ` Wiktor Moskwa 2007-07-28 17:31 ` Jeffrey R. Carter ` (2 subsequent siblings) 3 siblings, 1 reply; 29+ messages in thread From: Dmitry A. Kazakov @ 2007-07-28 17:28 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Workqueues in Ada 2007-07-28 17:28 ` Dmitry A. Kazakov @ 2007-07-28 17:52 ` Wiktor Moskwa 2007-07-28 19:53 ` Simon Wright 2007-07-28 20:45 ` Dmitry A. Kazakov 0 siblings, 2 replies; 29+ messages in thread From: Wiktor Moskwa @ 2007-07-28 17:52 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Workqueues in Ada 2007-07-28 17:52 ` Wiktor Moskwa @ 2007-07-28 19:53 ` Simon Wright 2007-07-28 21:25 ` Wiktor Moskwa 2007-07-28 20:45 ` Dmitry A. Kazakov 1 sibling, 1 reply; 29+ messages in thread From: Simon Wright @ 2007-07-28 19:53 UTC (permalink / raw) 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.) ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Workqueues in Ada 2007-07-28 19:53 ` Simon Wright @ 2007-07-28 21:25 ` Wiktor Moskwa 0 siblings, 0 replies; 29+ messages in thread From: Wiktor Moskwa @ 2007-07-28 21:25 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Workqueues in Ada 2007-07-28 17:52 ` Wiktor Moskwa 2007-07-28 19:53 ` Simon Wright @ 2007-07-28 20:45 ` Dmitry A. Kazakov 2007-07-28 21:19 ` Wiktor Moskwa 1 sibling, 1 reply; 29+ messages in thread From: Dmitry A. Kazakov @ 2007-07-28 20:45 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Workqueues in Ada 2007-07-28 20:45 ` Dmitry A. Kazakov @ 2007-07-28 21:19 ` Wiktor Moskwa 2007-07-29 8:36 ` Dmitry A. Kazakov 0 siblings, 1 reply; 29+ messages in thread From: Wiktor Moskwa @ 2007-07-28 21:19 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Workqueues in Ada 2007-07-28 21:19 ` Wiktor Moskwa @ 2007-07-29 8:36 ` Dmitry A. Kazakov 2007-07-29 19:53 ` Wiktor Moskwa 2007-07-30 15:52 ` Matthew Heaney 0 siblings, 2 replies; 29+ messages in thread From: Dmitry A. Kazakov @ 2007-07-29 8:36 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Workqueues in Ada 2007-07-29 8:36 ` Dmitry A. Kazakov @ 2007-07-29 19:53 ` Wiktor Moskwa 2007-07-30 6:47 ` Niklas Holsti 2007-07-30 15:53 ` Matthew Heaney 2007-07-30 15:52 ` Matthew Heaney 1 sibling, 2 replies; 29+ messages in thread From: Wiktor Moskwa @ 2007-07-29 19:53 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Workqueues in Ada 2007-07-29 19:53 ` Wiktor Moskwa @ 2007-07-30 6:47 ` Niklas Holsti 2007-07-30 15:56 ` Matthew Heaney 2007-07-30 15:53 ` Matthew Heaney 1 sibling, 1 reply; 29+ messages in thread From: Niklas Holsti @ 2007-07-30 6:47 UTC (permalink / raw) 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 . @ . ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Workqueues in Ada 2007-07-30 6:47 ` Niklas Holsti @ 2007-07-30 15:56 ` Matthew Heaney 0 siblings, 0 replies; 29+ messages in thread From: Matthew Heaney @ 2007-07-30 15:56 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Workqueues in Ada 2007-07-29 19:53 ` Wiktor Moskwa 2007-07-30 6:47 ` Niklas Holsti @ 2007-07-30 15:53 ` Matthew Heaney 2007-07-30 19:57 ` Wiktor Moskwa 1 sibling, 1 reply; 29+ messages in thread From: Matthew Heaney @ 2007-07-30 15:53 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Workqueues in Ada 2007-07-30 15:53 ` Matthew Heaney @ 2007-07-30 19:57 ` Wiktor Moskwa 0 siblings, 0 replies; 29+ messages in thread From: Wiktor Moskwa @ 2007-07-30 19:57 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Workqueues in Ada 2007-07-29 8:36 ` Dmitry A. Kazakov 2007-07-29 19:53 ` Wiktor Moskwa @ 2007-07-30 15:52 ` Matthew Heaney 2007-07-31 20:54 ` Wiktor Moskwa 1 sibling, 1 reply; 29+ messages in thread From: Matthew Heaney @ 2007-07-30 15:52 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Workqueues in Ada 2007-07-30 15:52 ` Matthew Heaney @ 2007-07-31 20:54 ` Wiktor Moskwa 2007-08-01 8:30 ` Dmitry A. Kazakov 0 siblings, 1 reply; 29+ messages in thread From: Wiktor Moskwa @ 2007-07-31 20:54 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Workqueues in Ada 2007-07-31 20:54 ` Wiktor Moskwa @ 2007-08-01 8:30 ` Dmitry A. Kazakov 0 siblings, 0 replies; 29+ messages in thread From: Dmitry A. Kazakov @ 2007-08-01 8:30 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Workqueues in Ada 2007-07-28 17:00 Workqueues in Ada Wiktor Moskwa 2007-07-28 17:28 ` Dmitry A. Kazakov @ 2007-07-28 17:31 ` Jeffrey R. Carter 2007-07-28 17:56 ` Wiktor Moskwa 2007-07-28 20:18 ` Wiktor Moskwa 2007-07-28 21:54 ` Robert A Duff 2007-07-30 15:48 ` Matthew Heaney 3 siblings, 2 replies; 29+ messages in thread From: Jeffrey R. Carter @ 2007-07-28 17:31 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Workqueues in Ada 2007-07-28 17:31 ` Jeffrey R. Carter @ 2007-07-28 17:56 ` Wiktor Moskwa 2007-07-28 20:18 ` Wiktor Moskwa 1 sibling, 0 replies; 29+ messages in thread From: Wiktor Moskwa @ 2007-07-28 17:56 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Workqueues in Ada 2007-07-28 17:31 ` Jeffrey R. Carter 2007-07-28 17:56 ` Wiktor Moskwa @ 2007-07-28 20:18 ` Wiktor Moskwa 2007-07-28 20:48 ` Robert A Duff 2007-07-29 6:30 ` Jeffrey R. Carter 1 sibling, 2 replies; 29+ messages in thread From: Wiktor Moskwa @ 2007-07-28 20:18 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Workqueues in Ada 2007-07-28 20:18 ` Wiktor Moskwa @ 2007-07-28 20:48 ` Robert A Duff 2007-07-28 21:03 ` Wiktor Moskwa 2007-07-29 6:30 ` Jeffrey R. Carter 1 sibling, 1 reply; 29+ messages in thread From: Robert A Duff @ 2007-07-28 20:48 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Workqueues in Ada 2007-07-28 20:48 ` Robert A Duff @ 2007-07-28 21:03 ` Wiktor Moskwa 2007-07-28 21:38 ` Robert A Duff 0 siblings, 1 reply; 29+ messages in thread From: Wiktor Moskwa @ 2007-07-28 21:03 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Workqueues in Ada 2007-07-28 21:03 ` Wiktor Moskwa @ 2007-07-28 21:38 ` Robert A Duff 2007-07-28 22:12 ` Wiktor Moskwa 2007-07-29 6:34 ` Jeffrey R. Carter 0 siblings, 2 replies; 29+ messages in thread From: Robert A Duff @ 2007-07-28 21:38 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Workqueues in Ada 2007-07-28 21:38 ` Robert A Duff @ 2007-07-28 22:12 ` Wiktor Moskwa 2007-07-29 0:30 ` Robert A Duff 2007-07-29 6:34 ` Jeffrey R. Carter 1 sibling, 1 reply; 29+ messages in thread From: Wiktor Moskwa @ 2007-07-28 22:12 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Workqueues in Ada 2007-07-28 22:12 ` Wiktor Moskwa @ 2007-07-29 0:30 ` Robert A Duff 2007-07-29 6:38 ` Jeffrey R. Carter 0 siblings, 1 reply; 29+ messages in thread From: Robert A Duff @ 2007-07-29 0:30 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Workqueues in Ada 2007-07-29 0:30 ` Robert A Duff @ 2007-07-29 6:38 ` Jeffrey R. Carter 0 siblings, 0 replies; 29+ messages in thread From: Jeffrey R. Carter @ 2007-07-29 6:38 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Workqueues in Ada 2007-07-28 21:38 ` Robert A Duff 2007-07-28 22:12 ` Wiktor Moskwa @ 2007-07-29 6:34 ` Jeffrey R. Carter 1 sibling, 0 replies; 29+ messages in thread From: Jeffrey R. Carter @ 2007-07-29 6:34 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Workqueues in Ada 2007-07-28 20:18 ` Wiktor Moskwa 2007-07-28 20:48 ` Robert A Duff @ 2007-07-29 6:30 ` Jeffrey R. Carter 1 sibling, 0 replies; 29+ messages in thread From: Jeffrey R. Carter @ 2007-07-29 6:30 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Workqueues in Ada 2007-07-28 17:00 Workqueues in Ada Wiktor Moskwa 2007-07-28 17:28 ` Dmitry A. Kazakov 2007-07-28 17:31 ` Jeffrey R. Carter @ 2007-07-28 21:54 ` Robert A Duff 2007-07-30 15:48 ` Matthew Heaney 3 siblings, 0 replies; 29+ messages in thread From: Robert A Duff @ 2007-07-28 21:54 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Workqueues in Ada 2007-07-28 17:00 Workqueues in Ada Wiktor Moskwa ` (2 preceding siblings ...) 2007-07-28 21:54 ` Robert A Duff @ 2007-07-30 15:48 ` Matthew Heaney 3 siblings, 0 replies; 29+ messages in thread From: Matthew Heaney @ 2007-07-30 15:48 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 29+ messages in thread
end of thread, other threads:[~2007-08-01 8:30 UTC | newest] Thread overview: 29+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2007-07-28 17:00 Workqueues in Ada Wiktor Moskwa 2007-07-28 17:28 ` Dmitry A. Kazakov 2007-07-28 17:52 ` Wiktor Moskwa 2007-07-28 19:53 ` Simon Wright 2007-07-28 21:25 ` Wiktor Moskwa 2007-07-28 20:45 ` Dmitry A. Kazakov 2007-07-28 21:19 ` Wiktor Moskwa 2007-07-29 8:36 ` Dmitry A. Kazakov 2007-07-29 19:53 ` Wiktor Moskwa 2007-07-30 6:47 ` Niklas Holsti 2007-07-30 15:56 ` Matthew Heaney 2007-07-30 15:53 ` Matthew Heaney 2007-07-30 19:57 ` Wiktor Moskwa 2007-07-30 15:52 ` Matthew Heaney 2007-07-31 20:54 ` Wiktor Moskwa 2007-08-01 8:30 ` Dmitry A. Kazakov 2007-07-28 17:31 ` Jeffrey R. Carter 2007-07-28 17:56 ` Wiktor Moskwa 2007-07-28 20:18 ` Wiktor Moskwa 2007-07-28 20:48 ` Robert A Duff 2007-07-28 21:03 ` Wiktor Moskwa 2007-07-28 21:38 ` Robert A Duff 2007-07-28 22:12 ` Wiktor Moskwa 2007-07-29 0:30 ` Robert A Duff 2007-07-29 6:38 ` Jeffrey R. Carter 2007-07-29 6:34 ` Jeffrey R. Carter 2007-07-29 6:30 ` Jeffrey R. Carter 2007-07-28 21:54 ` Robert A Duff 2007-07-30 15:48 ` Matthew Heaney
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox