/**
* Генератор последовательности простых чисел.
* Используется экземплярами PrimeNumber для получения простых чисел и проверки на простоту.
* В единичном экземпляре хранит последовательность сгенерированных простых чиселю
* */
private static class PrimeNumberGenerator
{
/**
* Шаг возрастания размера массива простых чисел
* */
private static final int ADD_ARRAY_LENGTH_STEP = 10;
/**
* Массив простых чисел
* */
long[] numbers;
/**
* Количество сгенерированных простых чисел
* */
int numbersCount;
/**
* Инициализация генератора
* */
public PrimeNumberGenerator()
{
assert ADD_ARRAY_LENGTH_STEP > 0 : "ADD_ARRAY_LENGTH_STEP > 0";
numbers = new long[ADD_ARRAY_LENGTH_STEP];
numbers[0] = 2;
numbersCount = 1;
}
/**
* Возвращает i-тое по порядку простое число
* */
private long get(int i)
throws PrimeNumberException
{
while (numbersCount <= i) {
calculateNextNumber(numbersCount);
}
return numbers;
}
/**
* Записывает следующее после i-того по счету простое число
* в массыв numbers. (поэтому synchronized)
* */
private synchronized void calculateNextNumber(int i)
throws PrimeNumberException
{
assert i <= numbersCount : "i <= numbersCount";
if (i == numbersCount) {
if (numbersCount == numbers.length)
arrayIncrease();
numbers[numbersCount] = calculateNextNumber();
numbersCount++;
}
}
/**
* Находит и возвращает следующее простое число
* */
private long calculateNextNumber()
throws PrimeNumberException
{
long c = numbers[numbersCount - 1];
do {
if (c == Long.MAX_VALUE)
throw new PrimeNumberException("Next prime number out of range for long type.");
c++;
} while (findDividerAmongFoundsPrimeNumbers(c));
return c;
}
/**
* Ищет делитель числа number среди найденных простых чисел.
* */
private boolean findDividerAmongFoundsPrimeNumbers(long number){
boolean result = false;
long sqrtC = (long)Math.sqrt(number);
for (int i = 0; i < numbersCount && numbers <= sqrtC; i++){
if (number % numbers == 0) {
result = true;
break;
}
}
return result;
}
/**
* Увеличивает массив для хранения простых чисел
* */
private void arrayIncrease()
throws PrimeNumberException
{
if (numbers.length == Integer.MAX_VALUE)
throw new PrimeNumberException("Prime number count is maximal");
long newlen = numbers.length;
newlen += ADD_ARRAY_LENGTH_STEP;
newlen = Math.min(newlen, (long)Integer.MAX_VALUE);
long[] newarr = new long[(int)newlen];
System.arraycopy(numbers, 0, newarr, 0, numbers.length);
numbers = newarr;
}
..............................
}
Синхронизация единого кеша между потоками
[color=red]Перенесено из темы Singleton - зло или добро?.[/color]
Или другой пример: мне "дешевле" иметь несколько небольших кешей, чем реализовывать синхронизацию доступа между несколькими потоками. Кстати, очень жизненная ситуация.
Цитата: Green
Или другой пример: мне "дешевле" иметь несколько небольших кешей, чем реализовывать синхронизацию доступа между несколькими потоками. Кстати, очень жизненная ситуация.
Жизненная. Но не в моем случае.
У меня синхронизировать надо только добавление нового простого числа в кеш. Такая ситуация случится если два потока одновременно запросят простое число которое еще не найдено.
Если один поток запрашивает ненайденное число а другой число поменьше (оно у нас уже есть) то для первого визовется синхронизирований метод поиска нового числа в PrimeNumberGenerator а второй просто отдаст число из кеша несинхронизированым методом.
Цитата: Rebbit
Жизненная. Но не в моем случае.
У меня синхронизировать надо только добавление нового простого числа в кеш. Такая ситуация случится если два потока одновременно запросят простое число которое еще не найдено.
Если один поток запрашивает ненайденное число а другой число поменьше (оно у нас уже есть) то для первого визовется синхронизирований метод поиска нового числа в PrimeNumberGenerator а второй просто отдаст число из кеша несинхронизированым методом.
У меня синхронизировать надо только добавление нового простого числа в кеш. Такая ситуация случится если два потока одновременно запросят простое число которое еще не найдено.
Если один поток запрашивает ненайденное число а другой число поменьше (оно у нас уже есть) то для первого визовется синхронизирований метод поиска нового числа в PrimeNumberGenerator а второй просто отдаст число из кеша несинхронизированым методом.
Синхронизировать все же придется получение и нового и уже кешированных значений, т.к. для того, чтоб узнать, закешированно ли уже значение, тебе надо на некоторое время захватить кеш.
Цитата: Green
Синхронизировать все же придется получение и нового и уже кешированных значений, т.к. для того, чтоб узнать, закешированно ли уже значение, тебе надо на некоторое время захватить кеш.
Нет под рукой своего кода. Завтра покажу.
Простые числа константны Кеш хранится в генераторе. То что уже попало в кеш доступно только для чтения (засобами генератора). Также генератор знает количество чисел в кеше. Индексом простого числа есть его порядковый номер. Если номер запрашиваемого числа меньше заполненого кеша то генератор возвращает его и синхронизация не нужна.
Увеличение числа закешированых елементов происходит только после добавления в кеш.
Метод который ищет новое число (единственный синхронизированый) получает на вход его номер. Возможна ситуация что он 2 раза вызовется для одного номера простого числа, но тогда одним ифом просто остановится. Я завтра покажу код. Думаю он надежен. Если нет тоже хорошо - значит дыру исправлю
После твоего поста напугался что прокололся.
Числа хранятся в простом приватном масиве генератора. Если его длинна исчерпана то выделяется новое место и масив переносится. Вот тут и прокол мог быть. Ищем новое число, оно не помещается, один поток переносит масив, а второй обращается еще к старому. Но нет. В момент изменения указателя на массив чисел новая копия уже существует а до етого старая копия цела и невредима.
Или межет случится что ОС передаст управление другому потоку переписав только половину адреса ? Я не знаю таких деталей.
Проколов может быть много разных в тех местах, где транзакции не атомарны.
Например, допустим, что генератор посчитал новое число. Он должен добавить его в кеш и увеличить счетчик кеша.
Допустим, обрашение к кешу из другого потока произошло в момент между занесением числа в кеш и инкрементом счетчика. Что тогда произойдет в твоем коде?
Например, допустим, что генератор посчитал новое число. Он должен добавить его в кеш и увеличить счетчик кеша.
Допустим, обрашение к кешу из другого потока произошло в момент между занесением числа в кеш и инкрементом счетчика. Что тогда произойдет в твоем коде?
Даю часть генератора (Java)
Полностю код тут
Теперь по вопросу "что произойдет". Потестить не успел, но предпологаю что случится следующее.
В кеше уже будет новое число но второй поток об етом еще не узнает.
Он войдет в
long get(int i).
Тут если запрашиваем чтото уже найденное (но не последнее для которого щетчик еще не изменен) оно сразу и возвратится, если последнее найденное для которого щетчик еще не изменен -
второй поток попытается войти в
private synchronized void calculateNextNumber(int i)
но етот метод синхронизированый. Он же и осуществляет добавление елемента и увеличение щетчика.
Когда етот метод в первом потоке завершится, второй тоже в него войдет, но в нем ничего не произойдет изза
На етот момент numbersCount уже будет коректным и i < numbersCount
В long get(int i).
завершится. По сути просто зря вызвали синхронизированый метод который ничего не сделал. Но такая ситуация когда оба потока будут запрашивать постоянно одни и те же числа не должна случастся часто. При запросе разных чисел проблем не возникнет.
Если я конечно не ошибаюсь.
ЗЫ. А если ошибаюсь - не бейте сильно. Я еще с механизмом синхронизации особо не розбирался.
Код:
Теперь по вопросу "что произойдет". Потестить не успел, но предпологаю что случится следующее.
В кеше уже будет новое число но второй поток об етом еще не узнает.
Он войдет в
long get(int i).
Тут если запрашиваем чтото уже найденное (но не последнее для которого щетчик еще не изменен) оно сразу и возвратится, если последнее найденное для которого щетчик еще не изменен -
второй поток попытается войти в
private synchronized void calculateNextNumber(int i)
но етот метод синхронизированый. Он же и осуществляет добавление елемента и увеличение щетчика.
Когда етот метод в первом потоке завершится, второй тоже в него войдет, но в нем ничего не произойдет изза
Код:
if (i == numbersCount) {
В long get(int i).
Код:
while (numbersCount <= i)
Если я конечно не ошибаюсь.
ЗЫ. А если ошибаюсь - не бейте сильно. Я еще с механизмом синхронизации особо не розбирался.
Прежде чем сказать о синхронизации немножко о коде.
Перефразируя, "Пишешь на Java - используй Java" ;).
Бинарный поиск по массиву есть в классе-сервисе java.util.Arrays.
Потом, зачем использование именно массива в этом коде? Это загромождает код, так как отдельно приходится отслеживать изменение размера массива - притом, ты заводишь отдельную переменную класса int numbersCount, для этого отслеживания.
Но главное - ты каждые 10 шагов создаешь НОВЫЙ массив, и переписываешь туда старый! Зачем??
Тебе надо что - коллекцию с быстрым добавлением элемента в конец ее, и с быстрым поиском по ней.
Можно использовать ArrayList<Long>, например.
Перефразируя, "Пишешь на Java - используй Java" ;).
Бинарный поиск по массиву есть в классе-сервисе java.util.Arrays.
Потом, зачем использование именно массива в этом коде? Это загромождает код, так как отдельно приходится отслеживать изменение размера массива - притом, ты заводишь отдельную переменную класса int numbersCount, для этого отслеживания.
Но главное - ты каждые 10 шагов создаешь НОВЫЙ массив, и переписываешь туда старый! Зачем??
Код:
/**
* Увеличивает массив для хранения простых чисел
* */
private void arrayIncrease()
throws PrimeNumberException
{
if (numbers.length == Integer.MAX_VALUE)
throw new PrimeNumberException("Prime number count is maximal");
long newlen = numbers.length;
newlen += ADD_ARRAY_LENGTH_STEP;
newlen = Math.min(newlen, (long)Integer.MAX_VALUE);
long[] newarr = new long[(int)newlen];
[color=red]System.arraycopy(numbers, 0, newarr, 0, numbers.length); [/color]
numbers = newarr;
}
* Увеличивает массив для хранения простых чисел
* */
private void arrayIncrease()
throws PrimeNumberException
{
if (numbers.length == Integer.MAX_VALUE)
throw new PrimeNumberException("Prime number count is maximal");
long newlen = numbers.length;
newlen += ADD_ARRAY_LENGTH_STEP;
newlen = Math.min(newlen, (long)Integer.MAX_VALUE);
long[] newarr = new long[(int)newlen];
[color=red]System.arraycopy(numbers, 0, newarr, 0, numbers.length); [/color]
numbers = newarr;
}
Тебе надо что - коллекцию с быстрым добавлением элемента в конец ее, и с быстрым поиском по ней.
Можно использовать ArrayList<Long>, например.
Цитата: Zorkus
Бинарный поиск по массиву есть в классе-сервисе java.util.Arrays.
Мне нужен поиск не по массиву а по его заполненой части.
Цитата: Zorkus
Потом, зачем использование именно массива в этом коде? Это загромождает код, так как отдельно приходится отслеживать изменение размера массива - притом, ты заводишь отдельную переменную класса int numbersCount, для этого отслеживания.
Суть переменной numbersCount в первую очередь в том что она помнит количество найденных простых чисел и никакого отношения к масиву не имеет. Тоесть ето конечно указатель на конец заполненой части - но в первую очередь ето поле используется для того чтоб определить надо ли искать новое число или отдать уже найденное.
Я не могу положится на всякие getLength, getSize в организации своей синхронизации поскольку ети методы в классах контейнерах могут роботать по разному в разных реализациях.
Где загромождение кода ? Только в arrayIncrease. Не вижу больше метода, где массив мешает пониманию.
Цитата: Zorkus
Но главное - ты каждые 10 шагов создаешь НОВЫЙ массив, и переписываешь туда старый! Зачем??
Код:
/**
* Увеличивает массив для хранения простых чисел
* */
private void arrayIncrease()
throws PrimeNumberException
{
if (numbers.length == Integer.MAX_VALUE)
throw new PrimeNumberException("Prime number count is maximal");
long newlen = numbers.length;
newlen += ADD_ARRAY_LENGTH_STEP;
newlen = Math.min(newlen, (long)Integer.MAX_VALUE);
long[] newarr = new long[(int)newlen];
[COLOR=red]System.arraycopy(numbers, 0, newarr, 0, numbers.length); [/COLOR]
numbers = newarr;
}
* Увеличивает массив для хранения простых чисел
* */
private void arrayIncrease()
throws PrimeNumberException
{
if (numbers.length == Integer.MAX_VALUE)
throw new PrimeNumberException("Prime number count is maximal");
long newlen = numbers.length;
newlen += ADD_ARRAY_LENGTH_STEP;
newlen = Math.min(newlen, (long)Integer.MAX_VALUE);
long[] newarr = new long[(int)newlen];
[COLOR=red]System.arraycopy(numbers, 0, newarr, 0, numbers.length); [/COLOR]
numbers = newarr;
}
Можно использовать ArrayList<Long>, например.
ADD_ARRAY_LENGTH_STEP можно установить и побольше.
А на счет ArrayList. Посмотри его исходник и нечего нового там не увидиш.
[quote=ArrayList]
Код:
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
[COLOR=red]elementData = (E[])new Object[newCapacity];
System.arraycopy(oldData, 0, elementData, 0, size);[/COLOR]
}
}
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
[COLOR=red]elementData = (E[])new Object[newCapacity];
System.arraycopy(oldData, 0, elementData, 0, size);[/COLOR]
}
}
[/quote]
Кроме того получим задержки на приведении long в Long и обратно.
Long ведь не получится использовать в проверке на деление без остатка, а ArrayList<long> не бывает.
Цитата: Rebbit
Мне нужен поиск не по массиву а по его заполненой части.
Суть переменной numbersCount в первую очередь в том что она помнит количество найденных простых чисел и никакого отношения к масиву не имеет. Тоесть ето конечно указатель на конец заполненой части - но в первую очередь ето поле используется для того чтоб определить надо ли искать новое число или отдать уже найденное.
Я не могу положится на всякие getLength, getSize в организации своей синхронизации поскольку ети методы в классах контейнерах могут роботать по разному в разных реализациях.
Где загромождение кода ? Только в arrayIncrease. Не вижу больше метода, где массив мешает пониманию.
Суть переменной numbersCount в первую очередь в том что она помнит количество найденных простых чисел и никакого отношения к масиву не имеет. Тоесть ето конечно указатель на конец заполненой части - но в первую очередь ето поле используется для того чтоб определить надо ли искать новое число или отдать уже найденное.
Я не могу положится на всякие getLength, getSize в организации своей синхронизации поскольку ети методы в классах контейнерах могут роботать по разному в разных реализациях.
Где загромождение кода ? Только в arrayIncrease. Не вижу больше метода, где массив мешает пониманию.
У тебя сейчас есть массив в коде. Есть счетчик его длины, и из разнообразных методов он используется совместно с массивом. Согласен теперь, что ArrayList используют такое же распределение памяти - но почему бы не использовать его (для примера)?
Насчет того, что нельзя положиться на реализации коллекций - почему?
Можно же посмотреть исходники того, как это реализовано, вдобавок, коллекции - это часть Core Api, они думаю,реализации стандартны.
Просто на мой взгляд, это бы могло сократить код и сакцентировать именно на проектной части ГПЧ.
Цитата:
У меня синхронизировать надо только добавление нового простого числа в кеш.
Т.е. существенно в теме то, что есть неатомарная операция добавления, как я понимаю твой интерес в этой области. И ты не концентрируешься на том, как именно происходит добавление и как осуществляется управления добавленными числами внутри.
Цитата:
ADD_ARRAY_LENGTH_STEP можно установить и побольше.
А на счет ArrayList. Посмотри его исходник и нечего нового там не увидиш.
Был неправ, что еще сказать :). Меня счетчик зацепил, и реализацию ArrayList не стал тогда смотреть, каюсь.
Цитата:
Кроме того получим задержки на приведении long в Long и обратно.
Long ведь не получится использовать в проверке на деление без остатка, а ArrayList<long> не бывает.
Ну их в самом первом приближении можно не учитывать, думаю. Тем более тут вроде бы не было особой речи о производительности.
Цитата: Zorkus
.........................
Просто на мой взгляд, это бы могло сократить код и сакцентировать именно на проектной части ГПЧ.
..........................
Тем более тут вроде бы не было особой речи о производительности.
..........................
Все ето так. Я поступил немного некорректно приводя етот код в котором, мозможно, не очень хочется розбираться. Но дело в том что я делал его для себя и таким как щитал нужным. Отсюда и оптимизацыя по производительности. И отказ от контейнеров. А приводя код тут мне не хотелось (лень матушка) его модишицировать для лутшего понимания.
Цитата: Zorkus
Т.е. существенно в теме то, что есть неатомарная операция добавления, как я понимаю твой интерес в этой области. И ты не концентрируешься на том, как именно происходит добавление и как осуществляется управления добавленными числами внутри.
Примерно так.
Да ето все то началось с пустяка (см. тему о синглетонах). Я хотел показать что мой генератор должен быть глобальным объектом (не удалось), а там слово за слово о синхронизации и о том что она в моем генераторе не будет особо влиять на производительность и о том что в даном случае синхронизировать надо только добавление нового елемента в кеш.
Хотя если немножко переделать то и синхронизированых методов не надо. Без них можно.
Насколько я знаю, в JVM побочные затраты на собственно синхронизацию метода очень невелики. Буквально наносекунды.