Слияние кода завершено, страница обновится автоматически
Сравнение скорости поиска CQEngine с двумя типами итераций: наивной и оптимизированной, которые обсуждались ранее здесь.
Для тех, кто не знаком с микротестами, имейте в виду, что результаты ниже полезны только для сравнения относительной задержки подходов (и даже тогда с оговорками), а абсолютная задержка, вероятно, будет выше в производственных средах: Мифы, ложь и микротесты
Тестирование основано на примере онлайн-автодилера. У дилера есть веб-сайт с каталогом из 100 000 автомобилей. Таким образом, у него есть коллекция из 100 000 объектов Car. Сайту необходимо извлекать автомобили, соответствующие критериям, заданным в запросах.
В рамках теста проводится несколько отдельных тестов, которые имитируют поиск автомобилей на основе различных запросов и с использованием различных индексов CQEngine. Эти тесты измеряют время поиска (или задержку) для одного и того же запроса с использованием наивной итерации, оптимизированной итерации и CQEngine.
Тесты также измеряют задержку «Статистики CQEngine», которая относится к скорости, с которой CQEngine может подсчитать количество объектов, соответствующих запросу, используя ускоренный метод ResultSet.size(). Этот метод может быстро определить количество объектов по статистике, содержащейся в индексах в некоторых, но не во всех тестовых случаях.
Класс Car (источник) (http://github.com/npgall/cqengine/blob/master/code/src/test/java/com/googlecode/cqengine/testutil/Car.java) — это простой неизменяемый объект с атрибутами CQEngine, определёнными для его полей: carId, manufacturer, model, color, doors, price.
Класс CarFactory (источник) (http://github.com/npgall/cqengine/blob/master/code/src/test/java/com/googlecode/cqengine/testutil/CarFactory.java) содержит метод, который генерирует коллекцию автомобилей любого заданного размера. Метод создаёт коллекцию из набора из 10 шаблонов. Первый автомобиль — Ford Focus, второй — Ford Fusion и так далее. Метод присваивает уникальный монотонно возрастающий carId каждому автомобилю, который он создаёт. Когда запрашивается более 10 автомобилей, метод начинает снова проходить через шаблоны. Поэтому автомобиль 0 и автомобиль 10 — оба Ford Focus, автомобиль 1 и автомобиль 11 — оба Ford Fusion и т. д.
Таким образом, некоторые статистические данные о составе коллекции автомобилей:
| Цвет | % автомобилей | Производитель | % автомобилей | Количество дверей | % автомобилей |
|---|---|---|---|---|---|
| Красный | 30% | Ford | 30% | 5 | 50% |
| Зелёный | 30% | Honda | 30% | 4 | 20% |
| Синий | 20% | Toyota | 30% | 3 | 20% |
| Чёрный | 10% | BMW | 10% | 2 | 10% |
| Белый | 10% |
Учитывая, что тест создаёт коллекцию из 100 000 автомобилей, например: 30 000 из этих автомобилей будут произведены Ford, и 10 000 автомобилей будут конкретно моделью Ford Focus, равномерно распределённой по всей коллекции.
Тест проводился на машине Apple с процессором Intel Core i7 1,8 ГГц, работающей под управлением OS X 10.7.4 и Java 1.6.0_26. Все тесты проводились по 10 000 раз в качестве прогрева, прежде чем снова запустить их по 10 000 раз для измерения. Перед каждым измерением выполнялась сборка мусора. Исходный код логики тестовой среды можно найти здесь и здесь. Исходный код индивидуальных тестов упоминается в каждом тесте ниже.
Исходный вывод теста с разделением табуляцией доступен как... Таблица результатов
Поскольку CQEngine использует ленивую оценку, он почти сразу возвращает ResultSet для каждого запроса. Для измерения производительности CQEngine эти тесты получают ResultSet от CQEngine, а затем перебирают все автомобили в наборе результатов, просто подсчитывая количество результатов. Как обсуждалось в некоторых примерах ниже, маловероятно, что реальное приложение будет делать это, и поэтому это несколько жёстко для CQEngine, преуменьшая его преимущества. Однако это кажется единственным способом сравнить производительность с итерацией на равных условиях в этом сценарии микротеста.
CQEngine является базовым в этих результатах, и обратите внимание на использование «быстрее» вместо «так же быстро, как». Если результат говорит, что CQEngine на 1600% быстрее, чем итерация, это означает, что CQEngine может обработать на 1700%, или в 17 раз больше запросов за единицу времени, чем итерация (это 1700%, то есть в 17 раз быстрее).
Тест однопоточный для измерения задержки, а не пропускной способности, поэтому используется только одно из ядер процессора 1,8 ГГц. Многопоточный доступ, который поддерживает CQEngine, даст значительно более высокую пропускную способность, и, таким образом, показатели пропускной способности значительно занижены в (до) количества ядер.
Получение одного объекта Car из коллекции на основе Car.carId со значением 500, которое однозначно идентифицирует автомобиль. UniqueIndex на Car.CAR_ID.
Этот пример демонстрирует поддержку CQEngine для постоянного времени извлечения независимо от размера коллекции.
Результаты теста
Извлечение и повторение объектов Car из коллекции на основе Car.manufacturer со значением «Ford». HashIndex на Car.MANUFACTURER.
Этот запрос соответствует 30 000 автомобилей; 30% коллекции из 100 000 автомобилей. Этот тест заставляет CQEngine перебирать все 30 000 автомобилей, хотя большинству приложений не потребуется так много результатов. Напротив, подходы к итерации могут потребовать повторения всей коллекции, поскольку совпадающие результаты могут быть расположены ближе к концу коллекции. CQEngine ResultSets намеренно поддерживают постраничную навигацию по результатам, и благодаря ленивой оценке, если приложение прекращает итерацию, никакие ненужные вычисления не будут выполнены. Тем не менее этот пример призван продемонстрировать производительность CQEngine при запросе и обработке большой части коллекции.
Результаты теста
1256 запросов в секунду (на одном ядре процессора 1,8 ГГц).
795,942 микросекунды на запрос.
CQEngine в 423,17% быстрее, чем наивная итерация.
CQEngine в 241,83% быстрее, чем оптимизированная итерация. Результаты бенчмарка
4 341 запросов в секунду (на одном ядре процессора с тактовой частотой 1,8 ГГц);
230,361 микросекунды на запрос;
CQEngine быстрее наивной итерации на 1 627,06 %;
CQEngine быстрее оптимизированной итерации на 1 324,17 %.
Извлечение и итерация объектов Car из коллекции на основе того, что Car.price больше или равен 3 000,00 и меньше 4 000,00. NavigableIndex по Car.PRICE.
Этот запрос соответствует 20 000 автомобилей; 20 % от коллекции из 100 000 машин.
between(Car.PRICE, 3000.0, true, 4000.0, false).
SELECT * FROM cars WHERE price >= 3000.0 AND price < 4000.0.Результаты бенчмарка:
Извлечение и итерация объектов Car из коллекции на основе того, что Car.model начинается с «P». RadixTreeIndex по Car.model.
Этот запрос соответствует 10 000 автомобилей; 10 % от коллекции из 100 000 машин. Обратите внимание: также см. ReversedRadixTreeIndex, который поддерживает запросы типа «заканчивается на». Он будет иметь идентичные характеристики производительности, как этот RadixTreeIndex, поэтому его не тестировали отдельно.
startsWith(Car.MODEL, "P").SELECT * FROM cars WHERE model LIKE 'P%'.Результаты бенчмарка:
Извлечение и итерация объектов Car из коллекции на основе того, что Car.model содержит «g». SuffixTreeIndex по Car.model.
Этот запрос соответствует 10 000 автомобилей; 10 % от коллекции из 100 000 машин.
contains(Car.MODEL, "g").SELECT * FROM cars WHERE model LIKE '%g%'.Результаты бенчмарка:
Извлечение и итерация объектов Car из коллекции на основе того, что Car.model имеет значение «Focus». Без индексов.
В этом примере демонстрируется неправильно настроенное приложение, которое не добавило никаких индексов. CQEngine может обрабатывать любой запрос, но без подходящих индексов это не позволяет ускорить запрос, и он может работать хуже итерации. Приложения должны убедиться, что они добавили подходящие индексы. Запрос соответствует 10 000 автомобилей; 10% от коллекции из 100 000 машин.
Результаты тестов:
Извлекаем и перебираем объекты Car из коллекции на основе следующих условий:
Индекс HashIndex для Car.DOORS. Индексов для Manufacturer или Color нет.
Этот пример демонстрирует обработку запросов CQEngine, для которых оптимальные индексы не существуют. Идеальная конфигурация для этого типа запросов должна иметь CompoundIndex для трёх полей выше, чтобы обеспечить постоянное время извлечения. Однако в этом случае был добавлен только HashIndex для Car.DOORS. CQEngine максимально использует доступные индексы. В этом случае он использует индекс Car.DOORS, чтобы уменьшить набор кандидатов с 100 000 до 20 000 автомобилей, а затем перебирает набор кандидатов, применяя фильтрацию «на лету», чтобы вернуть только те автомобили, которые соответствуют остальной части запроса. Этот запрос в конечном итоге соответствует 10 000 автомобилям; 10 % от коллекции из 100 000 автомобилей.
Обратите внимание, что получение статистики CQEngine в этом примере происходит медленнее, чем в других. Статистика CQEngine относится к вызову resultSet.size() для ResultSet, возвращаемого CQEngine, вместо определения размера путём фактического перебора и подсчёта результатов.
CQEngine часто может рассчитать, сколько объектов будет соответствовать запросу, фактически не перебирая никакие объекты, на основе внутренних подсчётов, доступных в записях внутри индексов. В этом примере, поскольку индексы недоступны для предоставления полной статистики, CQEngine возвращается к подсчёту объектов, применяя фильтрацию «на лету» к набору кандидатов, что влечёт за собой более высокие затраты.
Метод resultSet.contains() также можно ускорить аналогичным образом (применяя тесты на принадлежность множеству к отдельным множествам внутри индексов). В этом примере этот метод будет затронут аналогичным образом, внутренне возвращаясь к фильтрации «на лету» набора кандидатов.
Запрос CQEngine:
and(
equal(Car.MANUFACTURER, "Toyota"),
equal(Car.COLOR, Car.Color.BLUE),
equal(Car.DOORS, 3)
)
SQL-эквивалент:
SELECT * FROM cars
WHERE
manufacturer = 'Toyota'
AND color = 'blue'
AND doors = 3
Исходный код: здесь (http://github.com/npgall/cqengine/blob/master/code/src/test/java/com/googlecode/cqengine/benchmark/tasks/NonOptimalIndexes_ManufacturerToyotaColorBlueDoorsThree.java).
Результаты тестов:
Перебираем объекты Car из коллекции на основе следующих условий:
Этот пример показывает улучшение производительности при добавлении оптимального индекса для того же запроса, что и в примере с неоптимальными индексами выше. Этот запрос соответствует 10 000 автомобилей; 10 % от коллекции из 100 000 автомобилей. Результаты бенчмарка
StandingQueryIndex: извлечение автомобилей марки Toyota синего цвета с количеством дверей не равным пяти
Извлечение и итерация объектов Car из коллекции на основе значения Car.manufacturer, равного «Toyota», значения Car.color, равного Car.Color.BLUE, и значения Car.doors, не равного 5.
Пример демонстрирует StandingQueryIndex. Этот тип индекса поддерживает набор объектов, соответствующих запросу или фрагменту запроса. По мере добавления и удаления объектов из коллекции он проверяет объекты, чтобы определить, соответствуют ли они запросу, добавляя их в этот набор или удаляя их из него по мере необходимости. Когда CQEngine видит запрос или фрагмент запроса, для которого существует индекс StandingQueryIndex, он может извлекать соответствующие объекты для этого запроса или фрагмента запроса со сложностью O(1). Этот запрос соответствует 10 000 автомобилей; 10 % от коллекции из 100 000 автомобилей.
and(
equal(Car.MANUFACTURER, "Toyota"),
equal(Car.COLOR, Car.Color.BLUE),
not(equal(Car.DOORS, 5))
)
SELECT * FROM cars
WHERE
manufacturer = 'Toyota'
AND color = 'blue'
AND doors <> 3
Результаты бенчмарка
Quantized HashIndex: получение по уникальному ключу
Получение одного объекта Car из коллекции на основе уникального идентификатора автомобиля Car.carId, равного 500. Квантованный HashIndex на Car.CAR_ID с коэффициентом сжатия 5.
Этот пример демонстрирует эффект квантования индексов. Квантование позволяет контролировать детализацию индексов. В этом примере индекс был создан с помощью IntegerQuantizer с коэффициентом сжатия 5. Это означает, что каждые 5 последовательных carId будут сгруппированы вместе и сохранены как одна запись в индексе. Это уменьшает размер индекса (снижает нагрузку на память) и вместо этого обменивает его на немного более высокую загрузку ЦП во время извлечения. Индекс должен будет фильтровать результаты, полученные из записи на лету, чтобы убедиться, что они действительно соответствуют запросу.
equal(Car.CAR_ID, 501).SELECT * FROM cars WHERE carId = 501.Результаты бенчмарка
Квантованный NavigableIndex: получение CarId в диапазоне
Получение трёх объектов Car из коллекции на основе идентификаторов автомобилей Car.carId в диапазоне от 500 до 502. Квантованный NavigableIndex на Car.CAR_ID с коэффициентом сжатия 5.
Этот пример показывает, что квантование можно применять к навигационным индексам с минимальными накладными расходами при запросах типа range. CQEngine применяет фильтрацию на лету. Фильтрация только квантованных записей в начале и/или конце диапазонов
between(Car.CAR_ID, 500, 502)
SELECT * FROM cars WHERE carId BETWEEN 500 AND 502
Результаты бенчмарка
В предыдущих тестах измерялась производительность CQEngine при извлечении объектов. В этом разделе оценивается скорость и накладные расходы при построении индексов для объектов.
Исходный код для этих тестов можно найти здесь. Оригинальный вывод из теста доступен в виде таблицы здесь.
Тест проводился по той же методике, что обсуждалась в разделе методологии, на том же компьютере Apple с процессором 1,8 ГГц.
Тест выполнялся со сборкой из 100 000 объектов автомобилей, измеряя время, затраченное на построение следующих типов индексов для коллекции.
Обычно накладные расходы на индексирование всей коллекции возникают только тогда, когда объекты добавляются в IndexedCollection массово. Впоследствии объекты могут быть добавлены в IndexedCollection и удалены из неё напрямую, так что возникают только накладные расходы для каждого объекта.
Следует отметить, что если все индексы добавляются в IndexedCollection до добавления объектов массово, то все индексы будут построены за один проход; таким образом, если несколько индексов добавляются заранее, накладные расходы будут меньше суммы указанных.
Результаты
| Индекс | Микросекунды для индексации коллекции из 100 000 объектов | Микросекунды на объект | Количество вставок в секунду (одно ядро 1,8 ГГц) |
|---|---|---|---|
UniqueIndex на CarId |
24 032,8 | 0,24 | 4 166 667 |
HashIndex на CarId |
874 702,26 | 8,747 | 114 324 |
Квантованный HashIndex на CarId (коэффициент сжатия 10) |
85 204,84 | 0,852 | 1 173 709 |
HashIndex на Manufacturer |
28 487,08 | 0,284 | 3 521 127 |
HashIndex на Model |
27 310,68 | 0,273 | 3 663 004 |
CompoundIndex на Manufacturer, Color, Doors |
109 761,58 | 1,097 | 911 577 |
NavigableIndex на Price |
30 393,94 | 0,303 | 3 300 330 |
RadixTreeIndex на Model |
58 100,02 | 0,581 | 1 721 170 |
SuffixTreeIndex на Model |
27 386,04 | 0,273 | 3 663 004 |
Выводы
Вы можете оставить комментарий после Вход в систему
Неприемлемый контент может быть отображен здесь и не будет показан на странице. Вы можете проверить и изменить его с помощью соответствующей функции редактирования.
Если вы подтверждаете, что содержание не содержит непристойной лексики/перенаправления на рекламу/насилия/вульгарной порнографии/нарушений/пиратства/ложного/незначительного или незаконного контента, связанного с национальными законами и предписаниями, вы можете нажать «Отправить» для подачи апелляции, и мы обработаем ее как можно скорее.
Опубликовать ( 0 )