Concurrent, page-based, dynamically-sized linear data structure with O(1) random access and STL-compliant iterators. It is primarily intended for applications that concurrently insert (a possibly unkown number of) elements into a dynamically growing linear array, and fast random access to said elements. More...

#include <openvdb/util/PagedArray.h>

Classes
class	ConstIterator

class	Iterator

class	Page

class	ValueBuffer

Public Types
using	ValueType = ValueT

using	Ptr = SharedPtr< PagedArray >

Public Member Functions
	PagedArray ()
	Default constructor. More...

	~PagedArray ()
	Destructor removed all allocated pages. More...

	PagedArray (const PagedArray &)=delete

PagedArray &	operator= (const PagedArray &)=delete

ValueBuffer	getBuffer ()

size_t	push_back_unsafe (const ValueType &value)

void	shrink_to_fit ()
	Reduce the page table to fix the current size. More...

ValueType &	operator[] (size_t i)
	Return a reference to the value at the specified offset. More...

const ValueType &	operator[] (size_t i) const
	Return a const-reference to the value at the specified offset. More...

void	fill (const ValueType &v)
	Set all elements in the page table to the specified value. More...

bool	copy (ValueType *p, size_t count) const
	Copy the first count values in this PageArray into a raw c-style array, assuming it to be at least count elements long. More...

void	copy (ValueType *p) const

void	resize (size_t size)
	Resize this array to the specified size. More...

void	resize (size_t size, const ValueType &v)
	Resize this array to the specified size and initialize all values to v. More...

size_t	size () const
	Return the number of elements in this array. More...

size_t	capacity () const
	Return the maximum number of elements that this array can contain without allocating more memory pages. More...

size_t	freeCount () const
	Return the number of additional elements that can be added to this array without allocating more memory pages. More...

size_t	pageCount () const
	Return the number of allocated memory pages. More...

size_t	memUsage () const
	Return the memory footprint of this array in bytes. More...

bool	isEmpty () const
	Return true if the container contains no elements. More...

bool	isPartiallyFull () const
	Return true if the page table is partially full, i.e. the last non-empty page contains less than pageSize() elements. More...

void	clear ()
	Removes all elements from the array and delete all pages. More...

Iterator	begin ()
	Return a non-const iterator pointing to the first element. More...

Iterator	end ()
	Return a non-const iterator pointing to the past-the-last element. More...

void	sort ()
	Parallel sort of all the elements in ascending order. More...

void	invSort ()
	Parallel sort of all the elements in descending order. More...

void	merge (PagedArray &other)
	Transfer all the elements (and pages) from the other array to this array. More...

void	print (std::ostream &os=std::cout) const
	Print information for debugging. More...


ConstIterator	cbegin () const
	Return a const iterator pointing to the first element. More...

ConstIterator	begin () const
	Return a const iterator pointing to the first element. More...


ConstIterator	cend () const
	Return a const iterator pointing to the past-the-last element. More...

ConstIterator	end () const
	Return a const iterator pointing to the past-the-last element. More...


template<typename Functor >
void	sort (Functor func)
	Parallel sort of all the elements based on a custom functor with the api: More...

Static Public Member Functions
static Ptr	create ()
	Return a shared pointer to a new instance of this class. More...

static size_t	pageSize ()
	Return the number of elements per memory page. More...

static size_t	log2PageSize ()
	Return log2 of the number of elements per memory page. More...

Friends
class	ValueBuffer

Detailed Description

template<typename ValueT, size_t Log2PageSize = 10UL>
class openvdb::v12_0::util::PagedArray< ValueT, Log2PageSize >

Concurrent, page-based, dynamically-sized linear data structure with O(1) random access and STL-compliant iterators. It is primarily intended for applications that concurrently insert (a possibly unkown number of) elements into a dynamically growing linear array, and fast random access to said elements.

Note: Multiple threads can grow the page-table and push_back new elements concurrently. A ValueBuffer provides accelerated and threadsafe push_back at the cost of potentially re-ordering elements (when multiple instances are used).

This data structure employes contiguous pages of elements (a std::deque) which avoids moving data when the capacity is out-grown and new pages are allocated. The size of the pages can be controlled with the Log2PageSize template parameter (defaults to 1024 elements of type ValueT).

There are three fundamentally different ways to insert elements to this container - each with different advanteges and disadvanteges.

The simplest way to insert elements is to use PagedArray::push_back_unsafe which is not thread-safe:

