constexpr std::strlen(const char*)

Yuriy Chernyshov
Yuriy Chernyshov

По факту многие современные компиляторы имеют функцию __builtin_strlen, которая является constexpr.
Нужно только закрепить эту возможность в стандарте.

На ::strlen такие требования наложить, понятно, не получится.

12
рейтинг
simple & useful
16 комментариев
yndx-antoshkka

+1. Стоит большую часть <cstring> сделать constexpr. Нужны добровольцы для написания прототипа.

yndx-antoshkka
Nate Reinar Windwood

yndx-antoshkka, ну прототип strlen пишется на коленке:

namespace std
{
	constexpr size_t strlen(const char *str)
	{
		auto result = size_t(0);
		while (*(str++) != '\0')
			++result;
		return result;
	}
}

Или вот еще версия поизящнее, но она полагается на TCO:

namespace std
{
	constexpr size_t strlen(const char *str, const size_t tail = 0)
	{
		return (*str == '\0') ? tail : strlen(str + 1, tail + 1);
	}
}

Думаю, и с остальной частью <cstring> проблем не должно быть. Могу взяться, если надо.

Nate Reinar Windwood
yndx-antoshkka

Nate Reinar Windwood, возьмитесь пожайлуйста, буду благодарен!

Самой простой имплементации без рекурсий будет достаточно. Особый смак - если имплементация будет использовать __builtin_* на платформах, которые умеют constexpr __builtin_* (например GCC умеет constepxr __builtins_strlen)

yndx-antoshkka
Виктор Губин

yndx-antoshkka, к сожалению не всегда работает, хоть и очень заманчиво

#include <cstdint>

#ifdef __GNUG__
#	define __strlen(__x) __builtin_strlen((__x))
#elif defined(_MSC_VER)
#   include <intrin.h>
#   include <string.h>
#   pragma intrinsic(strlen)
#   define __strlen(__x) strlen( (__x) )
#endif // compiler specific

#include <iostream>

static constexpr std::size_t strlen_impl(const char* s, std::size_t ret) noexcept {
    return '\0' == *s ? ret : strlen_impl(s+1,ret+1);
}

constexpr std::size_t ct_strlen(const char* s) noexcept {
    return nullptr == s ? 0 : strlen_impl(s,0); 
} 

static constexpr uint8_t atob_imp(const char* a,uint8_t ret) noexcept {
    return '\0' == *a ? ret : atob_imp(a+1, (ret * 10) + ( *a - '0') );
}

constexpr uint8_t atob(const char* a) noexcept {
//   static_assert(__strlen(a) <= 3, "3 is max" );
    return atob_imp(a, static_cast<unsigned int>(0) );
}

int main(int argc, const char** argv)
{
    constexpr const char* str  = "123";
 //   static_assert( 3U == __strlen(str), "123 expected");
    static_assert( ct_strlen(str) <= 3, "3 is max" );
	static_assert( 123U == atob(str), "123 expected");
	unsigned int ret =  atob(str);
    std::cout << ret << std::endl;
	return 0;
}

 

Виктор Губин
yndx-antoshkka

Виктор Губин, достаточно чтобы работало на одном компиляторе (GCC умеет лучше других constexpr)

yndx-antoshkka
Виктор Губин

yndx-antoshkka, в том-то и дело что __builtin_ как и pragma intinsic это рекомендация компилятору к оптимизации, а не constxepr. Компилятор - смотрит на это добро, и сам решает что с этим делать, вычислить на compile time, вставить ассемблерный блок наподобие

size_t strlen(const char *s)
{
	int d0;
	size_t res;
	asm volatile("repne\n\t"
		"scasb"
		: "=c" (res), "=&D" (d0)
		: "1" (s), "a" (0), "0" (0xffffffffu)
		: "memory");
	return ~res - 1;
}

или вызвать библиотечную функцию (call strlen)

Если в примере вернуть static_assert-ты, то все 4-ре компилятора откажутся компилировать. 

2. Тривиальный байт-луп, типа strlen(str+1, tail +1) работает за O(N). Миниум, нужно как-то так. Но reintrepret_cast<const std::size_t*>(str) как и ассемблерные вставки и constrxpr не дружат по известным причинам.

Виктор Губин
Nate Reinar Windwood

yndx-antoshkka, ок, на выходных тогда. Для начала без билтинов напишу, а там посмотрим. Я в компиляторах не то чтобы разбираюсь, а у вас тут консенсуса пока, вроде, нету)

Nate Reinar Windwood
Виктор Губин

Nate Reinar Windwood, Можно и с интрисиками без особых проблем. Правда contexpr только наивные алгоритмы толком можно реализовать, что пагубно скажется на скорости компиляции, особенно всякого рода генераторов паресеров или компайл тайм регекспов наподобие sprit или expressive. Впрочем они и без того комплируются дико долго.

Виктор Губин
Nate Reinar Windwood

yndx-antoshkka, в общем, я создал: https://github.com/natewind/cstring-constexpr

Надеюсь, на буднях буду успевать понемногу доделывать.

Nate Reinar Windwood
Nate Reinar Windwood

Виктор Губин, это выглядит страшно >_<

Пожалуй, я пока не готов разбираться в интринсиках.

Nate Reinar Windwood
languagelawyer

Допустимо, что `std::X` и `::X` для `X` из библиотеки C будут вести себя по-разному?

