Записки программиста

Про сабж можно почитать на хабре: http://habrahabr.ru/blogs/infosecurity/70330/.

Исследовал тему хранилищ типа ключ/значение и обратил внимание, что все тесты на производительность сетевых хранилищ производились в однопоточном режиме. Типа “Tokyo Cabinet крутая бибилиотека, выдаёт порядка 17К запросов в секунду на дисковой базе данных, но через сеть (Tokyo Tyrant) всего 1.6К запросов в секунду”, а потом “latency — это зло”. Но почему-то не видел многопоточных тестов, как это бывает в реальных web-приложениях со множеством фронтендов. И не видел клиентских библиотек, работающих по событийной схеме, а не по схеме “послал запрос, жду ответа, ненавижу latency”. Ведь в этих случаях latency будет не так страшна, или я где-то не прав?

Гео-база maxmind окончательно задолбала своими приколами, когда треть Москвы определяется как область в Великобритании. Могу себе представить как она определяет географию для других городов России. В поисках нормальной базы ip-адресов России нашёл ipgeobase.ru. Бесплатная, поддерживаемая, актуальная база для России. Но когда дело дошло до парсинга, меня её формат взбесил. Вместо того, чтобы сделать так, как делают те же maxmind, где последовательно располагаются блоки адресов, они реализовали структуру со множественными вложениями, парсер для которой, без поллитра не напишешь.

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

Скачать скрипт можно тут: ipgeobase.php.gz.

Для работы скрипта нужен файл cidr_ru_block.txt из архива db_files.tar.gz. Запускаться скрипт должен в том же каталоге, что и cidr_ru_block.txt. После работы скрипта появляются 3 файла: ipgeobase-states.dat, ipgeobase-cities.dat, ipgeobase-ips.dat.

В ipgeobase-states.dat храняться области в формате [идентификатор области]\t[название области].
В ipgeobase-cities.dat храняться города в формате [идентификатор города]\t[идентификатор области]\t[название города].
В ipgeobase-ips.dat храняться диапазоны ip-адресов в формате [IP от]\t[IP до]\t[идентификатор области]\t[идентификатор города].

При повторном запуске скрипт начитывает данные из ipgeobase-states.dat и ipgeobase-cities.dat (если они есть). Таким образом, при появлении новых городов или областей, идентификаторы “старых” записей не изменятся. IP храняться в виде беззнакового 32-битного числа.

Как-то так, надеюсь кому-то мой труд облегчит жизнь

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

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

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

Теперь о самом решении. Задача стоит в том, чтобы максимально быстро выбрать набор данных, удовлетворяющих некоторому набору признаков, представленных в виде битовой маски. Далее предполагается, что мы работаем со 128-битным регистрами sse.

Мои идеи крутились вокруг деления битовой маски на куски по 128 бит и последовательной проверки каждого слова на соответствие поисковой маске. В результате получается матрица размерностью ceil(размер битовой маски / 128) по ширине и длинной в количество записей.

Новая идея в том, что мы строим матрицу, где строке соответствует один бит из битовой маски, а в столбцах у нас записи. Таким образом, у нас одно слово описывает один бит у 128 записей. Получается, что за одну операцию мы проверяем один бит у 128 записей. Если у нас n бит в маске, то мы проверим 128 записей за n операций. По-моему красиво

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

ИМХО красивая реализация

Давненько я тут не писал, совсем разленился… Решил написать о чём болит голова второй день…

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

Первое что приходит в голову для ускорения перебора — использование битовых операций. Сформировал маску и пошёл AND-ом по списку, красота. Но когда наткнулся на необходимость проверить что значение больше (или меньше) заданного, впал в ступор. Если диапазон значений меньше или равен количеству бит в целом, никаких проблем нет, а если диапазон шире, ступор.

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

В своё время я достаточно долго искал словари для использования их в контексте. В результате написал на php скрипт для генерации словоформ русского языка на основе словаря aspell. Кому надо, может скачать архив.

В архиве словарь aspell для русского языка в формате utf-8 и два скрипта, которые генерируют словоформы с разным форматом вывода. В результате получается порядка 1.3М словоформ.

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

В результате перешёл на использование HTTP. Для себя я выделил следующие преимущества. Во-первых, при использовании HTTP, у меня есть возможность использовать огромное количество готового программного обеспечения для создания инфраструктуры. Тот же nginx можно прикрутить в качестве балансировщика. Во-вторых, теперь никаких telnet-ов для тестирования, можно использовать любой браузер. В третьих, такой демон можно легко, без переработок, использовать в качестве сервиса с доступом по HTTP.

Рекомендую подумать на эту тему

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

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

Сейчас ломаю голову как показывать баннеры в контекстной сети. Вопрос делится на два возможных варианта: показ рекламы в контекстной сети на подобии Adsense, бегун или директ (где выбирается заданное количество объявлений подходящих по ключевым словам для данной страницы) и показ в контекстной сети на подобии videoclick или автоконтекста бегуна (где линкуются ключевые фразы на странице, при наведении на которые, показывается реклама).

В обоих вариантах есть общие вещи, но есть и различия. В первом варианте кампании не конфликтуют друг с другом, а просто выбираются на основе каких-то приоритетов (скорее всего по ECPM, количеству заработанных денег за тысячу показов), а во втором легко может произойти конфликт, когда одна или более кампаний “дерутся” за одно слово или фразу. Читать дальше…