bird

(no subject)

Consider a binary search tree (AVL, red-black, whatever). The goal "find the least key strictly greater than the specified one" ("upper_bound" in C++ STL, higherEntry//higherKey in Java, etc.) can be implemented in manner (Java-like pseudocode):

current = root;
bestsofar = null;
while (current != null) {
  if (example_key < current.key) {
    bestsofar = current;
    current = current.left;
  } else {
    current = current.right;
  }
}
// return for KV extracting
return bestsofar;


This can be improved with optimizations (e.g. C5 adds special processing case without comparings if found exact match), but the main principle remains that we use single pass from the root to a leaf.

But Java TreeMap implementation uses strange variant (the same at least in versions 8...13):

    Entry<K,V> p = root;
    while (p != null) {
        int cmp = compare(key, p.key);
        if (cmp < 0) {
            if (p.left != null)
                p = p.left;
            else
                return p;
        } else {
            if (p.right != null) {
                p = p.right;
            } else {
                Entry<K,V> parent = p.parent;
                Entry<K,V> ch = p;
                while (parent != null && ch == parent.right) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        }
    }
    return null;


so, in some cases it backtracks using "parent" link to find the place it started passing only left-side links before final right-side dead end. (Really, all 4 key-based inexact searches utilizes this way, with minor differences and mirrored conditions.)

What case is being optimized with this approach?

This entry was originally posted at https://netch80.dreamwidth.org/49623.html. Please comment there using OpenID.
  • Current Mood
    amused amused
finch

(no subject)

Хочу странного.
Про виртуализацию в линии IBM S/370...zSeries говорят, что она имеет чрезвычайно мелкие накладные расходы и позволяет делать до 3-4 уровней вложенности без заметной просадки производительности.
Но не могу понять, как они этого достигают.
Документ "Principles of operation" свободно доступен, но именно эта тема превращается в "смотрю в книгу, вижу фигу" в завале подробностей глав типа "ASN translation".
Внятные описания стиля howto не гуглятся.
Или я не по тем словам ищу?

This entry was originally posted at https://netch80.dreamwidth.org/48481.html. Please comment there using OpenID.
finch

вести с грабельных полей: bison, flex

Раз в пятый, наверно, пытаюсь сделать что-то лёгкое пробное на bison+flex и обламываюсь на чудовищно путаной и неудобной реализации. Прямой рукописный парсер оказалось сделать легче.
Вот сейчас что-то такое написал, что flex сгенерировал файл со строками:

#line 346 "lexer.h"
#undef yyIN_HEADER
#endif /* yyHEADER_H */
UFFER_STATE yy_scan_buffer (char *base,yy_size_t size ,yyscan_t yyscanner );
YY_BUFFER_STATE yy_scan_string (yyconst char *yy_str ,yyscan_t yyscanner );
YY_BUFFER_STATE yy_scan_bytes (yyconst char *bytes,yy_size_t len ,yyscan_t yyscanner );


Кто такой UFFER_STATE и на ком он стоял?

(UPDATE: это получилось, если задать %option header-file, но не задать %option outfile. Но нигде не описано, что нельзя задавать только первый из них!)

bison не может в h-файле описать yylval. byacc не может описать в h-файле ничего, кроме кодов лексем - остальное, мол, описывайте сами.

Обоим bison и flex нельзя задать включаемые в этот h-файл строки, отчего, в частности, YYSTYPE или контекстный параметр парсеру надо или описывать одинаково в нескольких местах, или передавать void* и конвертить его в каждом месте использования. Причём они сами не включают нужное в выходные *.h, отчего их надо подключать только со своими источниками определений.

В доке flex сказано "читаем из yyin типа FILE*, вариантов нет", но чуть позже оказывается, что можно переопределить YY_INPUT. Извините, это была секция не туториала-букваря. Спасибо, что в нормальных stdio есть funopen() и fopencookie(), но кто кроме дедов об этом помнит?

Дефолтов для yywrap, yyerror не предлагается, хотя можно было уже давно придумать несколько типичных вариантов.

Bison с pure scanner передаёт параметр-куку всем функциям, кроме yylex(), которому она нужна больше остальных.

За один вечер можно наматериться на неделю.

UPD: победил. Но количество хаков, потребовавшихся, чтобы обойти недоработки и свернуть их с жесточайшего legacy, не радует.

This entry was originally posted at https://netch80.dreamwidth.org/47561.html. Please comment there using OpenID.
finch

дыбро

Немного IT-дыбра.

Обновил и подлатал представления о теме синтаксического анализа и вокруг. Общий вывод - всё достаточно грустно, разрыв теории с практикой достиг состояния "не сходятся, и всем пофиг". Все более-менее сложные реальные проекты творят нисходящий закат солнца вручную (Clang, Go...) или делают хитрые подпорки под относительно стандартные средства (как bison в GCC, но со специфичными C/C++ хаками, когда лексер смотрит в таблицы идентификаторов). Особенно "порадовало" Most vexing parse - после такого однозначно понятно, почему Go, Rust, Swift (и наверняка ещё много кто) взяли паскалевский порядок слов в определениях. (Напоминает конкуренцию SVO/SOV/etc. в живых языках и её последствия в виде позиции определяющего слова.) Или аналог для C# - когда парсинг конструкции вида f(G<1,2>(7)) зависит от достаточно "левых" признаков вроде следующих скобок.
При этом много голосов за "нематематичные" подходы вроде PEG (для которого фиг определишь в общем случае, написал конфликтную грамматику или нет - приоритеты и контекстные ограничения гарантируют разбор стандартных случаев, а там хоть трава не расти).

Обнаружил, что, несмотря на достаточно большой опыт в C/C++, не вляпывался до сих пор в самые мрачные варианты undefined behavior и его последствий, типа такого. И при этом никто не учит, что "here may be dragons" (целыми стадами) - например, Шилдт («C++ базовый курс») вообще ни слова, Страуструп - одно упоминание вскользь на 1000 страницах; в вузах тоже про это ни слова (по тому, как учили дочку); словно завеса умолчания, после которой вдруг встречаешься с последствиями, когда приступаешь к реальной работе. Как-то всё это странно. (Ещё ссылок, кому надо: 1, 2.)
Радует, что при всём при этом уже есть средства (как UB sanitizers) детекта заметного количества таких ситуаций (так что плотность их влияния на некорректность выходного результата становится ниже плотности влияния испорченной памяти).

Перевёл домашний настольник с FreeBSD на Linux. Причина - при переходе на 11ю фрю начало саморесетиться в произвольные моменты, но при реальной загрузке (два браузера) не жило больше 10 минут. На форуме не помогли, были только смутные обвинения видео в Haswell процессоре. Но умудрялось падать даже в Virtualbox, то есть видео ни при чём. Времени и настроения разбираться не было, так что привет, Kubuntu (такая же, как на работе и на лаптопе). Linux по крайней мере там работает :) но обидно. У фряхи было таки много мелких, но приятных удобств.

Осознал, что после превращения linkedin в обыкновенную соцсеть с лайками - присутствие на нём означает не только цель куда-то перейти, но и просто почитать что-то от коллег :) Для поддержки этой ситуации - начал закидывать такие же заметки на linkedin (на английском). Ну, начал - громко сказано :) но парочка есть ;)

