Multi-(threading | processing) ?

My third adventure in the parallel world started off with my own code - a lexer for C, written in Python. To those of you who are new to terminology of compiler design - lexical analysis is the step 0 of the compilation process.
In a nutshell, a lexer performs the following functions:

• Strip off comments from the source code
• Generate tokens i.e seggregate input code into identifiers, operators, punctuation etc...
• Populate the symbol table

So, how are the tokens generated?

The input code is matched with a bunch of predefined regular expression and classified accordingly. Sounds simple enough? At this point, it is worth noting that this can be really expensive for large pieces of code as the expressions themselves are not guaranteed to be simple. But wait, can't this be done in parallel?  Yes, you hit the nail right on its head!

Revisiting our problem with the "parallel eye"

Ideally, we want some workers that scan the input in parallel. As soon as one worker finds the matching regular expression, we want all the workers to stop. It reminds me of the time when I made my whole family search for my spectacles at home while I'd actually left it in college! That's right, we have to deal with input that matches nothing as well.

Parallelism in Python

Python is a language that has never disappointed me in its collection of libraries and quite expectedly-voila! We are all well familiar with the differences between processes and threads as stated by our dear old python; nevertheless, I thought this would be a good opportunity to explore into the same.

Mutiprocessing vs Multithreading

Implementing the lexer with multi-(threading|processing) can be approached in two ways:

• Make each worker return the match object or None
• Make each worker update a global variable

Obviously, the second option is better, as we can let other workers terminate if and when the global variable is set. This is precisely where I was accurately wrong, fundamentally!  Processes don't share memory - hence, even if the different worker processes saw the same initial value of the global variable, they would be updating their own local copies of the global variable; thus defeating the purpose successfully! Not to mention, sharing the variable among processes is not really worth the effort.
On the other hand, threads (even with python's GIL) serve our purpose to a great extent.

As you pretty much guessed, the red dots correspond to multiprocessing while the green ones to multithreading. The separation is strikingly large!

Hope this post made you a little curious about the parallel world of python! Adios till my next adventure - happy coding in a parallel world. 😊

P. S: All relevant code and readme files will be here.

A Simple Text Editor

A parallel world has many doors,
With lots to explore and lots to find.
Knock knock and thee shall ask for more,
With fork and join, to blow your mind.

Enough with the theatricals? Yes, I understand.

So, for my second adventure in the parallel world, I set out to inspect parallelism in Java. Don't worry - this is not going to be the nine hundred and ninety ninth post that you are reading, explaining Java's incredible journey from threads to executor service! Contrarily, this is about my experience in putting the same into use.

I found this cute, simple text editor written in Java on GitHub, that I thought had some scope for improvement. It had most of the features of a typical text editor, except for scroll pane (which I thought was pretty necessary). After sufficient twiddling, I happened to notice that it had no "find all" feature and there was my light-bulb moment - implementing a parallel search for a word in a document.


Implementing a parallel search for a word in a document

If you think about it, it is piece of cake - You have some jumbo text, in which you have to find the occurrence of a word. All you java lovers are probably wondering why all this hue and cry for a simple String.indexOf() function call. Well, I was also in agreement till I discovered that the indexOf function is, in reality, implemented as O(mn) algorithm.  (If you are fortunate enough to have not come across this notation, you can either refer here or take my word for "We can do better".)

A simple parallel approach to the same problem is to divide the search among threads i.e break up the jumbo text into smaller chunks and make each thread return occurrences of the search string. But wait, what if the word is spread across the chunks? Yes, we have to handle that case separately.

A screenshot of the find all implementation

All said and done, with a few lines of code, this new feature was added to the text editor. It seemed to perform pretty well with a running time of 2 milliseconds for 237 occurrences in a text of about 20000 characters (using the same old O(mn) algorithm). However, there was no significant change in the performance when the number of threads was increased.

Hope you liked this short simple post on Java parallelism. Look forward to more in the upcoming posts. Till such time, happy coding in a parallel world.😊

P.S. All relevant code will be available here.

The Page Rank Mystery

I kick-started my quest for some long slow code, out there, lost in the GitHub world, waiting to be rescued by some parallel programmer, who'd walk by, and wave his magic openmp wand and change the world. Eventually I discovered that hunting for "slow code" is a wild goose chase; it makes much more sense to look for "interesting code". Voila-algorithm implementations!

So I stumbled upon this repository implementing the infamous page rank algorithm. Much to my disappointment, it was very well-written in Greek. The readme directed me to this useful link: How Google Finds Your Needle in the Web's Haystack, that explained the latent ugly math of the algorithm. Henceforth, I dived into the C++ code to get a clearer picture of what is happening.

The code was surprisingly very fast for large inputs (about 1.2 seconds for 100000 vertices). This is probably because of the extensive use of library functions that are assuredly compiler friendly. An extremely useful lesson: When you write code, exploit the language library as much as you can! Nevertheless, when I looked at 0.65 seconds response time on Google search results page, I hoped that there might be some scope for improvement. 

A quick examination of the code from the perspective of a profiler yields obvious results : that the page rank computation is essentially the bottleneck.  I suppressed my instincts to instantly use the #pragma mantra and played around with the serial code. For instance, it might have caught your eye that the current element of the H vector is computed in each and every iteration!

But wait! Aren't computations involving double data types expensive? Loss of precision? It depends on the representation? Either way, why would I want to compute it every single time? Can't I just compute once and store it in an array? Isn't that more cache friendly?

Yes. I had the same set of questions on my mind. As it turns out, I could not have been more wrong. The computation, though expensive, is conditional. For a sparse matrix, pre-computing values in an array would hardly make any difference; in fact, pray that it does not add more overhead. This led me to my second lesson: Don't always blame the expensive computation.

Parallelizing the computations on the rows using good old openmp reduced the running time by 0.2 seconds (16% speedup). Frankly, I was balked. Ouch! Expectations hurt. I welcome any comments on your speculation of the reason. 

Moving on, my next move was to address the smaller elephant in the room - the file input. Reading a huge file line by line seems highly inefficient for several reasons such as increase in number of system calls and therefore increased interrupts, the file pointer has to be moved more frequently etc...

So, what is the most efficient way to read a file? Perhaps read the entire file into a string and then parse the string. I tested the same with a sample file and realized that this was indeed the case.

Hurrah! Our page rank algorithm got 0.15 s faster!

Summing up, I believe that the optimization is still "work in progress". But that is for another time in another post. Till such time, happy coding in a parallel world. 😊

P.S: All the relevant code and readme files will be available in my gitHub account.