Сравнение эффективности CLB-дерева в 32-битных и 64-битных архитектурах.
Веретенников Александр Борисович
Уральский государственный университет им. А. М. Горького
abvmt2@mail.ru, abvmt@e1.ru
http://cs.usu.edu.ru/home/abv/

	В настоящее время активно развивается разработка приложений в 64-битных архитектурах. В частности, процессоры Intel и AMD уже поддерживают архитектуру EM64T. Автор разработал ряд алгоритмов [1-5], предназначенных для создания индекса и поиска в большом наборе текстовых документов. Данные алгоритмы были успешно опробованы в 32-битной архитектуре. В данной работе рассмотрены вопросы связанные с вопросом перехода с 32-битной архитектуры на 64-битную и приведены результаты экспериментов сравнения производительности в 32-битной и 64-битной среде.

Основные преимущества 64-битной архитектуры.

	Основным преимуществом данной архитектуры очевидно является объем адресуемой оперативной памяти. В 32-битной архитектуре максимальный объем адресного пространства составляет 4 Гб. При этом обычно операционная система резервирует часть этого пространства под собственные нужды и приложению остается например 2 Гб. На сегодняшний момент подобный объем оперативной памяти часто недостаточен для решения ряда задач.
	Следует также отметить, что при ограничении в 2 Гб мы обычно не можем задействовать все 2 Гб, т. к. при выделении  блоков памяти память может стать фрагментированной. Как правило в случае невозможности выделить блок памяти возбуждается исключение. Корректная обработка данной ситуации и восстановление работы программы могут быть достаточно сложны. Некоторые системы для решения данной проблемы не используют больше 1,5 Гб оперативной памяти, оставляя таким образом некоторый запас для надежности.

Эксперименты проводились на следующей конфигурации:

Процессор: Intel Core 2 Duo E6700, 2.66 GHz, кэш: L1  Data – 2 x 32 кб, L1 inst. 2 x 32 кб, L2 - 4096 кб.
Оперативная память: 8 гб, DDR2 800.
Жесткий диск: Seagate Barracuda 7200.10, 7200 RPM, кэш 16 мб., объем 750 гб.
FSB 1066 MHz.
Операционная система: Microsoft Windows 2008 Enterprise x64 Edition with Service Pack 1.

	Следует отметить, что данная операционная система и процессор позволяют выполнять как 32-, так и 64-битные приложения.

Архитектура системы

	Исследуемые алгоритмы	 оформлены в виде библиотеки. Библиотека может индексировать файлы в различных форматах, например RTF, PDF, CHM, HTML, DJVU и кодировках, например UNICODE, UTF8, CP1251, ASCII, KOI8. Поддерживается обработка архивов форматов ZIP, CAB, RAR, 7Z, ARJ, TAR, и др. Библиотека реализована в виде COM-сервера для операционных систем Windows.

Состав библиотеки
1.	Ядро, осуществляет создание индекса и поиск.
2.	Модуль поддержки морфологии.
3.	Модуль распознавания кодировки. При распознавании кодировки также учитывается морфология.
4.	Модуль поддержки форматов файлов. Поддержка форматов файлов и архивов реализована с помощью подключаемых дополнительных модулей, которые могут быть реализованы в виде динамических библиотек или написаны на Java. Модуль поддержки форматов файлов реализован в виде отдельного процесса для повышения надежности системы.
5.	Модуль атрибутов документов, для сохранения описания документов.
6.	Модуль репозитария, для сохранения текстов документов. Создается для того, чтобы при поиске можно было быстро получать фрагмент текста, содержащий найденную фразу. Тексты в репозитарии могут сохраняться с использованием различных алгоритмов сжатия.
 7.	Модуль COM осуществляет доступ к остальным модулям извне с помощью COM, что позволяет использовать библиотеку в различных языках программирования.
 8.	Модуль создания индекса похожих документов.

	Библиотека написана на языке C++. Для компиляции использовался компилятор из Microsoft Visual Studio 2008. COM-сервер реализован с помощью библиотеки ATL. Также используется библиотека STL. 
	Модуль 4 организован в виде отдельного исполняемого файла, который вызывает отдельные подмодули для каждого формата файла. Модуль 2 выделен в отдельную динамическую библиотеку. Остальные модули скомпилированы вместе в одну динамическую библиотеку.
	На 64-битную архитектуру были переведены все модули, кроме модуля поддержки форматов файлов и его подмодулей. Модуль поддержки форматов реализован в виде отдельного процесса, и таким образом его можно использовать и в 32-, и в 64-битном приложении.

	Далее указано, какие ресурсы потребляет каждый модуль в процессе работы. Выделено два типа ресурсов: 1 - вычислительные ресурсы (процессор и обращения к оперативной памяти), 2 - внешняя память (чтение и запись на жесткий диск).

