Самый быстрый Индиан

Ну что мои маленькие сыроеды-любители. Пожалуй качественно вброшу ведь из под моего пера вышла еще одна настоящая нетленка.

Легендарный супероптимизированый алгоритм, который реализует весьма сложные Trie структуры данных и топчет вот эти вот эти ваши самые реализации ассоциативных массивов std::map, glib, dictionary.net и прочью заморскую попсу в разы, а то и на порядок.

github.com/Bazist/HArray (Windows & Linux)

PS: Готовлю потихоньку раскат гром и молнии на хабр, но пока потренируемся на Доу.

👍НравитсяПонравилось1
В избранноеВ избранном3
LinkedIn

Лучшие комментарии пропустить

1. Не надо «the most optimized». Просто «Trie implementation in C++», или «Fast Trie implementation». Но лучше без «fast», если нет тестов и легко воспроизводимых benchmark’ов.
2. Tab for indentation, spaces for alignment. Можно забить, и получить срач на тему spaces-vs-tabs вместо обсуждения кода когда оно пойдёт на Reddit.
github.com/...ValuesByRange.cpp#L22-L29
3. Не надо оставлять закомментированные блоки. Если один лишний повод для срача.
github.com/...dKeyAndValue.cpp#L22-L204
4. StdAfx.h, windows.h, int _tmain(int, _TCHAR*[]) — wtf? system("pause")?!
5. printf’ы в C++ коде? После include <iostream>? Ещё один повод для срача.

6*. Не эксперт в VS, но я бы ожидал там два проекта: собственно библиотеку, и отдельно от неё демку/тест/пример который main.c.
7*. Зачем в .gitattributes строки с 3-й до конца? Зачем мусор в .gitignore? VS реально столько оставляет в проекте, или это просто копипаст откуда-то?

8. Обычные Makefile-ы сильно увеличат шансы сборки левыми людьми.
Соответственно шансы получить отзывы по сути, а не по форматированию.
Или CMakeLists, и поубирать VS проекты.

9. Тесты, или что-то хотя бы отдалённо похожее на тесты. Сильно рекомендуется. Очень сильно.

Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
не надо так. В map нет никаких значений произвольной длины, все значения занимают sizeof(v) байтиков. Посмотри уже наконец, как работает мапа, там несложно

Эээ ...
Это что получается, я могу создать мап только с фиксированой длиной ключа sizeof(k) и фиксированой длиной велью sizeof(v) ? Тоесть я не могу вставлять в один и тотже инстанц мапы ключи разной длины ?

Печаль. Одни из первых версий которые я делал, работали именно с ключами фиксированой длины и работали в два раза быстрее чем текущая версия. Ради фичи вставлять ключи разной длины в один и тотже контейнер (которая полезна в реальных проекта) пришлось свой код замедлить даже больше чем в 2 раза. Я точно помню, даже на слабее машинке 10 млн 16ти байтных рандом ключей вставлял и читал меньше чем за 1 секунду, а сейчас больше 2х секунд. Это конечно все еще в несколько раз быстрее чем std::map, но осадочек остался. Может быть стоит форкнуть версию и сделать версию именно с ключами фиксированой длины в контейнере.

Это что получается, я могу создать мап только с фиксированой длиной ключа sizeof(k) и фиксированой длиной велью sizeof(v) ?
fn main() {
    let mut map1 = BTreeMap::new();

    map1.insert(vec![0, 5, 7, 8], "first");
    map1.insert(vec![42], "second");

    let mut map2 = HashMap::new();
    map2.insert(map1, 123456);
}

Так std::map вроде тоже подобный код поддерживает.
Только потом выясняется что он ссылки на эти обьекты хранит (которые фиксированой длины), а не делает честную побайтовую копию обьектов прозвольной длины и помещает внутрь контейнера.

map1.insert(vec![0, 5, 7, 8], "first");
map1.insert(vec![42], "second");

Но я считаю что у меня это скорей киллер фича. Для СУБД мапа которая хранит ссылки на обьекты в качестве ключей, по сути бесполезна и не может выступать в качестве основного storage механизма. Потому что нормальный storage должен делать копию обьекта произвольной длины и его хранить независимо от внешнего кода.

В коде, который я привел, ключ вставляется в мапу(а не ссылка), мапа владеет ключем, а не содержит ссылку на него. Синтаксис для передачи ссылки отличается.

Вставка ключа внутрь мапы:

    let key = vec![0, 5, 7, 8];
    map1.insert(key, "first");

Вставка ссылки на ключ внутрь мапы:

    let key = vec![0, 5, 7, 8];
    map1.insert(&key, "first");

Ок, значит в Расте мапа работает так как у меня.
Да и в других языках, вроде .NET и Java, такое же поведение.
Поэтому меня и удивило, почему std::map работает иначе, с урезаным функционалом.

Поэтому меня и удивило, почему std::map работает иначе, с урезаным функционалом.

дайте мне пистолет с одним патроном

Ок, значит в Расте мапа работает так как у меня.

В таком случае я должен спросить, какой был смысл писать свою мапу, если можно было использовать растовскую?

Может из-за этого ?

1. Очень высокая скорость работы. Тестирование без всяких подвохов, Key/Value контейнер имеет достаточно простые сценарии использования. В среднем HArray в 5-10 раз быстрее работает чем типичные реализации контейнеров вроде std::map, при этом имея даже немного более широкую функциональность. И в многих кейсах работает быстрее чем Hashtables, особенно на скорости вставок. Единственный кейс где Hashtables уверенно обгоняет HArray, это ключи последовательной природы, вроде 1,2,3 и тд. Но ирония в том, что для таких ключей Вам не нужен HArray, не нужен Hashtables или другой map, а подойдет обычный массив.

2. Малое потребление памяти. Для монотонных ключей, которые имеют общий префикс (пути к файлам, пути к обьектам, словари и тд) возможна компрессия данных по сравнению с оригинальным их размером. Компрессия данных невозможна в бинарных деревьях и тем более в хештаблицах, где перерасход памяти стабильно составляет в 2-3 раза.

3. Данные в контейнере находятся в сортированом (или близком к этому) виде. Возможность очень быстро определять, есть ли ключ с каким либо префиксом в контейнере. Доступна широкая функциональность по скану ключей. Возможность сканировать поддиапазоны ключей. При этом при сканировании поддиапазона мы не читаем все ключи вподряд, а как бы сканируем только «хвосты» ключей. Такая функциональность недоступна в хештаблицах и доступна в неоптимальном виде в бинарных деревьях.

4. Специфические, но не синтетические, контр примеры. Это когда вставляются длинные ключи с похожими префиксами. Они не использовались в бенчмарках, чтобы не давать HArray явное преимущество, но на этих контр примерах потребление памяти и скорость работы может отличатся в десятки и сотни раз в пользу HArray.

5. Нет хешфункций, нет коллизий. HArray отлично работает с большими обьемами данных, вставить миллиард ключей или больше в такую структуру не проблема. При этом плавное потребление памяти и почти константное время на вставках/поиске, которое зависит скорее от длины ключа, а не от количества ключей.

6. Еще немного плюшек: Возможность задавать правила сортировки ключей внутри контейнера. Нет Stop World событий на вставке (это когда структуре в какойто момент необходимо полностью перестроится, что занимает время). Сериализация/десериализация на диск, на скоростях близких к максимальной скорости работы диска (поскольку структура сбрасывает и подымает на диск страницы памяти, а не делает обход всего графа).

7. Удаление ключей с плавным освобождением памяти и упрощения структуры.

я могу создать мап только с фиксированой длиной ключа sizeof(k) и фиксированой длиной велью sizeof(v)

std::map типізована, тобто знає тип ключа і тип значення. І відповідно вміє їх правильно конструювати, копіювати, переміщувати і знищувати.

Тьфу ты, я думал тут про мотоцикл

Как его запустить? при make у меня куча error вылетает

Пишет что ты криворукий ))))))))

Тебя мама не кормит ? Почему такой злой.

Target: x86_64-linux-gnu
Configured with: ../src/configure -v —with-pkgversion=’Ubuntu 10.3.0-1ubuntu1′ —with-bugurl=file:///usr/share/doc/gcc-10/README.Bugs —enable-languages=c,ada,c++,go,brig,d,fortran,objc,obj-c++,m2 —prefix=/usr —with-gcc-major-version-only —program-suffix=-10 —program-prefix=x86_64-linux-gnu- —enable-shared —enable-linker-build-id —libexecdir=/usr/lib —without-included-gettext —enable-threads=posix —libdir=/usr/lib —enable-nls —enable-bootstrap —enable-clocale=gnu —enable-libstdcxx-debug —enable-libstdcxx-time=yes —with-default-libstdcxx-abi=new —enable-gnu-unique-object —disable-vtable-verify —enable-plugin —enable-default-pie —with-system-zlib —enable-libphobos-checking=release —with-target-system-zlib=auto —enable-objc-gc=auto —enable-multiarch —disable-werror —with-arch-32=i686 —with-abi=m64 —with-multilib-list=m32,m64,mx32 —enable-multilib —with-tune=generic —enable-offload-targets=nvptx-none=/build/gcc-10-gDeRY6/gcc-10-10.3.0/debian/tmp-nvptx/usr,amdgcn-amdhsa=/build/gcc-10-gDeRY6/gcc-10-10.3.0/debian/tmp-gcn/usr,hsa —without-cuda-driver —enable-checking=release —build=x86_64-linux-gnu —host=x86_64-linux-gnu —target=x86_64-linux-gnu —with-build-config=bootstrap-lto-lean —enable-link-mutex
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 10.3.0 (Ubuntu 10.3.0-1ubuntu1)

Main.cpp:854:6: error: variable or field ‘testHArrayStr’ declared void
854 | void testHArrayStr(std::string* keys, uint32 countKeys)
| ^~~~~~~~~~~~~
Main.cpp:854:25: error: ‘string’ is not a member of ‘std’
854 | void testHArrayStr(std::string* keys, uint32 countKeys)
| ^~~~~~
Main.cpp:28:1: note: ‘std::string’ is defined in header ‘’; did you forget to ‘#include ’?
27 | #include “HArray.h”
+++ |+#include
28 |
Main.cpp:854:33: error: ‘keys’ was not declared in this scope
854 | void testHArrayStr(std::string* keys, uint32 countKeys)
| ^~~~
Main.cpp:854:46: error: expected primary-expression before ‘countKeys’
854 | void testHArrayStr(std::string* keys, uint32 countKeys)
| ^~~~~~~~~
Main.cpp:992:6: error: variable or field ‘testHArrayStrVar’ declared void
992 | void testHArrayStrVar(std::string* keys, uint32 countKeys)
| ^~~~~~~~~~~~~~~~
Main.cpp:992:28: error: ‘string’ is not a member of ‘std’
992 | void testHArrayStrVar(std::string* keys, uint32 countKeys)
| ^~~~~~
Main.cpp:992:28: note: ‘std::string’ is defined in header ‘’; did you forget to ‘#include ’?
Main.cpp:992:36: error: ‘keys’ was not declared in this scope
992 | void testHArrayStrVar(std::string* keys, uint32 countKeys)
| ^~~~
Main.cpp:992:49: error: expected primary-expression before ‘countKeys’
992 | void testHArrayStrVar(std::string* keys, uint32 countKeys)
| ^~~~~~~~~
Main.cpp:1180:6: error: variable or field ‘testStdMapStr’ declared void
1180 | void testStdMapStr(std::string* keys, uint32 countKeys)
| ^~~~~~~~~~~~~
Main.cpp:1180:25: error: ‘string’ is not a member of ‘std’
1180 | void testStdMapStr(std::string* keys, uint32 countKeys)
| ^~~~~~
Main.cpp:1180:25: note: ‘std::string’ is defined in header ‘’; did you forget to ‘#include ’?
Main.cpp:1180:33: error: ‘keys’ was not declared in this scope
1180 | void testStdMapStr(std::string* keys, uint32 countKeys)
| ^~~~
Main.cpp:1180:46: error: expected primary-expression before ‘countKeys’
1180 | void testStdMapStr(std::string* keys, uint32 countKeys)
| ^~~~~~~~~
Main.cpp:1230:6: error: variable or field ‘testDenseHashMapStr’ declared void
1230 | void testDenseHashMapStr(std::string* keys, uint32 countKeys)
| ^~~~~~~~~~~~~~~~~~~
Main.cpp:1230:31: error: ‘string’ is not a member of ‘std’
1230 | void testDenseHashMapStr(std::string* keys, uint32 countKeys)
| ^~~~~~
Main.cpp:1230:31: note: ‘std::string’ is defined in header ‘’; did you forget to ‘#include ’?
Main.cpp:1230:39: error: ‘keys’ was not declared in this scope
1230 | void testDenseHashMapStr(std::string* keys, uint32 countKeys)
| ^~~~
Main.cpp:1230:52: error: expected primary-expression before ‘countKeys’
1230 | void testDenseHashMapStr(std::string* keys, uint32 countKeys)
| ^~~~~~~~~
Main.cpp:1283:6: error: variable or field ‘testStdUnorderedMapStr’ declared void
1283 | void testStdUnorderedMapStr(std::string* keys, uint32 countKeys)
| ^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:1283:34: error: ‘string’ is not a member of ‘std’
1283 | void testStdUnorderedMapStr(std::string* keys, uint32 countKeys)
| ^~~~~~
Main.cpp:1283:34: note: ‘std::string’ is defined in header ‘’; did you forget to ‘#include ’?
Main.cpp:1283:42: error: ‘keys’ was not declared in this scope
1283 | void testStdUnorderedMapStr(std::string* keys, uint32 countKeys)
| ^~~~
Main.cpp:1283:55: error: expected primary-expression before ‘countKeys’
1283 | void testStdUnorderedMapStr(std::string* keys, uint32 countKeys)
| ^~~~~~~~~
Main.cpp:1335:6: error: variable or field ‘fillSeqStrs’ declared void
1335 | void fillSeqStrs(std::string* keys, uint32 countKeys)
| ^~~~~~~~~~~
Main.cpp:1335:23: error: ‘string’ is not a member of ‘std’
1335 | void fillSeqStrs(std::string* keys, uint32 countKeys)
| ^~~~~~
Main.cpp:1335:23: note: ‘std::string’ is defined in header ‘’; did you forget to ‘#include ’?
Main.cpp:1335:31: error: ‘keys’ was not declared in this scope
1335 | void

fillSeqStrs(std::string* keys, uint32 countKeys)
| ^~~~
Main.cpp:1335:44: error: expected primary-expression before ‘countKeys’
1335 | void fillSeqStrs(std::string* keys, uint32 countKeys)
| ^~~~~~~~~
Main.cpp:1352:6: error: variable or field ‘fillRandStrs’ declared void
1352 | void fillRandStrs(std::string* keys, uint32 countKeys)
| ^~~~~~~~~~~~
Main.cpp:1352:24: error: ‘string’ is not a member of ‘std’
1352 | void fillRandStrs(std::string* keys, uint32 countKeys)
| ^~~~~~
Main.cpp:1352:24: note: ‘std::string’ is defined in header ‘’; did you forget to ‘#include ’?
Main.cpp:1352:32: error: ‘keys’ was not declared in this scope
1352 | void fillRandStrs(std::string* keys, uint32 countKeys)
| ^~~~
Main.cpp:1352:45: error: expected primary-expression before ‘countKeys’
1352 | void fillRandStrs(std::string* keys, uint32 countKeys)
| ^~~~~~~~~
Main.cpp: In function ‘void HArray_VS_StdMap_StrKey(uint32, uint32, uint32)’:
Main.cpp:1370:7: error: ‘string’ is not a member of ‘std’
1370 | std::string* strKeys = new std::string[stopOnAmount];
| ^~~~~~
Main.cpp:1370:7: note: ‘std::string’ is defined in header ‘’; did you forget to ‘#include ’?
Main.cpp:1370:15: error: ‘strKeys’ was not declared in this scope
1370 | std::string* strKeys = new std::string[stopOnAmount];
| ^~~~~~~
Main.cpp:1370:34: error: ‘string’ in namespace ‘std’ does not name a type
1370 | std::string* strKeys = new std::string[stopOnAmount];
| ^~~~~~
Main.cpp:1370:29: note: ‘std::string’ is defined in header ‘’; did you forget to ‘#include ’?
1370 | std::string* strKeys = new std::string[stopOnAmount];
| ^~~
Main.cpp:1374:2: error: ‘fillSeqStrs’ was not declared in this scope; did you mean ‘fillSeqBins’?
1374 | fillSeqStrs(strKeys, stopOnAmount);
| ^~~~~~~~~~~
| fillSeqBins
Main.cpp:1379:3: error: ‘testHArrayStr’ was not declared in this scope; did you mean ‘testHArrayBin’?
1379 | testHArrayStr(strKeys, countKeys);
| ^~~~~~~~~~~~~
| testHArrayBin
Main.cpp:1380:3: error: ‘testDenseHashMapStr’ was not declared in this scope; did you mean ‘testDenseHashMapBin’?
1380 | testDenseHashMapStr(strKeys, countKeys);
| ^~~~~~~~~~~~~~~~~~~
| testDenseHashMapBin
Main.cpp:1381:3: error: ‘testStdMapStr’ was not declared in this scope; did you mean ‘testStdMapBin’?
1381 | testStdMapStr(strKeys, countKeys);
| ^~~~~~~~~~~~~
| testStdMapBin
Main.cpp:1382:3: error: ‘testStdUnorderedMapStr’ was not declared in this scope; did you mean ‘testStdUnorderedMapBin’?
1382 | testStdUnorderedMapStr(strKeys, countKeys);
| ^~~~~~~~~~~~~~~~~~~~~~
| testStdUnorderedMapBin
Main.cpp:1390:2: error: ‘fillRandStrs’ was not declared in this scope; did you mean ‘fillRandBins’?
1390 | fillRandStrs(strKeys, stopOnAmount);
| ^~~~~~~~~~~~
| fillRandBins
Main.cpp:1395:3: error: ‘testHArrayStr’ was not declared in this scope; did you mean ‘testHArrayBin’?
1395 | testHArrayStr(strKeys, countKeys);
| ^~~~~~~~~~~~~
| testHArrayBin
Main.cpp:1396:3: error: ‘testDenseHashMapStr’ was not declared in this scope; did you mean ‘testDenseHashMapBin’?
1396 | testDenseHashMapStr(strKeys, countKeys);
| ^~~~~~~~~~~~~~~~~~~
| testDenseHashMapBin
Main.cpp:1397:3: error: ‘testStdMapStr’ was not declared in this scope; did you mean ‘testStdMapBin’?
1397 | testStdMapStr(strKeys, countKeys);
| ^~~~~~~~~~~~~
| testStdMapBin
Main.cpp:1398:3: error: ‘testStdUnorderedMapStr’ was not declared in this scope; did you mean ‘testStdUnorderedMapBin’?
1398 | testStdUnorderedMapStr(strKeys, countKeys);
| ^~~~~~~~~~~~~~~~~~~~~~
| testStdUnorderedMapBin
Main.cpp:1404:11: error: type ‘’ argument given to ‘delete’, expected pointer
1404 | delete[] strKeys;
| ^~~~~~~
Main.cpp: In function ‘void HArray_VS_StdMap_StrKey_Var(uint32, uint32, uint32)’:
Main.cpp:1415:7: error: ‘string’ is not a member of ‘std’
1415 | std::string* strKeys = new std::string[stopOnAmount];
| ^~~~~~
Main.cpp:1415:7: note: ‘std::string’ is defined in header ‘’; did you forget to

‘#include ’?
Main.cpp:1415:15: error: ‘strKeys’ was not declared in this scope
1415 | std::string* strKeys = new std::string[stopOnAmount];
| ^~~~~~~
Main.cpp:1415:34: error: ‘string’ in namespace ‘std’ does not name a type
1415 | std::string* strKeys = new std::string[stopOnAmount];
| ^~~~~~
Main.cpp:1415:29: note: ‘std::string’ is defined in header ‘’; did you forget to ‘#include ’?
1415 | std::string* strKeys = new std::string[stopOnAmount];
| ^~~
Main.cpp:1419:2: error: ‘fillRandStrs’ was not declared in this scope; did you mean ‘fillRandBins’?
1419 | fillRandStrs(strKeys, stopOnAmount);
| ^~~~~~~~~~~~
| fillRandBins
Main.cpp:1424:3: error: ‘testHArrayStrVar’ was not declared in this scope; did you mean ‘testHArrayBin’?
1424 | testHArrayStrVar(strKeys, countKeys);
| ^~~~~~~~~~~~~~~~
| testHArrayBin
Main.cpp:1430:11: error: type ‘’ argument given to ‘delete’, expected pointer
1430 | delete[] strKeys;
| ^~~~~~~

Попробуй сейчас master забрать.

Говорил, что код на марсоход можно ставить, а он даже не собирается.

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

Говорил, что код на марсоход можно ставить, а он даже не собирается.

Ну ошибки нужно читать.
Его компилятор почему-то не видит std::string.
Я добавил явно
#include string в main.
Но вообще-то, в stdafx.h уже есть подобная строчка. И везде такой код компилировался.
Так что хз или поможет. Вполне могут быть проблемы с этой специфической машиной и настройками компилятора на ней.

У меня Убунту обычная и компилятор из коробки.

Его компилятор почему-то не видит std::string.
Я добавил явно
#include string в main.
Но вообще-то, в stdafx.h уже есть подобная строчка. И везде такой код компилировался.
Так что хз или поможет. Вполне могут быть проблемы с этой специфической машиной и настройками компилятора на ней.

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

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

Код я разрабатываю и компилирую в Visual Studio. Потому что удобнее VS ничего не придумали. И уже только потом проверяю под другие компиляторы на Линукс машине. В данном случае код полностью компилировался и работал под Visual Studio на винде, но перестал собираться под Линукс. Что я уже пофиксил.

Код я разрабатываю и компилирую в Visual Studio. Потому что удобнее VS ничего не придумали.

CLion
Code Blocks
Visual Studio Code
Vim

Ты просто VS не видел. Как раз пол часа назад дебажил в Code::Blocks по сравнению с VS он выглядит как текстовый редактор.

Ошибки со стрингами пропали, но сейчас вот эти:

g++ HArray_delValueByKey.cpp HArray_getValueByKey.cpp HArray_getKeysAndValuesByRange.cpp HArray_hasPartKey.cpp HArray_insert.cpp HArray_scanKeysAndValues.cpp HArray_rebuild.cpp HArray_resizeHeader.cpp HArray_shrink.cpp HArray_test.cpp Main.cpp -o HArray -w
In file included from HArray_delValueByKey.cpp:20:
HArray.h: In member function ‘bool HArray::saveToFile(const char*)’:
HArray.h:213:3: error: ‘errno_t’ was not declared in this scope
213 | errno_t errorCode = fopen_s(&pFile, path, „wb”);
| ^~~~~~~
HArray.h:215:10: error: ‘errorCode’ was not declared in this scope
215 | if (!errorCode)
| ^~~~~~~~~
HArray.h: In member function ‘bool HArray::loadFromFile(const char*)’:
HArray.h:300:3: error: ‘errno_t’ was not declared in this scope
300 | errno_t errorCode = fopen_s(&pFile, path, „rb”);
| ^~~~~~~
HArray.h:302:10: error: ‘errorCode’ was not declared in this scope
302 | if (!errorCode)
| ^~~~~~~~~
In file included from HArray_getValueByKey.cpp:20:
HArray.h: In member function ‘bool HArray::saveToFile(const char*)’:
HArray.h:213:3: error: ‘errno_t’ was not declared in this scope
213 | errno_t errorCode = fopen_s(&pFile, path, „wb”);
| ^~~~~~~
HArray.h:215:10: error: ‘errorCode’ was not declared in this scope
215 | if (!errorCode)
| ^~~~~~~~~
HArray.h: In member function ‘bool HArray::loadFromFile(const char*)’:
HArray.h:300:3: error: ‘errno_t’ was not declared in this scope
300 | errno_t errorCode = fopen_s(&pFile, path, „rb”);
| ^~~~~~~
HArray.h:302:10: error: ‘errorCode’ was not declared in this scope
302 | if (!errorCode)
| ^~~~~~~~~
In file included from HArray_getKeysAndValuesByRange.cpp:20:
HArray.h: In member function ‘bool HArray::saveToFile(const char*)’:
HArray.h:213:3: error: ‘errno_t’ was not declared in this scope
213 | errno_t errorCode = fopen_s(&pFile, path, „wb”);
| ^~~~~~~
HArray.h:215:10: error: ‘errorCode’ was not declared in this scope
215 | if (!errorCode)
| ^~~~~~~~~
HArray.h: In member function ‘bool HArray::loadFromFile(const char*)’:
HArray.h:300:3: error: ‘errno_t’ was not declared in this scope
300 | errno_t errorCode = fopen_s(&pFile, path, „rb”);
| ^~~~~~~
HArray.h:302:10: error: ‘errorCode’ was not declared in this scope
302 | if (!errorCode)
| ^~~~~~~~~
In file included from HArray_hasPartKey.cpp:20:
HArray.h: In member function ‘bool HArray::saveToFile(const char*)’:
HArray.h:213:3: error: ‘errno_t’ was not declared in this scope
213 | errno_t errorCode = fopen_s(&pFile, path, „wb”);
| ^~~~~~~
HArray.h:215:10: error: ‘errorCode’ was not declared in this scope
215 | if (!errorCode)
| ^~~~~~~~~
HArray.h: In member function ‘bool HArray::loadFromFile(const char*)’:
HArray.h:300:3: error: ‘errno_t’ was not declared in this scope
300 | errno_t errorCode = fopen_s(&pFile, path, „rb”);
| ^~~~~~~
HArray.h:302:10: error: ‘errorCode’ was not declared in this scope
302 | if (!errorCode)
| ^~~~~~~~~
In file included from HArray_insert.cpp:21:
HArray.h: In member function ‘bool HArray::saveToFile(const char*)’:
HArray.h:213:3: error: ‘errno_t’ was not declared in this scope
213 | errno_t errorCode = fopen_s(&pFile, path, „wb”);
| ^~~~~~~
HArray.h:215:10: error: ‘errorCode’ was not declared in this scope
215 | if (!errorCode)
| ^~~~~~~~~
HArray.h: In member function ‘bool HArray::loadFromFile(const char*)’:
HArray.h:300:3: error: ‘errno_t’ was not declared in this scope
300 | errno_t errorCode = fopen_s(&pFile, path, „rb”);
| ^~~~~~~
HArray.h:302:10: error: ‘errorCode’ was not declared in this scope
302 | if (!errorCode)
| ^~~~~~~~~
HArray_insert.cpp: In member function ‘bool HArray::insert(uint32*, uint32, uint32)’:
HArray_insert.cpp:1489:2: error: jump to label ‘FILL_KEY’
1489 | FILL_KEY:
| ^~~~~~~~
HArray_insert.cpp:488:12: note: from here
488 | goto FILL_KEY;
| ^~~~~~~~
HArray_insert.cpp:552:10: note: crosses initialization of ‘uint32 keyValue’
552 | uint32 keyValue = key[keyOffset];
| ^~~~~~~~
HArray_insert.cpp:1489:2: error: jump to label ‘FILL_KEY’
1489 | FILL_KEY:
| ^~~~~~~~
HArray_insert.cpp:313:12: note: from here
313 | goto FILL_KEY;
|

