lunchbox::LFVector< T, nSlots > Class Template Reference

STL-like vector implementation providing certain thread-safety guarantees. More...

#include <lfVector.h>

Collaboration diagram for lunchbox::LFVector< T, nSlots >:

Public Types
typedef ScopedFastWrite	ScopedWrite
typedef T	value_type
typedef LFVectorIterator < LFVector< T, nSlots >, T >	iterator
	Iterator over the vector elements. More...
typedef LFVectorIterator < const LFVector< T, nSlots > , const T >	const_iterator
	Iterator over the const vector elements. More...

Public Member Functions
	LFVector ()
	LFVector (const size_t n)
	LFVector (const size_t n, const T &t)
	LFVector (const LFVector &from)
template<int32_t fromSlots>
	LFVector (const LFVector< T, fromSlots > &from)
	~LFVector ()
LFVector &	operator= (const LFVector &from)
bool	operator== (const LFVector &rhs) const
bool	operator!= (const LFVector &rhs) const
bool	empty () const
size_t	size () const
T &	operator[] (size_t i)
const T &	operator[] (size_t i) const
T &	front ()
T &	back ()
const_iterator	begin () const
const_iterator	end () const
iterator	begin ()
iterator	end ()
void	expand (const size_t newSize, const T &item=T())
	Resize the vector to at least the given size. More...
void	push_back (const T &item, bool lock=true)
	Add an element to the vector. More...
void	pop_back ()
	Remove the last element (STL version). More...
bool	pop_back (T &element)
	Remove the last element (atomic version). More...
iterator	erase (typename LFVector< T, nSlots >::iterator pos)
	Remove an element. More...
iterator	erase (const T &element)
	Remove the last occurence of the given element. More...
void	resize (const size_t size, const T &value=T())
	Resize the vector. More...
void	clear ()
	Clear the vector and all storage. More...
ScopedWrite	getWriteLock ()

Detailed Description

template<class T, int32_t nSlots = 32>
class lunchbox::LFVector< T, nSlots >

STL-like vector implementation providing certain thread-safety guarantees.

All operations not modifying the vector size are lock-free and wait-free. All operations modifying the vector size are serialized using a spin lock. The interaction of operations is documented in the corresponding modify operation.

Undocumented methods behave like the STL implementation. The number of slots (default 32) sets the maximum elements the vector may hold to 2^nSlots-1. Each slot needs one pointer additional storage. Naturally it should never be set higher than 64.

Not all std::vector methods are implemented. Serializable using boost.serialization.

Example:

/* Copyright (c) 2011-2014, Stefan Eilemann <stefan.eilemann@epfl.ch>
 *                    2012, Daniel Nachbaur <danielnachbaur@gmail.com>
 *
 * This library is free software; you can redistribute it and/or modify it under
 * the terms of the GNU Lesser General Public License version 3.0 as published
 * by the Free Software Foundation.
 *
 * This library is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License for more
 * details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this library; if not, write to the Free Software Foundation, Inc.,
 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 */

#define TEST_RUNTIME 600 // seconds
#include "test.h"

#pragma warning (push)
#pragma warning (disable: 4985) // http://www.softwareverify.com/blog/?p=671
#  include <lunchbox/lfVector.h>
#pragma warning (pop)

#include <lunchbox/clock.h>
#include <lunchbox/init.h>
#include <lunchbox/monitor.h>
#include <lunchbox/omp.h>
#include <lunchbox/thread.h>

#include <limits>

#define LOOPSIZE  200000

lunchbox::Clock _clock;
typedef lunchbox::LFVector< size_t > Vector_t;
float rTime_;
float wTime_;
float eTime_;
float cTime_;
float pTime_;

lunchbox::Monitor< size_t > stage_;
#define STAGESIZE 10000;

class Reader : public lunchbox::Thread
{
public:
    Reader() : vector( 0 ) {}
    virtual ~Reader() {}

    virtual void run()
    {
        size_t stage = 0;
        while( true )
        {
            stage += STAGESIZE;
            stage_.waitGE( stage );
            if( stage_ == std::numeric_limits< size_t >::max( ))
                return;

            if( vector )
            {
                for( size_t i = 0; i < LOOPSIZE; ++i )
                {
                    if( i < vector->size( ))
                    {
                        const size_t value = (*vector)[ i ];
                        TESTINFO( i == value || value == 0,
                                  i << " - " << value << " - " << (*vector)[i]<<
                                  ": " << *vector );
                    }
                }
                rTime_ = _clock.getTimef();
            }
            ++stage_;
        }
    }

    Vector_t* vector;
};

