Про подсчёт битов, беззнаковые типы в Kotlin и про ситуации, когда экономия на спичках оправдана

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

… расходовать память или такты процессора на элементы в миллиардных объёмах — это нехорошо…

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

Немного контекста

Приложение iFunny имеет дело с колоссальным объёмом графического и видеоконтента, а нечёткий поиск дубликатов является одной из очень важных задач. Сама по себе это большая тема, заслуживающая отдельной статьи, но сегодня я просто немного расскажу о некоторых подходах к обсчёту очень больших массивов чисел, применительно к этому поиску. Конечно же, у всех разное понимание «очень больших массивов», и тягаться с Адронным коллайдером было бы глупо, но всё же. :)

Если совсем коротко про алгоритм, то для каждого изображения создаётся его цифровая подпись (сигнатура) из 968 целых чисел, а сравнение производится путем нахождения «расстояния» между двумя сигнатурами. Учитывая, что объём контента только за два последних месяца составил порядка 10 миллионов изображений, то, как легко прикинет в уме внимательный читатель, — это как раз те самые «элементы в миллиардных объёмах». Кому интересно — добро пожаловать под кат.

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

Должен признаться, что я немного слукавил. При предварительном анализе алгоритма удалось сократить количество значений в каждой сигнатуре с 968 до 420. Уже в два раза лучше, но порядок величин остался тот же.
Хотя, если подумать, то не так уж я и слукавил, и это будет первым выводом: прежде чем приступать к задаче, стоит подумать — а нельзя ли её как-то заранее упростить?

Алгоритм сравнения довольно простой: вычисляется корень из суммы квадратов разностей двух сигнатур, делится на сумму предварительно рассчитанных значений (т.е. в каждой итерации суммирование всё же будет и совсем его в константу не вынести) и сравнивается с пороговым значением. Стоит отметить, что элементы сигнатуры ограничены значениями от -2 до +2, а, соответственно, абсолютное значение разности — значениями от 0 до 4.

Ничего сложного, но количество решает.

Подход первый, наивный

// Порог
const val d = 0.3

// 10.000.000 объектов. 
// Будем держать эту цифру в уме,
// чтобы не упоминать в каждом втором предложении
val collection: MutableList<Signature> = mutableListOf()        

// signature — массив из 420 значений типа Byte
class Signature(val signature: Array<Byte>, val norma: Double)  

fun getSimilar(signature: Signature) = collection
    .filter { calculateDistance(it, signature) < d }

fun calculateDistance(first: Signature, second: Signature): Double = 
	Math.sqrt(first.signature.mapIndexed { index, value ->
        Math.pow((value - second.signature[index]).toDouble(), 2.0)
    }.sum()) / (first.norma + second.norma)

Давайте посчитаем, что у нас тут с количеством операций:
10M квадратных корней Math.sqrt
10M сложений и делений / (first.norma + second.norma)
4.200M вычитаний и возведений в квадрат Math.pow((value - second.signature[index]).toDouble(), 2.0)
4.200M сложений .sum()

Какие у нас есть варианты:

1. При таких объёмах тратить целый Byte (или, не дай бог, кто-то догадался бы использовать Int) на хранение трёх значащих бит — это непростительное расточительство.
2. Может, как-то подсократить количество математики?
3. А нельзя ли сделать какую-нибудь предварительную фильтрацию, не такую затратную по вычислениям?

Подход второй, упаковываем

Кстати, если кто-то предложит, как можно упростить вычисления при такой упаковке — получит большое спасибо и плюс в карму. Хоть и один, но зато от всей души :)

Один Long — это 64 бита, что, в нашем случае, позволит хранить в нём 21 значение (и 1 бит останется неприкаянным).

// массив из 20 значений типа Long
class Signature(val signature: Array<Long>, val norma: Double) 

