to const or not to const

[Kai-Uwe Bux]

Hi folks,


I recently dived into multi-threaded issues. To make my life a little
easier, I decided that it would be nice to have a simple fifo buffer to ease
communications between threads. The interface is this:

template < typename T >
class fifo {

public:

typedef T value_type;
typedef std::size_t size_type

fifo ( size_type n = -1 );

void push ( value_type const & value );

value_type pop ( void );
// blocks until an item is available

bool available ( void ) const;
// returns true if the a call to pop() would not block

void wait_available ( void ); // should this be const ?
// blocks until a call to pop() will not block

};

Typically there are some threads push()ing items into the fifo and one
thread pop()ing items off the buffer and processing them. It is clear that
push() and pop() should not be const: they change the contents of the
buffer. Also, availble() should be const since it just returns a property of
the buffer without modifying it.

But, what about wait_available()? Even though it does not change the buffer
contents by itself, once it returns it effectively signals to the thread
where it was called that another thread has pushed in item. So it marks a
change of the buffer, even though it does not in itself bring that change
about. Should this method be const or not?


Background [use cases in the consumer thread]

a)
while ( true ) {
event e = buffer.pop();
e.handle();
update_screen();
}

b)
while ( true ) {
buffer.wait_available();
while ( buffer.available() ) {
event e = buffer.pop();
e.handle();
}
update_screen();
}


Best

Kai-Uwe Bux

 

[munna]

Hi folks,

I recently dived into multi-threaded issues. To make my life a little
easier, I decided that it would be nice to have a simple fifo buffer to ease
communications between threads. The interface is this:  

  template < typename T >
  class fifo {

  public:

    typedef T value_type;
    typedef std::size_t size_type

    fifo ( size_type n = -1 );

    void push ( value_type const & value );

    value_type pop ( void );
    // blocks until an item is available

    bool available ( void ) const;
    // returns true if the a call to pop() would not block

    void wait_available ( void ); // should this be const ?
    // blocks until a call to pop() will not block

   };

Typically there are some threads push()ing items into the fifo and one
thread pop()ing items off the buffer and processing them. It is clear that
push() and pop() should not be const: they change the contents of the
buffer. Also, availble() should be const since it just returns a property of
the buffer without modifying it.

But, what about wait_available()? Even though it does not change the buffer
contents by itself, once it returns it effectively signals to the thread
where it was called that another thread has pushed in item. So it marks a
change of the buffer, even though it does not in itself bring that change
about. Should this method be const or not?

Background [use cases in the consumer thread]

a)
  while ( true ) {
    event e = buffer.pop();
    e.handle();
    update_screen();
  }

b)
  while ( true ) {
    buffer.wait_available();
    while ( buffer.available() ) {
      event e = buffer.pop();
      e.handle();
    }
    update_screen();
  }

Best

Kai-Uwe Bux

IMO, since you plan to make wait_available() a member function of
buffer class and since by itself it doesn't trigger any "state-change"
on "this" pointer, it should be made as a const function. But how does
the querying thread gets to know about the pushing of items by other
threads, just by calling this member? A callback perhaps? Just
curious...

 

[Kai-Uwe Bux]

Hi folks,

I recently dived into multi-threaded issues. To make my life a little
easier, I decided that it would be nice to have a simple fifo buffer to
ease communications between threads. The interface is this:

template < typename T >
class fifo {

public:

typedef T value_type;
typedef std::size_t size_type

fifo ( size_type n = -1 );

void push ( value_type const & value );

value_type pop ( void );
// blocks until an item is available

bool available ( void ) const;
// returns true if the a call to pop() would not block

void wait_available ( void ); // should this be const ?
// blocks until a call to pop() will not block

};

Typically there are some threads push()ing items into the fifo and one
thread pop()ing items off the buffer and processing them. It is clear
that push() and pop() should not be const: they change the contents of
the buffer. Also, availble() should be const since it just returns a
property of the buffer without modifying it.

But, what about wait_available()? Even though it does not change the
buffer contents by itself, once it returns it effectively signals to the
thread where it was called that another thread has pushed in item. So it
marks a change of the buffer, even though it does not in itself bring
that change about. Should this method be const or not?