class Writer : public lunchbox::Thread
{
public:
    Writer() : vector( 0 ) {}
    virtual ~Writer() {}

    virtual void run()
    {
        size_t stage = 0;
        while( true )
        {
            stage += STAGESIZE;
            stage_.waitGE( stage );
            if( stage_ == std::numeric_limits< size_t >::max( ))
                return;

            if( vector )
            {
                for( size_t i = 0; i < LOOPSIZE; ++i )
                {
                    if( i < vector->size( ))
                        (*vector)[ i ] = i;
                }
                wTime_ = _clock.getTimef();
            }
            ++stage_;
        }
    }

    Vector_t* vector;
};

class Pusher : public lunchbox::Thread
{
public:
    Pusher() : vector( 0 ) {}
    virtual ~Pusher() {}

    virtual void run()
    {
        size_t stage = 0;
        while( true )
        {
            stage += STAGESIZE;
            stage_.waitGE( stage );
            if( stage_ == std::numeric_limits< size_t >::max( ))
                return;

            if( vector )
            {
                while( vector->size() < LOOPSIZE )
                    vector->push_back( 0 );
                pTime_ = _clock.getTimef();
            }
            ++stage_;
        }
    }

    Vector_t* vector;
};

class Copier : public lunchbox::Thread
{
public:
    Copier() : vector( 0 ) {}
    virtual ~Copier() {}

    virtual void run()
        {
            Vector_t copy;
            copy = *vector;
            *vector = copy;
            TEST( copy.size() >= vector->size( ));
            cTime_ = _clock.getTimef();
        }
    Vector_t* vector;
};

class Eraser : public lunchbox::Thread
{
public:
    Eraser() : vector( 0 ) {}
    virtual ~Eraser() {}

    virtual void run()
        {
            const size_t pos = vector->size() / 2;
            Vector_t::iterator i = vector->begin() + pos;
            Vector_t::iterator j = vector->erase( i );
            TEST( j != vector->end( ));
            TEST( i == j );
            eTime_ = _clock.getTimef();
        }
    Vector_t* vector;
};

class Flusher : public lunchbox::Thread
{
public:
    Flusher() : vector( 0 ) {}
    virtual ~Flusher() {}

    virtual void run()
        {
            size_t i = 0xFFFFFFFFu;
            while( vector->pop_back( i ))
            {
                TEST( i == 0 || i >= vector->size( ));
            }
        }
    Vector_t* vector;
};

template< class V, class T > void _runSerialTest()
{
    V vector;

    _clock.reset();
    while( vector.size() < LOOPSIZE*10 )
        vector.push_back( T( 0 ));
    pTime_ = _clock.getTimef();

    _clock.reset();
    for( size_t i = 0; i < LOOPSIZE*10; ++i )
    {
        if( i < vector.size( ))
            vector[ i ] = i;
    }
    wTime_ = _clock.getTimef();

    _clock.reset();
    typename V::const_iterator it = vector.begin();
    for( size_t i = 0; i < LOOPSIZE*10; ++i )
    {
        const size_t value = *it;
        TESTINFO( i == value || value == 0, i << ", " << value );
        ++it;
        if( it == vector.end( ))
            it = vector.begin();
    }
    rTime_ = _clock.getTimef();

    _clock.reset();
    for( size_t i = 0; i < 10; ++i )
    {
        V copy;
        copy = vector;
        vector = copy;
        TEST( copy.size() >= vector.size( ));
    }
    cTime_ = _clock.getTimef();

    _clock.reset();
    const size_t pos = vector.size() / 2;
    typename V::iterator i = vector.begin() + pos;
    typename V::iterator j = vector.erase( i );
    TEST( j != vector.end( ));
    TEST( *j == 0 || *j >= pos );
    eTime_ = _clock.getTimef();

    _clock.reset();
    while( !vector.empty( ))
        vector.pop_back();
    const float fTime = _clock.getTimef();

    std::cerr << std::setw(11) << float(LOOPSIZE*10)/rTime_ << ", "
              << std::setw(11) << float(LOOPSIZE*10)/wTime_ << ", "
              << std::setw(11) << float(LOOPSIZE*10)/pTime_ << ", "
              << std::setw(9) << float(10)/cTime_ << ", "
              << std::setw(9) << float(10)/eTime_ << ", "
              << std::setw(9) << float(LOOPSIZE*10)/fTime << ", "
              << std::setw(3) << 0 << ", " << std::setw(3) << 0
              << std::endl;

    vector.push_back( 42 );
    i = vector.begin();
    i = vector.erase( i );
    TEST( i == vector.begin( ));
    TEST( vector.empty( ));

    vector.push_back( 42 );
    vector.push_back( 17 );
    vector.resize( 1 );
    TEST( vector.size() == 1 );
    TEST( vector[0] == 42 );

    vector.resize( 10, 17 );
    TEST( vector.size() == 10 );
    TEST( vector[0] == 42 );
    TEST( vector[1] == 17 );
    TEST( vector[9] == 17 );
}

