Что такое сэмпл в программировании

Методы и алгоритмы сэмплинга в анализе данных

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

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

Замечание. Русскоязычным аналогом слова сэмплинг, как известно, является понятие «выборка». Однако здесь возникает неоднозначность: в русском языке выборка может пониматься как выбранное подмножество данных (sample), так и сам процесс его формирования (sampling). Поэтому в дальнейшем для обозначения собственно процесса отбора данных мы будем использовать транслит «сэмплинг», а для обозначения полученного подмножества данных будем использовать слово «выборка».

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

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

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

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

Закономерным является вопрос: почему вместо генеральной совокупности приходится исследовать выборку? Дело в том, что генеральная совокупность — это множество всех объектов (единиц наблюдения) предметной области, относительно которых предполагается обнаруживать закономерности и делать выводы при решении конкретной задачи. Элементами генеральной совокупности являются все объекты, свойства и характеристики которых могут интересовать аналитика. Поэтому использование в анализе выборок обусловлено следующими причинами:

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

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

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

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

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

Рисунок 1. Генеральная совокупность и выборка

Основные этапы построения выборки

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

1. Определение генеральной совокупности. На данном этапе аналитик должен определить из каких объектов будет состоять совокупность (людей, домохозяйств, предприятий, товаров и т.д.), какими признаками они характеризуются, а также произвести географическую и временную привязку. В некоторых случаях может возникнуть ситуация, когда совокупность может содержать наблюдения, которые будут являться следствием наблюдением другой совокупности (суперсовокупности). При этом совокупность и суперсовокупность могут частично перекрываться.
2. Определение основы выборки (sampling frame). В простейшем случае, в выборку может быть включен любой элемент совокупности — это называется прямым отбором. Однако на практике может оказаться полезным сформировать так называемую основу выборки — часть генеральной совокупности, элементы которой удовлетворяют требованиям решаемой задачи. Например, это могут быть люди старше 18 лет, клиенты с доходом выше среднего по региону и т.д. Возможно требование, чтобы каждый элемент совокупности попадал в основу выборки только один раз. Применяется показатель инцидентности (охвата) выборки, равный процентной доле генеральной совокупности, которая будет использоваться для отбора.
3. Выбор метода и алгоритма сэмплинга (план выборки). Этот выбор не всегда очевиден и однозначен. На практике приходится использовать опыт решения аналогичных задач, либо выбирать лучший метод экспериментально. Кроме этого выбранный метод зависит от типа данных и количества объектов.
4. Определение объёма выборки. Зависит от многих факторов. Например, в статистических методах исследования объём выборки должен обеспечивать возможность оценки законов распределения данных и их параметров. В машинном обучении объём обучающей выборки должен обеспечивать её полноту и репрезентативность, а также может зависеть от особенностей модели. Например, число примеров обучающей выборки для обучения нейронной сети должно превышать число межнейронных связей, которые настраиваются в процессе обучения. В противном случает сеть не приобретёт обобщающей способности.
5. Реализация процесса сэмплинга. Также имеет свои особенности. Например отбор наблюдений может производится из локальных или удалённых источников. Во втором случае процесс извлечения выборок больших объёмов может сопровождаться повышением нагрузки на сеть компании. Поэтому его лучше реализовывать в соответствии с наиболее безопасным временным регламентом. Кроме этого в процессе сэмплинга может произойти разрыв соединения, поэтому важно, чтобы после его восстановления процесс можно было продолжить, а не начинать сначала.
6. Сбор данных по отобранным объектам (если это необходимо). В некоторых случаях в процессе сэмплинга отбираются только идентификаторы объектов. Например, клиенты для опроса могут сначала отбираться по номерам клиентских карт, а потом в ходе опроса определяются их пол, возраст, доход и т.д.

Классификация методов сэмплинга

Общепринятая классификация методов сэмплинга представлена на рис. 2.

Рисунок 2. Классификация методов сэмплинга

Все методы сэмплинга делятся на две группы — детерминированные и вероятностные (probability sampling) или случайные (random sampling). В детерминированных методах процесс формирования выборки производится в соответствии с формально заданными правилами и ограничениями. Например «выбрать всех мужчин в возрасте от 30 до 40 лет». Тогда все объекты, удовлетворяющие правилу будут помещены в выборку обязательно. В вероятностных методах для каждого объекта определяется вероятность, с которой он может быть взят в выборку.

Вероятностный (случайный) сэмплинг

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

Случайный сэмплинг имеет три разновидности: простой, стратифицированный и групповой.

Простой случайный сэмплинг (Simple Random Sampling — SRS). В этом методе каждый объект генеральной совокупности имеет равную вероятность быть отобранным в выборку. При этом объекты выбираются из основы выборки произвольным образом и независимо друг от дуга. SRS является самым простым из методов случайного сэмплинга. При этом он может являться частью некоторой более сложной процедуры формирования выборки.

Простейшим способом реализации SRS является следующая последовательность действий:

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

SRS может производится с возвратом или без возврата. В первом случае каждый объект основы выборки может быть извлечён один раз, а во втором может извлекаться повторно. Выборка с возвратом используется, например, для небольшой основы выборки, если количество объектов в ней недостаточно для формирования обучающего множества достаточного объема.

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

Преимуществами SRS являются:

• минимальные знания о генеральной совокупности;
• простота интерпретации результатов.

В настоящее время существует несколько алгоритмов реализации SRS.

Наивный алгоритм. Каждому элементу совокупности устанавливается вероятность быть выбранным 1/N . Затем, выполняется N операций извлечения из совокупности в выборку.

