strcmp

Introduction

From The Open Group Base Specifications issue 7, 2018:

#include <string.h>

int strcmp(const char *s1, const char *s2);

• The strcmp() function shall compare the string pointed to by s1 to the string 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 strings being compared.
• Upon completion, strcmp() shall return an integer greater than, equal to, or less than 0, if the string pointed to by s1 is greater than, equal to, or less than the string pointed to by s2, respectively.
• No error are defined.

Implementation

Relevant concepts: Operator precedence, type casting, const keyword

Basic implementation

int	ft_strcmp(const char *s1, const char *s2)
{
	while (*s1 == *s2 && *s1 && *s2)
	{
		++s1;
		++s2;
	}
	return (*(unsigned char *)s1 - *(unsigned char *)s2);
}

Improved implementation

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

# include <stdint.h>

int	ft_strcmp(const char *s1, const char *s2)
{
	const unsigned char	*cs1;
	const unsigned char	*cs2;
	const uint64_t		*ll1;
	const uint64_t		*ll2;
	uint64_t			one_each_byte;

	cs1 = (const unsigned char *)s1;
	cs2 = (const unsigned char *)s2;
	if ((((uintptr_t)s1 & 0x7) == ((uintptr_t)s2 & 0x7)))
	{
		while ((uintptr_t)cs1 & 0x7)
		{
			if (*cs1 != *cs2 || !*cs1)
			return (*cs1 - *cs2);
			++cs1;
			++cs2;
		}
		one_each_byte = 0x0101010101010101L;
		ll1 = (const uint64_t *)cs1;
		ll2 = (const uint64_t *)cs2;
		while (1)
		{
			if ((*ll1 != *ll2)
				|| (((*ll1 - one_each_byte) & ~*ll1) & (one_each_byte << 7)))
				break ;
			++ll1;
			++ll2;
		}
		cs1 = (const unsigned char *)ll1;
		cs2 = (const unsigned char *)ll2;
	}
	while (*cs1 == *cs2)
	{
		if (!*cs1)
			break ;
		++cs1;
		++cs2;
	}
	return (*cs1 - *cs2);
}

Speed tests

• Results are a percentage of the performance against a glibc strcmp.
• Compiler is gcc [Apple LLVM version 10.0.1 (clang-1001.0.46.4)].
• for each size the test runtime is 5 seconds.
• Memory is aligned.

Basic implementation

Size\flag	-O3 -fno-builtin	-O2	-Os	(none)
1	98%	101%	94%	97%
10	98%	100%	98%	95%
100	89%	90%	88%	62%
1K	52%	53%	49%	16%
10K	16%	16%	14%	3%
100K	12%	12%	10%	2%
1M	13%	14%	11%	3%

Improved implementation

Size\flag	-O3 -fno-builtin	-O2	-Os	(none)
1	100%	100%	98%	96%
10	99%	99%	99%	98%
100	101%	98%	98%	91%
1K	92%	92%	91%	67%
10K	64%	64%	64%	24%
100K	56%	57%	56%	17%
1M	67%	66%	67%	21%

Test function

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

size_t	strcmp_speed_test(int len, int second, int (str)(const char *, const char *))
{
	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)
	{
		str(dst, src);
		i++;
		chrono = clock() - start;
	}
	free(src);
	free(dst);
	return (i);
}

Other implementations

• MUSL libc strcmp
• GNU libc strcmp

Further Reading

• why is strcmp not SIMD optimized?: question by user1095108, October 2014