В старых версиях раста для работы с коллизиями в хэшмапах использовалось линейная зондирование (???, linear probing), а сиды переиспользовались. ~5 лет назад было обнаружено что это приводит к (неожиданно) квадратичному поведению.

Вот отличный writeup на эту тему: Accidentally Quadratic: Rust hash iteration+reinsertion

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

Так-же hashbrown, библиотека которую использует std, после редизайна использует ~квадротичное зондирование, что тоже помогает с этим.

Если интересно как редезайнули hashbrown (SwissTable), то можно прочитать вот тут: https://gankra.github.io/blah/hashbrown-tldr/

Цитируя авторку статьи:
> it was such an improvement that it reduced compile times for basically every rust program by ~10% (rustc is just several HashMaps in a trenchcoat)

> The first erroneous computation example is CVE-2021-39137 which is an interesting go-ethereum bug identified by Guido Vranken. The bug caused a netsplit in the Ethereum network and essentially results from the ability to have a mutable and non-mutable slice referencing the same chunk of memory.

A deeper dive into CVE-2021-39137 – a Golang security bug that Rust would have prevented
https://research.nccgroup.com/2022/02/07/a-deeper-dive-into-cve-2021-39137-a-golang-security-bug-that-rust-would-have-prevented/

И что б два раза не вставать. Интересный пост

> On 2/2/2022, I reported a critical security issue to Optimism—an "L2 scaling solution" for Ethereum—that would allow an attacker to replicate money on any chain using their "OVM 2.0" fork of go-ethereum (which they call l2geth).

Attacking an Ethereum L2 with Unbridled Optimism
https://www.saurik.com/optimism.html

#prog #c #article

Статья о том, как правильно использовать этот ваш fork (спойлер: СЛОЖНО)

habr.com/ru/post/586604/

#music

Bytenommer — Fair and square

youtube.com/watch?v=CMLPy2NJwVc

В продолжение темы. И да, это решение одной из задач на Leetcode.

class Open {
private:
enum class Value {
Paren,
Bracket,
Brace
};
Value value;
Open(Value val): value(val) {}
public:
Open() = delete;

static std::optional<Open> from_char(char ch) {
switch (ch) {
case '(': return Open(Value::Paren);
case '[': return Open(Value::Bracket);
case '{': return Open(Value::Brace);
default: return std::nullopt;
}
}

bool complements(char ch) const & {
switch (ch) {
case ')': return value == Value::Paren;
case ']': return value == Value::Bracket;
case '}': return value == Value::Brace;
default: return false;
}
}
};

class Solution {
public:
bool isValid(string s) {
std::vector<Open> stack {};
for (auto ch : s) {
if (auto open = Open::from_char(ch); open.has_value()) {
stack.push_back(*open);
} else {
if (!stack.empty() && stack.back().complements(ch)) {
stack.pop_back();
} else {
return false;
}
}
}
return stack.empty();
}
};

В Meta (которая ex-Facebook) сделали интересную модельку: реконструкция 3D модели объекта под новым ракурсом в новом видео из увиденных видео с объектом в прошлом.

#prog #cpp #article

C++ Coroutines Do Not Spark Joy

#video и, наверное, #game?

https://fxtwitter.com/i/status/1467218987809267712

#programming
В топе бенчмарков веб-фреймворков оказался фреймворк на Js, Just-JS

https://just.billywhizz.io/blog/on-javascript-performance-01/

https://www.techempower.com/benchmarks/#section=data-r20&test=composite

Компьютер может просто работать и просто считать циферки, не его вина, что кто-то код писать не умеет

Я придерживаюсь презумпции няшности. Все — няшки, пока не доказано обратного.

То есть Вафель — няшка, Q. E. D.

Блять

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

#prog #regex #parsing #haskell

Fix-ing regular expressions

TL;DR: We add variables, let bindings, and explicit recursion via fixed points to classic regular expressions. It turns out that the resulting explicitly recursive, finitely described languages are well suited for analysis and introspection.

