Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Java Новый топик    Ответить
 Как оптимизировать?  [new]
Hett
Member

Откуда: Бийск, Новосибирск
Сообщений: 13630
Можно ли как-то сделать, чтобы работало быстрее?
    public int distanceBetween(CompactHash hash1, CompactHash hash2) {
        return Math.abs(hash2.getVal0() - hash1.getVal0())
                + Math.abs(hash2.getVal1() - hash1.getVal1())
                + Math.abs(hash2.getVal2() - hash1.getVal2())
                + Math.abs(hash2.getVal3() - hash1.getVal3())
                + Math.abs(hash2.getVal4() - hash1.getVal4())
                + Math.abs(hash2.getVal5() - hash1.getVal5())
                + Math.abs(hash2.getVal6() - hash1.getVal6())
                + Math.abs(hash2.getVal7() - hash1.getVal7())
                + Math.abs(hash2.getVal8() - hash1.getVal8())
                + Math.abs(hash2.getVal9() - hash1.getVal9())
                + Math.abs(hash2.getValA() - hash1.getValA())
                + Math.abs(hash2.getValB() - hash1.getValB())
                + Math.abs(hash2.getValC() - hash1.getValC())
                + Math.abs(hash2.getValD() - hash1.getValD())
                + Math.abs(hash2.getValE() - hash1.getValE())
                + Math.abs(hash2.getValF() - hash1.getValF());
    }


Интересно, что когда я попробовал отказаться от getter-ов, то стало работать медленнее.
22 апр 20, 14:45    [22120775]     Ответить | Цитировать Сообщить модератору
 Re: Как оптимизировать?  [new]
mayton
Member

Откуда: loopback
Сообщений: 46531
Скорее всего - никак, без понимания внутренней структуры CompactHash.
Если внутри - биткарта - то возможно сложением по модулю 2 (XOR) двух
хешей и подсчетом битов в результате мы получим то что ты хотел. Но это
нарушает инкапсуляцию.
22 апр 20, 14:52    [22120785]     Ответить | Цитировать Сообщить модератору
 Re: Как оптимизировать?  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 8552
С учетом 16 значений - как-то хочется MMX, но тогда JNI

Вроде, в И-нете предлагают заменять abs на подсчет двух вариантов + OR. Насколько это работает и математически правильно - не знаю
http://www.asmcommunity.net/forums/topic/?id=18590
22 апр 20, 15:03    [22120795]     Ответить | Цитировать Сообщить модератору
 Re: Как оптимизировать?  [new]
Hett
Member

Откуда: Бийск, Новосибирск
Сообщений: 13630
mayton
Скорее всего - никак, без понимания внутренней структуры CompactHash.
Если внутри - биткарта - то возможно сложением по модулю 2 (XOR) двух
хешей и подсчетом битов в результате мы получим то что ты хотел. Но это
нарушает инкапсуляцию.


Там просто 16 int полей. Собственно вот в первом посте они все и есть. Поля хранят информацию о цветовой гамме видео файла, нужно понять на сколько один файл по этой гамме близок к другому.
22 апр 20, 15:14    [22120802]     Ответить | Цитировать Сообщить модератору
 Re: Как оптимизировать?  [new]
mayton
Member

Откуда: loopback
Сообщений: 46531
Сразу скажу что java не сильна в таких операциях. Тут как раз был-бы нужен JNI+C и какая-то библиотека
на подобие OpenCV.

А задача твоя может звучит как (примерно) Расстояние Манхеттена на целочисленных векторах. Формула - глупая.
(среднее квадратическое было-бы лучше) тк. на ней слабые компоненты вектора будут полностью
подавлены соседями которые по модулю будут более численно велики. По смыслу это так как будто слабый
синий цвет в численном превосходстве подавляет зеленый хотя субъективно все наоборот.

Да и вообще подобные метрики считают в double а не в int. Там есть хотя-бы какая-то толерантность к малым величинам.

Ябы переписал на JNI/С++

double distanceBetween(double* hash1, double* hash2) {... }
22 апр 20, 15:28    [22120812]     Ответить | Цитировать Сообщить модератору
 Re: Как оптимизировать?  [new]
Hett
Member

