http://supertech.csail.mit.edu/papers/FrigoLePr99.pdf вот статья, которая даёт необходимое теоретическое объяснение тому, что штрассена алгоритм cache-oblivious
Лучше просто бенчи. Я поверю в штрассена на размере 500 примерно, не раньше
Constantine
Andrei
А ты сам гуглил?
Andrei
Лучше просто бенчи. Я поверю в штрассена на размере 500 примерно, не раньше
Энивей, даже 500х500 матрицы — это маленькие.
Andrei
В физике гораздо больше.
Constantine
Энивей, даже 500х500 матрицы — это маленькие.
Ну я назвал прикидкой минимальную границу. С матрицами которые в оперативу не лезут отдельный разговор
Andrei
Ну я назвал прикидкой минимальную границу. С матрицами которые в оперативу не лезут отдельный разговор
Btw, если речь идёт о перемножении на gpu, то кеш тут вообще не играет роли. Или о перемножении на ПЛИСине.
Constantine
Btw, если речь идёт о перемножении на gpu, то кеш тут вообще не играет роли. Или о перемножении на ПЛИСине.
Я веду речь исключительно про алгоритмы цпу, да
Matway
Мда. Какова вероятность события, что я, размышляя о математической библиотеке вообще и реализации алгоритма Штрассена в частности, открою чат и увижу сиё в ту же секунду?
Berkus
Andrei
Мда. Какова вероятность события, что я, размышляя о математической библиотеке вообще и реализации алгоритма Штрассена в частности, открою чат и увижу сиё в ту же секунду?
Юнгианская синхрония коллективного бессознательного, всё как обычно.
Matway
Истина где-то между вашими ответами.
Nikita
cyberzx 🇷🇺
pro, есть небольшая задачка
допустим у нас есть некая хэш-мап, которая позволяет лукап делать не только по ключу, а так же по ключу + заранее посчитаный хэш. например eastl::hash_map
так же есть constexpr функция для расчёта хеша по строке - constexpr size_t hash_fnv1(const char* str);
ну и какой-нибудь класс с атрибутами и этой хеш-мапой с ключами-строками и геттером T getAttribute(const char* str);
Как сделать так, что бы вызывая getAttribute("some_key"), хэш гарантированно читался в compile-time?
cyberzx 🇷🇺
Если вызвать hash_fnv1("some_key"), то тут будет compile-time
а это параметр передаётся через функцию то есть
getAttribute(const char* str) { size_t h = hash_fnv1(str); }, то никак нельзя зафорсить compile-time, так как str уже не является constant value.
cyberzx 🇷🇺
И нет никакого способа указать, что str это constant value. Приходится делать макросы.
А так хочется решать подобные задачи чисто С++ кодом без тёмной макро магии
cyberzx 🇷🇺
На готболте набросаю, что бы сразу было видно где compile-time, а где run-time
cyberzx 🇷🇺
https://godbolt.org/g/LDnnfb
cyberzx 🇷🇺
Если вызвать str_hash_fnv1 напрямую со строковым литералом, то гарантированно значение будет известно во время компиляции.
а вот если вызывать из функции, которая принимает строковой литерал, то уже никаких гарантий нет. и нельзя использовать резльтутат str_hash_fnv1 как constexpr значение.
И я понимаю почему так. Функция get_some_value_by_hash должна быть обобщённой от параметра str, и для каждого его значения будет сгенерированно новое тело функции. Что вполне приемлимо с инлайном и оптимизацией.
Но как сделать эту обобщённую функцию от значения?
Шаблоны могут в качестве параметров иметь только целочисленные типы. Строка не может быть параметром шаблона.
Andrew
кажется есть идея
cyberzx 🇷🇺
У меня в примере они все constexpr
cyberzx 🇷🇺
Но когда ты вызываешь одну constexpr из другой с её параметром, компилятор результат вызова первой не считает constant value, даже если знает, что параметр константа
Aidar
И да const char это примитив если что
cyberzx 🇷🇺
И на что это влияет?
Aidar
const char*
Aidar
На то что оно может быть параметром щаблона
cyberzx 🇷🇺
А как передать этот параметр?
Такое вот не компилируется
#include <stddef.h>
#include <stdio.h>
template<const char* s>
void print()
{
printf(s);
}
int main()
{
print<"hello world">();
return 0;
}
cyberzx 🇷🇺
a.cpp: In function ‘int main()’:
a.cpp:12:24: error: no matching function for call to ‘print()’
print<"hello world">();
^
a.cpp:5:6: note: candidate: template<const char* s> void print()
void print()
^~~~~
a.cpp:5:6: note: template argument deduction/substitution failed:
a.cpp:12:24: error: ‘"hello world"’ is not a valid template argument for type ‘const char*’ because string literals can never be used in this context
print<"hello world">();
cyberzx 🇷🇺
Вообщем там всё сложно. Можно передать указатель на переменную с внешней линковкой. С литералами такое не прокатит
Aidar
смотри
Aidar
https://godbolt.org/g/WHJpza
Aidar
https://godbolt.org/g/8xCaMW
Aidar
кто объяснит?
Aidar
а какая насрать разница
cyberzx 🇷🇺
тут понятно. в первом случае ты форсишь выполнение b по constexpr пути, так как результат его присваиваешь в constexpr переменную.
во втором случае это не форсится и тут уже оптимизатор решает как и когда что считать
Aidar
https://godbolt.org/g/urVPZz
Aidar
еще
cyberzx 🇷🇺
У меня конечная задача, что бы можно было делать выборку из хэш мапы по строковому литералу и при этом хэш всегда считался только в compile-time
Но лукап это же не constexpr операция
cyberzx 🇷🇺
Надо понимать, что компилятор может считать constexpr функции в компайл-тайме или рантайме как захочет его левая нога, если мы не заставляем его делать
А заставить можно, например, так std::integral_constant<bbb(5)>::value
Andrew
ребяты, дело не в параметре
Andrew
смотрите, я сделал передачу параметра через шаблон
Andrew
struct string_holder //
{ // All of this can be heavily optimized by
static const char* asString() // the compiler. It is also easy to generate
{ // with a macro.
return "lorem ipsum"; //
} //
};
template<typename string_holder>
constexpr int str_hash_fnv1()
...
Aidar
template<const char* data> int hash(){
return 1;
}
static constexpr char asd[] = "asd";
int main(){
int hh = hash<asd>();
return hh;
}
Andrew
я думаю вся фигня из-за этого:
the full-expression of its initialization, including all implicit conversions, constructors calls, etc, must be a constant expression
Andrew
если в тело затолкать не вычисление хеша, а что-то проще — оно работает
Aidar
да
Aidar
нельзя частитчно сделать функцию constexpr
Aidar
только шаблон
Andrew
можно ещё посмотреть constexpr версию std::floor
Aidar
я уже бугуртил насчет этого
Aidar
короче текущий констекспр в си++ полный кал
cyberzx 🇷🇺
template<const char* data> int hash(){
return 1;
}
static constexpr char asd[] = "asd";
int main(){
int hh = hash<asd>();
return hh;
}
Да, так можно делать. Но это надо заводить переменные со значениями. Что делает API неудобным. А хочется строковые литералы
Aidar
он в 99% не применим ваще
Andrew
http://szelei.me/constexpr-murmurhash/
Andrew
https://github.com/sztomi/constexpr_murmurhash/blob/master/constexpr_murmur3.h
Andrew
вот у него там даже циклов нет
cyberzx 🇷🇺
в С++11 нельзя циклы в constexpr
Aidar
а еще си++11 уже дохрена лет
Aidar
<del>он устарел</del>
cyberzx 🇷🇺
да согласен
Aidar
но constexpr от этого лучше не стал
cyberzx 🇷🇺
вот у него там даже циклов нет
но там у него constexpr класс для строки. вот, кстати, интересное решение
Andrew
да, я так же делал, когда мучил твой пример
cyberzx 🇷🇺
ну всё равно, нельзя сделать такое API
`
Attribute Object::getAttribute(const char* key)
{
return amap.getByHash(str_hash(key), key));
}
cyberzx 🇷🇺
Было бы здорово иметь constexpr параметры
то есть
Attribute Object::getAttribute(constexpr const char* key);
и этот метод вызывался только в тех случаях, когда ключ известен во время компиляции
cyberzx 🇷🇺
И это фактически обобщённая функция. Но не шаблонная
Andrew
https://godbolt.org/g/CnwoJx
Andrew
короч вот
Andrew
можешь взять за шаблон, впихнуть свою хеш-функцию
Aidar
Нельзя
Aidar
А ещё такую строку нельзя в шаблон упихать
Aidar
Потому что литеральные типы там тоже не разрешены
Aidar
Это сейчас решается только передачей данных в самом типе
Andrew
всмюсле? ) задача была расчитать простой хеш во время компиляции
Andrew
как Кибер это будет юзать, только ему известено ))
cyberzx 🇷🇺
всмюсле? ) задача была расчитать простой хеш во время компиляции
Эта задача решена вполне успешно. Если взять твой пример, то мне нужно вот такое. (не компилируется)
constexpr void print(str_view s)
{
printer<mm3_x86_32(s, 0x9747b28c)> p;
}
Aidar