Алгоритм случайной сортировки. Генерируется последовательность чисел из равномерного распределения (0..1) и последовательно присваиваются элементам совокупности в качестве ключа. Затем объекты упорядочиваются по порядку возрастания ключа и из полученного списка выбирается N первых объектов.

Резервуарный алгоритм (reservoir sampling, R-sampling). Используется для формирования простой случайной выборки без замены из k элементов совокупности неизвестного размера N за один проход. Размер совокупности неизвестен алгоритму и обычно слишком велик, чтобы все N элементов поместились в оперативную память.

Алгоритм формирует подмножество из k элементов совокупности, называемое резервуаром. Изначально в него помещаются k первых элементов. Затем элементы перебираются последовательно до тех пор пока не будет достигнут конец ввода. При этом для каждого элемента задаётся индекс i>k . Затем алгоритм генерирует случайное число j , такое, что 1<j<i .

Если j <=k , то элемент выбирается и заменяет собой элемент, который в данный момент занимает j -ю позицию в резервуаре. В противном случае, элемент отбрасывается. Иными словами i -й элемент выбирается в резервуар с вероятностью k/i . Преимущество алгоритма в том, что не требуется знать размер совокупности и он всегда использует один и тот же объём памяти. Недостаток — алгоритм работает достаточно медленно.

Стратифицированный сэмплинг (Stratified sampling). Стратификация — это процесс разделения исходной совокупности на несколько однородных групп (страт) перед процедурой сэмплинга. Тогда стратифицированным называется метод сэмплинга, при котором объекты из каждой страты извлекаются независимо.

Страты должны быть исчерпывающими (т.е. любой объект принадлежит какой-либо страте) и взаимоисключающими (каждый объект может принадлежат к одной и только одной страте). К каждой страте применяется процедура простого случайного сэмплинга.

Рисунок 3. Стратифицированный сэмплинг

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

Пропорциональная. Формирует страты пропорционально доле соответствующих типов объектов в совокупности. Например, если совокупность состоит из n людей, из которых m мужчины и f женщины, то можно сформировать две страты, одна из которых содержит m/n мужчин и f/n женщин.

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

Стратифицированный сэмплинг является наиболее эффективным если выполняются следующие условия:

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

Преимущества стратифицированного сэмплинга:

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

Недостатки стратифицированного сэмплинга:

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

Выборка с вероятностью, пропорциональной размеру (Sampling with Probability Proportional to Size — PSS). Иногда в исходной совокупности присутствует переменная, которая связана с признаком, по которому производится группировка. Такую переменную (её называют переменной размера) можно использовать для повышения точности выборки. Она определяет значимость объекта, от которой зависит вероятность его попадания в выборку.

Например, пусть требуется сформировать выборку клиентов для маркетингового опроса. При этом ожидается, что результаты опроса могут коррелировать с возрастом респондента. Тогда можно выбрать возраст в качестве переменной размера. Для этого разобьём всех клиентов на возрастные категории, скажем, 21-30 лет, 31-40, 41-50 и 51-60. Пусть в первую возрастную категорию попали 500 клиентов, во вторую 700, в третью 1000, а в последнюю 300 (всего 2500 клиентов). Тогда вероятность для клиента из соответствующей категории быть выбранным для опроса составит:

где N — общее число клиентов, N_i — число клиентов i -й категории. Т.е. для клиента второй возрастной категории эта вероятность составит P_i=700/2500=0,28 .

Применение PSS-сэмплинга позволяет сделать выборку более целенаправленной, повысить в ней содержание объектов, которые в наибольшей степени влияют на результаты анализа.

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

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

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

На первый взгляд кластерная выборка похожа на стратифицированную: и в том, и в другом случае извлечение объектов производится из независимых частей исходной совокупности. Но страты (слои) представляют собой подмножества совокупности, сформированные по диапазонам значений некоторого признака, например, возраста клиента. Т.е. клиенты с близким возрастом (например от 30 до 40) окажутся в одной страте.

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

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

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

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

Кластерный сэмплинг делят на три вида: одноэтапный, двухэтапный и многоэтапный.

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

Рисунок 4. Одноэтапный кластерный сэмплинг

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

Рисунок 5. Двухэтапный кластерный сэмплинг

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

Основное приложение кластерного сэмплинга — снижение издержек социальных или маркетинговых исследований в территориально распределённых структурах (поэтому кластерный сэмплинг иногда называют географическим, территориальным или районированным).

Систематический сэмплинг — вид случайного сэмплинга, в котором объекты совокупности выбираются последовательно через случайно определяемый интервал h.

Случайным образом выбирается число h, на которое алгоритм смещается по списку элементов (начиная от 1-го) совокупности и выбирается элемент, определяемый смещением. Затем снова случайно выбирается смещение (отсчитывается от выбранного элемента) и снова выбирается элемент.

Рисунок 6. Систематический сэмплинг

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

Этот метод даёт хороший результат только если исходная совокупность однородная. Если же в ней содержаться какие-либо циклические зависимости, которые могут синхронизироваться с интервалом h , то выборка может получиться нерепрезентативной. Чтобы снизить вероятность такого исхода, возможно случайное перемешивание набора данных, из которого производится выборка.

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

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

Детерминированный сэмплинг

