CAS and idling

AtomicDecUntilZeroMain.java

package ru.inlinetelecom.vn2.util;

import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicLong;

/**
 * вариант с uncontended lock (getAvailableProcessors >= worker_count
 */
public class AtomicDecUntilZeroMain {

    // счетчик холостого хода
    private static AtomicLong idlingCounter = new AtomicLong(0);

    /**
     * 1) вызывается из многих потоков
     * 2) не должно быть меньше 0
     * 3) если уже 0 и вызывают этот метод, то должно оставаться 0
     *
     * @param counter
     * @return 0 or value after decrement
     */
    private static int decUntilZero(AtomicInteger counter) {
        while (true) {
            int current = counter.get();
            if (current == 0) {
                return current;
            }
            int next = current - 1;
            if (counter.compareAndSet(current, next)) {
                return next;
            }

            idlingCounter.incrementAndGet();
        }
    }

    public static void main(String[] args) throws InterruptedException {

        final int initialValue = 400000000;
        final int countOfThreads = 4; // всего потоков
        final int countOfDecPerThread = initialValue/countOfThreads; // количество декрементов на один поток

        final AtomicInteger counter = new AtomicInteger(initialValue);

        ExecutorService executor = Executors.newFixedThreadPool(countOfThreads);

        long startedAt = System.currentTimeMillis();

        final CountDownLatch latch = new CountDownLatch(countOfThreads);

        for (int i = 0; i < countOfThreads; i++) {
            executor.execute(new Runnable() {
                @Override
                public void run() {
                    for (int i = 0; i < countOfDecPerThread; i++) {
                        decUntilZero(counter);
                    }
                    latch.countDown();
//                    System.out.println("task in progress..." + (latch.getCount()));
                }
            });
        }

        System.out.println("всех ждёмс, однако...");
        latch.await();
        long elapsed = System.currentTimeMillis() - startedAt;
        executor.shutdown(); // за ненадобностью более!
        System.out.println("Ну наконец-ТА дождалИСА!!! Урра товариСЧи, уРРа!");

        System.out.println("================================================");
        int now = counter.get();
        System.out.println("== INPUT DATA");
        System.out.println(String.format("%s: %d", "initial         ", initialValue));
        System.out.println(String.format("%s: %d", "threads         ", countOfThreads));
        System.out.println(String.format("%s: %d", "dec per threads ", countOfDecPerThread));
        System.out.println("== RESULTS");
        System.out.println(String.format("%s: %d", "еще осталось    ", now));
        System.out.println(String.format("%s: %d", "раз выполнилось ", (initialValue - now)));
        System.out.println(String.format("%s: %d", "холостых ходов  ", idlingCounter.get()));
        System.out.println(String.format("%s: %s", "elapsed, millis ", elapsed));
    }

}

Немало так получилось 89M холостых ходов на 100M декрементов!
Вот мои результаты:

== INPUT DATA
initial : 100000000
threads : 100
dec per threads : 1000000
== RESULTS
еще осталось : 0
раз выполнилось : 100000000
холостых ходов : 89389160
elapsed, millis : 5180

Интересно посмотреть сколь времени уйдет на:

