#dev #rust

Загадка, теперь уже точно.

fn test<T: ?Sized>() {
    dbg!(is_concrete_type!(i32));
    dbg!(is_concrete_type!(T));
}
fn main() {
    test::<i32>();
}

[src/main.rs:35:5] is_concrete_type!(i32) = true
[src/main.rs:36:5] is_concrete_type!(T) = false

Как? (Конкретные названия типов и T не хардкодятся)

(Очевидно, спойлеры) Реализация

#dev #rust

https://purplesyringa.moe/blog/the-rust-trademark-policy-is-still-harmful/

#dev

К слову о том, почему UB от strict aliasing — это все еще UB, а не "да ладно, нормально все будет": Clang компилирует классический Quake'овский код

float Q_rsqrt( float number )
{
  long i;
  float x2, y;
  const float threehalfs = 1.5F;

  x2 = number * 0.5F;
  y  = number;
  i  = * ( long * ) &y;            // evil floating point bit level hacking
  i  = 0x5f3759df - ( i >> 1 );               // what the fuck?
  y  = * ( float * ) &i;
  y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//  y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

  return y;
}

в

Q_rsqrt:
        ret

и имеет полное на это право
source: https://mastodon.social/@regehr/113471011505378920

#math

Задачка на вечер: n фиксированных чисел x1, ..., xn в полуинтервале [0; 1) хешируются в таблицу с закрытой адресацией размера m методом floor(x*m). Покажите, что независимо от n, xi, m, увеличение размера таблицы может ухудшить среднее время запроса только в константу раз.

Подсказка (чисто ради интуитиции, хотя, может быть, она доводится до решения): Представьте плотность такого распределения как δ(x1) + ... + δ(xn), где δ — дельта-функция Дирака. Тогда разные размеры таблицы соответствуют разным разбиениям отрезка [0; 1], которому соответствуют разные суммы Римана. Можно ли воспользоваться тем, что суммы Римана с уменьшением шага разбиения обычно сходятся, и поэтому вроде как остальные параметры разбиений тоже должны быть похожи?

#math

Запишу решение, чтобы не потерялось, и если кто-то не следит за комментами.

Посмотрим на то, какие бакеты были и какие стали:

было    /------------/------------/------------/------------/------------/
стало   /----/----/----/----/----/----/----/----/----/----/----/----/----/
элементы   *   *      *  **  *     * *  *        *           ** ***    *

Зафиксируем пока число элементов в каждом из изначальных бакетов и посмотрим, какое самое плохое число коллизий может получиться в новом случае.

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

Таким образом, в худшем варианте числа лежат только в новых бакетах, пересекающих границу старых (здесь * обозначает потенциальные позиции):

было    -----|------
стало     |-----|
элементы   *****

Для i-го такого нового бакета обозначим за ai количество чисел, лежащих в нем слева от старой границы, а за bi — справа. Тогда сумма квадратов размеров бакетов была C = sum (a[i+1] + bi)^2, а стала C' = sum (ai + bi)^2.

Тогда имеем:

C' = sum (ai + bi)^2

Перепишем сумму через среднее арифметическое:

C' = 4 * sum ((ai + bi) / 2)^2

Применим неравенство о среднем арифметическом и среднем квадратичном:

C' <= 4 * sum (sqrt((ai^2 + bi^2) / 2))^2

Раскроем скобки:

C' <= 2 * sum (ai^2 + bi^2)

Разделим сумму на две, а затем заменим индексы в одной из сумм и сложим обратно:

C' <= 2 * sum (a[i+1]^2 + bi^2) <= 2 * C

Таким образом, доказана нужная оценка с константой 2. Легко проверить, что она достигается.

Подъехал сильно более простой пруф:

Рассмотрим разделители между старыми бакетами. Проделаем теперь два шага, чтобы перейти к новому разделению:

- Добавим к ним разделители между новыми бакетами. От этого количество коллизий увеличиться не могло.

- Внутри новых бакетов уберем разделители между старыми бакетами. Таких разделителей максимум по одному на каждый новый бакет, т.е. было отдельно a и b точек, а стало a + b. Но (a + b)^2 <= 2 * (a^2 + b^2), поэтому количество коллизий могло увеличиться максимум вдвое.

#snippet

Эффективно применить константный permute (он же gather) к байту:

uint64_t precompute_mask(int indices[8]) {
  uint64_t mask = 0;
  for (int i = 0; i < 8; i++)
    if (indices[i] != -1)
      mask |= 1ULL << (i * 8 + indices[i]);
  return mask;
}

uint8_t permute(uint8_t byte, uint64_t mask) {
  return pext(byte * 0x0101010101010101ULL, mask);
}

https://purplesyringa.moe/blog/any-python-program-fits-in-30-characters/

#dev #python

Нашли способ уместиться в 24 символа и значительно уменьшить оверхед — обновила пост!

#dev #web

Небольшая заметка, чтобы разгрузить беклог.