int main( int, char** )
{
#ifdef LUNCHBOX_USE_OPENMP
    const size_t nThreads = lunchbox::OMP::getNThreads() * 3;
#else
    const size_t nThreads = 16;
#endif

    std::cout << "       read,       write,        push,      copy,     erase, "
              << " flush/ms,  rd, other #threads" << std::endl;
    _runSerialTest< std::vector< size_t >, size_t >();
    _runSerialTest< Vector_t, size_t >();

    std::vector< Reader > readers(nThreads);
    std::vector< Writer > writers(nThreads);
    std::vector< Pusher > pushers(nThreads);

    stage_ = 1;
    size_t stage = 0;

    for( size_t l = 0; l < nThreads; ++l )
    {
        readers[l].start();
        writers[l].start();
        pushers[l].start();
    }
    lunchbox::sleep( 10 );

    for( size_t i = 1; i <= nThreads; i = i<<1 )
        for( size_t j = 1; j <= nThreads; j = j<<1 )
        {
            // concurrent read, write, push
            Vector_t vector;
            for( size_t k = 0; k < nThreads; ++k )
            {
                readers[k].vector = k < i ? &vector : 0;
                writers[k].vector = k < j ? &vector : 0;
                pushers[k].vector = k < j ? &vector : 0;
            }

            const size_t nextStage = ++stage * STAGESIZE;

            _clock.reset();
            stage_ = nextStage;
            stage_.waitEQ( nextStage + (3 * nThreads) );
            TEST( vector.size() >= LOOPSIZE );

            // multi-threaded copy
            std::vector< Copier > copiers(j);

            _clock.reset();
            for( size_t k = 0; k < j; ++k )
            {
                copiers[k].vector = &vector;
                copiers[k].start();
            }
            for( size_t k = 0; k < j; ++k )
                copiers[k].join();

            for( size_t k = 0; k < vector.size(); ++k )
                TEST( vector[k] == k || vector[k] == 0 );

            // multi-threaded erase
            std::vector< Eraser > erasers(j);

            _clock.reset();
            for( size_t k = 0; k < j; ++k )
            {
                erasers[k].vector = &vector;
                erasers[k].start();
            }
            for( size_t k = 0; k < j; ++k )
                erasers[k].join();

            for( size_t k = 0; k < vector.size(); ++k )
            {
                if( vector[k] == 0 )
                    break;
                if( k > vector.size() / 2 )
                {
                    TEST( vector[k] > vector[k-1] );
                }
                else
                {
                    TEST( vector[k] == k );
                }
            }

            // multi-threaded pop_back
            const size_t fOps = vector.size();
            std::vector< Flusher > flushers(j);
            _clock.reset();
            for( size_t k = 0; k < j; ++k )
            {
                flushers[k].vector = &vector;
                flushers[k].start();
            }
            for( size_t k = 0; k < j; ++k )
                flushers[k].join();
            const float fTime = _clock.getTimef();
            TEST( vector.empty( ));

            std::cerr << std::setw(11) << float(i*LOOPSIZE)/rTime_ << ", "
                      << std::setw(11) << float(j*LOOPSIZE)/wTime_ << ", "
                      << std::setw(11) << float(LOOPSIZE)/pTime_ << ", "
                      << std::setw(9) << float(j)/cTime_ << ", "
                      << std::setw(9) << float(j)/eTime_ << ", "
                      << std::setw(9) << float(fOps)/fTime << ", "
                      << std::setw(3) << i << ", " << std::setw(3) << j
                      << std::endl;
        }

    stage_ = std::numeric_limits< size_t >::max();
    for( size_t k = 0; k < nThreads; ++k )
    {
        readers[k].join();
        writers[k].join();
        pushers[k].join();
    }

    return EXIT_SUCCESS;
}

Definition at line 52 of file lfVector.h.

Member Typedef Documentation

template<class T, int32_t nSlots = 32>

typedef LFVectorIterator<const LFVector<T, nSlots>, const T> lunchbox::LFVector< T, nSlots >::const_iterator

Iterator over the const vector elements.

Version

1.3.2

Definition at line 105 of file lfVector.h.

template<class T, int32_t nSlots = 32>

