Хеш-таблица с транзакциями на Go

Привет, продолжим удивительное. Смех смехом, но на Go стали доступны:

1. Хеш-таблица с транзакциями.

2. Структуры данных второго порядка.

И в отличие от C++, они еще не создают проблемы для Garbage Collector. Вы угадайте почему, а я немного процитирую:

------------------8<------------------

Все выглядит примерно так:

func NewMemDb() MemDb { /* ... */ }

type MemDb interface {
    Close() error
    StartTrn() Transaction
}

type Transaction interface {
    Close() error

    Get(key Ptrsz) (Ptrsz, bool)
    All(getKeys bool, getVals bool) (keys []Ptrsz, vals []Ptrsz)

    Set(key Ptrsz, val Ptrsz)
    Del(key Ptrsz)

    DependVal(key Ptrsz, val Ptrsz)
    DependDel(key Ptrsz)

    Commit() error
    Rollback() error
}

А именно:

• Объект MemDb создается с помощью функции NewMemDb().

• У MemDb есть функция Close() -- мы ОБЯЗАНЫ ее вызвать!!!

• Объект Transaction создается с помощью функции StartTrn().

• У Transaction тоже есть функция Close(). Да, мы ОБЯЗАНЫ!

• Transaction работает с данными через lib.Ptrsz. Точно также, как и mdb.BlobMap.

• Чтение данных выполняется посредством функций Get() и All(). Возвращаемые ими Ptrsz указывают на внутренние структуры MemDb. Они остаются валидными пока не завершена транзакция и не было вызовов Set() и Del(), инвалидирующих указатели.

• Изменение данных выполняется посредством функций Set() и Del(). MemDb копирует себе байты, на которые указывают key и val.

• Функции DependVal() и DependDel() устанавливают зависимости. Их проверяет Commit().

• Функции Commit() и Rollback() завершают транзакцию. Завершают, но не закрывают! Мы ОБЯЗАНЫ вызвать Close()!!

• Просто Close() означает Rollback().

------------------8<------------------

Вот, кстати, полный текст статьи, но там почти что невозможно обнаружить ссылку на исходники... Ага, не раз такое видел в комментариях!

Linkedin писали русские

Перевод: https://www.linkedin.com/pulse/observe-dont-just-see-sergey-derevyago-cbj7f

Ватсон: Я думаю, мои глаза не хуже ваших.
Холмс: Да, это так. Но вы смотрите и не видите...

Сколько лет вы уже смотрите на эту картинку?

Нет, там не аудио компонент. А простое понятное русское слово...

С днём программиста!

Мое решение для Нерешаемой Проблемы

Все дети знают, что много мусора создает большие проблемы для Garbage Collector. Ну а взрослые видели и НЕРЕШАЕМЫЕ! Причем, мусора было немного:

We kept digging and learned the spikes were huge not because of a massive amount of ready-to-free memory, but because the garbage collector needed to scan the entire LRU cache in order to determine if the memory was truly free from references.

Что в этом случае делают взрослые? Правильно! Взрослые в ужасе убегают...

У меня есть решение для тех, кто устал убегать: mdb.BlobMap. Это быстрая хеш-таблица, не создающая проблем сборщику мусора:

ОК, что значит "не создающая проблем"? В данном случае это значит, что весь mdb.BlobMap -- это просто массив uint64...

Так НЕ БЫВАЕТ?!

Бывает, чо https://ders.by/go/blobmap/blobmap.html

Эффективные хеш-таблицы на Go

В Go нет недостатка хеш-таблиц. Вы всегда можете использовать встроенную map[Key]Val, с ошеломительной скоростью обладающую непревзойденным удобством! А изобилие типов Key, разрешенных к использованию, способно довести до изумления!

Вот только ни указатель, ни слайс не подходят... Невозможно подсунуть свои операции (равенства и хеширования). Но хоть со скоростью все хорошо! (извините, не удержался)

Итого, мне пришлось написать HashMap[K, V any], закрывающую проблемы.

------------------8<------------------

В это трудно поверить, но:

• Без резервирования памяти (конфигурация R0), map[uint64]uint64 работает в 1.93 раза медленнее UintMap! И производит в 5.64 раза больше мусора!!

• А с полным резервированием (R1), в 1.72 раза медленнее! И аж в 16.5 раз больше мусора!!!

