Первый элемент односвязного списка и последующий список обычно называют head и tail. Если вам по каким-то причинам потребовалось делить список на первый элемент, второй элемент и остаток, предлагаю второй элемент называть neck

В старых версиях раста для работы с коллизиями в хэшмапах использовалось линейная зондирование (???, 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 и полиморфной рекурсии — это означает, что итоговый результат не переносим в лоб на другие ЯП.