На самом деле нет

== Rust должен умереть, МГУ сделал замеры
https://habr.com/ru/post/598219/

Весь смысл статьи не в том, что Раст можно опустить на уровень ассемблера, а в том что он остается по прежнему высокоуровневым языком, средства которого активно используют там, где раньше доминировал Си. Даже без стандартной библиотеки у Раста остаётся система типов, которая позволяет минимизировать количество ошибок, возникающих из-за человеческого фактора. И это одна из главных причин, по которой Раст хотят включить в ядро Линукса.

когданибудь подарю себе такое. 1000$ за движок. но блин. это просто нереально интересно

== Building a V8 Engine Model Kit - Full Metal Car Engine Model Kit
https://youtu.be/J03KnMP99sE

Узнаем расстояние между городами

Геодезическое расстояние – это длина кратчайшего пути между двумя точками на любой поверхности Земли. В следующем примере мы покажем, как пользователь может вычислить геодезическое расстояние на основе данных широты и долготы.

В нашем примере мы узнаем, ято расстояние между городами Нью-Йорк и Техас 2507 километров.

Узнаем в какой части света находится страна

countryinfo - модуль Python для возврата данных о странах, информации ISO и штатах/провинциях внутри них.

Установка пакета - pip install countryinfo.

Документацию пакета можно найти здесь.

В равной ли степени горутины делят между собой процессорное время?

Ответ
Существует 2 типа многозадачности:

кооперативная - передачей управления процессы занимаются самостоятельно;

вытесняющая многозадачность - планировщик дает отработать процессам равное время, после чего перещелкивает контекст.

С версии Go 1.14 планировщик с кооперативного стал асинхронно вытесняющим. Сделано это было по причине долго отрабатывающих горутин, надолго занимающих процессорное время и не дающих доступа до него другим горутинам. Теперь когда горутина отрабатывает больше 10 м/с Go будет пытаться переключить контекст для выполнения следующей горутины. Казалось бы вот он ответ. Но не все так просто... Части кооперативного поведения до сих пор присутствуют, к примеру перед вытеснением горутины необходимо выполнить проверку куска кода на атомарность, с точки зрения garbage collector. Операция вытеснения может настичь горутину в любом месте, в зависимости от состояния данных, сборщик мусора может отработать совсем не так как ожидалось. Так как Go живой язык, в который постоянно вносятся изменения, реализация и тонкости в разных версиях могут отличаться. Настоятельно советую обновлять свои знания по этой теме по мере релизов Go.

@golang_interview

#rust

Поддержку Rust в ядре Linux вмержил Линус 🎉

#prog #rust #article

How (and why) nextest uses tokio, part 1

Или хороший пример того, как async может пригодиться в программе, которая вообще никак не связана с общением по сети.

Петров и тут поспел. шикарный доклад

== Кругом враги. Как параноику планировать свою работу / Григорий Петров (Moscow Python)
https://youtu.be/SQ4NAOU5Jso

== забудь слово Ошибка
https://youtu.be/5iygkx-XfrY

Mypy 0.981 Released

из всего списка мне зашло
import TypedDict from typing
и
интерфейс из протокола
остальное просто улучшения

== Updates about mypy, an optional static type checker for Python
https://mypy-lang.blogspot.com/2022/09/mypy-0981-released.html

весь список:
- Support for Python 3.6 and 2 Dropped
- Generate Error on Unbound TypeVar Return Type
- Methods with Empty Bodies in Protocols Are Abstract
- Implicit Optional Types Will Be Disabled by Default
- Experimental Support for General Recursive Types
- Generic NamedTuples and TypedDicts
- Better Support for Callable Attributes

== вполне. советую
https://youtu.be/gOB3hpAVIIQ

- Транзакция, транзакционная база данных
- Расшифровка ACID
- Atomicity (атомарность)
- Consistency (консистентность)
- Isolation (изоляция)
- Read committed
- Snapshot isolation (repeatable read)
- Демонстрация отличий read committed и repeatable read на примере MySQL
- MVCC
- Проблема lost update
- Durability

Так как я уже не могу закончить этот пост неделю, напишу, что есть. Главное -- писать, остальное не так важно.

Что такое хорошая хеш-функция?

Этот вопрос на первый взгляд всегда кажется более научным, чем практическим. Да, в теории есть какие-то критерии. Даже пытались выстроить 5 уровней хэш-функции. Что взломать сложно или какие-то c-way-collisions найти очень быстро нельзя.

Криптографические хэши очень давно устоялись в индустрии и если перформанс для вас не так важен, SHA-3 и вперед.

В науке практически ничего невозможно доказать про хэш-функции кроме universal hashing, поэтому индустрия здесь надеется на смысл, чтобы хоть как-то предсказать хэши было сложно в случае хэш-таблиц.

И я тут даже не хочу говорить о каких-то хэшах типа MurMur, Farmhash, Cityhash, Wyhash, и тд. Если вам интересно, можете посмотреть их сравнение на smhasher: этот репозиторий кстати очень недооценён, сравнивать хэш-функции на коллизии, случайность стоит, а вот мало кто такой неблагодарной работой занимается.

Вопрос, который я решал последние пару месяцев и о котором я всё не мог написать, а как находить хэш-функции с хорошим распределением и ещё желательно, чтобы они были быстрыми?