languagelawyer
yndx-antoshkka

Да, это ОК

yndx-antoshkka
Konstantin Lazukin

Для этих целей можно воспользоваться std::string_view, у которого есть constexpr конструктор и метод length.

#include <string_view>

constexpr std::size_t mystrlen(std::string_view sv)
{
    return sv.size();
}

static_assert(mystrlen("123")==3);
Konstantin Lazukin
Виктор Губин

На самом деле компиляторы давно уже оптимизируют все так как нужно. Cмотрим ассемблерный вывод

Однако есть другой вопрос, strlen посчитывает кол-во байт в строке, однако кол-во символов в строке может быть меньше чем кол-во байт в ней нарпимер если в const char* мы храним UTF-8. 

Положим наша строка вылядит вот так:

const char* umessage = "Hello!Привет!Χαιρετίσματα!Helló!Hallå!你好!こんにちは!";

Ее длина в байтах имеем 81, однако в символах - 47. Этот не маловажный факт хотелось-бы знать во многих случаях. Реализовать функцию определения длины в символах  можно напимер вот так:

#include <cstring>

#ifdef __GNUG__
#	if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
#		define IS_LITTLE_ENDIAN 1
#	endif // __ORDER_LITTLE_ENDIAN__
#	define __clz(__x) __builtin_clz((__x))
#elif defined(_MSC_VER)
#	define IS_LITTLE_ENDIAN 1
#	ifdef __ICL
#		define __clz(__x) _lzcnt_u32((__x))
#	elif defined(_M_AMD64) || ( defined(_M_IX86_FP) && (_M_IX86_FP >= 2) )
#		pragma intrinsic(__lzcnt)
#		define __clz(__x) __lzcnt((__x))
#	else
		#pragma intrinsic(_BitScanReverse)
		__forceinline int __clz(unsigned long x)  noexcept {
			unsigned long ret = 0;
			_BitScanReverse(&ret, x);
			return  static_cast<int>(ret);
		}
#	endif
#endif // compiler specific

#include <iostream>

namespace utf8 {

/// Checks a byte is UTF-8 single byte character
inline constexpr bool isonebyte(const char c)
{
	return static_cast<uint8_t>(c) < uint8_t(0x80U);
}

/// Checks a byte is UTF-8 character tail byte
inline constexpr bool ismbtail(const char c) noexcept
{
	return 2 == ( uint8_t(c) >> 6);
}

/// Returns UTF-8 character size in bytes, based on first UTF-8 byte
inline constexpr unsigned int char_size(const char ch)
{
	return isonebyte(ch)
	? 1
	:
	// bit scan forward on inverted value gives number of leading multi-byte bits
#ifdef IS_LITTLE_ENDIAN
	static_cast<unsigned int>( __clz( ~( static_cast<unsigned int>(ch) << ((sizeof(unsigned int) << 3 ) - 8) ) ) );
#else
	static_cast<unsigned int>( __clz( ~ ( static_cast<unsigned int>(ch) ) ) );
#endif // IS_LITTLE_ENDIAN
}

inline std::size_t strlength(const char* u8str) noexcept {
	std::size_t ret = 0;
	for(const char *c = u8str; '\0' != *c; c += char_size(*c) )
		++ret;
	return ret;
}



} // namespace utf8

const char* umessage = "Hello!Привет!Χαιρετίσματα!Helló!Hallå!你好!こんにちは!";

int main(int argc, const char** argv)
{

	std::cout << std::strlen(umessage) << std::endl;
	std::cout << utf8::strlength(umessage) << std::endl;

	return 0;
}

Однако это "велосипед", хотелось-бы иметь поддержку со стороны стороны стандартной билиотеки.

 

Виктор Губин
yndx-antoshkka

Виктор Губин, вы усложняете: static_assert от параметра функции и не должен работать; MSVC не умеет constexpr builtin (как и многих других вещей).

Всё что нужно для proposal, это показать что предожение на constexpr в принципе реализуемо с текущим развитием компиляторов. Тоесть нужна подобная имплементация и тесты. А после принятия предложения - уже дело разработчиков компиляторов сделать эффективно (добавить constexpr интринсики).

yndx-antoshkka
Виктор Губин

yndx-antoshkka, почему-бы тогда не пойти еще дальше и прописать в стандатре С++XX что все функции стандартной библиотеки С из ctype, cstring, cmath, stdarg (+  что-то еще типа snprintf, sscanf ...) объявляются операторами языка.

Таковые доступны вообще без #include-ов или префиксов типа __builtin и их можно использовать в constrexpr выражениях и функциях если позволяет контекст. 

Возможно потребуется поддержка со стороны ABI,  как и в случае с: __cxa_guard_xxx, RTTI и exceptions. Т.е. подобное не сработает если нет ABI (в драйверах, ядрах ОС и т.п. ABI как и либс реализуют свой или подключают что-то готовое)

static foo _foo;

foo *f = dynamic_cast<foo*>(bar);

throw std::runtime_error();

class foo {
...
virtual ~foo() noexcept = 0;
...
};

foo::~foo() noexcept
{}

Виктор Губин
Обновлено 
Другие идеи
Группа создана, чтобы собирать предложения к стандарту C++, организовывать их внутренние обсуждения, помогать готовить их для отправки в комитет и защищать на общих собраниях в рабочей группе по С++ Международной организации по стандартизации (ISO).
Все предложения