Loading...
Searching...
No Matches
PagedArray< ValueT, Log2PageSize > Class Template Reference

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 | ValueBuffer
class | ConstIterator
class | Iterator
class | Page

## Public Types

using | ValueType = ValueT
using | Ptr = SharedPtr<PagedArray>

## Public Member Functions

| PagedArray ()
| Default constructor.
| ~PagedArray ()
| Destructor removed all allocated pages.
| 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.
ValueType & | operator[] (size_t i)
| Return a reference to the value at the specified offset.
const ValueType & | operator[] (size_t i) const
| Return a const-reference to the value at the specified offset.
void | fill (const ValueType &v)
| Set all elements in the page table to the specified value.
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.
void | copy (ValueType *p) const
void | resize (size_t size)
| Resize this array to the specified size.
void | resize (size_t size, const ValueType &v)
| Resize this array to the specified size and initialize all values to v.
size_t | size () const
| Return the number of elements in this array.
size_t | capacity () const
| Return the maximum number of elements that this array can contain without allocating more memory pages.
size_t | freeCount () const
| Return the number of additional elements that can be added to this array without allocating more memory pages.
size_t | pageCount () const
| Return the number of allocated memory pages.
size_t | memUsage () const
| Return the memory footprint of this array in bytes.
bool | isEmpty () const
| Return true if the container contains no elements.
bool | isPartiallyFull () const
| Return true if the page table is partially full, i.e. the last non-empty page contains less than pageSize() elements.
void | clear ()
| Removes all elements from the array and delete all pages.
Iterator | begin ()
| Return a non-const iterator pointing to the first element.
Iterator | end ()
| Return a non-const iterator pointing to the past-the-last element.
ConstIterator | cbegin () const
| Return a const iterator pointing to the first element.
ConstIterator | begin () const
ConstIterator | cend () const
| Return a const iterator pointing to the past-the-last element.
ConstIterator | end () const
void | sort ()
| Parallel sort of all the elements in ascending order.
void | invSort ()
| Parallel sort of all the elements in descending order.
template<typename Functor>
void | sort (Functor func)
| Parallel sort of all the elements based on a custom functor with the api:
void | merge (PagedArray &other)
| Transfer all the elements (and pages) from the other array to this array.
void | print (std::ostream &os=std::cout) const
| Print information for debugging.

## Static Public Member Functions

static Ptr | create ()
| Return a shared pointer to a new instance of this class.
static size_t | pageSize ()
| Return the number of elements per memory page.
static size_t | log2PageSize ()
| Return log2 of the number of elements per memory page.

## Friends

class | ValueBuffer

## Detailed Description

template<typename ValueT, size_t Log2PageSize = 10UL>
class openvdb::v10_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);
openvdb::v10_0::util::PagedArray::push_back_unsafe
size_t push_back_unsafe(const ValueType &value)
Definition PagedArray.h:192
openvdb::v10_0::util::PagedArray::PagedArray
PagedArray()
Default constructor.
Definition PagedArray.h:156

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();
openvdb::v10_0::util::PagedArray::getBuffer
ValueBuffer getBuffer()
Definition PagedArray.h:179

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);
}
);
openvdb::v10_0::util::PagedArray::pageSize
static size_t pageSize()
Return the number of elements per memory page.
Definition PagedArray.h:333

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;
openvdb::v10_0::util::PagedArray::resize
void resize(size_t size)
Resize this array to the specified size.
Definition PagedArray.h:287

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();
openvdb::v10_0::util::PagedArray::begin
Iterator begin()
Return a non-const iterator pointing to the first element.
Definition PagedArray.h:367
openvdb::v10_0::util::PagedArray::end
Iterator end()
Return a non-const iterator pointing to the past-the-last element.
Definition PagedArray.h:374

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

## Ptr

template<typename ValueT, size_t Log2PageSize = 10UL>

using Ptr = SharedPtr<PagedArray>

## ValueType

template<typename ValueT, size_t Log2PageSize = 10UL>

using ValueType = ValueT

## Constructor & Destructor Documentation

## PagedArray() [1/2]

template<typename ValueT, size_t Log2PageSize = 10UL>

PagedArray | ( |  | ) |

inline

Default constructor.

## ~PagedArray()

template<typename ValueT, size_t Log2PageSize = 10UL>

~PagedArray | ( |  | ) |

inline

Destructor removed all allocated pages.

## PagedArray() [2/2]

template<typename ValueT, size_t Log2PageSize = 10UL>

PagedArray | ( | const PagedArray< ValueT, Log2PageSize > & |  | ) |

delete

## Member Function Documentation

