Concurrency::combinable< _Ty > Class Template Reference

The combinable<T> object is intended to provide thread-private copies of data, to perform lock-free thread-local sub-computations during parallel algorithms. At the end of the parallel operation, the thread-private sub-computations can then be merged into a final result. This class can be used instead of a shared variable, and can result in a performance improvement if there would otherwise be a lot of contention on that shared variable. More...

#include <ppl.h>

Public Member Functions
	combinable ()
	Constructs a new combinable object. More...
template<typename _Function >
	combinable (_Function _FnInitialize)
	Constructs a new combinable object. More...
	combinable (const combinable &_Copy)
	Constructs a new combinable object. More...
combinable &	operator= (const combinable &_Copy)
	Assigns to a combinable object from another combinable object. More...
	~combinable ()
	Destroys a combinable object. More...
_Ty &	local ()
	Returns a reference to the thread-private sub-computation. More...
_Ty &	local (bool &_Exists)
	Returns a reference to the thread-private sub-computation. More...
void	clear ()
	Clears any intermediate computational results from a previous usage. More...
template<typename _Function >
_Ty	combine (_Function _FnCombine) const
	Computes a final value from the set of thread-local sub-computations by calling the supplied combine functor. More...
template<typename _Function >
void	combine_each (_Function _FnCombine) const
	Computes a final value from the set of thread-local sub-computations by calling the supplied combine functor once per thread-local sub-computation. The final result is accumulated by the function object. More...

Private Member Functions
	__declspec (align(64)) struct _Node
void	_InitNew ()
void	_InitCopy (const combinable &_Copy)
_Node *	_FindLocalItem (unsigned long _Key, size_t *_PIndex)
_Node *	_AddLocalItem (unsigned long _Key, size_t _Index)

Static Private Member Functions
static _Ty	_DefaultInit ()

Private Attributes
_Node *volatile *	_M_buckets
size_t	_M_size
std::tr1::function< _Ty()>	_M_fnInitialize

Detailed Description

template<typename _Ty>
class Concurrency::combinable< _Ty >

The combinable<T> object is intended to provide thread-private copies of data, to perform lock-free thread-local sub-computations during parallel algorithms. At the end of the parallel operation, the thread-private sub-computations can then be merged into a final result. This class can be used instead of a shared variable, and can result in a performance improvement if there would otherwise be a lot of contention on that shared variable.

Template Parameters

_Ty	The data type of the final merged result. The type must have a copy constructor and a default constructor.

For more information, see Parallel Containers and Objects.

Constructor & Destructor Documentation

template<typename _Ty >

Concurrency::combinable< _Ty >::combinable ( )

inline

Constructs a new combinable object.

The first constructor initializes new elements with the default constructor for the type _Ty .

The second constructor initializes new elements using the initialization functor supplied as the _FnInitialize parameter.

The third constructor is the copy constructor.

See also

Parallel Containers and Objects

        : _M_fnInitialize(_DefaultInit)
    {
        _InitNew();
    }

template<typename _Ty >

template<typename _Function >

Concurrency::combinable< _Ty >::combinable ( _Function  _FnInitialize )

inlineexplicit

Constructs a new combinable object.

Template Parameters

_Function

The type of the initialization functor object.

Parameters

_FnInitialize

A function which will be called to initialize each new thread-private value of the type _Ty . It must support a function call operator with the signature _Ty ().

The first constructor initializes new elements with the default constructor for the type _Ty .

The second constructor initializes new elements using the initialization functor supplied as the _FnInitialize parameter.

The third constructor is the copy constructor.

See also

Parallel Containers and Objects

        : _M_fnInitialize(_FnInitialize)
    {
        _InitNew();
    }

template<typename _Ty >

Concurrency::combinable< _Ty >::combinable ( const combinable< _Ty > &  _Copy )

inline

Constructs a new combinable object.

Parameters

_Copy

An existing combinable object to be copied into this one.

The first constructor initializes new elements with the default constructor for the type _Ty .

The second constructor initializes new elements using the initialization functor supplied as the _FnInitialize parameter.

The third constructor is the copy constructor.

See also

Parallel Containers and Objects

        : _M_size(_Copy._M_size), _M_fnInitialize(_Copy._M_fnInitialize)
    {
        _InitCopy(_Copy);
    }

template<typename _Ty >

Concurrency::combinable< _Ty >::~combinable ( )

inline

Destroys a combinable object.

    {
        clear();
        delete [] _M_buckets;
    }

