VPF::Синхронизированные и не -"-"- коллекции

Greg

Дата 8.6.2008, 19:26 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 158
Регистрация: 16.9.2006
Где: Беларусь, г.Минск

Репутация: 1
Всего: 7

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

Код


        int len = 500000;
        int seed = 8;
        long startTime, endTime, duration;

        RandomArray ra1 = new RandomArray(len, seed);
        RandomArray ra2 = new RandomArray(len, seed);       

        List<Integer> usualList = ra1.getList();
        List<Integer> synchList = Collections.synchronizedList(ra2.getList());// ra2.getList();

        startTime = System.currentTimeMillis();
        Collections.sort(usualList);
        endTime = System.currentTimeMillis();
        duration = endTime - startTime;
        System.out.println("sort of usual list: " + duration + " ms");

        startTime = System.currentTimeMillis();
        Collections.sort(synchList);
        endTime = System.currentTimeMillis();
        duration = endTime - startTime;
        System.out.println("sort of synchronized list: " + duration + " ms");

RandomArray.java:

Код


import java.util.LinkedList;
import java.util.List;
import java.util.Random;

public class RandomArray {
    private List<Integer> loi;
    private int[] arr;

    public RandomArray(int len, long seed) {
        Random rand = new Random(seed);
        this.arr = new int[len];
        loi = new LinkedList<Integer>();
        for (int i = 0; i < len; i++) {
            int j = rand.nextInt();
            arr[i] = j;
            loi.add(j);
        }
    }

    public int[] getArray() {
        return arr;
    }

    public List<Integer> getList() {
        return loi;
    }
}

Я получил результаты:

Код


sort of usual list: 1391 ms
sort of synchronized list: 1422 ms
-------
sort of usual list: 1407 ms
sort of synchronized list: 1500 ms
-------
sort of usual list: 1344 ms
sort of synchronized list: 1453 ms

Заменяя строку 9 первого листинга получаю приблизительно тоже:

Код


sort of usual list: 1375 ms
sort of synchronized list: 1422 ms

Получается, что этим методом не получается убедиться в правильности заключения ? Почему так и как надо ?

Это сообщение отредактировал(а) Greg - 8.6.2008, 20:19

--------------------

Страх перед возможностью ошибки не должен отвращать нас от поисков истины.

Platon

Дата 8.6.2008, 20:09 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1801
Регистрация: 25.4.2006

Репутация: 16
Всего: 40

В общем что я имею:

Цитата

sort of usual list: 1969 ms
sort of usual list: 2047 ms
sort of usual list: 1796 ms
sort of usual list: 2000 ms
sort of usual list: 1813 ms
sort of usual list: 1969 ms
sort of usual list: 1844 ms
sort of usual list: 2078 ms
sort of usual list: 2125 ms
sort of usual list: 2000 ms
AVG sort of usual list: 1964
sort of synchronized list: 2079 ms
sort of synchronized list: 2062 ms
sort of synchronized list: 1968 ms
sort of synchronized list: 2032 ms
sort of synchronized list: 1984 ms
sort of synchronized list: 1953 ms
sort of synchronized list: 2047 ms
sort of synchronized list: 2031 ms
sort of synchronized list: 2000 ms
sort of synchronized list: 1985 ms
AVG sort of synchronized list: 2014

Если оба списка несинхронизированные

Цитата

sort of usual list: 1937 ms
sort of usual list: 2000 ms
sort of usual list: 1875 ms
sort of usual list: 1985 ms
sort of usual list: 1843 ms
sort of usual list: 1968 ms
sort of usual list: 1828 ms
sort of usual list: 1984 ms
sort of usual list: 1844 ms
sort of usual list: 1984 ms
AVG sort of usual list: 1924
sort of synchronized list: 1829 ms
sort of synchronized list: 2015 ms
sort of synchronized list: 1797 ms
sort of synchronized list: 1890 ms
sort of synchronized list: 1922 ms
sort of synchronized list: 1938 ms
sort of synchronized list: 1844 ms
sort of synchronized list: 2000 ms
sort of synchronized list: 1860 ms
sort of synchronized list: 1953 ms
AVG sort of synchronized list: 1904

Весьма занимательно.

Это сообщение отредактировал(а) Platon - 8.6.2008, 20:36

--------------------

Блог на винграде
Мой Блог о Java
For Java developers... only

Platon

Дата 8.6.2008, 20:41 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1801
Регистрация: 25.4.2006

Репутация: 16
Всего: 40

А вообще стоит глянуть реализацию Collections.sort()

Код


Object[] a = list.toArray();
    Arrays.sort(a);
    ListIterator<T> i = list.listIterator();
    for (int j=0; j<a.length; j++) {
        i.next();
        i.set((T)a[j]);
    }

И Collections.SynchronizedList.listIterator()

Код


public ListIterator<E> listIterator() {
        return list.listIterator(); // Must be manually synched by user
        }

--------------------

Блог на винграде
Мой Блог о Java
For Java developers... only