Background [use cases in the consumer thread]

a)
while ( true ) {
event e = buffer.pop();
e.handle();
update_screen();
}

b)
while ( true ) {
buffer.wait_available();
while ( buffer.available() ) {
event e = buffer.pop();
e.handle();
}
update_screen();
}

Best

Kai-Uwe Bux

IMO, since you plan to make wait_available() a member function of
buffer class and since by itself it doesn't trigger any "state-change"
on "this" pointer, it should be made as a const function. But how does
the querying thread gets to know about the pushing of items by other
threads, just by calling this member? A callback perhaps? Just
curious...

The method wait_available() blocks its calling thread until the buffer is
non-empty. That means that in the consumer thread you could have something
like:

bool b; // only introduced for exposition
while ( b = buffer.available() ) // really = not ==
{
buffer.pop()
}
// now, b is false, i.e., the last call to available() returned false.
buffer.wait_available();
assert( b != buffer.available() ) // available() now returns true.

Clearly, the state of the buffer changed from before the call to
wait_available() to after the call; and predictably so, even though another
thread has to bring about the change. It's phenomena like this, that had me
reconsider whether wait_available() should be const.


Best

Kai-Uwe

 

[Jonathan Lee]

But, what about wait_available()? Even though it does not change the buffer
contents by itself, once it returns it effectively signals to the thread
where it was called that another thread has pushed in item.

There's no condition_variable data member that it modifies? Both C++0x
and Boost's condition_variable::wait() is non-const. My own event
queue
has such a member and thus my wait() is non-const.

Or.. you could force the function to be non-const by having a non-void
return value. Return the event at the front of the queue. Or a "null"
event if the wait() returns unexpectedly.

Anyway, I don't really see why it would _have_ to be const. In most
(all?)
use cases you're just gonna call pop() right after wait_available()
returns. i.e., it will have to be non-const sometime in the same
scope.

--Jonathan

 

[Alf P. Steinbach]

* Kai-Uwe Bux:

I recently dived into multi-threaded issues. To make my life a little
easier, I decided that it would be nice to have a simple fifo buffer to ease
communications between threads. The interface is this:

template < typename T >
class fifo {

public:

typedef T value_type;
typedef std::size_t size_type

fifo ( size_type n = -1 );

void push ( value_type const & value );

value_type pop ( void );
// blocks until an item is available

This method is very interesting. In a single-threaded program it should clearly
not be the basic interface but just a convenience wrapper around 'top' and
'remove_top', because the copying of value_type may throw after altering the
fifo state, preventing sound exception guarantee. But in a multi-threaded
environment how does one use the more primitive operations safely?

I can imagine that 'top' and 'remove_top' would be accessed within a block
protected by a mutex.

I think that mutex thingy should be exposed as part of the interface, and the
'pop' above an inline convenience method.

bool available ( void ) const;
// returns true if the a call to pop() would not block

void wait_available ( void ); // should this be const ?
// blocks until a call to pop() will not block

Here you're really into that problem but apparently not realizing, or perhaps I
don't understand the intended semantics. After 'available' indicates something
is available, how long is it available? Is there only ever 1 consumer?

};

Typically there are some threads push()ing items into the fifo and one
thread pop()ing items off the buffer and processing them. It is clear that
push() and pop() should not be const: they change the contents of the
buffer. Also, availble() should be const since it just returns a property of
the buffer without modifying it.

But, what about wait_available()? Even though it does not change the buffer
contents by itself, once it returns it effectively signals to the thread
where it was called that another thread has pushed in item. So it marks a
change of the buffer, even though it does not in itself bring that change
about. Should this method be const or not?

The question is rather, should this method be or not? ;-)


Cheers & hth.,

- Alf

 

[tonydee]

I recently dived into multi-threaded issues. To make my life a little
easier, I decided that it would be nice to have a simple fifo buffer to ease
communications between threads. The interface is this:  

  template < typename T >
  class fifo {

  public:

    typedef T value_type;
    typedef std::size_t size_type

    fifo ( size_type n = -1 );

    void push ( value_type const & value );

    value_type pop ( void );
    // blocks until an item is available

    bool available ( void ) const;
    // returns true if the a call to pop() would not block

    void wait_available ( void ); // should this be const ?
    // blocks until a call to pop() will not block

   };