^~~~~~~~
HArray_insert.cpp:552:10: note: crosses initialization of ‘uint32 keyValue’
552 | uint32 keyValue = key[keyOffset];
| ^~~~~~~~
HArray_insert.cpp:1493:2: error: jump to label ‘FILL_KEY2’
1493 | FILL_KEY2:
| ^~~~~~~~~
HArray_insert.cpp:539:11: note: from here
539 | goto FILL_KEY2;
| ^~~~~~~~~
HArray_insert.cpp:552:10: note: crosses initialization of ‘uint32 keyValue’
552 | uint32 keyValue = key[keyOffset];
| ^~~~~~~~
HArray_insert.cpp:1493:2: error: jump to label ‘FILL_KEY2’
1493 | FILL_KEY2:
| ^~~~~~~~~
HArray_insert.cpp:361:11: note: from here
361 | goto FILL_KEY2;
| ^~~~~~~~~
HArray_insert.cpp:552:10: note: crosses initialization of ‘uint32 keyValue’
552 | uint32 keyValue = key[keyOffset];
| ^~~~~~~~
In file included from HArray_scanKeysAndValues.cpp:20:
HArray.h: In member function ‘bool HArray::saveToFile(const char*)’:
HArray.h:213:3: error: ‘errno_t’ was not declared in this scope
213 | errno_t errorCode = fopen_s(&pFile, path, „wb”);
| ^~~~~~~
HArray.h:215:10: error: ‘errorCode’ was not declared in this scope
215 | if (!errorCode)
| ^~~~~~~~~
HArray.h: In member function ‘bool HArray::loadFromFile(const char*)’:
HArray.h:300:3: error: ‘errno_t’ was not declared in this scope
300 | errno_t errorCode = fopen_s(&pFile, path, „rb”);
| ^~~~~~~
HArray.h:302:10: error: ‘errorCode’ was not declared in this scope
302 | if (!errorCode)
| ^~~~~~~~~
In file included from HArray_rebuild.cpp:20:
HArray.h: In member function ‘bool HArray::saveToFile(const char*)’:
HArray.h:213:3: error: ‘errno_t’ was not declared in this scope
213 | errno_t errorCode = fopen_s(&pFile, path, „wb”);
| ^~~~~~~
HArray.h:215:10: error: ‘errorCode’ was not declared in this scope
215 | if (!errorCode)
| ^~~~~~~~~
HArray.h: In member function ‘bool HArray::loadFromFile(const char*)’:
HArray.h:300:3: error: ‘errno_t’ was not declared in this scope
300 | errno_t errorCode = fopen_s(&pFile, path, „rb”);
| ^~~~~~~
HArray.h:302:10: error: ‘errorCode’ was not declared in this scope
302 | if (!errorCode)
| ^~~~~~~~~
In file included from HArray_resizeHeader.cpp:21:
HArray.h: In member function ‘bool HArray::saveToFile(const char*)’:
HArray.h:213:3: error: ‘errno_t’ was not declared in this scope
213 | errno_t errorCode = fopen_s(&pFile, path, „wb”);
| ^~~~~~~
HArray.h:215:10: error: ‘errorCode’ was not declared in this scope
215 | if (!errorCode)
| ^~~~~~~~~
HArray.h: In member function ‘bool HArray::loadFromFile(const char*)’:
HArray.h:300:3: error: ‘errno_t’ was not declared in this scope
300 | errno_t errorCode = fopen_s(&pFile, path, „rb”);
| ^~~~~~~
HArray.h:302:10: error: ‘errorCode’ was not declared in this scope
302 | if (!errorCode)
| ^~~~~~~~~
HArray_resizeHeader.cpp: At global scope:
HArray_resizeHeader.cpp:23:6: error: no declaration matches ‘void HArray::resizeHeader()’
23 | void HArray::resizeHeader()
| ^~~~~~
HArray_resizeHeader.cpp:23:6: note: no functions named ‘void HArray::resizeHeader()’
In file included from HArray_resizeHeader.cpp:21:
HArray.h:28:7: note: ‘class HArray’ defined here
28 | class HArray
| ^~~~~~
In file included from HArray_shrink.cpp:21:
HArray.h: In member function ‘bool HArray::saveToFile(const char*)’:
HArray.h:213:3: error: ‘errno_t’ was not declared in this scope
213 | errno_t errorCode = fopen_s(&pFile, path, „wb”);
| ^~~~~~~
HArray.h:215:10: error: ‘errorCode’ was not declared in this scope
215 | if (!errorCode)
| ^~~~~~~~~
HArray.h: In member function ‘bool HArray::loadFromFile(const char*)’:
HArray.h:300:3: error: ‘errno_t’ was not declared in this scope
300 | errno_t errorCode = fopen_s(&pFile, path, „rb”);
| ^~~~~~~
HArray.h:302:10: error: ‘errorCode’ was not declared in this scope
302 | if (!errorCode)
| ^~~~~~~~~
In file included from HArray_test.cpp:21:
HArray.h: In member function ‘bool HArray::saveToFile(const char*)’:
HArray.h:213:3: error: ‘errno_t’ was not declared in this scope
213 | errno_t errorCode = fopen_s(&pFile, path, „wb”);
| ^~~~~~~
HArray.h:215:10: error: ‘errorCode’ was not declared in this scope
215 | if (!errorCode)
|

^~~~~~~~~
HArray.h: In member function ‘bool HArray::loadFromFile(const char*)’:
HArray.h:300:3: error: ‘errno_t’ was not declared in this scope
300 | errno_t errorCode = fopen_s(&pFile, path, „rb”);
| ^~~~~~~
HArray.h:302:10: error: ‘errorCode’ was not declared in this scope
302 | if (!errorCode)
| ^~~~~~~~~
In file included from Main.cpp:28:
HArray.h: In member function ‘bool HArray::saveToFile(const char*)’:
HArray.h:213:3: error: ‘errno_t’ was not declared in this scope; did you mean ‘error_t’?
213 | errno_t errorCode = fopen_s(&pFile, path, „wb”);
| ^~~~~~~
| error_t
HArray.h:215:10: error: ‘errorCode’ was not declared in this scope
215 | if (!errorCode)
| ^~~~~~~~~
HArray.h: In member function ‘bool HArray::loadFromFile(const char*)’:
HArray.h:300:3: error: ‘errno_t’ was not declared in this scope; did you mean ‘error_t’?
300 | errno_t errorCode = fopen_s(&pFile, path, „rb”);
| ^~~~~~~
| error_t
HArray.h:302:10: error: ‘errorCode’ was not declared in this scope
302 | if (!errorCode)
| ^~~~~~~~~
make: *** [makefile:2: all] Error 1

Вот так сиди, убирай ворнинги.
Visual Studio ругалась ворнингом, что замените fopen на fopen_s
При этом получается fopen_s с ее структурой errno_t под линукс уже не компилится,
потому что fopen_s ниразу не стандарт.
Получается нужна развилка отдельно под линукс, отдельно под виндовз.
От фикса ворнингов похоже больше вреда чем пользы получилось.

Ладно, доберусь до убунту машины, перепроверю. Чтоб не дергать если еще что всплывет.
Спасибо за труд, хорошо что обнаружилось.

Из доки

Serialize/Deserialize from/to file at a speed close to the max speed of hard drive

HArray ha;

ha.saveToFile("c:\\dump");

ha.loadFromFile("c:\\dump");

Ок. И при чём тут хэш к сериализатору/десериализатору?

Одна из фишек HArray, что при сохранении на диск, он не обходит весь граф обьектов, что может быть очень долго. Он просто сбрасывает страницы памяти на диск и потом ровно также их читает, не нужно вставлять туда по новой элементы по одному. Тоесть если диск пишет, допустим, 250 мб/сек. То примерно с такой скоростью HArray может быть сериализован и десериализован с диска.

Добрался до Линукс машины, запушил изменения, можно проверять.
Вычистил все ворнинги и эроры.

Стабильность — признак мастерства. За 5 лет ничего не изменилось :)))))

# g++ HArray_insert.cpp
HArray_insert.cpp:1489:2: error: jump to label 'FILL_KEY' [-fpermissive]
  FILL_KEY:
  ^~~~~~~~
HArray_insert.cpp:488:12: note:   from here
       goto FILL_KEY;
            ^~~~~~~~
HArray_insert.cpp:552:10: note:   crosses initialization of 'uint32 keyValue'
   uint32 keyValue = key[keyOffset];
          ^~~~~~~~
я ж правильно понимаю, что если это все-таки сбилдить, и включить все оптимизации, то компилятор может тупо вырезать все ветки, которые ведут к этому гото?

Если не ошибаюсь, это неопределенное поведение.

не шарю c/c++, но судя по цппреференсу, это что-то еще хуже чем ub — стандарт говорит, что такой код даже компилироваться не должен. Что в таком случае оно будет выдавать с О3?

Это просто бздик этого компилятора, что нельзя прыгать в такой конструкции.
Для него это реинициализация.

LABEL:
uint32 keyValue = key[keyOffset];
goto LABEL;

Я переписал (и закомитил) вот так и претензии у него к коду отпали.

uint32 keyValue;
LABEL:
keyValue = key[keyOffset];
goto LABEL;
goto LABEL;

goto это хорошо, особенно прыгать из одного if в другой. Перепиши по нормальному свой код =)

Его уже нереально переписать.
В 2016 году прилетели инопланетяне, оставили unhumanity logic код, показали землянам как надо писать такие контейнеры и улетели. Остается чесать тыковку и думать, почему это работает.
/Sarcasm Off/

Артем, Панк и Головатый, я думаю у вас достаточно уже занний, чтобы форкнуть эти поделки и дофиксать по человечески, а там уже и монгу потеснить и свой самолет прикупить :-)
Если че я инвестирую свою гробовую заначку :-))))

Мені справді цікаво погратися з цією структурою, але в такому вигляді як вона є це дуже складно. Принаймні для мене.

Trie я ніколи не писав, але колись сам реалізовував різні види дерев з усіма операціями, міряв у порівнянні з std::map та boost::hash_map, навіть підглядав щось у тих всередині. Приємно згадати :)

Если б ТС описал алгоритм, и доказал формально его корректность, можно было бы о чем-то говорить. Портировать алгоритм, который может иметь формальный баг, нет смысла.

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

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

Один из этих языков я презираю, а другой — ненавижу.

Это ты зря. Ценность языка на самом деле не в синтаксисе, а в наличии продвинутого компилятора для него. Люди закопали сотни человеколет, чтобы код после компиляторов Си/Си++ был максимально эффективным. А вот сколько на компилятор Раст потратили человеколет, неизвестно. Но явно меньше чем на Си/Си++.
Отсюда вывод, возможно для Раст лучше залинковать готовые бинарники скомпилированные С/С++ компиляторами.

Это ты зря. Ценность языка на самом деле не в синтаксисе, а в наличии продвинутого компилятора для него.

Не вижу смысла об этом спорить. Я свой выбор сделал и в советах не нуждаюсь.

Люди закопали сотни человеколет, чтобы код после компиляторов Си/Си++ был максимально эффективным. А вот сколько на компилятор Раст потратили человеколет, неизвестно. Но явно меньше чем на Си/Си++.

В компиляторе раста такой же бекенд, как и в компиляторе clang. А скоро еще допилят бекенд gcc, тогда вообще збс будет.

Отсюда вывод, возможно для Раст лучше залинковать готовые бинарники скомпилированные С/С++ компиляторами.

Зачем раст линковать с тем, в чем скорее всего течет память и есть UB?

Зачем раст линковать с тем, в чем скорее всего течет память и есть UB?

Пруфы будут ? Вот код который чекает консистентность страниц памяти. Сверяет что каждый бит сошёлся в контрольных суммах. github.com/...​er/HArray/HArray_test.cpp
Этого кода могло бы и не быть, как в тысячах других проектах, но он есть. Его роль, чтобы качество работы программы, хоть на марсоход поставляй. Целый слой логики отвечающий за самодиагностику состояния контейнера в каждый момент времени.

Пруфы будут ? Вот код который чекает консистентность страниц памяти. Сверяет что каждый бит сошёлся в контрольных суммах. github.com/...​er/HArray/HArray_test.cpp

Можешь написать зачем эти биты чекать? Что именно это дает и где этот чек выполняется?

Можешь написать зачем эти биты чекать? Что именно это дает

Типичный баг с этим контейнером выглядит примерно так.
При вставке 7,854,123 ключа, что-то пошло не так. Допустим не дозаписали сегмент в блоке. Постепенно ситуация ухудшается, данные тихо кораптятся и при вставке 9,123,456 ключа процесс крашится или ключи перестают корректно читатся. Вот чтобы обнаружить точку где начались проблемы как можно раньше и существует этот код. Также он чекает висячие ссылки, блоки которые записаны, но не используются и нигде не фигурируют в пулах.

где этот чек выполняется?

Выполняется когда гоняют тесты и бенчмарки. Наиболее тяжелые кейсы, когда контейнер нужно разобрать по кирпичикам при удалении ключей. Начинается сложный процесс описанный в этом топике dou.ua/forums/topic/33788 И этот код помагает чекать, что после каждой итерации при сворачивании от сложного к простому, контейнер находится в полностью консистентном состоянии и готов для применения следующей итерации изменений.

Допиливать до рабочего состояния его солянку из С и С++ у меня лично желания нет. Один из этих языков я презираю, а другой — ненавижу.
Я б портировал на Rust

С любым свеже-выпущенным процессором — производителем процессора поставляется компилятор С.

Кто в здравом уме и не будучи в состоянии наркотического одурения — будет поставлять с процессором компилятор Раста?

Так что, хипстеры могут продолжать развлекаться любимым Растом в своих песочницах и генерить свои «оупен-соурс» неоплачиваемые поделки сколько влезет. Вход в реальную индустрию (тy, что со специалистами и с деньгами) — Расту не грозит.

Можно пример процессора, под который не собирается Rust?

doc.rust-lang.org/...​stc/platform-support.html

Собственно, гарантированная поддержка — лишь для „Tier 1” платформ:
— ARM64 Linux (kernel 4.2, glibc 2.17+) 1
— 32-bit MinGW (Windows 7+)
— 32-bit MSVC (Windows 7+)
— 32-bit Linux (kernel 2.6.32+, glibc 2.11+)
— 64-bit macOS (10.7+, Lion+)
— 64-bit MinGW (Windows 7+)
— 64-bit MSVC (Windows 7+)
— 64-bit Linux (kernel 2.6.32+, glibc 2.11+)

На „Tier 2” собирается, но с „красными” тестами.

На „Tier 3”, может не собраться. Или даже если соберётся — (может) не запуститься (т.к., к примеру, не хватает памяти).

Т.е. внезапно на большинство свежевыпущенных мейнстримовых процессоров есть поддержка или Tier 1 или Tier 2. Это результат годного дизайна экосистемы компилятора — вместо того, чтоб самим пилить бекенд, взяли бекенд LLVM и получили бесплатную поддержку тонны платформ.

Кое-что требует допиливания (поэтому куча вещей или отсутствует, или лежит в Tier 3), но это место, где рынок голосует — put your time where your mouth is. Если не нашлось хотя бы одного красноглазика, который хотя бы запилит Tier 3 поддержку, значит платформа мертва, или настолько закрыта, что несовместима с идеологией Rust.

Скоро допилят gcc as backend, тогда вообще збс будет.

Так что не надо тут сказки рассказывать про «свежевыпущенные процессоры».

Хз как в Раст, но компиляторы на Си/Си++ писали настоящие задроты еще тогда, когда над каждым байтом трусились как над последними штанами. Я когда-то читал что умеет делать Си компилятор, так он умеет даже рекурсию разворачивать в циклы. Тоесть любой новый ЯП, может выигрывать конечно по синтаксису или брать другими фишками. Но если речь идет о том, чтобы написать действительно оптимизированный код, то Си/Си++ компилятор вне конкуренции, поскольку это десятки мегабайт алгоритмов по оптимизации в архиве. И конечно такие невероятные вложения времени и сил для написания компиляторов на новые ЯП уже никто не делает.

Я когда-то читал что умеет делать Си компилятор, так он умеет даже рекурсию разворачивать в циклы.

Я рад, что ты для себя открыл такую штуку как tail call optimization, которую изобрели еще в 70-х годах (как и все остальные крутые штуки в области computer science).

Кстати, есть языки, в которых нет циклов вообще (например, Scheme), и tail call optimization, это единственное, что позволяет в этих языках делать циклы.

Си/Си++ компилятор вне конкуренции

Давно уже не вне конкуренции. Можешь найти бенчмарки, на которых Rust стоит рядом с С и С++.

поскольку это десятки мегабайт алгоритмов по оптимизации в архиве. И конечно такие невероятные вложения времени и сил для построения качественных компиляторов для новых ЯП уже никто не делает.

Умные люди давно поняли, что пилить тулчейн с нуля для каждого языка не получится, поэтому сейчас есть компоненты для построения тулчейны языка, например, LLVM, который используется Clang-ом для компиляции C/C++ и Rust-ом для компиляции Rust кода, предоставляя им практически одинаковые оптимизации (за вычетом оптимизации неопределенного поведения С/С++), и одинаковый набор поддерживаемых платформ.

Кроме того, в пятый раз напишу, что в добавок к LLVM бекенду, уже пилится альтернативный Rust бекенд на базе GCC, и оптимизации и платформы, которые поддерживает GCC, тоже будут доступны в Rust.

Давно уже не вне конкуренции. Можешь найти бенчмарки, на которых Rust стоит рядом с С и С++.

Если бы я написал контейнер который работает по скорости «рядом» с тем же std::map меня бы даже слушать не стали. Сдается мне что мало Расту приблизится к скорости С/С++ чтобы его вытеснить. Поскольку С/С++ это уже давно мейнстрим и стандарт.
Ну а синтаксис, С/С++ выбирают не за синтаксис, а за наработаную кодовую базу и возможность писать на нем низкоуровневый код.

Давно уже не вне конкуренции. Можешь найти бенчмарки, на которых Rust стоит рядом с С и С++.

Раст уже осилил что-нибудь похожее на «placement new»? Насколько я понял, нет.

А без этого, о каких вообще бенчмарках можно говорить?
Разве что, если сравниватъ с кодом, написанным полными нубами (они обычно и пишут эти публичные т.н. «бенчмарки») — которые понятия не имеют, как правильно писать производительный код на C/C++.

А потом, на основании этих т.н. «бенчмарков» — другие нубы рассказывают, что «модерн жаба уже быстрее плюсов».

Раст уже осилил что-нибудь похожее на «placement new»? Насколько я понял, нет.

Это бессмысленный вопрос, потому что в Rust нет конструкторов с понимании C++. Но мы можем написать функцию, которая проинициализирует указанный указатель так, как нам нужно. Возможно нам надо будет привести его через unsafe и всё. Вот пример поэлементной инициализации массива без копирования:

doc.rust-lang.org/...​-array-element-by-element

Но мы можем написать функцию, которая проинициализирует указанный указатель так, как нам нужно.

«Так как нам нужно» — то там где нужно/хочется Расту.
При этом, с выделением памяти (вызовом аллок) под капотом, под каждый чих.

Это не тот код, который может показать перфоманс.

Пример с вектором (Vec<T>) не катит, т.к.
«A vector is a densely packed array in memory, and it requires that all its element occupy the same amount of space. The size of the elements needs to be known at compile time. Trait objects don’t have a known size, so you can’t store them in a Vec.»

То есть, вектор объектов (не указателей на объекты, а именно объектов) — таким не создать.
(хотя, размер класса должен быть известен во время компиляции)

Пример с вектором (Vec) не катит, т.к.
„A vector is a densely packed array in memory, and it requires that all its element occupy the same amount of space. The size of the elements needs to be known at compile time. Trait objects don’t have a known size, so you can’t store them in a Vec.”

То есть, вектор объектов (не указателей на объекты, а именно объектов) — таким не создать.

Покажи пример раст кода, который из-за этого ограничения не скомпилируется.

Обсуждение 2020-го года:

„Why does rust need something like placement new”
www.reddit.com/...​thing_like_placement_new

Насколько я понимаю, текущее положение дел такое:
„the order before optimizing is the following:
— Create object.
— Allocate memory.
— Move object.
And swapping step one and two is difficult to the optimizer.”

В общем, не летает. О каком производительном коде тогда, вообще может идти речь?

Мы вернемся к placement new, ты сначала ответь на вопрос: dou.ua/...​sb_comments_forum#2158644

Мы вернемся к placement new, ты сначала ответь на вопрос: dou.ua/...​sb_comments_forum#2158644
Покажи пример раст кода, который из-за этого ограничения не скомпилируется.

Я не любитель раста, т.к. зачем тратить время на хипстерский язык — который сейчас популярен, а через 2 года о нём никто не вспомнит?
Таких языков всегда было дохрена и раст в этом ряду — далеко не первый и не последний.

То, что я видел — выглядело так:

trait Foo { }

pub struct A {}

impl Foo for A {}

fn test() -> Vec<Foo> 
{
    let generic_vec: Vec<Foo> = Vec::new();
    generic_vec.push(A {});
    return generic_vec;
}

Это должно быть, что-то типа плэйсмент нью (и поскольку Vec<Foo> выглядит, как вектор объектов, а не указателей — вероятно, так и есть).
И это не летает.

P.S. Ок, а такое катит?

pub struct A {}

fn test() -> Vec<A> 
{
    let generic_vec: Vec<A> = Vec::new();
    generic_vec.push(A {});
    return generic_vec;
}
Я не любитель раста, т.к. зачем тратить время на хипстерский язык — который сейчас популярен, а через 2 года о нём никто не вспомнит?

Не переживай, у человека, у которого нет времени учить Rust, всегда найдется время, чтоб холиварить о нем.

То, что я видел — выглядело так:
trait Foo { }

pub struct A {}

impl Foo for A {}

fn test() -> Vec<Foo> 
{
    let generic_vec: Vec<Foo> = Vec::new();
    generic_vec.push(A {});
    return generic_vec;
}
Это должно быть, что-то типа плэйсмент нью (и поскольку Vec выглядит, как вектор объектов, а не указателей — вероятно, так и есть).
И это не летает.

Разумеется, не летает. И это не имеет никакого отношения к placement new.

Trait (на русский переводится как «типаж», чтоб тебе было понятнее) — это не объект, это аналог интерфейса из других языков программирования (или абстрактного класса из C++). Он описывает какое поведение реализует структура, но не описывает какие данные в ней находятся. Из-за этого компилятору и вектору неизвестно сколько байт нужно зарезервировать, чтоб сохранить там данные — 0 байт (как в твоем случае), или 10 байт или 100 байт, или 10 килобайт.

В С++ есть такая же проблема, ты не можешь создать std::vector< IFoo > и класть в него экземпляры классов, котоыре реализует IFoo, потому что в векторе есть место только чтоб хранить сам IFoo, который занимает 0 байт.
Вернее, ты можешь, и вызовешь object slicing, со всеми вытекающими последствиями, когда Rust это запрещает на этапе компиляции, чтоб збс.

Если не веришь, можешь показать код на С++, который делает аналогичное, я тебе покажу где в нем косяк.

Не переживай, у человека, у которого нет времени учить Rust, всегда найдется время, чтоб холиварить о нем.

«Учить» — значит, использовать его для реального кода, т.е. в каком-то проекте. С другой стороны, зачем использовать в проекте какую-то хипстерищну-однодневку — когда есть надёжное и работающее.

С хипстерами я периодически сталкиваюсь (т.к. ими забита вся современная индустрия). Тянет такой в проект какой-нибудь пайтон, непонятно зачем — и пишет на нём ахинею, типа b = bytes(item['value'], 'utf-8') где летят эксэпшены и которую приходится править, чтобы работало.

И спрашивается, что челу мешало использовать язык/средства, в которых он флюент — вмеcто того, чтобы тащить в проект непонятно что и непонятно зачем?
То же самое и с растом.

П.С. Я в предыдущем комменте уже дописал кейс без трэйтoв — такое работает?

Выше тебе уже другой ответил оратор, это делается через MaybeUninit.

Для него C компилятор есть? Пишут, что кто-то осилил прогнать через mrustc, сгенерировать аналогичный C код из Rust программы и дальше собрать C компилятором.

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

dou.ua/forums/topic/33788

Я до речі дивився твій код щоб зробити навколо нього інтерфейс типу мапи, щоб можна було щось типу
HArrayMap<string, string> m;

m["string1"] = std::string("string2");
робити, але без хеш-функції з коробки не вийде. І якщо хешувати об’єкти та контролювати час життя ключів та значень — це доволі багато коду.

Упростил тебе задачу.
Добавил методы врапперы:

bool insert(const char* key, uint32 keyLen, uint32 value);
bool getValueByKey(const char* key, uint32 keyLen, uint32& value);
bool hasPartKey(const char* key, uint32 keyLen);
bool delValueByKey(const char* key, uint32 keyLen);

Теперь чтобы передать std::string можно сделать както так.

std::string myKey = "blablabla";

HArray ha;
ha.insert(myKey.c_str(), myKey.length(), 555);

uint32 value;
ha.getValueByKey(myKey.c_str(), myKey.length(), value);

printf("%u", value);

ha.delValueByKey(myKey.c_str(), myKey.length());

Есть 2 варианта.
1. Написать пулл строк, где хранить строки с айдишниками. А в value хранить айдишник строки.
2. Хранить в value напрямую адресс строки (char*)value. Но такой вариант не подходит для 64х битных систем, value пока что 32 бита, поскольку я в основном использую в своем коде пулы и мне 4,2 млрд ключей и велью с головой.

1. Написать пулл строк, где хранить строки с айдишниками

Якщо їх зберігати як просто масив то час пошуку ключа раптом стане O(n) і мапі будеш програвати.

Якщо ж викорстатит ту саму мапу — в чому сенс тоді ще й твій контейнер брати?

2. Хранить в value напрямую адресс строки

Тут дві проблеми:
1. за різними адресами можуть бути ідентичні рядки.
2. рядок за оригінальною адресою може змінитися.

Що робити з типами які не можна просто скопіювати блоком, а треба викликати конструктор?

Не совсем понял.
Ты можешь на самом деле делать даже так

HArray ha;

std::string myKey = "blablabla1";
ha.insert(myKey.c_str(), myKey.length(), 555);

myKey = "blablabla2";
ha.insert(myKey.c_str(), myKey.length(), 555);

myKey = "blablabla3";
ha.insert(myKey.c_str(), myKey.length(), 555);

Итого у тебя в контейнере 3 ключа.
И также извлекать. Поведение такое же как у обычного Dictionary в какой нить джаве или дот нете.

Ти просто конвертував std::sting в char[555]. Таке дале не з усіма типами можна робити, наприклад якщо інкапсульовані вказівники.

Так а контейнер тут причем. Нужно конвертнуть обьект в массив байт, перед тем как добавлять как ключ. Возможно можно прямо с указателями.
Например

struct Bla
{
    int* myValue;
    int* myValue2;
}
Может конвертнуться как ключ в 8 байт. Если ты в одном адрессном пространстве, то вполне себе уникальный ключ.

Якщо є конструктор копіювання то треба викликати його. І деструктор відповідно.

Хто буде робити копії за ось тими вказівниками і хто буде їх звільняти?

Ну Key/Value это аналог индекса в субд. Индекс это отдельная структура для поиска объектов (строк) по определенному ключу. Индекс строится рядом оригинальной структуры (таблица) и не участвует в удалении или создании объектов (строк) в ней.

Все так, але я ж те саме вже кілька разів повторив. Щоб скористатися твоїм контейнером в С++ коді треба:
— написати свою хеш-функцію, можливо для кожного типу даних
— знати як правильно робити копії ключів та значень в/з масиву байтів
— знати коли ключі та значення звільняються, конвертувати їх в правильний тип (інформація про який вже буде втрачена) і викликати деструктор

До того ж щоб просто замінити std::map у найпростішому випадку мені треба буде:
— написати ітератор для кожної можливої комбінації типу ключа та значення
— додати підтримку алокаторів.

Якщо говорити про чистий С то твій контейнер там має більше сенсу, але і порівнювати з мапою тоді не варто — мапа дає набагато більше функціоналу і робить більше.

Давай я как-то доберусь и сделаю value произвольной длины и тогда можно будет повторить полностью интерфейсы std::map.

Ось тут хороші приклади та посилання на документацію про те який мінімум треба зробити для свого stl-like контейнера — stackoverflow.com/...​ng-your-own-stl-container.

не надо так. В map<k,v> нет никаких значений произвольной длины, все значения занимают sizeof(v) байтиков. Посмотри уже наконец, как работает мапа, там несложно

sizeof(v)

Сейчас у меня sizeof(v) всегда 4 байта.
А сделать нужно чтобы можно было велью не только 4 байта записывать.

эх, думал тут про мотоциклы...А тут скукотень для которой и boost’а хватает.

Продолжаем тему с тестированием Артема, где Артем не смог вставить 80 млн ключей.
dou.ua/...​rums/topic/18849/#2044301

Я подебажил код, ожидаемо он упал потому что закончились пулы.
Сделал ресайз пулов динамически и залил изменения в master

На своей машине в твоем тесте я вставил 1.2 миллиарда ключей

По памяти у меня отожрало 18.3 гб.
(Оригинальный размер датасета:
1.2 billion * (4byte key + 4 byte value) = 9.6 гб)
Если у тебя на борту больше, сможешь вставить больше, вплоть до 4 млрд ключей.

Круто. Как только теперь это можно использовать на практике?

Це ідеальний код без багів який перемагає будь-що за будь-яких умов. А на практиці користуйтеся своїм попсовим std::map та іншими недолугими подєлками з тестами, документацією та білд-процесом.

Любой код идеален, пока к нему не добавляют тесты, документацию и билд-процессы.

Любой код идеален, пока

... його не запускають

У меня есть знакомый который работал в конторе которая занимается видеокодеками, писал как раз те самые автоматизированные тесты. Как ты думаешь, как они тестируют свой код ? Да очень просто. У них есть большой корпус не сжатых видео файлов самых разных типов и размеров и они их пропускают их все через видеокодеки, а потом смотрят что получается. Полный цикл их тестирования длится часами. Они не встроены в какието билд степы и тд.
Ровно также как и архиваторы тестируют. Пакуют корпус больших файлов, потом разжимают и смотрят что побитово все совпадает. Понимаешь, никто не пишет такие простые тесты «А что будет если ноль передали в качестве параметра». В этом нет смысла. Для таких проектов, с сложными алгоритмами, это не имеет смысла.

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