Квотный сэмплинг. Квотный сэмплинг представляет собой детерминированную версию группового, где исходная совокупность также разделяется на непересекающиеся подмножества. Затем выбор объектов производится из каждого подмножества в соответствии с определённой пропорцией (квотой), например 100 мужчин и 200 женщин в возрасте от 30 до 40 лет. Отсутствие вероятностной основы делает выборку ненадёжной.

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

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

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

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

Преимущество удобной выборки:

• высокая скорость получения данных;
• простота реализации;
• доступность данных;
• низкие затраты.

Основным недостатком является отсутствие репрезентативности выборки.

Панельный сэмплинг. Разновидность случайного сэмплинга, в процессе которого выборка формируется несколько раз с определённым временным интервалом. Каждый период формирования панельной выборки называется «волна». Целью является отслеживание изменения бизнес-процессов во времени.

Сэмплинг снежного кома. Сэмплинг снежного кома — вариант детерминированного сэмплинга, в котором сначала формируется небольшое начальное множество объектов. Затем к нему добавляются новые объекты, каким-либо образом связанные с начальными. Затем включаются объекты, связанные с добавленными, и процесс разрастания выборки происходит подобно снежному кому.

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

Рисунок 7. Сэмплинг снежного кома

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

Основная область применения выборки снежного кома — социальные и маркетинговые исследования. Преимущества технологии заключается в следующем:

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

Недостатками метода являются:

• неустойчивость — одна и та же процедура формирования выборки может дать разные результаты;
• объем выборки заранее неизвестен;
• отсутствие контроля за процессом сэмлинга.

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

Рисунок 8. Последовательный сэмплинг

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

Преимуществом метода является простота реализации, а недостатком — отсутствие репрезентативности выборки.

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

Параметром алгоритма является коэффициент N , который определяет во сколько раз нужно увеличить в выборке число наблюдений с заданным значением признака. Например, если изначально число клиентов со значением признака «Возраст» равным 30 в выборке составляло 10, то после применения алгоритма сэмплинга со смещением оно составит 50.

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

Особенности применения сэмплинга

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

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

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

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

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

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

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

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

Сэмплирование и точность вычислений

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

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

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

Проблема

Ключевой вопрос: насколько хорошо сэмпл описывает «генеральную совокупность»? Раз мы берем сэмпл с общего массива, то получаемые нами метрики оказываются случайными величинами. Разные сэмплы дадут нам разные результаты метрик. Разные, не значит любые. Теория вероятности говорит нам, что получаемые сэмплированием значения метрики должны группироваться вокруг истинного значения метрики (сделанного по всей выборке) с определенным уровнем ошибки. При этом у нас часто бывают задачи, где для решения можно обойтись разным уровнем ошибки. Одно дело прикинуть, получаем ли мы конверсию 50% или 10%, а другое дело получить результат с точностью 50.01% vs 50.02%.

Интересно, что с точки зрения теории, наблюдаемый нами коэффициент конверсии по всей выборке — это тоже случайная величина, т.к. «теоретический» коэффициент конверсии можно посчитать только на выборке бесконечного размера. Это означает, что даже все наши наблюдения в БД на самом деле дают оценку конверсии со своей точностью, хотя нам кажется, что вот эти наши подсчитанные цифры абсолютно точны. Это так же приводит к выводу, что даже если сегодня коэффициент конверсии отличается от вчерашнего, то это еще не означает, что у нас что-то поменялось, а лишь означает, что сегодняшний сэмпл (все наблюдения в БД) из генеральной совокупности (все возможные наблюдения за этот день, которые произошли и не произошли) дал несколько иной результат, чем вчерашний. Во всяком случае для любого честного продукта или аналитика это должно быть базовой гипотезой.

Формулировка задачи

Допустим у нас 1 000 000 записей в БД вида 0/1, которые говорят нам о том, случилась ли конверсия по событию. Тогда коэффициент конверсии это просто сумма 1 делить на 1 млн.

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

Теоретические рассуждения

Задача сводится к расчету доверительного интервала коэффициента конверсии по выборке заданного размера для биноминального распределения.

Из теории стандартное отклонение для биноминального распределения это:
S = sqrt(p * (1 — p) /N)

Где
p — коэффициент конверсии
N — Размер выборки
S — стандартное отклонение

Непосредственно доверительный интервал я считать из теории не стану. Там довольно сложный и запутанный матан, который в итоге связывает стандартное отклонение и конечную оценку доверительного интервала.

Давайте разовьем «интуицию» по поводу формулы стандартного отклонения:

1. Чем больше размер сэмпла, тем меньше ошибка. При этом ошибка падает в обратной квадратичной зависимости, т.е. увеличение выборки в 4 раза увеличивает точность лишь в 2 раза. Это означает, что в какой-то момент наращивание размера сэмпла не даст особых преимуществ, а так же означает, что довольно высокую точность можно получить достаточно маленькой выборкой.

1. Есть зависимость ошибки от величины коэффициента конверсии. Относительная ошибка (т.е. отношение ошибки к величине коэффициента конверсии) имеет «мерзкую» тенденции быть тем больше, чем ниже коэффициент конверсии:

1. Как мы видим, ошибка «взлетает» в небеса при низком коэффициенте конверсии. Это означает, что если вы сэмплируете редкие события, то вам нужны большие размеры выборки, иначе вы получите оценку конверсии с очень большой ошибкой.

Моделирование

Мы можем полностью отойти от теоретического решения и решить задачу «в лоб». Благодаря языку R теперь это сделать очень просто. Чтобы ответить на вопрос, в какую мы ошибку получим при сэмплировании, можно просто сделать тысячу сэмплирований и посмотреть, какую ошибку мы получаем.