Мир как-то слишком мало ответов знает на этот вопрос. Можно даже проще сформулировать: даны не более 16 байт (hi, lo) и длина, какое минимальное количество инструкций надо, чтобы получить хороший хэш?

Так как много вычислений хэшей происходит именно на всяких числах, маленьких строках, много циклов проводится в хэш таблицах, доминирующие элементы маленькие.

А что важно хэштаблице? Коллизии, потом скорее усложнение их поиска и чтобы "на проде" работало нормально. Коллизии чаще встречаются на размерах степеней двойки, как делают, скажем flat_hash_* в Abseil и Folly. Поэтому важно, чтобы нижние биты не сильно совпадали даже если нет коллизий :)

Итак, у нас есть хэш таблицы, у них не очень большие ключи и просто туча применений.

Попытка 1: crc

Инструкции CRC32 впаяны прям в процессоры x86 и Arm. Хоть это вычисление достаточно быстрое, CRC32C никогда не был сделан для хэш-таблиц, падает статистические тесты. Достаточно много коллизий, когда данные не слишком отличаются, это фактически означает, что если вы будете добавлять какие-нибудь указатели или числа/строки с одинаковым суффиксом, то коллизий будет достаточно много.

Этот факт я не особо знал. а вот ClickHouse повсеместно использует crc для хешей, можно идти ломать их join или что-нибудь ещё 😊 (не проверял, terms and conditions apply).

Ещё один страшный факт, что даже 64 битные crc32 инструкции возвращают 32 бита, если ваша хэштаблица приближается к 2^26 элементов, коллизий будет уже очень много.

Попытка 2: 128 битное умножение

Мы в abseil выбрали approach слегка другой, а название ему 128 битное умножение

(seed + number) * prime_number

Далее это число 128 битное, сделаем xor верхней и нижней части, это будет хэш для 8 байт. Для 16 повторить ещё раз c верхней частью и seed как результат нижней части.

На удивление это имеет достаточно хорошее распределение.

Зачем делать xor? Потому что если seed+number чётное, то умножение будет очень предсказуемым и нижние биты предсказуемы чаще. Считается, что при умножении средние и верхние биты числа не очень предсказуемы. Это хорошо на практике показано у PCG-random. Поэтому разбавить нижние биты всегда нужно чем-то.

Похожую идею можно увидеть даже у MurMur:

uint64_t fmix64 ( uint64_t k )
{
k ^= k >> 33;
k *= BIG_CONSTANT(0xff51afd7ed558ccd);
k ^= k >> 33;
k *= BIG_CONSTANT(0xc4ceb9fe1a85ec53);
k ^= k >> 33;
return k;
}

Попытка 3: перебор

Для 16 байт мы знаем, что есть хэш функция с хорошим распределением в 6 инструкций. Вопрос, а какое минимальное? Можно взять какой-нибудь set и перебрать. Вопрос в том, какие данные брать: я решил брать около 1000 входов, где есть случайные числа и все их соседи, где отличаются на 2 бита.

3 инструкции не работают совсем, лучшая 4 инстручная последовательность

r0 = hi - seed;
r1 = lo + 0x71b1a19b907d6e33;
r2 = r0 * r1;
r3 = r2 ^ r2_hi;
return r3;

Ломается на распределениях побольше. Всего перебор дал где-то 40 вариантов, все сломались на бОльших распределениях.

Можно перебирать 5 инструкций, но количество операций уже растёт слишком экспоненциально. На каждом шаге выбор где-то из 100 вариантов (все пары переменных * операции (+-^*,shift,rotate,crc,&,|)), в итоге даже если не разрешать все сдвиги или rotate, получается много. 115^n примерно, где n количество инструкций, на каждую итерацию надо проверить около 1000 входов на коллизии, что достаточно затратно. В итоге для n = 5, 10^15-10^16 итераций, ну можно запустить map reduce pipeline на часы. Ура, нашли 25k вариантов.

Дальше я пока сдался, потому что ощущение, что я схожу с ума. Чтобы отсеивать дальше, надо уметь больше распределений или запускать прям smhasher на все найденные.

Ну либо пойти к DeepMind, пусть их RL штуки находят хэш функции, наверное, можно поумнее.

Но мне кажется я вот вот либо докажу, что не существует хорошей 5 инстручной хеш функции для 16 байт, либо найду её наконец-то. Даже если все найденные свалятся, то никто не знает, может, я просто не добавил нужную инструкцию в перебор.

Мораль: перебирать ассемблер адски тяжело. Отсеивать плохие хэш-функции быстро адски тяжело. Ускорения в оба направления могут помочь нам дать лучшие хэш-функции. Пока вопрос открыт. Продолжаю рисёрч.

Сходство строк в Python

Метод ratio() возвращает меру подобия/схожести последовательностей в виде числа с плавающей точкой в диапазоне [0, 1].

Почему такой штуки у меня не было когда работал в КонструкторскомБюро ? Потому что бомж
https://youtu.be/u_Z3c9DXY4A

​Чего его не любить? Хороший язык программирования...

#кек #twitter

Повторение мать...
https://youtu.be/qb6l4B57Qmw