Ну и я жду код, который крашит или показывает баги в моей либе. Пока я такого кода не увидел. Но зато ты на каждом углу трезвонишь что «мало тестов есть баги». Что не соответствует действительности.

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

Це інтеграційні та/або E2E тести.

Они не встроены в какието билд степы

А юніт-тести є частиною білд процесу.

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

Ти можеш скільки завгодно розказувати, що багів нема.

Ну и я жду код, который крашит или показывает баги в моей либе

А я чекаю тестів.

Це інтеграційні та/або E2E тести.

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

Ты не согласен ? Ты собрался код архиватора или кей велью тестировать монкей юнит тестами типа а что будет есть неправильный ключ передали ? Твой подход просто не работает. А недостаток квалификации не дает тебе понять почему это не будет работать. Лол.

Коли у тебе є коробка радіодетальок то в процесі збірки радіо з них:
— перевіряємо кожну детальку — юніт-тести
— перевіряємо кожен вузол (блок живлення, антену, підсилювач, ...) - інтеграційні тести
— перевіряємо, що можна покрутивши ручку посунути стрілку на потрібну частосу і почути передачу саме на цій частоті — E2E тести.

Те що ти пропонуєше це зібрати радіо, а коли щось не працює то лізти перевіряти кожну детальку. Що і дорого, і довго, і показує незрілість процесів.

— перевіряємо кожну детальку — юніт-тести
— перевіряємо кожен вузол (блок живлення, антену, підсилювач, ...) - інтеграційні тести
— перевіряємо, що можна покрутивши ручку посунути стрілку на потрібну частосу і почути передачу саме на цій частоті — E2E тести.

Ну отличный пример. Тебе показывают радио, которое работает, ловит в жмеринке австралийские радиостанции, а ты кричишь что в этом радио тебе не хватает проверки того как работают транзисторы. И на основе этого делаешь глубокомысленный вывод что «либа сырая без тестов». Тебе самому не смешно ? Тебе показывают рабочуют либу которая прошла все E2E тесты, на загрузке миллиардов ключей, что по сути является сертификацией ее качества. А ты предлагаешь тестирование отдельных резисторов, транзисторов и диодов. Ты натестируешь, все по отдельности будет работать, а вместе не будет работать. В этом нет никакого смысла. Тебе надо, можешь добавить такие тесты, я апрувну пулл реквест, но в моем понимании это пустая трата времени.

Тебе показывают радио

Твоя ліба в найкращому випадку вузол. Сама по собі вона нічого не робить і має бути використана в реальній програмі щоб мати для мене користь. І цілком нормально очікувати, що був хоч якийсь контроль якості і відповідності заявленим характеристикам.

вывод что «либа сырая без тестов»

Ліба не викликає довіри і не має сенсу дивитися на неї доки не буде тестів.

Тебе показывают рабочуют либу которая прошла все E2E тесты

Де ці тести?

А ты предлагаешь тестирование отдельных резисторов, транзисторов и диодов.

Так, мені потрібні гарантії того, що базові компоненти належної якості і мають заявлену поведінку.

В этом нет никакого смысла.

В цьому лише сенс і є. Брати непойми що у використання, без тестів та документації — який в цьому сенс?

Тебе надо, можешь добавить такие тесты

Тобі треба щоб я серйозно сприймав твою лібу і спробував її використовувати — ти добавляй тести.

E2E тест имеет наивысшую ценность. Он показывает что продукт работает, не отдельные компоненты его, а весь продукт работает так как надо. Все части согласованы в своей работе.
Е2Е тест для контейнера, это вставка большого количества ключей и их правильное извлечение и удаление.
Нагрузочные тесты в 1600 строчек кода которые тестируют три метода insert/get/delete ты можешь найти в функции main.
Ты можешь запустить эти тесты. Можешь написать свои тесты и взять свои сценарии использования. Известных багов на сейчас — нет. Хотя сценарии использования запредельные, превысили миллиард ключей.

E2E тест имеет наивысшую ценность.

Вартість, а не цінність. Бо коли щось, що можна було зловити на етапі білду ловить E2E — це дуже дорого, з великим відставання і під час роботи над іншою вже задачою.

Известных багов на сейчас — нет.

За відсутності тестів так завжди буває.

Вартість, а не цінність. Бо коли щось, що можна було зловити на етапі білду ловить E2E — це дуже дорого, з великим відставання і під час роботи над іншою вже задачою.

Мне не дорого. Мне нормально. Кейс Артема я пофиксил за минут 15 и даже не залазя в код написал что пул закончился.
Любой баг в своем алгоритме я фикшу не более 2х часов. Мне главное найти сценарий, где мой код не отработает. И именно Е2Е тест наиболее замороченный и эффективный для выявления багов.
А юниттесты в моем кейсе (не в других проектах) почти бесполезны.

Мне не дорого. Мне нормально.

Але ж ти намагаєшся продати свою лібу не лише собі. Відповідно і виникають питання про відповідність заявленого реальності.

Я никому ничего не продаю. И даже не собираю пожертвования. Я просто говорю что я написал достаточно революционный алгоритм и подкрепил его открытым кодом, Е2Е нагрузочными тестами и гарантией отсутствия багов. В случае наличия багов (а если они не обнаружились при работе с миллиардом ключей в контейнере, то в обычном кейсе на неск миллионов ключей и говорить неочем) я пофикшу их очень быстро.

Я никому ничего не продаю

«Продаю» тут в сенсі не заробляння грошей, а пропозиції іншим скористатися твоїм кодом. Бо інакше для чого ця тема?

Дуже легко зробити репо з випадковим кодом і без тестів, а потім казати, що тести не потрібні і все ідеально — бо гарантія.

Е2Е нагрузочными тестами

Де покриття коду можна подивитися?

гарантией отсутствия багов

Як перевірити цю гарантію. На слово вірити не буду. Які тести можна запустити і побачити, що код робить те, що від нього очікують?

Які тести можна запустити і побачити, що код робить те, що від нього очікують?

Запускаешь проект и ждёшь минут 15 прохождения всех тестов.

Запускаешь проект

Що це словосполучення означає?

У тебе там написано Windows & Linux. Ок:

git clone github.com/Bazist/HArray.git
cd HArray
make

вгадай що далі.

Мейк файл вроде как чинил. Специально Линукс машину для этого искал чтобы потестировать. Не сбилдидось ?

На вінді:

> nmake
NMAKE : fatal error U1064: MAKEFILE not found and no target specified
Stop.

На лінуксі:

$make
make: *** No targets specified and no makefile found.  Stop.

Так вот мейкфайл
github.com/...​ob/master/HArray/makefile

Ты в правильной директории make запускаешь ?

Ты в правильной директории make запускаешь ?

Чітко слідую інструкціям в документації.

Ок, скорей в твоём случае

git clone github.com/Bazist/HArray.git
cd HArray/HArray
make

Тобто від документації могла б бути якась користь?

Ок, а як щодо купи варнінгів в «ідеальному коді»? — pastebin.com/mcrWHkVD

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

Да и смотрю ворнинги в основном ругаются на дебажные printf

Ворнинги ничего не значат в данном случае

Відсутність тестів теж нічого не означає. Як і відсутність документації. Та і взагалі може не компілятися — це мало що значить, код же ідеальний. Ось і гарантія.

Корректность кода тестируют здесь более основательными методами

Тобто ніякими.

Ну і для чого такий коди без тестів, без документації та ще й з варнінгами? Ти за той час поки намагаєшся мене переконати в ідеальності свого коду вже давно міг покриття хоча б 70% зробити. І не на словах, а прямо в репорті покриття показати — ось воно.

Код идеальный багов нет, потому что те драконовские нагрузочные тесты с кучей разных проверок все давным давно повычищали. Чай не автопилот теслы тестируем, а простой контейнер для ключей. Он покрыт тестами на 100% вдоль и поперек.

Код идеальный багов нет

Але це не точно — нема ніяких тестів щоб це підтвердити.

Он покрыт тестами на 100%

Але це не точно — репорт з покриттям відсутній.

та ще й з варнінгами

Ты бы те варнинги почитал хотябы. На printf ругается. Очень смешно.

Ты бы те варнинги почитал хотябы.

На даному етапі мені достатньо того що вони є. Після цього вірити в те що «код ідеальний» якось не раціонально.

Ты бы те варнинги почитал хотябы.

Та хоч на scanf — компілятор тобі явно каже, що твій код не ідеальний як мінімум.

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

Как бы не имеет. Это тест, в котором под капотом десятки или даже сотни компонентов, который показывает pass/fail сигнал. Если pass — все збс. Если fail — хуево, и чо теперь с этим делать? Надо проверять компоненты по отдельности и разбираться какой именно из них косячит, сейчас посмотирм тесты более низкого уровня, oh shit...!

Полный цикл их тестирования длится часами.

Вот когда нет юнит тестов, циклы тестирования и занимают часы и даже недели в случае если это ручное тестирование. Юнит тесты должны выполняться за считанные минуты (и тут счёт на тысячи тестов будет).

Но ты прав в одном — end-to-end тест с правильными данными способен покрыть 100% кода, если конечно в коде нет сложных превентивных проверок на например инъекции в данные.

Но ты прав в одном — end-to-end тест с правильными данными способен покрыть 100% кода, если конечно в коде нет сложных превентивных проверок на например инъекции в данные.

Именно так и есть. Только таким тестам можно доверять. Юнит тесты, да, можно добавить просто как демонстрация какой-то функциональности, но не более.

Юнит тесты, да, можно добавить просто как демонстрация какой-то функциональности

Ти схоже просто не розумієш для чого потрібні юніт-тести. Бо сказане звучить як «компіляцію можна додати як демонстрацію, але не більше».

потрібні юніт-тести.

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

Я тебе уже сказал как тестируют видеокодеки и архиваторы

А я тобі сказав чому не варто витрачати час на лібу у якої навіть юніт-тестів нема.

Пойди продай им свои юниттесты.

Для чого це мені? У них є продукт який задовольняє, або ні мої вимоги як користувача. Як вони це роблять там у себе і чи тестують взагалі мене не хвилює.

Але ж ти намагаєшся продати не продукт, а код, лібу навколо якої треба ще буде писати продукт. І відповідно виникає питання які гарантії якості, де хоча б тести і покриття?

кадр который сделает упор на простенькие юнитесты, никогда не напишет и не отладит такой сложный проект.

Зі «складним проектом» ти сильно вперед забігаєш. Спочатку хоча б юніт-тести додай.

Зі «складним проектом» ти сильно вперед забігаєш. Спочатку хоча б юніт-тести додай

Ну ты человека который собрал работающее полностью радио пытаешься убедить сидеть с амперметром и чекать резисторы, диоды и транзисторы что они работают. Зачем ? Если радио работает в самых замороченных сценариях очевидно же что все его мелкие части тоже работают как надо.

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

Так, перевірити усі елементи до того як з них збирати вузли, не кажучи вже про усе рішення — це лише логічно і економить час та зусилля.

Для себе можеш робити як хочеш, але якщо плануєш мене зацікавити використовувати свій код то маєш показати тести і покриття хоча б.

радио работает в самых замороченных сценариях очевидно же что все его мелкие части тоже работают как надо

У тебе не радіо, а усього лише один з його елементів. Сама по собі твоя ліба не дає ніякої цінності користувачам доки навколо неї не написано код програми. А мені щоб використати твій компонент потрібні гарантії роботи відповідно заявленим характеристикам.

Ти ж пропонуєш зібрати радіо з твоїм компонентом і потім перевіряти чи працює воно, а як ні — лише тоді перевіряти твій компонент. Усе якось догори ногами і в самий затратний спосіб.

Ти ж пропонуєш зібрати радіо з твоїм компонентом і потім перевіряти чи працює воно, а як ні — лише тоді перевіряти твій компонент. Усе якось догори ногами і в самий затратний спосіб.

А ты как хотел ? Если у нас на работе хотят использовать Редис, то запихивают его в наш сценарий использования, именно с нашими данными и смотрят как он себя ведёт. С какой скоростью работает.
Я могу лишь гарантировать что мой код корректно работает на всех моих нагрузочных сценариях и известных багов не обнаружено, даже если вставляли сотни миллионов и даже миллиард ключей.

у нас на работе хотят использовать Редис

Продукт з багатьма відомими випадками використання, з документацією та підтримкою. Не соромся вже, порівнюй свою лібу з віндою чи лінуксом, там теж мабуть тестів не пишуть через свою крутість (ні).

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

А, так у тебе ліба спеціально лише для гарантованих тобою сценаріїв. Якісь інші дані чи послідовність операцій і все, гарантія втрачається?

А, так у тебе ліба спеціально лише для гарантованих тобою сценаріїв. Якісь інші дані чи послідовність операцій і все, гарантія втрачається?

Дело в том, что контейнер по своей сути достаточно прост для тестирования. Он даже не многопоточный. Просто пишешь ключ и велью и читаешь. Не понимаю почему ты такую проблему раздул. Например DniproDB это полноценная база данных, там багов много, есть ограничения, ее тяжело тестировать. Сценариев много использования, многопоточность и вот это вот все.
Но key/value это самая надёжная часть. Она действительно без багов и я в ней уверен.

контейнер по своей сути достаточно прост для тестирования

І де тести?

Не понимаю почему ты такую проблему раздул

Тому що є певний когнітивний дисонанс коли хтось стверджує про ідеальний код без багів і в той же час не може зрозуміти для чого потрібні юніт-тести.

і в той же час не може зрозуміти для чого потрібні юніт-тести.

Так ты же сам расписал эволюцию тестов.
Самое простое пройти юнит тесты.
Сложнее интеграционные.
И самое сложное Е2Е.

Я пропустил юнит тесты потому что они ровно нихрена толком в моем случае не выявят. Но выявит тяжёлая артиллерия вроде интеграционных или е2е, типа чекать контрольные суммы, лить ключи до аут оф мемори, лить ключи самой разной природы и длины, чекать каждый вставленный ключ и тд.

Так ты же сам расписал эволюцию тестов.

Яка ще еволюція? Я тобі розписав для чого потрібні види тестів які використовують найчастіше.

Я пропустил юнит тесты потому что они ровно нихрена толком в моем случае не выявят

Крім випадків коли виявлять і не треба буде дебажити код щоб знайти елементарну помилку чи тайпо.

Крім випадків коли виявлять і не треба буде дебажити код щоб знайти елементарну помилку чи тайпо.

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

Элементарных помилок там уже давно не осталось

Це треба довести.

Будем руководствоваться презумкцией невиновности. Багов нет до тех пор пока не доказано обратное.

:D

Тоді і правда будь-який код без документації та тестів є ідеальним та без багів.

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

Ты занимаешься тем что выдумываешь себе проблемы. Ворнинги, тесты не такие, документация не такая на контейнер с тремя методами и тд. А что если контейнер у тебя не будет работать. У меня работает на миллиарде, а у тебя наверно план 50 млрд ключей вкачать.

Короче не занимай время, я спать.

Розумієш, ти прийшов продавати свій «ідеальний код без багів», а коли до нього виникли питання почав вигадувати виправдання замість виправити. За той час, що ти намагаєшся довести, що юніт-тести чи документація не потрібні ти міг би їх вже написати.

І я особисто не бачу ніякого сенсу навіть пробувати користуватися лібою в якій мало того, що відсутні тести та документація, так ще і автор на всі вказані проблеми доводить що вони не важливі.

Навіть уявимо хтось ризикнув твоїм кодом скористатися, включив його в свій білд. Бац — варнінги, білд падає. Всьо, на цьому твого «ідеального» коду позбуваються і забувають про нього.

Я до речі дивився твій код щоб зробити навколо нього інтерфейс типу мапи, щоб можна було щось типу

HArrayMap<string, string> m;

m["string1"] = std::string("string2");

робити, але без хеш-функції з коробки не вийде. І якщо хешувати об’єкти та контролювати час життя ключів та значень — це доволі багато коду.

Але маючи таке можна було б вже порівнювати на тих сценаріях де мапу та інші колекції використовують.

але без хеш-функції з коробки не вийде

А зачем хешфункция, если HArray не требует хешфункций ? В этом его фишка, он сортирует и упаковывает ключи без всяких хешей, что является предметом нестабильности в хештаблицах (коллизии).

Можно сделать конвертацию как-то так. Правда строка должна быть выровнена по 4м байтам.
std::string str = «bla bla bla»;
uint32*key = (uint32*)str.c_str();

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

Если я оберну твой harray в некий ipc процесс, сделаю маршаллинг для выборки ключей (для потоко защищённости и множества клиентов), то так как

uint32*key = (uint32*)str.c_str();

Ключ у тебя поинтер на сырые данные, и каждый новый запрос будет аллоцировать вычитанные из сокета ключи в новое место в памяти — harray не сможет детерминированно вычитать ключ foo с разных запросов?

Не совсем понял схему. HArray нужно передать три значения
поинтер на ключ uint32*, длину ключа и велью. И он прочитает все данные с этого поинтера и вставит в контейнер.

Не совсем понял схему. HArray нужно передать три значения
поинтер на ключ uint32*, длину ключа и велью. И он прочитает все данные с этого поинтера и вставит в контейнер.

Я еще не разбирался с твоим проектом построчно =)
Но если есть два ключа
std::string key1="foo"
std::string key2="foo"

Они идентичны? Даже если c_str() указывает на разные «foo» ?

Да. Контейнер копирует ключ и проверяет дубликаты. Если это дубликат ключа, то велью апдейтится.

Контейнер копирует ключ и проверяет дубликаты

Як він це робить якщо у нього нема інформації про тип ключа, а відповідно і про те як правильно зробити копію. Наприклад у мене ключем буде наступний тип:

struct key {
   void* pv;
   char* pc;
   ...
};

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

Я копирую массив байт

В С++ цього не достатньо. Я там спеціально написав вказівники. Тобто мені ще треба буде вручну робити копії усіх об’єктів всіх можливих типів.

Але навіть не це найгірше. Як ти будеш викликати деструктор для «масиву байт»? Ось ті вказівники які для твого коду насправді байти є адресами пам’ять за якими треба звільнити.

Не совсем понял.
Ты мне передал допустим обьект как ключ 64 байт к примеру.
Я их себе в контейнер скопировал. После того как ты ключ из контейнера удалил, я в контейнере 64 байт удалил.

Ты мне передал допустим обьект как ключ 64 байт к примеру.
Я их себе в контейнер скопировал.

Деякі з тих байтів були вказівниками чи вкладеними об’єктами які треба правильно копіювати.

После того как ты ключ из контейнера удалил, я в контейнере 64 байт удалил.

І проігнорував деструктор типу, не звільнив пам’ять.

А зачем хешфункция

для того щоб наступне працювало:

sting s1 = "key1", s2 = "key1";

if (m[s1] == m[s2]) {...}

А з твоїм кодом мені треба:
— написати свою хеш-функцію
— десь зберігати ключі
— десь зберігати значення
— відстежувати час життя ключів та значень

Мапа та інші контейнери все це роблять з коробки.

Не совсем понятно. Этим кодом ты будешь сравнивать values

m[s1] == m[s2]

Если ты написал простинький пул, где велью это айди строк в этом пуле, то никаких проблем писать такой код нет.

Если ты написал простинький пул, где велью это айди строк в этом пуле,

Поки забудемо про те що мені ще й «простенький пул» писати треба буде і спитаю — як цей пул організувати? Просто масивом/списком, чи може std::map використати?

Убрал все Warnings. Можно забирать master.

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

ПС: По ходу дела допустил одну очепятку и тесты это мигом выявили, исправил.

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

Можно уточнить в каких проектах?

В 2 моих проектах (полнотекстовый движок и документоориентированная субд)
и еще пару человек мне писало по имейлу, спрашивало что да как.

А где используются сии поделия, в каких продуктах?

Наконецто. А почему ты пятницу пропустил ?

Сделал ресайз пулов динамически и залил изменения в master

І тест додав який підтверджує, що тепер не буде крешитися за таких умов?

Добавлять тест на вставку 1,2 млрд ключей ?
А у std::map такой тест например есть ?
Потому что у меня на таком обьеме он крашится и виснет.

Добавлять тест на вставку 1,2 млрд ключей ?

Як інтеграційний тест — чому б і ні?

А у std::map такой тест например есть ?

Я тобі вже показував де подивитися які юніт-тести є для мапи.

Як інтеграційний тест — чому б і ні?

И что это даст ? А если у когото память закончится ? И почему именно 1,2 млрд ключей. 2 млрд я не смог вставить, у меня на ноутбуке память закончилась. Может лучше 8 или 16 млрд ключей ? Чтобы каждый юзер кричал что моя либа крашится, не разобравшись про аут оф мемори эксепшин в тестах ?

И что это даст ?

Це дасть підтвердження того, що код працює як і до змін.

А если у когото память закончится ?

У кого це «кого-то»?

И почему именно 1,2 млрд ключей.

Не знаю чому ти саме таку кількість запропонував.

Может лучше 8 или 16 млрд ключей ?

Може і краще. Ти як автор тесту маєш розуміти який саме сценарій перевіряєш.

Потому что у меня на таком обьеме он крашится и виснет.

А ты эксэпшены ловишь?

Ловлю, но в этом мало смысла. Это Fatal Error который по хорошему приведет к перегрузке приложения. (пример с out of memory, если память закончилась, то делать уже ничего не получится)

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

Добро пожаловать на СУбд-строительные верфи. Господин Прокофьев пока не подтвердил свою подписку на следующую пятницу. Ты ещё можешь успеть запрыгнуть на алтарь.

реализует весьма сложные Trie структуры данных и топчет вот эти вот эти ваши самые реализации ассоциативных массивов std::map, glib, dictionary.net и прочью заморскую попсу в разы, а то и на порядок.

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

автор, без злобы, желаю тебе вылечиться и поучиться хоть немного.

и серьёзно в реализации trie не может быть ничего крутого. это структура данных на реализацию которой в универе 10 минут давали

Он регулярно лечится водичкой, но видать вода не живая, а мертвая :-)

Мде. Если в эмигосрачах у тебя ещё был шанс пресмыкаться из под табуретки, то в техническом топике просто проедуться катком по твоей тонкой вайтишной натуре )

Это опять какая-то дичь про лабрадора??? :-)

візьмем цю моду винесення в топчік
ти дорікаєш std::map за відсутність

6. Сохранятся на диск на уровне скорости работы дисковой системы — не умеет

і відповідно вихваляєшся наявністю цього в тебе
dou.ua/...​rums/topic/18849/#2136000

Якщо оце та геніальна функція збереження github.com/...​ster/HArray/HArray.h#L220 —

Велью фиксировано действительно 4 байтами, потому что чаще всего это поинтер на объект.

то скажи, будь-ласка, яка користь із файла з поінтерами на об’єкти, стрічки, будь-що, якщо це поінтери. Де збережені дані?

Вы просто не понимаете рассовое превосходство моего алгоритма. Это просто другой уровень, чем гавеные деревья и хештаблицы. И прежде всего даже не по скорости, а по функциональности.

«ві нє понімаєтє, єто другоє»

6. Сохранятся на диск на уровне скорости работы дисковой системы — не умеет

Ну вообще надо постараться, чтоб сохранаться на диск медленнее скорости работы дисковой системы.

Мне это удается, поскольку я сбрасываю на диск готовые пейджи скопом. Если у тебя какая-то говноструктура, которая представлена миллионом мелких объектов в графе который ещё нужно обойти, то твоя структура нихера не оптимизирована для работы с диском. Мой же контейнер сериализируется/десериализируется на уровне 100 мб/сек с обычным шпиндельный диском.

Мой же контейнер сериализируется/десериализируется на уровне 100 мб/сек с обычным шпиндельный диском.

Ты сейчас хвастаешься или жалуешься?

Конечно хвастаюсь. У меня готовые мегабайтные страницы памяти пишутся на диск. И также читаются. Получить такое в обычной мапе или хештаблице совсем не просто. Собственно поэтому они и не умеют сбрасываться и подыматься с диска на максимальной скорости винчестера.

то скажи, будь-ласка, яка користь із файла з поінтерами на об’єкти

Я написал на HArray два движка СУБД, которые работают с диском.
В качестве value сохраняется offset в файле.

Сама по себе твоя идея переложить сериализацию на контейнер черевата. Ты никогда не сможешь решить общий случай сериализации объекта, со всеми вложеностями, циклическими ссылками и тд. Это не тривиальная задача. В дотнете есть мембервайсклон. Но и он нихера не работает, а бежит по верхам. Потому мне твой бомбеж на счёт велью не понятен.
Ты пытаешься решить задачу которая за скобками Кей велью контейнера

Сама по себе твоя идея переложить сериализацию на контейнер черевата. Ты никогда не сможешь решить общий случай сериализации объекта, со всеми вложеностями, циклическими ссылками и тд. Это не тривиальная задача. В дотнете есть мембервайсклон. Но и он нихера не работает, а бежит по верхам. Потому мне твой бомбеж на счёт велью не понятен.
Ты пытаешься решить задачу которая за скобками Кей велью контейнера

«а как дисал, а как дисал»

зверху в топіку

Легендарный супероптимизированый алгоритм, который реализует весьма сложные Trie структуры данных и топчет вот эти вот эти ваши самые реализации ассоциативных массивов std::map, glib, dictionary.net и прочью заморскую попсу в разы, а то и на порядок.

Ты услышал что тебе написали ?
Как ты в дикшинари собрался сериализовать например объекты с циклическими ссылками, а потом десериализовать чтобы все встало в памяти как надо автоматом ?

Ты услышал что тебе написали ?
Как ты в дикшинари собрался сериализовать например объекты с циклическими ссылками, а потом десериализовать чтобы все встало в памяти как надо автоматом ?

а ти побачив чим ти хвалишся і що насправді у тебе?

Ты приписываешь дикшинари и мапам функциональность, которую они _впринципе_ не могут реализовать правильно. Кстате это хороший был бы вопрос на собеседование, узнать у кандидата почему сериализовать десериализовать объекты в общем случае нифига не тривиальная задача. Думаю всяких профнепригодных слоупоков можно было бы с лёгкостью отсеивать. О таком в этих ваших литкодах не напишут. А теория графов тут просто кричит

Ты приписываешь дикшинари и мапам функциональность, которую они _впринципе_ не могут реализовать правильно.

serde.rs
Out of the box, Serde is able to serialize and deserialize common Rust data types in any of the above formats. For example String, &str, usize, Vec, HashMap are all supported. In addition, Serde provides a derive macro to generate serialization implementations for structs in your own program.

common Это примитивные типы. Они мне нахер не нужны в субд. А ты реализуй в общем случае, чтоб любой объект. Пример с циклическими ссылками я приводил.

common Это примитивные типы.

serde вполне работает с композитными типами

Пример с циклическими ссылками я приводил.

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

Потому что я не вижу смысла это реализовывать как половинчатое решение. А в всяких дикшинари и мапах оно именно так и работает. Вплоть до того что мы сериализовать ниче не будем пока не заимплементите сами функцию как ваш объект правильно сериализовать. Если так, то какая разница где его сериализовать. И зачем это делегировать мапе.

И зачем это делегировать мапе.

Это хороший вопрос. Зачем сувать всю возможную функциональность в один класс? Есть такая штука как single responsibility principle. Один класс отвечает за сериализацию, другой за эфективное хранение данных в памяти и организацию доступа к нему и т.п.

Вплоть до того что мы сериализовать ниче не будем пока не заимплементите сами функцию как ваш объект правильно сериализовать.

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

Кстате кинь ссылку на исходники функции которая сериализирует хешмап в расте.
Если там сбрасываются готовые страницы (для этого там должен быть рукопашный менегер памяти) то Ок, если там обходят циклопический граф и сериализирует элементы по одному то тормознутая академическая имплементация.

Кстате кинь ссылку на исходники функции которая сериализирует хешмап в расте.

github.com/...​rde/src/ser/impls.rs#L374

Если там сбрасываются готовые страницы (для этого там должен быть рукопашный менегер памяти)

Тебе для этих целей не нужен рукопашный «менегер памяти», тебе нужен memory-mapped file.
У тебя этого, разумеется, нет, ты просто открываешь файл через fopen и фигачишь туда свои внутреннее представление данных.

если там обходят циклопический граф и сериализирует элементы по одному то тормознутая академическая имплементация.

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

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

Это Артем ошибся примерно на два или три порядка. Обход десятков миллионов объектов разбросанных по памяти в классическом академическом варианте Node(Parent) может быть очень и очень больно. На счёт SSD немного не согласен, не обязательное условие. SSD будет выигрывать прежде всего за счёт отсутствия позиционирования механической головки. Но если мы в лоб пишем гигабайты ровно по дорожке диска, то там скорость на обычном шпиндельном диске может достигать до 500мб/сек. Именно с такой (Макс) скоростью HArray весь сериализируется и десериализируется с диска. Что очень удобно для старта СУБД, она просто подымает страницы памяти с диска в рам, не вставляя элементы по одному в контейнер по новой.
И здесь же элементарно реализуется уже известный LRU, ибо отслеживать какие нужны страницы в рам а какие лучше вытеснить на диск тоже очень просто.