Если читали мои претензии к регулярным выражениям, то наверняка помните, что одной из моих претензий было отсутствие декомпозируемости. В статье это решается за счёт добавления явных переменных (точнее, привязок в форме let x = r in re). Также добавление явного fix расширяет возможности языка и даёт возможность использовать рекурсию. На практике это означает, что подобное решение в состоянии распарсить известный пример грамматики, являющейся контекстно-зависимой: aⁿbⁿ.

К сожалению, не обошлось без ложки дёгтя: даже с некоторыми оптимизациями производительность итогового решения оставляет желать лучшего — что, в принципе, вполне ожидаемо, учитывая, что распознавание использует подход regular expression derivatives, который при применении в лоб приводит к сильному распуханию промежуточных структур данных. А ещё лично меня несколько расстраивает использование в финальной версии fix и полиморфной рекурсии — это означает, что итоговый результат не переносим в лоб на другие ЯП.

#prog #rust #rustreleasenotes

Вышла версия Rust 1.59.0!

(Об известных событиях есть короткая ремарка в начале блогопоста, но, в отличие от заметок к релизу Rust 1.44.0, почти полностью убирать пост не стали. Впрочем, не исключено, что это лишь из-за того, что дата публикации поста совпала с этим днём)

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

▪️ВАЖНО: из-за багов инкрементальную компиляцию по умолчанию отключили. Её всё так же можно активировать самостоятельно, но в таком случае готовьтесь к ICE. Хорошие новости: баг вроде пофиксили, так что в следующем релизе включат обратно.

▪️В присваиваниях (а не только в декларациях) теперь можно использовать паттерны. Пример из блога достаточно красноречив:

let (a, b, c, d, e);

(a, b) = (1, 2);
[c, .., d, _] = [1, 2, 3, 4, 5];
Struct { e, .. } = Struct { e: 5, f: 3 };

assert_eq!([1, 2, 1, 4, 5], [a, b, c, d, e]);

И да, присваивания в духе (a, b) = (b, a) работают, причём с не-Copy типами. Rust стал ещё чуть больше похож на Python (предыдущей фичей была f-строки).

▪️Изменения в const generics: их теперь можно объявлять вперемешку с ти́повыми параметрами, а сами значения const generics на объявлениях типов теперь могут иметь значения по умолчанию. И если вы думаете, что это нишевая штука, то я могу совершенно точно сказать, что на предыдущей работе мне из-за отсутствия значения по умолчанию для const generics пришлось отказаться от одного кусочка API, которое я разрабатывал, и сделать его менее эргономичным.

▪️Совершенно внезапно стабилизировали ассемблерные вставки! Я удивлён, не думал, что они уже настолько готовы. С другой стороны, пока что они работают лишь для архитектур x86/x86-64, ARM, AArch64 и RISC-V.

▪️Линт private-in-public ослабили: теперь не является ошибкой иметь на impl-е трейта в where clause ограничение публичного типа приватным трейтом и ограничение приватного типа публичным трейтом (в PR, который вносит это изменение, рассказывается, почему это ок).

▪️С части методов Hash{Map, Set} сняли лишние ограничения на типы.

▪️ Ну и традиционно "о-боже-почему-они-стабилизировали-эту-простую-вещь-только-сейчас"-часть. Всё перечислять не буду, укажу только на std::thread::available_parallelism (кстати, в отличие от аналогичного API в стандартной библиотеке C++, эта функция возвращает io::Result<NonZeroUsize>, так что с нулём разбираться не придётся), Result::{cloned, copied}, ops::ControlFlow::{is_break, is_continue} и is_power_of_two на NonZeroX типах.

А ещё в этот раз в подробных заметках о релизе довольно объёмная секция о совместимости. Советую на всякий случай прочитать, но, если вы не делаете ничего странного, то вас наверняка ничего не затронет (кроме, разве что, того, что split_inclusive на пустых слайсах возвращает пустое значение — и то это приведение в соответствие с аналогичным методом у str).

Кстати, я тут понял, что посты с разбором нововведений сложно найти, так что сделал хештег rustreleasenotes и отредактировал все старые посты с ними, которые смог найти, чтобы они включали этот хештег