Member Function Documentation

template<typename _Ty >

Concurrency::combinable< _Ty >::__declspec ( align(64)  )

inlineprivate

    {
        unsigned long _M_key;
        _Ty _M_value;
        _Node* _M_chain;

        _Node(unsigned long _Key, _Ty _InitialValue)
            : _M_key(_Key), _M_value(_InitialValue), _M_chain(NULL)
        {
        }
    };

template<typename _Ty >

_Node* Concurrency::combinable< _Ty >::_AddLocalItem ( unsigned long  _Key, size_t  _Index  )

inlineprivate

    {
        _Node* _NewNode = new _Node(_Key, _M_fnInitialize());
        _Node* _TopNode;
        do
        {
            _TopNode = _M_buckets[_Index];
            _NewNode->_M_chain = _TopNode;
        } while (_InterlockedCompareExchangePointer(reinterpret_cast<void * volatile *>(&_M_buckets[_Index]), _NewNode, _TopNode) != _TopNode);

        return _NewNode;
    }

template<typename _Ty >

static _Ty Concurrency::combinable< _Ty >::_DefaultInit ( )

inlinestaticprivate

    {
        return _Ty();
    }

template<typename _Ty >

_Node* Concurrency::combinable< _Ty >::_FindLocalItem ( unsigned long  _Key, size_t *  _PIndex  )

inlineprivate

    {
        _CONCRT_ASSERT(_PIndex != NULL);

        *_PIndex = _Key % _M_size;

        // Search at this index for an existing value.
        _Node* _CurrentNode = _M_buckets[*_PIndex];
        while (_CurrentNode != NULL)
        {
            if (_CurrentNode->_M_key == _Key)
            {
                return _CurrentNode;
            }

            _CurrentNode = _CurrentNode->_M_chain;
        }

        return NULL;
    }

template<typename _Ty >

void Concurrency::combinable< _Ty >::_InitCopy ( const combinable< _Ty > &  _Copy )

inlineprivate

    {
        _M_buckets = new _Node*[_M_size];
        for (size_t _Index = 0; _Index < _M_size; ++_Index)
        {
            _M_buckets[_Index] = NULL;
            for (_Node* _CurrentNode = _Copy._M_buckets[_Index]; _CurrentNode != NULL; _CurrentNode = _CurrentNode->_M_chain)
            {
                _Node* _NewNode = new _Node(_CurrentNode->_M_key, _CurrentNode->_M_value);
                _NewNode->_M_chain = _M_buckets[_Index];
                _M_buckets[_Index] = _NewNode;
            }
        }
    }

template<typename _Ty >

void Concurrency::combinable< _Ty >::_InitNew ( )

inlineprivate

    {
        _M_size = Concurrency::details::_GetCombinableSize();
        _M_buckets = new _Node*[_M_size];
        memset((void*)_M_buckets, 0, _M_size * sizeof _M_buckets[0]);
    }

template<typename _Ty >

void Concurrency::combinable< _Ty >::clear ( )

inline

Clears any intermediate computational results from a previous usage.

    {
        for (size_t _Index = 0; _Index < _M_size; ++_Index)
        {
            _Node* _CurrentNode = _M_buckets[_Index];
            while (_CurrentNode != NULL)
            {
                _Node* _NextNode = _CurrentNode->_M_chain;
                delete _CurrentNode;
                _CurrentNode = _NextNode;
            }
        }
        memset((void*)_M_buckets, 0, _M_size * sizeof _M_buckets[0]);
    }

template<typename _Ty >

template<typename _Function >

_Ty Concurrency::combinable< _Ty >::combine ( _Function  _FnCombine ) const

inline

Computes a final value from the set of thread-local sub-computations by calling the supplied combine functor.

Template Parameters

_Function

The type of the function object that will be invoked to combine two thread-local sub-computations.

Parameters

_FnCombine

The functor that is used to combine the sub-computations. Its signature is T (T, T) or T (const T&, const T&), and it must be associative and commutative.

Returns

The final result of combining all the thread-private sub-computations.

See also