Обход десятков миллионов объектов разбросанных по памяти в классическом академическом варианте Node(Parent) может быть очень и очень больно.

Если твоя задача это сериализация хеш структуры, то в мапу подставляется свой аллокатор который выделяет память под ноды из своих собственных «страниц» памяти из адресного пространства процесса, и дальше эти страницы можно дампить на диск как хочется через fwrite. Если имеет значение порядок данных, то есть некая связанность — это тоже в аллокаторе можно разрулить (грубо говоря где выделять место под ноду)

Ok, допустим записать страницы тебе удастся. Прочитать их как ? Как сказать стандартной мапе что вставлять по новой ничего не надо. Используй уже готовые десериализированные страницы памяти.

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

. Но если мы в лоб пишем гигабайты ровно по дорожке диска, то там скорость на обычном шпиндельном диске может достигать до 500мб/се

Да ладно!
с хардваре видимо знаком по наслышке ?

Одиночный HDD 7200 пишет 250MB/s на внешних дорожках в лучшем случае. На внутренних скорость падает вдвое.
То есть в среднем диск будет выдавать 160MB/s
и это в идеальных условиях.
например www.ixbt.com/...​exos-x18-18tb-review.html

Да ладно!
с хардваре видимо знаком по наслышке ?

ні, просто бенчмаркає у вакуумі, без зливання кешів

Ждал ответа про о enterprise 10/15k rpm, но видимо и так достаточно lol

В Дельфі колись серіалізація-десеріалізація компонент на формах (а потім і датамодулях) була зроблена. І навіть працювала.

Про серіалізацію підграфу об’єктів я диплом писав :)

Дауж, мысли в слух. На самом деле этот топик не о супер оптимизированных алгоритмах, а о человеческой психологии. Я не являюсь экспертом в большом количестве компутер сцаинц технологий. Мне нечего сказать человеку который написал крутую нейросеть, например. Но почему-то другие люди, приходят в этот топик и пытаются показать свою крутую экспертизу и непременно через несколько сообщений садятся в лужу.
Дружище, каким бы ты не был спецом, литкодовцем, топ архитектором, миллионером и просто хорошим человеком пойми. Есть области где ты не шаришь и тебя ждёт фиаско.
Поэтому впредь, если у тебя нет признанных собственноручных крутых реализаций хотябы хештаблиц, других очень сложных структур данных, движков баз данных, не трать мое и свое время. И не подымай эту тему.
Спасибо.

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

Перше — «визнаність» твоєї «крутої реалізації» дещо надумана. Знають її лише на тих ресурсах де ти сам її піарив, та і то знають більше через твій стиль спілкування, а не через крутість реалізації.

Друге — не треба бути автором «крутих реалізацій» щоб задавати питання. А питання до твого коду є — чому він не компілиться без ворнінгів, чому крешиться, чому в нього треба лазити руками кожного разу коли треба щось «оптимізувати», чому розкидані магічні значення, ...

Третє — ти перший почав «піднімати цю тему» та «витрачати час» і мав би бути елементарно вдячним за те, що люди витрачають час і дивляться на твій код. І не просто дивляться, а знаходять проблеми, задають питання по темі та висловлюють сумніви.

И не подымай эту тему.

Після того як ти припиниш розказувати нісенітниці про ідеальний код та те як твоя реалізація удєлує мепи та хеш-таблиці.

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

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

з тобою через твою геніальність напевне в тімі ніхто не працює :-), ти сам собі тім

У порядних конторах про косметику тебе просто засміють.
Твій код може бути геніальним (на самом деле нет), але при PR review там є банальні, автоматичні, жесточайші і бездушні automatic checks.
1. компілюється з warnings — до побачення, помилка, приходь, коли пофіксаєш
2. cyclomatic code complexity check — функція на 1300 рядочків — до побачення, помилка, приходь, коли пофіксаєш
3. security check — лазаєш по пам’яті грязними ручонками, конвертуєш int/pointer направо і наліво — будь любєзєн, внеси ці зауваження в exception/ignore list (ну, тобто всю твою програму) — до побачення, помилка, приходь, коли пофіксаєш
і т.д.

І це ще до того, як колеги почнуть твій код розглядати.

Почему я и сказал что ты формошлеп. Работаешь по хомячковым шаблонам своего Лида. Мне пох* на хомячковые стандарты. Я буду использовать гоуту, длинные функции и прочий арсенал настоящего джедая который пишет алгоритмы уровня кернела.
Для галеры я пишу код который проходит все ревьювы и стандарты. Это делать проще чем писать действительно крутой оптимизированный код.
И такому глупому хомячку как ты этот скил недоступен от слова совсем.

Почему я и сказал что ты формошлеп. Работаешь по хомячковым шаблонам своего Лида. Мне пох* на хомячковые стандарты. Я буду использовать гоуту, длинные функции и прочий арсенал настоящего джедая который пишет алгоритмы уровня кернела.
Для галеры я пишу код который проходит все ревьювы и стандарты. Это делать проще чем писать действительно крутой оптимизированный код.
И такому глупому хомячку как ты этот скил недоступен от слова совсем.

це все adhominem і мимо каси, ліда блін, бггг

хомячковиє стандарти, бггг

«алгоритмы уровня кернела» — ти хоч кернел бачив (Windows/Linux)? Тебе би Linus змішав з гівном, або просто проігнорив би за такий код

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

Я сам код «рівня кернела» не писав, писав навколо нього, але довелося його побачити і навіть трошки подебажити у певній кількості (Windows 7/8). І код той написано чисто (з використанням SAL — docs.microsoft.com/...​quality/understanding-sal) і компілиться він без варнінгів. І покрито його тестами теж дуже добре.

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

Якби не хочеться переходити на особистості, але ти переоцінюєш свою експертність та унікальність.

Код чого тобі показати? Це ж не я в цьому топіку розказую про ідеальність свого коду.

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

Именно так. Есть реализация, есть о чем говорить. Есть экспертиза. Нет реализации — давай досвидания.

Я рассказываю про идеальность своего кода, поскольку он хорошо работает

Варнінги при компіляції, segfault під час робити та необхідність ручних правок просто для того щоб зберігати дані іншого розміру — це що завгодно, але не ідеальний коди і не код який добре працює.

segfault під час робити

Последний сегфолт я видел когда память закончилась, когда пытались вкачать 300 миллионов ключей. Вот бросал ссылку на машинках помощнее вкачивали миллиард ключей без сегфолтов.
Причем на таких объемах всякие стдмапы и денсы дохнут как мухи, но не мой алгоритм. Ибо ему пох* на коллизии он создан на запредельные объемы данных.

Це круто, але історії лишаються історіями. І доки у тебе не буде тестів та прикладів використання вірити їм буде не кожен.

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

Хуцпа

«Хуцпа» — определяется как «особо циничная, подлая, наглая ложь», «верх цинизма и наглости, парализующий оппонента».
Другие определения, которыми часто обозначают понятие «хуцпа», — сверхнаглость, бессовестность, бесцеремонность, нахальство, хамство, нетерпимость по отношению к другим, дерзкое и наглое лицемерие. Часто эти определения употребляют с приставкой «сверх-» и другими словами, подчеркивающими превышение всяких норм и выход за рамки установленного: «сверхнаглость», «суперложь», «экстраординарная наглость», «необыкновенное нахальство», «неслыханное вранье», «невиданная дерзость», «запредельная бесстыжесть», «небывалая бесчестность» и так далее.
...
Американские судьи Алекс Козински и Юджин Волок приводят объяснение употребления этого слова в английском языке на примере анекдота: «Юноша, который убил обоих родителей, чтобы получить наследство, в суде просит о помиловании, ссылаясь на то, что он круглый сирота».

===
по решті пунктів Oleksandr Golovatyi сказав нижче — dou.ua/...​rums/topic/18849/#2135965

Аффтор, а ты случайно раньше не зажигал на sql.ru в ветке ПТ?
уж больно ник и слог знакомый

и на sql.ru и на ixbt жег напалмом под ником bazist.

точно, помню что на ПТ был базист (в линке аффтора на гитхаб увидел bazist и сразу вспомнил) и тоже всякую дичь нес
я вот хотел проверить свою мысль и зашел на sql.ru — выяснилось что ПТ уже почил в бозе, не выдержал бедняга срачей :)))

да ну, там же вменяемое сообщество, гениев не приемлют :)))

Похоже мы все в колбасных топиках имели дело с проффесиональным троллем ))

из него тролль как известно из чего пуля. Он искренне верит в свои поделки.

Это и есть искусство быть троллем — на серьёзных щщах задвигать всякую чушь и убедить всех что ты сам в неё веришь. :))

Это «чушь» работает. Так что пецтеть можно что угодно, но на гите все есть и запускается ровно в 2 клика.
И после этого все вопросы кто тролль, а кто дело говорит, моментально отпадают.

тут увы другйо случай: для троллинга несколько лет педалить какую то говноподелку — чересчур.

Так я не понял. Ты в очередь на жертвоприношение величайшим алгоритмам становится будешь ?
Если честно, для меня шкурка галерного архитектора наименее ценна. Все знают что нормальный архитектор грамотно борется с сложностью в проекте, а галерный архитектор наоборот, вносит максимальное количество своей глупости, чтобы раздуть проект до максимально возможных сроков. Как по штату сотрудников, так и по срокам реализации.

:) бомбеж оценил. Но по сути то есть что сказать? За 5 лет получилось внедрить свою поделку хоть куда то, хоть в приватбанк продать?

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

вопросов больше нет :)))

Да я. Но нужно учитывать что оба ресурса российские.
И на обоих ко мне отношение было предвзято политическое.
Особенно на

ixbt

где в технических темах
я общался с отморозками которые спонсируют ДНР/ЛНР.
Именно поэтому я ушел с обоих этих форумов.

Шо опять? Там ошибки в коде, автора кто только(в том числе и я немного) ссаными тряпками не гонял :)

Ты немного опоздал. Для своих жертвоприношений самым совершенным алгоритмам я беру не больше одной тушки мамкиных архитекторов / прЫнциплов в неделю. Но ты всегда можешь записаться в очередь.

как успехи? За 5 лет сколько процентов рынка бд подмял? Кому из лидеров рынка свое поделие продал? А хоть той, ошибки в коде на которые тебе 5 лет назад пофиксил? :)

Нет там никаких ошибок в коде. Успокойся уже. Нагрузочные тесты все прекрасно показывают. Были тесты (не я делал) миллиард ключей вставляли.

На счёт рынка, если ты хочешь торговать, гоу в ларек с шавермой. Это теоретически-практические работы в компьютер сцаинц.

а їсти ти також будеш

компьютер сцаинц

?

Это мое хобби, могу себе позволить

Были тесты (не я делал) миллиард ключей вставляли.

В 32х битовом процессе при том что под винду доступно только 2Gb виртуального адресного пространства на процесс.

docs.microsoft.com/...​ed/virtual-address-spaces

/LARGEADDRESSAWARE

+ Структура частично занимается компрессией данных
+ Никаких проблем пересобрать под 64 разряда

/LARGEADDRESSAWARE

Ну будет 3Gb, ты даже не вместишь туда миллиард uint32_t. Как всегда спиздел про миллиарды, даже не подумав.

+ Никаких проблем пересобрать под 64 разряда

Проблемы я тебе выше указал, оно работать у тебя не будет.

Ну будет 3Gb,

Не 3 а 4 Гб. Учи матчасть.

Проблемы я тебе выше указал, оно работать у тебя не будет.

Я как понял ты уже разобрался в алгоритме и вынес вердикт ?
Пока нет, мне виднее как и что там работает.

Не 3 а 4 Гб. Учи матчасть.

Точно-точно? Есть такое подозрение что ты ошибаешься :)

И если немного подумать, то вот как будет в 32-битном процессе работать взаимодействие с кернелом если юзерспейс отдать 4gb?

Если округлить будет почти 4. Кернел не отъедает гиг, ест мелочь на адрессные таблицы для win32.

Google говорит что эта опция даёт до 3gbyte.
Ты уверен что знаешь как округление работает?

Наверно у меня какой-то другой Гугл
This is why the /LARGEADDRESSAWARE flag was introduced into the Portable Executable (PE) file format header. The LAA flag indicates to the operating system that this 32bit application is „certified” by its developers to handle full 4GB of memory.

codekabinett.com/...​handle full 4GB of memory.

Тебе перевести?
Этот флаг говорит системе что процесс может работать с полными 4gb.

По твоей же ссылке

To understand what this means we need to go back in time. When the Windows operating system was 32bit only, it was able to address a maximum of 4GB of RAM memory (theoretically, effectively only ~3GB). Any application instance running on 32bit Windows was only allowed a maximum of 2GB of memory. The remaining memory was reserved for the operating system to run its own processes and other applications.

32-битный процесс в 32-битной системе никаким образом не может получить 4gb.
3 вот твоя цифра.

32-битный в 64-битной я без понятия. Я не знаю как работает MMU в этом случае, например можно ли держать два поддерева страниц в одном процессе, одно с 32 а другие для кернела с 64. Подозреваю что нет, и ограничение все равно будет 3gb.

Но я не специалист, а ты же специалист по округлениям, расскажи как это работает.

Но я не специалист, а ты же специалист по округлениям, расскажи как это работает.

Старт адрессов в заголовке Win32 (PE32) процесса начинается с 400000. Тоесть тебе доступно 4гб — 400кб.

По факту, оси нужно еще меньше места в твоих 4гб.
Представь что тебе нужно написать кернел операционной системы для 32х бит. Все хорошо, потому что ты можешь хендлить все 4гб в поинтере, все тебе доступно. Но есть проблема. А что если твое приложение должно взаимодейстовать с ОС ? На какие адресса ты должен отправлять колы внутри своей песочницы ? Для этого, когда тебе выделяют память тебе ее выделяют не всю, а чуть-чуть оставляют как раз на маппинг внутренних вызовов функций к внешним. Те самые 400кб. Другими словами когда процесс дергает win32 функцию, он дергает свой внутренний адресс, а таблица уже указывает что код который должен выполнятся, находится за рамками песочницы в 4гб.

Пришёл адрес в кернел из юзерспейса. Каким образом кернел получит доступ к данным по адресу?

Кернел насколько я понимаю всегда замаплен в адресное пространство юзерспейса.

Пришёл адрес в кернел из юзерспейса. Каким образом кернел получит доступ к данным по адресу?

Для кернела твой процесс не более чем песочница в контейнере на 4 гб виртуальной памяти.

Кернел насколько я понимаю всегда замаплен в адресное пространство юзерспейса.

Да. Кернел знает, что если ты обращаешся внутри своей песочницы на адресс меньше 400000 то ты по сути дергаешь экстернал кол Win32 api. Именно поэтому первые 400 килобайт своего адрессного пространства тебе не доступны.

Нет, подождите.
Вот пошёл сисколл с адресов буфера в кернел. Этот буфер надо отправить отправить в сетевую карту.
Как и где ты его будешь копировать?

Что значит как и где ? Для Кернела все страницы памяти открыты для чтения. Кернел видит, что пришел указатель на буфер с такойто песочницы, лезет туда (вычисляем этот адресс: начало адресса процесса + адресс буфера) и читает все данные.

Что значит открыты?
Есть многоуровневая таблица страниц. Процессор по ней ходит. Чтобы кернел мог читать из адресного пространства процесса и свои данные одновременно, надо чтобы и кернел и юзерспейс были одновременно замаплены в одно виртуальное адресное пространство.

Кернел на то и кернел, что он стоит НАД всеми песочницами. Он ими управляет и для него нет никаких защит памяти на страницах. Эти правила существуют для песочниц. Как получить точный адрес буфера я написал. Адресс процесса + Адресс буфера который пришел с песочницы процесса = Физический адресс в ОЗУ

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

Давай ты сначала разберёшься как на низком уровне это работает.

Нет, давай уж ты разбирайся.
Поскольку это работает, буферы передаются с процессов на сетевые карты и тд. А как это работает, это уже тебе разбираться, с моими обьяснениями или без.
Лучше без.

Я тебе говорю как.
Оно замаплено, все замаплено одновременно. И кернел и юзерспейс.
Просто дескрипторы которые кернел помечены как доступные из привилегированного режима только.
И вот делаем сисколл и передаём указатель в кернел. Кернел можем обращаться к этому указателю как к своему.

вычисляем этот адресс: начало адресса процесса + адресс буфера

1) адреса
2) Что такое «начало адресса процесса»?

of RAM memory (theoretically, effectively only ~3GB).

Это приблизительное слишком приблизительное.
Сам подумай. Если ОСи нужно АЖ 1 гб из твоего адрессного пространства, то как раньше работали машинки на винде с 64 мегабайтами ОЗУ на борту. И это НА ВСЕ. По факту оси нужно отьесть с твоей памяти на кернел совсем крохи.

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

. Если ОСи нужно АЖ 1 гб из твоего адрессного пространства, то как раньше работали машинки на винде с 64 мегабайтами ОЗУ на борту.

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

Читать научись контекст. Физически оси нужно намного меньше гига с твоего адрессного пространства.

Какой именно?
Ты в курсе что ОС тоже растут и жрут память. Драйвера там всякие.

Что-то меня уже начало утомлять.
Вернемся к первоначальному посту. Почему я считаю что 4гб (округленно) а не 2гб или 3гб как писал Горчак и о том, в какую сторону я округляю.

ibb.co/F3jDDpD

Ось одала больше чем 3,8 гб с флагом /LARGEADDRESSAWARE

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

Ну извините. Кстате тебе плюс, за адекватное общение и попытку разобраться. Надеюсь Прокофьев к следующей пятнице начистит отполирует шкурку (хотябы копнет по верхам trie). Я на своем алтаре к следующей пятнице хочу увидеть по крайней мере ухоженную тушку галерного архитектора.

И что там случилось в конце, любопытства ради? Исключение или ты на ноль проверить забыл?
А sizeof указателя точно 4 байта?

Точно 4, x86 сборка
Дальше краш приложения, нужно экскпшин в c++ ловить

Ну значит порядка 200 мегабайт ОС на твоей системе. Сделать какой-нибудь драйвер который полгига зааллоцирует и все.

2Gb сделали по умолчанию не просто так. Есть shared memory, есть file mapping, создание потоков и стеков для каждого потока. Для каждого действие необходио линейное виртуальное адресное пространство. Место под всё это резервируется ОС. Всё равно тебе эту память никто не даст для работы, не зависимо от того что ты там считаешь или насчитал.

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

ibb.co/F3jDDpD

Отдает 3.8 гиг из коробки

Ну т.е. ОС всё равно забрала себе 300Mb, а не 400Kb. И при этом ты не можешь выполнить ни одного системное действия, ни замапить расшаренную память, ни даже создать поток, ни открыть динамически DLL. Такое себе достижение. Именно поэтому этот ключь не дефолтный, он подразумевает что разработчик понимает что он делает.

Ну а теперь вернёмся к миллиардам (именно во множественном числе) записей? Опять знаменитое бубно-сжатие пространства для бетоно-метров, теперь уже для памяти процессов под виндой? :D

Ну а теперь вернёмся к миллиардам (именно во множественном числе) записей? Опять знаменитое бубно-сжатие пространства для бетоно-метров, теперь уже для памяти процессов под виндой? :D

Я же писал. Не я даже тестировал. У меня были канадские архитекторы из Белл на ставке QA

Читай.
forum.ixbt.com/...​c.cgi?id=26:43056:545#545

К слову там жалуются что удаление у меня не реализовано. И я потом его таки реализовал. И как реализовал. Это настоящий алгоритмический шедевр.

Я же писал. Не я даже тестировал. У меня были канадские архитекторы из Белл на ставке QA
Читай.
forum.ixbt.com/...​c.cgi?id=26:43056:545#545

З таким самим успіхом можеш перечислити регалії Artyom’а і Oleksandr’a — з переписуванням їхніх контор — Amazon, Microsoft, GoDaddy, Tableau і т.д. (про мої контори скромно умолчім, я анонім і ніхто)

І як ти відповідаєш тому QA? Нєбось подякував?

forum.ixbt.com/topic.cgi?id=26:43056-20
Ні, написав тому прославленому архітекту
«Вы меня уже начинаете утомлять своей тупостью.»

А, он оно чьо :-)

Насколько я понимают все это будет в адресном пространстве процесса, в тех двух гигабайтах.

2 гигабайта именно я так понимаю серьезной причины нет. Скорее на заре показалось хорошей идеей поделить пополам. Потом, гуглится что ещё покрывается знаковым интом.

Насколько я понимают все это будет в адресном пространстве процесса, в тех двух гигабайтах.

Да, просто нужно различать caging который имеет стандартная библиотека и в основном она тусуется в нижних 2Gb и системные вызовы, которые имеет доступ к любому виртуальному адресному пространству процесса.

Потом, гуглится что ещё покрывается знаковым интом.

Именно так, весь фан начинался когда использовалась арифметика указателей, а указатели оказывались знаковыми. Слишком много легаси кода не работало. Например скомпиленное Win32S приложение из 3.11 должно было работать вплоть до Windows 7 в режиме совместимости.

Второй момент named shared memory. Например, «базовики» делали именно таким образом поддержку PAE (когда процессор в 32 битовом режиме мог адресовать >4Gb физической памяти) в процессах. Создавались shared memory по 256-512Mb в большом количестве и по-очередно мапились в процесс и вымапливались старые, когда нужен был доступ к этой памяти. А те 2Gb — это как раз то место куда ОС мапит такие вещи по дефолту, чтобы не мешать хипу: MapViewOfFile()/UnmapViewOfFile().

Также люди которые понимают как это работает — делали ballooning памяти через VirtualAlloc(...,MEM_RESERVE,...) — когда процесс при старте может разметить себе виртуальную память под свои нужды без выделения памяти, и затем мапить туда куски системной памяти для работы по нужным адресам. Для этого никаких опций компилятору давать не нужно было — это работает из коробки, если выйти за пределы стандартной библиотеки.

techcommunity.microsoft.com/...​ysical-memory/ba-p/723674 — там для сервера вінди цікаво розповідає чувак (шле привіт нам з далекого 2008).
Звичайно, що можна написати свій менеджер пам’яті, не такий перебірливий до ресурсів.
Я думаю що це задача на декілька днів для справжнього майстра!

вінди цікаво розповідає чувак

это ж Марк Русинович, его Windows Internals должна быть как библия для тех кто серьезно под винду пишет
Но по правде говоря тяжело у меня эта книга шла :)))
7я редакция покрывает современные версии винды
docs.microsoft.com/...​sources/windows-internals

Не 3 а 4 Гб. Учи матчасть.

Т.е. стека у тебя нет, и ты даже не смотрел с чем линкуется обычное консольное приложение — там в адресное пространство клиента мапируются мегабайты dll’ек, они все должны быть в непрерывном виртуальном адресном пространстве, поэтому ОС резервирует память под них и под будущие загрузки. Винда не знает будешь ли ты что-то динамически подгружать или нет, и если будешь память под них остаётся в резерве — хочешь ли ты этого или нет.

Я как понял ты уже разобрался в алгоритме и вынес вердикт ?

Зачем мне весь алгоритм? Если ты пишешь говнокод, который хранит поинтеры в uint32_t вместо uintptr_t, то я могу только тебе посочувствовать.

Т.е. стека у тебя нет

Стек в моем адрессном пространстве. Занимает аж 1 мб, если не изменяет память.

там в адресное пространство клиента мапируются мегабайты dll’ек,

Осталось разобраться сколько мегабайтов длл мапируется к HArray которые вызывает new да delete и иногда чтото на консоль выводит.

Зачем мне весь алгоритм?

Незачем тебе, здесь я согласен.

Нет там никаких ошибок в коде.

чувак, тобі не бракує хуцпи брехати, коли всі ходи записані і на 5 році виявляється, що структура не вміє хендлити неіснуючі ключі, тупо повертає 0
dou.ua/...​rums/topic/18849/#2134680

Нагрузочные тесты все прекрасно показывают. Были тесты (не я делал) миллиард ключей вставляли.

нагрузочні тести працюють в одній функції, там де init/insert/get/delete/destroy

як тільки розносиш їх в різні закутки і починаєш робити отаке
dou.ua/...​rums/topic/18849/#2135157

1) точно такий же рядок, але за іншою адресою — ключ буде інший?
2) переписати рядок за адресою str — ключ лишається той же?

так одразу видно де зачітив і що структура тупо по можливостям не здатна конкурувати з std::map, чи Python dict

Успокойся уже.

вот такі да :-)

одразу видно де зачітив і що структура тупо по можливостям не здатна конкурувати з std::map

Так, заявляти про неї як заміну мепам/хеш-таблицям це дещо нахабно. Але чисто теоретично може бути задача коли треба швидко ключ->ідентифікатор знаходити. І тоді за умови що клієнт:
— сам реалізує хеш-функцію
— пам’ятає усі ключі
— гарантує існування об’єктів раніше доданих у колекцію
— гарантує незмінність об’єктів раніше доданих у колекцію

все це може і буде літати. Але навіть для цього потрібна нормальна документація, нормальні тести та приклади, нормальні бенчмарки та щоб усе це просто збиралося різними компіляторами під різні платформи.

я правильно розумію, що ключі та значення в цій структурі можуть бути лише числами і лише користувач розбирається як їх інтерпретувати?

Саме так. Він реалізував доволі оптимальний спосіб збереження значень фіксованого розміру. В поточній реалізації це 32-розрядні значення наскільки я розібрався.

Нет, ключ может быть переменной длины. Для этого при вставке передается длина ключа. Велью фиксировано действительно 4 байтами, потому что чаще всего это поинтер на объект.
Но это можно переделать, просто в моих сценариях мне это не нужно.

Легендарный супероптимизированый алгоритм, который реализует весьма сложные Trie структуры данных и топчет вот эти вот эти ваши самые реализации ассоциативных массивов std::map, glib, dictionary.net и прочью заморскую попсу в разы, а то и на порядок.

а насправді

Велью фиксировано действительно 4 байтами, потому что чаще всего это поинтер на объект.
Но это можно переделать, просто в моих сценариях мне это не нужно.

Я написав

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

на що ти відповідаєш

Велью фиксировано действительно 4 байтами

Наче ж одне й те саме?

Так а че 4 а не 8? Ты уже в Azure и AWS не найдешь x32 виртуалок вообще, все x64, даже ARM.

тобто я можу використовувати як ключ рядки?

Да, ключ это любой массив байт любой длины выровненный по границе в 4 байта (в целях быстродействия)

чувак, тобі не бракує хуцпи брехати, коли всі ходи записані і на 5 році виявляється, що структура не вміє хендлити неіснуючі ключі, тупо повертає 0
dou.ua/...​rums/topic/18849/#2134680

*Фейспалм*
Какие будут следующий ошибки ?
Ошибки комментариев в коде ?

*Фейспалм*
Какие будут следующий ошибки ?
Ошибки комментариев в коде ?

ах, то для тебе це мєлочь? :-)
це у нас тут фейспалм 5 років тому і зараз знову
не диво написати тести, які вставляють і одразу читають задані значення із якогось масиву, а от на реальних задачках такі симульовані тести уже побоку
та блін, навіть простим читанням твого коду баги знаходяться, я мовчу вже про всілякі сегфолти, що були в людей раніше

На реальных задачах, по крайней мере те что у меня под рукой сейчас
std::map и hastable ___вообще___ не подходят по ____функциональности____

Остальное мне уже не интересно.
Баги иди в своем формошлепстве ищи.
Ты слишком т/глуп чтобы понимать как работают такие вещи. Иди нещасный LRU переучивай к собеседованию по 20 кругу (чего кстате меня и бомбануло. Люди до лру не могут додуматься, а некоторым рассказали и они забыли к следующему собесу).

На реальных задачах, по крайней мере те что у меня под рукой сейчас
std::map и hastable ___вообще___ не подходят по ____функциональности____
Остальное мне уже не интересно.
Баги иди в своем формошлепстве ищи.
Ты слишком т/глуп чтобы понимать как работают такие вещи. Иди нещасный LRU переучивай к собеседованию по 20 кругу (чего кстате меня и бомбануло. Люди до лру не могут додуматься, а некоторым рассказали и они забыли к следующему собесу).

хи-хи, гляди, як тебе заїло

тепер по пунктам
1. я хз, які у тебе реальні задачі, але твоя бібліотека обмежена і з багами
2. я не формошльоп, а ти хужеформошльопа — бо у тебе синдром Даннинга-Крюгера помножений на віндузятництво программінга
3. як бачиш, не глупий — розковиряв і потестив твій код (хоча я на C/C++ дуже давно не писаа), знайшов ще один баг — вот ти і злішся
4. на реалізацію LRU з віддебажженям і проходженням всіх тестів у перший раз у мене пішло 90 хв
5. запиляй LRU тут і розкажеш потім, скільки це зайняло часу — leetcode.com/...​ms/lru-cache/description . Має бути набагато швидше, ніж тут свій недороблений код захищати :-)

