Optimized memchr() Implementation For The Linux Kernel Up To ~4x Faster

Written by Michael Larabel in Linux Kernel on 10 July 2022 at 01:58 PM EDT. 25 Comments
A set of proposed patches promise to make the Linux kernel's memchr() implementation faster for locating a character within a block of memory. In tests carried out by the developer, the new implementation can be nearly four times faster on large searches.

The latest memchr() patches sent out this Sunday for the Linux kernel aim to speed-up this function that can be around ~4x faster for long strings. Yu-Jen Chang who sent out the patches explained:
The original version of memchr() is implemented with the byte-wise comparing technique, which does not fully use 64-bits or 32-bits registers in CPU. We use word-wide comparing so that 8 characters can be compared at the same time on CPU. This code is base on David Laight's implementation.

We create two files to measure the performance. The first file contains on average 10 characters ahead the target character. The second file contains at least 1000 characters ahead the target character. Our implementation of “memchr()” is slightly better in the first test and nearly 4x faster than the original implementation in the second test.

This may be nice for micro-benchmarking memchr() but in the grand scheme probably won't equate to any material benefits for end-users especially as the biggest performance gains will be with very long strings. Checking the Linux kernel source tree today, there are around 129 times memchr() (or ~323 for different variations of memchr) is used ranging from just the Linux kernel tools to being used within file-system code and various drivers.

The patches for those interested can be found on the Linux kernel mailing list for review.
Related News
About The Author
Michael Larabel

Michael Larabel is the principal author of Phoronix.com and founded the site in 2004 with a focus on enriching the Linux hardware experience. Michael has written more than 20,000 articles covering the state of Linux hardware support, Linux performance, graphics drivers, and other topics. Michael is also the lead developer of the Phoronix Test Suite, Phoromatic, and OpenBenchmarking.org automated benchmarking software. He can be followed via Twitter, LinkedIn, or contacted via MichaelLarabel.com.

Popular News This Week