This entry was originally posted at https://netch80.dreamwidth.org/47296.html. Please comment there using OpenID.
bird

Боевой сдвоенный походный оксиморон, 1 экз.

Некая спека говорит о типах данных

String: Alpha-numeric free format strings, can include any character or punctuation except the delimiter. All char fields are case sensitive (i.e. morstatt ≠ Morstatt).

Так всё-таки alpha-numeric или оно can include punctuation? Или вообще except the delimiter?

This entry was originally posted at http://netch80.dreamwidth.org/46964.html. Please comment there using OpenID.
  • Current Mood
    фигея
bird

О разуме компиляторов

Исходник:

bool FixMessage::isResendable() const
{
    unsigned type = getType();
    return type != FIX_MT_LOGON && type != FIX_MT_HEARTBEAT &&
           type != FIX_MT_TEST_REQUEST && type != FIX_MT_RESEND_REQUEST &&
           type != FIX_MT_SEQ_RESET && type != FIX_MT_LOGOUT;
}


Выхлоп gcc:

0000000000438570 <_ZNK10FixMessage12isResendableEv>:
  438570:       8b 4f 0c                mov    0xc(%rdi),%ecx
  438573:       b8 01 00 00 00          mov    $0x1,%eax
  438578:       83 e9 30                sub    $0x30,%ecx
  43857b:       83 f9 11                cmp    $0x11,%ecx
  43857e:       77 12                   ja     438592 <_ZNK10FixMessage12isResendableEv+0x22>
  438580:       b8 37 00 02 00          mov    $0x20037,%eax
  438585:       48 d3 e8                shr    %cl,%rax
  438588:       83 e0 01                and    $0x1,%eax
  43858b:       48 83 f0 01             xor    $0x1,%rax
  43858f:       83 e0 01                and    $0x1,%eax
  438592:       f3 c3                   repz retq