PagedArray<size_t> array;

for (size_t i=0; i<100000; ++i) array.push_back_unsafe(i);

The fastest way (by far) to insert elements is by means of a PagedArray::ValueBuffer:

PagedArray<size_t> array;
auto buffer = array.getBuffer();
for (size_t i=0; i<100000; ++i) buffer.push_back(i);
buffer.flush();

or

PagedArray<size_t> array;
{
    //local scope of a single thread
    auto buffer = array.getBuffer();
    for (size_t i=0; i<100000; ++i) buffer.push_back(i);
}

or with TBB task-based multi-threading:

PagedArray<size_t> array;
tbb::parallel_for(
    tbb::blocked_range<size_t>(0, 10000, array.pageSize()),
    [&array](const tbb::blocked_range<size_t>& range) {
        auto buffer = array.getBuffer();
        for (size_t i=range.begin(); i!=range.end(); ++i) buffer.push_back(i);
    }
);

or with TBB thread-local storage for even better performance (due to fewer concurrent instantiations of partially full ValueBuffers)

PagedArray<size_t> array;
auto exemplar = array.getBuffer();//dummy used for initialization
tbb::enumerable_thread_specific<PagedArray<size_t>::ValueBuffer>
    pool(exemplar);//thread local storage pool of ValueBuffers
tbb::parallel_for(
    tbb::blocked_range<size_t>(0, 10000, array.pageSize()),
    [&pool](const tbb::blocked_range<size_t>& range) {
        auto &buffer = pool.local();
        for (size_t i=range.begin(); i!=range.end(); ++i) buffer.push_back(i);
    }
);
for (auto i=pool.begin(); i!=pool.end(); ++i) i->flush();

This technique generally outperforms PagedArray::push_back_unsafe, std::vector::push_back, std::deque::push_back and even tbb::concurrent_vector::push_back. Additionally it is thread-safe as long as each thread has it's own instance of a PagedArray::ValueBuffer. The only disadvantage is the ordering of the elements is undefined if multiple instance of a PagedArray::ValueBuffer are employed. This is typically the case in the context of multi-threading, where the ordering of inserts are undefined anyway. Note that a local scope can be used to guarentee that the ValueBuffer has inserted all its elements by the time the scope ends. Alternatively the ValueBuffer can be explicitly flushed by calling ValueBuffer::flush.

The third way to insert elements is to resize the container and use random access, e.g.

PagedArray<int> array;
array.resize(100000);
for (int i=0; i<100000; ++i) array[i] = i;

or in terms of the random access iterator

PagedArray<int> array;
array.resize(100000);
for (auto i=array.begin(); i!=array.end(); ++i) *i = i.pos();

While this approach is both fast and thread-safe it suffers from the major disadvantage that the problem size, i.e. number of elements, needs to be known in advance. If that's the case you might as well consider using std::vector or a raw c-style array! In other words the PagedArray is most useful in the context of applications that involve multi-threading of dynamically growing linear arrays that require fast random access.

Member Typedef Documentation

using Ptr = SharedPtr<PagedArray>

using ValueType = ValueT

Constructor & Destructor Documentation

PagedArray ( )

inline

Default constructor.

~PagedArray ( )

inline

Destructor removed all allocated pages.

PagedArray ( const PagedArray< ValueT, Log2PageSize > & )

delete

Member Function Documentation

Iterator begin ( )

inline

Return a non-const iterator pointing to the first element.

ConstIterator begin ( ) const

inline

Return a const iterator pointing to the first element.

size_t capacity ( ) const

inline

Return the maximum number of elements that this array can contain without allocating more memory pages.

ConstIterator cbegin ( ) const

inline

Return a const iterator pointing to the first element.

ConstIterator cend ( ) const

inline

Return a const iterator pointing to the past-the-last element.

Warning: Iterator does not point to a valid element and should not be dereferenced!

void clear ( )

inline

Removes all elements from the array and delete all pages.

Warning: Not thread-safe!

bool copy	(	ValueType *	p,
		size_t	count
	)		const

inline

Copy the first count values in this PageArray into a raw c-style array, assuming it to be at least count elements long.

Parameters

p	pointer to an array that will used as the destination of the copy.
count	number of elements to be copied.

void copy ( ValueType * p ) const

inline

static Ptr create ( )

inlinestatic

Return a shared pointer to a new instance of this class.

Iterator end ( )

inline