3. як бачиш, не глупий — розковиряв і потестив твій код (хоча я на C/C++ дуже давно не писаа), знайшов ще один баг — вот ти і злішся

Какой баг ? Это максимум тех депт, а минимум вкусовщина.

Уровень анализа у вас царапина на сопле истребителя. Это тех депт максимум.
Возвращать 0 вместо поинтера на объект если объект не найден.

Уровень анализа у вас царапина на сопле истребителя. Это тех депт максимум.
Возвращать 0 вместо принтера на объект если объект не найден. Не позорься

HArrayInt повертає uint32, 0, але не поінтер
ти читати мої комменти і свій код не вмієш
dou.ua/...​rums/topic/18849/#2134680

не позорся

HArrayInt повертає uint32, 0, але
не поінтер

Ты не можешь конвертнуть 32 бита в 32 бита в 32х битном процессе ?
(uint*)value

Печаль.

Ты не можешь конвертнуть 32 бита в 32 бита в 32х битном процессе ?
(uint*)value
Печаль.

1. Примітивно працюєш і намагаєшся увільнути.
2. Свого коду не знаєш.
Ти тестуєш запихання int‘ів, а не pointers
github.com/...​aster/HArray/Main.cpp#L87
3. у теперішній реалізації неможливо відрізнити, чи прочитався 0 по ключу, чи цього ключа немає. Бо «вкусовщина» супералгоритму.

3. у теперішній реалізації неможливо відрізнити, чи прочитався 0 по ключу, чи цього ключа немає. Бо «вкусовщина» супералгоритму.

Если для тебя критичен этот 0, используй следующую функцию.

github.com/...​ray/HArray_hasPartKey.cpp

Она проверяет есть ли ключ в контейнере.
Возвращает true/false. В отличии от бинарных деревьев и хештаблиц, может чекать ключи не только на есть ключ/нет ключа, но и есть ли вообще любой ключ который подходит под заданный шаблон. Функция работает за константное время, где константа это длина переданного шаблона О(1).

PS: Не пиши мне больше. Я вижу что ты решил взять меня измором своей тупостью.

Если для тебя критичен этот 0, используй следующую функцию.
github.com/...​ray/HArray_hasPartKey.cpp
Она проверяет есть ли ключ в контейнере.
Возвращает true/false. В отличии от бинарных деревьев и хештаблиц, может чекать ключи не только на есть ключ/нет ключа, но и есть ли вообще любой ключ который подходит под заданный шаблон.

посібо

Тепер перепиши testHArrayInt, щоб перед кожним getValueByKey воно дьоргало hasPartKey.
Запусти тести. Що буде — ой, уже не таке швидке, як раніше.

PS: Не пиши мне больше. Я вижу что ты решил взять меня измором своей тупостью.

я тільки почав, не треба твою хуцпу вважати моєю тупістю

тепер по ось цьому питанню дай відповідь
dou.ua/...​rums/topic/18849/#2135372

він там відповів вже (побіг за попкорном)

Тепер перепиши testHArrayInt, щоб перед кожним getValueByKey воно дьоргало hasPartKey.

Если бы я был говнокодером вроде тебя, то наверное так бы и написал. Но я же не говнокодер.
Поэтому getValueByKey переписываю специально для тебя за 5 минут, так чтобы абсолютно не потерять в скорости.

uint32 getValueByKey(uint32 key, bool& isExists)
	{
                isExists = true;

		HeaderCellInt& headerCell = pHeader[key >> BLOCK_BITS];
		uint32 rightPart = (key & BLOCK_SIZE);

		switch (headerCell.Type)
		{
		case 1:
		{
			if (headerCell.Code == rightPart)
			{
				return headerCell.Offset;
			}

			break;
		}
		case 2:
		{
			DoublePageInt* pPage = pDoublePages[headerCell.Offset >> 16];
			if (pPage)
			{
				DoubleValueCellInt& valueCell = pPage->pValues[headerCell.Offset & 0xFFFF];

				if (headerCell.Code == rightPart)
				{
					return valueCell.Value1;
				}
				else if (valueCell.Code2 == rightPart)
				{
					return valueCell.Value2;
				}
			}

			break;
		}
		case 3:
		{
			uint32 offset = headerCell.Offset + rightPart;

			MultiplyPageInt* pPage = pMultiplyPages[offset >> 16];
			if (pPage)
			{
				MultiplyValueCellInt& valueCell = pPage->pValues[offset & 0xFFFF];

				if (valueCell.Code == headerCell.Code)
				{
					return valueCell.Value;
				}
			}

			break;
		}
		};
               
                isExists = false;
		return 0;
	}
Возвращает флаг isExists найдено\не найдено.
Не благодари.
Если бы я был говнокодером вроде тебя

чувак, май на стримання, тут твій засраний код на GitHub висить, я ж там ковиряюся, бо у мене на цьому тижні приступ доброти і агрономії, аналіз як це на добрива перетворити

Возвращает флаг isExists найдено\не найдено.
Не благодари.

не буду, але хотів

тепер додай перевірку на isExists в тести
стало швидше? :-)

і т.д., ця низькорівнева реалізація без допилювання напильником і обв’язки перевірками купи фунцій, обв’язками alloc/destroy memory і т.п. — може бути швидкою і коректною тільки у вакуумі бенчмарків

в ріл-лайф її пустити — себе не поважати

Уровень анализа у вас царапина на сопле истребителя.

Может привести к удару истебителем об землю.

Вот и отговорки пошли, а истребитель-то уже в кучку металлолома превратился. Но может он сразу из соломы был? И не взлетал даже, а так в овраг спихнули.

Мне уже перестает быть интересным этот топик на доу.
За 5 лет существования этой темы, я помню единственный баг (не косметика) нашел канадский архитектор контрактор на ixbt. Я пофиксил этот баг за минут 15, но это был реальный баг в имплементации алгоритма, провтыкал одно место.

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

Начни писать юнит тесты. Пока их нет, твой проект работает по happy-path. С тестами сам найдешь несколько десятков багов :)

Начни писать юнит тесты. Пока их нет, твой проект работает по happy-path. С тестами сам найдешь несколько десятков багов :)

Видишь ты тоже не понимаешь специфику проекта.
Когда ты вставляешь десятки миллионов ключей в самых разных комбинациях, а потом удаляешь их по одному, разбирая структуру по винтикам до самого основания, пропустить баг крайне тяжело. Каждая строчка в коде покрыта тысячи если не сотни тысяч раз в разных комбинация. Ты просто не дойдешь до конца бенчмарка (который к слову длится минут 20 полной нагрузки на структуру),
если там будет хотябы один баг.

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

Легко пропустить, если ворочаешь десятками миллионов, но не дошел до 70 миллионов, как я ниже продемонстрировал :)

. Каждая строчка в коде покрыта тысячи если не сотни тысяч раз в разных комбинация.

Як ти збирав статистику покриття, яким кодом?

За 5 лет существования этой темы, я помню единственный баг

dou.ua/...​rums/topic/18849/#2044301

Там у тебя еще вроде с сегфолтом падает при 70 миллионах ключей, уже пофиксил?

Мне уже перестает быть интересным этот топик на доу.

канєшно, якщо за всяку муру і недоробки, провтики, проскакування гострих кутів і тд тебе постійно макають в твоє творіння — то «художніка каждий может обідєть» :-)
але хуцпи при тому...

Какой баг ? Это максимум тех депт, а минимум вкусовщина.

:-D, блін, я з тої хуцпи не можу

5. запиляй LRU тут і розкажеш потім, скільки це зайняло часу — leetcode.com/...​ms/lru-cache/description . Має бути набагато швидше, ніж тут свій недороблений код захищати :-)

Когда уже дойдет что НЕ ИНТЕРЕСНО имплементить простые задачи, что уже десятки тысяч раз заимплеменчены. Тем более в академических целях.
Самый высший пилотаж заимплементить фундаментально иначе то, что никто и никогда не имплементил до тебя. И получить качественно другой результат.
Вот высший пилотаж.

Когда уже дойдет что НЕ ИНТЕРЕСНО имплементить простые задачи, что уже десятки тысяч раз заимплеменчены. Тем более в академических целях.
Самый высший пилотаж заимплементить фундаментально иначе то, что никто и никогда не имплементил до тебя. И получить качественно другой результат.
Вот высший пилотаж.

ти рядок покажеш, чи будеш пілотірувати далі високо словоблудієм?
dou.ua/...​rums/topic/18849/#2135372

НЕ ИНТЕРЕСНО имплементить простые задачи

Вибач, але починати доведеться з простих. До того ж ти сам заявив про три різні реалізації LRU які зробив за 15 хвилин. Мені особисто цікаво подивитися на них.

а це що таке?
github.com/...​ray/HArray_insert.cpp#L23
mapping string <=>uint32?
а чого uint32*, а не char*?

uint32 HArray::insert(uint32* key,
					uint32 keyLen,
					uint32 value)

Причому ключ фіксований до 64 байт?
github.com/...​ster/HArray/Main.cpp#L831

const char STR_KEY_LEN = 64;

А як на рахунок string <=> string?

const char STR_KEY_LEN = 64;

Это в бенчмарке задается на строках какой длины будем тестировать.
В данном случае берутся рандомные строки в 64 символа.

А як на рахунок string <=> string?

Не совсем понял ?
char* str = «hello world»;
uint32 value = (uint32)str;

Для 32х битного процесса (даже на 64х разрядной системе) должно сработать.

Не совсем понял ?
char* str = «hello world»;
uint32 value = (uint32)str;

Для 32х битного процесса (даже на 64х разрядной системе) должно сработать.

вот я от тоже не поняв, я думав, що там можна string<=>string,
але там нікуди контент value не копіюється, тобто я очікував, що всередині insert буде strcpy, чи memcpy, а там тільки таке
github.com/...​ay/HArray_insert.cpp#L114

pContentPage->pContent[contentIndex] = value;
char* str = «hello world»;
uint32 value = (uint32)str;
Для 32х битного процесса (даже на 64х разрядной системе) должно сработать.

Facepalm. Не будет оно работать на 64х разрядной системе.

char* str = «hello world»;
uintptr_t value = (uintptr_t)str;

Будет, поскольку в 64х разрядной системе можно запустить 32х битный процесс
(поинтер = 4 байта будет в контексте процесса)

Будет, поскольку в 64х разрядной системе можно запустить 32х битный процесс
(поинтер = 4 байта будет в контексте процесса)

Чекай. То ти стверджуєш, що в HArray можна зберігати strings, як values, якщо покласти в value поінтер на на string?

Будет, поскольку в 64х разрядной системе можно запустить 32х битный процесс

Мова про те, щоб зробити 64-бітний процес.

uint32 value = (uint32)str;

Конгеніально! Що буде коли:
1) точно такий же рядок, але за іншою адресою — ключ буде інший?
2) переписати рядок за адресою str — ключ лишається той же?

А взагалі то це дуже хитро примусити код клієнта перейматися копіюванням, часом життя та консистентністю даних в такій колекції, а самому просто числа тасувати. Я не кажу, що воно не потрібно, але щоб це стало заміною звичайним map та set треба дописату купу коду.

Одному коду клиента надо хранить велью Инты. Другому строки. Третьему (что чаще всего) объекты. Я решил что велью это поинтер. Могу собрать реализацию где велью будет 8-16 или сколько надо байт и встраиваться в HArray. Хотя не вижу в этом смысла, в листьях обычно лежат объекты, часто разного размера. Но всё-таки если кому надо, могу за деньги собрать такую реализацию

Я решил что велью это поинтер

Я зрозумів. І це нормальний підхід, просто мені з документації не очевидно було, що часом життя значень та їх іммутабельністю має перейматися клієнт.

Одному коду клиента надо хранить велью Инты. Другому строки. Третьему (что чаще всего) объекты. Я решил что велью это поинтер. Могу собрать реализацию где велью будет 8-16 или сколько надо байт и встраиваться в HArray. Хотя не вижу в этом смысла, в листьях обычно лежат объекты, часто разного размера. Но всё-таки если кому надо, могу за деньги собрать такую реализацию

вот
коли у тебе Value буде «сколько надо байт и встраиваться в HArray» — тоді будуть зовсім інакші тести з stdmap і вимоги до пам‘яті, плюс танці з аллокацією/деаллокацією.

Какая аллокация деалокация. Когда же вы научитесь код читать. Все велью хранятся в контент пейджах. Сейчас это 4 байт. Ставишь больше и цикл форич пишет велью такой длины которой надо в контент пейдж. Я ниодин new не добавлю в имплементацию.

На счёт std::map он тестировался с велью 4 байта. Все честно.

Какая аллокация деалокация.

ніяка, я ж написав «будуть»

Когда же вы научитесь код читать. Все велью хранятся в контент пейджах. Сейчас это 4 байт. Ставишь больше и цикл форич пишет велью такой длины которой надо в контент пейдж.

я код читав, такого не бачив, не дивно не побачити, бо функція на 1300 чи скільки там рядочків — це звісно з Best Practices

покаж пальцем в рядок на Github де цей цикл?

Там где велью переданное в insert копируется. Твой Кеп.

Там где велью переданное в insert копируется. Твой Кеп.

пальцем ткни, я лінки наводив
не полінись і ти

А вот принципиально не буду. Если человек не может найти в коде где копируется переменная value в одной единственной функции, то это о чем-то говорит

Вообще я вспомнил, я для тебя мультик снял. Есть на центральной странице проекта на гите. Визуально сможешь зафиксировать что никаких ограничений на размер велью нет ?

Вообще я вспомнил, я для тебя мультик снял. Есть на центральной странице проекта на гите. Визуально сможешь зафиксировать что никаких ограничений на размер велью нет ?

блін, ну це капєц якийсь
тут Artyom постійно дістає тебе з «show me your code», у тебе вже і код є — а ти мультікі показуєш

Вообще я вспомнил, я для тебя мультик снял

А треба було лінк на рядок коду дати усього лише.

А вот принципиально не буду. Если человек не может найти в коде где копируется переменная value в одной единственной функции, то это о чем-то говорит

бо її нема і ніякого копіювання в форіч нема
те що я бачив ще вчора — це присвоєння value (uint32), а ти розповідаєш про якийсь цикл і «такой длины»

покаж рядок — я вибачуся

покаж рядок — я вибачуся

Ок. Вот цикл который пишет хвост ключа и в конце записывает Value. Если велью больше чем 4 байта, то цикл продолжается и мы записываем столько сегментов Value сколько нужно (это модификация о которой я говорил).

github.com/...​y/HArray_insert.cpp#L1533

Жду вибачень.

Ок. Вот цикл который пишет хвост ключа и в конце записывает Value. Если велью больше чем 4 байта, то цикл продолжается и мы записываем столько сегментов Value сколько нужно (это модификация о которой я говорил).

Посібо, я знав, що це поруч
Покажи модифікацію, яка буде робити наступне «Ставишь больше и цикл форич пишет велью такой длины которой надо в контент пейдж.»

Поки що я там бачу (і бачив раніше, за що і почав розпитуватися) тільки присвоєння value (4 байти)
github.com/...​y/HArray_insert.cpp#L1539

Жду вибачень

я б хотів вибачитися, але ти розказуєш про неіснуючі штуки
покажи ось це
«Ставишь больше и цикл форич пишет велью такой длины которой надо в контент пейдж.»

Погоди. Я свою часть договора выполнил.

я б хотів вибачитися
Жду вибачень.

Про то что я буду это имплементить я не сказал. Я обещал что нет _никакой_ проблемы заимплементить модификацию которая будет сохранять велью больше чем 4 байта и показал где это можно сделать. И сделаю это за деньги если кому надо, это тоже я говорил.

Так что жду вибачень.

2Punk Floyd

Так, у тебя еще 15 минут. Дальше у меня дежурная прогулка по лесу и набережной озера, наблюдая закат с мыслями о суперсовершенных алгоритмах.
Меня устроит вполне скромная фраза без излишиств
"Вибач мене будьласка я був неправий"©

бо її нема і ніякого копіювання в форіч нема
те що я бачив ще вчора — це присвоєння value (uint32), а ти розповідаєш про якийсь цикл і «такой длины»
покаж рядок — я вибачуся

«бо її нема» — а нема, то й нема за що вибачатися

не треба було телитися цілу добу, щоб потім підтвердити очевидне

і вертаємся до попереднього

dou.ua/...​rums/topic/18849/#2135223
«вот
коли у тебе Value буде „сколько надо байт и встраиваться в HArray“ — тоді будуть зовсім інакші тести з stdmap і вимоги до пам‘яті, плюс танці з аллокацією/деаллокацією.»

«бо її нема» — а нема, то й нема за що вибачатися

не треба було телитися цілу добу, щоб потім підтвердити очевидне

Тоесть ты забалаболил и свою часть уговора не выполнил. Ок.

і вертаємся до попереднього

dou.ua/...​rums/topic/18849/#2135223
«вот
коли у тебе Value буде „сколько надо байт и встраиваться в HArray“ — тоді будуть зовсім інакші тести з stdmap і вимоги до пам‘яті, плюс танці з аллокацією/деаллокацією.»

Ну почему ты такой тугой. Ты всего лишь пишешь велью на страницу. Если велью 4 байта то и я и стд МАП тратит на это условных 4 такта. Если мы будем писать 8 байт то и я и мапа будет тратить только условных 8 тактов
Это блеать велью, все время что ты тратишь просто тратишь на запись последовательно байт. Ну неужели нельзя это понять.

Тоесть ты забалаболил и свою часть уговора не выполнил. Ок.

балабол ти, бо ти мені показав те, чого не існує, і про я писав раніше, що не існує, претензії тільки до тебе самого

Ну почему ты такой тугой. Ты всего лишь пишешь велью на страницу. Если велью 4 байта то и я и стд МАП тратит на это условных 4 такта. Если мы будем писать 8 байт то и я и мапа будет тратить только условных 8 тактов
Это блеать велью, все время что ты тратишь просто запись последовательно байт. Ну неужели нельзя догадаться ??

Тугий у нас тут ти. А може просто чітер.
Порівнювати і ганяти тести зберігання у твоїй структурі 1 (одного!) поінтера на структуру проти std::map і подібних структур, де value (variable length) копіюється всередину.

Ще раз
«вот
коли у тебе Value буде „сколько надо байт и встраиваться в HArray“ — тоді будуть зовсім інакші тести з stdmap і вимоги до пам‘яті, плюс танці з аллокацією/деаллокацією.»

std::map

Жесть. Покажи мне что в мапе копируется кроме велью = 4 байта в моих бенчмарках.
Ты реально сейчас в топе среди всех тупых отписавших в этом топике примерно за последний год. Первенство держит все ещё хлопец который предложил переписать на ООП.
Но ты уже близок.

Жесть. Покажи мне что в мапе копируется кроме велью = 4 байта в моих бенчмарках.

звиняй, у кишках std::map не ковирявся, але припускаю, що там буде
1) alloc пам’яті, якщо value менше, ніж уже pre-alloc
2) копіювання ВСЬОГО value туди. Value може бути variable length і для цього у std::map є туча коду

У твоїх так званих benchmarks ти використовуєш std::map не на повну потужність, записуєш туди огризок і пишаєшся тим.
Але як тільки ми вийдемо за межі огризка, і почнем зберігати у твоїй структурі variable length дані, так одразу буде видно хто і де насрав, і чому std::map та й інші структури/бібліотеки мають купу оверхеду.

Ты реально сейчас в топе среди всех тупых отписавших в этом топике примерно за последний год. Первенство держит все ещё хлопец который предложил переписать на ООП.
Но ты уже близок.

Ти на жаль припускаєшся дурної помилки через свою хуцпу — вважаєш себе геніальним, а всіх решта по дефолту тупими. Якщо ти це перестанеш робити (а це неможливо, бо хуцпа) — то ти зможеш вчитатися і зрозуміти що тобі пишуть, без переходу одразу в атаку.

1) alloc пам’яті, якщо value менше, ніж уже pre-alloc
2) копіювання ВСЬОГО value туди. Value може бути variable length і для цього у std::map є туча коду

Можна передавати володіння елементами, але це все одно вимагає чогось більшого ніж набір 4-байтних значень.

что в мапе копируется кроме велью = 4 байта в моих бенчмарках

Мапа, на відміну від твоєї структури робить копії об’єктів, а також вміє переміщувати їх та передавати володіння. У тебе ж просто 4 байти фіксовано. До того ж у мапи є такі чудові речі як ітератори, можливість використовувати її як абстрактний контейнер з алгоритмами, можливість прикрутити алокатор і тому подібне. І все це «з коробки» і без того щоб автори мапи «от щас спеціально для тебе за 5 хвилин переписав як треба».

Для того щоб серйозно заявляти про хоч якусь наближеність твоєї структури до тієї ж мапи тобі мінімально треба:
— зробити з неї ADT колекцію
— додати хеш-функції
— додати ітератори
— покрити все юніт-тестами
З цим можна буде говорити вже про бенчмарки.

А для використання в реальних проектах треба ще:
— константні ітератори
— алокатори
— діапазони
— ...

Мапа, на відміну від твоєї структури робить копії об’єктів, а також вміє переміщувати їх та передавати володіння.

Копии каких обьектов она делает ? Любой обьект класса в Си кроме структур, это указатель. Сделав указатель я покрыл почти 100% случаев. Какие вопросы ?

Для того щоб серйозно заявляти про хоч якусь наближеність твоєї структури до тієї ж мапи тобі мінімально треба:
— зробити з неї ADT колекцію

Моя структура и так абстрактная. Ей всеравно что такое ключ и что такое велью. Это набор битов.

— додати хеш-функції

Мне это не нужно. Плюс моей структуры, что она работает без хешфункций и сортирует данные.

— додати ітератори

Там есть визитор.

— покрити все юніт-тестами

Бенчмарки теже тесты, все покрывают. Проблем нет.

З цим можна буде говорити вже про бенчмарки.

Можно. Но для начала мапе нужно научится следующее.
1. Научится компрессить данные для ключей с одинаковым префиксом — она это не умеет
2. Научится сканировать поддиапазоны ключей, например все ключи которые начинаются с такогото префикса — она этого не умеет
3. Реализовать функцию hasPartKey которая работает как поиск ключа по шаблону за О(1) — не умеет
4. Научится удалять ключи, с плавным освобождением памяти, балансировкой и шринком страниц — не умеет
5. Научится вставлять и искать ключи почти за константное время О(1) — не умеет
6. Сохранятся на диск на уровне скорости работы дисковой системы — не умеет
7. Искать по диапазону ключей за тоже близкое к О(1) время — не умеет.

Я этот список могу продолжать долго.
Вы просто не понимаете рассовое превосходство моего алгоритма. Это просто другой уровень, чем гавеные деревья и хештаблицы. И прежде всего даже не по скорости, а по функциональности.

Копии каких обьектов она делает ? Любой обьект класса в Си кроме структур, это указатель. Сделав указатель я покрыл почти 100% случаев. Какие вопросы ?

блд, на що я трачу свій час....

С бубуном общаться — или постебаться с него или послать нах. Второе на форуме типа запрещено :-)

Копии каких обьектов она делает ?

Будь-яких, що збергіаються в ній.

Любой обьект класса в Си кроме структур, это указатель.

Вказівник — це вказівник, а об’єкт — це об’єкт.

Сделав указатель я покрыл почти 100% случаев

Ти покрив лише випадок коли треба зберігати вказівники. А це насправді не так часто трапляється. Як в твоїй колекції зберігати той же std::string? І так, мені треба зберігати саме в колекції як я це можу зробити з std::map, а не перейматися часом життя тих рядків.

Моя структура и так абстрактная.

Це не правда. Як в ній зберігати std::string?

Мне это не нужно.

Це потрібно користувачу твоєї колекції. Інакше для кожного типу даних мені доведеться писати хеш-функцію.

Там есть визитор

Тобто зробити так, щоб твою структуру можна було використовувати з алгоритмами має бути не складно.

Бенчмарки теже тесты, все покрывают

Покажи статистику покриття.

Но для начала мапе нужно научится следующее

Мапі нічого не треба. Те що її без проблем використовують в безлічі проектів на протязі пари десятків років це лише підтверджує. Це тобі свою реалізацію треба підтягнути до тієї ж мапи, якщо хочеш з нею порівнювати.

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

Ти визначся чи в тебе алгоритм, чи структура даних. Якщо таки алгоритм то чому його не запиляти так, щоб можна була використовувати в тих же stl колекціях?

Это просто другой уровень, чем гавеные деревья и хештаблицы.

І поки що це рівень proof of concept.

Завели оффтопік в іншому топіку — dou.ua/...​rums/topic/33483/#2134487
Тепер вертаємся сюди

Що робити, коли не знайдений елемент у hashtable?

1. Реалізація C++ — std::map — find en.cppreference.com/w/cpp/container/map/find

Return value

Iterator to an element with key equivalent to key. If no such element is found, past-the-end (see end()) iterator is returned.

2. Реалізація hashtable у класичній книжці по C — Кернігана і Річі
github.com/...​chapter06/tablookup.c#L72
Структура і повернення

struct nlist *np;
...
return NULL; // Not found

3. Реалізація Бубна
github.com/...​r/HArray/HArrayInt.h#L484

uint32 getValueByKey(uint32 key)
...
return 0;

Швидкий тест, звиняйте, що без засікання часу :-D

void testHArrayZeroInt()
{
        printf("HArrayInt => ");

        HArrayInt ha;
        ha.init(26);

        for (unsigned int i = 0; i < 10; i++)
        {
                printf("got value %u from key %u\n", ha.getValueByKey(i), i);
        }

        ha.destroy();
}

Вивід

$ ./HArray
HArrayInt => got value 0 from key 0
got value 0 from key 1
got value 0 from key 2
got value 0 from key 3
got value 0 from key 4
got value 0 from key 5
got value 0 from key 6
got value 0 from key 7
got value 0 from key 8
got value 0 from key 9

Я поменяю. Но NULL в Си насколько помню это и есть int* p=0. Тоесть поинтер вникуда.

Я поменяю. Но NULL в Си насколько помню это и есть int* p=0. Тоесть поинтер вникуда.

ти не можеш з C функції, що вертає цілочисельне значення — вернути NULL, який буде інтерпретований як 0, який цілком може бути валідним значенням

функція або має вертати структуру, яку ще потім треба обробити, або писати значення в кудась по поінтеру і вертати true/false (якщо не знайдений і не записаний елемент)

і вертати true/false (якщо не знайдений і не записаний елемент)

Можно и так сделать. Там это без разницы.

NULL в Си насколько помню это и есть int* p=0

Не гарантовано. NULL можу бути і не 0, але (void*)0 завжди NULL. Також про nullprt в плюсах глянь.

Например на LynxOS NULL — это валидный поинтер, также на разных PPC Cisco продуктах NULL тоже валидный.

Я зараз не згадаю де точно, але колись на початку кар’єри працював з embedded програмістами які для крихітних проців з пару кіло пам’яті писали і у них там для однієї платформи NULL був щось типу 07777.

Перша сторінка пам’яті — також місцями традиційно NULL... тобто GPF...

Когда это будет в boost ?

Когда они это купят и будут платить per CPU core

Добавил анимацию как эта штука работает.
Схема правда упрощенная, все ньюансы не вместить в гиф.
raw.githubusercontent.com/...​Array_works_animation.gif

там все настолько быстро переключается, что я не успеваю понять

все равно без доки нифига не понятно. надо в поверпойнт по слайдам с текстом.

Все верно: когда быстро — завораживает, но для понимания — хреново. Особенно если знание очень сильно изолированное. В этом случае надо всю предметную область step by step минута за минутой в мозг записывать.

Слайды мега круто будет сделать. И слайды рулят безусловно. И два кнопки — вперед и назад.
Хитрость таких кнопок — что всегда можно прийти к началу и всегда можно прийти к концу. И что можно менять стрелу времени с прямой на обратную. И что можно думать сколько угодно времени и разбираться с конкретным фреймом пока не разберешься, а потом переходить на следующий фрейм. И вообще это крутой бизнес — слайдирование (но об этом только спонсорам расскажу)
P.S. если не зацикливать, не замыкать круг, как вот сейчас, когда начало от конца ничем не отличается.

Читал сейчас твою статью на Хабре — захватывающе. И пришла мысль про «забывание» — редко затребываемые данные стоит забывать. Время доступа к ним сравнимо с временем обновления из источника. Что подводит ко взгляду на информацию, как на то, что имеет массу, плотность. x=2 это генератор двойки в икс. Но если потом y=x-2 то в икс не должно ничего остаться. Информация как песчинки, переносится от одного data store к другому, как песочные часы работают.
Это радует потому, что актуальность информации всегда будет на высоте там, где старая информация тускнеет, де-определяется, квантуется и исчезает.

