×Закрыть

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

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

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

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

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

👍НравитсяПонравилось0
В избранноеВ избранном2
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

Когда это будет в 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); //здесь три инструкции 
тем сложнее и медленнее работает код.
Отсюда следствие: если код сложный и медленный, то кто-то не нашел простого решения.
Например, как споласкивая чашку после чая, максимально быстро не оставить в чашке ни одной чаинки? Я нашел решение.

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

Поэтому когда он его упростит — этот алгоритм станет еще быстрее.

Вот еще вариант ответа (из жизни): Купюры в миллион долларов используют редко поэтому: 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?

А чем объясняется отставания на 16 байтовых случайных ключах?
Запускал под Release-x64

Insert/Search/Delete 9000000 RANDOM keys (16 bytes each) ...
HArray => Insert: 1949 msec, Search: 1647 msec, Delete: 25576 msec.
std::map => Insert: 8389 msec, Search: 7931 msec.
std::unordered_map => Insert: 3519 msec, Search: 939 msec.

P.S. На остальных кейсах HArray выигрывает, выглядит круто

Обьясняется тем что хештаблица в некоторых случах может быть делать меньше 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).

(возражение только в этом пункте)

Так-то невыделение памяти это типичное поведение даже для Binary Tree и Linked List, вряд ли можно назвать это костылем

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

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

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

Не понял этот момент. Если принципиально структура построена так, что «превыделить» память невозможно (как LinkedList и BinaryTree), как можно ее выделить и получить буст к перформансу?
Или, например, std:set это не годный контейнер?

Насправді, для ліста та 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 для поддержки коллизий. Вместо аллокации элементов этого связного списка в куче (что будет медленно но уверенно херить кучу и усложнять работу сборщика мусора), память под все элементы выделяется одним большим блоком заранее и будет расходоваться по мере наполнения хеш-таблицы данными.

Спасибо, но из вышеприведенного я понял что улучшение только за счет облегчения работы сборщику мусора. Как это повлияет, например, на перфоманс того же lookup? И на языки без сборки мусора, например С++?
Я понимаю как оно влияет на таких структурах как обычный массив, т.к. используются разные SIMD инструкции и последовательный доступ к памяти. А как это поможет linked list’у?

P.S.
На реальном примере, когда вставляют в середину, а не последовательно. Если последовательно то понятно, что на cache line будут и следующие элементы

Це оптимізує тільки виділення/видалення елементів. Тому що виділити та видалити пам’ять це, загалом, нетривіальна операція. На пошук воно не дуже вплине, хіба що більш щільне розташування елементів може призвести до меншої кількості 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 медленнее т.к. память выделяется один раз» не выдерживает критики.

На 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+ то это не имеет практически смысла. Может быть сканы по диапазонам ключей там будут чуток лучше в определенных контрпримерах. (Trie всетаки делает это более размашесто). Все остальное — банально больше seek times.
Ну и да, пока что мы говорим только про InMemory структуры, для которых кстате также как и для диска справедливо Latency и Seek Time.

Вот один из немногих толковых комментариев.
Ну дик він і написаний справжнім Гуру. ;)
Разобрать какую-нибудь «Войну и мир» на строки и сделать мапу строка -> следующая строка.

Это слишком просто и делал такое уже и не раз.
Я разбирал Либрусек на части. А это около 400 тысяч книг почти в 300 гигабайтах текстовых файлов. Скорость индексирования поднималась до 100 мб\сек на один поток, а размер словаря превысил 15 млн слов (книги там на разных языках).

Короче я портировали бОльшую часть под Линукс. Многие из 45 тестов работают нормально. Разница между STD::map и моей либой ощутимо выросла в мою пользу при компиляции GCC(может это конфигурация компа такая ?). Но есть в некоторых тестах хитрый сегфолт краш и мне понадобится некоторое время чтобы с этим разобраться. Особенно учитывая что после VS в этом code::blocks сидеть весьма непривычно. Но я что-то придумаю. Всем Удачи.

давай так, портируй под анроид лиункс......и там все разбирайсе — там тетпишут

Да не взлетит у него по одной простой причине. Может алгоритм он и крутой делает, но его реализация будет вечно падать и глючить по одной простой причине: безумное ЧСВ и не желание слушать других. Поиграется еще некоторое время, потом закинет в пыльный чулан, ибо надоест.

Баги это просто баги. Их рано или поздно выкосят. Под Виндовс багов уже нет давно. Под Линукс, нужно еще дополнительно тестировать. На 45 нагрузочных тестах вот не падает, нормально.
А на счет ЧСВ это почемуто в украинском айти эстеблешменте он раздут до невероятных размеров. Как будто уже успели написать и протестировать по пять нетленок каждый мирового уровня. Пафос некоторых доставлят — "Портируйте мне бесплатно под Си я хочу попробовать использовать в своем личном проекте, ведь мое время дороже чем ваше !«© Или «Протестирую непременно как появится сmake файл, ведь я пользователь под Linux». Ну замечательно. Но если нормальное компьюнити, и заинтеерсовано в нормальной идее — то оно НЕ должно мне выносить мозг, а должно посильно помочь хотябы с элементарными вещами.

Мне лично, в целом всеравно. Мне больше наука дорога, алгоритм в готовом виде пылился 3 года, может быть не увидел свет вообще. Короче кому не нравится — используйте std::map и его аналоги. И веруйте что это верх инженерной мысли, гы гы.

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

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

Ему тут уже написали конкретных предложений море, в том числе и с возможным заказом от моснтров индустрии.

Але ніхто не допоміг. Триндіти не мішки ворочати. Всі гаразди тільки надати «корисну пораду». Так ком’юніті не побудувати ніколи...

Вот возьмись и помоги. Что других призываешь, а сам?

Я ж написав вище, що не можу... А так би залюбки!

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

Ну так выучи С с плюсами. Даже кошечка для тренировки есть.

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

Але ніхто не допоміг. Триндіти не мішки ворочати. Всі гаразди тільки надати “корисну пораду”. Так ком’юніті не побудувати ніколи...
Ты правда не понимаешь? Зачем ему помогать, если он сам себе помочь не может? Он не может сделать даже элементарного — причесать код, перед тем как выкладывать. Такая внешняя небрежность свидетельствует о внутренней небрежности тоже, в продакшене я бы побоялся использовать его код. Попробовать — да, использовать — нужно разобрать алгоритм полностью, иначе врядли.

Ну так би й сказав, корона тисне..

Лучше уж корона снаружи, чем ЧСВ изнутри.

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

Ну дик завжди важко співпрацювати із людиною, яку з самого початку змішали із лайном...

На ваше сожаление, я отлично помню этот тред. Поэтому, могу заявить, что вы перекруиваете факты. Тс облил ведром с поносом тех, кто пытались быть конструктивными, ну а потом обтекающие ус0троили ему алаверды. Однако, могу заметить, что алаверды сие не идет ни в какое сравнение с тем, что продолжает нести тс.

Тс облил ведром с поносом тех, кто пытались быть конструктивными

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

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

Я заметил, как оно у вас сложился с Горчаком и Чидженком.

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

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

Их замечания имели рациональное звено, которое позже подтвердили Горчак и Чидженко (который вас, сначала, кстати, даже пытался защищать).

И кстате это даже полезно, иначе будет тема с унылыми тремя комментариями.

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

Ой, ну я вас умоляю. Вроде ландшафт украинского айти просто кишит первокласными продуктами мирового уровня вроде Оракла, Постгрес, Гугл и тд и тут только вот я такой никакой попался из-за которого проект «не взлетит». Даже москали со своими Яндексами, Касперскими и Бреинджеинами на две головы вше чем мы. Оглянись вокруг и схамениться, как тут уже писали. Иначе всю жизнь будете конкурировать с индусами и циганами за проекты. Ну или за границей стеснятся своих корней.

Вроде ландшафт украинского айти просто кишит первокласными продуктами мирового уровня вроде Оракла, Постгрес, Гугл и тд и тут только вот я такой никакой попался из-за которого проект «не взлетит».

В васших утвержедниях 2 логических ошибки:
1. Ваш продукт не первоклассный;
2. Ваш продукт не мирового уровня.

Ваш продукт мог бы таковым стать, есил бы сообщество решило его допилить. Однако, с вашей персоналией, шансов на то, что ваш продукт станет чего-то стоить, нет.

Оглянись вокруг и схамениться, как тут уже писали.

Зачем это мне? Чисто, чтобы потом посидеть в поносе, извергаемом вами в свободное, от работы время? Нет, спасибо. Я лучше с Ортой поработаю, он парень приятный и его продукты, как раз, мирового уровня, т.е. такие, что ими пользуется весь мир.

Ну или за границей стеснятся своих корней.

Не проецируйте свои фобии на других.

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

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

Не патриот значит.

Патриотизм не имеет ничего общего с идиотизмом. Работать с вами — идиотизм.

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

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

Вот потому мне жалко всяких Физиков Теоретиков, или Математиков Теоретиков. Выкатываешь такой классную теорию, тут толпой набегают гуманитарии, маркетологи и шутники и смешуют твою теорию с навозом. В итоге только на втором, а то и третьем поколении наконец до людей наконец доходит о чем же тогда говорил автор. В Computer Science совершенно все не так. Ты делаешь чтото интересное, просто делаешь реализацию, выкатываешь benchmarks на которых компьютер полностью и недвузначно апрувит твою теорию и сразу 999 гуманитариев идут в лес. Profit !

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

Ни Горчак, ни Чидженко не являются гуманитариями. Так вот, в лес вас послали они.

Выкатываешь такой классную теорию, тут толпой набегают гуманитарии, маркетологи и шутники и смешуют твою теорию с навозом.

Если идеальная теория написана фекалиями на тонком слое поноса, то никто ее читать не будет, какой бы гениальной она ни была.

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

Ни Горчак, ни Чидженко не являются гуманитариями. Так вот, в лес вас послали они.

Давай ты за них не будешь говорить. Ок ?

Давай ты за них не будешь. говорить. Ок ?

Мне не надо за них говорить. В этом треде они свое мнение сказали сами.

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

Дуже Дякую.
Коли почуете десь на ганку
— Ти знаешь куме СКБД Днипро в двадцять разив швидше працюе за оту москальську Монгу
— Так, звисно !
И так хитро усмихнетися, бо ви вже майже знаете чому.

Пафос некоторых доставлят — "Портируйте мне бесплатно под Си я хочу попробовать использовать в своем личном проекте, ведь мое время дороже чем ваше !«©
Ты даже читать не умеешь — 01.org/igvt-g — это далеко не личный проект.
Но если нормальное компьюнити, и заинтеерсовано в нормальной идее — то оно НЕ должно мне выносить мозг, а должно посильно помочь хотябы с элементарными вещами.
С элементарными вещами должно разбираться не нормальное коммьюнити, а нормальный автор. Написал, выложил, сделай поддержку.
Мне больше наука дорога, алгоритм в готовом виде пылился 3 года, может быть не увидел свет вообще.
В общем ещё один мастер «и так сойдёт», не способный довести идею до конца, бросающий проект на 80% готовности. Таких в мире миллионы и цена им 0.

Можете допомогти довести до 100%... Якщо ви дійсно маєте унікальний досвід як це зробити.

Какой в этом смысл? В мире есть множество увлекательных вещей, куда подтирание жопы за малолеткой не входит.

Никогда не был таким, может поэтому мне такие индивидуумы чужды.

Ви одразу народилися із знаннями да досвідом?

У меня до сих пор нет ни знаний, ни опыта.

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

А я с этим категорически не согласен. Узкая ориентированность только на свой результат, создание условий под него и отмахивание от всего, что видится прямо сейчас не нужным — это, да, присутствует. Типаж «испанский лётчик» — смотрит только вперёд в узкую амбразуру туда, куда летит, не обращая внимания ни на что вокруг. Но я видел несколько раз, как такие добивались таки своего прорывного результата — а ту же самую вычистку/адаптацию делали уже другие, не столь концентрированные, с широким опытом. Даже завидую — меня ничто пока так активно и глубоко не интересовало.

А результат таки есть — по крайней мере бенчмарки показывает очень вкусные цифры, и valgrind молчит. :)

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

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

ну да, мы откровенных дибилов фильтруем. Я так понимаю, потратить 15 минут в день на отчетность — для тебя непосильный труд? :)

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

Ніхто не любить критику. Ви себе зараз чуєте? Ви зараз дуже активно підтверджуєте, що автор топіка правий на 200%.

Ну да, чо уж там, нормальное поведение: вывалить полурабочий говнокод в паблик, обьявив себя гением.
наехать на несогласных, заявив что все они «не шарят».
когда ему потыкали в конкретные косяки — заявить что «а пофик правьте сами».
когда поправили — сказать «криво поправили», вы все не шарите.
... и после этого обидеться на весь мир, заявив что его не уважают и не хотят помочь.
Все это с пафосом и чсв овер 9000.
Нормальное поведение, что уж там. Правильное.

Ви заздрите, чи що? Мене, як спеціаліста в певній галузі, абсолютно не турбує максималізм та манерність автора топіку. Тому що я навчився дивитися в сутність, а не звертати увагу на мішуру. Ситуація така, що реальний клас показав тільки Нетч. Але це й зрозуміло.

Тому що я навчився дивитися в сутність, а не звертати увагу на мішуру.
Да нету там сути. Только мишура и пафос.
Я это по косвенным признаком в другом топике еще понял. Ни разу не качая и не компилируя сорцы.
И завидовать тут совершенно нечему.

Когда умный показывает на небо дурак смотрит на палец ©

Вера, которую не разделяет никто, называется шизофренией. ©

Покажіть свій проект, яким би ви могли пишатися. Покажіть свій клас. А то тут більшість розмов схожі на діалог:
— Все лайно! Всі лайнюки! Я — краще!
— Чим?
— Чим лайно!
:-/

Сперва добейся, ага.
Я даже на NDA не буду ссылаться, хотя все проекты в которых я участвую — под ним. И даже на то, что продакшн кода я сейчас пишу достаточно мало.
Просто нет такого проекта, который я сделал сам. Все в коллективе. Кто-то проектирует, кто-то педалит, кто то ревьюит...
поэтому попросту нет «моего» кода и «моего» проекта.
А любая ссылка на коллективное творчество ожидаемо приведет к бурлению на тему «а ты же не сам это сделал!»