1. Берем разные коэффициенты конверсии (от 0.01% до 50%).
2. Берем 1000 сэмплов по 10, 100, 1000, 10000, 50000, 100000, 250000, 500000 элементов в выборке
3. Считаем коэффициент конверсии по каждой группе сэмплов (1000 коэффициентов)
4. Строим гистограмму по каждой группе сэмплов и определяем, в каких пределах лежат 60%, 80% и 90% наблюдаемых коэффициентов конверсии.

Код на R генерирующий данные:

В результате мы получаем следующую таблицу (дальше будут графики, но детали лучше видны в таблице).

Коэффициент конверсии	Размер сэмпла	5%	10%	20%	80%	90%	95%
0.0001	10	0	0	0	0	0	0
0.0001	100	0	0	0	0	0	0
0.0001	1000	0	0	0	0	0	0.001
0.0001	10000	0	0	0	0.0002	0.0002	0.0003
0.0001	50000	0.00004	0.00004	0.00006	0.00014	0.00016	0.00018
0.0001	100000	0.00005	0.00006	0.00007	0.00013	0.00014	0.00016
0.0001	250000	0.000072	0.0000796	0.000088	0.00012	0.000128	0.000136
0.0001	500000	0.00008	0.000084	0.000092	0.000114	0.000122	0.000128
0.001	10	0	0	0	0	0	0
0.001	100	0	0	0	0	0	0.01
0.001	1000	0	0	0	0.002	0.002	0.003
0.001	10000	0.0005	0.0006	0.0007	0.0013	0.0014	0.0016
0.001	50000	0.0008	0.000858	0.00092	0.00116	0.00122	0.00126
0.001	100000	0.00087	0.00091	0.00095	0.00112	0.00116	0.0012105
0.001	250000	0.00092	0.000948	0.000972	0.001084	0.001116	0.0011362
0.001	500000	0.000952	0.0009698	0.000988	0.001066	0.001086	0.0011041
0.01	10	0	0	0	0	0	0.1
0.01	100	0	0	0	0.02	0.02	0.03
0.01	1000	0.006	0.006	0.008	0.013	0.014	0.015
0.01	10000	0.0086	0.0089	0.0092	0.0109	0.0114	0.0118
0.01	50000	0.0093	0.0095	0.0097	0.0104	0.0106	0.0108
0.01	100000	0.0095	0.0096	0.0098	0.0103	0.0104	0.0106
0.01	250000	0.0097	0.0098	0.0099	0.0102	0.0103	0.0104
0.01	500000	0.0098	0.0099	0.0099	0.0102	0.0102	0.0103
0.1	10	0	0	0	0.2	0.2	0.3
0.1	100	0.05	0.06	0.07	0.13	0.14	0.15
0.1	1000	0.086	0.0889	0.093	0.108	0.1121	0.117
0.1	10000	0.0954	0.0963	0.0979	0.1028	0.1041	0.1055
0.1	50000	0.098	0.0986	0.0992	0.1014	0.1019	0.1024
0.1	100000	0.0987	0.099	0.0994	0.1011	0.1014	0.1018
0.1	250000	0.0993	0.0995	0.0998	0.1008	0.1011	0.1013
0.1	500000	0.0996	0.0998	0.1	0.1007	0.1009	0.101
0.5	10	0.2	0.3	0.4	0.6	0.7	0.8
0.5	100	0.42	0.44	0.46	0.54	0.56	0.58
0.5	1000	0.473	0.478	0.486	0.513	0.52	0.525
0.5	10000	0.4922	0.4939	0.4959	0.5044	0.5061	0.5078
0.5	50000	0.4962	0.4968	0.4978	0.5018	0.5028	0.5036
0.5	100000	0.4974	0.4979	0.4986	0.5014	0.5021	0.5027
0.5	250000	0.4984	0.4987	0.4992	0.5008	0.5013	0.5017
0.5	500000	0.4988	0.4991	0.4994	0.5006	0.5009	0.5011

Посмотрим случаи с 10% конверсией и с низкой 0.01% конверсией, т.к. на них хорошо видны все особенности работы с сэмплированием.

При 10% конверсии картина выглядит довольно простой:

Точки — это края 5-95% доверительного интервала, т.е. делая сэмпл мы будем в 90% случаев получать CR на выборке внутри этого интервала. Вертикальная шкала — размер сэмпла (шкала логарифмическая), горизонтальная — значение коэффициента конверсии. Вертикальная черта — «истинный» CR.

Мы тут видим то же, что мы видели из теоретической модели: точность растет по мере роста размера сэмпла, при этом одна довольно быстро «сходится» и сэмпл получает результат близкий к «истинному». Всего на 1000 сэмпле мы имеем 8.6% — 11.7%, что для ряда задач будет достаточно. А на 10 тысячах уже 9.5% — 10.55%.

Куда хуже дела обстоят с редкими событиями и это согласуется с теорией:

У низкого коэффициента конверсии в 0.01% принципе проблемы на статистике в 1 млн наблюдений, а с сэмплами ситуация оказывается еще хуже. Ошибка становится просто гигантской. На сэмплах до 10 000 метрика в принципе не валидна. Например, на сэмпле в 10 наблюдений мой генератор просто 1000 раз получил 0 конверсию, поэтому там только 1 точка. На 100 тысячах мы имеем разброс от 0.005% до 0.0016%, т.е мы можем ошибаться почти в половину коэффициента при таком сэмплировании.

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

Сэмплирование