Когда-как.
У крупных контор с миллионами клиентов небольшое ускорение кода может сэкономить очень много денег. Таким бывает не жалко посадить пару программистов оптимизировать код.
А еще бывают случаи, когда медленно — вообще не вариант. Например, для передачи звука в телефонии или для боев по сети в игрушках.

Проще не значит медленно. Напротив, проще всегда значит быстрее. Почему так? Потому что простота это всегда минимальная обработка сырого сырья некоторым набором правил. Чем больше правил применяется и или чем больше делается последовательных применений одного и того же правила т.е. вот так: a= f(a); a=f(a); a=f(a); //здесь три инструкции 
тем сложнее и медленнее работает код.
Отсюда следствие: если код сложный и медленный, то кто-то не нашел простого решения.
Например, как споласкивая чашку после чая, максимально быстро не оставить в чашке ни одной чаинки? Я нашел решение.

Вот автор этой темы хвалится, что его сложный алгоритм работает быстрее простого, который у всех

Поэтому когда он его упростит — этот алгоритм станет еще быстрее.

Далеко не факт. Одно из направлений оптимизации, это добавление кода в простое решение, некоторое узкоспециализированное ускорение для часто встречающегося случая. Ну а дальше чем больше таких случаев, тем сложнее код.

Например, нужно скопировать фрагмент памяти. Самое простое решение for (int i=0; i<len; ++i) *dst++ = *src++;, но копирование по одному символу достаточно медленное. Быстрее будет код, который копирует сразу по uint64_t или с использованием каких-то больших XMM регистров, но это приводит у сложнению кода: нам надо определить, сколько полных значений будет скопировано, а потом в конце докопировать невписавшийся остаток. Код сложнее, но быстрее.

Например, нужно скопировать фрагмент памяти. Самое простое решение for (int i=0; i < len; ++i) *dst++ = *src++;

С каких пор это стало проще, чем обычный memmove/memcpy?

но копирование по одному символу достаточно медленное. Быстрее будет код, который копирует сразу по uint64_t или с использованием каких-то больших XMM регистров, но это приводит у сложнению кода: нам надо определить, сколько полных значений будет скопировано, а потом в конце докопировать невписавшийся остаток. Код сложнее, но быстрее.

Мы слава богу не в 80-х годах живем, компиляторы уже давно научились разворачивать циклы, определять патерны работы с памятью и включать SIMD где нужно, причем делать это платформо-независимо без необходимости усложнять исходный код.

Дабы не быть голословным:
godbolt.org/z/4dEzeqjx7

С каких пор это стало проще, чем обычный memmove/memcpy?

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

Или вы считаете, что все задачи уже решены, и надо просто играться в лего?

1. Объясните, почему вы использовали префиксный инкремент (в скобках справа) вместо более логичного постфиксного?
2. Зачем копировать, если нужно переписывать с затиранием. Копировать — грешно. Информация материальна. Использование копирования нарушает закон сохранения массы-энергии. Копирование это как рак. Громоздкое и ригидное нечто порождает.
3.

Ну а дальше чем больше таких случаев, тем сложнее код.

Именно так. Поэтому соревнование, «а давайте сделаем проще код» — это очень правильное соревнование.
Допустим на входе у нас разношерстная куча данных. Ну и пусть тогда каждая утилита (простая) только свой тип данных и отбирает и обрабатывает.
Поддержка универсального комбайна или поддержка гаечного ключа, собирающего различного рода комбайны и тракторы и планеры и даже наверное космические корабли... Что выберете?

1. Более логично очень условно, но если брать C++, то там есть разные итераторы, для которых инкремент переопределён. Переопределённый постфиксный ++ должен вернуть старый объект, и оптимизатор не всегда мог понять, что эти действия не нужны.

2. — 3. Вечный флейм.

Вот еще вариант ответа (из жизни): Купюры в миллион долларов используют редко поэтому: ru.wikipedia.org/wiki/Свободные_деньги
надо нещадно их демерджить)))
А вот «трудовые» рублики — 10-20-50-100 хай сохраняются подольше.
Вот такое прогрессивное налогообложение. И заметь, это лучшее предложение из всех, которые нам современная инфоматика предлагает.

Вы же огласите алгоритм коллега ? Потребление памяти интересует

Потребление памяти интересует

Потребление памяти растет почти линейно, без скачков. Оверхед, примерно как у хештаблиц x2-x3, это Worst Case (когда ключи короткие и они рандом). Есть и Best Case для HArray, если ключи часто совпадают по префиксу (урлы, пути, длинные слова и тд) то контейнер может работать как архиватор при этом insert, lookup будет еще быстрее.

В следующем примере каждый ключ 64 байта. В первом случае 64х байтные ключи похожи между собой, отличаются несколькими байтами. Во втором случае 64х байтные ключи рандом.
Результаты такие.
Оригинальный датасет => 5 млн * (64 байта ключ + 4 байта вэлью) = 340 mb

=== HArray VS google::dense_hash_map VS std::map VS std::ordinary_map testing ===
Insert/Search/Delete 5000000 SIMILAR keys (64 bytes each) ...
HArray => Insert: 1552 msec, Search: 1694 msec, Delete: 6089 msec, Memory: 413 mb.
std::map => Insert: 8809 msec, Search: 8908 msec.
std::unordered_map => Insert: 3694 msec, Search: 1188 msec.

Insert/Search/Delete 5000000 RANDOM keys (64 bytes each) ...
HArray => Insert: 1883 msec, Search: 1872 msec, Delete: 8258 msec, Memory: 749 mb.
std::map => Insert: 7774 msec, Search: 7583 msec.
std::unordered_map => Insert: 3648 msec, Search: 1197 msec.

Вот кстате кейс. Увеличили размер ключа с 64х байт до 128ми байт.
Итого
Оригинальный датасет => 5 млн * (128 байта ключ + 4 байта вэлью) = 660 mb

Insert/Search/Delete 5000000 SIMILAR keys (128 bytes each) ...
HArray => Insert: 1824 msec, Search: 1899 msec, Delete: 6619 msec, Memory: 413 mb.
std::map => Insert: 12319 msec, Search: 12531 msec.
std::unordered_map => Insert: 5222 msec, Search: 1782 msec.

Получили сжатие ключей на 30% от оригинального размера. Такой себе архиватор.
При этом в этом же кейсе, стандартная хештаблица будет потреблять памяти примерно 1-2 гб.
Тоесть в разы больше чем это делает HArray.

1) С Джуди скорость сравнивали? Если у Вас быстрее — можно писать статью в Overload, и на гите появятся последователи.
2) Как оно себя ведет, когда ключи разной длины? Например, разбить Гутенберга на предложения, и пнуть туда.

1) С Джуди скорость сравнивали? Если у Вас быстрее — можно писать статью в Overload, и на гите появятся последователи.

dou.ua/...​rums/topic/18849/#1006289
Но это вроде был HArray для интов. Для ключей переменной длины нужно мерять.

2) Как оно себя ведет, когда ключи разной длины? Например, разбить Гутенберга на предложения, и пнуть туда.

Шунтирует ветки и вставляет ключи разной длины в один и тотже контейнер.
Единственое все они выровнены по границе в 4 байта (сегмент).
Тоесть длины ключей могут быть 4, 8, 12, 16, 20 и тд байт.

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

Бизнес план:
1) Делаешь dual license типа этой www.pjsip.org/licensing.htm
2) Пишешь статью в Оверлоад или еще какой читаемый журнал со статьями в открытом доступе
3) Пихаешь статью на сайты по хай-лоаду, например ithare.com
4) Имеешь клиентов
5) Когда клиент хочет больше и качественнее, просишь 20К
6) Отдаешь 10К Горчаку, он пихает свой префетч в проблемное место, и клиенту хорошо
7) Еще можно отдать 5К мне, я за две недели перепишу половину кода, и в нем потом вообще никто не разберется

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

Монга уже раскручена. Ее долго выбивать с рынка, можешь не успеть до пенсии. А пропихнуть структуру данных, которая разгрузит сервера на 30% — это выглядит реальнее.

В данном случае Монга, это пробный шар на рынке документоориентированных баз данных. Такой себе FoxPro или Access, без транзакций, без аспектов, с ограничением на размер документов, без приличной скорости, без аналитических запросов.
За которым идет Oracle, его время просто еще не настало.

И зачем разработчикам переходить с монги...кстати куда переходить то?
Тут все пишут что код даже не читабельный :-)

Только не паникуй
ibb.co/Zh5Zkj4

PS: Это уже с ACID и транзакциями. Shapshot, Read commited, Repeatable read

Откуда эта картинка взята ?

en.wikipedia.org/wiki/Write-ahead_logging
Вот статья из картинки sj14.gitlab.io/post/2018/12-22-dbbench
Насколько я понимаю, SQLite рвет всех потому, что он однопоточный на запись, и не нужны мютексы и другая хрень.

Ясно, WAL означает что все должно влезть в РАМ, что позволительно для SQLite, но не оч. позволительно для баз более серьезных.
По этой же схеме работает Тарантул. По этой же схеме и моя база, но я буду от этого потихоньку избавлятся или комбинировать разные методы.

WAL означает что все должно влезть в РАМ

нет

нет

Формально нет, по факту да. Под нагрузкой WAL будет писать быстрее, чем он будет успевать мержится в основной индекс. Поэтому красивые картинки с WAL обычно где все лежит в RAM, а на диск попадет как нибудь потом.

WAL тоже пишет на диск в журнал — для того, чтобы не потерялись данные если система упадет во время трансакции.

Да, но эти данные должни попасть в

успевать мержится в основной индекс

на диске. Журнал существует чтобы восстанавливать хвост последних операций на диске, но не всю базу.

Ну так если дойдет до этого — то нужно мерять в бенчмарках что там реально происходит. Вырубить процесс и глянуть, сколько записей он восстанавливает из журнала. Если там реально SQLite будет сравним с твоей базой.

Я имел в виду — померять перформанс не на синтетических данных, а на реальном гиге реальных предложений из книжек. Может отличаться.

То о чем ты говоришь, уже реализовано. BH использует HArray для построения инвертированного индекса.
github.com/Bazist/BH
Другими словами в HArray лежит словарь.
В случае Либрусека словарь на сотни гиг или 400 тыс книг..
Скорость индексации там достаточно большая. Около 60 мб\сек чистого текста.

Так а как сравнить с другими имплементациями?

Не знаю, нужно ли. Везде есть свои особенности. В данном случае при индексации HArray под нагрузкой что на синтетических данных, что на словарях держит около 10м\сек запросов на поиск\вставку. В один поток.
На удачных имплементациях хештаблиц, скорость будет похожей.
Может отличатся на 20-30%, но не существенно.

Чтобы писать статью и делать шум нужно показать воспроизводимый эксперимент на реальных данных, как ты уделываешь всех самых крутых.
И базу продать трудно — там и надежность, и репликация, и дофига всего. А вот подсадить конторы на свою таблицу, и доить за поддержку нечитаемого кода — почему бы нет.
А потом, когда будут деньги и шумок за таблицу — можно и базу допилить и продавать.

JudyArray слетел с рынка по причине, что люди не понимают зачем писать такие сложные структуры если есть хештаблицы. Хештаблицу можно дотюнить до скоростей Judy или HArray.
Но есть область, где бинарные деревья и хештаблицы вообще никак не подходят. И эта область в документоориентированных базах данных.
Такого еще никто не делал, нужно копать сильно глубже.

Можно бить на то, что твоя структура разгрузит сервера по памяти и процу, в кеш влезет больше данных, и система будет работать быстрее на меньшем количестве железа. Вообще без труда от их программистов. То есть, они улучшают качество сервиса и одновременно уменьшают абонплату облаку.

Оно то может и так. Но мы живем в неидеальном мире.
Даже вот по гугловской либе
github.com/...​blob/master/Benchmarks.md
dense_hash_map делает std::map как Бог черепаху.
Как ты думаешь, все бросились менять std::map на dense_hash_map ? Конечно нет. Интересен прикладной софт, а структура да хороша, но ее еще нужно правильно применить, где раскроются все ее лучшие стороны.

Может, dense_hash_map недостаточно рекламируют? Тем более, std::map это уже прошлое тысячелетие. В стандарте давно unordered_map.

Если влепить твою структуру в memcached и показать, что размер и скорость кеша увеличились на той же памяти, и поездить по короноконференциям — вполне можешь получить заказчиков, а потом на следующих выставках — хвастаться, что Нетфликс юзает твой софт.

Кстати, вот чувак писал свой кеш.
dou.ua/...​/?from=similar_posts_tech
Спроси, чем у него все закончилось. Может, расскажет про грабли, или историю успеха.

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

о распределенных базах знаний

Веб 3.0. Который хз когда еще придет.
www.e-xecutive.ru/wiki/index.php/Веб_3.0

Распределенные неопределенности чем-то похожи на материал, а когда они, квантово запутанные (например, утиной типизацией), встречаются с определителем то становятся материей. Веществом.
Мы скоро начнем создавать виртуальное вещество из нашего кода)))

zip читати вміє? можна буде натравити на локальну базу флібусти?

Прорыв у вас? Потому что волновая функция у нас теперь совпадает по некоторым параметрам. Наверное. Одно дело делаем.

Олег, эта тема не выдержит двух поехавших :)

Ухожу, ухожу. Коммунальные надо заплатить, паспорт переоформить... Мои посты в помощь. Их даже можно просто как набор ключевых слов для активизации определенных областей нейронов использовать

Круто було б якби ти якийсь враппер зробив щоб твої коллекції можна було як SLT-коллекції юзати. Тоді можна було б написати простий тест для порівняння HArray з std::map, boost::hash_map та іншими. І хто завгодно міг би ці тести запустити будь-де за наявності С+±компілятора.

Бубен, я решил посмотреть как твой алгоритм сравнится со стандартной std::collections::HashMap

Делал только один бенчмарк — HArrayInt_VS_StdMap_IntKey, только с последовательными числами.

Код:
play.rust-lang.org/...​65150cc6fd17bcdbc7a352f46

Если будешь пытаться запустить на том веб-сайте Sandbox, переключи в режим Release, понизь кол-во итераций в 10 раз, и учти, что работать будет медленно, так как Sandbox работает на слабых виртуалках и не подходит для бенчмарка.

Бенчмарк запускал на Windows 10, Intel Core i9-9880H @2.3 GHz.

Rust в режиме release с включенной lto. Мой результат:

Keys count: 0, elapsed: 0
Keys count: 10000000, elapsed: 111
Keys count: 20000000, elapsed: 214
Keys count: 30000000, elapsed: 336
Keys count: 40000000, elapsed: 463
Keys count: 50000000, elapsed: 545
Keys count: 60000000, elapsed: 653
Keys count: 70000000, elapsed: 808
Keys count: 80000000, elapsed: 892
Keys count: 90000000, elapsed: 978
Keys count: 100000000, elapsed: 1085

В твоем коде я увеличил кол-во итераций, чтоб была равна моему, и закомментировал бенчмарки на сторонние хеш-таблицы:

	HArrayInt_VS_StdMap_IntKey(0,   //start
								10000000,   //step
								100000000); //stop
	for (uint32 countKeys = startOnAmount; countKeys <= stopOnAmount; countKeys += stepOfAmount)
	{
		printf("Insert/Search %u SEQUENCE keys (%u bytes each) ...\n", countKeys, sizeof(uint32));
		testHArrayInt(intKeys, countKeys);
		//testDenseHashMapInt(intKeys, countKeys);
		//testStdMapInt(intKeys, countKeys);
		//testStdUnorderedMapInt(intKeys, countKeys);
		printf("\n");
	}

Запускал твой код из-под Visual Studio в режиме Release/x64, без отладчика. Результат:

=== HArrayInt VS google::dense_hash_map<int,int> VS std::map<int,int> VS std::ordinary_map<int,int> testing===
Insert/Search 0 SEQUENCE keys (4 bytes each) ...
HArrayInt => Insert: 0 msec, Search: 0 msec.

Insert/Search 10000000 SEQUENCE keys (4 bytes each) ...
HArrayInt => Insert: 105 msec, Search: 32 msec.

Insert/Search 20000000 SEQUENCE keys (4 bytes each) ...
HArrayInt => Insert: 243 msec, Search: 90 msec.

Insert/Search 30000000 SEQUENCE keys (4 bytes each) ...
HArrayInt => Insert: 327 msec, Search: 110 msec.

Insert/Search 40000000 SEQUENCE keys (4 bytes each) ...
HArrayInt => Insert: 429 msec, Search: 131 msec.

Insert/Search 50000000 SEQUENCE keys (4 bytes each) ...
HArrayInt => Insert: 560 msec, Search: 158 msec.

Insert/Search 60000000 SEQUENCE keys (4 bytes each) ...
HArrayInt => Insert: 659 msec, Search: 192 msec.

Insert/Search 70000000 SEQUENCE keys (4 bytes each) ...
HArrayInt =>
C:\src\HArray\Release\HArray.exe (process 22280) exited with code -1073741819.
Press any key to close this window . . .

На 70 миллионов ключей твоя программа падает, почему не разбирался.

Сводная таблица

HArrayInt_VS_StdMap_IntKey / SEQUENCE_TESTS

keys count	    rust hashmap, ms	harrayint, ms
10000000        95                  105
20000000        192                 243
30000000        270	                327
40000000        374	                429
50000000        448	                560
60000000        572	                659
70000000        644	                error
80000000        726	                error
90000000        849	                error
100000000       957                 error

HArray сливает std::collections::HashMap по скорости insert/lookup 11-27% и вдобавок крашится на больших объемах данных.

Во-первых, сиквенц это ворст кейс для HArrayInt.
github.com/...​p_seq_32bits.png?raw=true
Во-вторых, ты сравниваешь структуры с сильно разной функциональностью. HArrayInt сортирует данные при вставки и предоставляет запросы типо вернуть ключи по ренжам, обойти сортированный список. Хештаблица ничего не сортирует и сохраняет как хеш пошлет.
В-третьих, Данные сильно синтетические. Возьми рандом. И если добавляешь 100 млн ключей, то возьми передай в конструторе сапасити как
HArrayInt ha;
ha.init(27);
или
ha.init(28);

и перемеряй.

ha.init(27);
или
ha.init(28);

Что эти магические цифры обозначают Почему 28 а не 100? Почему нет никакого нормального описания аргументов?

В ридми есть такое описание
HArray ha;
ha.init(); //ha.init(24) set your custom capacity for big datasets

Оно говорит каким будет размер хедера
2^24*4 байт

Я заменил

github.com/...​aster/HArray/Main.cpp#L77

	ha.init(26);

на

	ha.init(26);

теперь падает в самом начале, еще до того как я добавил какие-либо ключи

=== HArrayInt VS google::dense_hash_map<int,int> VS std::map<int,int> VS std::ordinary_map<int,int> testing===
Insert/Search 0 SEQUENCE keys (4 bytes each) ...
HArrayInt =>
C:\src\HArray\Release\HArray.exe (process 13500) exited with code -1073740791.
Press any key to close this window . . .

Бубен, библиотека очень косячная, как ты ее тестил?

ha.init(26);
на
ha.init(26);

Не совсем понял. Зачем 26 менять на 26 ?

Только что на моем ноуте iCore7, RAM 16gb
=== HArrayInt VS google::dense_hash_map VS std::map VS std::ordinary_map testing===
Insert/Search 70000000 SEQUENCE keys (4 bytes each) ...
HArrayInt => Insert: 1395 msec, Search: 297 msec.

std::map улетела с эрором. Наверно памяти не хватило.

Не совсем понял. Зачем 26 менять на 26 ?

Поменял на 28, опечатка была в сообщении. Твой код падает с ошибкой, которую я привел.

Если у тебя сиквенц последовательность. То значение можешь вообще 20 поставить :)
Там от хедера ничего не зависит. Только лишняя память. Worst Case всетаки.

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

Да, сорри, допишу документацию по этому параметру. Он единственный магический. Дефолт там 26 обычно его хватает.
По твоему кейсу я поставил

ha.init(20);

И HArrayInt выжило до 100 млн ключей

=== HArrayInt VS google::dense_hash_map VS std::map VS std::ordinary_map testing===
Insert/Search 10000000 SEQUENCE keys (4 bytes each) ...
HArrayInt => Insert: 169 msec, Search: 86 msec.

Insert/Search 20000000 SEQUENCE keys (4 bytes each) ...
HArrayInt => Insert: 372 msec, Search: 98 msec.

Insert/Search 30000000 SEQUENCE keys (4 bytes each) ...
HArrayInt => Insert: 509 msec, Search: 148 msec.

Insert/Search 40000000 SEQUENCE keys (4 bytes each) ...
HArrayInt => Insert: 686 msec, Search: 247 msec.

Insert/Search 50000000 SEQUENCE keys (4 bytes each) ...
HArrayInt => Insert: 850 msec, Search: 246 msec.

Insert/Search 60000000 SEQUENCE keys (4 bytes each) ...
HArrayInt => Insert: 1066 msec, Search: 296 msec.

Insert/Search 70000000 SEQUENCE keys (4 bytes each) ...
HArrayInt => Insert: 1184 msec, Search: 345 msec.

Insert/Search 80000000 SEQUENCE keys (4 bytes each) ...
HArrayInt => Insert: 1340 msec, Search: 386 msec.

Insert/Search 90000000 SEQUENCE keys (4 bytes each) ...
HArrayInt => Insert: 1533 msec, Search: 444 msec.

Insert/Search 100000000 SEQUENCE keys (4 bytes each) ...
HArrayInt => Insert: 1682 msec, Search: 493 msec.

По твоему кейсу я поставил

ha.init(20);

Ты вообще знаешь что этот параметр делает и как он работает, или рандомно подбираешь пока не заработает? :)

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

Теперь у меня твой код работате на 100 миллионов.

Я еще выяснил, что я по-ошибке неправильно считал время. Мой бенчмарк выдает total время (insert + lookup), а твой отдельно Insert и отдельно Lookup. Я недоглядял и брал только Lookup время из твоего вывода.

Вот поправил результаты:

keys count  rust hashmap ,insert  harrayint, insert	
10000000    64                    96
20000000    118                   208
30000000    180                   307
40000000    229                   386
50000000    315                   478
60000000    373                   582
70000000    412                   704
80000000    475                   790
90000000    571                   872
100000000   596                   985

keys count  rust hashmap, lookup  harrayint, lookup
10000000    24                    32
20000000    49                    72
30000000    74                    97
40000000    96                    128
50000000    125                   163
60000000    151                   190
70000000    170                   222
80000000    231                   255
90000000    237                   290
100000000   276                   309

HArray в среднем работает на 63% дольше на вставке и 28% дольше на lookup.

К сожалению не могу твой раст померять.
Получается твой раст работает в 2 раза быстрее чем dense_hash_map или unordered_map
Я в это слабо верю, в чемто есть подвох. Может он детектит что это просто монотонная последовательность и просто херачит в массив. Это нечестная игра синтетического теста.

А вообще я на этот вопрос отвечал. Сравнивать нужно экскаваторы с экскаваторами, а не автобусы с поездами

Во-первых, сиквенц это ворст кейс для HArrayInt.
github.com/...​p_seq_32bits.png?raw=true
Во-вторых, ты сравниваешь структуры с сильно разной функциональностью. HArrayInt сортирует данные при вставки и предоставляет запросы типо вернуть ключи по ренжам, обойти сортированный список. Хештаблица ничего не сортирует и сохраняет как хеш пошлет.
Я в это слабо верю, в чемто есть подвох.

Лол. Разумеется, во всех тестах, в которых Бубен слил, есть какой-то подвох. Во всех тестах, где Бубен выиграл все было честно :)

Может он детектит что это просто монотонная последовательность и просто херачит в массив.

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

Но у меня есть тебе утешение. Rust использует LLVM на бекенде. Так же как и clang. Сделай так чтоб твой код компилился под clang и посмотрим, получит ли твой код такой же буст от оптимизаций или нет.

Я в это слабо верю, в чемто есть подвох. Может он детектит что это просто монотонная последовательность и просто херачит в массив. Это нечестная игра синтетического теста.

— Benchmarks are rigged!
— If you count benchmark legal results, we easily win. If you count illegal benchmark times, they can try to steal victory from us.
— We were winning in all the key benchmarks by a lot, actually. And then our number started miraculously getting whittled away in secret.
— ANY BENCHMARK THAT CAME IN AFTER JANUARY 24TH WILL NOT BE COUNTED!
— STOP THE PERFORMANCE TESTS!

А вообще я на этот вопрос отвечал. Сравнивать нужно экскаваторы с экскаваторами, а не автобусы с поездами

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

При этом тот, кто тестит map на вставке 4-байтного ключа и значения жалуется на то, что тесты синтетические :)

То, что кол-во ключей заранее известно, позволяет получить еще лучше перформанс и это офигенно.

Ты лучше объясни почему твой код сливает и на вставке и на lookup?

Тю, не заметил. Так ты тут читишь
let mut map = HashMap::with_capacity_and_hasher(keys_count, NoopHasherBuilder {});

Передаешь размер хештаблицы в конструкторе.
Тоесть твой мап ОДИН РАЗ выделает большой кусок памяти на все элементы и сразу. Это синтетика.

В то время как HArrayInt не знает количества вставляемых элементов и честно растет в размерах (вызывая раз за разом тормознутый new()) в зависимости от того сколько элементов добавили.

Я изменил эту строчку, поставил сапасити 0 (в начале теста не известно количество вставляемых ключей) и твой Раст деградировал почти в 1.5 — 2 раза :)

play.rust-lang.org/...​65150cc6fd17bcdbc7a352f46

Если схитрить и передать в конструктор количество вставляемых ключей

let mut map = HashMap::with_capacity_and_hasher(keys_count, NoopHasherBuilder {});

Keys count: 0, elapsed ms: 0
Keys count: 1000000, elapsed ms: 27
Keys count: 2000000, elapsed ms: 54
Keys count: 3000000, elapsed ms: 80
Keys count: 4000000, elapsed ms: 110
Keys count: 5000000, elapsed ms: 137
Keys count: 6000000, elapsed ms: 159
Keys count: 7000000, elapsed ms: 185
Keys count: 8000000, elapsed ms: 208
Keys count: 9000000, elapsed ms: 299
Keys count: 10000000, elapsed ms: 245

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

let mut map = HashMap::with_capacity_and_hasher(0, NoopHasherBuilder {});

Keys count: 0, elapsed ms: 0
Keys count: 1000000, elapsed ms: 41
Keys count: 2000000, elapsed ms: 84
Keys count: 3000000, elapsed ms: 101
Keys count: 4000000, elapsed ms: 200
Keys count: 5000000, elapsed ms: 189
Keys count: 6000000, elapsed ms: 205
Keys count: 7000000, elapsed ms: 220
Keys count: 8000000, elapsed ms: 341
Keys count: 9000000, elapsed ms: 359
Keys count: 10000000, elapsed ms: 519

Тоесть Хешмап в Расте проигрывает как по функциональности, так и по скорости HArrayInt при равных условиях.

Тю, не заметил. Так ты тут читишь
let mut map = HashMap::with_capacity_and_hasher(keys_count, NoopHasherBuilder {});

Передаешь размер хештаблицы в конструкторе.
Тоесть твой мап ОДИН РАЗ выделает большой кусок памяти на все элементы и сразу. Это синтетика.

В чем синтетика? Кол-во ключей известно заранее. Не вижу проблемы в том, чтоб задать его, если структура выиграет в перформансе от этого. У тебя тоже есть какие-то магические константы, которые нужно тюнить в зависимости от входных данных. Почему честно когда твой код это требует и нечестно когда мой код это требует?

В то время как HArrayInt не знает количества вставляемых элементов и честно растет в размерах (вызывая раз за разом тормознутый new()) в зависимости от того сколько элементов добавили.

Никто тебе не мешал добавить API, который позволит задать кол-во элементов заранее, чтоб твой код выиграл по перформансу.

В чем синтетика? Кол-во ключей известно заранее.

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

У тебя тоже есть какие-то магические константы, которые нужно тюнить в зависимости от входных данных. Почему честно когда твой код это требует и нечестно когда мой код это требует?

На этих магических константах мой код отжирает на порядки менььше памяти на старте чем поделка из раста

Никто тебе не мешал добавить API, который позволит задать кол-во элементов заранее, чтоб твой код выиграл по перформансу.

Никто не мешает твоей Хешмапе предоставить следующие Апи:
1. Скан ключей по диапазону
2. Скан ключей как сортированный список
3. Поиск ключа по подстроке
4. Удаление ключа с плавным освобождением памяти

Мы к этому вернемся. Ты сначала скажи, ты признаешь, что твоя поделка сливает Rust std::collections::HashMap на lookup?

Ты сначала скажи, ты признаешь, что твоя поделка сливает Rust std::collections::HashMap на lookup?

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

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

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