Название модуля	Потребление ресурсов процессора и оперативной памяти	Использование жесткого диска	
Ядро	Среднее	Большое	
Модуль распознавания кодировки	Незначительно	Отсутствует	
Модуль поддержки морфологии	Большое	Отсутствует	
Модуль поддержки форматов файлов	Большое	Среднее	
Модуль атрибутов документов	Незначительно	Незначительно	
Модуль репозитария	В зависимости от используемых алгоритмов сжатия	Большое	
Создание индекса похожих документов	Большое	Среднее	

Рассмотренные вопросы перехода на 64-битную архитектуру:

1.	Библиотека реализована в виде COM-сервера, рассмотрен вопрос перевода COM-сервера с 32-битной на 64-битную архитектуру.
2.	Вопросы связанные с размером указателя и числовых типов данных, которые могли изменится с переходом на 64-битную архитектуру.
3.	Модуль 4 остался без изменений. Рассмотрены вопросы корректной передачи данных между основным процессом и модулем 4.

Перевод COM-сервера на 64-битную архитектуру.

	Перевод COM-сервера с 32-битной на 64-битную архитектуру не вызвал никаких проблем. Для этого потребовалось только изменить настройки компилятора. 

Размеры типов данных

	Размер указателя естественно меняется с 32 бита на 64 бита. Теоретически могут возникать проблемы, если используется преобразование указателя в числовой тип и обратно. Таких проблем обнаружено не было.
	Размеры числовых типов могут варьироваться в зависимости от компилятора. В используемом компиляторе числовые типы short, int, long, long long и их беззнаковые аналоги имеют одинаковый размер как на 32-битной архитектуре, так и на 64-битной архитектуре (соответственно 16, 32, 32, 64 бита).

Эксперименты

	Были проведены эксперименты создания индекса.
Параметры создания индекса, которые влияют на производительность:

H	Размер B дерева	
K	Размер кластера для слов, входящих в словарь морфологического анализатора.	
KU	Размер кластера для слов, не входящих в словарь морфологического анализатора.	

Автор не описывает смысл данных параметров, детальное описание можно получить в [1-3]. Далее кратко приведен алгоритм создания индекса.

1.	Чтение файлов и запись данных во временные файлы (предварительная обработка). Этап включает в себя морфологический анализ, анализ кодировки файлов и запись данных в репозитарий.
2.	Запись данных из временных файлов в индекс.
2.1.	Добавление в индекс слов, входящих в словарь морфологического анализатора
2.2.	Добавление в индекс слов, не входящих в словарь морфологического анализатора
2.3.	Добавление в индекс информации о часто используемых словах.
3.	Создание индекса похожих документов.

	1. Индексирование набора текстовых документов.

	Общий размер документов: 86 Гб, известных слов 90%. Все файлы представляли собой обычный текст.
	H = 32 Кб, K = 256 Кб, KU = 16 Кб, размер кэша 1 Гб, размер буфера для индекса похожих документов 1 Гб.
	Получившийся объем индекса 56 Гб.
	Репозитарий, индекс похожих документов и индекс часто используемых слов не создавались.

	32	64	
Общее время создания индекса	4 ч 16 мин	4 ч 11 мин	
Распознавание кодировки	3 мин 27 сек	3 мин 8 сек	
Морфологический анализ	49 мин 36 сек	51 мин 45 сек	
Чтение файлов	2 ч 50 мин	2 ч 44 мин	
Время добавления в индекс слов, входящих в словарь морфологического анализатора	54 мин	52 мин	
Время добавления в индекс слов, не входящих в словарь морфологического анализатора	31 мин	34 мин	
Суммарное время добавления данных в индекс	1 час 25 мин	1 час 26 мин	

	2. Индексирование набора текстовых документов.

	Набор файлов и параметры, аналогичный предыдущему.
	Только в этот раз создавался репозитарий, индекс похожих документов и индекс часто используемых слов. При создании репозитария использовался алгоритм Хаффмана для сжатия данных.
	Суммарный объем индекса 139 Гб, из них 57 Гб - репозитарий.

	32	64	