Typically there are some threads push()ing items into the fifo and one
thread pop()ing items off the buffer and processing them. It is clear that
push() and pop() should not be const: they change the contents of the
buffer. Also, availble() should be const since it just returns a property of
the buffer without modifying it.

But, what about wait_available()? Even though it does not change the buffer
contents by itself, once it returns it effectively signals to the thread
where it was called that another thread has pushed in item. So it marks a
change of the buffer, even though it does not in itself bring that change
about. Should this method be const or not?

It should be const if it doesn't mutate the object's value itself.
For example, some thread might want to wait for these events, but just
count them... a const reference/pointer to the fifo should suffice.
But, a further thought below....

Background [use cases in the consumer thread]

a)
  while ( true ) {
    event e = buffer.pop();
    e.handle();
    update_screen();
  }

b)
  while ( true ) {
    buffer.wait_available();
    while ( buffer.available() ) {
      event e = buffer.pop();
      e.handle();
    }
    update_screen();
  }

I can see two possibilities:

- wait_available() waits on a condition variable / acquires a mutex, a
precondition for calling buffer.pop(). This would be efficient from a
locking perspective, but suggests buffer.pop() would be unsafe to call
without a prior wait_available()... not a good design, or

- wait_available() releases the mutex, only to have buffer.pop() have
to acquire it again... a little inefficient in this most-common usage.

Am I missing something?

Can't usage b) above be simplified to:

while (true) {
event e = buffer.pop();
e.handle();
if (not buffer.available())
update_screen();
}

Cheers,
Tony

 

[Kai-Uwe Bux]

* Kai-Uwe Bux:

This method is very interesting. In a single-threaded program it should
clearly not be the basic interface but just a convenience wrapper around
'top' and 'remove_top', because the copying of value_type may throw after
altering the fifo state, preventing sound exception guarantee.

Interesting point, but not very strong. Typically, one would use a fifo of
events or pointers to event and their copy constructors would not throw.

But in a
multi-threaded environment how does one use the more primitive operations
safely?

I can imagine that 'top' and 'remove_top' would be accessed within a block
protected by a mutex.

I think that mutex thingy should be exposed as part of the interface, and
the 'pop' above an inline convenience method.

No, one of the main advantages of the fifo class is to hide the mutex so
that client code does not have to get thread synchronization right. The
whole fifo class is the convenience wrapper around more primitive thread
synchronization mechanisms.

Here you're really into that problem but apparently not realizing, or
perhaps I don't understand the intended semantics. After 'available'
indicates something is available, how long is it available?

Until the next call to pop().

Is there only ever 1 consumer?

Yes, that is the use case.

Think of a fifo< event* >. There are multiple threads producing and
push()ing events. E.g., one thread can push() events signaling that a key
was pressed, another does something about buttons being clicked on, and a
third may watch a directory for files showing up or disappearing. The main
loop in _the_ consumer thread would just pop() events, handle them, and
update the screen.

The question is rather, should this method be or not? ;-)

I introduced the method to solve a particular problem and from the code in
front of me, I am pretty certain the method (or something equivalent in
power, convenience, and thread-issues-hiding) should be.


Best

Kai-Uwe Bux

 

[Kai-Uwe Bux]

There's no condition_variable data member that it modifies? Both C++0x
and Boost's condition_variable::wait() is non-const. My own event
queue
has such a member and thus my wait() is non-const.

Sure there is. But this member is not exported and there is a difference
between physical and logical constness. I could declare the mutex and
condition variables mutable.

Or.. you could force the function to be non-const by having a non-void
return value. Return the event at the front of the queue. Or a "null"
event if the wait() returns unexpectedly.

Huh? Could you please elaborate on this one: you are suggesting an
alternative interface, and unfortunately, I don't understand what it should
look like.

Anyway, I don't really see why it would _have_ to be const. In most
(all?)
use cases you're just gonna call pop() right after wait_available()
returns. i.e., it will have to be non-const sometime in the same
scope.

