[concurrency-interest] Proposal WeightedLinkedBoundedQueue

Thierry Hanot thanot at infovista.com
Fri Nov 24 06:11:46 EST 2006


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 private:-(. 

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 :-)

	 

	 

	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 :-)).

		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/20061124/6e3047de/attachment-0001.html 


More information about the Concurrency-interest mailing list