Home | Articles | CV (pdf | short)
<2011-11-30> by Lorenzo

HSGrep benchmarking

Few days ago, I rewrote sgrep in Haskell. I was curious to know how it compares to grep in term of execution speed. In particular, I was interested to verify that hsgrep scales as O(log n), instead of O(n), with n being the size of the file analyzed.

First of all, in order to have similar performance to grep, I had to convert my original program to use Haskell's bytestrings. You can find the code here. Testing files are generated with this script.

Here are the results obtained. grep is still faster for smallish files (I haven't spent too much time tweaking hsgrep), but hsgrep scales much better and it wins for files larger than few megabytes!


Figure 1: HSGrep benchmark