True, it's not a practical problem.


Best

Kai-Uwe Bux

 

[Kai-Uwe Bux]

It should be const if it doesn't mutate the object's value itself.
For example, some thread might want to wait for these events, but just
count them... a const reference/pointer to the fifo should suffice.
But, a further thought below....

The interface does not allow for counting items (yet).

Background [use cases in the consumer thread]

a)
while ( true ) {
event e = buffer.pop();
e.handle();
update_screen();
}

b)
while ( true ) {
buffer.wait_available();
while ( buffer.available() ) {
event e = buffer.pop();
e.handle();
}
update_screen();
}

I can see two possibilities:

- wait_available() waits on a condition variable / acquires a mutex, a
precondition for calling buffer.pop(). This would be efficient from a
locking perspective, but suggests buffer.pop() would be unsafe to call
without a prior wait_available()... not a good design, or

- wait_available() releases the mutex, only to have buffer.pop() have
to acquire it again... a little inefficient in this most-common usage.

Am I missing something?

No. It's the second one. Performance is not an issue, convenience and ease
of reasoning is.

Can't usage b) above be simplified to:

while (true) {
event e = buffer.pop();
e.handle();
if (not buffer.available())
update_screen();
}

Now, that's great! Thanks.


Best

Kai-Uwe Bux

 

[Jonathan Lee]

there is a difference between physical and logical constness.
I could declare the mutex and condition variables mutable.

Sure, but I'm not in the habit of declaring things mutable
unless I had a really good reason why wait_available()
_must_ be const. You don't seem to be in that position.

Huh? Could you please elaborate on this one: you are suggesting an
alternative interface, and unfortunately, I don't understand what it should
look like.

I just mean something like

Event e = buffer.wait_available(); // accomplishes wait() and pop()
if (e.valid())
e.handle();

Nothing big. But since wait_available() is almost always followed
by a true result from available(), and a pop(), you may as well do
it all in one. For the few times that wait_available() returns
and available() is false, just set the returned event to be
invalid.

If you do this, then wait_available() is obviously non-const.

--Jonathan

 

[Kai-Uwe Bux]

Sure, but I'm not in the habit of declaring things mutable
unless I had a really good reason why wait_available()
_must_ be const. You don't seem to be in that position.

Well, I posed the question because I was pondering alternatives. Currently,
I am leaning toward non-const. (Actually, I am leaning toward eliminating
wait_available() as tonydee has elsethread shown how I can do what I want
without).

I just mean something like

Event e = buffer.wait_available(); // accomplishes wait() and pop()
if (e.valid())
e.handle();

Nothing big. But since wait_available() is almost always followed
by a true result from available(), and a pop(), you may as well do
it all in one. For the few times that wait_available() returns
and available() is false, just set the returned event to be
invalid.

Probably, you are focusing on a different issue here: when there are
multiple consumers, wait_available() could return, yet the other consumer
picks the item. This is not, what I am worrying about. I just wanted to be
able to write a loop where I can handle several events and only update the
screen after the last of the available events has been processed. [Use case
(b) from my original post.]

If you do this, then wait_available() is obviously non-const.

Best

Kai-Uwe Bux

 

[Jonathan Lee]

Probably, you are focusing on a different issue here: when there are
multiple consumers, wait_available() could return, yet the other consumer
picks the item.

Well, I was worried about the fact that most wait() functions can
spuriously return. So wait_available() returning probably does not
guarantee that available() will be true, even with a single
consumer.

I'm pretty sure pthreads and boost both have caveats about spurious
wakeups. Not sure about windows or C++0x...

--Jonathan

 

[Kai-Uwe Bux]

Well, I was worried about the fact that most wait() functions can
spuriously return. So wait_available() returning probably does not
guarantee that available() will be true, even with a single
consumer.

Yeah, I read that in the posix man pages. Hence, my implementation of
wait_available() reads like this:

void wait_available ( void ) {
posix::guard data_guard ( data_lock );
while ( the_data.empty() ) {
data_guard.wait( non_empty );
}
}

