Hi,

I'm trying to implement unbounded concurrent queues and I wonder which
behavior would be expected when the implementation needs to allocate a
dynamic resource and the resources are not available. Should the push
blocking operations behave as if the queue was full when there is no
more memory or should the operation just throw bad_alloc?

As requesting external memory could be blocking, does it means that
non-blocking operations can not use general allocation mechanisms?
Should implementation of these kind of queues use an internal pool?

Which queue_op_status for non-blocking operations would be returned when
there is no non-blocking memory available ? Do we need a new literal?
queue_op_status::no_memory_available?

Does it means that lock-free unbounded queue can not be implemented
without blocking on the worst case?

Best,
Vicente


--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en.



.

On 4/1/13, Vicente J. Botet Escriba <vicente.botet@wanadoo.fr> wrote:
> I'm trying to implement unbounded concurrent queues and I
> wonder which behavior would be expected when the implementation
> needs to allocate a dynamic resource and the resources are not
> available. Should the push blocking operations behave as if
> the queue was full when there is no more memory or should the
> operation just throw bad_alloc?

My expectation is that programmers will want "unbounded" to not
wait for pops, and hence the operation should throw bad_alloc.
I can see a variant of queues where the programmer does not specify
a bound, but permits the implementation to pick a bound based on
system effects.  In that case, it should act as full.

> As requesting external memory could be blocking, does it means that
> non-blocking operations can not use general allocation mechanisms?
> Should implementation of these kind of queues use an internal pool?

Interesting point.  I think what we need is a non-blocking allocator.
I.e. the allocation call can return busy.

In the absence of that allocator, I think non-blocking operations
should use an internal pool.

> Which queue_op_status for non-blocking operations would be
> returned when there is no non-blocking memory available?  Do we
> need a new literal?  queue_op_status::no_memory_available?

Why wouldn't this simple be status full?

> Does it means that lock-free unbounded queue can not be implemented
> without blocking on the worst case?

You can implement it intrusively.  I.e. the queue pointers are
embedded in the element being queued and the sender and receiver
are responsible for allocation.  Knowing when you can deallocate
is hard without a garbage collector.

I am not a fan of intrusive data structures, but sometimes they
seem necessary.

--
Lawrence Crowl

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en.



.

Le 02/04/13 23:44, Lawrence Crowl a =E9crit :
> On 4/1/13, Vicente J. Botet Escriba <vicente.botet@wanadoo.fr> wrote:
>> I'm trying to implement unbounded concurrent queues and I
>> wonder which behavior would be expected when the implementation
>> needs to allocate a dynamic resource and the resources are not
>> available. Should the push blocking operations behave as if
>> the queue was full when there is no more memory or should the
>> operation just throw bad_alloc?
> My expectation is that programmers will want "unbounded" to not
> wait for pops, and hence the operation should throw bad_alloc.
Agreed.
> I can see a variant of queues where the programmer does not specify
> a bound, but permits the implementation to pick a bound based on
> system effects.  In that case, it should act as full.
And block waiting for memory?
>
>> As requesting external memory could be blocking, does it means that
>> non-blocking operations can not use general allocation mechanisms?
>> Should implementation of these kind of queues use an internal pool?
> Interesting point.  I think what we need is a non-blocking allocator.
> I.e. the allocation call can return busy.
Good idea.
>
> In the absence of that allocator, I think non-blocking operations
> should use an internal pool.

which should again be non-blocking ;-)
>
>> Which queue_op_status for non-blocking operations would be
>> returned when there is no non-blocking memory available?  Do we
>> need a new literal?  queue_op_status::no_memory_available?
> Why wouldn't this simple be status full?
Humm,  full or busy?
>
>> Does it means that lock-free unbounded queue can not be implemented
>> without blocking on the worst case?
> You can implement it intrusively.  I.e. the queue pointers are
> embedded in the element being queued and the sender and receiver
> are responsible for allocation.  Knowing when you can deallocate
> is hard without a garbage collector.
Intrusive queues would avoid the problem but then the user would need a=20
lock-free allocator :(
Anyway, I don't the deallocation problem if a lock-free allocator is=20
available. The queue could have ownership of the nodes until the=20
consumer pops them, so there is a ownership transfer between the=20
producer and the consumer. Am I missing something?
> I am not a fan of intrusive data structures, but sometimes they
> seem necessary.
>
Agreed.

Vicente

--=20

---=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposa=
ls/?hl=3Den.



.

On 4/3/13, Vicente J. Botet Escriba <vicente.botet@wanadoo.fr> wrote:
> Le 02/04/13 23:44, Lawrence Crowl a =E9crit :
> > On 4/1/13, Vicente J. Botet Escriba <vicente.botet@wanadoo.fr> wrote:
> > > I'm trying to implement unbounded concurrent queues and I
> > > wonder which behavior would be expected when the implementation
> > > needs to allocate a dynamic resource and the resources are not
> > > available. Should the push blocking operations behave as if the
> > > queue was full when there is no more memory or should the operation
> > > just throw bad_alloc?
> >
> > My expectation is that programmers will want "unbounded" to not wait
> > for pops, and hence the operation should throw bad_alloc.
>
> Agreed.
>
> > I can see a variant of queues where the programmer does not specify
> > a bound, but permits the implementation to pick a bound based on
> > system effects.  In that case, it should act as full.
>
> And block waiting for memory?

It depends on the operation.  The simple push, yes.  For the non-waiting
push, no.

> > > As requesting external memory could be blocking, does it means that
> > > non-blocking operations can not use general allocation mechanisms?
> > > Should implementation of these kind of queues use an internal pool?
> >
> > Interesting point.  I think what we need is a non-blocking allocator.
> > I.e. the allocation call can return busy.
>
> Good idea.
>
> > In the absence of that allocator, I think non-blocking operations
> > should use an internal pool.
>
> which should again be non-blocking ;-)

Yes.

> > > Which queue_op_status for non-blocking operations would be returned
> > > when there is no non-blocking memory available?  Do we need a
> > > new literal?  queue_op_status::no_memory_available?
> >
> > Why wouldn't this simple be status full?
>
> Humm, full or busy?

Thinking out loud here.  If the queue has a finite but unspecified
size, then I think returning full is fine.  If the queue has infinite
size, then busy might be reasonable.

> > > Does it means that lock-free unbounded queue can not be implemented
> > > without blocking on the worst case?
> >
> > You can implement it intrusively.  I.e. the queue pointers are
> > embedded in the element being queued and the sender and receiver are
> > responsible for allocation.  Knowing when you can deallocate is hard
> > without a garbage collector.
>
> Intrusive queues would avoid the problem but then the user would
> need a lock-free allocator :(

Not necessarily, because the thread might do the allocation at a
time when waiting is not critical.

> Anyway, I don't the deallocation problem if a lock-free allocator
> is available. The queue could have ownership of the nodes until
> the consumer pops them, so there is a ownership transfer between
> the producer and the consumer. Am I missing something?

I think that can work, but the ownership information is conventional,
not enforced.  (It would be good to exploit move semantics through
the queue.)

> > I am not a fan of intrusive data structures, but sometimes they
> > seem necessary.
>
> Agreed.

--=20
Lawrence Crowl

--=20

---=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposa=
ls/?hl=3Den.



.