CSE 305 - Tutorial 7 - Fine-grain and lazy concurrent sets

File benchmarking_sets.cpp contains the code performing a prescribed number of insertions into the coarse- and fine-grained versions of ListSet and measuring the runtime. You can compile it with make set_benchmarker and run as ./set_benchmarker num_threads num_insertions (for example ./set_benchmarker 2 1000). However, the code provided to you works only for a single thread at the moment.

You are asked to do the following:

• complete the code so that, for every value of the num_threads, it performes the prescribed number of insertions from several threads in parallel;
• collect the runtime data for different number of threads (a bit beyond the number of cores on you machine) and different values of insertions (ranging from 1000 and 50000). Analyze how the performace changes depending on the method, number of threads, and number of insertions (not just qualitatively “larger/smaller” but also more quantitatively “linear/quadratic/constant factor”). Explain the patterns you observe, write the runtimes and your explanations in the comments after the code. If your machine does not have enough cores for an interesting analysis, use the machines in the classroom (you can connect to them by ssh).

Design a version of the SetList class (fine grained version), BoundedSetList, that has fixed capacity, and a thread inserting an element into a set that has reached the capacity and does not contain the element gets blocked. Note that the data structure should be still fine-grained, that is, the mutex count_lock should be taken only at the moment of actual insertion. If at this point the capacity has already reached, you should unlock everything and wait for the empty space to appear, and start the insertion all over. For further details, see td7.cpp.

Improve the lazy version SetListLazy (provided in the archive, see also the second section of the lecture) to MultisetList, a class implementing a multiset, that is, a set that contains each element with a multiplicity. The add method will increase the multiplicity by one if the element is already in the set. The remove method will decrease the multiplicity if it is positive, and return false only if there was no such element in the set. Furthermore, it is required that elements with zero multiplicity are eventually deleted from the set.

Note that, if you store the multiplicity, you do not need the marked field anymore.