to const or not to const

Discussion in 'C++' started by Kai-Uwe Bux, Apr 9, 2010.

  1. Kai-Uwe Bux

    Kai-Uwe Bux Guest

    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
    Kai-Uwe Bux, Apr 9, 2010
    #1
    1. Advertising

  2. Kai-Uwe Bux

    munna Guest

    On Apr 9, 8:22 am, Kai-Uwe Bux <> wrote:
    > 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...
    munna, Apr 9, 2010
    #2
    1. Advertising

  3. Kai-Uwe Bux

    Kai-Uwe Bux Guest

    munna wrote:

    > On Apr 9, 8:22 am, Kai-Uwe Bux <> wrote:
    >> 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
    Kai-Uwe Bux, Apr 9, 2010
    #3
  4. Kai-Uwe Bux

    Jonathan Lee Guest

    On Apr 8, 11:22 pm, Kai-Uwe Bux <> wrote:
    > 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
    Jonathan Lee, Apr 9, 2010
    #4
  5. * 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
    Alf P. Steinbach, Apr 9, 2010
    #5
  6. Kai-Uwe Bux

    tonydee Guest

    On Apr 9, 12:22 pm, Kai-Uwe Bux <> wrote:
    > 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
    tonydee, Apr 9, 2010
    #6
  7. Kai-Uwe Bux

    Kai-Uwe Bux Guest

    Alf P. Steinbach wrote:

    > * 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.


    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.


    >> 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?


    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.

    >> };
    >>
    >> 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? ;-)


    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, Apr 9, 2010
    #7
  8. Kai-Uwe Bux

    Kai-Uwe Bux Guest

    Jonathan Lee wrote:

    > On Apr 8, 11:22 pm, Kai-Uwe Bux <> wrote:
    >> 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.


    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, Apr 9, 2010
    #8
  9. Kai-Uwe Bux

    Kai-Uwe Bux Guest

    tonydee wrote:

    > On Apr 9, 12:22 pm, Kai-Uwe Bux <> wrote:
    >> 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....


    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
    Kai-Uwe Bux, Apr 9, 2010
    #9
  10. Kai-Uwe Bux

    Jonathan Lee Guest

    On Apr 9, 12:16 am, Kai-Uwe Bux <> wrote:
    > 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
    Jonathan Lee, Apr 9, 2010
    #10
  11. Kai-Uwe Bux

    Kai-Uwe Bux Guest

    Jonathan Lee wrote:

    > On Apr 9, 12:16 am, Kai-Uwe Bux <> wrote:
    >> 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.


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

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


    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
    Kai-Uwe Bux, Apr 9, 2010
    #11
  12. Kai-Uwe Bux

    Jonathan Lee Guest

    On Apr 9, 12:40 am, Kai-Uwe Bux <> wrote:
    > 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
    Jonathan Lee, Apr 9, 2010
    #12
  13. Kai-Uwe Bux

    Kai-Uwe Bux Guest

    Jonathan Lee wrote:

    > On Apr 9, 12:40 am, Kai-Uwe Bux <> wrote:
    >> 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.


    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
    Kai-Uwe Bux, Apr 9, 2010
    #13
  14. Kai-Uwe Bux

    Balog Pal Guest

    "Kai-Uwe Bux" <>

    > 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
    >
    Balog Pal, Apr 9, 2010
    #14
  15. Kai-Uwe Bux

    tonydee Guest

    On Apr 9, 12:53 pm, "Alf P. Steinbach" <> wrote:
    > >     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?


    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
    tonydee, Apr 9, 2010
    #15
  16. * Balog Pal:
    > "Alf P. Steinbach" <>
    >> 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.


    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
    Alf P. Steinbach, Apr 9, 2010
    #16
  17. Kai-Uwe Bux

    Balog Pal Guest

    "Alf P. Steinbach" <>
    > 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, Apr 9, 2010
    #17
  18. Kai-Uwe Bux

    Balog Pal Guest

    "Alf P. Steinbach" <>
    > 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. ;-)
    Balog Pal, Apr 9, 2010
    #18
  19. Kai-Uwe Bux

    Kai-Uwe Bux Guest

    tonydee wrote:

    > On Apr 9, 12:53 pm, "Alf P. Steinbach" <> wrote:
    >> > 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?

    >
    > 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 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, Apr 9, 2010
    #19
  20. Kai-Uwe Bux

    Kai-Uwe Bux Guest

    Balog Pal wrote:

    > "Kai-Uwe Bux" <>
    >
    >> 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.


    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.
    Kai-Uwe Bux, Apr 9, 2010
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    11
    Views:
    1,086
  2. Javier
    Replies:
    2
    Views:
    543
    James Kanze
    Sep 4, 2007
  3. 0m
    Replies:
    26
    Views:
    1,090
    Tim Rentsch
    Nov 10, 2008
  4. fungus
    Replies:
    13
    Views:
    871
    fungus
    Oct 31, 2008
  5. Replies:
    2
    Views:
    526
    Andrew Koenig
    Feb 9, 2009
Loading...

Share This Page