Return a non-const iterator pointing to the past-the-last element.

Warning: Iterator does not point to a valid element and should not be dereferenced!

ConstIterator end ( ) const

inline

Return a const iterator pointing to the past-the-last element.

Warning: Iterator does not point to a valid element and should not be dereferenced!

void fill ( const ValueType & v )

inline

Set all elements in the page table to the specified value.

Parameters

v	value to be filled in all the existing pages of this PagedArray.

Note: Multi-threaded

size_t freeCount ( ) const

inline

Return the number of additional elements that can be added to this array without allocating more memory pages.

ValueBuffer getBuffer ( )

inline

Returns: a new instance of a ValueBuffer which supports thread-safe push_back!

void invSort ( )

inline

Parallel sort of all the elements in descending order.

bool isEmpty ( ) const

inline

Return true if the container contains no elements.

bool isPartiallyFull ( ) const

inline

Return true if the page table is partially full, i.e. the last non-empty page contains less than pageSize() elements.

When the page table is partially full calling merge() or using a ValueBuffer will rearrange the ordering of existing elements.

static size_t log2PageSize ( )

inlinestatic

Return log2 of the number of elements per memory page.

size_t memUsage ( ) const

inline

Return the memory footprint of this array in bytes.

void merge ( PagedArray< ValueT, Log2PageSize > & other )

Transfer all the elements (and pages) from the other array to this array.

Parameters

other non-const reference to the PagedArray that will be merged into this PagedArray.

Note: The other PagedArray is empty on return.

Warning: The ordering of elements is undefined if this page table is partially full!

PagedArray& operator= ( const PagedArray< ValueT, Log2PageSize > & )

delete

ValueType& operator[] ( size_t i )

inline

Return a reference to the value at the specified offset.

Parameters

i	linear offset of the value to be accessed.

Note: This random access has constant time complexity.

Warning: It is assumed that the i'th element is already allocated!

const ValueType& operator[] ( size_t i ) const

inline

Return a const-reference to the value at the specified offset.

Parameters

i	linear offset of the value to be accessed.

Note: This random access has constant time complexity.

Warning: It is assumed that the i'th element is already allocated!

size_t pageCount ( ) const

inline

Return the number of allocated memory pages.

static size_t pageSize ( )

inlinestatic

Return the number of elements per memory page.

void print ( std::ostream & os = std::cout ) const

inline

Print information for debugging.

size_t push_back_unsafe ( const ValueType & value )

inline

Parameters

value value to be added to this PagedArray

Note: For best performance consider using the ValueBuffer!

Warning: Not thread-safe and mostly intended for debugging!

void resize ( size_t size )

inline

Resize this array to the specified size.

Parameters

size	number of elements that this PageArray will contain.

Will grow or shrink the page table to contain the specified number of elements. It will affect the size(), iteration will go over all those elements, push_back will insert after them and operator[] can be used directly access them.

Note: No reserve method is implemented due to efficiency concerns (especially for the ValueBuffer) from having to deal with empty pages.

Warning: Not thread-safe!

void resize	(	size_t	size,
		const ValueType &	v
	)

inline

Resize this array to the specified size and initialize all values to v.

Parameters

size	number of elements that this PageArray will contain.
v	value of all the size values.

Will grow or shrink the page table to contain the specified number of elements. It will affect the size(), iteration will go over all those elements, push_back will insert after them and operator[] can be used directly access them.

Note: No reserve method is implemented due to efficiency concerns (especially for the ValueBuffer) from having to deal with empty pages.

Warning: Not thread-safe!

void shrink_to_fit ( )

Reduce the page table to fix the current size.

Warning: Not thread-safe!

size_t size ( ) const

inline

Return the number of elements in this array.

void sort ( )

inline

Parallel sort of all the elements in ascending order.

void sort ( Functor func )

inline

Parallel sort of all the elements based on a custom functor with the api:

bool operator()(const ValueT& a, const ValueT& b)

which returns true if a comes before b.

Friends And Related Function Documentation

friend class ValueBuffer

friend

Classes

Public Types

Public Member Functions

Static Public Member Functions

Friends

Detailed Description

template<typename ValueT, size_t Log2PageSize = 10UL> class openvdb::v12_0::util::PagedArray< ValueT, Log2PageSize >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

template<typename ValueT, size_t Log2PageSize = 10UL>
class openvdb::v12_0::util::PagedArray< ValueT, Log2PageSize >