/ Bioinformatics

MUMmer

MUMmer is one of the most used sequence alignment tools, right after BLAST. Most of its code base is quite old but still being actively developed (see MUMmer4). The following issue has been sitting in there for over five years.

struct Score
{
  long int value;
  char used;
};

struct Node
{
  Score S[3];
  int max;
};

The Node structure is used in the nucmer program for a base per base alignment. Each Node is the cell of the alignment matrix. The issue with the above definition is that a third of each Node is just padding, wasted memory. Each Score takes up 8 + 1 = 9 bytes of memory. However, as long ints have to be aligned properly, seven bytes of padding are added at the end of each Score. The following layout is much more compact.

struct Node
{
  long int values[3];
  char used[3];
  int max;
};

This structure has one byte of padding on 32 total bytes. Previously the numbers were 25 unused bytes of 52 byte. So almost half of the memory allocated was unused. With the new layout, two Nodes fit into one cache line, which also makes the code faster! On an average run nucmer uses a third less memory and is 20% faster! Unfortunately, the appropriate pull request has not yet been merged, at of the point of writing.