Comments 47
По поводу интринсиков: они будут работать, только если есть поддержка в процессоре. Если запустить этот код на процессоре, где инструкция не поддерживается, получите падение процесса с illegal instruction.
По-хорошему, надо проверять доступность инструкции и делать fallback на код, который сделает то же самое на более базовом наборе инструкций.
По-хорошему, надо проверять доступность инструкции и делать fallback на код, который сделает то же самое на более базовом наборе инструкций.
Знаю. Согласен. Спасибо. Сам писал про интринсики в .net core 3.0 статью. Но тут я решил упростить всё. В конце статьи тоже написано, что нет и обработки ошибок, и проверок. банально всё упадёт, если групп тегов меньше 50.
Если я правильно трактую документацию Intel и википедию, то _mm_popcnt_u32 была представлена в наборе команд SSE 4.2 в 2007 году и ныне поддерживается большинством процессоров. Так что в современных условиях проверка, конечно, с точки зрения логики важна, но несколько избыточна.
Хотя при работе с интринсиками в первую очередь стоит ориентироваться на примерные характеристики целевого устройства (или набора устройств).
Хотя при работе с интринсиками в первую очередь стоит ориентироваться на примерные характеристики целевого устройства (или набора устройств).
Но упомянуть про проверку всё-таки стоило. Ничего плохого в этом нет.
Не могу не согласится, ибо у самого были случаи, когда находился пара пользователей с крайне специфичным железом :)
В данном вопросе больше ориентировался на предположение, что данный код будет исполняться на сервере.
Да. На сервере.
На самом деле когда я писал это всё для коллеги, он думал гонять на большой фреймворке 4.7 и я туда никакие popcnt не вписывал. Потом показал ему, что на .netcore можно быстрее и он задумался о переезде или хотя бы отпочковывании некоторых функций на .netcore в отдельную библиотеку. Но по-моему там до сих пор ничего не решилось.
На самом деле когда я писал это всё для коллеги, он думал гонять на большой фреймворке 4.7 и я туда никакие popcnt не вписывал. Потом показал ему, что на .netcore можно быстрее и он задумался о переезде или хотя бы отпочковывании некоторых функций на .netcore в отдельную библиотеку. Но по-моему там до сих пор ничего не решилось.
Прошу прощения, забыл про такую хитрую штуку (слышал о ней от разработчика из Microsoft, смотрел запись его выступления на dotnext), а именно — компилятор сам резолвит данное условное выражение в зависимости от таргета и подставляет соответствующий код. Так что здесь проверка абсолютно никакого оверхеда иметь не будет, но при этом будет полезной.
Интересно было бы сравнить различные варианты fallback-ов на больших данных.
Интересно было бы сравнить различные варианты fallback-ов на больших данных.
Про это видео: www.youtube.com/watch?v=n3-j_sTtGb0? Да, вы правы. Я совсем забыл про то, что JIT может вырубить эти проверки.
Так-то оно так, но есть нюанс. Запустят вашу сборку на каком-нибудь RaspberryPI на ARM, и оно кааак… Ну или на армовом сервере. Или ещё какую экзотику из коробки достанут.
Мне кажиться что на SQL ету задачу можно решить и попроще, и точно будет не медленнее.
Ведь дание точно есть в базе.
Ведь дание точно есть в базе.
Предложите решение я с интересом его рассмотрю.
Мне почему-то тоже кажется, что словарь тезаурусов на SQL будет выполнять такой поиск за 1 запрос, к тому же, позволит группировать похожие по смыслу тэги как синонимичную связь.
Но создание словаря и групп — ручная и рутинная работа + лишняя возня с классификацией видео (т.к. метаданные каждого видео нужно обработать, положить в бд и классифицировать ранее не встречавшиеся теги по группам и типам связей)
Думаю, для миллиона видео это может быть overkill.
PS зато, добавив немного других типов тезаурусов, можно очень быстро реализовывать функционал «максимально непохожее видео» — все связи омонимы, «частично похожее видео» и просто поиск по нескольким тэгам.
Но создание словаря и групп — ручная и рутинная работа + лишняя возня с классификацией видео (т.к. метаданные каждого видео нужно обработать, положить в бд и классифицировать ранее не встречавшиеся теги по группам и типам связей)
Думаю, для миллиона видео это может быть overkill.
PS зато, добавив немного других типов тезаурусов, можно очень быстро реализовывать функционал «максимально непохожее видео» — все связи омонимы, «частично похожее видео» и просто поиск по нескольким тэгам.
количество бит можно еще считать так:
сложность будет O от количества единичных бит
можно было бы посмотреть на результат с таким подсчетом
int CountOfBits(int a)
{
int result = 0;
while(a)
{
result++;
a=a&(a-1);
}
}
сложность будет O от количества единичных бит
можно было бы посмотреть на результат с таким подсчетом
Рассмотрю этот вариант в ближайшее же время. Он скорее всего будет медленее, чем popcnt, но хочется сравнить с предподсчётом битов. Мой вариант составления CountOfSettedBits думаю точно медленее чем ваш код. Спасибо за идею!
Ну, если уж оптимизировать, то не result++, а ++result. Выполняется быстрее за счет того, что не надо сохранять значение до инкремента для предполагаемого возврата значения.
Данный алгоритм можно найти в книге «Алгоритмические трюки для программистов», Г. Уоррен мл. Но там написано, что его эффективность проявляется только для «разреженных» чисел с малым количеством единиц. Впрочем, список тэгов таким и будет являться.
Данный алгоритм можно найти в книге «Алгоритмические трюки для программистов», Г. Уоррен мл. Но там написано, что его эффективность проявляется только для «разреженных» чисел с малым количеством единиц. Впрочем, список тэгов таким и будет являться.
Отброшенное (не использованное) значение будет заоптимизировано. Здесь не имеет значения такая микрооптимизация (которой ещё и нет).
Ви, таки, не поверите, но я тоже не верил раньше.
Я вот не программист, но когда прочитал про это, захотел убедиться лично. Скачал и установил Visual Studio. На C++ написал вложенные циклы из большого количества инкриментов тем и другим способом. Скомпилировал с включенным оптимизатором.
Разница была такая существенная, что просто поразила.
Я вот не программист, но когда прочитал про это, захотел убедиться лично. Скачал и установил Visual Studio. На C++ написал вложенные циклы из большого количества инкриментов тем и другим способом. Скомпилировал с включенным оптимизатором.
Разница была такая существенная, что просто поразила.
Вы их просто инкрементировали или результат куда-то сохраняли для дальнейших манипуляций? Предполагаю второе.
Prefix 30.73 ms
Postfix 30.86 ms
Postfix
00007fff`97e8617f mov rax,0FFFFFFFFFFFFFFFFh
00007fff`97e86189 xor edx,edx
00007fff`97e8618b inc edx
00007fff`97e8618d lea rcx,[rax-1]
00007fff`97e86191 and rax,rcx
00007fff`97e86194 test rax,rax
00007fff`97e86197 jne 00007fff`97e8618b
00007fff`97e86199 add esi,edxPrefix
00007fff`97e996ef mov rax,0FFFFFFFFFFFFFFFFh
00007fff`97e996f9 xor edx,edx
00007fff`97e996fb inc edx
00007fff`97e996fd lea rcx,[rax-1]
00007fff`97e99701 and rax,rcx
00007fff`97e99704 test rax,rax
00007fff`97e99707 jne 00007fff`97e996fb
00007fff`97e99709 add esi,edxкод
public class Benchmark {
static int CountOfBitsPostfix(ulong a) {
int result = 0;
while (a != 0) {
result++;
a &= a - 1;
}
return result;
}
static int CountOfBitsPrefix(ulong a) {
int result = 0;
while (a != 0) {
++result;
a &= a - 1;
}
return result;
}
[Benchmark]
public int Prefix() {
int result = 0;
for (int i = 0; i < 1000000; i++) {
result += CountOfBitsPrefix(ulong.MaxValue);
}
return result;
}
[Benchmark]
public int Postfix() {
int result = 0;
for (int i = 0; i < 1000000; i++) {
result += CountOfBitsPostfix(ulong.MaxValue);
}
return result;
}
}оптимизировать, то не result++, а ++result
Надо бы посмотреть на результирующий ассемблер, есть подозрение что итог будет одинаковый.
эффективность проявляется только для «разреженных» чисел с малым количеством единиц
А я так и написал, сложность будет O от количества единичных бит :)
Результаты большого бенчмарка с вашим кодом в MeasureSimilarity:
RandomTest и Descendant = 1.21 c, Ascendant = 1.1 с. Что всего лишь в два раза хуже, чем вариант с предподсчётом. Можно как минимум алгоритм предподсчёта заменить вашим. Спасибо!
RandomTest и Descendant = 1.21 c, Ascendant = 1.1 с. Что всего лишь в два раза хуже, чем вариант с предподсчётом. Можно как минимум алгоритм предподсчёта заменить вашим. Спасибо!
Чем больше тегов у видео совпадает, тем более они похожи.
Не совсем понял смысл этого предложения, а в коде разбираться — опыта нет…
Что значит «больше тегов»? Имеется в виду абсолютное число совпадающих тэгов (пар) или относительное?
Поясню на примере…
Вот есть два видео А и Б и у каждого ровно один тэг:
А — #драма
Б — #драма
Как видим, число совпадающих пар тэгов — 1. Относительное — тоже 1.
Но возьмем другую пару видео:
В — #драма, #мелодрама, #криминал, #боевик
Г — #драма, #мелодрама, #детектив, #нуар
Абсолютное число совпадающих пар — 2.
А вот относительное число можно подсчитать, аналогично доле совпадающих N-грамм в N-граммном анализе: 2*(чило_совпадающих_тэгов)/(число_тэгов_в_первом + число_тэгов_во_втором):
2*2/(4+4)=0,5
Т.е. абсолютное число совпадающих тэгов стало больше, а относительное — меньше.
И мне кажется, пользоваться надо как раз относительной величиной, т.к. она учитывает не только чем фильмы похожи, но и насколько они различаются.
Во втором вашем случае MeasureSimilarity вернёт 2. Моему коллеге показалось, что этого достаточно. Но и такой алгоритм как у вас неплохо ложится на интринсики и будет совсем чуть медленее текущего. Я вашу идею передам коллеге для экспериментов.
Простите, не владею терминологией по теме. Интринсики — это куда?
Это одна из оптимизаций применённых автором. встроенная в компилятор функция.
В данном случае функция подсчёта единичных бит в числе. Но как и говорилось, ваш подход не сильно изменит код и не повлияет на оптимизации. Но ваш подход идеалогически мне нравится больше.
Выше вам уже ответили, но дополню, что определение можно почитать здесь:
en.wikipedia.org/wiki/Intrinsic_function
Рассматриваемый в статье интринсик можно найти тут: software.intel.com/sites/landingpage/IntrinsicsGuide/#othertechs=POPCNT&expand=4373
Там есть псевдокод описания операции и много всего другого. Идея в том, что вся логика подсчёта количества выставленных битов заменяется на вызов одной ассемблерной инструкции popcnt r64, r64, а дальше оно уже как-то сделано в процессоре и отрабатывает быстрее, чем если это писать руками. Но процессор может не поддеживать эту инструкцию и нужны дополнительные проверки. В .NetCore 3.0 для всего этого сделали очень удобные механизмы.
en.wikipedia.org/wiki/Intrinsic_function
Рассматриваемый в статье интринсик можно найти тут: software.intel.com/sites/landingpage/IntrinsicsGuide/#othertechs=POPCNT&expand=4373
Там есть псевдокод описания операции и много всего другого. Идея в том, что вся логика подсчёта количества выставленных битов заменяется на вызов одной ассемблерной инструкции popcnt r64, r64, а дальше оно уже как-то сделано в процессоре и отрабатывает быстрее, чем если это писать руками. Но процессор может не поддеживать эту инструкцию и нужны дополнительные проверки. В .NetCore 3.0 для всего этого сделали очень удобные механизмы.
UFO just landed and posted this here
На мой взгляд, можно было бы делегировать эту задачу SQL.
Конечно при использовании SQL возникают вопросы лицензии…
- Он оптимизирован для работы с большими массивами данных
- Многие моменты он сам оптимизирует. Например, видя индексы он может выбрать соединение слиянием. Может еще и параллелизм добавить
Конечно при использовании SQL возникают вопросы лицензии…
А по каким признакам предполагаете индексировать? По самим тэгам? Так их 4096. Многовато будет для индексации.
Предложите реализацию, можно отдельной статьёй. Заодно было бы интересно сравнить быстродействие.
Кстати, решить это на SQL было бы тоже занимательно.
Конечно, индексировать по 4096 индексам невозможно. Ну не поддерживает SQL такого числа индексов у одной таблицы.
Но можно попытаться сделать вот что: Т.к. многие тэги будут идти «в наборе», то можно сначала кластеризировать фильмы в несколько типичных кластеров. Вернее, не фильмы, а их наборы тэгов.
И делать двухстадийную выборку. На первом шаге выбирать фильмы, которые могут принадлежать тому же кластеру, что и эталон, а потом уже из этой выборки выбрасывать лишние.
Например, есть два кластера, в один из которых (К1) входит среди прочих тэг #драма, а в другой (К2) — тэг #фэнтези (тоже среди прочих). И много еще прочих кластеров, но они нам не интересны.
Если эталонный фильм имеет эти два тэга, то в первичную выборку попадают только фильмы, принадлежащие хотя бы одному из этих кластеров. А потом уже в ней делаем более точное вычисление релевантности.
Конечно, индексировать по 4096 индексам невозможно. Ну не поддерживает SQL такого числа индексов у одной таблицы.
Но можно попытаться сделать вот что: Т.к. многие тэги будут идти «в наборе», то можно сначала кластеризировать фильмы в несколько типичных кластеров. Вернее, не фильмы, а их наборы тэгов.
И делать двухстадийную выборку. На первом шаге выбирать фильмы, которые могут принадлежать тому же кластеру, что и эталон, а потом уже из этой выборки выбрасывать лишние.
Например, есть два кластера, в один из которых (К1) входит среди прочих тэг #драма, а в другой (К2) — тэг #фэнтези (тоже среди прочих). И много еще прочих кластеров, но они нам не интересны.
Если эталонный фильм имеет эти два тэга, то в первичную выборку попадают только фильмы, принадлежащие хотя бы одному из этих кластеров. А потом уже в ней делаем более точное вычисление релевантности.
P.S. Если говорить о кластеризации, то это само по себе интересная задача.
Прежде всего тем, что кластеризировать придется в неевклидовом пространстве. Чтобы не заниматься этим в евклидовом, но 4096-мерном.
Но этого мало… Дело в том, что сама метрика невнятная. Что принимать за расстояние между тэгами?
Я вот предлагаю принять за расстояние величину -ln(K), где K — ДОЛЯ фильмов, в которых эти два тэга встретились одновременно.
Тогда, если какие-то два тэга одновременно не встречаются никогда, то расстояние равно +Inf. А если встречаются только вместе постоянно, то расстояние равно 0 (они, как бы, эквивалентны).
Может быть есть другие предложения по метрике?
Прежде всего тем, что кластеризировать придется в неевклидовом пространстве. Чтобы не заниматься этим в евклидовом, но 4096-мерном.
Но этого мало… Дело в том, что сама метрика невнятная. Что принимать за расстояние между тэгами?
Я вот предлагаю принять за расстояние величину -ln(K), где K — ДОЛЯ фильмов, в которых эти два тэга встретились одновременно.
Тогда, если какие-то два тэга одновременно не встречаются никогда, то расстояние равно +Inf. А если встречаются только вместе постоянно, то расстояние равно 0 (они, как бы, эквивалентны).
Может быть есть другие предложения по метрике?
Немного тупанул… Забыл про такую удобную вещь, как расстояние редактирования.
В случае использования хранимых процедур SQL, удобнее будет выдавать в выборку только фильмы, для которых расстояние Левенштейна с эталонным набором тэгов не превышает, допустим, 2.
Правда, это не отменяет возможности (а может быть и необходимости) применения кластеризации для предварительной выборки.
Кстати, для каждого тэга можно указывать его «вес» в соответствующем кластере тэгов. Т.е. долю фильмов/роликов с данным тэгом среди общего числа фильмов/роликов, обладающими хотя бы одним тэгом из этого же кластера тэгов.
Тогда поиск можно начинать среди кластеров, имеющих наибольший вес в своем кластере. Это позволит лучше находить в первую очередь ролики по редким тэгам.
Правда, как сделать эту приоритетность поиска средствами самого SQL — не знаю. Яжнепрограммист :)
В случае использования хранимых процедур SQL, удобнее будет выдавать в выборку только фильмы, для которых расстояние Левенштейна с эталонным набором тэгов не превышает, допустим, 2.
Правда, это не отменяет возможности (а может быть и необходимости) применения кластеризации для предварительной выборки.
Кстати, для каждого тэга можно указывать его «вес» в соответствующем кластере тэгов. Т.е. долю фильмов/роликов с данным тэгом среди общего числа фильмов/роликов, обладающими хотя бы одним тэгом из этого же кластера тэгов.
Тогда поиск можно начинать среди кластеров, имеющих наибольший вес в своем кластере. Это позволит лучше находить в первую очередь ролики по редким тэгам.
Правда, как сделать эту приоритетность поиска средствами самого SQL — не знаю. Яжнепрограммист :)
Немного жаль, что до AVX-512 нет метода для подсчета количества единичных бит даже в 128-битном регистре. Можно было бы на них тогда перейти.
Единственное мелкое улучшение, которое я вижу — код
list.Insert(index, newInfo);
if (list.Count > resultLength) {
list.RemoveAt(resultLength);
}
имеет смысл заменить на
if (list.Count == resultLength) {
list.RemoveAt(resultLength);
}
list.Insert(index, newInfo);
В первом варианте список временно может вырасти до 51 элемента, что больше Capacity и повлечет перевыделение памяти.
Раньше CompareTo() == -1 заменили бы на CompareTo() < 0, поскольку сравнение с 0 было на 1 инструкцию короче, но сейчас это вряд ли имеет значение.
Единственное мелкое улучшение, которое я вижу — код
list.Insert(index, newInfo);
if (list.Count > resultLength) {
list.RemoveAt(resultLength);
}
имеет смысл заменить на
if (list.Count == resultLength) {
list.RemoveAt(resultLength);
}
list.Insert(index, newInfo);
В первом варианте список временно может вырасти до 51 элемента, что больше Capacity и повлечет перевыделение памяти.
Раньше CompareTo() == -1 заменили бы на CompareTo() < 0, поскольку сравнение с 0 было на 1 инструкцию короче, но сейчас это вряд ли имеет значение.
В первом варианте список временно может вырасти до 51 элемента, что больше Capacity и повлечет перевыделение памяти.
Согласен, но только один раз и, имхо, можно пренебречь. Хотя соглашусь, что проглядел такую оптимизацию.
CompareTo() == -1 заменили бы на CompareTo() < 0
Тут надо смотреть что будет после JIT компиляции, но спасибо.
Дополню про CompareTo.
Int32.CompareTo, похоже, не инлайниться, и в Reference Source сейчас такая реализация
public int CompareTo(int value) {
// Need to use compare because subtraction will wrap
// to positive for very large neg numbers, etc.
if (m_value < value) return -1;
if (m_value > value) return 1;
return 0;
}
Поскольку у нас величина similarity и индексы ограничены, сравнение можно свести к вычитанию и в TagsSimilarityInfo.CompareTo избавиться от вызовов Int32.CompareTo вовсе.
Int32.CompareTo, похоже, не инлайниться, и в Reference Source сейчас такая реализация
public int CompareTo(int value) {
// Need to use compare because subtraction will wrap
// to positive for very large neg numbers, etc.
if (m_value < value) return -1;
if (m_value > value) return 1;
return 0;
}
Поскольку у нас величина similarity и индексы ограничены, сравнение можно свести к вычитанию и в TagsSimilarityInfo.CompareTo избавиться от вызовов Int32.CompareTo вовсе.
Ну и пара косметических замечаний по MergeTaskResults. Во внутреннем цикле j можно начинать от 1, чтобы не сравнивать элемент с самим собой. Присваивание
currentBest = taskResults[minIndex][indices[minIndex]];
проще заменить на currentBest = current;
Для реального случая код, конечно, будет сложнее — потребуется учитывать неравное количество элементов в списке результатов и их исчерпание.
currentBest = taskResults[minIndex][indices[minIndex]];
проще заменить на currentBest = current;
Для реального случая код, конечно, будет сложнее — потребуется учитывать неравное количество элементов в списке результатов и их исчерпание.
Спасибо большое за все замечания и дополнения. Когда-нибудь я достигну совершенства :).
MergeTaskResult я сначала написал с дополнительными проверками на невыход за пределы в taskResult(minIndex вначале == -1, проверка на невыход, current и currentBest вначале null и т.д.), но потом удалил, т.к. много ненужного для статьи кода получалось, аcurrentBest = taskResults[minIndex][indices[minIndex]]; ` осталось как артефакт. Я на неделе прикручу все предложения и ещё раз измерю скорость. Вряд ли будут большие улучшения, но всё-таки.
При всем уважении к предложенному Вами алгоритму, все же замечу (имхо) что решение через разряженные матрицы было бы более изящным и главное универсальным. Я посидел с листком бумаги над Вашей задачей — и действительно, прослеживается довольно интересный алгоритм с очень эффективным рассчетом и кординальным снежением размерности пространства поиска решения.
Вполне возможно. Можете предоставить код/расчёты/выкладки и приправить это всё теорией? Я с удовольствием узнаю новое. Пока что я даже не понял куда копать.
Да, постраюсь предоставить решение. Уж не знаю как его лучше будет оформить, возможно даже в виде небольшой статьи-довеска.
Что касается проблематики вопроса, то вспомнилась весьма неплохая книга Роберта Седжвика «Алгоритмы на Java», конкретно, ее раздел посвященный разряженным векторам, в русском 4-ом издании 453 страница. Впрочем там весьма мутно и поверхностно все это описывается, но оно и понятно, потому что тема довольно сложная. Однако, в нашем случае с тегами, думаю все можно упростить.
Что касается проблематики вопроса, то вспомнилась весьма неплохая книга Роберта Седжвика «Алгоритмы на Java», конкретно, ее раздел посвященный разряженным векторам, в русском 4-ом издании 453 страница. Впрочем там весьма мутно и поверхностно все это описывается, но оно и понятно, потому что тема довольно сложная. Однако, в нашем случае с тегами, думаю все можно упростить.
Sign up to leave a comment.
Эволюция одного алгоритма