Сперва добейся, ага.
Мимо каси.
Клас програміста заключається не в тому, що він як мавпа може кидатися лайном, а в тому, що він може а) розібратися в коді іншого програміста (навіть якщо він здається лайнокодом) б) самостійно виправити помилки або написати власну реалізацію й доказати свою точку зору кодом. Це як було із Еплом та Майкрософтом. Майкрософт міг скільки завгодно стібати Епл з приводу телефонів, але так і не спромігся зробити щось краще. Ітог ми знаємо: Епл на коні, Майкрософт злився з ринку. Так само і тут. Всі відмазки про те, що розбиратися в коді ТС або допомагати йому, є зайвою витратою часу, я особисто сприймаю як повну професійну імпотенцію критиків. І всі намагання щось доказати без надання коду тільки підтверджують мою правоту. На конкурс мірянія піпіськами не приходять із власними лінійками ;)

В общим да, «сперва добейся и напиши ему код». Лично я считаю такую точку зрения крайне недалекой и ущербной.
Что только подтверждается этим топиком: некоторые собеседники таки скачали, скомпилили, запустли, указали на ошибки и предложили чендж реквесты на заливку. В ответ получили от топикстартера очередную порцию говна, что «вы тут багов понаделали», причем без конкретики.
Повторюсь, я же чисто по формальным признакам, потратив буквально минут 15, определил что «не взлетит» — это, не побоюсь этого слова, признак класса :)

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

dou.ua/...rums/topic/18849/#1005075
Вот эта ветка показательна, ога.

В общим да, «сперва добейся и напиши ему код». Лично я считаю такую точку зрения крайне недалекой и ущербной.
Таке враження, що ви не читали мого поста. Не треба добиватися, треба просто не вважати себе самим розумним. А якщо заявив про себе, то будь ласка доказуй свій клас, інакше ти простий балабол. Давайте простими словами. Змагання виграють не ті, хто краще за все розповідають, які вони круті та як вони всіх можуть виграти, а ті, хто стають на стартову лінію та реально доказують, що вони щось можуть. Це не «спочатку досягни», це інше.
Ви не допускаєте того, що люди могли не розібратися із задачею та реалізацією? Ні? Зовсім? А я таке бачу крізь. Мені особисто багато разів казали — не полетить. А воно, блін, летіло. Ще й як летіло!
А якщо заявив про себе, то будь ласка доказуй свій клас, інакше ти простий балабол.
Еще раз по буквам: народ полез разбираться с кодом и тыкнул автора в конкретные проблемы.
Я же указал на то, что код говно, посмотрев на него по диагонали. То есть мой прогноз оказался верен и правилен. Вот собственно говоря в чем и класс. :)

Ваша суб’єктивна оцінка коду не цікава нікому. Ви це розумієте?

Ваша суб’єктивна оцінка коду не цікава нікому. Ви це розумієте?

Она объективна. Это подтвердили девы с proven record, как Горчак и Чидженко. Другое дело, что говнокод мог бы кто-то из сообщества, подправить. Там рефакторинга на 1-2 вечера + неделька на портабельность нормальную + покрытие тестами еще на пару неделек.

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

З.Ы. Скажите, а вы не мульт Бубна?

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

«...а вы и есть за меня будете?»

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

github.com/Bazist/HArray.WIN
github.com/Bazist/HArray.UNX

0 форков, 0 пулл реквестов. Никто не хотел комитить, как я погляжу.

Не понимаю о чем спор.

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

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

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

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

Во-вторых, если вы не хотите комитить, то какие ко мне вообще претензии что я не учел чьи-то хотелки ?

А зачем что-то коммитить, чтобы потом слушать о том, что мы все поломали и у вас все классно? Автор любого PoC либо взаимодействует с сообществом и оно улучшает его код, либо получает реакцию, как в сиим топике.

Она объективна.
Можете називати як завгодно. Практичної цінності для оточуючих вона все одне не несе ніякої.
Но, лично я этого делать не стану, особенно, после писков аффтара о том, как ему код сломали, да какие все идиоты вокруг.
Автор гарно спілкується із іншими учасниками топіку. Окрім того ще й нормально сприймає їх зауваження та пропозиції. Задайтеся запитанням, чому?
З.Ы. Скажите, а вы не мульт Бубна?
Я його навіть особисто не знаю.
Можете називати як завгодно. Практичної цінності для оточуючих вона все одне не несе ніякої.
Не несет тем, кто не желает слушать критику. А я тут не работаю, а развлекаюсь, соответсвенно не парюсь по поводу того что меня не услышали и не подбираю политкорректных формулировок.
Пару примеров.
Я отметил что в HArrayVarRAM::insert есть проблемы. Посмотрев ее по диагонале. Потом народ нашел проблемы.
Я отметил: проблемы с CI/CD. Аффтар потом начал: “поффиксал в версии под линух, но не под виндовз...”, “кто-то что-то поломал, бывает...”
Было бы желание услышать...

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

Можете називати як завгодно. Практичної цінності для оточуючих вона все одне не несе ніякої.

Ваше утверждение не соответствует действительности.

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

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

Комменты от изначально адекватных участников, которые сильны конкретно в той специализации, на которую претендует аффтар:
dou.ua/...ign=reply-comment#1006214
dou.ua/...ign=reply-comment#1005983
dou.ua/...ign=reply-comment#1006079

А вот просто несколько примеров замечаний и смотрим на реакцию ТС:
dou.ua/...ign=reply-comment#1006077
dou.ua/...ign=reply-comment#1005368
dou.ua/...ign=reply-comment#1005025
dou.ua/...ign=reply-comment#1005130
dou.ua/...ign=reply-comment#1005014
dou.ua/...ign=reply-comment#1005008
dou.ua/...ign=reply-comment#1004977
dou.ua/...ign=reply-comment#1004906
dou.ua/...ign=reply-comment#1004901

Ну и вся ветка: dou.ua/...ign=reply-comment#1005075

которые сильны конкретно в той специализации, на которую претендует аффтар:

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

А вот просто несколько примеров замечаний и смотрим на реакцию ТС:

Ну, после фантастики типа «на ARM thumb, int — 16 бит» я бы просто в игнор занёс.
Реально, замечания (включая мои) до сих пор были только придиркой к форме. Я не видел пока ни одного по сути алгоритма, от слова «вообще».

Ну вот есть мнение, что если автор типа алгоритмист, но ниразу не программист — то может ему и алгоритм надо презентовать в виде блок схемы на форуме математиков?

Почему-то :) почти ни в одной книге по алгоритмам так не делают.
Хотя есть любимый Кожаевым «Дракон»... ой, простите, одраконахнислова

смею предположить, что исключительно по той причине, что квалификация авторов этих книг позволяет им написать вменяемые примеры алгоритмов на каком нибудь языке прораммирования.
Впрочем мат статьи с квадратиками и ромбиками, я видел в приличном количестве — то есть это ниразу не исключение.
Ну и я вот рандомно открыл Кнута — пожалуйста и картинки и примерчик реализации:
joxi.ru/nAyXvP5uXoVg32

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

Вполне возможно, причина именно в этом.
И именно поэтому я не хочу отвергать только по формальным признакам, не связанным с самим алгоритмом.

Я наверное больше доверяю мат статистике. И конечно допускаю вероятность того, что автор:
— будучи неадекватен в девелопменте, куммуникации с людьми, теоретических основах распределенных СУБД(был у нас с ним в другом топике спор на эту тему), коммерческой разработке и внедрении софта
— декларируя себя как супергуру во всех озвученных областях,
является гением от алгоритмизации. Но считаю такую вероятность околонулевой.

Ну, после фантастики типа «на ARM thumb, int — 16 бит» я бы просто в игнор занёс.

Перепутал чел размер инструкций и размер данных. Бывает. Однако, таки по стандарту зацикливаться на конкретную битность не стоит типов, если не используются *_t типы, не так ли? Есил мы говорим о портабельности, то таки надо либо жестко зашивать типы через *_t, либо уже писать с рассчетом, что тип не обязательно именно битности х86_64. На тех же avr, насколько я помню, int — таки 2 байта.

Я не видел пока ни одного по сути алгоритма, от слова «вообще».

Простите, но вопрос алгоритма не стоит лично для меня, пока такая форма. Лично у меня возникает ощущение, что алгоритм лазает по памяти, которую он не аллочил. Чтобы точно понять и дать фидбек, мне надо отрефакторить код. Чтобы отрефакторить код мне понадобится инпут от ТСа. А инпут от него будет: «раз у вас тормозит, значит вы напортачили, идиоты»

На тех же avr, насколько я помню, int — таки 2 байта.

Ну вот потому я говорил — что смотрю только на те платформы, где такой толстый-и-быстрый trie имеет хоть какой-то смысл. Там, как правило, данных не менее единиц гигабайт.

Простите, но вопрос алгоритма не стоит лично для меня, пока такая форма.

Ну вот очень жаль, потому что именно такая позиция дала 90% мусора данной темы.

А инпут от него будет: «раз у вас тормозит, значит вы напортачили, идиоты»

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

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

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

Ну вот очень жаль, потому что именно такая позиция дала 90% мусора данной темы.

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

еще б туда расстояние Левенштейна вставить.
Было у него попытка «супер поиска» на ixbt. Там он всем рассказал что расстояние Левенштейна — это фигня и прошлый век, у него гораздо круче будет.

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

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

Это не так: dou.ua/...ign=reply-comment#1006880

Да, после этого вы снизили накал дискуссии, но недостаточно.

И вы это считаете нормальным.

Ваш код, действительно, не готов для продакшн. Но это нормально для PoC. А вот ваша реакция вида «вы все идиоты и не лечитесь, один я в белом пальто стою красивый» — это ненормально.

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

В том-то и звгвоздка, он не совсем рабочий. Он рабочий на уровне PoC. Рабочий библиотечный код не может быть грязным с огромным количеством дублирования, с отсутствующими smart pointers и exception handling. Более того, он не может лазать по памяти, которую вы не заалочили.

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

Я ничего не выношу, я отмечаю как участник open source community, что никто не будет заниматься взомжоно и гениальной (я не признаю пока гениальности, не подумайте), с персоналией, имеющей ваши подходы.

Прикопатсья там есть к чему. Начнем с того, что ваш код падает и не является кросс-платформенным, я уже молчу о качестве самого кода.

Думаю, не было бы у нас линукса, если бы Линус себя вел так, как ведете себя вы. Это при том, что что Линус, что тот же Столман, крайне одиозны сами по себе. Но они не гадят на комьюнитИ, с которым собираются взаимодействовать.

В том-то и звгвоздка, он не совсем рабочий.
Ну сейчас тебе расскажут про фундаментальный код который один раз пишется и потом никогда не читается и нидайбожы не правится. В общим очередная итерация: dou.ua/...ign=reply-comment#1004913

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

таое мнение чрезвычайно ценно для епама вообще и для иеня в частности :)))

Не треба добиватися, треба просто не вважати себе самим розумним. А якщо заявив про себе, то будь ласка доказуй свій клас, інакше ти простий балабол. Давайте простими словами. Змагання виграють не ті, хто краще за все розповідають, які вони круті та як вони всіх можуть виграти, а ті, хто стають на стартову лінію та реально доказують, що вони щось можуть.

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

Я вже писав, що не володію матчастиною. Допоміг би залюбки. Не через його пафос чи ПВВ, а тому що гарні починання завжди треба підтримувати. Адекватне суспільство можно побудувати тільки на альтруїстичному обміні інформацією та досвідом. Стековерфлоу тому дуже яскравий приклад. Називати код іншої людини лайном — це шлях нарцисизма, меншовартості та самозатвердження за рахунок інших. Коротше, бажаю швидше вам вилікуватися від дитячих комплексів.

Не через його пафос чи ПВВ, а тому що гарні починання завжди треба підтримувати.
Это эе время можно потратить на помощь адекватному человеку.
Канечно называть говно говном неполиткорректно, но зато коротко и по делу.

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

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

А хто сказав, що автор критеріїв був адекватним? :D

опыт использования предложенных критериев. И опыт неиспользования предложенных критериев. Про софт управления железом тойоты читали? Вот так там последовательное неприменение best practice. И наверняка там тоже много разговоров про фундаментальный код, в котором все в угоду перфоманса и про то что написанный код решает задачу — и это главное.

Перечитайте мой вопос выше. Почему вы не адресуете претензии, озвученные вами, ТС?

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

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

Коротше, бажаю швидше вам вилікуватися від дитячих комплексів.

Опять же, адресуйте это замечание ТС.

Називати код іншої людини лайном — це шлях нарцисизма, меншовартості та самозатвердження за рахунок інших.

Простите, но изначально с автором так не говорили. Автор сам направил дискуссию в это русло своими реакциями. Пруф тут: dou.ua/...ign=reply-comment#1006880

Почему вы не адресуете претензии, озвученные вами, ТС?
Тому що він мусить пройти весь шлях розвитку особистості самостійно. Неадекватна критика та кидання лайном не стимулює в нього адекватної реакції, а тільки визиває агресію та зворотнє кидання лайном.
Простите, но изначально с автором так не говорили.
Що ми читаємо в постах від коментаторів?
В общем ещё один мастер “и так сойдёт”, не способный довести идею до конца, бросающий проект на 80% готовности. Таких в мире миллионы и цена им 0.
Зверхнє ставлення до ТС
Если бы были мозги, то ты бы это сделал в первую очередь.
Приниження
безумное ЧСВ и не желание слушать других. Поиграется еще некоторое время, потом закинет в пыльный чулан, ибо надоест.
Офігенно “констуктивна” критика! Приниженя можливостей ТС

Давайте продовжу

Какой в этом смысл? В мире есть множество увлекательных вещей, куда подтирание жопы за малолеткой не входит.
а все потому что про CI ты ваще ни в дуб ногой:
Далі продовжувати? Чи вже зрозуміло й так хто чого вартий?
Неадекватна критика та кидання лайном не стимулює в нього адекватної реакції, а тільки визиває агресію та зворотнє кидання лайном.

