First thing first: we accidentally sabotaged
Data.Text. Its variant used tuples for the outer loop state instead of the data type with strict fields — quite a disadvantage. It now performs a bit better than
String. Please accept our apologies for screaming that that sky was falling down.
I’ve posted a prettied-up slice of our benchmarking suite on my university personal page. It’s the main algorithm from the data types post for
UArray Int Char,
Seq Char, and
We also include a
ByteString version that has some further optimizations we came up with after the fact. Please try to best it! Enjoy!
SPECIALISE pragma vs copy-and-paste
Turns out the slight overhead of SPECIALISE we were seeing was most likely incidental and just happened to look systematic. We had decided to use the pragma in this code release, since it’s just so much cleaner that way. That gave
Text a significant performance boost and that’s how we realized we had copied from the wrong variant when writing the
Text variant. This is exactly why we were so concerned that the SPECIALISE pragma somehow had some overhead: copy-and-pasting is just begging for bugs! … so ashamed …
Here’s what we get when we run this code as released (with SPECIALISE pragmas) and also with manual specialization via copy-and-paste. Note that use of the SPECIALISE pragma shows no overhead.
|variant||average time (s)||slow down factor||standard deviation||SNR|
|with the SPECIALISE pragma|
|with manual specialization via copy-and-paste-and-annotate|
(I just ran the SPECIALISEd version again in the background while editing this post and
String slightly outperformed
Text. This nondeterminism is driving me nuts.)
Also, check out Max Bolingbroke’s
edit-distance library. That’s the only “related work” we found on hackage, and from his source code comments it looks like he’s waaay better at optimizing than we are.
That last post we promised is still in the works… thanks for your patience. Due dates, due dates, due dates!