Детальному анализу способов сэмплирования посвящена гл. 3. Сейчас же наша задача состоит лишь в том, чтобы уяснить смысл этого слова.

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

В принципе, сэмпл — это ни что иное, как сохраненная в памяти синтезатора последовательность цифровых отсчетов, получившихся в результате анало-го-цифрового преобразования звука музыкального инструмента. Если бы не существовала проблема экономии памяти, то звучание каждой ноты можно было бы записать в исполнении каждого музыкального инструмента. А игра на таком синтезаторе представляла бы собой воспроизведение этих записей в необходимые моменты времени. Но если идти по такому пути, то пришлось бы хранить в памяти множество вариантов звучания каждой ноты, причем все они должны отличаться протяженностью звучания, динамикой звукоизв-лечения и т. д. На это не хватит никакого объема памяти. Поэтому сэмплы хранятся в памяти не в том виде, в каком они получаются сразу же после прохождения АЦП. Запись подвергается хирургическому воздействию, делится на характерные части [фазы): начало, протяженный участок, завершение звука. В зависимости от применяемой фирменной технологии эти части могут делиться на еще более мелкие фрагменты. В памяти хранится не вся запись, а лишь минимально необходимая для ее восстановления информация о каждом из фрагментов. Изменение протяженности звучания производится за счет управления числом повторений отдельных фрагментов.

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

Для создания и воспроизведения сэмплов служит синтезатор. В наши дни синтезатор конструктивно реализован в одном-двух корпусах микросхем,

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

В звуковых картах находят применение несколько синтезаторов различных фирм. В гл. 3 мы подробно рассмотрим наиболее распространенный в наши дни синтезатор EMU8000. Популярность этого устройства не случайна. Достаточно высокое качество работы сочетается в нем с относительно небольшой ценой. О перспективности EMU8000 свидетельствует тот факт, что для него разработано программное обеспечение, позволяющее не только эксплуатировать готовые сэмплы, но и создавать свои собственные.

Отметим, что наряду с сэмплами, записанными в ПЗУ звуковой карты, в настоящее время стали доступными наборы сэмплов (банки), созданные как в лабораториях фирм, специализирующихся на синтезаторах, так и любителями компьютерной музыки. Эти банки можно найти на многочисленных лазерных дисках и в Internet.

1.2.6. Компрессия и шумоподавление

Рассматривая требования к АЦП и ЦАП звуковой карты, мы уже коснулись двух проблем: борьбы с искажениями и борьбы с шумами. Эти проблемы тесно связаны друг с другом.

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

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

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

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

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

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

Так, например, наиболее распространенная система шумопонижения типа Dolby А позволяет существенно улучшить эффективность магнитных и оптических носителей аналоговых записей и систем связи, служащих для передачи звуковых программ [78]. Система Dolby А основана на принципе компан-дирования, но только для сигналов низкого уровня и раздельно в четырех частотных поддиапазонах. В каждом из поддиапазонов определяется общий уровень частотных составляющих сигнала. Если он оказывается ниже порогового значения, то в процессе записи сигнал усиливается, а при воспроизведении, наоборот,ослабляется.

Система Dolby А базируется на полученном экспериментально так называемом спектральном окне аналоговой ленты. Вид спектрального окна представлен на рис. 1.25.

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

Рис. 1.25. Спектральное окно аналоговой магнитной ленты

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

Поскольку ныне применяются цифровые носители записи, практически свободные от того, что принято называть собственными шумами, изменяются и подходы к шумоподавлению. На первый план теперь выдвигаются ограничения, обусловленные не свойствами материала носителя записи, а особенностями слухового аппарата человека. Новая система шумопонижения Dolby SR, основанная на так называемом принципе наименьшего воздействия, учитывает не только спектральное окно носителя, но и окно слышимости человека, представленное на рис. 1.26.

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

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

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

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

Утешает только то, что звуковой редактор Cool Edit, который будет рассмотрен в гл. 2, в определенной степени позволит снизить зафиксированные в записи искажения. Дело в том, что в нем программно реализованы такие совершенные методы обработки сигнала (в частности сжатия динамического диапазона и шумоподавления), какими располагают далеко не все специализированные электронные устройства. Например, при наличии резких выбросов сигнала, вызванных импульсными помехами или случайными перегрузками микрофона, программа поможет вам заранее обнаружить эти аномалии и либо удалить их, либо плавно изменить уровень сигнала в районе выброса. Вы будете иметь возможность произвольно измененять мышью амплитудную характеристику компрессора динамического диапазона. Участки фонограммы, свободные от записи полезного сигнала, можно будет заменить «абсолютной тишиной». Кроме того, используя алгоритмы спектральных преобразований с целью снижения заметности шумов, вы сможете на практике использовать информацию о спектральных окнах, приведенных на рис. 1.25 и 1.26.

Профилирование со сверхсветовой скоростью: теория и практика. Часть 1

2019-09-17 в 13:58, admin , рубрики: java, linux, Raiffeisenbank, raiffeisenIT, Блог компании Райффайзенбанк, высокая производительность, Программирование

Привет! Из заголовка вы уже поняли, о чём я собираюсь рассказать. Тут будет много хардкора:
мы обсудим Java, С, С++, ассемблер, немного Linux, немного ядра операционной системы. А ещё разберём практический кейс, поэтому статья будет в трёх больших частях (достаточно объёмных).

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

Содержание

Время и средство постижения — профилировщик