Parallel Containers and Objects

    {
        _Node* _CurrentNode = NULL;
        size_t _Index;

        // Look for the first value in the set, and use (a copy of) that as the result.
        // This eliminates a single call (of unknown cost) to _M_fnInitialize.
        for (_Index = 0; _Index < _M_size; ++_Index)
        {
            _CurrentNode = _M_buckets[_Index];
            if (_CurrentNode != NULL)
            {
                 break;
            }
        }

        // No values... return the initializer value.
        if (_CurrentNode == NULL)
        {
            return _M_fnInitialize();
        }

        // Accumulate the rest of the items in the current bucket.
        _Ty _Result = _CurrentNode->_M_value;
        for (_CurrentNode = _CurrentNode->_M_chain; _CurrentNode != NULL; _CurrentNode = _CurrentNode->_M_chain)
        {
            _Result = _FnCombine(_Result, _CurrentNode->_M_value);
        }

        // Accumulate values from the rest of the buckets.
        _CONCRT_ASSERT(_Index < _M_size);
        for (++_Index; _Index < _M_size; ++_Index)
        {
            for (_CurrentNode = _M_buckets[_Index]; _CurrentNode != NULL; _CurrentNode = _CurrentNode->_M_chain)
            {
                _Result = _FnCombine(_Result, _CurrentNode->_M_value);
            }
        }

        return _Result;
    }

template<typename _Ty >

template<typename _Function >

void Concurrency::combinable< _Ty >::combine_each ( _Function  _FnCombine ) const

inline

Computes a final value from the set of thread-local sub-computations by calling the supplied combine functor once per thread-local sub-computation. The final result is accumulated by the function object.

Template Parameters

_Function

The type of the function object that will be invoked to combine a single thread-local sub-computation.

Parameters

_FnCombine

The functor that is used to combine one sub-computation. Its signature is void (T) or void (const T&), and must be associative and commutative.

See also

Parallel Containers and Objects

    {
        for (size_t _Index = 0; _Index < _M_size; ++_Index)
        {
            for (_Node* _CurrentNode = _M_buckets[_Index]; _CurrentNode != NULL; _CurrentNode = _CurrentNode->_M_chain)
            {
                _FnCombine(_CurrentNode->_M_value);
            }
        }
    }

template<typename _Ty >

_Ty& Concurrency::combinable< _Ty >::local ( )

inline

Returns a reference to the thread-private sub-computation.

Returns

A reference to the thread-private sub-computation.

See also

Parallel Containers and Objects

    {
        unsigned long _Key = Concurrency::details::platform::GetCurrentThreadId();
        size_t _Index;
        _Node* _ExistingNode = _FindLocalItem(_Key, &_Index);
        if (_ExistingNode == NULL)
        {
            _ExistingNode = _AddLocalItem(_Key, _Index);
        }

        _CONCRT_ASSERT(_ExistingNode != NULL);
        return _ExistingNode->_M_value;
    }

template<typename _Ty >

_Ty& Concurrency::combinable< _Ty >::local ( bool &  _Exists )

inline

Returns a reference to the thread-private sub-computation.

Parameters

_Exists

A reference to a boolean. The boolean value referenced by this argument will be set to true if the sub-computation already existed on this thread, and set to false if this was the first sub-computation on this thread.

Returns

A reference to the thread-private sub-computation.

See also

Parallel Containers and Objects

    {
        unsigned long _Key = Concurrency::details::platform::GetCurrentThreadId();
        size_t _Index;
        _Node* _ExistingNode = _FindLocalItem(_Key, &_Index);
        if (_ExistingNode == NULL)
        {
            _Exists = false;
            _ExistingNode = _AddLocalItem(_Key, _Index);
        }
        else
        {
            _Exists = true;
        }

        _CONCRT_ASSERT(_ExistingNode != NULL);
        return _ExistingNode->_M_value;
    }

template<typename _Ty >

combinable& Concurrency::combinable< _Ty >::operator= ( const combinable< _Ty > &  _Copy )

inline

Assigns to a combinable object from another combinable object.

Parameters

_Copy

An existing combinable object to be copied into this one.

Returns

A reference to this combinable object.

    {
        clear();
        delete [] _M_buckets;
        _M_fnInitialize = _Copy._M_fnInitialize;
        _M_size = _Copy._M_size;
        _InitCopy(_Copy);

        return *this;
    }

Member Data Documentation

template<typename _Ty >

_Node* volatile* Concurrency::combinable< _Ty >::_M_buckets

private

template<typename _Ty >

std::tr1::function<_Ty ()> Concurrency::combinable< _Ty >::_M_fnInitialize

private

template<typename _Ty >

size_t Concurrency::combinable< _Ty >::_M_size

private

---

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

• VS2013/inc/ppl.h