Я вам кинул ссылки на нормальные комменты. Автор сам спровоцировал агрессию.

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

Що ми читаємо в постах від коментаторів?
Зверхнє ставлення до ТС
Есил вы потрудитесь, то этот коммент Горчака пришле уже после того, как Горчак предложил причесать код, чтобы он мог его показать в QNX и Intel ( dou.ua/...ign=reply-comment#1005965 ) . На что, кстати, Горчак получил весьма некорректный ответ. Странно, чего это после такого ответа специалист с proven record вдруг начал смотреть свысока.
Далі продовжувати? Чи вже зрозуміло й так хто чого вартий?

Вам бы перечитать всю дискуссию с каждым из оппонентов. И всюду будет, как с Горчаком. Люди пытались выйти на конструктив, их ТС назвал идиотами.

Зверхнє ставлення до ТС
Что вижу, то и говорю, типаж ТС довольно распространен.
Приниження
Я просто был удивлён таким гордым отказом. Кто-то оторвался от реальности и не понимает то, чем дышит мир коммерческой разработки. Как мотивировать себя что-то делать? Да никак — оставайтесь в жопе ©.
Что вижу, то и говорю, типаж ТС довольно распространен
Як і ваш. На жаль...
Кто-то оторвался от реальности и не понимает то, чем дышит мир коммерческой разработки.
Як можна відірватися від того, де жодного разу не був?
Як і ваш. На жаль...
А ты, а ты ... детский сад.
Як можна відірватися від того, де жодного разу не був?
ТС пишет посты не приходя в сознание? Вау!
А ты, а ты ... детский сад.
Розумію, нікому не приємно чути правду...
ТС пишет посты не приходя в сознание? Вау!
Навіщо продовжувати образи людини? Ви так самозатверджуєтеся?

Ты хоть читаешь то, что пишешь?

Ты даже читать не умеешь — 01.org/igvt-g — это далеко не личный проект.

И что там ?

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

В эту поддержку не входит бездумное переписывание на все возможные языки.

В общем ещё один мастер «и так сойдёт», не способный довести идею до конца, бросающий проект на 80% готовности. Таких в мире миллионы и цена им 0

Не неси чушь. Ты же не идиот и понимаешь, что Ассоциативный Массив достаточно простая сруктура и в плане интерфейса и в плане кода. Ее дописать, протестировать, покрыть тестами несчастные три функции в интервейсе и выловить все баги достаточно не сложно. Что я и сделал.

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

TestCase 1:

# uname -a
QNX localhost 7.0.0 2016/10/05-09:59:37EDT x86pc x86_64
# ./ha64
=== HArrayInt VS std::map<int,int> testing ===
Insert/Search 1000000 SEQUENCE keys (4 bytes each) ...

run fault pid 479260 tid 1 signal 11 code 1 ip 0×804e003 ./ha64
pid 479260 core file created at /root/ha64.core

TestCase 2:

# uname -a
QNX localhost 7.0.0 2016/10/05-09:59:12EDT x86pc x86
# ./ha32
=== HArrayInt VS std::map<int,int> testing ===
Insert/Search 1000000 SEQUENCE keys (4 bytes each) ...

run fault pid 454684 tid 1 signal 11 code 1 ip 0×804dd96 ./ha32
pid 454684 core file created at /root/ha32.core

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

Что тут меряли, код в студию.
Эта HArrayInt вообще простая как табуретка.

Что тут меряли, код в студию.
Без единого изменения вот этот код:
github.com/.../tree/master/HArray_Linux

Хорошо. Почему у других не падает. У тебя падает. Конфигурация ? Компилятор ?

Другая операционка, я же написал в исходном письме.

Что-то ты юлишь. Какая такая другая операционка. На которой гоуту и офсеты не работают ? Вчера тестировал под Убунту и все ок. Там вообще есть специфика, если ты вставляешь под 40 млн рандом ключей и у тебя есть хотя бы один микроскопический баг, он обязательно выстрелит тебе рикошетом в голову.

Вообщем проверь что Int 32 бита, char 8 бит и short 16 бит на твоей кофемолке, если все так то должно работать !
Или заведи ишью на гите, я попробую глянуть что там может быть.

ообщем проверь что Int 32 бита, char 8 бит и short 16 бит на твоей кофемолке
Чувак, на дворе 21 век. В сад, в общем....

А кстати — размеры на твоей QNX именно такие? (без связи с обсуждаемым софтом)

OK, это хорошо. Просто 21-й век, увы, разнообразнее. С одной стороны винда с sizeof(long)==4, с другой Swift с, цитирую, «On a 64-bit platform, Int is the same size as Int64».

В >99.99% реальных платформ масштаба «не самый крошечный embedded» (то есть те, для которых данная разработка вообще хоть как-то может пригодиться) именно такие размеры — это включает в себя x86 всех видов, ARM, MIPS, Power, другие, которые встречаются.
Поэтому реальность такова, что на это таки можно залагаться (если именно C/C++), и будет такой ещё много-много лет.
Мало того, я у себя на практике вынужден точно так же залагаться на sizeof(long)==8 и на LE. Для этого, конечно, есть специальный unit test, который первым сломается при попытке перенести на что-то более странное (например, Windows, или из железа — zSeries), но сейчас не ориентируемся на другое.

Выше уже писали, что была ошибка из-за неверного размера.

Не видел. Видел ошибку типа «выделили массив размера 1, используем N», но это никак не вопрос размера базового типа.

Есть типы данных int_32, int_fast32 и т.п.

Я как раз _не_ говорю, что не надо использовать эти типы и жёстко оставаться на int/etc. Если бы я адаптировал этот код под свои правила, я бы перевёл на типы из stdint.h или поискал вариант генерализации.
Но основной посыл всё-таки в том, что это — в краткосрочной перспективе — не имеет никакого отношения к основному обсуждаемому вопросу, и завязка на фиксированные размеры достаточна, чтобы взлететь.

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

Потому что автор кода — не автор алгоритма.

Ну если верить сравнению с trie от HP, то тут алгоритм таки новый.

Зачем копать глубже, если уже на поверхности видна куча багов и проблем?

Именно затем, что не в них основной вопрос.

Ну напиши лучше реализацию. Только чтобы результаты были не хуже чем здесь
github.com/...ray_Benchmarks_Ubuntu.txt

Уже сто раз писал. Что код написан чуть ли не единственным верным способом. И давайте это так принимать, пока не доказано обратного.

Чем плох код ? Тем что он работает быстрее чем 99% других поделок ?

Ну так делайте, не вижу реквестов в гите.
У меня живого коммерческого опыта на Си всего 6 месяцев. Я чистый дотнетчик под вин и совершенно мне не интересно заниматься прилизованием тем более под линукс. Вот баги да — я готов пофиксить. Ибо это сам алгоритм. Но заниматься тупым прилизованием не вижу смысла

куча багов и проблем

Наша песня хороша, начинай сначала ©

не надо использовать эти типы и жёстко оставаться на int/etc

Не совсем понял почему поднялась буча по поводу 32х битного инта. Предусматривая это, я специально в stdafx.h ввел алиасы uint, ulong, uchar и дальше везде их использую. Чтобы специально отвязаться от конкретных платформ. Соотвественно можно попробовать запустить и на системах где int и 16 бит

#define uint unsigned __int32
#define ulong unsigned __int64
#define ushort unsigned __int16
#define uchar unsigned __int8
#define ucode unsigned __int8

ты первый додумался до такого новаторского, 7е побо/юсь этого слова — прорывного шага в С++ девелопменте! А вот эти вот чуваки — они не шарят, так фигню всякую лепят... www.boost.org/...ndian/doc/arithmetic.html

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

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

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

Прекрасный пример, очень хорошо иллюстрирует как твой образ мышления(костыли и велосипеды, ога), так и твой полный отрыв от реальности и незнакомство с историей.
Потому что в нашем мире, американцы создали компактную ядерную бомбу, что дважды и доказали в японии.
А русские свою первую версию передрали один в один. С запозданием в пару-тройку лет. И успели сделать так быстро исключительно потому что повторяли как обезьяны технические решения американцев, не тратя тысячи человеколет на резеч с неизбежными тупиковыми ветками стоимостью в сотни человеколет. За подробностями — к судоплатову.

Ох уж эти двоишники. Им бы лишбы бездумно «передирать» тупиковые решения с соседней тетрадки троишников.
Цитата с вики.
«В 1948 году А. Д. Сахаровым были выдвинуты, на основе расчетов, основополагающие идеи конструкции водородной бомбы РДС-6[5]. После этого разработка бомбы пошла по двум направлениям: „слойка“ (РДС-6с), которая подразумевала атомный заряд, окруженный несколькими слоями легких и тяжелых элементов, и „труба“ (РДС-6т), в которой плутониевая бомба погружалась в жидкий дейтерий. США разрабатывали похожие схемы. Например, схема „Alarm clock“, которая была выдвинута Эдвардом Теллером, являлась аналогом „сахаровской“ слойки, но она никогда не была реализована на практике. А вот схема „Труба“, над которой так долго работали ученые, оказалась тупиковой идеей.»

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

#define uint unsigned __int32

Проблема в том, что видя «uint» 99.9% читателей будет подозревать всего лишь сокращение для локального unsigned int. Соответственно разрядности последнего. Потому что это ну очень уж типичная манера. А после этого, если, например, int 16 бит, а твой uint 32 — это грубейшее нарушение POLA.

Если ты бы назвал их BoobenInt и т.п. — вопросов бы, скорее всего, не было.

Мало того, я у себя на практике вынужден точно так же залагаться на sizeof(long)==8
Я последние 15 лет полагаюсь только на stdint. И мне откровенно начхать на размер лонга.

Кое-где не я устанавливаю правила. Написано long — значит, так и будет. Потому что всякие интерфейсы к хери, например, написанной железячниками, которым какой-то злой гипнотизёр внушил, что они классные программисты.

Хм, надо будет сделать очередную попытку запинать народ на тему новых типов :)

Хм, надо будет сделать очередную попытку запинать народ на тему новых типов :)
Обычно после открытия stdint начинается вторая стадия болезни — stdint пихается везде, где нужны машинные типы и не нужны. Что-то типа такого: int32_t status=ioctl(....);

Потом обычно наступает ремиссия и просветление.

int32_t status=ioctl(....);

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

Вот ты оценишь — работаю сейчас с одной либой с API вида

int foo_send (foo_channel_t ch, const void ∗buf, size_t payload_len, int ∗nsent)

возвращает статус (0 или errno), объём отправленного — в *nsent. То есть передавать я формально могу столько данных, сколько влезает в size_t (считаем, 2**64-1), а вот получить подтверждение переданного я могу только на 2**31-1 из них :)
Уж лучше бы они везде int32_t честно воткнули, не страдая попытками впихнуть невпихуемое...

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

Хм, я напустил valgrind с увеличенной redzone-size, и тот молчит. Это что же за «вызход за пределы аллоцированной памяти» такой у тебя?

Что такое memory overcommit ты знаешь, просто на него надо обращать внимание, ибо иногда за это отрывают руки.

==23708== Warning: set address range perms: large range [0×84ca040, 0×284ca048) (undefined)
HArrayInt => Insert: 500 msec, Search: 202 msec.
==23708== Warning: set address range perms: large range [0×84ca028, 0×284ca060) (noaccess)

За 5 тестовых итераций статистика по page fault:

mike@mikenfs:~$ ps -o min_flt,maj_flt 23833
MINFL MAJFL
302304 0

Под конец тестирования:

root@mikenfs:~# ps -o min_flt,maj_flt 23833
MINFL MAJFL
1762243 0

Что он там меряет одному планктону известо. Использование calloc() вместо new/malloc ускоряет работу на 40% — это же писец.

P.S. Всё, я пошёл мыть руки после такого кода...

Что он там меряет одному планктону известо.ц.

Что мы меряем — известно. А вот что ты меряешь, пока что — неизвестно.
Кстате ты std::map померял хоть по своим параметрам, или это игра в одни ворота ? Судя потому как она проц грузит там трешак похуже будет.


Использование calloc() вместо new/malloc ускоряет работу на 40% — это же писец.

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

Там по сути свой рукопашный аллокатор памяти.
Прикрути правильный аллокатор к std::map — будет тебе такая же скорость, что и требовалось доказать. В QNX очень быстрые пул-аллокаторы, только ты ж память жрёшь по пол гига на массив, тоже касается и стека, что работает в винде и линуксе только благодаря lazy memory mapping.

Какие пол гига ? Зависит от того сколько ты собираешся вставить ключей и какое ты передаешь свое capacity в функцию Init. Передай меньше чем 26, например 20 и будет тебе счастье.
Практика показывает, что моя сруктура даже экономней потребляет память чем std::map и GLib
wiki.pikosec.com/...tle=HArrayInt_VS_std::map
wiki.pikosec.com/...ayInt_VS_GLib::GHashTable

Прикрути правильный аллокатор к std::map

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

Прикрути правильный аллокатор к std::map — будет тебе такая же скорость, что и требовалось доказать.

А вот это интересно. Есть быстрый рецепт, как это сделать? А то я с кастомными аллокаторами пока на очень далёкое «вы».

Хорошая статья (их много вообще) devnikhilk.blogspot.ca/...sample-stl-allocator.html

Ладно, я понял, что вопрос неверно задал, но, скорее всего, на него ответа вообще не было бы. Я хотел спросить про средство, которое бы «завернуло» эффективным образом мелкие аллокации в крупные, но потом понял, что тут таки надо алгоритм менять. Так что забей.

Аллокатор существует для «протачивания» std::map под определенные условия задачи. Если вы это сделаете, то скорей всего перекосите мапу для решения определенной задачи. Вообщем, если бы было все так просто, наверняка Степанов (идеолог STL) и сотоварищи встроили бы такой аллокатор изначально.

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

Итак:

= Бинарные деревья (B-Tree, RB-Tree, AVL, KD, Splay и др.)
В общей сложности сложность поиска Log(N). Причем это распросраняется фактически на весь датасет ключей, тоесть это средняя температура по больнице.

