[concurrency-interest] Proposal WeightedLinkedBoundedQueue

David Holmes dcholmes at optusnet.com.au
Sat Nov 25 05:32:33 EST 2006


Heh Heh! I forgot about using an atomic to maintain the weight :)

Tim's generalised semaphore approach also sounds feasible - and much simpler
in terms of getting the blocking semantics for excess weight.

Cheers,
David
  -----Original Message-----
  From: concurrency-interest-bounces at cs.oswego.edu
[mailto:concurrency-interest-bounces at cs.oswego.edu]On Behalf Of Thierry
Hanot
  Sent: Friday, 24 November 2006 9:12 PM
  To: dholmes at ieee.org; concurrency-interest at cs.oswego.edu
  Subject: Re: [concurrency-interest] Proposal WeightedLinkedBoundedQueue


  Ok - but practically speaking how to you calculate the size/weight? We
often talk informally about lightweight and heavyweight objects, but we
don't actually have a simple means of quantifying that. Are you just working
on the basis that if the user can define some notion of "weight" then this
data structure can impose a weight limit?



  Yes because the weight depends a lot about the architecture of what you
are doing.

  For instance if you use a queue to store task, the weight of the task can
an estimation of the cost of the task ( refuse task if you want to be sure
to guarantee the execution in a certain amount of time). If for a reason or
another the task is also containing data used during the execution, then the
weight can be an estimation of its size.

  In my case the queue contains data to be store in a database. Each data is
referenced by a composite id and we have some other information about the
impact of the data. To avoid to have for each event the 3 objects (the
id,the data and the impacts). We have one event which is containing one id ,
n data and one compacted impact list.

  Then the size of an event is not 1. And when we want to avoid using to
much memory we need to use a weight estimation which instead of the count to
bound the queue.





  It seems rather special purpose. If weight was memory-usage, and we had a
way to measure that, then I could see use for this in some memory
constrained contexts.



  I agree, it's a bit specific. But the queues are very useful to have some
kind of "resource usage control".  The resource cannot be represented by the
counts of objects in the queue or by the memory but can be of any kind (
memory mostly but we can have network/cpu/disk .). And most of the
applications need the resource control (except if you have unlimited
resources)



  As it is I would think you could do this via a fairly simple wrapper, as
you'll need to track the cumulative weight as objects are added/removed.
You'll need stronger synchronization than provided by LinkedBlockingQueue
unless the weight-limit is allowed to be violated - so adding the sync in
the wrapper seems reasonable too.



  I was thinking of extending the LinkedBoundedQueue because we can
generalize all the principle in this queue easily. But the locks and
conditions are privateL.

  The main change in the code is:

  instead of using getAndIncrement(or decrement) we can use getAndAdd(+ or -
element.weigth) and  test the not full no anymore with an equality on
capacity but on >=.

  With this we can avoid any stronger synchronization ( even if we will
probably notify a bit too much the notFull condition).









  Cheers,

  David Holmes





  Best regards,

  Thierry Hanot



    -----Original Message-----
    From: concurrency-interest-bounces at cs.oswego.edu
[mailto:concurrency-interest-bounces at cs.oswego.edu]On Behalf Of Thierry
Hanot
    Sent: Thursday, 23 November 2006 9:43 PM
    To: dholmes at ieee.org; concurrency-interest at cs.oswego.edu
    Subject: Re: [concurrency-interest] Proposal WeightedLinkedBoundedQueue

    The weight is defined by the end user using a small interface yes.

    I use the term weight but size is also relevant J





    Thierry Hanot


----------------------------------------------------------------------------

    From: David Holmes [mailto:dcholmes at optusnet.com.au]
    Sent: jeudi 23 novembre 2006 01:26
    To: Thierry Hanot; concurrency-interest at cs.oswego.edu
    Subject: RE: [concurrency-interest] Proposal WeightedLinkedBoundedQueue



    How do you define and measure the "weight" of an object?



    David Holmes

      -----Original Message-----
      From: concurrency-interest-bounces at cs.oswego.edu
[mailto:concurrency-interest-bounces at cs.oswego.edu]On Behalf Of Thierry
Hanot
      Sent: Wednesday, 22 November 2006 10:18 PM
      To: concurrency-interest at cs.oswego.edu
      Subject: [concurrency-interest] Proposal WeightedLinkedBoundedQueue



      A small proposal for adding a new class in the concurrent package.

      All bounded collection are bounded to avoid to use to much memory.(At
least in my case J).

      But the element put in those collections are often with different
size.

      In my case  BoundedQueue is used as an event queue and we can have
composite events which contains itself many events.

      What do you think about adding some bounded collection no more based
on the count but on the sum of the weight of the object inside?



      After a quick look on the code of the LinkedBoundedQueue it seems
pretty easy to do.



      Does somebody else can see the advantage of this kind of object and is
there enough people interested to make it a part of the concurrent package?



      B.R





      Thierry Hanot


-------------- next part --------------
An HTML attachment was scrubbed...
URL: /pipermail/attachments/20061125/ee5587a1/attachment-0001.html 


More information about the Concurrency-interest mailing list