ivg

Дата 8.6.2008, 20:54 (ссылка)

(нет голосов)

Загрузка ...

Autonomous R&D

Профиль
Группа: Участник
Сообщений: 686
Регистрация: 8.2.2006
Где: Екатеринбург

Репутация: 33
Всего: 81

Цитата(Platon @ 8.6.2008, 23:41

)

А вообще стоит глянуть реализацию Collections.sort()

Точно. Полезное занятие. smile

Greg, замените sort() на reverse() и "почувствуйте разницу ©"

Greg

Дата 8.6.2008, 22:57 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 158
Регистрация: 16.9.2006
Где: Беларусь, г.Минск

Репутация: 1
Всего: 7

Platon, верно вы подметили - зря не посмотрел исходник. Удивлен, признаться, не ожидал увидеть такой контент метода smile

ivg, заменил попробовал и не почувствовал. Короче, прогу модифицировал - будем тестить синхронизированный и не синхронизированный метод add():

Код


    long len = 500000;
        List<Integer> usualList = new ArrayList<Integer>();
        List<Integer> synchList = Collections.synchronizedList(usualList);

        while (true) {
            add2ListAvgTimeout("ArrayList", usualList, len, 1);
            add2ListAvgTimeout("synch ArrayList", synchList, len, 1);
            //add2ListAvgTimeout("synch ArrayList", usualList, len, 1);                    
        }
    }

    public static void add2ListAvgTimeout(String name, List<Integer> list, long len, int iter) {
        long[] res = new long[iter];
        for (int i = 0; i < iter; i++) {
            System.gc();
            res[i] = add2ListTimeout(list, len);
        }

        long s = 0;
        for (long i : res) {
            s += i;
        }
        float rez = s/iter;
        System.out.println(name + ": " + rez + " ms");
    }
    public static long add2ListTimeout(List<Integer> list, long len) {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < len; i++) {
            list.add(32768);
        }
        long endTime = System.currentTimeMillis();
        return endTime - startTime;
    }

Результаты:

Код


ArrayList: 375.0 ms
synch ArrayList: 266.0 ms
ArrayList: 125.0 ms
synch ArrayList: 156.0 ms
ArrayList: 141.0 ms
synch ArrayList: 94.0 ms
ArrayList: 203.0 ms
synch ArrayList: 47.0 ms
ArrayList: 47.0 ms
synch ArrayList: 32.0 ms
ArrayList: 171.0 ms
synch ArrayList: 46.0 ms
ArrayList: 32.0 ms
synch ArrayList: 47.0 ms
ArrayList: 31.0 ms
synch ArrayList: 281.0 ms
ArrayList: 32.0 ms
synch ArrayList: 31.0 ms

После замены строки 7 на 8:

Код


ArrayList: 453.0 ms
synch ArrayList: 343.0 ms
ArrayList: 156.0 ms
synch ArrayList: 156.0 ms
ArrayList: 156.0 ms
synch ArrayList: 94.0 ms
ArrayList: 219.0 ms
synch ArrayList: 32.0 ms
ArrayList: 31.0 ms
synch ArrayList: 15.0 ms
ArrayList: 172.0 ms
synch ArrayList: 31.0 ms
ArrayList: 31.0 ms
synch ArrayList: 32.0 ms
ArrayList: 31.0 ms
synch ArrayList: 265.0 ms
ArrayList: 31.0 ms
synch ArrayList: 31.0 ms
ArrayList: 31.0 ms
synch ArrayList: 31.0 ms
ArrayList: 46.0 ms
synch ArrayList: 31.0 ms
ArrayList: 375.0 ms

Почему метод add() ArrayList работает медленнее чем его синхронизированный аналог ?

--------------------

Страх перед возможностью ошибки не должен отвращать нас от поисков истины.

ivg

Дата 8.6.2008, 23:37 (ссылка)

(нет голосов)

Загрузка ...

Autonomous R&D

Профиль
Группа: Участник
Сообщений: 686
Регистрация: 8.2.2006
Где: Екатеринбург

Репутация: 33
Всего: 81

Цитата(Greg @ 9.6.2008, 01:57

)

заменил попробовал и не почувствовал

Забыл добавить, что в первом случае надо заменить LinkedList на ArrayList, тогда Collections.reverse() работает по другому алгоритму, который и обеспечивает множество вызовов синхронизированных методов. У меня разница в три с копейками раза.

Цитата(Greg @ 9.6.2008, 01:57

)

Короче, прогу модифицировал - будем тестить синхронизированный и не синхронизированный метод add()

У вас один и тотже List используется. Куча времени уходит на выделение и копирование блоков памяти при росте списка, и всё это в методе add(). С точки зрения чистоты эксперимента он не подходит.

w38

Дата 9.6.2008, 11:58 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 8
Регистрация: 4.12.2006
Где: Украина, Одесса

Репутация: нет
Всего: нет

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

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Java: Общие вопросы \| Следующая тема »