fun calculateDistance(first: Signature, second: Signature): Double =
    Math.sqrt(first.signature.mapIndexed { index, value ->
        calculatePartial(value, second.signature[index])
    }.sum()) / (first.norma + second.norma)

fun calculatePartial(first: Long, second: Long): Double {
    var sum = 0L
    (0..60 step 3).onEach {
        val current = (first.ushr(it) and 0x7) - (second.ushr(it) and 0x7)
        sum += current * current
    }
    return sum.toDouble()
}

По памяти стало лучше (4.200M против 1.600M байт, если грубо), но что там с вычислениями?

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

Подход третий, упаковываем заново с подвыподвертом

Нутром чую, тут можно использовать битовую магию!

Давайте хранить значения не в трёх, а в четырёх битах. Таким, вот, образом:

Да, мы потеряем в плотности упаковки по сравнению с предыдущим вариантом, но зато получим возможность одним XOR'ом получать Long с разностями (не совсем) сразу 16-ти элементов. Кроме того, будет всего 11 вариантов распределения бит в каждом конечном полубайте, что позволит использовать заранее рассчитанные значения квадратов разностей.

// массив из 27 значений типа Long
class Signature(val signature: Array<Long>, val norma: Double) 

// -1 для невозможных вариантов
val precomputed = arrayOf(0, 1, 1, 4, 1, -1, 4, 9, 1, -1, -1, -1, 4, -1, 9, 16)

fun calculatePartial(first: Long, second: Long): Double {
    var sum = 0L
    val difference = first xor second
    (0..60 step 4).onEach {
        sum += precomputed[(difference.ushr(it) and 0xF).toInt()]
    }
    return sum.toDouble()
}

По памяти стало 2.160M против 1.600M — неприятно, но всё же лучше, чем начальные 4.200M.
Посчитаем операции:
10M квадратных корней, сложений и делений (никуда не делись)
270M XOR'ов
4.320 сложений, сдвигов, логических И и извлечений из массива.

Выглядит уже более интересно, но, всё равно, слишком много вычислений. К сожалению, похоже, что те 20% усилий, дающих 80% результата, мы тут уже потратили и пора подумать, где ещё можно выгадать. Первое, что приходит на ум, — вообще не доводить до расчёта, отфильтровывая заведомо неподходящие сигнатуры каким-нибудь легковесным фильтром.

Подход четвёртый, крупное сито

Если немного преобразовать формулу расчёта, то можно получить такое неравенство (чем меньше рассчитанная дистанция — тем лучше):

Т.е. теперь нам надо придумать, как на основании имеющейся у нас информации по количеству выставленных бит в Long'ах вычислить минимальное возможное значение левой части неравенства. После чего просто отбрасывать все сигнатуры, ему не удовлетворяющие.
Напомню, что x_i может принимать значения от 0 до 4 (знак не важен, думаю, понятно почему). Учитывая, что каждое слагаемое возводится в квадрат, несложно вывести общую закономерность:

Конечная формула выглядит так (она нам не понадобится, но я довольно долго её выводил и было бы обидно просто забыть и никому не показать):

Где B — количество выставленных бит.

На самом то деле, в одном Long'е всего 64 бита, читай 64 возможных результата. И они отлично рассчитываются заранее и складываются в массив, по аналогии с предыдущим разделом.

Кроме того, совершенно необязательно просчитывать все 27 Long'ов — достаточно на очередном из них превысить порог и можно прерывать проверку и возвращать false. Такой же подход, кстати, можно использовать и при основном расчёте.

fun getSimilar(signature: Signature) = collection
        .asSequence()  //  Зачем нам лишняя промежуточная коллекция!?
        .filter { estimate(it, signature) }
        .filter { calculateDistance(it, signature) < d }

val estimateValues = arrayOf(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49, 52, 55, 58, 61, 64, 69, 74, 79, 84, 89, 94, 99, 104, 109, 114, 119, 124, 129, 134, 139, 144, 151, 158, 165, 172, 179, 186, 193, 200, 207, 214, 221, 228, 235, 242, 249, 256)

