Monday, December 29, 2008

Производительность реализаций str(с)spn

Тесты strspn:

  1. Стандартная реализация: .850.870
  2. Тестовая реализация на С(пример кода в glibc): 1.886.713
  3. С удаленной переменной количество пропущенный символов: 1.757.733
  4. Использование множества для проверки разрешенных символов: 1.651.749
  5. С добавлением фильтрации на бинарный максимум и минимум: 2.983.546

Тесты strcspn:

  1. Стандартная реализация: 1.388.789
  2. Тестовая реализация на С(пример кода в glibc): 10.329.430
  3. Удаление вызова функции поиска символа в строке: 2.444.628
  4. С удаленной переменной количество пропущенный символов: 2.222.662
  5. Использование множества для проверки разрешенных символов: 1.607.756
  6. Использование множества для проверки разрешенных символов(с начальным сохранением разыменованного указателя): 1.654.748
  7. Использование множества для проверки разрешенных символов с фильтрацией на бинарный максимум и минимум: 1.872.716
  8. Использование множества для проверки разрешенных символов с фильтрацией на бинарный максимум и минимум(с начальным сохранением разыменованного указателя): 1.720.738
По результатам видно что добавление фильтра ничего не дает кроме 6% замедления по сравнению с обычной версией с использованием множества. То есть 2 операции косвенной адресации с последующим сравнением работают быстрее чем 1 операция косвенной адресации с бинарной операцией и сравнением результата.

Есть предположение что это следствие особенностей архитектуры:
  • оптимизации в Суперскалярной архитектуре(данные уже подгружены в кеш результатов);
  • быстрой работе с кешем (различия в косвенной адресации и обращении к регистру минимальны);
  • компилятор не разместил фильтр в регистре процессора и как результат получили вместо одного косвенного обращения два как и при работе с множеством(отличия для тестов с использованием разыменованного указателя).
В общем нужно пробовать оптимизировать ассемблерный код для исключения возможности косвенной адресации к фильтрам. Или придумать другие тесты....

P.S. Время указано в миллисекундах для Intel(R) Pentium(R) 4 CPU 3.00GHz(32 бита) и исходники тестов можно посмотреть c/strspn.

Saturday, December 27, 2008

Singularity?

Удалось запустить Singularity под эмулятором - она запустилась только под виртуальной машиной Microsoft(Microsoft Virtual PC/). Где то месяц назад пытался запустить под bochs и VMWare но в обоих эмуляторах она не запустилась - точную причину ошибки не помню, под Virtual PC она тоже не сразу запустилась - в стандартном примере настроек было указано 512 метров памяти - при запуске вывалилась ошибка, что столько памяти виртуальная машина выделить не может, оказалось для запуска нужно около 400 метров памяти в виртуальной машине(стандартных 128 мало), если памяти мало запуск(загрузка самой ОС) выдает что не может выделить достаточно памяти. После запуска появляется командная строка - с очень маленьким количеством команд. В общем не впечатлило - как демонстрация концепции в общем не плохо - но документация года три назад меня больше понравилась - а пока видно основной недостаток для демонстрации требование в пол гигабайта мне кажется много. Я думал что за три года они достигли больших успехов. По сравнению с Minix(концепция близка) и даже другими миниос - демонстрация не очень.

Ну а идея в общем то не плоха использовать для всех компонентов управляемый код(только загрузчик на C), но идея не уникальна ОС на java тоже существует, например JNode и требования по описанию ниже(сам не пробовал).
Идея:
  1. ограничить коммуникацию между приложениями и ядром только сообщениями;
  2. описание в заголовке приложения всей требующихся ему ресурсов и возможностей(нужен ли доступ к сети, возможности и потребность в памяти);
  3. возможность перезапуска приложения при сбое;
  4. отсутствие требования к смене контекста и блокирования доступа к чужим страницам, так как доступ к памяти полностью управляется средствами языка(Не очень критичное улучшение, так как все эти операции часто контролируются аппаратно, например x86).
- уже реализовано в других операционных системах и как следствие имеет общие с ними проблемы:
  1. накладные расходы по передаче сообщений между элементами(MINIX - обычно это ограничение указывается для него);
  2. реализация части функция вне ядра в виде сервисов добавляет дополнительные затраты(опять таки MINIX), хотя в принципе при хорошо продуманном интерфейсе это не столь существенно и так работает графика в Vista и Linux(Xсы).
Ограничение возможностей для приложений, в распостраненных ос, очень часто расширяют для особенных приложений, из-за ошибок в этих приложениях эта защита преодолевается. И как следствие, эта система не всегда работает особенно при увеличении популярности ос.

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

Достаточно интересным примером я считаю минимальное количество функций доступных приложению в Linux(как и Unix) и простота и универсальность этих функций и предоставляемых абстракций. Абстракции в Inferno(расширение концепций Unix) мне показались немного излишними, но возможно если их более точно понять, что под ними скрывается они окажутся даже более удобными и универсальными - пока я по описанию не очень точно понял смысл понятий на которых они основываются(отличие от концепций Unix). Но они достаточно эффективны, так как позволяют выполнять действия такие как копирование контента между 2 узлами управляемое с 3 достаточно эффективным через передачу управления непосредственно на первых 2 узла с передачей на 3 только статистики(очень похоже на самостоятельное управление передачей устройствами SCSI), вопрос безопасности и получения доверия между этими узлами в принципе решаем и при важности скрытия источника и приемника информации(непосредственно узлы не должны иметь полных данных) вполне решаем.

