Comments 45
Обычно двоичное дерево полезно тем, что в нем вставка/удаление за log(n). Но если дерево неизменяемое, в чем преимущество перед массивом?
И в Search сравнения?
TypeListSort тоже интересно увидеть
Но ведь в дереве поиска происходит ровно столько же операций сравнения ключей, неважно что там за ключи. Более того, сравнения идут с теми же самым элементами! Бинарный поиск в массиве — это фактически есть поиск в неявно хранимом бинарном дереве.
Бинарный поиск будет в константном массиве по всем параметрам лучше: и места меньше занимать будет и работать быстрее.
Также к своему стыду признаюсь, что так и не понял, можно ли статический массив разместить во Flash, а доступ к нему получать в runtime? Или придется все равно городить список типов?
template<int... Numbers>
Можно. Достаточно расположить его в секции которая попадет в ROM. Нужно смотреть ld script, но обычно они содержат секции вроде .ro_data
можно ли статический массив разместить во Flash, а доступ к нему получать в runtime?
Или я не понял вопрос, или у вас компилятор (скрипт линкера) сломался. Потому что на мелких армах банальный `const int arr[42] = {1,2,3}` с настройками компилятора по умолчанию ляжет во флешку.
Вот, например, в ATMega это не так - там гарвардская архитектура, и "память по умолчанию" - это ОЗУ. Чтобы переменная легла в ПЗУ, нужны магические заклинания.
Также по-другому могут работать "большие" армы - всякие cortex-a. Там, слава фон-Нейману, адресное пространство единое, но программа зачастую копируется целиком из ПЗУ в ОЗУ при старте и уже оттуда исполняется.
Скорее всего, у меня понимание такого низкого уровня уже сломалось. Например, в ПК образ программы лежит на диске и в момент загрузки размещается в RAM. В контроллерах, в том числе ARM, насколько понимаю, это не так. Есть RAM и Flash, RAM для данных, Flash для кода (я так думал), или доступ к flash-памяти из программы прозрачен и не отличается от доступа к участку RAM?
у меня понимание такого низкого уровня уже сломалось.
Удивительно. Человек, который пишет приличный (имхо) шаблонный код и умеет пользоваться IDA - и такая странная дырка в знаниях. Наверное, это от их избытка - было б поменьше, просто б не задумывались, оно б "само" работало :-)
доступ к flash-памяти из программы прозрачен и не отличается от доступа к участку RAM?
В случае кортексов - да, абсолютно прозрачен и никак не отличается от доступа к ОЗУ (ну, если не писать туда ничего и не заниматься тщательными измерениями "сколько тактов занимает чтение"). На уровне ассемблера это одни и те же инструкции, только разные адреса. На уровне Си/Си++ - во всех заготовках стартового кода (стартап, скрипт линкера) сделано так, чтобы RW переменные ложились в ОЗУ, RO - только во флеш.
Если чуть подробнее, то для переменных Си/С++ есть возможны три варианта - неинициализированные не-const переменные кладутся в секцию BSS, инициализированные не-const переменные кладутся в секцию DATA, const перменные (они, очевидно, все инициализированы) кладутся в секцию RODATA.
В промежутке между стартом контроллера и началом main() выполняется маленький кусочек кода (в случае gcc он обычно весь в одном исходном файле), который обнуляет BSS (ассемблерной вставкой или вызовом memset) и копирует DATA из флеша в ОЗУ (также ассемблерной вставкой или обычным memcpy). В случае RODATA никаких копирований нет, код сразу работает с данными во флеш.
Надо все-таки будет как-то более подробно изучить вопрос преобразования кода в исполняемые модули, чтобы лучше понимать работу компилятора и компоновщика.
Обработка строк предполагает дополнительные накладные расходы. Если множество ключей известно в момент компиляции и неизменно, тогда можно использовать таблицу дескрипторов с целочисленными ключами, например типа enum. enum значения ключей можно использовать в качестве индексов элементов массива. Тогда и хеш считать не придется.
Если вынуждены работать со строками, то да, придется "на лету". Я вижу два варианта:
Можно держать словарь, упорядоченный лексикографически (как альтернатива trie) и по нему запускать бин. поиск. Во втором массиве хранить по соответствующим индексам значения.
Аккуратная хеш-функция + хеш-таблица. Например, если строки короткие то можно считать в позиционной системе s[i] * 26^i. Вычисление хеша - отдельная большая тема. Скорее всего, кто-нибудь уже решил оптимальным образом задачу для коротких строк.
уже решил оптимальным образом задачу для коротких строк.
Можете посмотреть
What is the best 32bit hash function for short strings (tag names)?
http://www.orthogonal.com.au/computers/hashstrings/
Пишут, что crc32 подходит хорошо, предлагаются другие варианты. Я бы начал с лексикографически упорядоченного словаря + бин.поиск + массив значений. Если решение не подходит по скорости или памяти, то хеш.функция (напр. crc32) + таблица. Что-нибудь из этого может стать лучшей альтернативой trie.
Большая проблема шаблонной магии - раздутый код, который может не помещаться в кеш инструкций, замедляя выполнение программы. В вашем случае с бинарным деревом я не представляю, как процессор сможет оптимизировать гору ветвлений.
И trie хорошо, когда есть строки с общими префиксами, что не всегда так.
Это не совсем так. Если мы говорим о STM32F1xx (не F7 и более быстрых процессорах) и о внутренней SRAM (а не о внешней SDRAM, про которую статья по вашей ссылке), там нет никаких задержек, память работает на частоте ядра.
Но, с другой стороны, скорость работы внутренней флеш - максимум 24 МГц, при больших скоростях ядра надо конфигурировать контроллер, чтобы он вставлял циклы ожидания при обращении к ней. Чтобы эта конструкция не ОЧЕНЬ тормозила, есть микро-кэш: два 64-битных буфера. Каждое чтение флеш заполняет один из них (все 64 бита за раз). Для линейного кода, который не читает никаких констант, оно работает нормально. Но это сферический код в вакууме, и на хаотичные прыжки по коду эта конструкция отреагирует плохо.
Раздутый код? Шаблоны не добавляют код сами по себе! Особенно специализация, тут даже меньше должно быть.
На сколько я помню, префетчеров в армах (мк) нет) Поэтому никакой оптимизации ветвлений) Только кэш инструкций и данных.
Ориентироваться на использование кеша - плохая идея. Практически полное отсутствие детерминированости.
Тогда нужен "решатель" ключ -> индекс массива, по типу unordered_map.
По сути, у вас получился switch-case формируемый во время компиляции. Но есть плюс, по сравнению с switch, можно масштабировать вариативным шаблоном.
А можно добавить поддержку динамического добавления узлов? Ерунда, но иногда бывает нужно.
Не думали использовать хэшмап в компайл-тайме? Например, https://github.com/mapbox/eternal
Поскольку добавлять или удалять узлы не нужно, снимаются вопросы с управлением памятью, а look-up константный.
Вот насчет коллизий не знаю, но, наверное можно что-то придумать (static_assert выдавать, например :)
Для таких задач в compile-time нужно использовать массивы. Хотя, для общего развития, чтобы научиться работать с constexpr-выражениями, и такое сойдёт.
В смысле? У меня примерно вот так это выглядело - сортируешь статический массив в compile-time, потом, в runtime, просто ищешь по нему при помощи std::lower_bound/upper_boundstatic constexpr auto _symbols2 = MakeSortedArray
({
"USTECHIndex",
"AAPL_us",
"UK100Index",
"BARC_uk",
"DE30Index",
"BNP_fr",
"JAPANIndex",
});
Есть std::binary_search :) Но по моему опыту он очень хорошо стек кушает
Каким образом? Там даже рекурсии нет
Видимо, зависит от реализации std, я сходу не помню, но в моей почему-то было очень много вложенных вызовов каких-то вспомогательных
Нет, не зависит. Это старый и простой алгоритм https://en.cppreference.com/w/cpp/algorithm/lower_bound
Вообще говоря, конечно, может зависеть, ведь стандарт не оговаривает как именно реализуются стандартные алгоритмы..
Но видимо у меня какие-то фантомные воспоминания (или я с чем-то другим путаю), сейчас посмотрел стектрейс на том компиляторе, получил:
std::__lower_bound⟨int*, int, __rw::__rw_lt⟨int⟩, int⟩(T1, T1, const T2&, T3, T4*, std::random_access_iterator_tag) ⇒ __rw::__rw_lt⟨int⟩::operator ()(const int&, const int&) const
И 96 байт стека; по воспоминаниям было как-то сильно больше, но тот проект давно канул в Лету, так что признаю свою неправоту :)
Можно использовать другой способ, который займет столько же памяти.
Для удобства можно считать, что нас вершин 1024 штуки (степень двойки специально), нумерация от 0 до 1023 включительно.
Можно завести `std::array<int, 1024> keys` (ключи отсортированы) и `std::array <int, 1024> values`.
Поиск по ключу займет не более чем 10 сравнений, по одному биту каждый раз. Индексы ключей у нас от `0000000000` до `1111111111`, поэтому надо смотреть ключ посередине - по индексу `1000000000`. Если он больше, то единицу отнимаем. И потом смотрим следующий бит.
int some_key = XXX;
int index = 0;
for (int i = BYTES - 1; i >= 0; --i) {
if (some_key >= keys[index + (1 << i)]) {
index += (1 << i);
}
}
return value[index];std::array-то почему нет?
Кстати, есть еще такая штука - https://www.etlcpp.com
Stm32f103c8t6 предлагает 20 Кб RAM и 64 Кб Flash-памяти.
Спалю годноту, у Stm32f103c8t6 128 кб флеш памяти. У этого мк такой же кристалл, как и Stm32f103c(B)t6, просто вторая половина залочена. Так дешевле выпускать. Простыми манипуляциями компилятора и аплоадера можно легко открыть себе вторую половину.
Статическое константное дерево на шаблонах C++