= Хештаблицы.
Best Case пишут что O(1) но на самом деле трохи брешут. Потому что скорей О(|K|) ибо ключик таки нужно еще пропустить через хешфункцию, которая может содержать тяжелые матпреобразования, а когда пришли по адрессу, то еще перепроверить что мы правильно пришли.
Worst Case (который случается достаточно редко но с обьемами данных растет) это в общем случае без оптимизаций будет равен O(N).

= VyMa\Trie.
Best Case честное О(1) без каких либо. И этот лучший случай работает условно в 9 из 10 случаев.
Worst Case который случается только если «бомбардировать» структуру последовательными ключами, на самом деле вырождается в строго фиксированые 10 seek times и не более. Тоесть в общем случае это O(|10|). Вы это гарантировано получите, если ваш сет будет содержать больше 4 миллиардов ключей. Теоретически можно было бы избавиться и от вот этого O(|10|), имплементировав вариатор размеров блоков, но эта задача сейчас сложная даже для меня. Просто держим в уме — что это возможно. Еще интересно что Worst Case может быть и выше O(|10|) поскольку он зависит также от длины ключа. Если вы работаете с ключами выше 40 байт, (40/4 = 10), то сложность может дальше линейно вырождатся в O(|K/4|). Но на практике, это длинные ключи, с которыми хештаблицы и бинарные деревья работают вообще не оптимально, особенно по памяти. В целом на Worst Case случай достаточно сложно попасть, также как тяжело попасть в хештаблице на полное вырождение в связной список. И даже в этом самом плохом случае, она будет работать всеравно эффективней чем другие структуры (смотреть результаты бенчмарков с пометкой SEQUENCE)

Чувак, хочешь фокус покажу?

pastebin.com/3smXd8iA

Ололо, моя супер-пупер коллекция обгоняет всё известное науке! Волосы от неё становятся мягкими и шелковистыми! А ещё она решает ближневосточный конфликт и похмеляет с утра!

 assert(collection[i] = 42);

Всё, ты проиграл. Можешь не возвращаться.

Доёб к опечатке низащитан. С == тоже замечательно работает.

Доёб к опечатке низащитан.

«Проверка» от горе-кодера, который не в состоянии добавить -Wall или аналог и посмотреть, что же он написал, имеет отрицательную значимость. Как и его комментарии про «низащитан».

С == тоже замечательно работает.

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

