Difference between revisions of "GPU621/Braindead"

From CDOT Wiki
Jump to: navigation, search
m
(Updated STL section with Container Class Templates)
Line 4: Line 4:
  
 
== Group Members ==
 
== Group Members ==
 +
Joseph Chan
 +
Bowen Chu
 +
Henry Xu
 +
 +
== Background ==
 +
C++11 introduces many improvements and modifications, such as the addition of function objects and hash tables. These can be
 +
found within the STL, which stands for Standard Template Library. It consists of commonly used containers, algorithms,
 +
functions and iterator templates.
 +
 +
The C++11 STL has container classes such as a list and deque. However, the methods within these classes do not have built-in
 +
concurrency, despite the STL having thread classes that may be used for parallelization. Intel's oneAPI Threading Building
 +
Blocks (oneTBB) implements similar container classes that, unlike the STL container classes, has built-in concurrency which
 +
allows operations performed with them to be executed in parallel. Thus, oneTBB is one of many tools that can be used for
 +
parallel programming with containers.
 +
 +
== Standard Template Library (STL) ==
 +
The STL has many container classes. In this section, only three of the container types will be covered: vector, queue, and
 +
hash table.
  
−
Joseph Chan
+
=== Container Class Templates ===
 +
==== std::vector ====
 +
The std::vector template has an underlying data structure of a dynamic array. That is, the std::vector stores elements in a sequence akin to an array, but also has the functionality of resizing to match the capacity to the number of elements in the container. Upon adding or removing elements, the std::vector will resize itself to create or remove space depending on the number of elements that will be added.
 +
 
 +
Member functions:
 +
* at - accesses the specified element but throws an exception if it is out of bounds
 +
* operator[] - accesses the specified element
 +
* front - accesses the front element
 +
* back - accesses the back element
 +
* empty - checks whether the container is empty
 +
* size - returns the number of elements
 +
* clear - deletes all elements
 +
* insert - inserts elements
 +
* emplace - constructs and inserts an element
 +
* erase - deletes an element
 +
* push_back - adds an element to the end
  
−
Bowen Chu
+
==== std::queue ====
 +
The std::queue template has the same properties as std::vector in that it is a dynamically resizing array, but implements the First-In First-Out (FIFO) approach. This means that the first element to be added into the std::queue will be the first element to be removed from the queue. It also implies that the last element to be added will be the last element to be removed.
  
−
Henry Xu
+
Member functions:
 +
* front - accesses the first element
 +
* back - accesses the last element
 +
* empty - checks whether the container is empty
 +
* size - returns the number of elements
 +
* push - inserts an element at the front
 +
* emplace - constructs and inserts an element at the front
 +
* push - inserts an element at the front
 +
* pop - removes the first element
  
−
== Progress ==
+
==== std::unordered_map ====
 +
The std::unordered_map template has an underlying data structure of a hash map (or hash table). A hash map is an unsorted table of key-value pairs that have unique keys. In other words, there cannot be two or more pairs in the table that have the same key. In a hash table, the keys of the pairs are hashed by using a hash function.
  
−
=== June 13, 2021 ===
+
Member functions:
−
Created this page and decided on this topic: C++11 Threads Library Comparison to OpenMP - Case Studies.
+
* at - accesses the specified element but throws an exception if it is out of bounds
 +
* operator[] - accesses or inserts a specified element
 +
* find - finds an element with a specific key
 +
* empty - checks whether the container is empty
 +
* size - returns the number of elements
 +
* clear - deletes all elements
 +
* insert - inserts elements
 +
* emplace - constructs and inserts an element
 +
* erase - deletes an element
  
−
=== June 27, 2021 ===
+
=== Container Performance ===
−
Switched topic to C++11 STL Comparison to TBB - Case Studies.
+
==== Vector ====
 +
==== Queue ====
 +
==== HashMap ====
  
