Comments 47
По-хорошему, надо проверять доступность инструкции и делать fallback на код, который сделает то же самое на более базовом наборе инструкций.
Хотя при работе с интринсиками в первую очередь стоит ориентироваться на примерные характеристики целевого устройства (или набора устройств).
Не могу не согласится, ибо у самого были случаи, когда находился пара пользователей с крайне специфичным железом :)
В данном вопросе больше ориентировался на предположение, что данный код будет исполняться на сервере.
На самом деле когда я писал это всё для коллеги, он думал гонять на большой фреймворке 4.7 и я туда никакие popcnt не вписывал. Потом показал ему, что на .netcore можно быстрее и он задумался о переезде или хотя бы отпочковывании некоторых функций на .netcore в отдельную библиотеку. Но по-моему там до сих пор ничего не решилось.
Интересно было бы сравнить различные варианты fallback-ов на больших данных.
Ведь дание точно есть в базе.
Но создание словаря и групп — ручная и рутинная работа + лишняя возня с классификацией видео (т.к. метаданные каждого видео нужно обработать, положить в бд и классифицировать ранее не встречавшиеся теги по группам и типам связей)
Думаю, для миллиона видео это может быть overkill.
PS зато, добавив немного других типов тезаурусов, можно очень быстро реализовывать функционал «максимально непохожее видео» — все связи омонимы, «частично похожее видео» и просто поиск по нескольким тэгам.
int CountOfBits(int a)
{
int result = 0;
while(a)
{
result++;
a=a&(a-1);
}
}
сложность будет O от количества единичных бит
можно было бы посмотреть на результат с таким подсчетом
Данный алгоритм можно найти в книге «Алгоритмические трюки для программистов», Г. Уоррен мл. Но там написано, что его эффективность проявляется только для «разреженных» чисел с малым количеством единиц. Впрочем, список тэгов таким и будет являться.
Я вот не программист, но когда прочитал про это, захотел убедиться лично. Скачал и установил 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,edx
Prefix
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 от количества единичных бит :)
RandomTest и Descendant = 1.21 c, Ascendant = 1.1 с. Что всего лишь в два раза хуже, чем вариант с предподсчётом. Можно как минимум алгоритм предподсчёта заменить вашим. Спасибо!
Чем больше тегов у видео совпадает, тем более они похожи.
Не совсем понял смысл этого предложения, а в коде разбираться — опыта нет…
Что значит «больше тегов»? Имеется в виду абсолютное число совпадающих тэгов (пар) или относительное?
Поясню на примере…
Вот есть два видео А и Б и у каждого ровно один тэг:
А — #драма
Б — #драма
Как видим, число совпадающих пар тэгов — 1. Относительное — тоже 1.
Но возьмем другую пару видео:
В — #драма, #мелодрама, #криминал, #боевик
Г — #драма, #мелодрама, #детектив, #нуар
Абсолютное число совпадающих пар — 2.
А вот относительное число можно подсчитать, аналогично доле совпадающих N-грамм в N-граммном анализе: 2*(чило_совпадающих_тэгов)/(число_тэгов_в_первом + число_тэгов_во_втором):
2*2/(4+4)=0,5
Т.е. абсолютное число совпадающих тэгов стало больше, а относительное — меньше.
И мне кажется, пользоваться надо как раз относительной величиной, т.к. она учитывает не только чем фильмы похожи, но и насколько они различаются.
Это одна из оптимизаций применённых автором. встроенная в компилятор функция.
В данном случае функция подсчёта единичных бит в числе. Но как и говорилось, ваш подход не сильно изменит код и не повлияет на оптимизации. Но ваш подход идеалогически мне нравится больше.
en.wikipedia.org/wiki/Intrinsic_function
Рассматриваемый в статье интринсик можно найти тут: software.intel.com/sites/landingpage/IntrinsicsGuide/#othertechs=POPCNT&expand=4373
Там есть псевдокод описания операции и много всего другого. Идея в том, что вся логика подсчёта количества выставленных битов заменяется на вызов одной ассемблерной инструкции popcnt r64, r64, а дальше оно уже как-то сделано в процессоре и отрабатывает быстрее, чем если это писать руками. Но процессор может не поддеживать эту инструкцию и нужны дополнительные проверки. В .NetCore 3.0 для всего этого сделали очень удобные механизмы.
- Он оптимизирован для работы с большими массивами данных
- Многие моменты он сам оптимизирует. Например, видя индексы он может выбрать соединение слиянием. Может еще и параллелизм добавить
Конечно при использовании SQL возникают вопросы лицензии…
Конечно, индексировать по 4096 индексам невозможно. Ну не поддерживает SQL такого числа индексов у одной таблицы.
Но можно попытаться сделать вот что: Т.к. многие тэги будут идти «в наборе», то можно сначала кластеризировать фильмы в несколько типичных кластеров. Вернее, не фильмы, а их наборы тэгов.
И делать двухстадийную выборку. На первом шаге выбирать фильмы, которые могут принадлежать тому же кластеру, что и эталон, а потом уже из этой выборки выбрасывать лишние.
Например, есть два кластера, в один из которых (К1) входит среди прочих тэг #драма, а в другой (К2) — тэг #фэнтези (тоже среди прочих). И много еще прочих кластеров, но они нам не интересны.
Если эталонный фильм имеет эти два тэга, то в первичную выборку попадают только фильмы, принадлежащие хотя бы одному из этих кластеров. А потом уже в ней делаем более точное вычисление релевантности.
Прежде всего тем, что кластеризировать придется в неевклидовом пространстве. Чтобы не заниматься этим в евклидовом, но 4096-мерном.
Но этого мало… Дело в том, что сама метрика невнятная. Что принимать за расстояние между тэгами?
Я вот предлагаю принять за расстояние величину -ln(K), где K — ДОЛЯ фильмов, в которых эти два тэга встретились одновременно.
Тогда, если какие-то два тэга одновременно не встречаются никогда, то расстояние равно +Inf. А если встречаются только вместе постоянно, то расстояние равно 0 (они, как бы, эквивалентны).
Может быть есть другие предложения по метрике?
В случае использования хранимых процедур SQL, удобнее будет выдавать в выборку только фильмы, для которых расстояние Левенштейна с эталонным набором тэгов не превышает, допустим, 2.
Правда, это не отменяет возможности (а может быть и необходимости) применения кластеризации для предварительной выборки.
Кстати, для каждого тэга можно указывать его «вес» в соответствующем кластере тэгов. Т.е. долю фильмов/роликов с данным тэгом среди общего числа фильмов/роликов, обладающими хотя бы одним тэгом из этого же кластера тэгов.
Тогда поиск можно начинать среди кластеров, имеющих наибольший вес в своем кластере. Это позволит лучше находить в первую очередь ролики по редким тэгам.
Правда, как сделать эту приоритетность поиска средствами самого SQL — не знаю. Яжнепрограммист :)
Единственное мелкое улучшение, которое я вижу — код
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 компиляции, но спасибо.
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 вовсе.
currentBest = taskResults[minIndex][indices[minIndex]];
проще заменить на currentBest = current;
Для реального случая код, конечно, будет сложнее — потребуется учитывать неравное количество элементов в списке результатов и их исчерпание.
Спасибо большое за все замечания и дополнения. Когда-нибудь я достигну совершенства :).
MergeTaskResult
я сначала написал с дополнительными проверками на невыход за пределы в taskResult
(minIndex вначале == -1, проверка на невыход, current и currentBest вначале null и т.д.), но потом удалил, т.к. много ненужного для статьи кода получалось, а
currentBest = taskResults[minIndex][indices[minIndex]]; ` осталось как артефакт. Я на неделе прикручу все предложения и ещё раз измерю скорость. Вряд ли будут большие улучшения, но всё-таки.
Вполне возможно. Можете предоставить код/расчёты/выкладки и приправить это всё теорией? Я с удовольствием узнаю новое. Пока что я даже не понял куда копать.
Что касается проблематики вопроса, то вспомнилась весьма неплохая книга Роберта Седжвика «Алгоритмы на Java», конкретно, ее раздел посвященный разряженным векторам, в русском 4-ом издании 453 страница. Впрочем там весьма мутно и поверхностно все это описывается, но оно и понятно, потому что тема довольно сложная. Однако, в нашем случае с тегами, думаю все можно упростить.
Эволюция одного алгоритма