С житейской точки зрения, 1 секунда — это очень мало. Но мы-то знаем, что 1 секунда — это целый миллиард наносекунд. И пускай за 1 наносекунду всего лишь исполняется около 4 тактов процессора, за 1 секунду в компьютере выполняется очень много всего, что может улучшить или ухудшить нам жизнь.

Допустим, мы разрабатываем приложение, которое само по себе достаточно критично к быстродействию, а для некоторых фрагментов кода это вообще критично. Эти кусочки исполняются, скажем, сотни микросекунд — достаточно быстро, но они [участки кода] напрямую влияют на успешность нашего приложения и на количество зарабатываемых или теряемых денег. Например,
при отправке ордеров на заключение биржевых сделок задержка в 100 мкс может стоить бирже 1 млн. рублей и более на каждой сделке, которых в день проходит не одна, и не две, и даже не сто.

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

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

Как же нам учесть все эти нюансы и правильно отпрофилировать интересующий метод?

Концептуально, все профилировщики можно разделить на две группы профилировщиков инструментирующие или сэмплирующие. Рассмотрим каждую группу в отдельности.

Инструментирующие профилировщики вносят достаточно большие накладные расходы, потому что они модифицируют наш байт-код и вставляют в него запись таймингов. Отсюда ключевой недостаток таких профилировщиков: они могут существенно влиять на исполняемый код. В результате будет трудно сказать, насколько полученный профиль соответствует поведению на production-серверах: какие-то оптимизации могут работать иначе, какие-то случаются, а какие-то нет. Возможно, в других масштабах времени, — секунды, минуты, часы, — мы получим репрезентативные данные. Но в масштабе 100 мкс сработавшая или не сработавшая оптимизация может привести к тому, что профиль окажется совершенно не репрезентативен. Поэтому давайте присмотримся к другой группе профилировщиков.

Сэмплирующие профилировщики вносят либо минимальные, либо умеренные накладные расходы. Эти инструменты не влияют напрямую на исполняемый код, а их использование требует от вас чуть больше внимания. Поэтому остановимся именно на сэмпиирующих профилировщиках. Давайте посмотрим, какие данные и в каком виде мы будем получать от них.

Как работают сэмплирующие профилировщики?

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

Если мы будем наблюдать за состоянием стека вызовов в момент выполнения этого участка программы и периодически его записывать, то получим информацию в примерно таком виде:

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

В данном примере, метод D.a выполнялся столько же, сколько метод C.ccc, и это в 2 раза больше, чем метод D.b. Однако предположение о равномерности распределения сэмплов может оказаться не совсем верным, и тогда оценка времени выполнения будет некорректной.

С какой частотой нам нужно сэмплировать?

Допустим, мы хотим за 100 мкс взять 1000 сэмплов, чтобы понять, что там внутри исполнялось. Далее простой пропорцией вычисляем, что если нам нужно делать 1000 сэмплов в 100мкс, то это 10 млн. сэмплов за 1 секунду или 10.000.000 сэмплов/с.

Если мы будем сэмплировать на такой скорости, то за одно исполнение кода мы соберём 1000 сэмплов, агрегируем и поймём, что работало быстро или медленно. После этого будем анализировать производительность и корректировать код.

Однако частота 10 млн. сэмплов в секунду — это много. А если нам не удастся добиться такой скорости профилирования с самого начала? Допустим, мы собрали за 100 мкс всего лишь 10 сэмплов, а не 1000. В таком случае нам остается подождать следующего исполнения профилируемого кода, которое произойдет через 1 секунду (ведь профилируемый код выполняется раз в секунду). Так мы наберем ещё 10 сэмплов. Поскольку они у нас равномерно распределены, их можно объединять в общий набор. Достаточно подождать, пока профилируемый код исполнится 1000/10 = 100 раз, и мы наберём необходимые 1000 сэмплов (по 10 сэмплов каждый из 100 раз).

Выбираем профилировщик

Вооружившись этими теоретическими знаниями, давайте перейдём к практике.

Возьмём Async-profiler. Отличный инструмент (использует вызов виртуальной машины AsyncGetCallTrace), который собирает стек вызовов с точностью до инструкции байт кода виртуальной машины Java. Штатная частота сэмплирования async-profiler’а — 1000 сэмплов в секунду.

Решим простую пропорцию: 10.000.000сэмплов/сек — 1 секунда, 1000сэмплов/с — Х секунд.
Мы получим, что на штатной частоте сэмплирования async-profiler’а профилирование займет около 3 часов. Это долго. В идеале хочется собирать профиль максимально быстро, прямо-таки со сверхсветовой скоростью.

Попробуем разогнать Async-profiler. Для этого в readme находим флаг -i , который задаёт интервал сбора сэмплов. Попробуем установить флаг -i1 (1 наносекунда), или вообще -i0 , чтобы профилировщик сэмплировал без остановки. У меня получилась частота около 2,5 тыс. сэмплов в секунду. В этом случае суммарная длительность профилирования составит порядка 1 часа. Конечно, не 3 часа, но и не особо быстро. Кажется, чтобы достичь требуемых скоростей профилирования нужно сделать что-то качественно другое, выйти на новый уровень.

Чтобы достичь существенно больших частот, придётся отказаться от вызова AsyncGetCallTrace и воспользоваться perf — штатным профилировщиком Linux, который есть в каждом дистрибутиве Linux’а. Однако perf ничего не знает про Java, и нам еще предстоит обучить perf работать с Java. А пока попробуем запустить perf вот таким страшным образом:

• perf record означает, что мы хотим записать профиль.
• Флаг -F и аргумент 10 000 — это частота сэмплирования.
• Флаг -p говорит о том, что мы хотим профилировать только конкретный PID нашего Java-процесса.
• Флаг -g отвечает за сбор стеков вызовов.
• Наконец, с помощью sleep 1 мы ограничиваем запись профиля 1 секундой.

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

Учим perf собирать профиль Java-приложения

Выполним команду perf record …, подождем 1 секунду и запустим perf script, чтобы посмотреть, что же напрофилировалось? И увидим что-то не очень понятное:

Вроде бы это адреса, но нет имён Java-методов. Значит, нужно научить perf сопоставлять эти адреса с названиями методов.

В мире С и С++ для сопоставления адресов и имен функций используется так называемая отладочная информация. В специальной секции исполняемого файла хранится соответствие: по таким-то адресам лежит один метод, по другим адресам — другой метод. Perf эту информацию подтягивает и делает сопоставление.

Очевидно, что JIT-компилятор виртуальной машины не генерирует отладочную информацию в таком формате. Нам остается другой способ — записать данные о соответствии адресов и имен методов в специальный perf-map файл, который perf будет трактовать как дополнение к прочитанной отладочной информации. Этот perf-map файл должен лежать в папке tmp и иметь такую структуру данных:

Адрес начала кода метода	Длина кода	Имя метода
7f99a911d600	120	java.util.AbstractCollection.<init>
7f99a911d9c0	180	java.util.AbstractList.<init>
7f99a911de80	5c0	java.util.Arrays.copyOf
7f99a911ed40	140	java.util.ArrayList$Itr.hasNext
7f99a911f200	3e0	java.util.ArrayList$Itr.next

Первая колонка — это адрес начала кода метода, вторая — его длина, третья колонка — имя метода.

Итак, нам нужно сгенерировать подобный файл. Очевидно, что сделать это вручную не получится (откуда мы знаем, по каким адреcам JIT-компилятор разместит код), поэтому воспользуемся скриптом create-java-perf-map.sh из проекта perf-map-agent, передав ему PID нашего Java-процесса. Файл готов, проверяем его содержимое, ещё раз запускаем perf-script.

Вуаля! Мы видим имена java-методов! Что же только что произошло: мы научили профилировщик perf, который ничего не знает про Java, профилировать обычное Java-приложение и видеть горячие java-методы этого приложения!

Однако для анализа производительности интерсующего нас куска программы нам не хватает call-stack’а, чтобы отфильтровать интересующие данные от всех собранных сэмплов.

Как получить стек вызовов?

Теперь нужно ещё что-то сделать с perf или виртуальной машиной, чтобы получить стеки вызовов. Чтобы понять, что же нужно сделать, давайте сделаем шаг назад и посмотрим, как вообще работает стек. Представим, что у нас есть три функции f1, f2, f3. Причем f1 вызывает f2, а f2 вызывает f3.

В момент исполнения функции f3 посмотрим, в каком состоянии находится стек. Мы видим регистр rsp , который указывает на вершину стека. Также мы знаем, что в стеке есть адрес предыдущего стекового кадра. А как можно получить call-stack?

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

Что же нам для этого нужно? Нам нужен дополнительный регистр rbp, который будет указывать на желтую область. Получается, что регистр rbp позволяет perf получить стек вызовов, понять последовательность, которая нас привела в текущую точку. Подробнее эти детали рекомендую прочитать в System V Application Binary Interface. Там описано, как происходит вызов методов в Linux.

Мы поняли, в чем наша проблема. Нам нужно заставить виртуальную машину использовать регистр rbp по его изначальному назначению — в качестве указателя на начало стекового кадра. Именно так JIT-компилятор должен использовать регистр rbp. Для этого в вирутальной машине есть флажок PreserveFramePointer. Когда мы передадим виртуальной машине этот флаг, то виртуальная машина начнет использовать регистр rbp по его традиционному назначению. И тогда Perf сможет раскрутить стек. И мы получим в профиле настоящий колл-стек. Флажок был законтрибьючен небезызвестным Бренданом Греггом всего лишь в JDK8u60.

Запускаем виртуальную машину с новым флагом. Выполняем create-java-perf-map , затем perf record и perf script . Теперь мы умеем собирать точный профиль со стеками вызовов:

Мы научили профилировщик perf, входящий в комплект большинства дистрибутивов Linux, работать с Java-приложениями. Поэтому теперь мы можем видеть не только горячие участки кода, но и ту последовательность вызовов, которая привела к текущему горячему месту. Отличное достижение, если учесть, что профилировщик perf ничего не знает про java. Всему этому мы только что научили perf!

Увеличиваем частоту сэмплирования perf’а

Попробуем разогнать perf до 10 млн сэмплов в секунду. Сейчас у нас частота существенно меньше.

Чтобы автоматизировать все задачи, которые мы только что делали, можно воспользоваться скриптом perf-java-record-stack из проекта perf-map-agent. У него есть замечательная ручка — переменная окружения perf_record-freq , с помощью которой можно задать частоту сэмплирования. Сначала зададим 100 тыс. сэмплов в секунду и попробуем запустить. В консоли появляется грозное сообщение, что мы превысили максимально дозволенную частоту сэмплирования:

В моем случае лимит был в 30 тыс. сэмплов в секунду. Perf сразу говорит, какой аргумент ядра нужно поправить, что мы и сделаем либо с помощью echo sudo tee в нужный файл, либо напрямую через sysctl . Так:

Сейчас мы говорим ядру, что верхний предел частоты теперь 1 млн. сэмплов в секунду. Запускаем профилировщик ещё раз и указываем частоту 200 тыс. сэмплов в секунду. Профилировщик проработает 15 секунд и выдаст нам 1 млн. сэмплов. Вроде бы всё хорошо. По крайней мере никаких грозных сообщений об ошибках. Но какую же частоту мы получили на самом деле? Оказывается, всего лишь 70 тыс. сэмплов в секунду. Что же пошло не так?

Давайте посмотрим вывод команды dmesg :

Это вывод ядра ОС Linux. Оно поняло, что мы сэмплируем слишком часто, и это занимает слишком много времени, поэтому ядро понижает частоту. Получается, нам нужно выкрутить ещё одну ручку в ядре — она называется kernel.perf_cpu_time_max_percent и регулирует количество времени, которое ядро может тратить на прерывания от perf.

Закажем частоту сэмплирования 200 тыс. сэмплов в секунду. И через 15 секунд мы получаем 3 млн. сэмплов — 200 тыс. сэмплов в секунду.

Теперь посмотрим профиль. Запускаем perf script :

Видим странные функции и исполняемый модуль vmlinux — ядро Linux. Это точно не наш код. Что же произошло? Частота оказалась настолько большой, что в сэмплы начал попадать код ядра. То есть чем выше мы будем поднимать частоту, тем больше будет сэмплов, которые относятся не к нашему коду, а к ядру Linux.

Используем (явно) аппаратные события PMU/PEBS

Тогда я решил попробовать воспользоваться аппаратной технологией PMU/PEBS — Performance Monitoring Unit, Precise Event Based Sampling. Она позволяет получать уведомления о том, что какое-то событие произошло заданное количество раз. Это называется «период». Например, мы можем получать уведомления об исполнении процессором каждой 20-й инструкции. Давайте посмотрим это на примере. Пусть сейчас исполняется инструкция xor, а PMU-счётчик получает значение 18; затем идёт инструкция mov — счётчик равен 19; и следующую инструкцию, add %r14, %r13, PMU будет показывать как «горячую».

Дальше начинается новый цикл: исполняется inc — PMU сбрасывается до 1. Проходит ещё несколько итераций цикла. В итоге мы останавливаемся на инструкции mov , PMU отщелкивает 19. Следующая инструкция add, и опять мы помечаем её как «горячую». Смотрим листинг:

Не замечаете странностей? Цикл из пяти инструкций, но каждый раз мы помечаем одну и ту же инструкцию как горячую. Очевидно, что это неправда: все инструкции «горячие». На них тоже тратится время, а мы помечаем только одну. Дело в том, что у нас между периодом и счетчиком количества инструкций в итерации есть общий делитель 4. Получается, каждую четвёртую итерацию мы будем помечать одну и ту же инструкцию как «горячую». Чтобы избежать такого поведения, нужно в качестве периода выбирать такое число, при котором минимизируется вероятность появления общего делителя между количеством итераций в цикле и самим счётчиком. В идеале период должен быть простым числом, т.е. делиться только на себя и на единицу. Для примера выше: следовало бы выбрать период равный 23. Тогда бы мы поровну помечали все инструкции в этом цикле как «горячие».

Технология PMU/PEBS поддерживается в современном виде как минимум с 2009 года, то есть она есть почти на любых компьютерах. Чтобы применить ее явно, давайте модифицируем скрипт perf-java-record-stack . Заменим флаг -F на -e , который явным образом задаёт использование PMU/PEBS.

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

Запустили модифицированный скрипт perf-java-record-stack и за 15 секунд получили 4,5 млн. сэмплов — это почти 300 тыс. в секунду, по одному сэмплу каждые 3 мкс. То есть за одно исполнение нашего профилированного кода, за 100 мкс мы будем набирать 33 сэмпла. При такой частоте общая длительность сбора профиля составит всего лишь 30 секунд. Даже чашку кофе не выпить! В реальности же всё немного сложнее. Что будет, если наш код станет исполняться не раз в секунду, а раз в 5 секунд? Тогда длительность профилирования вырастет до 2,5 минут, что тоже вполне достойный результат.

Итак, за 30 секунд можно получить профиль, который полностью покроет все наши потребности в исследовании. Победа?

Но меня не покидало ощущение какого-то подвоха. Вернемся к ситуации, при которой наш код исполняется раз в 5 секунд. Тогда профилирование займёт 150 секунд, за это время мы соберем около 45 млн. сэмплов. Из них нам нужны лишь 1000, то есть 0,002 % собранных данных. Всё остальное — мусор, который замедляет работу других инструментов и добавляет накладные расходы. Да, задача решена, но решена в лоб, грязно, тупой силой.

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

Короткое резюме:

• Чтобы собрать профиль Java-приложения с помощью perf’а необходимо сгенерировать файл с информацией о символах с помощью скриптов из проекта perf-map-agent
• Чтобы собирать информацию не только про горячие участки кода, но и стеки, нужно запускать виртуальную машину с флагом -XX:+PreserveFramePointer
• Если хочется увеличить частоту сэмплирования, стоит обратить внимание на sysctl’и kernel.perf_cpu_time_max_percent и kernel.perf_event_max_sample_rate.
• Если в профиль начали попадать сэмплы из ядра, не относящиеся к приложению, стоит задуматься о явном указании периода PMU/PEBS.

Эта статья (и последующие её части) является расшифровкой доклада, адаптированного в текстовом виде. Если хочется не только прочитать, но и послушать про профилирование, ссылочка на выступление.