## begin() [1/2]

template<typename ValueT, size_t Log2PageSize = 10UL>

Iterator begin | ( |  | ) |

inline

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

## begin() [2/2]

template<typename ValueT, size_t Log2PageSize = 10UL>

ConstIterator begin | ( |  | ) | const

inline

## capacity()

template<typename ValueT, size_t Log2PageSize = 10UL>

size_t capacity | ( |  | ) | const

inline

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

## cbegin()

template<typename ValueT, size_t Log2PageSize = 10UL>

ConstIterator cbegin | ( |  | ) | const

inline

Return a const iterator pointing to the first element.

## cend()

template<typename ValueT, size_t Log2PageSize = 10UL>

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!

## clear()

template<typename ValueT, size_t Log2PageSize = 10UL>

void clear | ( |  | ) |

inline

Removes all elements from the array and delete all pages.

Warning
  Not thread-safe!

## copy() [1/2]

template<typename ValueT, size_t Log2PageSize = 10UL>

void copy | ( | ValueType * | p | ) | const

inline

## copy() [2/2]

template<typename ValueT, size_t Log2PageSize = 10UL>

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.

## create()

template<typename ValueT, size_t Log2PageSize = 10UL>

Ptr create | ( |  | ) |

inline static

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

## end() [1/2]

template<typename ValueT, size_t Log2PageSize = 10UL>

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!

## end() [2/2]

template<typename ValueT, size_t Log2PageSize = 10UL>

ConstIterator end | ( |  | ) | const

inline

## fill()

template<typename ValueT, size_t Log2PageSize = 10UL>

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

## freeCount()

template<typename ValueT, size_t Log2PageSize = 10UL>

size_t freeCount | ( |  | ) | const

inline

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

## getBuffer()

template<typename ValueT, size_t Log2PageSize = 10UL>

ValueBuffer getBuffer | ( |  | ) |

inline

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

## invSort()

template<typename ValueT, size_t Log2PageSize = 10UL>

void invSort | ( |  | ) |

inline

Parallel sort of all the elements in descending order.

## isEmpty()

template<typename ValueT, size_t Log2PageSize = 10UL>

bool isEmpty | ( |  | ) | const

inline

Return true if the container contains no elements.

## isPartiallyFull()

template<typename ValueT, size_t Log2PageSize = 10UL>

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.

## log2PageSize()

template<typename ValueT, size_t Log2PageSize = 10UL>

size_t log2PageSize | ( |  | ) |

inline static

Return log2 of the number of elements per memory page.

## memUsage()

template<typename ValueT, size_t Log2PageSize = 10UL>

size_t memUsage | ( |  | ) | const

inline

Return the memory footprint of this array in bytes.

## merge()

template<typename ValueT, size_t Log2PageSize>

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!

## operator=()

template<typename ValueT, size_t Log2PageSize = 10UL>

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

delete

## operator[]() [1/2]

template<typename ValueT, size_t Log2PageSize = 10UL>

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!

## operator[]() [2/2]

template<typename ValueT, size_t Log2PageSize = 10UL>

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!

## pageCount()

template<typename ValueT, size_t Log2PageSize = 10UL>

size_t pageCount | ( |  | ) | const

inline

Return the number of allocated memory pages.

## pageSize()

template<typename ValueT, size_t Log2PageSize = 10UL>

size_t pageSize | ( |  | ) |

inline static

Return the number of elements per memory page.

## print()

template<typename ValueT, size_t Log2PageSize = 10UL>

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

inline

Print information for debugging.

## push_back_unsafe()

template<typename ValueT, size_t Log2PageSize = 10UL>

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!

## resize() [1/2]

template<typename ValueT, size_t Log2PageSize = 10UL>

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!

## resize() [2/2]

template<typename ValueT, size_t Log2PageSize = 10UL>

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!

## shrink_to_fit()

template<typename ValueT, size_t Log2PageSize>

void shrink_to_fit | ( |  | ) |

Reduce the page table to fix the current size.

Warning
  Not thread-safe!

## size()

template<typename ValueT, size_t Log2PageSize = 10UL>

size_t size | ( |  | ) | const

inline

Return the number of elements in this array.

## sort() [1/2]

template<typename ValueT, size_t Log2PageSize = 10UL>

void sort | ( |  | ) |

inline

Parallel sort of all the elements in ascending order.

## sort() [2/2]

template<typename ValueT, size_t Log2PageSize = 10UL>
template<typename Functor>

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 Symbol Documentation

## ValueBuffer

template<typename ValueT, size_t Log2PageSize = 10UL>

friend class ValueBuffer

friend