немного вертится в Java - разложение долго в длинные [] битовых масок

Question

Я разлагаю одну длинную на длинную [] однобитовых длин на

public static int decompose(long[] buffer, long base) {
  int count = Long.bitCount(base);
  for (int i=0; i<count; i++) {
    base ^= (buffer[i] = Long.lowestOneBit(base));
  }
  return count;
}

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

Есть предложения?Я знаком с заклинанием преждевременной оптимизации, поэтому я больше не продвигаю свое решение в свое время, но, возможно, кто-то еще видел это раньше или пристрастился к оптимизации ... РЕДАКТИРОВАТЬ: пожалуйста, просмотрите любые предложения через Испытательный жетон Марка приведена ниже .Я более чем удивлен, что мое первое подозрение фактически удерживает.

тестовый код, который находится внутри метода JUnit:

Random rng = new Random();
long size = 0;
long[] hold = new long[Long.SIZE];
System.out.println("init:"+Long.toBinaryString(BitTwiddling.bitmask(rng.nextInt(Long.SIZE)))); //initialize BitTwiddling internals
long start = System.currentTimeMillis();
for (int i=0; i<compareIterations; i++) size+= BitTwiddling.decompose(hold,rng.nextInt(Integer.MAX_VALUE));
long delta = System.currentTimeMillis() - start;
double base = (double)size/delta;

size = 0;
start = System.currentTimeMillis();
for (int i=0; i<compareIterations; i++) size += BitTwiddling.decomposeAlt(hold, rng.nextInt(Integer.MAX_VALUE));
long delta2 = System.currentTimeMillis() - start;
double base2 = (double)size/delta2;

, затем сравните base и base2

Answer 1

Хорошо, после долгих и трудных попыток побить ваш исходный код, я нашел тот, который постоянно бьет ваш (в моей среде), бесстыдно крадя ваш код и подправляя его.

    protected int decompose(long[] buffer, long base) {
        int count = Long.bitCount(base);
        for (int i = 0; i < count; i++) {
            base -= (buffer[i] = Long.lowestOneBit(base));
        }
        return count;
    }

Единственное отличие: используется вычитаниевместо хор.Я не думаю, что есть какие-либо крайние случаи;Я конечно не нашел ни одного.Не знаю, почему они не оптимизированы для одной и той же вещи (при условии, что не являются крайними случаями), но это делает мой процесс постоянно быстрее (опять же, на моей машине).Я добавил эту версию в тестовый ответ.

Редактировать Я думаю, причина, по которой его нельзя оптимизировать, заключается в том, что компилятор не знает, что операнд всегда будет меньшеbase (так как мы переходим от младших битов к старшим).

Edit # 2 С установленным флагом -server у Карла неизменно немного быстрее, чем у меня снова.

Редактировать # 3 Да, конечно, при запуске на 64-битной JVM это значительно быстрее:

    protected int decompose(long[] buffer, long base) {
        int count = 0;
        while ( 0 != (base -= (buffer[count++] = Long.lowestOneBit(base))));
        return count;
    }

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

Answer 2

Вот тот жгут, который я сейчас использую. Я последовательно получаю код в вопросе (метод 1) для выполнения значительно быстрее. В настоящее время ответ Марка Петерса обычно самый быстрый, но Карл быстрее с установленным флагом -server. Кроме того, Mikera становится значительно более конкурентоспособным в режиме сервера (хотя все же медленнее, чем Carl / Mark).

import java.util.Random;

public abstract class Harness {
    public static void main(String[] args) {
        while (true) {
            long[] randomData = new long[4096];
            Random r = new Random();
            for (int i = 0; i < randomData.length; i++) {
                randomData[i] = r.nextLong();
            }
            long[] buffer = new long[64];

            Harness[] versions = new Harness[] {
                    new Control(randomData, buffer),
                    new Carl(randomData, buffer),
                    new MarkPeters(randomData, buffer),
                    new MarkPetersServer64Bit(randomData, buffer),
//                    new Rsp1(randomData, buffer), 
                    new Rsp2(randomData, buffer),
                    new Mikera(randomData, buffer)
                    };
            for (Harness v : versions) {
                v.doTest();
            }
        }
    }

    private final long[] buffer;
    private final long[] randomData;

    protected Harness(long[] randomData, long[] buffer) {
        this.randomData = randomData;
        this.buffer = buffer;
    }

    public void doTest() {
        long start = System.nanoTime();
        long count = 0;
        for (int times = 0; times < 1000; times++) {
            for (int i = 0; i < randomData.length; i++) {
                count = decompose(buffer, randomData[i]);
            }
        }
        long end = System.nanoTime();

        //verify decomposition of last item
        long l = 0;
        for ( int i = 0; i < count; i++ ) {
            l |= buffer[i];
        }

        System.out.println(getClass().getSimpleName() + " took " + (end - start)
                / 1000000.0 + " ms - last base: " + l);
    }

    protected abstract int decompose(long[] buffer, long base);

    private static class Control extends Harness {
        protected Control(long[] randomData, long[] buffer) {
            super(randomData, buffer);
        }

        @Override
        protected int decompose(long[] buffer, long base) {
            return 0;
        }
    }

    private static class Carl extends Harness {
        protected Carl(long[] randomData, long[] buffer) {
            super(randomData, buffer);
        }

        @Override
        protected int decompose(long[] buffer, long base) {
            final int count = Long.bitCount(base);
            for (int i = 0; i < count; i++) {
                base ^= (buffer[i] = Long.lowestOneBit(base));
            }
            return count;
        }
    }

    private static class Mikera extends Harness {
        protected Mikera(long[] randomData, long[] buffer) {
            super(randomData, buffer);
        }