fun estimate(first: Signature, second: Signature):Boolean{
    var bitThreshold = Math.pow(d * (first.norma + second.norma), 2.0).toLong()
    first.signature.forEachIndexed { index, value ->
        bitThreshold -= estimateValues[java.lang.Long.bitCount(value xor second.signature[index])]
        if (bitThreshold <= 0) return false
    }

    return true
}

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

Подход пятый, избавляемся от sequence

При работе с большими коллекциями, sequence — это хорошая защита от крайне неприятного Out of memory. Однако если мы заведомо знаем, что на первом же фильтре коллекция уменьшится до вменяемых размеров, то гораздо более разумным выбором будет использовать обычный перебор в цикле с созданием промежуточной коллекции, потому как sequence — это не только модно и молодёжно, но ещё и итератор, у которого hasNext сотоварищи, которые совсем не бесплатны.

fun getSimilar(signature: Signature) = collection
        .filter { estimate(it, signature) }
        .filter { calculateDistance(it, signature) < d }

Казалось бы, вот оно счастье, но захотелось «сделать красиво». Вот тут мы и подошли к обещанной поучительной истории.

Подход шестой, хотели как лучше

Мы же пишем на Kotlin, а тут какие-то инородные java.lang.Long.bitCount! А ещё недавно в язык подвезли беззнаковые типы. В атаку!

Сказано — сделано. Все Long заменены на ULong, из исходников Java с корнем выдрана java.lang.Long.bitCount и переписана как функция расширения для ULong

fun ULong.bitCount(): Int {
    var i = this
    i = i - (i.shr(1) and 0x5555555555555555uL)
    i = (i and 0x3333333333333333uL) + (i.shr(2) and 0x3333333333333333uL)
    i = i + i.shr(4) and 0x0f0f0f0f0f0f0f0fuL
    i = i + i.shr(8)
    i = i + i.shr(16)
    i = i + i.shr(32)
    return i.toInt() and 0x7f
}

Запускаем и… Что-то не так. Код стал отрабатывать заметно медленнее. Запускаем профайлер и видим странное (см. заглавную иллюстрацию статьи): на чуть меньше миллиона вызовов bitCount() почти 16 миллионов вызовов Kotlin.ULong.constructor-impl. WAT!?

Загадка объясняется просто — достаточно посмотреть в код класса ULong

public inline class ULong @PublishedApi internal constructor(@PublishedApi internal val data: Long) : Comparable<ULong> {
    @kotlin.internal.InlineOnly
    public inline operator fun plus(other: ULong): ULong = ULong(this.data.plus(other.data))
    @kotlin.internal.InlineOnly
    public inline operator fun minus(other: ULong): ULong = ULong(this.data.minus(other.data))
    @kotlin.internal.InlineOnly
    public inline infix fun shl(bitCount: Int): ULong = ULong(data shl bitCount)
    @kotlin.internal.InlineOnly
    public inline operator fun inc(): ULong = ULong(data.inc())
    и т.д.
 }

Нет, я всё понимаю, ULong сейчас experimental, но как так-то!?
В общем и целом, признаём подход несостоявшимся, а жаль.

Ну, а всё-таки, может можно ещё что-то улучшить?

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

Я использовал «Комбинированный метод»

fun Long.bitCount(): Int {
    var n = this
    n -= (n.shr(1)) and 0x5555555555555555L
    n = ((n.shr(2)) and 0x3333333333333333L) + (n and 0x3333333333333333L)
    n = ((((n.shr(4)) + n) and 0x0F0F0F0F0F0F0F0FL) * 0x0101010101010101).shr(56)
    return n.toInt() and 0x7F
}

Считаем попугаев

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

Выводы

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

Спасибо за внимание! :)

И да, продолжение следует.

Автор: Громов Андрей

Источник