Мы к этому вернемся. Ты сначала скажи, ты признаешь, что твоя поделка сливает Rust std::collections::HashMap на lookup?

Обьясняется тем что хештаблица в некоторых случах может быть делать меньше seek times. За счет того, что ключи разместила совершенно случайно, а не как сортированный список.

Но к слову сказать, самые первые версии контейнера работали в раза полтора быстрее. Но они не могли удалять ключи и ключи были фиксированой длины. Потом я добавил оверхед на эту ф-сть и скорость чуть подупала. Но не критично.

Мы к этому вернемся.

А что там возвращатся.
Читай список приимуществ HArray по сравнению с хештаблицами

1. Without any Stop World events such as Rebuild/Rehashing on Insert key.
2. Without any Hash Functions, the container has adpative algorithm for different nature of keys
3. Scan by Prefix/Scan by Range functionality as bonus
4. All Keys are sorted. Ability to set your Custom Order of Keys
5. Predictable behaviour even in worst case: smoothly consuming memory, almost constantly latency on insert/lookup
6. Prefix Compression helps reduce memory when keys have the same prefix: urls, file paths, words etc.
7. Serialize/Deserialize from/to file at a speed close to the max speed of the hard drive
8. Fair Delete operation with smoothly dismantling each Key. Dead fibres are used for insert new keys, so structure perfect works in massive insert/delete scenarios.

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

Поэтому пока ты не признаешь слив своей поделки на lookup (что продемонстрирует наличие базовой адекватности и понимания того, что происходит под капотом), мы дальше говорить не будем.

Поэтому, повторю вопрос:

Ты сначала скажи, ты признаешь, что твоя поделка сливает Rust std::collections::HashMap на lookup?

Ты так истеришь, как будто это ты лично эту хешмапу писал, а не какойто 50ти летний бородатый джедай, которому явно не нужно выпрашивать принципала. Ладно.

Вот тебе базовая адекватность. Еще на примере JudyArray (Trie) стало понятно, что в любой хештаблице можно подобрать такую хешфункцию, при которой JudyArray будет немного, но проигрывать по скорости хештаблице. При этом JudyArray (как и HArray, более совершенная версия) имеет другой список приимуществ, которые напрямую открывают путь в мир больших баз данных
dou.ua/...​rums/topic/18849/#2044934

Сам же по себе Trie это крайне изящная и красивая (хоть и сложная в реализации) структура, которая намного более приближена к биологическому миру с его ДНК и прочьими клевыми штуками. По сравнению с изяществом таких структур, которые красиво внутри разворачиваются и эволюционируют в ответ на прессинг вставки ключей, хештаблицы выглядят как каструбатое криптографическое фуфло. Которое не имеет каких либо аналогий в биологическом мире, что какбе намекает на их ценность как архитектурного шаблона. Если ты понимаешь, конечно, о чем я.

До речі було б дивно якби не зливала... Просто HashMap має дуже мало обмежень в порівнянні з його HArray’єм. Просто в HashMap’і лук-ап взагалі повинен відбуватись за пару процесорних інструкцій (ну ... + колізії) — таке важко побороти.

В чем синтетика?
Никто тебе не мешал добавить API, который позволит задать кол-во элементов заранее, чтоб твой код выиграл по перформансу.

«не все так просто» ©. В векторі reserve має сенс, в хеш-таблицях теж. В зв’язних списках і червоно-чорних деревах немає.

Я там вище написав що проблему великої кількості new() можна обійти зробивши можливість додати свій кастомний аллокатор ( en.wikipedia.org/wiki/Allocator_(C++ ), але перед тим треба би результати профайлу глянути.

В то время как HArrayInt не знает количества вставляемых элементов и честно растет в размерах (вызывая раз за разом тормознутый new())

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

Это не костыль. Это норм поведение структуры, которая не знает сколько памяти ей понадобится. Какой природы будут ключи. Будут сначала вставки или вставки и поиск идти вперешку. Ключи будут одной длины или разной. И ещё много других кондишенов.

Если бы я хотел сделать твой некостыль, для синтетических структур, я бы в конструкторе передал количество ключей, а потом типа понял что ты вставляешь числа последовательно и просто заполнил массив и сделал твою хешмапу в 5 раз по скорости. Заняло бы 10 строчек кода.

Но я так не сделал и написал максимально сбалансированную и универсальную структуру данных в 8к строк, которая выживает в любых боевых условиях. Которая ведёт себя максимально предсказуемо в разных корнер кейсах за О(1). Чего не скажешь о хештаблице с ее O(n) в худшем случае.

Чего не скажешь о хештаблице с ее O(n) в худшем случае.

Совершенно не обязательно: реализации хэш-таблиц, которые не делают перемещение всех ключей рывком, а делают это по 1-2 дополнительных ключа на каждую операцию добавления — достаточно распространены (например, в MSVC STL).

(возражение только в этом пункте)

Пока автор не выложит white paper, не о чем говорить, так как непонятно что именно и как много он выделяет и где можно оптимизировать, а по коду хрен разберет что он там наколбасил. Ему никто не мешает добавить возможность выделить всю память заранее и получить более высокий перфонмарс, если кол-во ключей известно (а оно известно), как это сделано практически в любом годном контейнере для элементов.

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

Насправді, для ліста та balanced BST, зазвичай, можна пам’ять виділити наперед і скористатись кастомними алокаторами, так шо new буде практично placement new (шо є no op у випадку інтів). За допомогою пулу, власне. Для trie така оптимізація теж, загалом, можлива, думаю і для даного trie теж. Тільки дещо морока це робити.

О. Я про це теж писав. Треба було мені перечитати все (лол) перед тим як самому вкидувати на вентилятор.

Не понял этот момент. Если принципиально структура построена так, что «превыделить» память невозможно (как LinkedList и BinaryTree), как можно ее выделить и получить буст к перформансу?

Например, в случае c linkedlist, если знаешь сколько нужно будет хранить элементов максимум, можно выделить заранее память под них большим куском и аллоцировать память оттуда кастомным мемпулом или чем-то аналогичным. В особо задроченых вариантах, без поддержки многопоточности, alloc (или free) можно будет сделать 2-3 инструкциями.

Или, например, std:set это не годный контейнер?

Не большой спец по С++, но быстрый поиск показывает, что std::set параметризируется типом аллокатора, т.е. при желании туда можно будет засунуть аллокатор на базе мемпула (если он там не встроен в конкретной реализации).

Вот пример:

referencesource.microsoft.com/...​/generic/dictionary.cs,61
referencesource.microsoft.com/...​generic/dictionary.cs,315

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

Це оптимізує тільки виділення/видалення елементів. Тому що виділити та видалити пам’ять це, загалом, нетривіальна операція. На пошук воно не дуже вплине, хіба що більш щільне розташування елементів може призвести до меншої кількості cache miss.

Понимаешь, какая штука: мозг умеет обрабатывать будущие события — подготавливает в голове реакции на разные альтернативные события — несколько вариантов, а твой процессор нет. А должен бы, ведь в ограниченной модели легче, чем в мозгу. Правда у мозга много нейронов, а у процессора с гулькин нос.
Извини, не удержался подразнить немного...

З linked list можна зробити фокус коли певна кількість елементів живе у нерозривному блоку пам’яті і при необхідності додається новий блок. Тобто всередині замість щоб кожен елемент вказував на наступний більша кількість елементів йде послідовно.

Морока буде позначати елементи як видалені і робити кастомний ітератор.

Тут проблема ИМХО в понимании области применения. По сути связный список необходим только для того, чтобы организовать в FIFO/LIFO очередь (например, события различные) некоторые элементы при условии, что мы не будем по ним бегать туда-сюда, тогда расположение в памяти элементов не имеет значения, последовательно или рандомно, мы работаем с одним элементом и может перейти к следующему или пушнуть элемент в голову списка. Если в списке оказываются больше дюжины элементов одновременно, то что-то пошло не так и организация данных выбрана неправильно.

Тут проблема ИМХО в понимании области применения.

Наприклад задача видавати ID з пулу. Їх можна повертати у довільному порядку назад в пул і гарантовано буде «переповнення» коли треба буде використовувати раніше видані, але вже звільнені ID. І якщо треба зробити за менше ніж O(n) часу та бажано менші ніж O(n) пам’яті то така модифікація списку блоками одночасно і проста для реалізації і дає виграш в швидкості як мінімум.

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

Это не будет работать в С++ с кучей мелких new вызовов. В стандартных библиотеках используют арены — это кусок памяти небольшого размера (64-1024Кб) в котором происходят аллокации. Как только память заканчивается, выделяется новая арена. Внутри арена может быть разбита на bit buckets, а не просто списки и т.д. Чистый список — это самоубийство.

Вы же там говорили про выделение хендлов. Вот как раз можно завести список свободных хендлов.
Пулы памяти хороши (правда, мне от них страшно) когда приходит момент, в который этот можно сбросить — то есть, программа выполняет циклические действия, вроде обработки запросов.

Для хэндлов хороши битмаски, например реализация IDR/IDA хендлов линуксовом ядре очень приятно сделана + если лицензия позволяет — оно отрывается от ядра линукса на раз-два-три и можно использовать в своих проектах:
www.kernel.org/...​/latest/core-api/idr.html

По поводу пулов памяти, опять же мне очень нравится реализация kmem_cache***() в линуксовом ядре, всё очень продуманно, есть даже конструкторы объектов в кеше/пуле, что инициализировать элементы перед тем как отдавать юзеру. Причём я не знаю кто был первым, но в ядре Solaris есть точно такое же API:

Solaris: docs.oracle.com/...​kmem-cache-create-9f.html
Linux: www.kernel.org/...​rstand/understand025.html

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

Спасибо, но мне как плюсовику-затейнику сложно(
Отложу пока не прийдется самому его писать

Как это повлияет, например, на перфоманс того же lookup?

На lookup в теории влияние будет слабое. Например, раз все узлы linked list аллоцированы из одного блока памяти, будет выше шанс на CPU cache hit или на TLB cache hit, чем если они аллоцировались из рандомных мест в куче втечене жизни программы, но все это сильно зависит от типа нагрузки и патерна доступа к данным.

Наибольший эфект будет проявляться в местах, где аллоцируется/освобождается память.

И на языки без сборки мусора, например С++?

Вполне позитивно повлияет, так как вместо аллокации/освобождения большого кол-ва маленьких блоков памяти (что имеет условно константные затраты по времени вне зависимости от размера блока) будет одна аллокация большого блока памяти. в начале работы программы. Ну и не будет фрагментации кучи, что тоже плюс.

На lookup в теории влияние будет слабое. Например, раз все узлы linked list аллоцированы из одного блока памяти, будет выше шанс на CPU cache hit или на TLB cache hit

Для linked list будет очень сильное влияние, т.к. процессор не может предсказать рандомные обращения к памяти, а вот последовательные аж бегом. А вообще, парни, вы идёте правильной дорогой, не ожидал столько правильных мыслей в этом треде. Ещё чуть-чуть и будет понимание почему Интел аж в 1995 в Pentium Pro добавил поддержку 2Mb страниц вместо 4Kb.

Таблицы для MMU находятся в таких же страницах памяти и если аллокаций по 4Kb блоков будет много, то каждое последовательное выделение памяти и добавление её в адресное пространство процесса будет всё медленнее и медленнее из-за растущих таблиц MMU.

Із цікавого — код читабельний, але взагалі не перегружений коментарями і чуваки схоже взагалі не чули про стайл чекери. Із плюсів — взагалі немає єрунди, коли заставляють використовувати такий стиль:

if (...)
{
    return 1;
}
else
{
    return 2;
}
— ну от не хочу я ультравайд вертикально ставити щоб з таким кодом працювати, пробачте.

І взагалі ... народ любить писати return в тому ж рядку, що і if:

if (...) return 1;
return 2;

Але те, що в коді деколи попадається пробєл після відкриваючої дужки в if (рядок 425), або те, що народ від фонаря ставить пробєли навколо == трохи дивує :).

Але те, що в коді деколи попадається пробєл після відкриваючої дужки в if (рядок 425)

Там просто по рукам мало били, нет общего стиля.

або те, що народ від фонаря ставить пробєли навколо == трохи дивує :).

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

Я часто ставлю пробєли як логічне групування:

d = b*b - 4*a*c
место аллокации элементов этого связного списка в куче (что будет медленно но уверенно херить кучу и усложнять работу сборщика мусора)

Це не тільки для цього зроблено :-). Більшою мірою для того, щоб можна було пройтись по всіх елементах мапи за «не дуже дорого».

Власне є такий жарт, що якщо ти маєш популярний продукт, то implementation стане specification. Тобто навіть якщо ти явно кажеш, що щось там unspecified/undocumented, то всерівно найдеться народ, який буде покладатись на цю фішку. І навіть не зважаючи на те, що народ явно робить єрунду, вони потім зляться коли їхня прога глючить.

Починаючи з якоїсь версії пітон реалізовував dict так, що ітерація по dict’у повертала ключі в тому порядку, в якому їх вставляли. Народ почав настільки полагатись на цю штуку, що її прийшлось додати цю фішку в специфікацію (починаючи з 3.7). І тепер прийдеться завжди тягнути це за собою.

Автори Го настільки люблять свою свободу, що самі шафлять ключі, щоб якийсь мудак не почав покладатись на якісь деталі реалізації:
play.golang.com/p/ev19NzZv0gD

вызывая раз за разом тормознутый new()

Так ето. Ти б результати профайлу привів, їй богу. Просто говорити що на new() йде багато часу без профайлу якось тупо, імхо. Просто якщо виявиться що new() займає 5%, то якось буде неловко.

По-друге зроби як всі людські контейнери СТЛ — прийми додатковим параметром (можна параметром шаблону) аллокатор. Це тобі дасть змогу наперед виділити N*sizeof(Node) байт під твої вузли і тоді, при потребі, new буде працювати дуже швидко. Знову ж таки перед тим як займатись цією штукою було б непогано показати результат профайлу — куди час зараз йде?

Пофиксил error.
Впринципе это какбы кновн ишью, пул закончился.
Поставил константу 2048 вместо 1024
const uint32 INIT_MAX_PAGES = 2048;

Позже надо будет авто resize прикрутить, для любителей засунуть от 70 млн секвенц ключей и потестить Worst Case HArrayInt

Я сделал git pull, проверил что INIT_MAX_PAGES теперь 2048, пересобрал, все равно падает.

Insert/Search 70000000 SEQUENCE keys (4 bytes each) ...
HArrayInt =>
C:\src\HArray\Release\HArray.exe (process 52992) exited with code -1073740791.
Press any key to close this window . . .

Пофикси багу и проверь что пофиксилось, выложи вывод программы, потом я еще раз попробую.

Я предлагаю тестить на датасетах до 50 млн ключей.
На 50 млн и выше у меня и стандартные либы (std::map, std::unordered_map)
с аутофмемори мрут.
А HArrayInt мрет гдето на 80 млн ключей, на моей машине.

Я вижу, что мрет. Наверное, надо разобраться почему? 80 миллионов ключей + значений каждое по 4 байта это 640МБ. Сколько дополнительно твоя структура жрет, что хранение такого кол-ва данных в памяти это проблема на моем компьютере с 64ГБ памяти?

Я вижу, что мрет. Наверное, надо разобраться почему? 80 миллионов ключей + значений каждое по 4 байта это 640МБ.

Забыл про 4 байта на велью. Это 1.3 гб. Оверхед гдето х2-х3 также как у хештаблицы.

Сколько дополнительно твоя структура жрет, что хранение такого кол-ва данных в памяти это проблема на моем компьютере с 64ГБ памяти?

Проблема что ты сбилдил как х32 битное приложение. А ему не отдадут больше 4 гиг.
Я только что сбилдил как х64, легко влезло 130 млн ключей.
Когдато помню архитектор с канады тестил, у него сказал влезло 1 млрд ключей.
Но там какаято непростая машинка была. Не ноут с 16 гб озу как у меня.

Проблема что ты сбилдил как х32 битное приложение. А ему не отдадут больше 4 гиг.

Я уже писал тебе, что в настройках сборки выбрал Release/x64.

Твой код падал задолго до того как достигает 4 гигов памяти.

Но там какаято непростая машинка была. Не ноут с 16 гб озу.

У меня тоже непростая машинка

Забыл про 4 байта на велью. Это 1.3 гб. Оверхед гдето х2-х3 также как у хештаблицы.

Сколько будет 80000000 * (4 + 4) ?

Эх, жаль, такой эпик срач пропустил. ТС, чем там сердце успокоилось? Допилил свой алгоритм? Если че, могу помочь с оптимизацией и кросс-платформенностью.

С этим алгоритмом проблем нет, он допилен и портирован и под линукс и под виндовс. Конечно нет предела совершенству, можно потратить и добрать в бенчмарках еще 10-20-30%, но сейчас это уже не интересно. Сейчас интересно этот же алгоритм адаптировать под хранение джисонов в базе данных. Там очень жирная теория получается, если в Trie хранить Json. Сжатие в 20-30 раз по дефолту за счёт инвертации данных, вставки секций джисона не приводят к его полной перезаписи, транзакции с блокировкой на уровне атрибутов и др. К сожалению времени очень не хватает, поэтому я только теорией занимаюсь, код не пишу. Хочу применить весь опыт и наработки, продумать и просчитать каждую деталь. Поэтому если интересно, писать ничего не нужно, есть алгоритмические задачи на подумать.

Ну если сможешь так поставить задачу чтобы я сходу врубился в условие — обещаю подумать на досуге. В качестве разминки для мозгов.

Ок, давай во вторник, по прилёту доберусь до своего блокнотика, там все по этому проекту, напишу развернутый пост. Спасибо что написал, лишний повод собраться и продолжить работу.

Дописал чесную функцию delete.
Если процесс вставки ключей в чемто напоминает процесс эволюции,
где свою жизнь ключ начинает как предельно простая примтивная конструкция,
постепенно усложнаяясь, разветвляясь и «эволюционируя» в серию блоков,
то при удаление идет полностью обратный процесс. Процесс деградации и распада на примитивы, которые в свою очередь могут быть использованы для построения новых структур (ключей). Таким образом если количество insert больше чем операций delete или их количество примерно равно, событие Stop World не происходит. Если количество операций delete значительно превышает количество операций insert, то контейнер в какойто момент определяет что может высвободить не менее 5% памяти и запускает процесс сборки муссора/дефрагментации, после которого отдает высвобожденные страницы памяти ОСи.

Также добавил возможность сериализации/десериализации на диск
и возможность задавать кастомные сортировки в структуре.

Такой пост уже приятно читать.
Я твоим не пользуюсь пока, потому что мне оно пока нигде не нужно. Но в закладки закинул.

Добавил побольше красивых графиков и таблиц
github.com/Bazist/HArray

О, уже приятно смотрится страничка. Добавил бы еще пару слов об своем алгоритме там. Тем кто зайдет будет яснее, что именно ты представляешь.

Ну вот както так, для бегинерз если основная идея
github.com/...ter/Trie_for_beginners.md

Пока что драфт, потом подправим.

Небольшой апдейт по проекту.
1. Унифицировал проект, теперь он компилится одинаково хорошо под Linux и под Windows из одних и тех же исходников.

2. Попытался с наскоку ввести элементы прямой адрессации. Потратил несколько вечеров чтобы сделать пруф-оф-концепт, неосилил. Точней осилил, но версия работает медленее чем текущая. Пока откладываем, но в уме держим, что всетаки теор. предел еще не достигнут.

3. Имел честь на прошлой неделе пободаться с Гордостью Всея Гугла — dense hash map. Надо сказать что в немалом количестве кейсов всетаки слил, на глаз счет 50/50 по всей той простыне бенчмарков. Конечно это был не совсем равноценный замер. и можно было сразу послать денсу в лес, поскольку мой Trie это честное поедсказуемое отсортированое дерево. Отсюда сканы по диапазону ключа, функции min max, префиксное сжатие, ровное наращивание памяти, отсудствие катастрофических worst cases (в некоторыъх случаях dense просто подвисала намертво, не так то просто подобрать хешфункцию). Из-за своей непредсказуемости и скудного функционала использовании хештаблиц в базах данных практически не имеет смысла.

4. Но я не сдался ! Кручу в голове потихоньку и прицениваюсь к созданию вариатора размера блоков. Это займет какоето время. В теории всеравно хорошо оптимизированое Trie должно работать быстрее чем Хештаблицы и уж тем более чем любые подвиды бинарных деревьев.

Думаю что с HArrayInt ложная тревога и слухи. Я вспомнил что один в один его передирал в менеджед дотнет язык и если бы там было что-то не чисто с bounds уже бы давно выяснилось

Меж тем, этим вечером я в целях более глубокого освоения Rust решил реализовать на нём какую-нибудь интересную структуру данных. В качестве таковой был выбран HAT-Trie с некоторыми моими изменениями в алгоритме. Матан по HAT-Trie здесь: crpit.com/...apers/CRPITV62Askitis.pdf Свои изменения я опишу, если кому-то будет интересно. За сегодняшний вечер получены результаты для 32-разрядных ключей и значений:
[zenom@lynx release]$ ./rust_playground Size 1000000 Insert 0 sec 125162718 nanos Search 0 sec 102876360 nanos Size 2000000 Insert 0 sec 258873856 nanos Search 0 sec 221173375 nanos Size 3000000 Insert 0 sec 392696414 nanos Search 0 sec 305683095 nanos Size 4000000 Insert 0 sec 547442910 nanos Search 0 sec 454124008 nanos Size 5000000 Insert 0 sec 698278097 nanos Search 0 sec 532422106 nanos Size 6000000 Insert 0 sec 866163393 nanos Search 0 sec 716194667 nanos Size 7000000 Insert 1 sec 41583520 nanos Search 0 sec 784532907 nanos Size 8000000 Insert 1 sec 168931976 nanos Search 0 sec 920360498 nanos Size 9000000 Insert 1 sec 357707590 nanos Search 1 sec 13637407 nanos
Оверхед по памяти:
[zenom@lynx release]$ /bin/time -f "Max resident %M KiB" ./rust_playground > /dev/null Max resident 191984 KiB
Никакой чёрной оптимизирующей магии пока не применял, писал более-менее идиоматичный Rust-код (с поправкой на то, что сам язык я только осваиваю). Если сообществу будет интересно, то могу после стабилизации, генерализации и возможной оптимизации кода опубликовать исходники, библиотеку и C-биндинги к ней.

Извиняюсь, форматирование полетело. Результаты бенчмарков: pastebin.com/Xft1uRA8

Давайте введем единицу измерения Один Идеал.
Один Идеал равен скорости работы моего алгоритма.
Если алгоритм сливает всего 2-3 раза идеалу, мы будем называеть его почти идеалом.
В 3-10 раз Микрософт-Линупс эдишн
10+ раз Сырной эдишин.

Итак. Насколько ваш алгоритм медленее работает Идеала ?

Чуваааак! Мне пиписьками мериться не интересно, цель я озвучил — тренируюсь писать на новом языке. Это раз. Быстрее или медленнее работают не алгоритмы, а реализации алгоритмов. Это два. И если скорость считать единственным критерием, то мой код дрючит вообще всё. Это три.

Конечно посмотрел код, куча вопросов, наприклад:

void reallocateContentPages()
{
............
for (; j < newSizeContentPages; j++)
{
pTempContentPages[j] = 0;
}
............
}
вот тут цикл обязательно гонять, мемсетом никак ?

----------------------------------------------------

catch (...) //maybe out of memory exception
{
destroy();

throw;
}

Если мы все мега оптимизируем, то исключения обязательно юзать?
Не знаю как в других компилерах, но жцц точно может 0 возвращать в случае ошибки в new, если какая то хренька с памятью.

Когда-то сравнивал memset и цикл. Компиляторы сейчас умные и разницы не было в релизе с оптимизацией. Но цикл, имхо читается тяжелее и кода больше.
Второе тоже не важно. Исключения по нехватке памяти редки и накладные на них не будут сильно влиять на результаты.

catch (...) //maybe out of memory exception
Но вот это хрень. Так сложно ловить именно bad_alloc? Здесь же ловяться все с++ исключения и возможно другие, в зависимости от ключей компиляции.

Мемсет я вообще выпилю со своего кода. Чем проще код тем лучше, тем меньше головняка на разных платформах. For наше все

Да, что я обычно и использую. Я вообще не люблю закатывать солнце ручками и стараюсь использовать то, что реализовано уже стандартом. Но не всегда хватает знаний. Многие фишки последних с++ я уже не копал даже серьезно, ибо не умещается в моей тупой голове это все.
Но и цикл с мемсетом можно, разницы в скорости не будет в большей части случаев. Понятно, что memset требует внимательности при использовании. Ну а цикл, это обычно от незнания того, что плюсы предлагают.

Кстати, забавный факт. Требуется очистить 32Mb некешеруемой памяти, установить там 64битовый паттерн (аналог PTE). Супер-пупер оптимизированный интелом memset сделал это за 180ms. Поделив эту память просто на 4 куска и вызвав 4 потока через pthread_create() на четырёхпроцессорной машине время очистки и завершения четырёх потоков составило 46ms. Операция очистки и установки паттерна делалась через тип double, чтобы записывать 64 бита за раз атомарно.

Дохлые процессоры — замена Intel Atom’у :) ark.intel.com/...me/80644/Apollo-Lake#@All Я не знаю, они вышли в продажу или ещё нет.

Я специально написал, что память не кешированная (замаплена с флагом PROT_NOCACHE, т.к. шарится с устройством).

Помню, когда только появился PREFETCH уже появилось много разных способов ускорения программ, но такая тонкая настройка не всегда нужна, причем по времени она дорого стоит, пока под разные архитектуры отладишь.
Простое умножение матриц для АMD и Intel уже по разному нужно оптимизировать. Поэтому я сейчас больше полагаюсь в этом на разработчиков библиотек.
Но, бубен пытается сделать что общеупотребимое, то в его случае это может быть полезно.

99%, что

Супер-пупер оптимизированный интелом memset

был рассчитан именно на кэшируемую память.

А на некэшируемой обычно есть какой-то жёстко требуемый размер передачи на одну операцию, и его надо соблюдать.

4 потока через pthread_create()

Думаю, однонитевый вариант, но с 4мя подряд store, сработал бы не сильно хуже.

С кешируемой используется prefetch, но он далеко не всемогущь. Поэтому четыре юнита, каждый со своим префетчем был бы всё равно эффективнее (может не в четыре, а 2.5-3 раза).

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

Посмотрю я на тебе, как ты что чуть более сложное напишешь и отладишь сразу в многопоточном.
Обычно пишешь и отлаживаешь в однопоточном и потом, если нужно делаешь многопоточный режим. Извини, но мой мозг настолько убог, что работает в однопоточном.
И то стараешься многопоточность делать где повыше.
Кстати, может дашь ссылку на реализацию алгоритмов оптимизации с поддержкой многопоточности на плюсах и не за бабки, а еще лучше для opencl. А да, интересуют от стандартных (с производной и без), а также SA и GA, понятно, что это все не для одной переменной.

Кстати, может дашь ссылку на реализацию алгоритмов оптимизации с поддержкой многопоточности на плюсах и не за бабки, а еще лучше для opencl. А да, интересуют от стандартных (с производной и без), а также SA и GA, понятно, что это все не для одной переменной.
Если честно, то без понятия, я в этих кругах не вращаюсь, всё больше обработка звука и изображений.

А что там со звуком. Линейный фильтры да FFT c LPC и редко-редко вэйвлеты. Ну еще GMM да HMM. Эти алгоритмы написаны и отлажены.
Но вот та же оптимизация на верхнем уровне ой как нужна оказывается, особенно SA да GA.
А вот я сильно удивился, когда оказалось, что c оптимизационными алгоритмами всё хуже. Не, теория расписана вдоль и поперек, а вот отлаженных и говтовых реализаций кот наплакал. Все лепят свои велосипеды с разной степенью глючности.

А что там со звуком.
Много чего, в основном реализация а ля ClearTalk.
А вот я сильно удивился, когда оказалось, что c оптимизационными алгоритмами всё хуже. Не, теория расписана вдоль и поперек, а вот отлаженных и говтовых реализаций кот наплакал. Все лепят свои велосипеды с разной степенью глючности.
Я только симплекс метод реализовывал для решения, когда докторскую делали, но это было давно и неправда.
Поэтому четыре юнита, каждый со своим префетчем был бы всё равно эффективнее

Зависит от соотношения скорости памяти и шины процессор — контроллер памяти.

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

Видимо, это у тебя вокруг седые дядьки с 30 годами стажа на 8051 :) В моих краях уже нормально «походя» применить какой-нибудь parallel_foreach (в чём-то эквивалент того, что ты описал), ну а пачки слегка конкурирующих async/promise-based агентов — регулярно выскакивают. Но это не причина параллелить вообще не проверяя, что получится :)

В моих краях уже нормально «походя» применить какой-нибудь parallel_foreach
TBB используете? Завидую чёрной завистью :)

