fifo

[Michele Moccia]

How can I implement a "time critical" fifo in c++ ?
I just have to manage sequences of raw bytes, no user defined types.
An std::queue<unsigned char> or std::deque<unsigned char> seems to be slow.
I've compared that to a platform depended solution (i tried to use a MS
Window pipe in the same process to create a fifo and it's very faster).

Many thanks
Michele Moccia

 

[Victor Bazarov]

How can I implement a "time critical" fifo in c++ ?

Think "circular buffer". You can probably easily wrap a vector or a deque
with two indices if you agree to have a limited size of your queue.

[...]

V

 

[Kai-Uwe Bux]

How can I implement a "time critical" fifo in c++ ?
I just have to manage sequences of raw bytes, no user defined types.
An std::queue<unsigned char> or std::deque<unsigned char> seems to be
slow. I've compared that to a platform depended solution (i tried to use a
MS Window pipe in the same process to create a fifo and it's very faster).

I don't know if this is fast (I am not even sure whether it is correct),
but if you want to try, feel free. If you get some benchmarks, please post
them:



#include <list>
#include <memory>

template < typename T, std::size_t N=1024,
typename Alloc=std::allocator<T> >
class fifo {
public:

typedef T value_type;
typedef std::size_t size_type;
typedef value_type & reference;
typedef value_type const & const_reference;
typedef value_type * pointer;
typedef value_type const * const_pointer;

private:

struct Block : public Alloc {

pointer const b;

Block ( void )
: b( Alloc::allocate(N) )
{}

void clear ( void ) {
Alloc::deallocate( b, N );
}

pointer begin ( void ) const {
return ( b );
}

pointer end ( void ) const {
return ( b+N );
}

};

std::list< Block > blocks;
size_type the_size;

pointer out_pointer;
pointer out_end;
pointer in_pointer;
pointer in_end;

public:

fifo ( void )
: blocks ( 1, Block() )
, the_size ( 0 )
, out_pointer ( blocks.front().begin() )
, out_end ( blocks.front().end() )
, in_pointer ( blocks.front().begin() )
, in_end ( blocks.front().end() )
{
assert( ! blocks.empty() );
}

bool empty ( void ) const {
return ( the_size == 0 );
}

size_type size ( void ) const {
return ( the_size );
}

reference front ( void ) {
return ( *out_pointer );
}

const_reference front ( void ) const {
return ( *out_pointer );
}

reference back ( void ) {
return ( *(in_pointer-1) );
}

const_reference back ( void ) const {
return ( *(in_pointer-1) );
}

void push ( const_reference x ) {
if ( in_pointer == in_end ) {
blocks.push_back( Block() );
in_pointer = blocks.back().begin();
in_end = blocks.back().end();
}
blocks.back().construct( in_pointer, x );
++ in_pointer;
++ the_size;
}

void pop ( void ) {
blocks.front().destroy( out_pointer );
++ out_pointer;
if ( out_pointer == out_end ) {
blocks.front().clear();
blocks.pop_front();
if ( blocks.empty() ) {
blocks.push_back( Block() );
in_pointer = blocks.back().begin();
in_end = blocks.back().end();
}
out_pointer = blocks.front().begin();
out_end = blocks.front().end();
}
-- the_size;
}

void clear ( void ) {
// FIXME: [this might be slow]
while ( the_size > 0 ) {
pop();
}
}

}; // fifo<>




Best

Kai-Uwe Bux