strlen

Introduction

From The Open Group Base Specifications issue 7, 2018:

#include <string.h>

size_t strlen(const char *s);

• The strlen() function shall compute the number of bytes in the string to which s points, not including the terminating NUL character.
• The strlen() function shall return the length of s; no return value shall be reseved to indicate an error.
• No errors are defined.

Implementation

Relevant concepts: Operator precedence, const keyword

Basic implementation

#include <string.h>

size_t	ft_strlen(const char *s)
{
	size_t	i;

	i = 0;
	while (*(s++))
		i++;
	return (i);
}

Improved implementation

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

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

size_t	*ft_strlen(const char *s)
{
	const uint64_t	*pll;
	uint64_t	one_each_byte;
	size_t		n;

	n = 0;
	while ((uintptr_t)s & 0x7)
	{
		if (!*s++)
			return (n);
		++n;
	}
	pll = (const uint64_t *)s;
	one_each_byte = 0x0101010101010101L;
	while (!(((*pll - one_each_byte) & ~*pll) & (one_each_byte << 7)))
	{
		++pll;
		n += 8;
	}
	s = (const char *)pll;
	while (*s++)
		++n;
	return (n);
}

Speed tests

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

Basic implementation

Size\flag	-O3 -fno-builtin	-O2	-Os	(none)
1	102%	103%	99%	99%
10	101%	99%	100%	96%
100	91%	93%	90%	72%
1K	61%	61%	60%	23%
10K	18%	19%	18%	4%
100K	11%	11%	11%	2%
1M	12%	12%	12%	2%

Improved implementation

Size\flag	-O3 -fno-builtin	-O2	-Os	(none)
1	101%	101%	102%	95%
10	97%	100%	100%	97%
100	98%	98%	98%	93%
1K	90%	88%	90%	68%
10K	57%	57%	57%	24%
100K	45%	44%	45%	15%
1M	52%	50%	50%	16%

Test function

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

size_t	strlen_speed_test(int len, int second, size_t (str)(const char *))
{
	clock_t			chrono = 0;
	clock_t			start = 0;
	size_t			i = 0;
	void			*buff;

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

Other implementations

• MUSL libc strlen
• GNU libc strlen