Откуда: Бийск, Новосибирск
Сообщений: 13630
mayton

А задача твоя может звучит как (примерно) Расстояние Манхеттена на целочисленных векторах. Формула - глупая.
(среднее квадратическое было-бы лучше) тк. на ней слабые компоненты вектора будут полностью
подавлены соседями которые по модулю будут более численно велики. По смыслу это так как будто слабый
синий цвет в численном превосходстве подавляет зеленый хотя субъективно все наоборот.

Что-то я не догнал, если честно, можно пример?

mayton

Да и вообще подобные метрики считают в double а не в int. Там есть хотя-бы какая-то толерантность к малым величинам.


Есть ли смысл, если данные изначально байтовых массивах и нужно посчитать колличество тех или иных значений?


mayton

Ябы переписал на JNI/С++
double distanceBetween(double* hash1, double* hash2) {... }


Это да, но хотелось бы оставить на последок, я думал может можно как-то математически обыграть.
Вот выше Leonid Kudryavtsev написал, например, нужно будет попробовать понять, но уже не сегодня.
22 апр 20, 16:59    [22120880]     Ответить | Цитировать Сообщить модератору
 Re: Как оптимизировать?  [new]
mayton
Member

Откуда: loopback
Сообщений: 46531
Hett

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

Математически эта формула уже несократима.

Но можно сыграть на командах MMX/SSE/AVX (по первому - Леонид писал).
Но Java это не умеет напрямую делать. Поэтому - JNI. Либо запускать вычисления в много
потоков но в данном конкретном случае (оба вектора очень маленькие)
и шаблоны map/reduce здесь не будут иметь практической пользы.
Потоки просто не успеют разогнаться и сделать join как расчет уже закончен.
Тоесть это все равно что ты решил мешок картошки подвезти на 20 см на тяжелом
траке.

Вот если-бы массивы были хотя-б по мильену...
22 апр 20, 18:05    [22120920]     Ответить | Цитировать Сообщить модератору
 Re: Как оптимизировать?  [new]
Zzz79
Member

Откуда:
Сообщений: 168
Интересно что ты пишешь ,если у тебя такие проблемы))
22 апр 20, 19:10    [22120973]     Ответить | Цитировать Сообщить модератору
 Re: Как оптимизировать?  [new]
забыл ник
Member

Откуда:
Сообщений: 3289
Zzz79
Интересно что ты пишешь ,если у тебя такие проблемы))

По опыту не факт что проблема есть, иногда на энтерпрайзе люди просто придумывают себе задачу
22 апр 20, 20:00    [22120995]     Ответить | Цитировать Сообщить модератору
 Re: Как оптимизировать?  [new]
mayton
Member

Откуда: loopback
Сообщений: 46531
Пусть перевернет поля на 90 градусов. Вот так.

class CompactHash  {
   int[] hash = new int[15];
   ...
}

Опять-же это формулу не меняет но позволяет хотя-бы подойти к векторизации.
22 апр 20, 20:06    [22121001]     Ответить | Цитировать Сообщить модератору
 Re: Как оптимизировать?  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 8552
1) Смотрю на
http://developer.classpath.org/doc/java/lang/Math-source.html

Если это правда, то вполне возможно, что возведение в квадрат (как советовал mayton) будет быстрее, чем условные переходы.

2.1)
На C еще предлагают реализовывать

abs(x) = (x XOR y) - y
where y = x >>> 31 (assuming 32-bit input), and >>> is arithmetic right shift operator.

gcc 4.6.3 generated assembly snippet (AT&T syntax)

movl -8(%rbp), %eax # -8(%rbp) is memory for x on stack
sarl $31, %eax # shift arithmetic right: x >>> 31, eax now represents y
movl %eax, %edx #
xorl -8(%rbp), %edx # %edx = x XOR y
movl %edx, -4(%rbp) # -4(%rbp) is memory for output on stack
subl %eax, -4(%rbp) # (x XOR y) - y

2.2) If you have a fast multiply by +1 and -1, the following will give you abs(x):
((x >>> 30) | 1) * x

и много других способов

https://stackoverflow.com/questions/2639173/x86-assembly-abs-implementation