For a single consumer thread, the return of the function does indicate that
there is some item waiting.


Best

Kai-Uwe Bux

 

[Balog Pal]

void wait_available ( void ); // should this be const ?
// blocks until a call to pop() will not block

But, what about wait_available()? Even though it does not change the
buffer
contents by itself, once it returns it effectively signals to the thread
where it was called that another thread has pushed in item. So it marks a
change of the buffer, even though it does not in itself bring that change
about. Should this method be const or not?

Normally my mutex and similar members are declared 'mutable' and functions
messing with them are const (if just do locking). Though a function shall
not leave with a changed state of a mutex (iow, it has a full critical
section), and document locking requirements as preconditions.

OTOH, your wait_available function is fishy as idea -- I can't imagine a
sensible use of it without a race condition introduced. By the time you
call that pop() the queue can be empty again. Or if you left a lock
running, you create an obligation to call one of a set of functions -- I do
that in some rare special cases, but prefer keeping the operation together.
Like a blocking version of pop().

Background [use cases in the consumer thread]

a)
while ( true ) {
event e = buffer.pop();
e.handle();
update_screen();
}

b)
while ( true ) {
buffer.wait_available();
while ( buffer.available() ) {
event e = buffer.pop();
e.handle();
}
update_screen();
}


Best

Kai-Uwe Bux

 

[tonydee]

This method is very interesting. In a single-threaded program it should clearly
not be the basic interface but just a convenience wrapper around 'top' and
'remove_top', because the copying of value_type may throw after altering the
fifo state, preventing sound exception guarantee. But in a multi-threaded
environment how does one use the more primitive operations safely?

Yes, same thoughts came to me, but I was too lazy to address it at the
time....

I can imagine that 'top' and 'remove_top' would be accessed within a block
protected by a mutex.

I think that mutex thingy should be exposed as part of the interface, and the
'pop' above an inline convenience method.

That sounds workable and clean from the perspective of this issue, but
doesn't a convenience function defeat the point? Sans pop(), it a bit
nasty from a usability perspective.

With a backyard hacker hat on, I might observe a great many copy
operations can't throw (especially if you ignore throws from new(),
discussed below), and pop() has an interesting characteristic: the
potential to "move" the object - which I think C++0x will facilitate
(?) - more efficiently than the Value& top() / void pop() semantics.
The simpler interface may become the better one in just a couple
years.

I remember reading an interesting article about the practicality of
trying to catch exceptions from memory allocation (i.e. new()), which
pointed out that most modern operating systems will do sparse memory
allocation, so unless the address space is smaller than the RAM+swap
(reasonably common for 32-bit apps / not for 64-bit), it's sure to get
the address space, and new won't throw. But, if an attempt is made to
page-fault in some of the memory supposedly allocated, then the "real"
allocation against RAM/swap takes place, and the application may
SIGSEGV. Point was, benefits of doing try/catch around new are
platform specific, and in modern practice you'll probably get more
production issues from more complex/verbose code than you'll
successfully handle during resource exhaustion....

Still, excellent points to bring into the design discussion. Thanks
Alf.

Cheers,
Tony

 

[Alf P. Steinbach]

* Balog Pal:

Interesting that this pop/top 'problem' is mentioned so much. In
practice I can't recall a single case -- the stuff I held in queues and
stacks just never had a throwing ctor. It was either some simple POD or
the equivalent of the unique_ptr. Even for single threaded stuff, but in
MT definitely the latter.

I do not want a fat copy inside a critical section. Let alone one that
calls system functions for memory and/or may throw.

Yah, the practical solution may just be to require non-throwing copying for the
items.

Anyway, I feel utterly stupid.

I'm looking at <url:
http://code.google.com/codejam/contest/dashboard?c=204113#s=a&a=2>, and they
say, "Behold, the Aha moment ..." -- and there's no Aha in my brain at all.

I'm assuming those colored lines are meant to be directional, after all it's a DAG.

But DAnG!


Cheers,

- Alf

 

[Balog Pal]

This method is very interesting. In a single-threaded program it should
clearly not be the basic interface but just a convenience wrapper around
'top' and 'remove_top', because the copying of value_type may throw after
altering the fifo state, preventing sound exception guarantee.

