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



Есть мнение, что специализированная read-only файловая система при прочих равных обладает преимуществами перед оной общего назначения т.к:

1. не обязательно управлять свободным пространством;
2. не надо тратиться на журналирование;
3. можно не заботиться о фрагментации и хранить файлы непрерывно;
4. возможно собрать всю мета-информацию в одном месте и эффективно ее кэшировать;
5. грех не сжимать мета-информацию, раз уж она оказалась в одной куче.

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

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

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

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

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

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

Несмотря на то, что эта структура данных была открыта давно и использовалась в текстовых редакторах на старых ЭВМ в 8-битную эпоху, это тайное знание предков было в значительной мере утеряно и в современных редакторах встречается редко. Попробуйте открыть файл, состоящий из одной строки мегабайт на 10, в Notepad или Far. Вставка и удаление символов будет длиться секундами.

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

Анонс. Спасибо за теплый прием Начал! Вижу, что тема lock-free интересна хабрасообществу, это меня радует. Я планировал построить цикл по академическому принципу, плавно переходя от основ к алгоритмам, попутно иллюстрируя текст кодом из libcds. Но часть читателей требует зрелищ не мешкая показать, как пользоваться библиотекой, особо не рассусоливая. Я согласен, в этом есть свой резон. В конечном счете, и мне не так интересно, что там внутри boost, — опишите, как его применять! Поэтому свой эпический цикл я разделю на три части: Основы, Внутри и Извне. Каждая статья эпопеи будет относится к одной из частей. В Основах будет рассказываться о низкоуровневых вещах, вплоть до строения современных процессоров; это часть для почемучек вроде меня. Внутри будет освещать интересные алгоритмы и подходы в мире lock-free, — это скорее теория о том, как реализовать lock-free структуру данных, libcds будет неисчерпаемым источником C++ кода. В Извне будут статьи о практике применения libcds, — программные решения, советы и FAQ. Извне будет питаться вашими вопросами/замечаниями/предложениями, дорогие хабражители.

А пока я судорожно готовлю начало Извне, — первая часть Основ. Статья во многом не о C++ (хотя и о нем тоже) и даже не о lock-free (хотя без atomic lock-free алгоритмы неработоспособны), а о реализации атомарных примитивов в современных процессорах и о базовых проблемах, возникающих при использовании таких примитивов.
Атомарность — это первый круг ада низкий уровень из двух.

Я полагаю что все в общих чертах знают о существовании такого замечательного математического инструмента как преобразование Фурье. Однако в ВУЗах его почему-то преподают настолько плохо, что понимают как это преобразование работает и как им правильно следует пользоваться сравнительно немного людей. Между тем математика данного преобразования на удивление красива, проста и изящна. Я предлагаю всем желающим узнать немного больше о преобразовании Фурье и близкой ему теме того как аналоговые сигналы удается эффективно превращать для вычислительной обработки в цифровые.

(с) xkcd

Без использования сложных формул и матлаба я постараюсь ответить на следующие вопросы:

• FT, DTF, DTFT — в чем отличия и как совершенно разные казалось бы формулы дают столь концептуально похожие результаты?
• Как правильно интерпретировать результаты быстрого преобразования Фурье (FFT)
• Что делать если дан сигнал из 179 сэмплов а БПФ требует на вход последовательность по длине равную степени двойки
• Почему при попытке получить с помощью Фурье спектр синусоиды вместо ожидаемой одиночной “палки” на графике вылезает странная загогулина и что с этим можно сделать
• Зачем перед АЦП и после ЦАП ставят аналоговые фильтры
• Можно ли оцифровать АЦП сигнал с частотой выше половины частоты дискретизации (школьный ответ неверен, правильный ответ — можно)
• Как по цифровой последовательности восстанавливают исходный сигнал

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

Количество ложно-положительных срабатываний фильтра Блума.

Описание

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

Грубо говоря, фильтр Блума возвращает 2 возможных ответа:

1. элемента нет в векторе
2. элемент возможно есть в векторе

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

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

UPD: схема заменена на вариант с контейнерами из С++11, соавторы — в комментариях ниже