typedef LFVectorIterator< LFVector< T, nSlots >, T > lunchbox::LFVector< T, nSlots >::iterator

Iterator over the vector elements.

Version

1.3.2

Definition at line 102 of file lfVector.h.

Constructor & Destructor Documentation

template<class T , int32_t nSlots>

lunchbox::LFVector< T, nSlots >::LFVector

(

)

Version

1.3.2

Definition at line 28 of file lfVector.ipp.

template<class T , int32_t nSlots>

lunchbox::LFVector< T, nSlots >::LFVector ( const size_t  n )

explicit

Version

1.3.2

Definition at line 35 of file lfVector.ipp.

References lunchbox::getIndexOfLastBit().

Here is the call graph for this function:

template<class T, int32_t nSlots>

lunchbox::LFVector< T, nSlots >::LFVector	(	const size_t	n,
		const T &	t
	)

Version

1.3.2

Definition at line 46 of file lfVector.ipp.

References lunchbox::getIndexOfLastBit().

Here is the call graph for this function:

template<class T, int32_t nSlots>

lunchbox::LFVector< T, nSlots >::LFVector ( const LFVector< T, nSlots > &  from )

explicit

Version

1.3.2

Definition at line 66 of file lfVector.ipp.

template<class T, int32_t nSlots>

template<int32_t fromSlots>

lunchbox::LFVector< T, nSlots >::LFVector ( const LFVector< T, fromSlots > &  from )

explicit

Version

1.3.2

Definition at line 75 of file lfVector.ipp.

template<class T , int32_t nSlots>

lunchbox::LFVector< T, nSlots >::~LFVector

(

)

Version

1.3.2

Definition at line 83 of file lfVector.ipp.

Member Function Documentation

template<class T , int32_t nSlots>

T & lunchbox::LFVector< T, nSlots >::back

(

)

Version

1.3.2

Definition at line 193 of file lfVector.ipp.

template<class T , int32_t nSlots>

LFVector< T, nSlots >::const_iterator lunchbox::LFVector< T, nSlots >::begin ( ) const

inline

Version

1.3.2

Definition at line 370 of file lfVector.ipp.

Referenced by lunchbox::LFVector< T, nSlots >::operator==().

Here is the caller graph for this function:

template<class T , int32_t nSlots>

LFVector< T, nSlots >::iterator lunchbox::LFVector< T, nSlots >::begin ( )

inline

Version

1.3.2

Definition at line 382 of file lfVector.ipp.

template<class T , int32_t nSlots>

void lunchbox::LFVector< T, nSlots >::clear

(

)

Clear the vector and all storage.

Thread-safe with other write operations. By nature not thread-safe with read operations.

Version

1.3.2

Definition at line 295 of file lfVector.ipp.

template<class T, int32_t nSlots = 32>

bool lunchbox::LFVector< T, nSlots >::empty ( ) const

inline

Version

1.3.2

Definition at line 86 of file lfVector.h.

template<class T , int32_t nSlots>

LFVector< T, nSlots >::const_iterator lunchbox::LFVector< T, nSlots >::end ( ) const

inline

Version

1.3.2

Definition at line 376 of file lfVector.ipp.

template<class T , int32_t nSlots>

LFVector< T, nSlots >::iterator lunchbox::LFVector< T, nSlots >::end ( )

inline

Version

1.3.2

Definition at line 388 of file lfVector.ipp.

template<class T, int32_t nSlots>

LFVector< T, nSlots >::iterator lunchbox::LFVector< T, nSlots >::erase

(

typename LFVector< T, nSlots >::iterator

pos

)

Remove an element.

A concurrent read on the item or any following item is not thread save. The vector's size is decremented first. Returns end() if the element can't be removed, i.e., the iterator is past end() or not for this vector.

Parameters

pos	the element to remove

Returns

an iterator pointing to the element after the removed element, or end() if nothing was erased.

Version

1.3.2

Definition at line 240 of file lfVector.ipp.

template<class T, int32_t nSlots>

LFVector< T, nSlots >::iterator lunchbox::LFVector< T, nSlots >::erase

(

const T &

element

)

Remove the last occurence of the given element.

A concurrent read on the item or any following item is not thread save. The vector's size is decremented first. Returns end() if the element can't be removed, i.e., the vector does not contain the element.

Parameters

element

the element to remove

Returns

an iterator pointing to the element after the removed element, or end() if nothing was erased.

Version

1.3.2

Definition at line 258 of file lfVector.ipp.

template<class T, int32_t nSlots>

void lunchbox::LFVector< T, nSlots >::expand	(	const size_t	newSize,
		const T &	item = T( )
	)