Но как изобразить на Java где unsigned арифметика через ж... - х.з.
22 апр 20, 20:13    [22121005]     Ответить | Цитировать Сообщить модератору
 Re: Как оптимизировать?  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 8552
Вполне возможно, что уход с int на float так же может быть оправдан. Т.к. будет аппаратная реализация данной инструкции

"In general, computing the absolute-value of a floating-point quantity is an extremely cheap and fast operation." ( C ) интернет

" it, most implementations follow the IEEE-754 standard. In that standard, each floating-point value's representation contains a bit known as the sign bit, and this marks whether the value is positive or negative....Therefore, taking the absolute value basically just amounts to flipping a byte in the value's representation in memory. In particular, you just need to mask off the sign bit (bitwise-AND), forcing it to 0—thus, unsigned."

Скорость не замерял. Нужно не мне.
22 апр 20, 20:22    [22121010]     Ответить | Цитировать Сообщить модератору
 Re: Как оптимизировать?  [new]
mayton
Member

Откуда: loopback
Сообщений: 46531
Да нет же. Не в том суть.

Не быстрее. Точнее. По сути мы считаем гипотенузу в 15 мерном пространстве
между двумя точками-хешами. Это более правильная метрика чем Манхеттен.
22 апр 20, 20:24    [22121013]     Ответить | Цитировать Сообщить модератору
 Re: Как оптимизировать?  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 8552
Если abs сделано через условные переходы..... то 16 переходов, 8 промахов предсказателя переходов... тут хоть возведение в квадрат, хоть квадратный корень, хоть тригонометрические ф-ции - будет совершенно пофиг

Но это нужно иметь доступ к актуальным исходникам + быть уверенным, что ф-ции приведенные в исходниках ровно те же, которые реально используются JVM.

Последнее предложение поясняю: ряд ф-ций хоть и имеют исходники на Java, на самом деле заменяются C-инлайнами реализованными в ядре/JIT.

Я бы подумал, что базовые арифметические функции, по хорошему, авторы Java должны были бы на C в JIT перетащить. Относится ли к этим ф-циям Math.abs - х.з. Смотреть код Open JDK или замерять время, лично мне влом.

Персонально я, взял бы в руки C с inline ассемблером и переписал на MMX. две пары по 3 инструкции (в первых Pentium было два исполняемых блока, т.ч. фактически 3 последовательные инструкции, т.к. две пары будет выполняться на разных процессорных блоках). Все остальное - от лукавого. IMHO & AFAIK На невозможность выполнения на 386, 486 процессорах - думаю в наше время можно забить.
22 апр 20, 20:38    [22121022]     Ответить | Цитировать Сообщить модератору
 Re: Как оптимизировать?  [new]
mayton
Member

Откуда: loopback
Сообщений: 46531
Мне кажется что в формуле Хетта слишком много ненужного полиморфизма.
Он не дает оптимизатору видеть что собственно мы работаем с двумя векторами.
Эти getters... чорт бы их побрал.
22 апр 20, 20:41    [22121026]     Ответить | Цитировать Сообщить модератору
 Re: Как оптимизировать?  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 8552
mayton

Мне кажется Вы излишне оптимистично относитесь к JIT

Его тоже разрабатывали наши коллеги-программисты. Коллегам нужно доверять.
22 апр 20, 20:47    [22121029]     Ответить | Цитировать Сообщить модератору
 Re: Как оптимизировать?  [new]
mayton
Member

Откуда: loopback
Сообщений: 46531
В плане correctness, я доверяю им на 100%

А вот в части simd или векторизации... Тут даже не вопрос доверия. А скорее - понимания предназначения.
22 апр 20, 21:12    [22121046]     Ответить | Цитировать Сообщить модератору
 Re: Как оптимизировать?  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 10171
Leonid Kudryavtsev
Но как изобразить на Java где unsigned арифметика через ж... - х.з.
Есть знаковый и логический сдвиг вправо, поэтому не надо делать unsigned для логического сдвига и проверять, что сдвиг знаковых - точно арифметический.
23 апр 20, 04:57    [22121168]     Ответить | Цитировать Сообщить модератору
Все форумы / Java Ответить