Interesting that this pop/top 'problem' is mentioned so much. In practice I
can't recall a single case -- the stuff I held in queues and stacks just
never had a throwing ctor. It was either some simple POD or the equivalent
of the unique_ptr. Even for single threaded stuff, but in MT definitely the
latter.

I do not want a fat copy inside a critical section. Let alone one that
calls system functions for memory and/or may throw.

 

[Balog Pal]

Anyway, I feel utterly stupid.

I'm looking at <url:
http://code.google.com/codejam/contest/dashboard?c=204113#s=a&a=2>, and
they say, "Behold, the Aha moment ..." -- and there's no Aha in my brain
at all.

I'm assuming those colored lines are meant to be directional, after all
it's a DAG.

IMO the left graph supposed to have arrows on all lines either up or down.

Tha AHA is probably reserved to those who learned graph theoty and still
remember it -- I don't qualify. ;-)

 

[Kai-Uwe Bux]

Yes, same thoughts came to me, but I was too lazy to address it at the
time....


That sounds workable and clean from the perspective of this issue, but
doesn't a convenience function defeat the point? Sans pop(), it a bit
nasty from a usability perspective.

With a backyard hacker hat on, I might observe a great many copy
operations can't throw (especially if you ignore throws from new(),
discussed below), and pop() has an interesting characteristic: the
potential to "move" the object - which I think C++0x will facilitate
(?) - more efficiently than the Value& top() / void pop() semantics.
The simpler interface may become the better one in just a couple
years.

I was thinking along the same lines. Would it be possible in C++0X to write
pop() with a strong exception safety guarantee? Something like: it does the
copy-construction internally and outside a move happens?

I remember reading an interesting article about the practicality of
trying to catch exceptions from memory allocation (i.e. new()), which
pointed out that most modern operating systems will do sparse memory
allocation, so unless the address space is smaller than the RAM+swap
(reasonably common for 32-bit apps / not for 64-bit), it's sure to get
the address space, and new won't throw. But, if an attempt is made to
page-fault in some of the memory supposedly allocated, then the "real"
allocation against RAM/swap takes place, and the application may
SIGSEGV. Point was, benefits of doing try/catch around new are
platform specific, and in modern practice you'll probably get more
production issues from more complex/verbose code than you'll
successfully handle during resource exhaustion....

Still, excellent points to bring into the design discussion.

Well, one could have the following interface:

template < typename T >
class fifo {

public:

typedef T value_type;
typedef std::size_t size_type


fifo ( size_type n = -1 );

void push ( value_type const & value );

class reader {
reader ( fifo & );
~reader ();
value_type const & top ( void ) const;
void pop ( void );
};

bool available ( void ) const;
// returns true if the a call to pop() would not block

void wait_available ( void ); // should this be const ?
// blocks until a call to pop() will not block

};

Now, in the consumer thread, one would have:

...
event e;
{
fifo< event >::reader hold_onto ( buffer );
e = hold_onto.top();
hold_onto.pop();
}
e.handle();
update_screen();
...

The constructor of the reader object would lock the buffer and wait until an
item becomes available. The destructor would unlock.


For the use cases, I have in mind, the above is overkill and makes client
code too messy. So, I think (as Alf suggested) that a convenience function
for non-throwing copy-constructors should be kept.


Best

Kai-Uwe Bux

 

[Kai-Uwe Bux]

Normally my mutex and similar members are declared 'mutable' and functions
messing with them are const (if just do locking). Though a function shall
not leave with a changed state of a mutex (iow, it has a full critical
section), and document locking requirements as preconditions.

OTOH, your wait_available function is fishy as idea -- I can't imagine a
sensible use of it without a race condition introduced. By the time
you
call that pop() the queue can be empty again.

If there are multiple consumer threads, that is very true. Therefore, pop()
also blocks until it can return a value. I hoped, the comment for pop()
would make that clear.

Or if you left a lock
running, you create an obligation to call one of a set of functions -- I
do that in some rare special cases, but prefer keeping the operation
together. Like a blocking version of pop().

Same here.