Вдумайтесь! На коленке написанная хеш-таблица для целых чисел UintMap почти в два раза обгоняет ЖУТКО оптимизированную нативную map[uint64]uint64!! И существенно менее мусорит!!!

Но раз трудно поверить, то давайте проверим:

func MyUintMap() {
    const N = umN

//R0|    um := lib.NewUintMap(0)
    um := lib.NewUintMap(N) //R1|

    for i := uint64(0); i < N; i++ {
        um.Findsert(i, i+N)
    }
    lib.Assert(um.Size() == N)

    cnt := 0
    for i := uint64(0); i < N; i++ {
        if *um.Val(um.Find(i)) == i+N {
            cnt++
        }

        if um.Find(i+N) == -1 {
            cnt++
        }
    }
    lib.Assert(cnt == N*2)

    for i := uint64(0); i < N; i++ {
        um.Delete(i)
    }
    lib.Assert(um.Size() == 0)
}

func GoUintMap() {
    const N = umN

//R0|    m := make(map[uint64]uint64)
    m := make(map[uint64]uint64, N) //R1|

    for i := uint64(0); i < N; i++ {
        m[i] = i + N
    }
    lib.Assert(len(m) == N)

    cnt := 0
    for i := uint64(0); i < N; i++ {
        if m[i] == i+N {
            cnt++
        }

        if _, ok := m[i+N]; !ok {
            cnt++
        }
    }
    lib.Assert(cnt == N*2)

    for i := uint64(0); i < N; i++ {
        delete(m, i)
    }
    lib.Assert(len(m) == 0)
}

Здесь всего-то лишь вставка, два поиска и удаление. Запустите go test -bench=UintMap -benchmem и увидите сами. Вот только можно ли ругать Google за неэффективный map[uint64]uint64?

------------------8<------------------

Итоги?

1. Смело берите HashMap[K, V any] для слайсов и указателей!

2. Немного оптимизированная BytesMap -- лучший выбор для []byte.

3. Интересно оптимизированная UintMap -- это выбор для целых чисел. Разберитесь, что там "не так", и используйте за основу.

И как всегда, исходный код, подробности и пару неудачных шуток вы можете найти в моей статье https://ders.by/go/hashmap/hashmap.html

Совершенный assert() для всех языков программирования

...как ни смешно, но пострадали стоматологи: стало меньше зубовного скрежета!

Когда C/C++ разработчики переключаются на другие языки, им очень не хватает привычного механизма assert()/NDEBUG. Он, в некотором смысле, позволяет получить "идеальный" метод управления Debug/Release конфигурациями:

Как вы правильно поняли, в Release конфигурации строки кода между #ifndef NDEBUG и #endif полностью исчезают, и мы получаем идеальный билд. Но идентичного результата можно добиться и с помощью комментариев... ^{(здесь должна была быть картинка, но вставить не получается)}

Гмм.. Значит будет лишь краткий конспект статьи.

ОК, как ни странно, но это правда: я создал утилиту DebRel, полезную ВСЕМ языкам программирования! Комментарии специального вида (D0 - D9 и R0 - R9) позволяют минимальными усилиями добиться "идеального" управления Debug/Release конфигурациями:

• Debug конфигурация дает нам всю необходимую диагностику! С различной глубиной.

• В Release конфигурации нет никаких следов Debug-а! Ни байта.

А именно:

• Конфигурация RN отменяет все остальные. Релиз -- эгоист!

• Конфигурация DN оставляет лишь строки от D0 до DN. Вы задаете глубину отладки.

В общем, сразу читайте https://ders.by/arch/debrel/debrel.html Там есть подробности, исходники и сам debrel.exe.

Как банки спасают Планету от рабства

(перевод: https://www.linkedin.com/pulse/banks-save-earth-from-slavery-sergey-derevyago-z2tsf)

Одним прекрасным утром Менеджер сказал Сотруднику:
- С сегодняшнего дня и до Нового Года, ты должен работать до ночи!
- Я что тут - раб?!
- Не раб, конечно. Но за шикарную премию ты будешь работать!
- Ты обещаешь?
- Железно!
- Ну, гони тогда деньги прямо сейчас. Я верну тебе, как заплатят.
- Ха-ха-ха, отличная шутка! Я купил своим много подарков, так что денег уже не осталось.
- Не вопрос. Возьми в банке кредит.
- Э-э... [Я не могу взять кредит, потому что не будет тебе никакой премии. Мне просто нужно доказать начальству, что я умею обманывать дураков]
- Спасибо, банк!