Changes

Generic Programming is a an objective when writing code to make algorithms reusable and with the least amount of specific code. Intel describes generic programming as "''writing the best possible algorithms with the least constraints''". An example of generic code is STL's templating functions which provide generic code that can be used with many different types without requiring much specific coding for the type( an addition template could be used for int, double, float, short, etc without requiring re-coding). A non-generic library requires types to be specified, meaning more type-specific code has to be created.  [[File:gputemplates.PNG |thumb|center|600px| An example of generic coding]]

The STL was created as a general purpose computation library that a focus on generic programming. The STL uses templates extensively to achieve compile time polymorphism. In general the library provide four components: algorithms, containers, functions and iterators. The library was, mostly, created by Alexander Stepanov due to his ideas about generic programming and its potential to revolutionize software development. Because of the ability of C++ to provide access to storage using pointers, C++ was used by Stepanov, even though the language was still relatively young at the time.  After a long period of engineering and development of the library, it obtained final approval in July 1994 to become part of the language standard. ==List of A Comparison from STL Functions:==In general, most of STL is intended for use within a serial environment. This however changes with C++17's introduction of parallel algorithms.

Are supported by STL for various algorithms such as sorting, searching and accumulation. All can be found within the header "'''<algorithm>'''". Examples include sort() and reverse functions()functions.

STL supports a variety of containers for data storage. Generally these containers are supported in parallel for read actions, but does not safely support writing to the container with or without reading at the same time. There are several header files that are included such as "'''<vector>'''", "'''<queue>'''", and "'''<deque>'''".'''Most STL containers do not support concurrent operations upon them.'''They are coded as:<pre>#include<vector>#include<dequeue>#include<queue> int main(){ vector<type> myVector; dequeue<type> cards; queue<type> SenecaYorkTimHortons; }</pre>

