Физическая память
21 min
Retrospective
Разобраться как были устроены исторические типы памяти интересно просто чтобы в очередной раз восхититься, каким изощренным и изворотливым может быть человеческий разум, особенно при нехватке ресурсов.
Насколько многомерным может быть многомерный точный индекс?
Medium
9 min
Вот, например, Milvius(DiskANN) рассчитан на вектора размерности до 32 768, но это приближенный поиск. Но как насчёт поиска точного?
В данной статье рассматривается работоспособность 1024 мерного индекса, хранилищем которого служит обычное B‑дерево (насколько вообще может быть обычным такое дерево). Используемый диск — вполне себе «железный» старый добрый WD Purple, оперативная память сознательно ограничена 8 Гб. Можно ли что‑то из этого выжать на рядовом десктопе за приемлемое время?
Бродим по лабиринту
Medium
9 min
Оптимизация поиска выхода из лабиринта представляется относительно простой задачей. Но она подразумевает накопление данных, обучение, если угодно.
Как только возникает потребность накапливать данные, стоит исходить из того, что этих данных станет много и придётся прибегнуть к технологиям из области баз данных.
Здесь представлена робкая попытка разобраться в теме.
А не замахнуться ли нам на Вильяма нашего Аккермана?
Medium
14 min
Tutorial
Продолжение статьи о разработке стекового процессора с оригинальной архитектурой.
Здесь мы занимаемся инфраструктурой - ассемблером, компилятором С и эмулятором процессора.
Про функцию Аккермана тоже будет, она используется в качестве теста.
Уж извините за кликбейтный заголовок.
By the pricking of my thumbs, something wicked this way comes
Medium
15 min
Tutorial
Эту фразу из «Макбета» Шекспира автор осмелится перевести как «благодаря зуду на кончиках моих пальцев может появиться что‑то очень странное».
Изначально хотелось всего‑лишь ознакомиться с Verilog, но, «опасное это дело, выходить за порог: стоит ступить на дорогу и, если дашь волю ногам, неизвестно куда тебя занесет».
Занесло в сторону процессора с собственной архитектурой. Автор давно неровно дышит в сторону стековых процессоров, здесь так же присутствуют раздельные конвейеры для потоков управления/исполнения и расширяемая упаковка кода.
Надеюсь, это окажется кому‑то полезным, так же как когда‑то автору был полезен игрушечный hoc из книги Кернигана и Пайка «Unix — программное окружение».
Происхождение и эволюция аллокатора памяти в С
11 min
Tutorial
Развитие технических конструкций или же программных систем зачастую напоминает эволюцию живых организмов. С тем отличием, что происходит быстрее и гораздо лучше задокументировано. Можно наблюдать постепенное усложнение, появление новых механизмов/алгоритмов по мере появления новых технических возможностей, комбинирование разных механизмов, исчезновение тупиковых ветвей ... В конце концов это приводит к балансу на пределе физических возможностей и, глядя на результат, уже непонятно, как вообще такое могло появиться на свет, сколько пядей во лбу требуется для общего понимания конструкции.
Аллокатор памяти в С - именно тот случай, когда при попытке ознакомиться с его современным устройством возникает стойкое желание остановиться, мысленно поблагодарить авторов и далее обращаться как с черным ящиком. Если же в читателе сильна любознательность, и/или есть желание постигнуть тайное знание, которое даст ощущение понимания странного поведения программ в нетривиальных случаях, добро пожаловать под кат.
Три архитектуры эльфам, семь гномам, девять людям… где же искать ту, что объединит их все?
60 min
Проводится сеанс разоблачения магии (CISC, RISC, OoO, VLIW, EPIC, ...).
Без традиционной рубрики “а что, если” тоже не обошлось.
Добро пожаловать под кат, правда, лёгкого чтения ожидать не стоит.
4K страницы: навсегда, на веки вечные
11 min
По ощущениям, 4К страницы памяти были с нам всегда, они воспринимаются как нечто совершенно естественное, аксиоматическое. В технике, где за любым числом стоит компромисс, это означает, что либо удалось нащупать объективный баланс, либо что число это находится в самом фундаменте и трогать его себе дороже, даже если изменения назрели.
Но, "для нас нет ничего святого"(С), попробуем выяснить почему именно 4К, изменится ли что-то если сделать 8К, 64К... Зачем вообще фиксировать конкретный размер, почему не сделать страницы произвольной (в пределах разумного) длины.
Как устроено множество Мандельброта. Хвост
9 min
Хвостом будем считать череду структур к западу от центральной кардиоиды вдоль по отрицательной части вещественной оси. В этой области таится целая бездна деталей. А в деталях, как известно, кроется дьявол … и его малютки.
Как устроено множество Мандельброта. Центральная кардиоида
5 min
Хорошо известно, что центральная часть множества Мандельброта представляет из себя кардиоиду. Не просто похожа, а именно ей и является. Сегодня мы пытаемся понять, почему именно кардиоида и что из этого следует.
Почему множество Мандельброта устроено так, как оно устроено
5 min
Созерцание фракталов завораживает, особенно это относится к предмету данной статьи, который демонстрирует вдобавок ко всему еще и изрядное разнообразие. Впрочем, не менее интересно попытаться разобраться, откуда что берётся, как из одного, в сущности, (пусть и комплексного) числа рождается всё это великолепие.
Если любопытно, добро пожаловать под кат.
STL, allocator, его разделяемая память и её особенности
11 min
Разделяемая память — самый быстрый способ обмена данными между процессами. Но в отличие от потоковых механизмов (трубы, сокеты всех мастей, файловые очереди ...), здесь у программиста полная свобода действий, в результате пишут кто во что горазд.
Так и автор однажды задался мыслью, а что если … если произойдёт вырождение адресов сегментов разделяемой памяти в разных процессах. Вообще-то именно это происходит, когда процесс с разделяемой памятью делает fork, а как насчет разных процессов? Кроме того, не во всех системах есть fork.
Казалось бы, совпали адреса и что с того? Как минимум, можно пользоваться абсолютными указателями и это избавляет от кучи головной боли. Станет возможно работать со строками и контейнерами С++, сконструированными из разделяемой памяти.
Отличный, кстати, пример. Не то, чтобы автор сильно любил STL, но это возможность продемонстрировать компактный и всем понятный тест на работоспособность предлагаемой методики. Методики, позволяющей (как видится) существенно упростить и ускорить межпроцессное взаимодействие. Вот работает ли она и чем придётся заплатить, будем разбираться далее.
Нерушимая память, нерушимые процессы
15 min
Прочитав недавно (1, 2, 3) с каким трудом даются “космические” процессоры, невольно задался мыслью, раз “цена” за устойчивое железо настолько высока, может быть стоит сделать шаг и с другой стороны — сделать устойчивый к спецфакторам “софт”? Но не прикладной софт, а скорее среду его выполнения: компилятор, ОС. Можно ли сделать так, чтобы выполнение программы в любой момент можно было оборвать, перезагрузить систему и продолжить с того же (или почти с того же) места. Существует же в конце концов гибернация.
Про геометрический смысл кодов Грея
3 min
Коды Грея имеют близкую родственную связь с кривой Гильберта.
Впрочем, при общении с коллегами выяснилось, что эта несложная зависимость выглядит в их глазах как нечто нетривиальное. Поиск в интернетах навскидку ничего не дал кроме мутной фразы в вики: “кривые Гильберта в пространствах большей размерности являются представителями обобщений кодов Грея”. Поэтому возникло желание раскрыть тему — коротенько, простым языком.
В результате под катом — «скандалы, интриги, расследования».
Логические поля в базах данных, есть ли противоядие
9 min
Часто в таблицах содержится большое количество логических полей, проиндексировать все из них нет возможности, да и эффективность такой индексации низка. Тем не менее, для работы с произвольными логическими выражениями в SQL пригоден механизм многомерной индексации о чем и пойдёт речь под катом.
Расставляем стандартные ячейки (заметки постороннего)
7 min
Натолкнувшись на статью “Уничтожим монополию …”, автор, как человек пусть от EDA очень далёкий, но от природы любознательный, не поленился пройтись по ссылкам и невольно поймал себя на мысли, что одно из основных технических решений — использование рядов стандартных ячеек (standard cell layout) — выглядит довольно спорно.
Да, такое расположение интуитивно понятно, ведь мы пишем и читаем похожим образом, кроме того, технологически просто располагать ячейки именно рядами, так удобно стыковать шины VDD и GND. С другой стороны, при этом возникает непростая комбинаторная задача, требуется разрезать схему на линейные куски и расположить эти куски таким образом, чтобы (грубо) минимизировать общую длину соединений.
И конечно же возник вопрос, нет ли альтернативных решений, … вот что если …
Гильберт, Лебег … и пустота
17 min
Под катом исследуется вопрос, как должен быть устроен хороший алгоритм многомерной индексации. На удивление, вариантов не так уж и много.
Lambda-функции в SQL… дайте подумать
13 min
О чем будет статья, и так понятно из названия.
Кроме того, автор объяснит, зачем с его точки зрения это нужно, а также расскажет, что SUBJ не просто модная технология, но и «дело вдвойне нужное — как приятное, так и полезное».
Колоночные СУБД против строчных, как насчет компромисса?
7 min
Колоночные СУБД активно развивались в нулевых годах, на данный момент они нашли свою нишу и практически не конкурируют с традиционными, строчными системами. Под катом автор разбирается, возможно ли универсальное решение и насколько оно целесообразно.
Кривая Гильберта vs Z-order
9 min
Неоднократно доводилось слышать мнение, что из всех заметающих кривых. именно кривая Гильберта наиболее перспективна для пространственной индексации. Мотивируется это тем, что она не содержит разрывов и потому в некотором смысле “хорошо устроена”. Так ли это на самом деле и при чем здесь пространственная индексация, разберёмся под катом.