Чувак! Не тупи ты так яросно, ну!


    1. -Wall такую ошибку в макросе не ловит, только в условном операторе. Иди читай ман по опциям gcc дальше
      Шутка, явно обозначенная таковой, не применимая на практике и работающая только за счёт оверкоммита, — это, разумеется, то самое место, где нужно искать опцию, которая позволит-таки поймать это предупреждение
      В коде нет ни одного ключа, идентичного другому. Идентичны только значения, которые могут быть вообще любыми. Если ты не отличаешь ключ от значения, то я сомневаюсь, что ты вообще способен хоть на какую-то осмысленную деятельность
      «Палево» здесь заключается не в значении ключей, а в настройках оверкоммита, что совершенно очевидно как из истории команд, так и из контекста, в котором я написал свой комментарий
  • Итого, чувак, не отличающий ключ от значения и не знающий, что такое оверкоммит, приходит рассказывать мне про отличие сравнения от присваивания. У тебя что, линтер вместо мозга?

    «- Господа, я всё придумал! Мы купим виноград, очень много винограда! 8 тонн! И положим его в огромный целлофановый пакет! Потом закопаем всё это в землю и через месяц выкопаем! Забродивший сок увезем в Москву, где откроем свой завод. И будем этим соком заправлять выдохшиеся фломастеры! Мы станем богатыми! Очень богатыми!
    — Первый канал представляет — ИДИОТЫ! По романам Федоров Михайловичей Достоевских.» © КВН, «ЛУНА» (Челябинск)

    -Wall такую ошибку в макросе не ловит, только в условном операторе.

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

    и работающая только за счёт оверкоммита

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

    Если ты не отличаешь ключ от значения,

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

    а в настройках оверкоммита

    Докажи. Более традиционной структурой, которая даёт эффективный поиск и использует такой же «overcommit». Пока что с твоей стороны это сплошной bullshit.

    не отличающий ключ от значения

    И снова — учись читать.

    У тебя что, линтер вместо мозга?

    У тебя, судя по последним постингам, мозга вообще нет. Или ты его засунул в зад вместо головы.

    Так он же написал про контекст. Что это была шутка с его стороны и ожидает что отнесутся как к шутке. Немного не качественная конечно, всетаки для более тонкого троллинга нужно было бы пофиксить «детские» ошибки, но тем не менее :)

    Так он же написал про контекст. Что это была шутка с его стороны

    Тогда он должен был и к моему исходному замечанию отнестись как к шутке. Он же вместо этого полез в бутылку.

    А учитывая, что вообще-то overcommit это тяжёлая палка о двух концах, и в каждой ОС решается по-своему и всё равно через одно место — тут совсем не тема для шуток.

    Воистину, хуже идиота только агрессивный идиот, упорствующий в своём идиотизме.

    Ну тогда тем более сам должен был отловить, или вместо макроса использовать шаблонную функцию.
    Какие шаблонные функции в C, родное сердце? Ты ещё и C от C++ не отличаешь?
    Чтобы доказать, что оверкоммит тут хоть как-то при чём...
    Достаточно посмотреть на размер аллоцируемой памяти. Если бы не оверкоммит, то процесс был бы прибит OOM-killer’ом.
    показать действительно аналогичную реализацию со сравнимой скоростью, которая бы что-то полезное делала, а не просто заливала память константами. Ты даже не попытался это сделать.
    Божечки! Ну перечитай ты тред, в который я отвечал. Мне реально западло объяснять суть анекдотов тем, до кого они не доходят даже с третьего раза.
    Докажи. Более традиционной структурой, которая даёт эффективный поиск и использует такой же «overcommit».
    Наркоман что ли? Полагаться на overcommit при реализации general-purpose структур нельзя, потому что его настройки могут быть разными. Что, кстати, и произошло выше по треду на QNX, где существуют требования реалтайма и поэтому lazy mapping недопустим.
    Воистину, хуже идиота только агрессивный идиот, упорствующий в своём идиотизме.

    О, ты посмотрелся в зеркало? Отлично, это первый шаг к правильным выводам. Только не останавливайся.

    Какие шаблонные функции в C, родное сердце? Ты ещё и C от C++ не отличаешь?

    А тебя никто не заставляет ограничиваться чистым C. А с учётом того, что тестируемый код на C++, вообще непонятно, откуда и зачем ты взял C.

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

    Хороший метод: сдулся — объявить всё сказанное шуткой и анекдотом. Боюсь только, не пройдёт.

    Полагаться на overcommit при реализации general-purpose структур нельзя, потому что его настройки могут быть разными.

    Теперь тебе осталось показать, что кто-то полагается на «конкретные настройки overcommit» при определении скорости.
    Если ты назвал таким «полаганием» использование крупноблочного new[], то тут как раз в типичном случае нет разницы с постепенным аллоцированием в результате наращивания объёма мелкими кусочками.
    А ещё это бы серьёзно повлияло на результаты в случае изменения размера начальной аллокации (значение параметра init()). Но этого не происходит, числа достаточно близкие и всё равно в выигрыше по сравнению с std::map.

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

    Что, кстати, и произошло выше по треду на QNX, где существуют требования реалтайма и поэтому lazy mapping недопустим.

    Что случилось с QNX, надо обсуждать с Горчаком. Он хоть как-то осмысленно это обсуждает, в отличие от тебя. Но в любом случае это не основная проблема и явно не причина скорости реализации.

    О, ты посмотрелся в зеркало? Отлично, это первый шаг к правильным выводам. Только не останавливайся.
    А когда я ходил в детский садик, то там ещё любили говорить «я в домике». Рекомендую освоить. Как раз соответствует твоему уровню развития.
    А тебя никто не заставляет ограничиваться чистым C.
    Мой код. На чём хочу, на том и пишу. А C++ просто не нужен.
    А с учётом того, что тестируемый код на C++, вообще непонятно, откуда и зачем ты взял C.
    Чувак, вот ты правда думаешь, что я сравниваю что-то с кодом топикстартера? Вот правда?
    Хороший метод: сдулся — объявить всё сказанное шуткой и анекдотом. Боюсь только, не пройдёт.
    Ага, разумеется. Я это всё писал всерьёз. И всерьёз предлагал аллоцировать массив в 16 Гб.
    Теперь тебе осталось показать, что кто-то полагается на «конкретные настройки overcommit» при определении скорости.
    Ты сам мне это предлагал предыдущим постом. У меня все ходы записаны:
    Докажи. Более традиционной структурой, которая даёт эффективный поиск и использует такой же «overcommit»
    структурой, которая использует такой же «overcommit»
    структурой, которая использует «overcommit»
    Из этого я и делаю вывод, что проблема std::map или в мелких аллокациях и недружественности к кэшу, или собственно алгоритме с недостаточно «плоским» деревом, или в обоих.
    В обоих. Крачно-чёрное дерево имеет асимптотическую оценку сложности как вставки, так и поиска O(log n), где n — количество элементов. Кроме того, нелокальные прыжки от ноды к ноде по указателям инвалидируют кэш. Trie имеет оценку O(n), но n в данном случае — это длина ключа. Таким образом, корректнее сравнивать структуру ТС с хэш-мапой.
    Что случилось с QNX
    Можно повторить и на Linux, установив vm.overcommit_memory=2 и, опционально, ограничив vm.overcommit_ratio. На моей машине падение воспроизводится с ограничением памяти до 4 Гб.
    Мой код. На чём хочу, на том и пишу. А C++ просто не нужен.

    Вот это и есть твоё «в домике». Спасибо за подтверждение.

    Чувак, вот ты правда думаешь, что я сравниваю что-то с кодом топикстартера? Вот правда?

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

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

    Что случилось с QNX, надо обсуждать с Горчаком. Он хоть как-то осмысленно это обсуждает, в отличие от тебя.
    Eh? Я же ясно сказал — сумасшедший расход памяти и стека. Скорость такой ценой не нужна.
    Я же ясно сказал — сумасшедший расход памяти и стека. Скорость такой ценой не нужна.

    Там начальные параметры показывают тот расход, можно подтюнить. Для многих задач (верю, что не для твоих) это лучше. Например, у нас сейчас типичный подход «аллоцируем всё по максимуму, а дальше не меняем», пусть оно даже 40GB займёт, но это оправдывается последующей скоростью (причём как суммарной, так и снижением peak latency), особенно с учётом Java GC (реально работает бутерброд из Java+C). И у нас тоже местами применяли trie для скорости лукапа. Поэтому и интересно, что же делает ТС.

    Для твоих же условий надо смотреть немного на другое — насколько оно будет адекватно работать с относительно небольшой начальной аллокацией, и расширением крупными блоками. Например, говоришь, что можно выделять по необходимости блоками по 256KB, при этом ограничить заполняемость снизу уровнем 70% — и пусть выкарабкивается из таких условий :)

    Если у тебя память ставится в главу угла, глянь реализации Trie на основе ацикличных графов — DAWG например. Эти реализации как раз сильно перекошены на экономию памяти с моделью доступа read-only.

    Неплохо.
    Тебя ожидает успех Малевича в программировании.

    Что такое memory overcommit ты знаешь

    Знаю. Что это самое дерьмовое грязное место во всей концепции современных ОС, и любая работа получается только тогда, когда хаки user land когерентны хакам kernel land. То, что у тебя получилось — это всего лишь их несочетаемость друг с другом. К качеству основного алгоритма это никак не относится.

    За 5 тестовых итераций статистика по page fault:

    Если всё равно быстрее конкурента, значит, этих фолтов не так уж и много?

    P.S. Всё, я пошёл мыть руки после такого кода...

    В описанных условиях — код более чем нормальный. На причесать найдётся народ. :)

    Что такое memory overcommit ты знаешь

    Знаю.

    Равно как знаю и то, что в десктопно-серверных ОС без него вообще сейчас не бывает. Запускаеш простенькую программку под обычной glibc, а она аллоцирует по 64MB на тред. Вот удобнее ей так, с целыми аренами общаться. 8 тредов — 512MB. А Бубен всего-то 256 одним рывком просил. Так кто прожорливее?

    просто на него надо обращать внимание, ибо иногда за это отрывают руки.

    Да, отрывают. Только не там и не так, как надо.

    Что такое Mach-styled VM, ты, наверно, знаешь. Вместе с его эффектами такого рода:

    1. Новый процесс. В память отображён бинарник и библиотеки. VSZ может быть
    дофига. RSS — только то, что изменилось (таблицы импорта в библиотеках
    плюс минимум данных и стека).
    2. Замапили гигабайтный файл. VSZ вырос на 1G. RSS не поменялся.
    3. Прочитали этот файл в памяти. VSZ не изменился. RSS — вырос на
    гигабайт или чуть меньше (если не сильно тесно).
    4. Подумали о жизни. В это время другим процессам потребовалась
    память. Половину кэша файла в памяти продискарили, VSZ не изменился,
    RSS упал на 500M.
    5. Форкнули из себя 10 копий. Все копии получили одну и ту же память
    кроме параметров в стеке (возвращаемый pid). Суммарный VSZ равен 10G,
    цена этой информации — 0 целых хрен десятых Суммарный RSS стал 5G,
    при этом реально в памяти занято только 500M.
    6. Одна из копий аллоцировала 100M и записала их данными обработки.
    Её VSZ и RSS выросли на 100M. Такой же рост у суммы.
    7. Эта копия форкнулась. Суммарные VSZ и RSS выросли на 1.1G, реальных
    затрат не поменялось.
    8. Новый форк переделал все данные в 100M области. Суммарные VSZ и RSS
    не поменялись, фактические затраты обоих выросли на 100M за счёт
    хранения копии.
    9. Ещё кому-то потребовалась память и система продискардила остаток
    большого файла в памяти. Суммарный VSZ не изменился. Суммарный RSS
    упал на 5.5G. Фактические затраты в памяти сократились на 500M.

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

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

    Возможно, в QNX этого нет. Тогда там любое добавление R/W памяти процесса, включая изменение режима на R/W, и любой fork должен проверяться на переполнение суммарной VM. Но если так, то шареная R/W память в нём — дикий расход суммарной VM. Даже когда ты просто подключил libc, таблицы её перемещений будут учитываться каждому процессу отдельно. Там же нет ключика mprotectʼу «вот это изменённое состояние теперь зафиксировать, для попытки следующих изменений создавать новый shadow object»? Гугл мне говорит, что нету. А значит — точно так же каменный век — или неэффективный перерасход VM, или возможность получить в лоб без предупреждения.

    Единственный качественный подход тут — увы, слишком сложный, чтобы его массово поддерживали — будет так:
    1. Заводить на процесс некоторый объём VM резерва в виде закоммиченных, но никуда не отображённых, страниц (без содержимого). Функции set/get управления объёмом этого резерва. По умолчанию размер 0 (аналогично текущему состоянию), сбрасывается в 0 у потомка после fork().
    2. При исчерпании VM (включая и общее количество, и различные групповые лимиты вплоть до rlimitʼа одного процесса) начинает расходоваться этот резерв.
    3. Оповещение о расходе этого резерва ниже сконфирурённого порога (оповещение сигналом, готовностью чтения спец. дескриптора — по обстановке).

    Вот если я где-то такое увижу — поверю, что там действительно думают о последствиях overcommitʼа. А без этого — как-то неинтересно, хоть там трижды «realtime» QNX.

    Равно как знаю и то, что в десктопно-серверных ОС без него вообще сейчас не бывает.
    Многие ли знают, что например в Windows 7 нет оверкоммита? Как нет? А вот так просто, его нет. Зато есть поддержка 2Мб страниц памяти, что сделало семёрку одной из самых любимых ОС за быстроту и отзывчивость. А также нормальную работу без свопа, кто его выключает в винде, тот поймёт.
    А Бубен всего-то 256 одним рывком просил. Так кто прожорливее?
    СУдя по отчёту волгринда он попросил пол гига и ему их дали, после он выжрал около полумегабайта стека, причём каким-то образом зацепив при это стек-гарда, тот ему этого не простил, ибо стек в QNX может увеличиваться динамически для основного потока, только если это происходит естественным путём, а не переполнением. Корка после гарда бесполезная и содержит обычный код, который повалился при обычном push rbp. В линуксе понятие переполнение стека очень мутное — оно подчиняется тем же законам, что и обычная память, а значит можно выжирать гигабайтами, пока не столкнёшься с данными или кодом.
    Гугл мне говорит, что нету. А значит — точно так же каменный век
    Этого нет в POSIX, а значит без него можно прожить, либо, как в данном случае — оно вторично — это попытка латать лодку во время шторма.
    А без этого — как-то неинтересно, хоть там трижды «realtime» QNX.
    Интересно или нет, но это не отменяет неработоспособности под QNX.

    P.S. Ну и все примеры с форками — это каменный век. Не зря посикс говорит, что если применил форк, то лишаешься поддержки потоков в данном приложении до окончания выполнения. Форк — это очень и очень грязно.

    Многие ли знают, что например в Windows 7 нет оверкоммита?

    Если вопрос из серии «удалось ли поразить собеседника?», то отвечу, что я это знал, но пару раз уже забывал, за ненужностью. Вообще вся система памяти в Windows в этом плане, да, прожорливее, но честнее. Одно из немногих её преимуществ :) которое, однако, компенсируется тяжёлыми заклинами при полном исчерпании (Linux пришлёпнул что-то и пошёл дальше, а тут может висеть часами).

    Зато есть поддержка 2Мб страниц памяти, что сделало семёрку одной из самых любимых ОС за быстроту и отзывчивость.

    В линуксе тоже есть поддержка. И не только large pages, но и huge pages :) Вот обсуждают улучшение от их работы.
    С другой стороны, large и huge pages это тупой хак (как почти всё у Intel). Чтобы получить large page, нужно аллоцировать 2MB одним куском, что может потребовать больших реаллокаций, а иногда и крайне сложно из-за того, что часть страниц неперемещаемы (wired). Лучше бы начали наконец увеличивать базовый размер страницы (сейчас оптимум около 64KB), или вообще сделали его настраиваемым в широких пределах, как в IA64.

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

    Если «сделали» это по сравнению с Windows XP, верю. Если по сравнению с лучшими конкурентами, там нет ничего особенного.

    после он выжрал около полумегабайта стека

    Вот это уже конкретно. Если это alloca(), то это проблема QNX, что она не подружила аллокатор со своим stack guard. Если что-то другое, надо поискать, что это было.

    Этого нет в POSIX, а значит без него можно прожить

    Уже смешно :) ты сам знаешь, что любой межвендорский стандарт это неизбежно только среднее по больнице.

    это попытка латать лодку во время шторма.

    Именно то, что я предложил, как раз лечение в самом корне. Вторично это выключать overcommit, делать ему хитрую логику и т.п. — это улучшает статистические показатели, но не лечит в основе (и в самых жёстких проявлениях).

    Не зря посикс говорит, что если применил форк, то лишаешься поддержки потоков в данном приложении до окончания выполнения.

    Это с чего такой вывод? Потомок после форка наследует один тред, да. И для устранения проблем от потери остальных (если это важно, а не просто exec() дёрнули) есть целевые методы. Родителю же без разницы, он продолжает работать как обычно.
    Давай точную цитату, или я считаю, что ты что-то недокурил.

    Если вопрос из серии «удалось ли поразить собеседника?», то отвечу, что я это знал, но пару раз уже забывал, за ненужностью.
    Я по поводу вот этой категоричности, цитирую:
    Равно как знаю и то, что в десктопно-серверных ОС без него вообще сейчас не бывает.
    В остальных сериях, 8 и 10 ввели dynamic memory из-за виртуализации, ибо она кушает много, но всё равно это далеко не тот убогий линуксовый оверкоммит.
    Вот это уже конкретно. Если это alloca(), то это проблема QNX, что она не подружила аллокатор со своим stack guard. Если что-то другое, надо поискать, что это было.
    Надо. Но как я уже сказал автору, ковыряться в данном гуано — это далеко за областями моего интереса, лучше это время уделить другим опенсоурс продуктам, где их гуано лежит ближе к душе. Кроме того QNX имеет замечательные инструментальные средства, которые доступны в трайал 30 дней, одно из них Memory Analysis и System Profiler (на базе иклипса). Любой, кому интересно может попробовать.
    Это с чего такой вывод? Потомок после форка наследует один тред, да.
    О боже, они таки реанимировали труп в новом посикс стандарте и вдохнули в него подобие жизни. Я этот момент пропустил. Раньше было проще — либо то, либо то. 20 с лишним caveats и ещё столько же implementation-specific и undefined операций. Труп стьюардессы нужно однозначно закопать.
    Я по поводу вот этой категоричности, цитирую

    Согласен. Windows у меня систематически не в контексте, поэтому забываю.

    В остальных сериях, 8 и 10 ввели dynamic memory из-за виртуализации, ибо она кушает много, но всё равно это далеко не тот убогий линуксовый оверкоммит.

    Почитаю, спасибо.

    где их гуано лежит ближе к душе

    :)

    О боже, они таки реанимировали труп в новом посикс стандарте и вдохнули в него подобие жизни.

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

    Меня в этом плане больше «радует» введение огромного количества новых атомарных (и нестандартных пока, увы) вызовов с опциями очереднаязюка_CLOEXEC. К сожалению, поезд слишком далеко ушёл, чтобы CLOEXEC автоматически ставить вообще на любые дескрипторы, даже настройкой уровня процесса с умолчанием на старом режиме(?) Вместе с другими соображениями (типа, nonblock должно быть опцией операции, в крайнем случае — дескриптора, а не ofile-сущности, *at() надо было планировать как можно раньше) — хочется таки машину времени.

    Надо. Но как я уже сказал автору, ковыряться в данном гуано — это далеко за областями моего интереса

    Замечательно, значит прикрываем тогда ветку Линукс, пускай Линуксоиды продолжают сидеть на старой и невероятно тормозной реализации std::map и ее аналогов.
    Ветка закрыта до тех пор, пока не найдется толковый человек который сможет рассказать в чем проблема.
    QNX я уж точно ставить не буду.

    Во второй половине поста указана проблема, ты просто её поскипал, так как не понимаешь о чём речь:

    dou.ua/...rums/topic/18849/#1006269

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

    Дай ряд рекомендаций, как переделать реализацию, чтобы избавится от этой проблемы именно под QNX.
    Старайся не есть стек, лучше выдели какую-то память заранее.
    Ну так я уже писал, что в Линуксах я почти полный ноль.
    Касательно скорость std::map под линуксом — я привёл статистику исключительных ситуаций — за первый тест около 60000 page fault операций, что как раз соответствует 60000*4096=~256Mb RAM. Т.е. каждый 25-й инсерт генерировал исключительную ситуацию, когда операционная система выделяла страницу памяти и подставляла её твоему процессу для заполнения. Естественно, что 25 инсертов выполняются гораздо быстрее чем подстановка страницы памяти. Вот всё время и профукивается на уровне ОС,а не в std::map.

    В лохматые времена реализация SGI STL содержала пул аллокатор с возможностью пре-аллоцирования памяти, т.е. ты знаешь, что у тебя будет 10млн элементов и ты мог заранее зарезервировать память у аллокатора ну или дать ему хинт, что вставлять будешь дофига, поэтому доаллоцировать он будет большими кусками, а не страницами по 4096 байт. С другой стороны я видел мало реальных использований std::map на больших данных, обычно пару тысяч элементов, тут скорость не принципиальна.

    В своём тесте для std::map ты можешь цикл с insert запустить два раза, во второму случае он просто сделает обновление записи, без каких-либо выделений памяти и можешь посмотреть на разницу в скорости. И вычислить сколько профукивается времени на реальное выделение памяти.

    Очень удобно все спихнуть на оператор new и издержки ОС внутри std::map, но тогда почему lookup операция в std::map еще медленее работает чем в HArrayInt/HArrayVarRAM. Разница в 10 и более раз на многих кейсах. Ведь там же уже ничего не выделяется по памяти. Мы просто находим и читаем нужный элемент.

    Очень удобно все спихнуть на оператор new и издержки ОС внутри std::map
    Извини, что пытался помочь. Удачи.

    Ты нормально поможешь если опишешь нормально условия при каких возникают проблемы.
    1. HArrayInt проблема только или с HArrayVarRAM тоже.
    2. Код теста желательно с локализацией примерно где есть фолт с страницей хотя бы приблизительно. Напр. на 1 млн все ок. А вот на 1.1 млн проблема
    3. Напишешь компилятор чем скомпилировал. Ось мы уже знаем.
    Хотя бы так.

    По STD::map я вроде как матан писал с сложностями алгоритма. Там ловить нечего.

    если на линуксе efence запользовать, то тоже падать будет
    mb@mb-work:~/tmp/HArray.UNX$ ./test
    === HArrayInt VS std::map<int,int> testing ===

    Electric Fence 2.2 Copyright © 1987-1999 Bruce Perens <bruce@perens.com>
    Insert/Search 1000000 SEQUENCE keys (4 bytes each) ...
    HArrayInt => Insert: 11 msec, Search: 2 msec.

    ElectricFence Exiting: mprotect() failed: Segmentation fault (core dumped)

    Можно more details ?
    В идеале подебажить на какой строчке падает.

    В идеале подебажить на какой строчке падает.

    Самое полезное в треде, я только сейчас узнал об Electric Fence. Спасибо. Я пытался пригвоздить память в линуксе через mlockall(MCL_CURRENT | MCL_FUTURE); но оно ещё не работает — не сделали поддержку. Иногда, когда с QNX пересаживаешься на Linux, то бывает ощущение что попал в какой-то ретро мир :) где ещё не изобрели электричество :)

    Самое полезное в треде, я только сейчас узнал об Electric Fence.
    Вот, кстати, да. Одно это стоило прочтения треда.

    Конечно я не знаток

    Electric Fence
    , но вы не подумали что хрень это все.
    У вас есть кусок памяти. Вы его привели к одному обьекту класса, потом по условиям задачи к другому обьекту класса. Все легально с точки зрения работы с памятью, вы работаете только с тем что вам выделили, так задумано алгоритмом. И что же скажет на это Electric Fence? Расскажет что вы залезли за пределы какогото типа ?
    Самое полезное в треде, я только сейчас узнал об Electric Fence.

    Мой FAQ уже лет, наверно, 15 существенно не меняется, а ты его так и не прочитал :(

    Мой жизненный TODO содержит материалов лет на 200 изучения, так что я много чего ещё не прочитал :)

    А я приду и поломаю всем праздник.

    : g++ -o test 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 -lefence
    : gdb ./test
    : run
    ...
    
    Program received signal SIGSEGV, Segmentation fault.
    0x00007ffff7014446 in strlen () from /usr/lib/libc.so.6
    : bt
    ...
    #5  0x00007ffff7bd6e0e in memalign () from /usr/lib/libefence.so.0
    #6  0x00007ffff78dca48 in operator new (sz=sz@entry=40) at /build/gcc/src/gcc/libstdc++-v3/libsupc++/new_op.cc:50
    ...
    #13 testStdMapInt (keys=keys@entry=0x7ffff4750600, countKeys=countKeys@entry=1000000) at Main.cpp:94
    #14 0x000000000040735c in HArrayInt_VS_StdMap_IntKey (startOnAmount=startOnAmount@entry=1000000, stepOfAmount=stepOfAmount@entry=2000000, 
        stopOnAmount=stopOnAmount@entry=10000000) at Main.cpp:156
    #15 0x0000000000407ae8 in main () at Main.cpp:548
    :frame 13
    #13 testStdMapInt (keys=keys@entry=0x7ffff4750600, countKeys=countKeys@entry=1000000) at Main.cpp:94
    94			mymap[keys[i]] = keys[i];

    Пытаемся понять, что именно там происходит.

    : strace ./test > test.out
    : grep mprotect test.out | tail
    ...
    mprotect(0x7f9c8291b000, 1323008, PROT_NONE) = 0
    mprotect(0x7f9c8291b000, 1323008, PROT_READ|PROT_WRITE) = 0
    mprotect(0x7f9c826bc000, 4096, PROT_READ|PROT_WRITE) = -1 ENOMEM (Cannot allocate memory)
    : grep mprotect test.out | wc -l
    132421

    Смотрим mprotect(2), 3-я причина для ENOMEM. Пересобираем без -lefence, strace, grep, 20 mprotect’ов. Причина в efence, а не в тестируемом коде.

    Убираем лишние нули в main, пересобираем с -lefence, всё проходит.

    Дико извиняюсь. Мне намекнули, что это мог быть стеб.
    Так есть баг в HArrayInt ? Стоит Linux + Efence ставить и юзать или нет ?

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

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

    сообщество поможет отрефакторить код

    [sarcasm on]
    "Гении господствуют над хаосом, бездарности стремятся к порядку"©
    [sarcasm off]

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

    Я думаю, що все реально. Очікуємо на статтю.

    Багов, которые может показать efence, в HArrayInt нет. У efence есть ограничение на количество malloc’ов. Тест вида «давайте сделаем 100K+ insert’ов» споткнулся об это ограничение.

    Поставить что-то для контроля проблем с памятью стоит. Именно efence — наверное нет, valgrind покажет всё, что может показать efence, плюс кое-чего сверху, и он удобней.

    Зачем тебе

    code::blocks
    при пользовании студией. Достаточно make или смаке.
    Пока большей частью не перешел на QtCreator большей частью так и работал, писал код в студии, а в линухе только собирал и тесты прогонял. Отладчика же студийного хватало в линухе IDE не нужна была совсем.

    Сделай, я не шарю и иду кататься на велосипеде с зеркалкой.

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

    Если есть баги пишите Step To Reproduce и заводите Issue на GitHub.
    По моему мнению там багов нет вообще. Протестировано в двух движках баз данных под высокими нагрузками и на больших обьемах в течении нескольких лет.

    Трое офицеров играют у одного из них дома в карты. Только раздали, вдруг из детской выскакивает сын хозяина и кричит:
    — А у папы два туза!
    Делать нечего, раздали по новой. Снова выскакивает сын и кричит:
    — А у капитана червовый марьяж!
    Снова пересдали. Снова выскакивает сын и кричит:
    — А у поручика...
    — Погоди! — перебивает поручик Ржевский , и уводит мальчика в детскую.
    Через пару минут возвращается, садится играть дальше. Проходит 5, 10,
    15 минут — мальчика нет. Хозяин квартиры спрашивает:
    — Поручик, Вы что, его побили?
    — Как можно, я же офицер!
    — А что же Вы сделали?
    — Я его дрочить научил

    ТС, исправь код чтоб под линуксом из коробки собирался без бубна

    Если нет линукса дома, на Azure за несколько долларов можно взять виртуалку.

    мейкфайл постараюсь добавить.
    Доступ к Линуксу есть.

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

    в целом похвально, только вы явно выбрали не того «противника».

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

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

    — вы сразу выделяете память
    Потому что там по сути встроен свой эффективный менеджер памяти, который запрашивает память по-странично.
    у вас фиксированный тип данных
    Не фиксированый. В одну и туже структуру можно добавлять ключи разной длины, но они выровнены на 4 байта.
    — std заморачивается на exception
    std::bad_allock и я пробрасываю. А других эксепшинов там по идее не должно быть.
    проводить тесты надо через 2 отдельных приложения, плюс выполнять их много раз
    и так далее

    Проводите. Тесты третьей стороны всегда хорошо.

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

    Открою страшную тайну....у компилера есть ключи для выравнивания памяти автоматически всего и везде, а также прагмы.
    Эффективный манагер памяти ... собственно это тоже решается путем линковки с другими либами (например: goog-perftools.sourceforge.net/doc/tcmalloc.html или передачей в качестве параметра своих аллокаторов для std контейнеров.

    Так же std контейнеры умеют пре-выделять память, например vector::reserv()

    Ну круто же. Но судя по бенчмаркам у меня сделано еще круче.

    В ваших бенчмарках вы влоб все делаете. Попробуйте стд-мап дать другой аллокатор, например вот из пулла буста: www.boost.org/...nterfaces/pool_alloc.html
    И сравните, как изменится ее скорость, с другими аллокаторами. По умолчанию, кстати, new/delete потоко безопасны (мутексы там), а malloc/free нет. Не смотрел, что у вас там, но замена new на malloc по идее тоже ускорит на 1 потоке. Но тогда не сработает способ с аллокаторами, тогда нужно менять либы (см выше).

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

    Существенно не поможет. Можете попробовать.

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

    Я надеюсь STD::map не сломаете и оживите его хотя бы на процентов 15.
    А мне там делать нечего, Бо я понимаю что в терминах О большого там ловить особо нечего. STD::map тут выступает как еще одна унылая реализация красно-черных деревьев с мат базой времен студенческой молодости Стоунбрейкера

    давайте так, конкретная реализация деревьев в стандарте не прописана, если микрософт проебал — все к ним, гцц реализация в 50 раз быстрее вашей.

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

    Я кстати могу протестить твой код на живом примере, но мне нужна реализация на С, а не просто интерфейс. Сейчас работают BSD RBTREE макросы быстрее в 2.5 раза чем GNU C++ реализация std::map и быстрее раз в 5 чем LLVM С++ реализация. Задача — хранить связки физического адреса памяти и виртуальной памяти для одного и того же участка для хоста и для гостевого клиента (разные виртуальные адреса), если элемента в списке нет, то мапится память и адреса вносятся в список и так далее. Цель — не мапить повторно то, что уже замапленно. Это обычная задача виртуализации GPU. За 1 фрейм можно намапить до 3.5Gb памяти и в конце фрейма освободить её, чтобы вначале нового фрейма замапить заново, но уже, возможно, по другим адресам. Операция очистки списка должна быть не хуже, чем максимальное время поиска.

    Для постоянного римапа 1Gb памяти специальный тест выдаёт около 115FPS в гостевой ОС. Можем потестировать твою поделку, но только С реализация.

    А на Lua тебе не переписать случайно ? Ну или Руби Паскаль Делфи чтобы удобней было тестировать мою «поделку».

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

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

    если бы результаты были стоящие
    Про результаты можно почитать тут:
    forum.ixbt.com/...aram=1&posts=&id=26&id=40
    Топики один другого забавней.

    Еслибы да кабы. О чем спич ?
    Почему написано на Си++, а не на Си ? Серьезно ? А что есть принципиальная разница ?

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

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

    Моё дело предложить...

    а malloc/free нет
    Согласно POSIX.1-2008, всё объявленное там thread-safe.

    в конкретно взятом сегодня снапшуте мес 1 назад обновы archlinux malloc работает норм, при компиляции того же кода на маке — фейлит ...потоками.

    Посикс тут очень жёсткий, если завёл потоки — делай всё thread-safe. Не можешь — убирай потоки. Ну а OSX посикс сертификация только базовая была, поэтому они и так не-посикс ОС.

    === HArrayInt VS std::map<int,int> testing ===
    Insert/Search 1000000 SEQUENCE keys (4 bytes each) ...
    HArrayInt => Insert: 27 msec, Search: 11 msec.
    std::map => Insert: 239 msec, Search: 83 msec.

    Insert/Search 3000000 SEQUENCE keys (4 bytes each) ...
    HArrayInt => Insert: 80 msec, Search: 35 msec.
    std::map => Insert: 700 msec, Search: 287 msec.

    Insert/Search 5000000 SEQUENCE keys (4 bytes each) ...
    HArrayInt => Insert: 132 msec, Search: 59 msec.
    std::map => Insert: 1177 msec, Search: 473 msec.

    Insert/Search 7000000 SEQUENCE keys (4 bytes each) ...
    HArrayInt => Insert: 185 msec, Search: 82 msec.
    std::map => Insert: 1685 msec, Search: 690 msec.

    Insert/Search 9000000 SEQUENCE keys (4 bytes each) ...
    HArrayInt => Insert: 239 msec, Search: 106 msec.
    std::map => Insert: 2157 msec, Search: 888 msec.

    Insert/Search 1000000 RANDOM keys (4 bytes each) ...
    HArrayInt => Insert: 18 msec, Error
    Search: 0 msec.
    std::map => Insert: 166 msec, Error
    Search: 1 msec.

    Insert/Search 3000000 RANDOM keys (4 bytes each) ...
    HArrayInt => Insert: 49 msec, Error
    Search: 1 msec.
    std::map => Insert: 473 msec, Error
    Search: 0 msec.

    Insert/Search 5000000 RANDOM keys (4 bytes each) ...
    HArrayInt => Insert: 78 msec, Error
    Search: 0 msec.
    std::map => Insert: 766 msec, Error
    Search: 0 msec.

    Insert/Search 7000000 RANDOM keys (4 bytes each) ...
    HArrayInt => Insert: 109 msec, Error
    Search: 1 msec.
    std::map => Insert: 1070 msec, Error
    Search: 0 msec.

    Insert/Search 9000000 RANDOM keys (4 bytes each) ...
    HArrayInt => Insert: 140 msec, Error
    Search: 0 msec.
    std::map => Insert: 1383 msec, Error
    Search: 1 msec.

    Insert/Search 1000000 PERIOD keys (4 bytes each) ...
    HArrayInt => Insert: 51 msec, Search: 13 msec.
    std::map => Insert: 234 msec, Search: 90 msec.

    Insert/Search 3000000 PERIOD keys (4 bytes each) ...
    HArrayInt => Insert: 153 msec, Search: 40 msec.
    std::map => Insert: 702 msec, Search: 284 msec.

    Insert/Search 5000000 PERIOD keys (4 bytes each) ...
    HArrayInt => Insert: 257 msec, Search: 65 msec.
    std::map => Insert: 1176 msec, Search: 468 msec.

    Insert/Search 7000000 PERIOD keys (4 bytes each) ...
    HArrayInt => Insert: 363 msec, Search: 91 msec.
    std::map => Insert: 1654 msec, ^CPress any key to continue . . .

    void HArrayInt_VS_StdMap_IntKey(uint startOnAmount, uint stepOfAmount, uint stopOnAmount)
    {
    printf("=== HArrayInt VS std::map<int,int> testing ===\n");

    uint* intKeys = new uint[stopOnAmount];
    uint* intVals = new uint[stopOnAmount];

    fillSeqInts(intKeys, stopOnAmount);

    for (uint countKeys = startOnAmount; countKeys <= stopOnAmount; countKeys += stepOfAmount)
    {
    printf("Insert/Search %u SEQUENCE keys (%u bytes each) ...\n", countKeys, sizeof(uint));
    testHArrayInt(intKeys, intVals, countKeys);
    testStdMapInt(intKeys, intVals, countKeys);
    printf("\n");
    }
    ...
    void testHArrayInt(uint* keys, uint* vals, uint countKeys)
    {
    printf("HArrayInt => ");

    HArrayInt ha;
    ha.init(26);

    clock_t start, finish;

    //INSERT ===========================================

    start = clock();

    for (int i = 0; i < countKeys; i++)
    {
    ha.insert(keys[i], vals[i]);
    }

    finish = clock();

    printf("Insert: %d msec, ", (finish — start));

    //SEARCH ===========================================
    start = clock();

    for (uint i = 0; i < countKeys; i++)
    {
    if (ha.getValueByKey(keys[i]) != vals[i])
    {
    printf("Error\n");
    break;
    }
    }

    finish = clock();

    printf("Search: %d msec.\n", (finish — start));

    //ha.print();

    ha.destroy();
    }

    Это под виндой. А под Линух сделай cmakelist.txt (или makefile).
    больше ничего не менял.

    Но откуда там Error для рандом ?
    Вносили снова правки ?

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

    Тут тоже весело: forum.ixbt.com/topic.cgi?id=26:43056
    пара особо забавных перлов


    C 30 млн какойто баг, нужно смотреть.
    А вот с 25 млн ключей.
    .....
    Стабильно мой код более эффективныйболее чем в 10 раз.

    Bazist
    Скорей всего у тебя нет файлика c:\\rand2.avi с которого генерятся рандом ключи.

    Естественно у меня нет файла це:\\ранд2.ави

    upd: forum.ixbt.com/...aram=1&posts=&id=26&id=40
    аффтар походу таки знаменит на ixbt :)

    Бубен много где знаменит своей упоротостью. Но о чем это говорит — не о чем.
    По упоростости посмотри на Криса Касперски, тот вообще помимо хакерства еще тот дока в разнообразной наркоте и галениках. Но куча же из вас внимательно читали его книжки и восхищались им. А да, работать с мышом — это еще тот гемор.

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

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

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

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

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

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

    Тебя послали на три буквы только что

    во припекает. Я даж не ожидал. Совсем поплыл Слава :)

    Да, мыщъх уникальный экземпляр.

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

    Блин, совсем забыл, кто там страдал под Linux. Я же несколько месяцев назад сделал полный порт DniproDB под Linux. В проекте под code::blocks все компилится и запускается.
    А если в консоле набрать db.SelfTest() то запускает 9 млн запросов в 11 бенчмарках.
    Кому этого мало, можете отдельно чудо-мапу отсюда попытаться выковырять, это не сложно

    github.com/Bazist/DniproServer.UNX

    Есть люди, которые собирают лайки на фоточки в инстаграм, а вы, походу — число форков на гитхабе. Случайно не начальнику крутость показать? :)
    ...уже все потестили. Дите ваше — пеленки сами меняйте. Зачем нам еще раз тестить ваш мусор, если вы игнорируете результаты. Т.о. образом налицо манипуляции, с неизвестной целью. Вероятно — набрать форков и тыкнуть их в нос кому-то, например начальнику, чтоб не уволил, или, у вас 5 шагов отрицания — «злость, отрицание, смирение..». Качество кода вас совершенно не волнует, исходя из ответов.
    А нас не волнуют ваши проблемы личности — или слушайте и учитесь, или хватит. Работать пора.

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

    не дай Бог, как ты писать....вот давай конкретный пример, по твоему тексту.
    Объясни мне убогому, сколько бит в типе uint?

    #define uint unsigned int

    Хорошо, это ты выучил, почти :)
    Правильный ответ: не меньше чем 16
    А кто сказал, что процессор 32 бита? В телефонах (и не только) стоят Arm, которые имеют режим thumb на 16 бит, и он предпочтительнее, т.к. работает обычно быстрее.
    Т.е. 1 телефон, 1 программа, в ней сразу могут быть смешаны 16-32-64 бита режимы процессора.
    Почему там у тя в коде везде ожидается ровно 32 ? С каких таких?
    Вот собственно «мои убогие правки» и были — я задал ровно 32 бита. Кстати правки ты так и не посмотрел. Вот тебе еще раз — мои испрвления выделены:
    github.com/...374799f13d4ed7fda99cbfc88

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

    А кто сказал, что процессор 32 бита? В телефонах (и не только) стоят Arm, которые имеют режим thumb на 16 бит, и он предпочтительнее, т.к. работает обычно быстрее. Т.е. 1 телефон, 1 программа, в ней сразу могут быть смешаны 16-32-64 бита режимы процессора.
    Почему там у тя в коде везде ожидается ровно 32 ? С каких таких?

    А потому что я не решаю сферическую задачу в вакууме.
    32 бита и работа под 32х битные регистры, для конкретно этой реализации краеугольный камень. Везде используются метрики экспансии блоков, выравнивания, офсетов, партицирование ключей, хеширования в четыре слота, специально под 32х битные процессы. Если у тебя Integer вдруг будет не 32 бита, а 16 бита или 64 бита, то это уже совершенно другой адаптированый алгоритм.
    Да и я думаю, что если у тебя int окажется 16 бит, то на гитхабе вылетит с ошибками примерно 90% программ. Даже обычный унылый классически for(int i=0; i < big_num; i++) просто зависнет намертво.

    Вот тебе еще раз — мои испрвления выделены:
    github.com/...374799f13d4ed7fda99cbfc88
    Вверху есть проект. Там есть все теже файлы HArrayVarRAM_чтототам, возьми сделай элементарный diff или скопируй их себе и будет тебе счастье.

    Зачем оно мне? Я уже сделал, скопировал, запустил. Если ты считаешь я накосячил — проверь мои исправления. Если я все сделал ОК, тогда std::map wins. Кстати не я 1 делал, там другой чел тоже отдельно от меня портировал, и даже сделал exe-32 бита, но компилятором GCC. Там твой алгоритм еще сильнее всосал, в 3 раза медленнее вышел, чем под линукс.

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

    блин) ты ваще даже не смотриш...гдеж там сотня, если исправил 5 строчек. Ну и сами тестовые функции, которые ты говриш не важны.
    Вот нахер с таким тобой крутым беседовать. Тебе показываешь результат, а ты уши зажал -"бла-бла-бла, я в домике".

    Тем более. 5 строчек исправить чтобы портировать правильно алгоритм под Линукс этого мало. Остальные 95 остались неисправленными. Копипаст тебя спасет.

    Ok, удалил fork тоже. Как сделаешь сборку командой cmake ./ свистнешь. Гляну.

    Про АРМ и Thumb бред. Полный.

    Жаль, тролей внизу развелось как куропаток на птицефабрике.
    Потому покидаю секции внизу, и представляю результаты последних тестов.
    Чтобы их проверить, достаточно скачать мой проект под Visual Studio и запустить тесты.
    Качаем, запускаем и проникаемся всей красотой игры действительно эффективных реализаций.

    github.com/...ter/HArray_Benchmarks.txt

    Скачав, відкрив, скомпіляти не можу — каже не та версія студії.

    У меня стоит Visual Studio Express 2015 for Desktop
    Качал отсюда, она бесплатная.
    www.visualstudio.com/downloads

    И живёт 30 дней. Я лучше Code::Blocks применю, оно кроссплатформенное и без извращений.

    Вот я не знаю насчет С++, но у нас в Джаве не принятно шарить проекты какой-то IDE — для этого у нас есть Maven/Gradle, которые прекрасно импортятся во все основые IDE и вообще можно даже без неё запустить. У вас такого нет?

    Для крестов общепринятый подход — нечто, что генерирует makefile. CMakeList.txt, напирмер. Совсем олдскул — автолулзы, но это принято только в GNU-мире.

    Ничего не понял. У кого там не получилось скомпилировать или смигрировать под Линукс ?
    В 2013 году собирал версию в code::blocks за несколько часов
    Солюшин
    github.com/.../tree/master/VymaDB_Linux

    Теже бенчмарки под Linux, за тотже год
    wiki.pikosec.com/...ayFix_VS_GLib::GHashTable

    По основному солюшину, сегодня зачекиню код.
    Там будет 45 разнообразных тестов.
    (Инты, Строки, Бинари ключи. Рандом, Последовательные, с Периодом и тд).
    Крутил вертел уже как хотел, быстрее работает во всех тестах от 3х до 20раз чем std::map

    PS: GCC кстате более качественно компилит мой код, чем Майкрософтовский

    Эксперимент можно заканчивать. На 20мил у меня 8Гб не хватило ...все зависло наглухо, пришлось REISUB юзать ...

    === HArrayVarRAM testing ===
    Start benchmarks ....
    Insert/Search 1000 random keys (256 bytes each) ...
    HArrayVarRAM => Insert: 13756 msec, Search: 100 msec.
    std::map => Insert: 44 msec, Error
    ...еще много Error
    Search: 1110 msec.

    Небольшие фиксы, до компилабельного cmake состояния тут:
    github.com/alexzk1/HArray

    А так — код ужасен, как по мне, и куча фактических ошибок. Утечек памяти и прочей фигни, во всяком случае в Main. Но судя по варнингам, не все хорошо и в либе самой. Старался не трогать. Так же...подозреваю будут проблемы, например, на arm, где 16/32/64 бита могут быть в 1 программе. Еще бы я погонял кросс-проверку, а правильно ли оно вообще данные хранит, т.к. там полно срезания битовости, вроде в член класса 8 бит суется 32 бита... но лень.
    --------------------
    Прогнал еще для ляма:

    === HArrayVarRAM testing ===
    Start benchmarks ....
    Insert/Search 1000000 random keys (256 bytes each) ...
    HArrayVarRAM => Insert: 399899 msec, Search: 309485 msec.
    std::map => Insert: 35253 msec, Error
    ...еще много Error на пару килобайт
    Search: 1141631 msec.
    --------
    Без оптимизации
    === HArrayVarRAM testing ===
    Start benchmarks ....
    Insert/Search 1000 random keys (256 bytes each) ...
    HArrayVarRAM => Insert: 45848 msec, Search: 239 msec.
    std::map => Insert: 207 msec, Error

    Для gcc отримую пачку помилок типу:
    error crosses initialization of ‘uint& keyValue’ .... ......
    Часу і бажання в тому розбиратися немає.

    P.S. Відповідь є тут: stackoverflow.com/...-switch-statement/8550253

    Автору варто почитати

    -fpermissive добавить
    там goto прыгает через объявления переменных, там ваще ХЗ че в итоге из этого выйдет. Скорее всего это UB. Но в нескольких экранах «так должно» лень копать.
    А вообще — склонируйте мой — там компильнулось.

    Та ж історія і куча error

    === HArrayVarRAM testing ===
    Start benchmarks ....
    Insert/Search 1000 random keys (256 bytes each) ...
    HArrayVarRAM => Insert: 62078 msec, Search: 108 msec.
    std::map => Insert: 65 msec, Search: 110 msec.

    P.S. Помилки пофіксив, автор взагалі не знає як працює strcmp

    правильно так:

    bool operator<(const Str& a, const Str& b)
    {
      return strcmp(a.Val, b.Val) < 0; // а не  strcmp(a.Val, b.Val) == 1
    }
    

    так что так, да. std::map wins!
    Мне не понятно, как в массив размера 1 он совал 20лямов? В оригинале так. М.б. там лютый мусор был и казалось по логу все быстро и верно? ))) Ну еще вот те goto смущают...

    ...о..а я и прощелкал сравнение :) глянул, что оно мне не нравится, но плюнул ..

    Спеціально провів кроскомпіляцію під x32 (додав опцію -m32), результати cхожі:

    === HArrayVarRAM testing ===
    Start benchmarks ....
    Insert/Search 1000 random keys (256 bytes each) ...
    HArrayVarRAM => Insert: 48796 msec, Search: 101 msec.
    std::map => Insert: 325 msec, Search: 198 msec.
    

    Для чистоты эксперимента, этот патченый код бы VC компильнуть и сравнить, что автор писал. Возможно, UB давали крутые оценки,а возможно std::map от MS фигня... но у меня винды нет :) А ВЦ-6 есть...образ))

    Угу, добавил фикс оператора, пропали ошибки (-О3)

    === HArrayVarRAM testing ===
    Start benchmarks ....
    Insert/Search 1000 random keys (256 bytes each) ...
    HArrayVarRAM => Insert: 13034 msec, Search: 69 msec.
    std::map => Insert: 297 msec, Search: 168 msec.

    === HArrayVarRAM testing ===
    Start benchmarks ....
    Insert/Search 1000 random keys (256 bytes each) ...
    HArrayVarRAM => Insert: 12187 msec, Search: 84 msec.
    std::map => Insert: 309 msec, Search: 163 msec.

    === HArrayVarRAM testing ===
    Start benchmarks ....
    Insert/Search 1000 random keys (256 bytes each) ...
    HArrayVarRAM => Insert: 15476 msec, Search: 206 msec.
    std::map => Insert: 281 msec, Search: 173 msec.

    И меня смущают такие резкие разбросы его алгоритма, до 30%, чета там не то.

    Не поможет. Аффтару надо начать с Макконнела, затем перейти к Меерсу и Саттеру. ПОтом возможно ему станет стыдно за этот пост. :)

    Не поверете...сам читал 2 книги всего по ++ - «Справочник по С и С++» 1997г и еще 1, забыл название, об общем проектировании программ, с примерами на С++ и критикой MFC. Вот недавно купил «Эффективное С14++», помоему оно мне повредило :) Напихал std::move, куда не стоило. В итоге откатывать пришлось. А так — практика и man.

    Имха тут все индивидуаллно. Ну а в случае топикстартера похоже что практики недостаточно.

    Говнокод и проблемы идут рядом чуть чаще чем всегда. Респект что не поленился заранать это говно, мне было откровенно лень.

    Да ну, весело же. О С++ уже года три пофлудить не с кем :)) - все яваскрипты какие-то...хых.

    К сожалению в данный момент у меня нет Линукса под рукой.
    Попробуйте взять солюшин тот который я когдато мигрировал и отлаживал в code::blocks.

    а все потому что про CI ты ваще ни в дуб ногой: github.com/....WIN/tree/master/Releases

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

    Судя по результатам тестов — ломают очень серьезно.
    А чтобы найти что. Нужно потратить N часов с дебагером и под Линуксом, которого у меня нет.
    Мне это также тяжело сделать, как уам запустить мой проект под Visual Studio
    и убедится во всем всеголишь по нажатию клавиши F5.

    Давайте начнем вот с этого:
    Str keys[1];
    +std::shared_ptr<str> keys;

    смысл в том, что у вас резервируется память на 1 элемент, а загружаем туда 20 000 000, не уверен, почему это вообще работало. Но пока представляется ключевым моментом.
    Так же стоит оператор < исправить на

    bool operator<(const Str& a, const Str& b)
    {
    return strcmp(a.Val, b.Val) < 0; // а не strcmp(a.Val, b.Val) == 1
    }

    Сделайте на своей VC и перетестируйте.

    Внезапно, но это не принципиально. Иначе было бы на консоле Error. Коллекция будет в ASC или DESC виде.
    Результаты работы с вашей функцией


    === HArrayVarRAM VS std::map<strkey,int> testing ===
    Insert/Search 1000000 SIMILAR keys (64 bytes each) ...
    HArrayVarRAM => Insert: 463 msec, Search: 403 msec.
    std::map => Insert: 2425 msec, Search: 2328 msec.

    Insert/Search 2000000 SIMILAR keys (64 bytes each) ...
    HArrayVarRAM => Insert: 940 msec, Search: 1076 msec.
    std::map => Insert: 5232 msec, Search: 5012 msec.

    Insert/Search 3000000 SIMILAR keys (64 bytes each) ...
    HArrayVarRAM => Insert: 1508 msec, Search: 1718 msec.
    std::map => Insert: 8607 msec, Search: 7981 msec.

    Insert/Search 1000000 RANDOM keys (64 bytes each) ...
    HArrayVarRAM => Insert: 421 msec, Search: 382 msec.
    std::map => Insert: 1441 msec, Search: 1359 msec.

    Insert/Search 2000000 RANDOM keys (64 bytes each) ...
    HArrayVarRAM => Insert: 1190 msec, Search: 996 msec.
    std::map => Insert: 3490 msec, Search: 3082 msec.

    Insert/Search 3000000 RANDOM keys (64 bytes each) ...
    HArrayVarRAM => Insert: 1556 msec, Search: 1529 msec.
    std::map => Insert: 5225 msec, Search: 5033 msec.

    Press any key to continue . . .

    Остальные тесты я уже тоже залил, можете ориентироваться на эти 45 тестов
    github.com/...ob/master/HArray/Main.cpp

    А вы размер массива поправили под тесты-то? Выход за границы памяти это пустяк?

    И да, с вашим оператором сравнения не верным так и было — 10кб слова Error

    Кстати, вы знаете, что такое «Undefined Behaviour» ? Это ваше «сломали» и есть. Когда вы нарушаете принципы стандарта языка, то что-то в итоге будет, но никто не гарантирует, что оно повторится одинакова на других машинах и(или) компиляторах. Поэтому вы и ковыряете дебугером сутками, что мы сходу нашли, как минимум 3 UB. Один из них в методе insert — goto. Но его трогать не решились, чтобы не ломать эксперимент.

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

    Послушайте. У вас в методе инсерт есть куча goto. Оно пропускает создание и инициализацию локальных переменных, что в итоге будет с вашим алгоритмом зависит от положения звезд на небе и фазы Юпитера. Кстати, это косвенно подверждают мои тесты — разброс вашей функции до 30% на моем компе, и до 3х раз на разных компах, причем std::map с этими же данными дает 3-5% разброс времени во всех случаях.

    Нет. Там все продумано. Еще раз.
    Возьмите те сорцы под Линукс которые я вам дал.
    Вы не знаете все ньюансы компиляции под Линукс и тем более самого алгоритма. Допустили ряд ошибок и пытаетесь чтото оспаривать после своих модификаций.

    github.com/.../tree/master/VymaDB_Linux

    т.е. вот это
    const uint MAX_SHORT = 65536;

    в хидере вы считаете нормальным?

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

    У меня уже нет сил с вами спорить.
    Просто возьмите то что я дал и проверьте.

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

    Какой код, о чем ты говоришь ?
    Он написан именно так, чтобы работать быстро.
    Поверь мне, у меня 14 лет активного опыта работы на самых разных языках, если нужно написать код красивый ,то я пишу так как надо. Но это не тот случай !
    Если вы не разобрались за 1 день так не расстраивайтесь.
    Я его писал 5 лет и часто думал что вообще это невозможно написать. Но написал. И есть результат.

    ....он ВОЗМОЖНО быстр и ВОЗМОЖНО работает только на каком-то ОГРАНИЧЕНОМ множестве машин, скорее всего только на твоей 1. Потому что он не верен с точки зрения языка и компилятора, а ты его подогнал под конкретные условия. Но вобщем и целом он мусор, а ты называешь это «сломали, бывает».

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

    А давай ты попробуешь, скачаешь и померяешь а потом напишешь свое мнение. Ты умный парень, мне не хотелось бы чтобы ты ишел на поводу какогото персонажа, которые пытался за 5 минут мигрировать под Линукс, наломал кучу дров и отказывается брать правильный исходник.
    Ок? Репо склонировали больше 10 раз и не только он мерял, кстате. И если была бы липа, мне бы уже написали сто раз, как с тем контрпримером. А так — да, смешно.

    ну...скачал
    github.com/Bazist/DniproExamples
    взял папочку линукс, ее файлами перезаписал мой тест (что уже сеня делал):

    y/HArrayFix_del.cpp: In member function ‘virtual bool HArrayFix::del(unsigned int*)’:
    /home/alex/Work/OpenSource/HArray/HArray/HArrayFix_del.cpp:24:6: error: ‘ContentCell’ was not declared in this scope
    ContentCell& contentCell = pContentPage->pContent[contentIndex];

    ^^^^^^^^^ то починил, кеш...
    сбросил кеш, терь новое

    /HArrayVarRAM.h:64:2: error: ‘VarPage’ does not name a type
    VarPage** pVarPages;
    ^~~~~~~

    Только эта ошибка ? Я уже не помню возможно ключи в компиляцию нужно еще прописать

    типы не объявлены, их просто нигде нет
    HArrayFixPair
    VarPair

    Кароче я хз шо ето ты за код для линукс дал, но тут не хватает типов. А я просто твои тесты хотел погонять с твоими правильными фиксами)
    Удалил нахрен это барахло все с компа...

    Ладно чувак не парься. У меня вечер забит сегодня, но если будет время я специально под линь скомпилирую и узреют Никс красноглазики истину.

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

    Лолшто. Там нет багов. В этот алгоритм вкачивали 160 млн ключей. Он индексировал терабайты в бубенкоме. Его прогинали в зверских тестах Днипры. Да там уже третий год чище чем в банке с спиртом.

    та да, код настолько идеален, что даже если макросом заменить тру на фолс, то все как работало так и будет, такое только за 14 лет на разных языках можно написать, если не разобрался за всю жизнь — не надо расстраиваться, этот код написан чтобы работать быстро как ядро, а не чтобы быть понятным хоть кому-нибудь

    Кстати, если мерять у кого длиннее...первую свою программу я написал 30 лет назад для микрокалькулятора МК-61 ))

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

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

    у меня макось :)
    и опять таки — что мерять то? рандомные результаты?

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

    на его компе
    Тоесть у меня какойто особый компилятор на машине, и особый комп ? Спасибо. Улыбнуло.

    Вы не поверите....именно так. Запустите на другой машине, с другой видеокартой и размером оперативы и вы удивитесь.

    с другой видеокартой и размером оперативы и вы удивитесь.

    Ржач. Уже и видеокарта имеет значение !
    Алгоритм писали примерно в течении 6 лет и запускался он на нескольких разных модификациях. Ну не меньше 10 так точно. Только 4 ноутбука у меня домашних поменялось. Плюс рабочие машинки и тд.

    Значение имеет разметка памяти в системе — самый простой вариант ее изменить я уже описал. Можно покруче — скомпилируйте под распери-пи, там есть винда 10, но процессор арм, раз вам сестра ноут с линуксом не дает.

    Да да да.
    Существует конфигурация с особой видеокартой которая оживит std::map в десять раз. Шутка дня. До пятницы бы хотябы дотянул.

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

    Осталось тебе найти и показать конфигурацию того особого компа. Дабы мы смогли наконец узреть контрпример

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

    абрвалг!
    Скомпилируй под анроид. Android-ndk.

    И еще, std::map у микрософт и в gcc это совершенно не зависимые и разные алгоритмы. Никто не говорит, что у микрософт самый быстрый. Более того, столь значительные расхождения времени вашего алгоритма у вас и у нас (в разы!) говорит о том, что он просто не верен с точки зрения языка. Вы его «заточили» под конкретный компилятор, игнорируя все ошибки. На 16 бит или 64 бит даже этим же компилятором, скорее всего, снова не заработает.

    std::map в любой своей модификации тут выступает скорей в роли статиста. На самом деле тут борьба мат моделей и оспаривается даже скорость работы не только RB и прочьих двоичных деревьев, но даже Хештаблиц (включая GLib).

    Все. Устал. Не прошибаемая глупость.
    Боритесь и превзмогайте. Было весело.

    Раз руки из одного места, одолжите комп у младшей сестренки с ВыНдОй и нажмите F5 после того как установите студию.
    Я думаю это для вас будет самый простой вариант.

    как можно ж править, это ж идеальный код :)))

    Лекция про Tries, что оно такое и зачем:

    www.youtube.com/watch?v=TJ8SkcUSdbU

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

    См. тж.: news.ycombinator.com/item?id=2108392 и ссылки в комментариях.

    news.ycombinator.com/item?id=2108392

    Хорошая ссылка. И по ссылке вроде даже более-менее взрослый код.
    Но автор утверждает что удалось обойти всего на 50%-100% std::map, этого мало конечно.
    Ну и тесты хотелось бы увидеть.

    ептыть...
    Str keys[1];

    .............
    gen_random(keys[i].Val, KEY_LEN — 1);

    и че, реально ето на винде работает?

    На винде в студии и не такое работает. Меня последний раз студия потрясла, когда успешно заюзала несуществующую переменную. Чего-то сама накомпиляла и даже как-то работало.

    В чём отличие от наивной реализации trie? Хочется на досуге поковырять, но код весьма слабо читаем.

    Это читать не нужно. Там определенно есть UB, т.о. вообще весь код/алгоритм/тест под сомнением. Пусть сначала UB чинит, а потом тесты повторить и обсуждать.

    goto FILL_KEY;

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

    Блин, я даже сразу не скажу как это исправить, чтоб не обвинили меня в поломке мега алгоритма. И так уже попереименовал, когда имя типа = имени переменной :)

    Интересно бы собрать это все с тестом std::map на GCC под arm-v6, arm-v7, arm-64, win-lin 32/64 и посмотреть, а то какие-то сомнения меня гложут, уж не под визуалку ли все подточено...да еще 32 бита...
    Кстати, std::map у микрософта свой, а у GCC свой. В стандарте только интерфейс и юзкейсы поведения описаны. Не факт, что будет такой же тормоз на 14с.
    ...и О3 попробовать, а то там присваивания в 8 бит значений 32 бит ...мож так и нада, а мож оптимазер поломает в этом месте.

    #define uint unsigned int

    нууу... arm-thumb режим (по умолчанию обычно, для мелких вещей) — будет 16 бит тут, точно так хотели? пока ставлю using uint = uint32_t;

    #define uint unsigned int
    кстати да, лучше через typedef, на случай если придётся подключить ещё какие-то хедеры определяющие uint.

    Собственно на С++ использование #define это моветон. Почти всегда, есть аналог, который провериться компилером без side-effects.

    нууу... arm-thumb режим (по умолчанию обычно, для мелких вещей) — будет 16 бит тут, точно так хотели?

    Что-то я очень сильно в этом (16 бит int для thumb) сомневаюсь. Пруфы есть?
    А то
    1) между thumb и native переключение влёгкую, в отличие от 16/32/64 на x86
    2) находятся обратные утверждения (например, тут один спутал точно так же с разрядностью команд, и его поправляли)

    Thumb 16 разрядные инструкции, thmub2 mix 16 и 32 разрядных. Ширина данных всегда одинаковая, регистры всегда 32 битные

    Спасибо. То есть я правильно догадался, что Захарова проглючило.

    Ну перефирийный код может быть улучшен.
    Сам алгоритм (в частности функция insert, getValueByKey и тд) не рефакторится не переписываться не будет. Они так написаны, потому что так надо.

    “Так надо” должны говорить тесты на корректность и на скорость. Там наверняка много можно улучшить.

    For the optimisation effort to yield measurable improvements on representative tasks, one must know whether and where effort is needed. A well-informed optimisation depends on sufficiently realistic, detailed and accurate measurements, developers are notoriously bad at guessing where optimisation is necessary.
    twiki.cern.ch/.../WorkBookOptimizeYourCode

    В getValueByKey просится вот такая структура: paste.ee/p/kVHeq

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

    И на статью тоже будет всем наплевать :)

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

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

    На одного перельмана — миллион бубнов. Статистика вещь упрямая. А упоротость автора ни разу не повышает шансов проявить себя.

    Перельман поупоротей Бубна во много раз. Може именно недостаточчная упоротость Бубна не позволит ему что-то сделать.

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

    Вотето у «архитектора» бомбит. Зачот.

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

    На одного перельмана — миллион бубнов и сто миллионов прокофьевых.

    Фиксед, во имя правды.

    ...во имя чесания своего немеряно раздутого чсв :)

    А кто такие сыроеды?
    Гребцы явно гребут на галерах.

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

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

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

    А ключ можно до 512 Бит увеличить? (℅

    Ключ может быть любой. Хоть килобайт.

    Я вообще не шарю в этих ваших материях, тред не читал и все такое. Если в lmdb запилить — быстрее будет? У меня там хештабла на 32 гб, мне бы может пригодилось

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

    У меня на данный момент на тестовой базе ~208M ключей, но ожидается на пару порядков^2 больше. Ключ — пара SHA3 в байтовом представлении (полагаю оверхед SHA3 будет значительно выше чем поиск по хештабле). Таблица — метрика для пар прообразов произвольных размеров.

    Я практически полностью уверен что прирост производительности был бы существенным.
    Но дело в том что сейчас у меня есть реализация только для 32х битных систем. Моему процессу ОСь не отдаст более 2-3 гб памяти. А этого не хватит для 208М ключей :(

    Успіхів! А коммерціалізація не плануєця?

    Я как прочел заголовок подумал сразу об мотоциклах Индиан, что топикстартер хотел уже купить мотика и самого быстрого. Зашел, и тут другое)))

    Да, фильм зачотный. Хорошо отображает многолетнее выпиливание того самого :)
    ru.wikipedia.org/...ki/Самый_быстрый_"Индиан

    Блин, ребята, взял себе литрушку пива :)
    Короче хронология событий. Поспал я наверно сегодня часа четыре, просыпаюсь, какоето чудо заморское из мордорского форума постит мне контрпример, утверждает что его пример работает в 3 раза быстрее чем у меня. Еду на работу, все мысли чтозанах. Приезжаю действительно, контрпример, ключ это строка на 256 рандом букв и цифр, мой алгоритм там где насовывал в 10 раз сливает теперь в 3 раза. Ну думаю всё, п-ц, 5 лет коту под хвост. Судьба Днипры висит на волоске. Еслиб хотябы какаято хештабла так отработала, ну там не сильно жалко. Ибо у нее нет и половины функционала что у меня (сканы по диапазону, по маскам ключей и тд), а тут — какието Red-Black деревья в std::map. Начинаю прозревать. Весь день меня тягают по совещаниям, голова не соображает. В обед два кофе «эспрессо», тут начинаю немножко оживать, иногда дорываюсь до своего чудо кода в перерывах между тасками и снимать метрики дерева со своего алгоритма, вроде более-менее нормально, явных перекосов не обнаружено. Тут начинаются первые звоночки, смотрю по расходу памяти. std::map занимает 250 мегабайт, а у меня 760 мегабайт. WTF?!. Декларировал же что еще по памяти выигрываю, а тут такой провал. И тут совершенно случайно под вечер понимаю, что вот это вот самое:

    std::map<char*, uint> mymap;

    На самом деле только декларирует что работает со строкой. А на самом то деле работает с 4 байтами указателя на эту строку ! Посыпаю голову пеплом в недостаочном знании приблуд STL, Трипл фейспалм. Когда моя структура чесно копирует 256 символов как алюч, это чудо копирует всего 4 байта !

    Переписываю, перемеряю. Все становится на свои места. Липовый тест летит в муссорник, контр примеры снимаются. Допиваю пиво. :-D

    Боже упаси мне превратиться во что-то подобное.)

    Зря, живая наука — это всегда интересно.

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

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

    Успокойся, поиграй в дотку, в вовчик, погуляй с девочками, поспи часов 11-12. Прибухни хорошенечко, наконец. Не нужно это тебе.

    Да я не об этом... Я о бухать и без девочек.

    эт точно, особенно прикольно про 4 байта, которые никто не гарантирует на платформах отличных от x86 ;)