==List <u>'''Memory Allocater'''</u>The use of TBB a memory allocator allows more precise control over how dynamic memory is created and used. It is the default memory allocation method(ie not the "new" keyword) for all STL containers==. The allocaters allow memory to scale rather then using delete and 'new' to manage a container's memory. They are defined within the header file "'''<memory>'''" and are coded as: <pre>#include <memory>

void foo(){std::allocater<type> name;}</pre> ==A Comparison from TBB=====Containers==='''<u>concurrent_queue</u>''' : This is the concurrent version of the STL container Queue. This container supports first-in-first-out data storage like its STL counterpart. Multiple threads may simultaneously push and pop elements from the queue. Queue does NOT support and front() or back() in concurrent operations(the front could change while accessing). Also supports iterations, but are slow and are only intended for debugdebugging a program. This is defined within the header "'''tbb/concurrent_queue.h'''" and is coded as: <pre>

'''<u>concurrent_vector</u>''' : This is a container class for vectors with concurrent(parallel) support. These vectors do not support insertion or erase operations but do support operations done by multiple threadssuch as push_back(). Note that when elements are inserted, they cannot be removed without calling the clear() member function on it, which removes every element in the array. The container when storing elements does not guarantee that elements will be stored in consecutive addresses in memory. This is defined within the header "'''tbb/concurrent_vector.h'''" and is coded as: <pre>

==Lock Convoying Problem=The Speed Improvement====What As the table suggests, completing push back operations using tbb's concurrent vector allows for increased performance against a serial connection. TBB additionally provides a benefit that it will never need to resize the vector as pushback operations are completed. In STL, the vector is a Lock?===dynamically allocated which requires it to reallocate and copy memory over which may further slow down the push back operation.

A Lock(also called "mutex") is a method ===Why was TBB slower for programmers Int?===When dealing with primitive types like int, the actual operation to secure code push back is not very complex; meaning that when executing in parallel a serial process can cause multiple threads to fight for a resource/container for some operationcomplete the push back quite quickly. When threads work in parallel to complete The vector can also likely hold a task with containers, there is no indication when the thread reach the container and need lot more data before requiring to perform an operation on itreallocate its memory. This causes problems TBB's practicality comes when multiple threads are accessing the same place. When doing an insertion performing a more complex action on a primitive type or from a simple action on a container with threads, we must ensure only 1 thread is capable of pushing more complex type. Parallel overhead(the resources required to it or else threads support tbb in parallel) may fight for controlalso increase the time required which could be the cause of the slowdown in the above comparison. By "Locking" TBB also provides automatic chunking and describes the container, we ensure only benifit for use of parallel_for is 1 thread accesses at any given timemillion clock cycles.

To use a lock, you program must be working in parallel(ex #include <thread>) ==Business Point of View Comparison for STL and should be completing something in parallel. You can find c++11 locks with #include <mutex>TBB=={| class="wikitable collapsible collapsed" style="text-align: left;margin:0px;"

//Protect until Unlock() TBB is calledfor multi-threading and STL is for single threading workloads. Only 1 thread may do this below at a time. It is //"locked"NightsWatchThe fastest known serial algorithm maybe difficult or impossible to parallelize.Lock();

//IncrementDaysWithoutWhiteWalkerAttack++;std::cout << "It has been " << DaysWithoutWhiteWalkerAttack << " since the last attack at Castle Black!\n"Some aspects to look out for when parallelizing your code are;

Note that there can be problems with locks. If a thread is locked but *Correct Problem Size, when testing for efficiency, it may show poor efficiency if the problem size is never unlockedtoo small. So, any other threads will be forced you would want to wait which may cause performance issuesuse serial instead, if the problem size is always small. Another If you have a large problem size and has great efficiency, then parallel is called "Dead Locking" where each thread may be waiting for another to unlock (and vice versa) and the program is forced way to wait and wait .go

Within STL, issues arise when you attempt to access containers in parallelResource: http://ppomorsk. With containers, when threads update the container say with push back, it is difficult to determine where the insertion occurred within the container(each thread is updating this container in any order) additionally, the size of the container is unknown as each thread may be updating the size as it goes (thread A may see a size of 4 while thread B a size of 9)sharcnet. For example, in a vector we can push some data to it in parallel but knowing where that data was pushed to requires us to iterate through the vector for the exact location . If we attempt to find the data in parallel with other operations ongoing, 1 thread could search for the data, but another could update the vector size during that time which causes problems with thread 1's search as the memory location may change should the vector need to grow(performs a deep copy to new memory)ca/Lecture_2_d_performance.pdf

===Lock Convoying in TBB===TBB attempts to mitigate the performance issue from parallel The increasing complexity of your code when accessing or completing an operation on a container through its own containers such as concurrent_vector. Through '''concurrent_vector''', every time an element is accessed/changed, a return of the index location is givennatural problem when working in parallel. TBB promises that any time an element is pushed, it will always be in Knowing the same location, no matter if the size of the vector changes responsibilities as in memory. With what you must worry about as a standard vector, when the size of the vector changes, the data developer is copied overkey. If any threads are currently traversing this vector when the size changesWhen trying quickly implement parallel regions in your code, any iterators may no longer be validor to just to keep your code serial.

Study RefIf you are going to try to parallelize your code using STL coupled with the threading libraries this is what you must worry: https://software.intel.com/en-us/blogs/2008/10/20/tbb-containers-vs-stl-performance-in-the-multi-core-ageThis leads into Concurrent_vector growing below..

==Efficiency Comparison Parallel *Thread Creation, terminating, and synchronizing, partitioning, and management must be handled by you. This increases the work load and the complexity, the thread creation and overall resource for and concurrent_vector==STL is managed by a combination of libraries.

''If only you knew *Dividing collection of data is more of the power of problem when using the Building Blocks''STL containers.

*Partitioning data.

====TBBWorries and Responsibilities====*Thread Creation, terminating, and synchronizing, partitioning, thread creation, and management is managed by TBB. This make you need not to worry about the heavy constructs of threads which are close to the hardware level.

*Making a solution from close to hardware level allows Own Parallel algorithms (makes you need not to be flexible to worry about the solution you heavy constructs of threads that are wanting to make. But present in the major downside is the requirement lower levels of implementing the foundations first to make your solution workprogramming. It also simple map, scan, pipeline, or reduce TBB has the potential of making your program inefficient if not done correctly.you covered

TBB does have Parallel Algorithms support*Dividing collection of data, that has been already mentioned. the block range coupled with it algorithms makes it simpler to divide the data