Кто-то догадался, что сократить проверку диапазона близких значений вычитанием базы - отлично.
Беззнаковое сравнение результата вычитания - очень остроумно.
xor с rax, когда достаточно с eax - чего пытаются добиться?
Финальный and с константой - разве из предыдущих команд не ясно, что там останется один бит?

Считаем контрольную сумму:

unsigned checksum(const char *m_begin, const char *m_before_csum)
{
    unsigned csum = 0;
    for (const char *p = m_begin; p != m_before_csum; ++p) {
        csum += *p;
    }
    csum &= 0xff;
    return csum;
}


Генерируем с векторизацией. Не буду приводить всю сумасшедшую простыню, только основной цикл:

        pxor    %xmm0, %xmm0
        addq    %rdi, %r9
        xorl    %edi, %edi
        pxor    %xmm6, %xmm6
        pxor    %xmm4, %xmm4
.L9:
        movdqa  (%r9), %xmm3
        movdqa  %xmm6, %xmm1
        movdqa  %xmm4, %xmm5
        addq    $1, %rdi
        pcmpgtb %xmm3, %xmm1
        movdqa  %xmm3, %xmm2
        addq    $16, %r9
        cmpq    %rdi, %rdx
        punpcklbw       %xmm1, %xmm2
        punpckhbw       %xmm1, %xmm3
        pcmpgtw %xmm2, %xmm5
        movdqa  %xmm2, %xmm1
        punpckhwd       %xmm5, %xmm2
        punpcklwd       %xmm5, %xmm1
        movdqa  %xmm4, %xmm5
        pcmpgtw %xmm3, %xmm5
        paddd   %xmm1, %xmm0
        paddd   %xmm2, %xmm0
        movdqa  %xmm3, %xmm2
        punpcklwd       %xmm5, %xmm2
        paddd   %xmm2, %xmm0
        movdqa  %xmm0, %xmm1
        movdqa  %xmm3, %xmm0
        punpckhwd       %xmm5, %xmm0
        paddd   %xmm1, %xmm0
        ja      .L9


Кто может объяснить, чем нуль в xmm4 принципиально отличается от нуля в xmm6, и почему их нельзя было объединить?

В пропущенной части: до начальной границы 16 байт - короткий простой цикл по байту, но после последней такой границы - цикл развёрнут в 15 отдельных групп со сравнением в каждой на достижение конца входного массива.

Замена char на unsigned char убирает только сравнения (pcmpgt*). Два разных нуля остаются.

За окном шёл снег и два нулевых регистра.

This entry was originally posted at http://netch80.dreamwidth.org/46641.html. Please comment there using OpenID.