Note: code for this project can be found on the project’s GitHub page.
Inspiration
In a series of recent posts, I wrote about a combinatorial object called a Latin square, a class in written C++ used to work with these objects, and some GPGPU (General Purpose GPU) algorithms I have developed to determine certain properties of these objects. Despite the performance improvements from porting the code base for this project to C++ and re-implementing the algorithms using multithreading (MPI, pthreads) and GPGPU computing, memory efficiency problems have arisen and will persist as the order of the Latin squares increases due to the combinatorial growth in the number of squares that need to be processed. Even now, when running the algorithms for relatively small orders, I am using all 32 GB of RAM available on my machine, causing the program to crash.
One solution to this problem is to write the Latin squares to a number of files which can later be post-processed before analyzing the results. This allows the objects storing the Latin squares (vectors, sets, unordered_sets, etc.) to be cleared, freeing up some memory. When implementing a file manager to handle writing these files while continuing to process the Latin squares, I thought there might be more widespread applications of such a queue and have created a simple framework that can easily be incorporated into any project. In this post, I discuss the implementation of the job queue I’ve written to manage the file writing for this research project.
Implementation
Objects We Print Must Be Printable
To make the file manager general-purpose, an abstract class is used to ensure the objects being written to a file contain a method to convert them to a string.
This abstract class ensures the objects being written to the file(s) implement the getPrintString() method. The return value of this method is what is written to a file followed by a line break. A very simple example implementation might look like this PrintableInt class which was used to test the file manager
This is a very rudimentary example. The PrintableInt class stores an integer value and, when being printed, returns the string representation of that value using the standard library’s to_string(…) function.
Writing Files Happens Off the Main Thread
To maintain computational efficiency, the file writing jobs shouldn’t take compute time from the main thread (which in my case should be processing Latin squares). Because of this, the file manager has a manager thread that is maintained by the class which handles all of the file writing and job dequeuing. To implement this control, the FileManager class definition looks like this
First, a JobVector type is defined as a std::vector of PrintableObjects. After trying to manage the <‘s and >’s while developing this class, I decided a type definition was appropriate (plus it’s a lot of typing). Next, a FileManagerException class is defined which extends the runtime_error class. This is for the sake of convenience as runtime errors can sometimes be difficult to find. When an instance of the FileMangerException is thrown at runtime it is much easier to find, in general, where the error is coming from.
Finally, the FileManger class is defined. This class has methods to start the manager thread, stop the manager thread (which also finishes the queued jobs), initialize a file (more or less adding the file to the maps/vectors used to manage the jobs), and queue jobs. There are two maps that store a filename to a particular object: one maps the filename to a pointer to an std::ofstream object which is the handle of the output file and the other maps the filename to a vector of JobVectors (std::vector<std::vector<std::shared_ptr<PrintableObject>>>).
Other variables being stored are the option to append to the files (bool _append) rather than overwrite them and the pthread handle to the manager thread so it can be stopped when the FileManager is stopped.
The implementation of these methods is provided below and can be found on the project’s GitHub.
Adding full code to a post makes the post much longer (especially C++ code). Because of this I will forego an explanation of this implementation but have added ample comments to the code to explain what everything is doing.
A Small Test
Using the aforementioned PrintableInt object, a short test of the FileManger was created.
In this test, random numbers from 1 to 100 are generated (100 per job for 20 jobs). The 20 jobs are spread evenly over 4 files. As the jobs are generated they are queued in the FileManger which actively processes the jobs. Once all of the jobs are queued the FileManager is stopped which takes some time as the remaining jobs are being processed. Again, more details are given in the code comments. This code can be compiled via
g++ -O3 --std=c++14 -I. -Wall -lpthread FileManagerTest.cpp -o fmt
and ran via
./fmt
Future Work
Further Threading
Currently, the file writing takes place on the manager’s thread. To make this more efficient, the file writing itself could be started on another thread and could indicate to the main thread when writing is complete so a new job could be created on another new thread (to prevent multiple threads from writing to the same file). I had an implementation like this created but was having a few issues so I settled on a slightly less efficient implementation to move on to other parts of the project.
Further Abstraction
Why does it have to be a file writing job queue, why not just an off-the-main thread job queue? The principles in the FileManager apply to almost any job queue. Further abstraction could be implemented that allows implementers to define, start, and stop a management thread, queue any type of job, and define what to do when processing a job. This implementation, I suspect, would be pretty straightforward with just a few more abstract classes.