• вариант с uncontended lock (getAvailableProcessors >= worker_count
• вариант с high contended lock (processors << worker_count)
• вариант с uncontended CAS
  Всюду посмотреть CPU load (через htop/atop).

Профиль

OS
Microsoft Windows [Version 6.1.7601]

Java version
java version "1.7.0_40"
Java(TM) SE Runtime Environment (build 1.7.0_40-b43)
Java HotSpot(TM) 64-Bit Server VM (build 24.0-b56, mixed mode)

CPU
Intel® Core™ i7-2620M Processor (2 Cores, 4 Threads)
http://ark.intel.com/products/52231/Intel-Core-i7-2620M-Processor-4M-Cache-up-to-3_40-GHz

Результаты тестов

#1 thread, вообще нет конкуренции

== INPUT DATA
initial : 400000000
threads : 1
dec per threads : 400000000
== RESULTS
еще осталось : 0
раз выполнилось : 400000000
холостых ходов : 0
elapsed, millis : 4725

#2 threads

== INPUT DATA
initial : 400000000
threads : 2
dec per threads : 200000000
== RESULTS
еще осталось : 0
раз выполнилось : 400000000
холостых ходов : 205356286
elapsed, millis : 13263

#3 threads

== INPUT DATA
initial : 400000000
threads : 3
dec per threads : 133333333
== RESULTS
еще осталось : 1
раз выполнилось : 399999999
холостых ходов : 300681635
elapsed, millis : 18900

#4 threads

== INPUT DATA
initial : 400000000
threads : 4
dec per threads : 100000000
== RESULTS
еще осталось : 0
раз выполнилось : 400000000
холостых ходов : 339373614
elapsed, millis : 19900

#10 threads

== INPUT DATA
initial : 400000000
threads : 10
dec per threads : 40000000
== RESULTS
еще осталось : 0
раз выполнилось : 400000000
холостых ходов : 327095618
elapsed, millis : 19246

#100 threads

== INPUT DATA
initial : 400000000
threads : 100
dec per threads : 4000000
== RESULTS
еще осталось : 0
раз выполнилось : 400000000
холостых ходов : 374434253
elapsed, millis : 21138

#1000 threads

== INPUT DATA
initial : 400000000
threads : 1000
dec per threads : 400000
== RESULTS
еще осталось : 0
раз выполнилось : 400000000
холостых ходов : 361086230
elapsed, millis : 20960

#10000 threads

== INPUT DATA
initial : 400000000
threads : 10000
dec per threads : 40000
== RESULTS
еще осталось : 0
раз выполнилось : 400000000
холостых ходов : 334843139
elapsed, millis : 19845

#100000 threads

пришлось перезагружаться... (

могу запустить на 24 ядрах

atop - это средство сбора данных о работе системы (типа top, но с возможность просмотра исторической статистики)
посмотри man atop
установи его sudo apt-get install atop
затем запусти сбор данных atop -w atop.log -S 1 (раз в секунду)
собирай данные в момент запуска своих экспериментов
после проведения эксперимента останови сбор статистики atop
и теперь ты можешь читать данные по использованию системных ресурсов из файла atop.log
это бинарный файл - его читать нужно через atop -r atop.log
листать посекундные отчеты можно с помощью интерактивной навигации - клавишы t и T
можешь например отрисовать график средней загрузки системы с помощью gnuplot
скрипт тут https://gist.github.com/LexaChebara/9951340
например cpl.sh atop.log

вообще неплохо бы исследования оформить графиком

кол-во холостых ходов лучше не в абсолютных величинах, а в относительных. например, в процентах от величины initialValue

да я о процентах уже подумал, улучу

какая версия jdk?

Profile

java version "1.7.0_40"
Java(TM) SE Runtime Environment (build 1.7.0_40-b43)
Java HotSpot(TM) 64-Bit Server VM (build 24.0-b56, mixed mode)

Linux 2.6.38-13-server #57 SMP Sun Feb 19 22:11:49 UTC 2012 x86_64 GNU/Linux

2 x Intel(R) Xeon(R) CPU E5645 @ 2.40GHz, т.е. 12 hardware cpu core или 24 потока

Results

Initial value - 400 000 000

Pool size	Ops per thread	Final value	Op count	Misses count	Time elapsed, ms
4	100 000 000	0	400 000 000	105 621 882	23 303
24	16 666 666	16	399 999 984	367 097 933	40 331
100	4 000 000	0	400 000 000	383 702 094	41 787

Интрересно, почему время увеличилось в 2 раза?

Время увеличилось в 2 раза вот почему.
Кол-во промахов стало в 3 раза больше.
Кол-во одновременно работающих потоков (так как 12 ядер) стало в 3 раза больше, а, следовательно, конфликтов стало больше. Вероятность конфликта растет с количеством одновременно работающих потоков. Операция cmpxchg блокирует шину данных при чтении из памяти.