apolukhin
commented
3 years ago yndx-antoshkka, 11 марта 2019, 16:15
+1. Стоит большую часть
Nate Reinar Windwood, 16 марта 2019, 2:29 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);
}
}Думаю, и с остальной частью
yndx-antoshkka, 18 марта 2019, 11:41 Nate Reinar Windwood, возьмитесь пожайлуйста, буду благодарен!
Самой простой имплементации без рекурсий будет достаточно. Особый смак - если имплементация будет использовать builtin_ на платформах, которые умеют constexpr _builtin (например GCC умеет constepxr builtins_strlen)
Виктор Губин, 18 марта 2019, 16:34 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, 18 марта 2019, 17:10 Виктор Губин, достаточно чтобы работало на одном компиляторе (GCC умеет лучше других constexpr)
Виктор Губин, 18 марта 2019, 18:05 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-ре компилятора откажутся компилировать.
- Тривиальный байт-луп, типа strlen(str+1, tail +1) работает за O(N). Миниум, нужно как-то так. Но reintrepret_cast<const std::size_t*>(str) как и ассемблерные вставки и constrxpr не дружат по известным причинам.
Nate Reinar Windwood, 20 марта 2019, 1:28 yndx-antoshkka, ок, на выходных тогда. Для начала без билтинов напишу, а там посмотрим. Я в компиляторах не то чтобы разбираюсь, а у вас тут консенсуса пока, вроде, нету)
Виктор Губин, 22 марта 2019, 22:29 Nate Reinar Windwood, Можно и с интрисиками без особых проблем. Правда contexpr только наивные алгоритмы толком можно реализовать, что пагубно скажется на скорости компиляции, особенно всякого рода генераторов паресеров или компайл тайм регекспов наподобие sprit или expressive. Впрочем они и без того комплируются дико долго.
Nate Reinar Windwood, 24 марта 2019, 19:57 yndx-antoshkka, в общем, я создал: https://github.com/natewind/cstring-constexpr
Надеюсь, на буднях буду успевать понемногу доделывать.
Nate Reinar Windwood, 24 марта 2019, 20:07 Виктор Губин, это выглядит страшно >_<
Пожалуй, я пока не готов разбираться в интринсиках.
languagelawyer, 11 марта 2019, 19:08
Допустимо, что std::X и ::X для X из библиотеки C будут вести себя по-разному?
yndx-antoshkka, 11 марта 2019, 19:39 Да, это ОК
Konstantin Lazukin, 12 марта 2019, 12:29 Для этих целей можно воспользоваться 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);Виктор Губин, 18 марта 2019, 15:02 На самом деле компиляторы давно уже оптимизируют все так как нужно. 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, 18 марта 2019, 19:09 Виктор Губин, вы усложняете: static_assert от параметра функции и не должен работать; MSVC не умеет constexpr builtin (как и многих других вещей).
Всё что нужно для proposal, это показать что предожение на constexpr в принципе реализуемо с текущим развитием компиляторов. Тоесть нужна подобная имплементация и тесты. А после принятия предложения - уже дело разработчиков компиляторов сделать эффективно (добавить constexpr интринсики).
Виктор Губин, 20 марта 2019, 18:44 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
{}Daniil Goncharov, 24 октября 2019, 19:42 Proof of concept реализация доступна здесь: https://github.com/Neargye/cstring-constexpr-proposal Текст прополза можно посмотреть здесь: https://github.com/Neargye/cstring-constexpr-proposal/blob/master/papers/proposal.md Версия в pdf: https://github.com/Neargye/cstring-constexpr-proposal/blob/master/papers/P1944R0.pdf
Найденные ошибки и улучшения можно отсылать в issues или pr.
Roman-Koshelev
Перенос предложения: голоса +16, -0 Автор идеи: Yuriy Chernyshov
По факту многие современные компиляторы имеют функцию __builtin_strlen, которая является constexpr. Нужно только закрепить эту возможность в стандарте.
На ::strlen такие требования наложить, понятно, не получится.