HSGrep benchmarking
Benchmark for binary search grep in Haskell

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!

HSGrep benchmark

November 30, 2011
117 words

haskell benchmark

Contact me

Hi! I'm Lorenzo Bolla, Senior Software Architect in London, UK.

When I'm not programming in Python, Rust, Go or Haskell, I am playing either basketball, piano or chess.