Как засунуть в HTML бинарные данные и извлечь их в JSе? Казалось бы, ответ простой — применить base64 и декодировать в рантайме. А если хочется еще и файл сделать маленьким? Вот такой код загружает данные в переменную s:

<script>(async()=>s=(await (await fetch("#")).bytes()).slice(80))()</script><!--Binary data goes here...

Решение простое, и заметки б не было, если б я до этого не перепробовала несколько способов, потому что забыла про существование fetch.

Самый интересный из них — UTF-16. Дело в том, что случайные бинарные данные намного вероятнее являются валидным UTF-16, чем валидным UTF-8, т.е. можно эскейпить сильно меньше символов и хранить бинарные данные практически бесплатно.

Подход, соответственно, следующий. Интерпретируем данные, которые нужно закодировать, как последовательность 16-битных чисел. Кодпоинты, задающие безопасные UTF-16 символы, т.е. все кроме суррогатов и кавычек/бэкслешей, прям так и выдаем на выход. А чтобы закодировать опасное число c, прибавляем к нему 0x10000 и выдаем на выход такой кодпоинт, закодированный в UTF-16. Для декодирования просто нужно пройтись по кодпоинтам строки, сделать & 0xffff, и реинтерпретнуть получившийся массив 16-битных чисел как массив байт.

Теряем мы здесь по одному слову на каждое слово в промежутке [0xd800; 0xe000) и еще по мелочи от эскейпов, т.е. размер файла от такого кодирования увеличивается всего где-то на 3%.

Дальше встает загадка о том, что на дворе 2024 год, все используют UTF-8, и браузеры дефолтнутся на него. Но! Стандарт по какой-то причине говорит, что если HTML-файл начинается с BOM, то кодировку надо определять по нему. Даже если в Content-type указана иная. Так что таким трюком можно заставить использовать UTF-16 даже Github Pages.

Остался нюанс, что это форсит UTF-16 на весь HTML-файл, увеличивая размер всего кроме бинарных данных. Так что где-то тут еще может быть разумно засунуть HTML прямо в бинарные данные и подгружать его в рантайме JSом.

Загадка. Одна из этих строк не скомпилируется. Какая?

let a1: _ = [b"a", b"a" as &[u8]];
let b1: _ = [b"a" as &[u8], b"a"];

let a2: [_; 2] = [b"a", b"a" as &[u8]];
let b2: [_; 2] = [b"a" as &[u8], b"a"];

let a3: [&[u8]; 2] = [b"a", b"a" as &[u8]];
let b3: [&[u8]; 2] = [b"a" as &[u8], b"a"];

&[T; N] автоматически умеет приводиться к &[T], поэтому третий код, конечно, работает в обеих вариациях.

Остается вопрос, что происходит при выводе типов. На практике оказывается, что b2 работает, а a2 не работает, т.е. тип элемента массива "жадно" выводится исходя из первого элемента. a1 и b1 по какой-то причине при этом оба работают. Таким образом, правильный ответ — a2.

Зная, что загвоздка в выводе типов заключается в приравнии типов, умеющих друг к другу coerce'иться, не в том порядке, угадайте, какие строки из следующих приведут к ошибке:

fn unify<T>(_x: T, _y: T) {}
unify(b"a", b"a" as &[u8]); // 1
unify(b"a" as &[u8], b"a"); // 2

if true { b"a" } else { b"a" as &[u8] }; // 3
if true { b"a" as &[u8] } else { b"a" }; // 4

Подсказка: true в if не влияет на вывод типов, с тем же успехом там могло быть любое другое условие.

Правильный ответ: не скомпилируется строка 1. Все остальные соберутся.

Почему 1 не собирается, а 2 собирается — в целом логично: опять тип выводится исходя из первого встреченного аргумента. Тут ничего нового по сравнению с [_; 2].

Почему и 3, и 4 собираются мне, опять же, неизвестно. Здесь вывод типов устроен как-то иначе. С match, к слову, то же самое, т.е. от (не)ограниченности количества объединяемых типов результат не зависит.

Имеете доступ к структуре за иммутабельной ссылкой, но хотите мутировать ее поле? Отрицаете любые авторитеты и хотите назло маме отморозить уши? Вас спасет баг rustc, заставляющий его автодополнять unsafe перед фигурными скобками:

struct Struct {
    field: i32,
}

fn mutate_behind_immutable_reference(r: &Struct) {
    let r = &mut { r.field };
    *r = 123;
}

(https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=3c3540db0fdef1ddf6e818a33ebad231)

И никакой borrow checker вам больше не помеха!

fn conjure<T>() -> T { unimplemented!() }

(123,) as (u64,);
// error[E0605]: non-primitive cast: `(i32,)` as `(u64,)`

(conjure(),) as (u64,);
// no error

То есть если universal-тип primitive-cast'нуть к числу, то для него заинферрится числовой тип, а если число primitive-cast'нуть к числу, то не заинферрится, а случится default numeric fallback. Весело.

https://purplesyringa.moe/blog/thoughts-on-rust-hashing/

#dev #rust

https://purplesyringa.moe/blog/the-ram-myth/

#dev #rust #algorithms