        @Override
        protected int decompose(long[] buffer, long base) {
            int count = 0;
            while (base != 0) {
                long mask = base & (-base);
                base &= ~mask;
                buffer[count++] = mask;
            }
            return count;
        }
    }

    private static class Rsp1 extends Harness {
        protected Rsp1(long[] randomData, long[] buffer) {
            super(randomData, buffer);
        }

        @Override
        protected int decompose(long[] buffer, long base) {
            int count = 0;

            if (0 != (base & 1)) {
                buffer[count++] = 1;
            }

            base >>>= 1;

            for (long bit = 1; 0 < bit && bit <= base; ) {
                if (0 < (base & bit)) {
                    buffer[count++] = (bit <<= 1);
                }
            }
            return count;
        }
    }

    private static class Rsp2 extends Harness {
        protected Rsp2(long[] randomData, long[] buffer) {
            super(randomData, buffer);
        }

        @Override
        protected int decompose(long[] buffer, long base) {
            int count = 0;

            for (long bit = 1; 0 != base; bit <<= 1, base >>>= 1) {
                if (0 < (base & 1)) {
                    buffer[count++] = bit;
                }
            }
            return count;
        }
    }

    private static class MarkPeters extends Harness {
        protected MarkPeters(long[] randomData, long[] buffer) {
            super(randomData, buffer);
        }

        @Override
        protected int decompose(long[] buffer, long base) {
            int count = Long.bitCount(base);
            for (int i = 0; i < count; i++) {
                base -= (buffer[i] = Long.lowestOneBit(base));
            }
            return count;

        }
    }

    private static class MarkPetersServer64Bit extends Harness {
        protected MarkPetersServer64Bit(long[] randomData, long[] buffer) {
            super(randomData, buffer);
        }

        @Override
        protected int decompose(long[] buffer, long base) {
            int count = 0;
            while ( 0 != (base ^= (buffer[count++] = Long.lowestOneBit(base))));
            return count;
        }
    }
}

Пример вывода

Какой метод лучше всего зависит от ситуации.

Несерверная 32-битная JVM

Control took 41.175272 ms - last base: 0
Carl took 691.966919 ms - last base: 5852835112840111303
MarkPeters took 642.230253 ms - last base: 5852835112840111303
MarkPetersServer64Bit took 742.594626 ms - last base: 5852835112840111303
Rsp2 took 3886.203787 ms - last base: 5852835112840111303
Mikera took 1044.451494 ms - last base: 5852835112840111303

Победитель: MarkPeters

Сервер, 32-битная JVM

Control took 2.354383 ms - last base: 0
Carl took 508.687401 ms - last base: 338317437500027646
MarkPeters took 521.831297 ms - last base: 338317437500027646
MarkPetersServer64Bit took 727.052206 ms - last base: 338317437500027646
Rsp2 took 3811.75662 ms - last base: 338317437500027646
Mikera took 665.252599 ms - last base: 338317437500027646

Победитель: Карл

Сервер (неявный или явный), 64-битная JVM

Control took 0.007186 ms - last base: 0
Carl took 543.701859 ms - last base: -8898262206218882664
MarkPeters took 439.706079 ms - last base: -8898262206218882664
MarkPetersServer64Bit took 391.831055 ms - last base: -8898262206218882664
Rsp2 took 1861.40449 ms - last base: -8898262206218882664
Mikera took 435.964319 ms - last base: -8898262206218882664

Победитель: MarkPetersServer64Bit

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

Доступны ли режимы -client и -server VM в 64-битной Java?

В настоящее время только виртуальная машина Java HotSpot Server поддерживает 64-битную операцию, а опция -server неявно используется с -d64. Это может быть изменено в будущем выпуске.

Answer 3

Так как я люблю оптимизацию *, вот версию, которую вы могли бы попробовать вместо этого:

public static int decompose(long[] buffer, long base) {
    int count = 0;
    while (base != 0) {
        long mask = base & (-base);
        base &= ~mask;
        buffer[count++] = mask;
    }
    return count;
}

Основные вещи, которые я сделал, были:

• Встроенные вычисления младшего бита, чтобы избежатьнакладные расходы на вызов метода.Это может быть победой в (редких, но возможных) случаях, когда компилятор / JVM не достаточно умен, чтобы сделать это для вас ....
• Передайте массив long в качестве входного параметра, чтобы избежатьраспределение памяти и необходимость подсчета битов для определения размера массива.Функция теперь возвращает количество найденных битовых масок.
• Обнуляйте биты по мере продвижения, чтобы вы могли как можно раньше выйти из цикла

*, потому что это весело, независимо от того, преждевременен он или нет

Answer 4

Как насчет этой версии?

public static int decompose(long[] buffer, long base) {
    int count = 0;

    if (0 != (base & 1)) {
        buffer[count++] = 1;
    }

    base >>>= 1;

    for (long bit = 1; 0 < bit && bit <= base; ) {
        if (0 < (base & bit)) {
            buffer[count++] = (bit <<= 1);
        }
    }
    return count;
}

Знаковый бит базы усложняет конечное условие в этом случае, поэтому мы предотвращаем это, «корректируя» базовое значение в начале.

В качестве альтернативы вместо проверки битовой маски по сравнению с базой, мы можем сместить саму базу:

public static int decompose(long[] buffer, long base) {
    int count = 0;

    for (long bit = 1; 0 != base; bit <<= 1, base >>>= 1) {
        if (0 < (base & 1)) {
            buffer[count++] = bit;
        }
    }
    return count;
}

Answer 5

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

for (int i= 0; i < result.length; i++)
    result[i]= base & (1<<i);

Должно быть четким и быстрым.