Exploring memcmp

http://justin.harmonize.fm/index.php/2009/05/exploring-memcmp/

by jmtulloss • 17 years ago

16 16 17 years ago

justin.harmonize.fm

tptacek4• 17 years ago

I don't have the time or energy to make a valuable comment about this, but my hunch is that in the real world, cache effects dominate instruction selection in how fast in-memory searching is.

jmtulloss4• 17 years ago

Agreed. In this case, I/O will tend to dominate as well. Looking into the optimized memcmp was fun though.

jws2• 17 years ago

7% speedup by going with SIMD instructions. I think I'd have guarded the memcmp() call with a check of the first byte and saved the call overhead on 99.5% of the bytes instead (insert assumptions on data).

jmtulloss4• 17 years ago

memcmp returns as soon as it finds a byte that doesn't match.

rarrrrrr• 17 years ago

memcmp is not the way to do it.

A much faster solution would be the same approach rsync takes with its "rolling checksum." To calculate the weak checksum of each block as you roll along the length of the file, you only have to do a calculation involving the bytes rolling out and in. http://samba.anu.edu.au/rsync/tech_report/node3.html

Then, for only the blocks that match this weak checksum, do memcmp or a strong digest check.

cperciva• 17 years ago

memcmp is not the way to do it.

Absolutely. The right way to do it is to use the memmem library call.

A much faster solution would be the same approach rsync takes with its "rolling checksum."

That's one way to improve performance, yes. (But it far predates rsync -- I think it might even predate Tridge.)

In many cases, a "look and skip" algorithm like KMP or BM will outperform a rolling checksum search; but of course if you've got 328MB of data on disk, nothing will make the search faster than the time it takes to read the data into RAM.

jmtulloss4• 17 years ago

memmem only returns the first string. I'm looking for a count of all the matches, with their byte offsets in the file.

brtzsnr• 17 years ago

""" A much faster solution would be the same approach rsync takes with its "rolling checksum." """

I know this function is attributed to Bernstein and it's called Bernstein hash [0]. You're describing the Rabin-Karp string matching algorithm [1].

[0] http://fr.wikipedia.org/wiki/Table_de_hachage#Fonction_de_Ha...

[1] http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algori...

codesink2• 17 years ago

the boyer-moore algorithm should have been used. it would probably outperform any other given implementation for this kind of problems.

Exploring memcmp

Related Stories