Общее время создания индекса	7 ч 43 мин	7 ч 41 мин	
Распознавание кодировки	3 мин 20 сек	3 мин 42 сек	
Морфологический анализ	50 мин 36 сек	55 мин 07 сек	
Чтение файлов	3 ч 58 мин	3 ч 44 мин	
Создание индекса похожих документов	1 ч 17 мин	1 ч 33 мин	
Время добавления в индекс слов, входящих в словарь морфологического анализатора	1 час 17 мин	1 час 12 мин	
Время добавления в индекс слов, не входящих в словарь морфологического анализатора	44 мин	48 мин	
Время записи данных об часто используемых словах	26 мин	23 мин	
Суммарное время добавления данных в индекс	2 часа 27 мин	2 ч 23 мин	

	3. Индексирование набора текстовых документов.

	Как в предыдущем случае, только размер кеща - 2 Гб. Случай 32-битной архитектуры не исследовался.	

	32	64	
Общее время создания индекса	-	7 ч 23 мин	
Распознавание кодировки	-	3 мин 26 сек	
Морфологический анализ	-	52 мин 50 сек	
Чтение файлов	-	3 ч 45 мин	
Создание индекса похожих документов	-	1 ч 27 мин	
Время добавления в индекс слов, входящих в словарь морфологического анализатора	-	1 час 10 мин	
Время добавления в индекс слов, не входящих в словарь морфологического анализатора	-	47 мин	
Время записи данных об часто используемых словах	-	23 мин	
Суммарное время добавления данных в индекс	-	2 ч 20 мин	

  	4. Индексирование файлов в архиве.

	Индексировались файлы в архивах формата rar, без сжатия. Суммарный размер архивов 110 ГБ. Файлы были в различных форматах, в основном текстовые файлы, HTML и RTF. Создавался репозитарий, индекс похожих документов и индекс часто используемых слов. При создании репозитария использовался алгоритм Хаффмана для сжатия данных.
	Суммарный объем индекса 142 Гб, из них 58 Гб - репозитарий.

	32	64	
Общее время создания индекса	9 час 23 мин	9 ч 03 мин	
Распознавание кодировки	4 мин 13 сек	4 мин 06 сек	
Морфологический анализ	53 мин 11 сек	55 мин 43 сек	
Чтение файлов	5 час 39 мин	5 ч 06 мин	
Создание индекса похожих документов	1 час 20 мин	1 ч 28 мин	
Время добавления в индекс слов, входящих в словарь морфологического анализатора	1 час 10 мин	1 час 10 мин	
Время добавления в индекс слов, не входящих в словарь морфологического анализатора	49 мин	54 мин	
Время записи данных об часто используемых словах	24 мин	22 мин	
Суммарное время добавления данных в индекс	2 час 23 мин	2 ч 26 мин	

	Проведенные эксперименты показали, что время работы системы в 32-х битном случае и 64-х битном случае примерно одинаковое. 
	Следует также обратить внимание на эксперименты 3 и 2 которые показывают, что в текущей реализации алгоритмов увеличение размера основного буфера в 2 раза не дает существенного увеличения производительности.

Список литературы

1.	Веретенников А. Б. Создание легко обновляемых текстовых индексов. Электронные библиотеки: перспективные методы и технологии, электронные коллекции: Труды Десятой Всероссийской научной конференции «RCDL'2008». Дубна: ОИЯИ, 2008. с. 149-154.
2.	Веретенников А. Б. Эффективное создание текстовых индексов. Проблемы теоретической и прикладной математики: Труды 39-й Всероссийской молодежной конференции. Екатеринбург: УрО РАН, 2008. с. 348-350.
3.	Веретенников А. Б., Лукач Ю. С. Еще один способ индексации больших массивов текстов. Известия Уральского государственного университета. Серия "Компьютерные науки", 2006, № 43. c. 103-122.
4.	Веретенников А. Б., Лукач Ю. С. CLB-деревья: новый способ индексации больших массивов текстов. Международная алгебраическая конференция: К 100-летию со дня рождения П. Г. Конторовича и 70-летию Л. Н. Шеврина. Тез. докл. Екатеринбург. Изд-во Урал. ун-та, 2005, с. 173-175.
5.	Веретенников А. Б. Эффективная индексация текстовых документов с использованием CLB-деревьев. Системы управления и информационные технологии, 2009,  1.1(35). - С. 134-139.