Перемеряй на QNX, все баги связаные с 64 разрядными регистрами должни были уйти.
github.com/Bazist/HArray.UNX

Мои поздравления, работает, но стек ты где-то порешь. Я увеличил размер стека по дефолту до 16Mb, чтобы оно не задевало stack guard — ты использовал 772К из 16Mb, что довольно таки много, ну а про 767Mb RAM уже и говорить нечего. Это в среднем, иногда 300Mb, иногда 1300Mb.

491547 1 ./ha64_g 10r RUNNING 0 767M 772K(16M)*

Ну а на последок держи сладкую пилюлю — скорость работы под QNX, std::map используется от LLVM C++, она тормознутая очень:

# ./ha64_g
=== HArrayInt VS std::map<int,int> testing ===
Insert/Search 1000000 SEQUENCE keys (4 bytes each) ...
HArrayInt => Insert: 13 msec, Search: 4 msec.
std::map => Insert: 342 msec, Search: 126 msec.

Insert/Search 3000000 SEQUENCE keys (4 bytes each) ...
HArrayInt => Insert: 45 msec, Search: 11 msec.
std::map => Insert: 1146 msec, Search: 385 msec.

Insert/Search 5000000 SEQUENCE keys (4 bytes each) ...
HArrayInt => Insert: 75 msec, Search: 19 msec.
std::map => Insert: 1972 msec, Search: 534 msec.

Insert/Search 7000000 SEQUENCE keys (4 bytes each) ...
HArrayInt => Insert: 100 msec, Search: 33 msec.
std::map => Insert: 2669 msec, Search: 758 msec.

Insert/Search 9000000 SEQUENCE keys (4 bytes each) ...
HArrayInt => Insert: 220 msec, Search: 38 msec.
std::map => Insert: 3634 msec, Search: 1231 msec.

Insert/Search 1000000 RANDOM keys (4 bytes each) ...
HArrayInt => Insert: 14 msec, Search: 6 msec.
std::map => Insert: 322 msec, Search: 312 msec.

Insert/Search 3000000 RANDOM keys (4 bytes each) ...
HArrayInt => Insert: 33 msec, Search: 19 msec.
std::map => Insert: 805 msec, Search: 804 msec.

Insert/Search 5000000 RANDOM keys (4 bytes each) ...
HArrayInt => Insert: 53 msec, Search: 31 msec.
std::map => Insert: 1350 msec, Search: 1340 msec.

Insert/Search 7000000 RANDOM keys (4 bytes each) ...
HArrayInt => Insert: 115 msec, Search: 68 msec.
std::map => Insert: 2215 msec, Search: 2143 msec.

Insert/Search 9000000 RANDOM keys (4 bytes each) ...
HArrayInt => Insert: 94 msec, Search: 56 msec.
std::map => Insert: 2397 msec, Search: 2651 msec.

Insert/Search 1000000 PERIOD keys (4 bytes each) ...
HArrayInt => Insert: 23 msec, Search: 4 msec.
std::map => Insert: 339 msec, Search: 100 msec.

Insert/Search 3000000 PERIOD keys (4 bytes each) ...
HArrayInt => Insert: 93 msec, Search: 13 msec.
std::map => Insert: 1089 msec, Search: 311 msec.

Insert/Search 5000000 PERIOD keys (4 bytes each) ...
HArrayInt => Insert: 119 msec, Search: 21 msec.
std::map => Insert: 1953 msec, Search: 658 msec.

Insert/Search 7000000 PERIOD keys (4 bytes each) ...
HArrayInt => Insert: 164 msec, Search: 29 msec.
std::map => Insert: 2669 msec, Search: 933 msec.

Insert/Search 9000000 PERIOD keys (4 bytes each) ...
HArrayInt => Insert: 217 msec, Search: 38 msec.
std::map => Insert: 3509 msec, Search: 993 msec.

=== HArrayVarRAM VS std::map<binkey,int> testing ===
Insert/Search 1000000 SEQUENCE keys (16 bytes each) ...
HArrayVarRAM => Insert: 145 msec, Search: 125 msec.
std::map => Insert: 795 msec, Search: 331 msec.

Insert/Search 3000000 SEQUENCE keys (16 bytes each) ...
HArrayVarRAM => Insert: 535 msec, Search: 331 msec.
std::map => Insert: 2694 msec, Search: 827 msec.

Insert/Search 5000000 SEQUENCE keys (16 bytes each) ...
HArrayVarRAM => Insert: 615 msec, Search: 500 msec.
std::map => Insert: 4102 msec, Search: 1441 msec.

Insert/Search 7000000 SEQUENCE keys (16 bytes each) ...
HArrayVarRAM => Insert: 996 msec, Search: 777 msec.
std::map => Insert: 6388 msec, Search: 2594 msec.

Insert/Search 1000000 RANDOM keys (16 bytes each) ...
HArrayVarRAM => Insert: 154 msec, Search: 104 msec.
std::map => Insert: 1229 msec, Search: 940 msec.

Insert/Search 3000000 RANDOM keys (16 bytes each) ...
HArrayVarRAM => Insert: 348 msec, Search: 327 msec.
std::map => Insert: 4461 msec, Search: 3611 msec.

Insert/Search 5000000 RANDOM keys (16 bytes each) ...
HArrayVarRAM => Insert: 611 msec, Search: 669 msec.
std::map => Insert: 7979 msec, Search: 6768 msec.

Insert/Search 7000000 RANDOM keys (16 bytes each) ...
HArrayVarRAM => Insert: 1103 msec, Search: 1254 msec.
std::map => Insert: 11952 msec, Search: 9912 msec.

Insert/Search 1000000 PERIOD keys (16 bytes each) ...
HArrayVarRAM => Insert: 41 msec, Search: 24 msec.
std::map => Insert: 395 msec, Search: 227 msec.

Insert/Search 3000000 PERIOD keys (16 bytes each) ...
HArrayVarRAM => Insert: 203 msec, Search: 117 msec.
std::map => Insert: 1237 msec, Search: 483 msec.

Insert/Search 5000000 PERIOD keys (16 bytes each) ...
HArrayVarRAM => Insert: 299 msec, Search: 122 msec.
std::map => Insert: 2196 msec, Search: 828 msec.

Insert/Search 7000000 PERIOD keys (16 bytes each) ...
HArrayVarRAM => Insert: 285 msec, Search: 171 msec.
std::map => Insert: 3447 msec, Search: 1721 msec.

=== HArrayVarRAM VS std::map<strkey,int> testing ===
Insert/Search 1000000 SIMILAR keys (64 bytes each) ...
HArrayVarRAM => Insert: 355 msec, Search: 461 msec.
std::map => Insert: 4686 msec, Search: 3333 msec.

Insert/Search 2000000 SIMILAR keys (64 bytes each) ...
HArrayVarRAM => Insert: 842 msec, Search: 1135 msec.
std::map => Insert: 9222 msec, Search: 8796 msec.

Insert/Search 3000000 SIMILAR keys (64 bytes each) ...
HArrayVarRAM => Insert: 1780 msec, Search: 1694 msec.
std::map => Insert: 14467 msec, Search: 14783 msec.

Insert/Search 4000000 SIMILAR keys (64 bytes each) ...
HArrayVarRAM => Insert: 2175 msec, Search: 2695 msec.
std::map => Insert: 19795 msec, Search: 21385 msec.

Insert/Search 5000000 SIMILAR keys (64 bytes each) ...
HArrayVarRAM => Insert: 3237 msec, Search: 3451 msec.
std::map => Insert: 25601 msec, Search: 26373 msec.

Insert/Search 1000000 RANDOM keys (64 bytes each) ...
HArrayVarRAM => Insert: 338 msec, Search: 364 msec.
std::map => Insert: 1717 msec, Search: 1605 msec.

Insert/Search 2000000 RANDOM keys (64 bytes each) ...
HArrayVarRAM => Insert: 937 msec, Search: 922 msec.
std::map => Insert: 3473 msec, Search: 3600 msec.

Insert/Search 3000000 RANDOM keys (64 bytes each) ...
HArrayVarRAM => Insert: 1500 msec, Search: 1548 msec.
std::map => Insert: 5896 msec, Search: 5495 msec.

Insert/Search 4000000 RANDOM keys (64 bytes each) ...
HArrayVarRAM => Insert: 2279 msec, Search: 2150 msec.
std::map => Insert: 8228 msec, Search: 7881 msec.

Insert/Search 5000000 RANDOM keys (64 bytes each) ...
HArrayVarRAM => Insert: 2981 msec, Search: 2830 msec.
std::map => Insert: 10440 msec, Search: 10046 msec.

Спасибо. А можно как-то вычислить что именно с стеком ? И кто именно порит, HArrayInt или HArrayVarRAM ? Это просто размера стека не хватило ?

Нет, не просто не хватило, а что-то вылезло за пределы (пусть даже на 4/8 байта — guard’у пофиг — он пристреливает процесс. Если бы это было легально расширение по типу push или alloca(), то гард бы доаллоцировал ещё 128Mb и сдвинул бы себя в конец 512+128 и так далее, в принципе до тех пор пока стек на наедет на код или данные.

Определить достаточно тяжело, мы портировали один Linux продукт, так у них там таймер заводился на стеке, а обрабатывался таймер в другом потоке, который получал указатель на стек другого потока. Как оно работало под Linux я не знаю, но под QNX мы получали страшные вещи, например, завели таймер, но выполнили задачу раньше и вышли из функции, но таймер не остановили и потом приходит прямая запись в стек из другого потока, что срок таймера вышел, а там в это время работает другая функция и ей трут стек. Так вот никакие valgrind, mudflap, sanitize не помогали. Только когда мы обвернули каждую запись по указателю в макрос, в котором проверяли не пишем ли мы в стек, только тогда нашли где проблема. В твоём случае по-проще конечно, просто старайся меньше использовать стек, используй заранее выделенную при инициализации память для своих внутренних нужд, пусть она и временная. ты всё равно пожираешь память гигабайтами, +/- мегабайт ничего не решит.

Ну Ок. Если нельзя определить это дебаг средствами, то можно хотябы грубо локализовать проблему.
1. УБРАТЬ из теста полностью работу с std::map дабы на 100% гарантировать что дело не в ней.
2. Оставить ТОЛЬКО HArrayInt в бенчмарках и протестировать.
3. Оставить ТОЛЬКО HArrayVarRAM в бенчмарках и протестировать.
Хотябы так, тогда может появится зацепка на что смотреть.
Под Ubuntu или Windows у меня пока нет вообще идей что это можно хоть както воспроизвести.
PS: Чтобы память не жрало много, можно уменьшить число в функции init. Поставить 20, например, вместо 24 или 26. Общий алгоритм примерно таков. 2^headerBase*4 = предвыделенное количество памяти

2. Оставить ТОЛЬКО HArrayInt в бенчмарках и протестировать.
По ходу валится гораздо раньше вот тут:

void init(uint headerBase)
{
memset(this, 0, sizeof(HArrayInt));

1) C++ класс — это не просто структура с данными.
2) sizeof(*this) и sizeof(HArrayInt) могут отличаться.
3) Сделай метод clear() и в нём очисть все данные вручную.

Понял, вечером закомичу изменения.
PS: Забавно, в том «спагетти» коде с гоуту, которое составляет ядро алгоритма, меньше багов чем в перефирийном отрефактореном коде :)

Нет, там дикая смесь самопала и потрохов около-tensorflow/etc. библиотек, присыпанных сверху слоем Lua, а в куче мест ещё и kdb+ (это чтобы жизнь мёдом не казалась даже уйдя с работы).
Увы. TBB это из серии того покоя, который только снится.

вот тут цикл обязательно гонять, мемсетом никак ?

Там рядом memset закомментированный => что-то с ним было не то. Можно уточнить, что именно. Возможно, какие-то виндовые тараканы.

Не знаю как в других компилерах, но жцц точно может 0 возвращать в случае ошибки в new, если какая то хренька с памятью.

Что-то сомневаюсь. Если это и было, то должны были давно исправить.

1. Речь про умолчательную форму new, а не специальную nothrow.
2. Я верю, что ты не видел граблей с memset. Поэтому вопрос к ТС.

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

но жцц точно может 0 возвращать
вот тут цикл обязательно гонять, мемсетом никак ?
Там рядом memset закомментированный => что-то с ним было не то. Можно уточнить, что именно. Возможно, какие-то виндовые тараканы.

На Линуксе были проблемы с мемсетом. Почему именно, не скажу, но когда убрал мемсет и заменил на обычные циклы — все заработало.

Юзай вот это

std::fill
пока не увидел, что здесь бутылочное горлышко.
Даже при переходе на pure С, просто функции напишешь нужные.
На Линуксе были проблемы с мемсетом. Почему именно, не скажу, но когда убрал мемсет и заменил на обычные циклы — все заработало.
Какие проблемы могут быть с memset’ом? %)

gcc использует билтин мемсет:

#include <stdint.h>                        // for uintptr_t
#define inline_memset(dst, c, N)                            \
   __asm__ __volatile__(                                              \
       "rep stos %1, (%0)\n\t"                                        \
       :: "D"((dst)), "a"((uintptr_t)(c)), "c"((N)/sizeof(uintptr_t)) \
       : "memory");

Проблемы обычно с руками, использующие мемсет...

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

gcc использует билтин мемсет:

Для фиксированного размера 16 — gcc породил два movq.

Для 100 — нечто длинное и сложное команд на 30, в котором, конечно, есть rep stosq, но только одна из всего этого набора. Остальное похоже на пляски вокруг невыровненного случая.

Для произвольного внешне заданного размера — три команды, последняя — jmp memset.

Всё это на gcc 4.8.4 для x86-64.

Твоё представление о gcc меня таки удивляет. Это в QNX такая версия? Сколько ей лет?

Там много паттернов, особенно, если ты даёшь выравненные на 8 данные, то она становится именно двумя командами. Увы, для остальных операционок — это мечта %)

Увы, для остальных операционок — это мечта %)

Ну вот что-то не видно тут зависимости от ОС. От компилятора — да, от ISA.
OK, thx, вопрос закрыт.

Можливо тому що у Вас:

	memset(pContentPages, 0, contentPagesSize * sizeof(uint)); 

а краще було б якось так:

 	memset(pContentPages, 0, contentPagesSize * sizeof(ContentPage*)); 

На x64 буде різниця.

Заодно открой для себя uintptr_t.

Очень рад за тебя, что ты нашел для себя легкую жертву в ньюансах линукс платформы. Теперь можешь открывать шампанское и праздновать, что у когото глаза не достаточно красные чтобы учесть все ньюансы этого линукс зоопарка. Особенно радует твой шах и мат с QNX, ведь я туда скорей всего никогда не доберусь и можно писать мне любые issue. Особенно когда тебя просят чтото конкретное, но ты конечно — ну тыпонел.

PS: Пойду на москальском форуме попасусь, может там ребята поскромнее.

Очень рад за тебя, что ты нашел для себя легкую жертву в ньюансах линукс платформы.
Хоть раз прочти C++11 или C99 стандарт от начала и до конца. Причём тут линукс?

Ой не свисти. Мне нужно было портировать с Виндовс под Линукс, я сел и за 20 мин это сделал. Там все достаточно просто и по стандартам, с некоторыми ньюансами на ваш overcommit. А вот сможешь ли ты свой любой проект из под Линукс портировать под Виндовс — большой вопрос.

Я уже лет как 10 пишу и под то и под то одновременно — никаких проблем. Проблемы, когда нужно что-то под MSVC исключительно написанное спортировать — вот тут жопа.
А с Линуха одна проблема — это долбаные автолузлы. Фигне если там простое, но там любят такое наворотить, что голову сломаешь.

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

А вот сможешь ли ты свой любой проект из под Линукс портировать под Виндовс — большой вопрос.
Ещё больший вопрос, что я знаю лучше винду или линукс — для себя я так и не определился.

Последний из известных opensource проектов, где я принимал участие — OpenAL Soft ( kcat.strangesoft.net/openal.html ) дописывался и писался исключительно на Windows, под другими операционками были только sanity checks.

При том, что MSVC начал стараться поддерживать C99 только в 2015-й версии. Так что для винды это, таки новости.

Вон в su.c-c++ коллеги драйверописатели задумчиво обсуждают, чи не перейти на 2008 или 2010 версию со старой освоенной 2005, и сходятся на том, что таки пока облом.
А ты говоришь — C++11...

Хотя какие-то подвижки есть — VS2015upd3 таки выкатило, говорят, компилятор с SSA(!), теперь ждём новых удивительных историй...

Это не Линуха нюансы, это с++.
Кто вообще тебе сказал, что указатель это unsigned __int32?
Более того указатель на туче платформ не связан с интом.
Ты просто слишком мало программируешь, чтобы ловить эти приколы даже под виндой. Я помню и 16 битную винду и 32 и 64. А если вспомнить весь зоопарк ОС, с которыми пришлось за 20 лет дело иметь, так прекрасно вбивается в бошку, что указатель — это указатель, а никак не int, long и т.п.
И более того, эти типы запрещены, если ты передаешь данные в бинарном, а не текстовом виде, а еще нужно учитывать выравнивания, как полей структур, так и данных и еще кучу разного. Сколько народа набило шишек на MS структурах (RIFF WAVE мой любимый пример).

Внимательней читайте код. Везде используется uint
#define uint uint32_t
#define ulong uint64_t
#define ushort uint16_t
#define uchar uint8_t
#define ucode uint8_t

Да пофиг. С какого бодуна указатель это

uint32_t
?
Вообще говоря там может быть любая херня вплоть до навороченной структуры (класса).
И кроме того, я бы советовал писать
#define bc_uint uint32_t
, а не вводить людей в заблуждение.

Это не указатель. Это 32х битное беззнаковое число в терминах алгоритма. И алгоритм требует платформе предоставить такие регистры, в которых вместится именно 32 бита.

Можливо тому що у Вас:

memset(pContentPages, 0, contentPagesSize * sizeof(uint));

а краще було б якось так:

memset(pContentPages, 0, contentPagesSize * sizeof(ContentPage*));

На x64 буде різниця.

так прекрасно вбивается в бошку, что указатель — это указатель, а никак не int, long и т.п.
Как раз вспоминался на днях Watcom/DOS4GW с 48 битовыми указателями — селектор+смещение %)

Кстати, что в нём буква W значит?
А то я одно время любил вытаскивать DOS4G.EXE из Heretic и подкладывать под борландовый выхлоп — оно местами даже чуть лучше работало :) но за полным отсутствием документации по источникам этого безобразия осталось непонятым, а потом я про него забыл на много лет.

Кстати, что в нём буква W значит?
W — это free re-distributive, коммерческая стоила около 200 баксов за рабочее место, она предоставляла полную версию DOS PM Extender’а, согласно спецификации, которая по большому счёту никому не нужна была, ибо там были очень специфические вещи, такие как перехват обращения к регистрам, памяти и прочее.

Понятно, спасибо.

Посыпаю голову пеплом.
Действительно на той конфигурации на которой тестировал,
64х битные указатели

Ваша структура надає інтерфейс для видалення елемента по ключу?

Только обнуление элемента.
Тоесть массовое удаление не приводит к шринканью самой структуры. Но с временем можно сделать rebuild и шринкануть все спейсы.
Чистое алгоритмическое удаление сделать — это достаточно сложная задача.

Простите, но я такой код физически не понимаю. Т.е. да, что-то оно делает. Что-то, вроде бы, хорошее. Однако, статьи нет, код настолько плох, что алгоритм можно понять только его отрефакторив в нормальную форму. При таком поведении автора вложение времени весьма бессмыссленно.

Ладно народ. Предлагаю на этой ноте временно закруглиться.
Два основных поинта.
1. Статье на Хабре быть.
2. Возможно стоит снять и выложить на ютуб курс лекций и правильно преподнести информацию

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

Есть еще один стандартный путь для программы — самоубицца. Что большинство программ и делают. Стандартная обработка исключений.

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

Пускай верхний код его ловит. Что мне с ним делать внутри инсерт ? Если нью не отработал то это краш процесса

Стандартный патерн для простых структур данных — если объект не удалось построить бросать на верх эксепшин. Верхний код сам должен решать что делать. Мапа же не может на консоль выводить текст эксепшина или меседжбоксы показывать. Разве что свой ребилд вызвать и сделать более компактным дерево. Но это тупик потому что для этого все равно нужно чуток памяти еще выделить

Напишите пример кода под Линукс и Виндовс. Я добавлю

Закомитил, правда под Win,
под линукс нет доступа пока что.

Проще всего обернуть в std::unique_ptr прямо в классе. Одна проблемка — он начиная с C++11, то есть старые VS могут не потянуть (а линуксовым компиляторам до gcc5 надо явно разрешать 11-й). Так что это залог на будущее.
Ну или самому делать временный RAII-аналог в конструкторе.

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

Ага, а если 3 выделились, а один нет. И начинается куча говнокода для выруливания снезабывание сбросить указатель в NULL. А если это не память, а другие ресурсы.
В итоге единственный разумный путь — или свои обертки или умные указатели, благо в С++ их сейчас уже нормально представлено. Причем накладные расходы сейчас нулевые. А код становиться и читабельнее и безопаснее на порядок.
Если мне где оказывается нужен голый указатель в плюсах, а 10 раз себе по рукам побъю, прежде, чем его оставлю, и только, если не придумал другого способа без него, буду возиться с этим указателем — ибо это потенциальная проблема с утечкой ресурсов, растрелом памяти и т.п.

Не всегда, встречаются чрезвычайно редкие ситуации, когда это нужно, впрочем, как и с goto. Но чаще всего — это именно ошибка.
Я не читал уже это правило Страуструпа, но сам для себя его вывел.
Но также в плюсах не надо забывать про стек и хип, но для оного желательно написать отдельный класс, что будет разруливаться.
Т.е. может в том коде предполагалось выделить под указатели память именно в хипе, а не в стеке, например, но не надо это делать методом, как выше.

Типо того. Но, предполагаю, если покопаться или пофантазировать долго, то наверное еще когда-то возможны. Просто не люблю говорить «никогда».

С Judy Array ещё никто не сравнивал?

Меряли когдато. Я немного проиграл по памяти но значительно выиграл по скорости.
Но конкретных цифр сейчас не найду, да и стоило бы перемерять

Judy медленее чуть меньше чем в два раза.

Спасибо Бро
Джуди писали крутые ребята из HP больше года целой тимой с оптимизацией под кеши проца. Это можно сказать первая серьезная попытка сделать что-то стоящее на основе Trie

Спасибо Бро
Я за справедливость. Та же Judy (1.0.5) неработоспособна и часто падает, очень сырая реализация. Кстати, на 14 Ubuntu LTS и под QNX она не проходит даже свои собственные тесты.
Джуди писали крутые ребята из HP больше года целой тимой с оптимизацией под кеши проца.
Все эти разговоры про кеши проца для домохозяек. То, что они ограничили размер структуры равным двум кешлайнам не имеет никакого критического значения. Я не увидел в коде ни одного вызова __builtin_prefetch() или _mm_prefetch() - без этого процессор работает как раньше, вычитывает больше чем надо и ни разу не может угадать куда будет обращение к следующей структуре, что гарантирует 100% cache miss.

В’ячеславе, вам дуже бракує скромності. Поводитесь та хвалите себе як вже згадані в треді російські «прінципіально новиє» школярі-шарлатани, при чому у вас причин так робити ще менше — про вас навіть сюжет на ТБ не показали, і гранд ви ніякий не виграли. Тон зневажливої до вас дискусії ви задали самі — своїми «качественно вброшу», «настоящая нетленка», «легендарный алгоритм». В кожному вашому слові зверхність та пафос. Важко вас сприймати всерйоз, інакше ніж троля чи ідіота.

Ну хорошо. Простите.
А то тут уже до уютненьного.it недалеко.

Вроде поборол сегфолт.

Компилятор GNU GCC, OS Ubuntu 10.1,
Железо вот такое rozetka.com.ua/...er_nx_g2jeu_002/p4741926

Результаты, мягко говоря, меня удивили.
Линуксовая мапа сливает в некоторых кейсах в десятки раз. (Кто там на нее надежды возлагал ?)
github.com/...ray_Benchmarks_Ubuntu.txt

Сырцы (правда опять без мейкфайла, извиняйте)
залил сюда
github.com/.../tree/master/HArray_Linux

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

Именно так. Есть алгоритмисты высочайшего уровня, которые призваны высечь в монолите выдающиеся реализации, показав тем самым настоящий Мастер Класс. А есть хомячки, такие как ты, которые бегают вокруг и скулят про копипасту, гоутушечки и лишний иострим в заголовке.

ты вообще не понимаешь кто такие «великие алгоритмисты» и как они работают.
А твои фантазии забавны, ога :)

Компилятор GNU GCC, OS Ubuntu 10.1,

ОС зверски старая. И я подозреваю, что только 32-битная, ибо:

Main.cpp:57:46: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘clock_t {aka long int}’ [-Wformat=]
  printf("Insert: %d msec, ", (finish - start));

Main.cpp:174:87: warning: format ‘%u’ expects argument of type ‘unsigned int’, but argument 3 has type ‘long unsigned int’ [-Wformat=]
   printf("Insert/Search %u PERIOD keys (%u bytes each) ...\n", countKeys, sizeof(uint));

Вывести 8-байтное целое как 4-байтное работает только чудом (из-за LE плюс соглашения о вызову). Нехорошо, ибо грязь.

Про мириады comparison between signed and unsigned integer expressions я активно и не вспоминаю — тут бы с более серьёзными проблемами разобраться (хотя и эти тоже важны, там легко вляпаться в ситуацию, когда, например, −1 превращается в UINT_MAX).

HArrayInt.h:173:9: warning: ‘countValues’ may be used uninitialized in this function [-Wmaybe-uninitialized]

Заметим, это всего лишь -Wall.. Я ещё не включал -Wextra, стра-а-ашно.

Можно также заглянуть в код...


clock_t msclock()
{
    return clock() / 1000; //in ms
}

Для кого в мане писали про CLOCKS_PER_SEC? Ладно, это можно списать на желание побыстрее что-то выкатить, но всё равно плохо — непереносимостью и соответственно проблемами воспроизведения.

Линуксовая мапа сливает в некоторых кейсах в десятки раз. (Кто там на нее надежды возлагал ?)

Надежды или нет, но я предложил сравнить. А тем более, что сравнивать надо при равенстве условий. На Intʼах делать быстрое достаточно легко. А вот как, например, будет в случае, если и ключи, и значения — std::string? Разобрать какую-нибудь «Войну и мир» на строки и сделать мапу строка -> следующая строка.

А ещё std::map из GCC — это тупое red-black. Я вообще не понимаю причины любви народа к ней — AVL в среднем показывает результаты на несколько процентов быстрее, и сопровождается легче — но с нынешней дороговизной доступа к RAM надо смотреть на полноценные B-деревья. Возьмите реализацию мапы из tarantool, она на B⁺-деревьях, и сравните скорость с ней, если получится аккуратно выдрать (там иерархия кастомных менеджеров памяти). И опять же не только на целых, но как минимум(!) на строках.

правда опять без мейкфайла, извиняйте

Ну добавьте.


OBJS= HArrayVarRAM_delValueByKey.o HArrayVarRAM_getKeysAndValuesByRange.o \
        HArrayVarRAM_getValueByKey.o HArrayVarRAM_getValuesByRange.o \
        HArrayVarRAM_hasPartKey.o HArrayVarRAM_insert.o \
        HArrayVarRAM_scanKeysAndValues.o Main.o stdafx.o

CXXFLAGS= -O -pipe -Wall -Wno-write-strings -std=c++11

test: $(OBJS)
        $(CXX) -o test $(OBJS)

.cpp.o:
        $(CXX) -c $< $(CXXFLAGS)

clean:
        rm -f test ./*.o

.PHONY: clean

восстановить табы перед коммитом.

Вот один из немногих толковых комментариев.
Кто шарит лучше в тонкостях GCC компиляции, предлагаю внести правки в код. Очень желательно чтобы они имели не «эстетический» характер, а действительно на чтото влияли, например, улучшали производительность еще.

Надежды или нет, но я предложил сравнить. А тем более, что сравнивать надо при равенстве условий. На Intʼах делать быстрое достаточно легко. А вот как, например, будет в случае, если и ключи, и значения — std::string? Разобрать какую-нибудь «Войну и мир» на строки и сделать мапу строка -> следующая строка.

Там же есть пачка бенчмарков где в качестве ключа используется 64х байтная строка сгенерированая или рандомно или по какомуто правилу. Адаптер именно для std::string написать не представляет никакого труда и производительности он практически не просадит.

Возьмите реализацию мапы из tarantool, она на B⁺-деревьях, и сравните скорость с ней, если получится аккуратно выдрать (там иерархия кастомных менеджеров памяти). И опять же не только на целых, но как минимум(!) на строках.

Если она на B+ то это не имеет практически смысла. Может быть