Resize the vector to at least the given size.

In contrast to resize(), expand() only increases the size of the vector, allowing concurrent resize operations on the same vector. Completely thread-save with read operations. Existing end() iterators will keep pointing to the old end of the vector. The size is updated after all elements have been inserted, so size() followed by a read is thread-safe. In contrast to while( vector.size() < newSize ) vector.insert( item ); this method's operation is atomic with other writes.

Parameters

newSize	the minimum new size.
item	the element to insert.

Version

1.3.2

Definition at line 200 of file lfVector.ipp.

template<class T , int32_t nSlots>

T & lunchbox::LFVector< T, nSlots >::front

(

)

Version

1.3.2

Definition at line 186 of file lfVector.ipp.

template<class T , int32_t nSlots>

LFVector< T, nSlots >::ScopedWrite lunchbox::LFVector< T, nSlots >::getWriteLock

(

)

Returns

the locked mutex for unlocked write operations.

Version

1.5

Definition at line 311 of file lfVector.ipp.

template<class T, int32_t nSlots = 32>

bool lunchbox::LFVector< T, nSlots >::operator!= ( const LFVector< T, nSlots > &  rhs ) const

inline

Version

1.3.2

Definition at line 84 of file lfVector.h.

template<class T , int32_t nSlots>

LFVector< T, nSlots > & lunchbox::LFVector< T, nSlots >::operator=

(

const LFVector< T, nSlots > &

from

)

Version

1.3.2

Definition at line 90 of file lfVector.ipp.

template<class T , int32_t nSlots>

bool lunchbox::LFVector< T, nSlots >::operator==

(

const LFVector< T, nSlots > &

rhs

)

const

Version

1.3.2

Definition at line 124 of file lfVector.ipp.

References lunchbox::LFVector< T, nSlots >::begin(), and lunchbox::LFVector< T, nSlots >::size().

Here is the call graph for this function:

template<class T , int32_t nSlots>

T & lunchbox::LFVector< T, nSlots >::operator[]

(

size_t

i

)

Version

1.3.2

Definition at line 151 of file lfVector.ipp.

References lunchbox::getIndexOfLastBit().

Here is the call graph for this function:

template<class T , int32_t nSlots>

const T & lunchbox::LFVector< T, nSlots >::operator[]

(

size_t

i

)

const

Version

1.3.2

Definition at line 166 of file lfVector.ipp.

References lunchbox::getIndexOfLastBit().

Here is the call graph for this function:

template<class T , int32_t nSlots>

void lunchbox::LFVector< T, nSlots >::pop_back

(

)

Remove the last element (STL version).

A concurrent read on the removed item produces undefined results, in particular end() and back().

Version

1.3.2

Definition at line 215 of file lfVector.ipp.

template<class T, int32_t nSlots>

bool lunchbox::LFVector< T, nSlots >::pop_back

(

T &

element

)

Remove the last element (atomic version).

A concurrent read on the removed item produces undefined results, in particular end() and back(). The last element is assigned to the given output element if the vector is not empty. If the vector is empty, element is not touched and false is returned. The whole operation is atomic with other operations changing the size of the vector.

Parameters

element

the item receiving the value which was stored at the end.

Returns

true if the vector was not empty, false if no item was popped.

Version

1.3.2

Definition at line 226 of file lfVector.ipp.

template<class T, int32_t nSlots>

void lunchbox::LFVector< T, nSlots >::push_back	(	const T &	item,
		bool	lock = true
	)

Add an element to the vector.

Completely thread-save with read operations. Existing end() iterators will keep pointing to the old end of the vector. The size is updated after the element is inserted, so size() followed by a read is thread-safe.

Parameters

item	the element to insert.
lock	true for internal lock, false if locked with getWriteLock()

Version

1.3.2

Definition at line 208 of file lfVector.ipp.

template<class T, int32_t nSlots>

void lunchbox::LFVector< T, nSlots >::resize	(	const size_t	size,
		const T &	value = T( )
	)

Resize the vector.

Thread-safe with other write operations. Shrinking is not thread-safe with concurrent reads on the removed elements and produces undefined results.

Version

1.7.2

Definition at line 280 of file lfVector.ipp.

template<class T, int32_t nSlots = 32>

size_t lunchbox::LFVector< T, nSlots >::size ( ) const

inline

Version

1.3.2

Definition at line 87 of file lfVector.h.

Referenced by lunchbox::LFVector< T, nSlots >::operator==().

Here is the caller graph for this function:

---

The documentation for this class was generated from the following files:

• lfVector.h
• lfVector.ipp