−
=== August 11, 2021 ===
+
== Thread Building Blocks (TBB) ==
−
Updated research.
+
=== Container Class Templates ===
 +
==== tbb::concurrent_vector ====
 +
==== tbb::concurrent_queue ====
 +
==== tbb::concurrent_hash_map ====
 +
=== Container Performance ===
 +
==== Concurrent Vector ====
 +
==== Concurrent Queue ====
 +
==== Concurrent HashMap ====
  
−
== Report ==
+
== STL and TBB Comparison ==
 +
=== Advantages and Disadvantages ===

Revision as of 00:30, 12 August 2021


GPU621/DPS921 | Participants | Groups and Projects | Resources | Glossary

C++11 STL Comparison to TBB - Case Studies

Our goal is to compare the STL to the TBB in C++11.

Group Members

Joseph Chan Bowen Chu Henry Xu

Background

C++11 introduces many improvements and modifications, such as the addition of function objects and hash tables. These can be found within the STL, which stands for Standard Template Library. It consists of commonly used containers, algorithms, functions and iterator templates.

The C++11 STL has container classes such as a list and deque. However, the methods within these classes do not have built-in concurrency, despite the STL having thread classes that may be used for parallelization. Intel's oneAPI Threading Building Blocks (oneTBB) implements similar container classes that, unlike the STL container classes, has built-in concurrency which allows operations performed with them to be executed in parallel. Thus, oneTBB is one of many tools that can be used for parallel programming with containers.

Standard Template Library (STL)

The STL has many container classes. In this section, only three of the container types will be covered: vector, queue, and hash table.

Container Class Templates

std::vector

The std::vector template has an underlying data structure of a dynamic array. That is, the std::vector stores elements in a sequence akin to an array, but also has the functionality of resizing to match the capacity to the number of elements in the container. Upon adding or removing elements, the std::vector will resize itself to create or remove space depending on the number of elements that will be added.

Member functions:

  • at - accesses the specified element but throws an exception if it is out of bounds
  • operator[] - accesses the specified element
  • front - accesses the front element
  • back - accesses the back element
  • empty - checks whether the container is empty
  • size - returns the number of elements
  • clear - deletes all elements
  • insert - inserts elements
  • emplace - constructs and inserts an element
  • erase - deletes an element
  • push_back - adds an element to the end

std::queue

The std::queue template has the same properties as std::vector in that it is a dynamically resizing array, but implements the First-In First-Out (FIFO) approach. This means that the first element to be added into the std::queue will be the first element to be removed from the queue. It also implies that the last element to be added will be the last element to be removed.

Member functions:

  • front - accesses the first element
  • back - accesses the last element
  • empty - checks whether the container is empty
  • size - returns the number of elements
  • push - inserts an element at the front
  • emplace - constructs and inserts an element at the front
  • push - inserts an element at the front
  • pop - removes the first element

std::unordered_map

The std::unordered_map template has an underlying data structure of a hash map (or hash table). A hash map is an unsorted table of key-value pairs that have unique keys. In other words, there cannot be two or more pairs in the table that have the same key. In a hash table, the keys of the pairs are hashed by using a hash function.

Member functions:

  • at - accesses the specified element but throws an exception if it is out of bounds
  • operator[] - accesses or inserts a specified element
  • find - finds an element with a specific key
  • empty - checks whether the container is empty
  • size - returns the number of elements
  • clear - deletes all elements
  • insert - inserts elements
  • emplace - constructs and inserts an element
  • erase - deletes an element

Container Performance

Vector

Queue

HashMap

Thread Building Blocks (TBB)

Container Class Templates

tbb::concurrent_vector

tbb::concurrent_queue

tbb::concurrent_hash_map

Container Performance

Concurrent Vector

Concurrent Queue

Concurrent HashMap

STL and TBB Comparison

Advantages and Disadvantages

Retrieved from "https://wiki.cdot.senecapolytechnic.ca/w/index.php?title=GPU621/Braindead&oldid=155539"