Thursday, December 25, 2008

Уточнения относительно старых постов

  • Изменения к gtkhtml применили полностью(rev 9074) теперь entity заменяются на основе кода созданного gperf и код замены использует двойной буфер.
  • По тесту Тьюринга - вопрос можно ли создать искусственный интеллект не обязательно сводить к философскому вопросу: "Познаваем ли мир", его можно решить создавая урезанную версию только в определенной области, при этом получаться четко ограниченные возможности и на новые идеи(решения) даже в этой области он не способен.

Monday, December 22, 2008

Сборка мусора

Или GC(Garbage Collection) применимо к glib.

В glib относительно памяти есть договоренность, что если возвращается константный указатель. то его освобождать не нужно, а в обратном случае нужно. Так же для gobject существуют функции g_object_ref () и g_object_unref (). Это решает проблему с слежением за выделением памяти, но требует от разработчика чтобы он следил за выделением памяти и при каждом копировании указатяля делал соответствующий вызов ref/unref. Что не совсем удобно... Система автоматической сборки мусора в C# или Java более удобна, но требует соответствующей поддержки от компилятора. Хотя эта проблема решена в Vala, так как он автоматически добавляет вызовы удаления памяти в чистом виде в glib его нет.

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

Отличие он настоящей сборки мусора - автоматически память не освобождается, только добавляется код отладки освобождения чтобы можно было посмотреть где выделялось. Очищать память автоматически не удастся(нужно придумывать систему макросов), что в общем случае делать не хочется или изменять компилятор. Оптимизация размещения объектов в памяти для glibc несколько теряет смысл так как все изменения указателей отслуживать сложно и нужно изменять код чтобы с непосредственно с указателями никто не работал и как-то выделял все ссылки в объектах чтобы можно было менять их расположение - что скорее всего особого смысла не имеет.

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

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

Sunday, December 21, 2008

Изменения к gtkhtml

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

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

Пока не применены мои изменения относительно замены функции получения кода спецсимвола по его имени через автоматически сгенерированную hash функцию(gperf) и замена ранее указанного перемещения(сдвига памяти) на использование 2 буферов.

В дальнейшем gtkhtml в evolution(по планам) будет заменен на WebKit и если планы не изменяться, то развитие проекта будет прекращено. А пока я подправил также и свой миниброузер ради которого и были сделаны эти изменения.

Wednesday, December 17, 2008

WebOs

Заготовка к 3 выступлению, которая не понадобилась.
Глубокие исследования не проводились,
только в теории.

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

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

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

Основными требованиями к данному хранилищу является:
  1. простота добавления новых документов с локального компьютера и возможность добавления с общедоступных сервером минуя стадию копирования файла на локальный диск, файл загружается с ресурса в глобальное хранилище автоматически;
  2. защищенность сеансов связи и использование аутентификации пользователя;
  3. экономия трафика системы - загрузка по запросу (с использованием логики пред-загрузки для файлов к которым происходит частое обращение в прошлых сеансах), реализация загрузки только отличий файлов.
Все существующее методы обеспечения и реализации удаленного рабочего стола обладают некоторыми недостатками:
  1. во время работы в такой среде требуется, чтобы на удаленном компьютере уже стояли полностью настроенные браузеры с установленными java и flash плагинами- что не во всех случаях доступно конечному пользователю.
  2. требование поддержки данными браузерами определенных технологий(javascript), что приводит к невозможности использования некоторых браузеров, если на них не было изначально рассчитано приложение.
  3. некоторые системы требуют установки дополнительных компонентов, контролировать работу которых сложно.
  4. большой объем пересылаемой информации на сервер, так как некоторые функции выполнить на локальном компьютере через браузер сложно;
  5. закрытость архитектуры – что, зачем, и куда отсылается;
  6. закрытость процедуры аутентификации, невозможно проверить ее надежность.
  7. не полная поддержка функций требующихся обычному пользователю (отсутствие интеграции компонентов и не полнота функций), например, существует: календарь, internet messenger, редактор текстов и изображений и почта, с возможность использования как хранилище документов, но они организованы как web-портал c упрощением многих функций. Это хорошо для возможности доступа с любой точки земного шара, но для постоянной работы не подходит;
  8. отсутствие гарантий конфиденциальности и неразглашения информации;
  9. реализация на основе систем удаленного рабочего стола, приводит к передаче больших объемов информации (действия пользователя + изображение с сервера), хоть и выполняется после сжатия и шифрования, представляют существенный объем, и не позволяют передавать звук и мультимедиа информацию;
  10. не реализована возможность работы при утере связи.
В результате исследования рассмотрены варианты реализации этой системы и сформированы принципы формирования эвристических правил определения первоочередности загрузки файлов с глобального хранилища в локальное. Введены категории по которым осуществляется расстановка приоритетов загрузки и синхронизации файлов. На основе составления статистики использования файлов пользователем и его предпочтений.

Wednesday, December 10, 2008

Динамический пользовательский интерфейс

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

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

Причиной почему был выбран XML было простота реализации рекурсивного описания компонентов внутри формочек и возможность в случае чего без редактора этих форм - руками подправить ошибки. Из этого XML формировался классы(C#) для упрощения дальнейшей обработки структуры и эти классы в дальнейшем передавались компоненту который по классам формировал элементы с нужной вложенностью и структурой.

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

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

Запуск приложения это создание контроллера окон с подгрузкой всех нужных данный и подачей сообщения о создании окна с параметрами.

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

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

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

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

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

Sunday, December 7, 2008

Проектирование


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