Я обожаю программирование графики! Мы все совершаем ошибки в процессе проектирования и написания кода. Иногда это ошибки логики (когда алгоритм продуман неточно или не до конца), иногда ошибки, возникающие по невнимательности, и ещё много-много вариантов. И что происходит в обычном рабочем процессе? — В списках нет необходимых записей, какие-то числа считаются неверно, вываливаются сообщения об ошибках и прочее. В программировании графики всё немного веселее, ведь часто мы получаем результат, который просто не соответствует ожидаемому. В своём небольшом проекте я решил сохранять такие “результаты” на протяжении всего процесса разработки и хотел бы поделиться ими с Вами.

Всех, кто не любит Android, Live Wallpaper, Minecraft, велосипеды, поток сознания, который слабо привязан к теме и всё около того, хочу сразу предупредить, что их может огорчить содержание этого поста, поэтому продолжайте чтение на свой страх и риск. Оставлю тут также и предупреждение для пользователей мобильного или просто небезлимитного интернета: дальше последует довольно много картинок.

Наш архитектор департамента серверной виртуализации Павел Емельянов дал интервью журналу «Системный администратор». Мы решили опубликовать здесь его интервью, в котором он рассказал о проекте CRIU, о том, как команда разработчиков работает с Linux-сообществом и с Линусом Торвальдсом, и об изменениях, которые могут произойти в области виртуализации в ближайшие годы.

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

Оригинальный pdf (на английском)
Переведённый pdf (на русском)

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

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

В предыдущих статьях с фотографиями кристаллов микросхем (1, 2, 3) — в комментариях писали о том, что было бы неплохо разобрать простую микросхему по деталям — чтобы было понятно «что есть что» на самом низком уровне, и где там «магический дым» прячется. Я долго не мог выбрать микросхему, в схеме которой можно было бы разобраться за несколько минут — но наконец решение было найдено: ULN2003 — массив транзисторов Дарлингтона.

Несмотря на свою простоту, микросхема до сих пор широко используется и производится. ULN2003 состоит из 21 резистора, 14 транзисторов и 7 диодов. Применяют её для управления относительно мощной нагрузкой (до 50 вольт / 0.5 ампер) от ножки микроконтроллера (или других цифровых микросхем). Каноническое применение — для управления мощными 7-и сегментными светодиодными индикаторами.

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

Эта статья рассказывает о времени выполнения и о расходе памяти большинства алгоритмов используемых в информатике. В прошлом, когда я готовился к прохождению собеседования я потратил много времени исследуя интернет для поиска информации о лучшем, среднем и худшем случае работы алгоритмов поиска и сортировки, чтобы заданный вопрос на собеседовании не поставил меня в тупик. За последние несколько лет я проходил интервью в нескольких стартапах из Силиконовой долины, а также в некоторых крупных компаниях таких как Yahoo, eBay, LinkedIn и Google и каждый раз, когда я готовился к интервью, я подумал: «Почему никто не создал хорошую шпаргалку по асимптотической сложности алгоритмов? ». Чтобы сохранить ваше время я создал такую шпаргалку. Наслаждайтесь!

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

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

Если когда-нибудь вы задумывались над тем, что значат слова «the processor supports precise aborts» в даташите, прошу под кат.

В повседневной практике разработчика встраиваемых систем приходится сталкиваться с необходимостью запуска двух и более разноплановых ОС на n-ядерных системах на кристалле. Это, как правило, Linux и специализированная RTOS. На плечи Linux ложится работа с тяжеловесными стеками протоколов, а RTOS же занимается задачами реального времени.
 
Одна из основных задач, которая встает при такой организации системы — обеспечение механизма взаимодействия, то есть межъядерный обмен данными. Если вам интересно узнать один из вариантов решения на базе открытой библиотеки OpenMCAPI, пролистать пару десятков строк программного кода и увидеть реальные цифры пропускной способности при использовании этой библиотеки, добро пожаловать под кат.

В настоящее время очевидно смещение вектора компьютерных атак от массового заражения к целевым, точечным атакам. Как сказал Е. Касперский: «Девяностые были десятилетием киберхулиганов, двухтысячные были десятилетием киберпреступников, сейчас наступила эра кибервойн и кибертеррора». Иллюстрацией этому являются всем известные примеры: Stuxnet, Duqu, Flamer, Gauss, которые многие антивирусные компании причисляют к кибероружию.

Основные тенденции в компьютерной безопасности

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

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

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

Позади уже полторы (первая, полуторная) части этой статьи, теперь наконец пришло время рассказать о структуре UEFI Firmware Volume и формате UEFI File System.