memcmp

Introduction

From The Open Group Base Specifications issue 7, 2018:

#include <string.h>

int memcmp(const void *s1, const void *s2, size_t n);

• The memcmp() function shall compare the first n bytes (each interpreted as unsigned char) of the object pointed to by s1 to the first n bytes of the object pointed to by s2.
• The sign of a non-zero return value shall be determined by the sign of the difference between the value of the first pair of bytes (both interpreted as type unsigned char) that differ in the objects being compared.
• tHe memcmp() function shall return an integer greater than, equal to, or less than 0, if the object pointed to by s1 is greater than, equal to, or less than the object pointed to by s2, respectively.
• No error are defined.

Implementation

Relevant concepts: Operator precedence, type casting, const keyword

Basic implementation

#include <string.h>

int	ft_memcmp(const void *s1, const void *s2, size_t n)
{
	unsigned char	*cs1;
	unsigned char	*cs2;

	if (!n)
		return (0);
	cs1 = (unsigned char*)s1;
	cs2 = (unsigned char*)s2;
	if (*cs1 == *cs2)
	{
		while (--n && *cs1 == *cs2)
		{
			++cs1;
			++cs2;
		}
	}
	return (*cs1 - *cs2);
}

Improved implementation

For more information, please refer to the Optimization Concepts page.

#include <string.h>
#include <stdint.h>

int					ft_memcmp(const void *s1, const void *s2, size_t n)
{
	const unsigned char *cs1;
	const unsigned char *cs2;
	const uint64_t 	*lls1;
	const uint64_t 	*lls2;

	cs1 = (const unsigned char *)s1;
	cs2 = (const unsigned char *)s2;
	if (n >= 8 && (((uintptr_t)s1 & 0x7) == ((uintptr_t)s2 & 0x7)))
	{
		while ((uintptr_t)cs1 & 0x7)
		{
			if (*cs1 != *cs2)
				return (*cs1 - *cs2);
			++cs1;
			++cs2;
			--n;
		}
		lls1 = (const uint64_t *)cs1;
		lls2 = (const uint64_t *)cs2;
		while (n >= 8)
		{
			if (*lls1 != *lls2)
				break;
			++lls1;
			++lls2;
			*n -= 8;
		}
		cs1 = (const unsigned char *)lls1;
		cs2 = (const unsigned char *)lls2;
	}
	if (!n)
		return (0);
	while (*cs1 == *cs2)
	{
		if (!--n)
			break ;
		++cs1;
		++cs2;
	}
	return (*cs1 - *cs2);
}

Speed tests

• Results are a percentage of the performance against a glibc memcmp [ldd (Ubuntu GLIBC 2.27-3ubuntu1) 2.27].
• Compiler is gcc [(Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0].
• for each size the test runtime is 5 seconds.
• Memory is aligned.

Basic implementation

Size\flag	-O3 -fno-builtin	-O2	-Os	(none)
1	100%	100%	98%	100%
10	100%	99%	99%	97%
100	96%	97%	93%	86%
1K	73%	75%	68%	36%
10K	25%	25%	19%	6%
100K	10%	10%	7%	2%
1M	10%	10%	7%	2%

Improved implementation

Size\flag	-O3 -fno-builtin	-O2	-Os	(none)
1	99%	100%	99%	98%
10	101%	100%	100%	98%
100	99%	99%	100%	96%
1K	96%	96%	95%	81%
10K	77%	76%	77%	32%
100K	63%	63%	63%	13%
1M	67%	67%	68%	14%

Test function

# include <time.h>
# include <string.h>
# include <stdlib.h>

size_t	memcmp_speed_test(int len, int second, int (mem)(const void *, const void *, size_t))
{
	clock_t			chrono = 0;
	clock_t			start = 0;
	size_t			i = 0;
	void			*src;
	void			*dst;

	src = malloc(len + 1);
	dst = malloc(len + 1);
	if (!dst || !src)
		exit(1);
	memset(src, 0xff, len + 1);
	memset(dst, 0xff, len + 1);
	((char *)src)[len] = 0;
	start = clock();
	while (chrono < second * CLOCKS_PER_SEC)
	{
		mem(dst, src, len);
		i++;
		chrono = clock() - start;
	}
	free(src);
	free(dst);
	return (i);
}

Other implementations

• MUSL libc memcmp
• GNU libc memcmp