Re: A new queue has come

DynamicArrayBlockingQueue is now in the CVS.  Note that some methods are 
not implemented yet.  Also, I have to do some optimizations like keeping 
track of number of waiters to don't call notifyAll.


Also, I think that it could be possible to create a 
MoreEfficientDynamicArrayBlockingQueue via a cyclic list of arrays.

One goal could be to use System.arraycopy less often, which is very 
expensive (System.arraycopy is actually used when the queue is resized).

Another goal could be to improve scalability; many enqueue and/or many 
dequeue operation could run in parallel, without waiting.

I only have few, incompletes and maybe wrong ideas about this, so your 
help will be appreciated.

Suppose that our queue have 3 internal arrays for beginning, we could 
define logical queue index like that:

---------------------
| 0 | 3 | ... | n-2 |
--------------------

---------------------
| 1 | 4 | ... | n-1 |
---------------------

---------------------
| 2 | 5 | ... |  n  |
---------------------

We could have 1 enqueueIndex and 1 dequeueIndex by array.  So, with this 
structure, it's seems possible to have 3 concurrent, wait-free, enqueue 
and 3 concurrent, wait-free, dequeue...



Another implementation could have the following organization:

-----------------
| 0 | 1 | 2 | 3 |
-----------------

-----------------
| 4 | 5 | 6 | 7 |
-----------------

-------------------
| 8 | 9 | 10 | 11 |
-------------------

...

In this one, we can probably use System.arraycopy less often.

What do you think?

Jean M




-------------------------------------------------------
SF email is sponsored by - The IT Product Guide
Read honest & candid reviews on hundreds of IT Products from real users.
Discover which products truly live up to the hype. Start reading now. 
http://productguide.itmanagersjournal.com/