Is there a way to accelerate the following algorithm for hamming distance calculation? By assembly language?

[prime_tang]

The following code is a basic algorithm for hamming distance calculation, but due to the design of my application, it requires many times to use this algorithm, in order to improve application efficiency, I want to improve the efficiency of this algorithm, is there any appropriate methods? Assembly language possible?

unsigned dist(const unsigned char *vec1, const unsigned char *vec2, unsigned dim)
{
const unsigned char popCountTable[] =
{
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};
unsigned dist_ = 0;
for (unsigned i = 0; i != dim; ++i)
{
dist_ += popCountTable[vec1[i] ^ vec2[i]];
}
return dist_;
}

[Lost User]

You should try at http://www.codeproject.com/Forums/326859/Algorithms.aspx[^], but you will need to provide more details of what this algorithm is doing and why your implementation is slow.

[Jochen Arndt]

I don't see much optimisation options. You are already using a lookup table and the code should not consume much time when dim is small. Rewriting it in assembler will be probably not faster because modern compilers will generate effective code (you may tell your compiler to generate an assembly output to check this). When the code should be always executed on modern x86 CPUs, you may replace the popcount lookup with the __popcnt x86 instruction. For MS compilers see https://msdn.microsoft.com/library/bb385231.aspx[^]. [EDIT] When using the popcnt instruction and your data are always a multiple of 2 or 4 (or 8 with 64-bit builds), you can reduce the number of loop executions by performing the operation with 16/32/64 bits.

[Chris Losinger]

Google says: http://bmagic.sourceforge.net/bmsse2opt.html[^]

image processing toolkits | batch image processing

[Shoaib]

I wouldn't recommend assembly, unless platform portability is not a concern. A relatively easier option would be to apply a Duff's device to this loop. Unrolling the loop can provide performance boost. However, unless this is, say DSP code that has to run over and over again its probably not worthwhile and the effects wont be noticable. http://en.wikipedia.org/wiki/Duff%27s_device[^] I would recommend to benchmark the code first to establish the base data for performance comparison.

[jschell]

prime_tang wrote:

but due to the design of my application, it requires many times to use this algorithm

First step would of course be to find a design that doesn't require many uses. That would have a far more significant impact on any speed up of the actual algorithm.

[Stefan_Lang]

I don't see much optimization potential in your function that a decent compiler won't apply already. That said, the first question you should ask: is there an actual performance bottleneck? Have you measured the time your application takes, and is it really too slow for your purposes? Second question: if there is a performance issue, which function is causing it? Maybe there are others called alongside this function that take more time and have more optimization potential? Typically, I/O is the slowest part of any application, so reducing I/O to the absolute minimum could already help. You say it is called often, so the next question would be: can you reduce the number of calls? You said the number of calls is high due to your application design, this implies a different design would require less calls?

GOTOs are a bit like wire coat hangers: they tend to breed in the darkness, such that where there once were few, eventually there are many, and the program's architecture collapses beneath them. (Fran Poretto)