Факториал (Потоки)

[sciko]

Что бы внезапно не получить недетерминированность, надо теорию вычислительных процессов знать.

А ещё никогда не совершать ошибки и иметь чистую библиотеку для используемых сущностей (привет STL) ^_^

Ведь на недетерминированность компилятор T++ никак не среагирует. В отличии от Хаскела, т.к. это чистый язык.

[Crazy]

Ведь на недетерминированность компилятор T++ никак не среагирует. В отличии от Хаскела, т.к. это чистый язык.

Где ты там видишь недетерменированность?

[sciko]

Вопроса не понял.

[Crazy]

Вопроса не понял.

Что в T++ приведет к недетерменированности ?

[sciko]

Что в T++ приведет к недетерменированности ?

Допустим стандартные функции sizeof, time, rand и т.п..

Но, конечно, основной бич Т++ -- побочные эффекты. И избавиться от них весьма и весьма сложно, особенно учитывая, что Т++ -- ОО-язык.

[Crazy]

Что в T++ приведет к недетерменированности ?

Допустим стандартные функции sizeof, time, rand и т.п..

Но, конечно, основной бич Т++ -- побочные эффекты. И избавиться от них весьма и весьма сложно, особенно учитывая, что Т++ -- ОО-язык.

Что не так со стандартными функциями?

Причем тут побочный эффект? T функции и переменные реализуют такой подход как "FUTURES, PROMISES, AND SIMILAR"
Вы же не против Mvars в Glasgow Haskell.

[sciko]

Что не так со стандартными функциями?

Конкретно эти функции возвращают разные значения несмотря на то, что им передаются на вход одинаковые значения входных аргументов. Это называется недетерминированность.

Причем тут побочный эффект?

При том что ООП -- это один большой побочный эффект.

Вы же не против Mvars в Glasgow Haskell.

А причём тут синхронизирующая переменная?

Да и вообще, T++ ничем не лучше того же OpenMP, только идёт блобом и скрывает свои глюки под красивыми словами. Поэтому в топку это произведение отечественных нанокодеров.

[Crazy]

Конкретно эти функции возвращают разные значения несмотря на то, что им передаются на вход одинаковые значения входных аргументов. Это называется недетерминированность.

Не путай недетерминированные функции c побочными эффектами и свойством детерминированности алгоритма.

При том что ООП -- это один большой побочный эффект.

Перекладывания с больной головы на здоровую, кто-то говорил про ООП?

Вы же не против Mvars в Glasgow Haskell.

А причём тут синхронизирующая переменная?

При том, что кроме т-функции есть т-переменная, которая выполняет блокировку процессов.

Да и вообще, T++ ничем не лучше того же OpenMP, только идёт блобом и скрывает свои глюки под красивыми словами. Поэтому в топку это произведение отечественных нанокодеров.

Лучше тем, что это сделали свойством языка, придав тем самым свойство параллельности. По крайней мере компьютеры с Скиф/Скиф грид, спокойно работают и входят в TOP 500 мощных компьютеров. А Alt Linux на базе Скиф предлагает решения Суперкомпьютер.

[drBatty]

Конкретно эти функции возвращают разные значения несмотря на то, что им передаются на вход одинаковые значения входных аргументов. Это называется недетерминированность.

вы не поверите, но значения time и rand вполне себе детерменированны. А про sizeof - поподробнее плз.

[sciko]

Не путай недетерминированные функции c побочными эффектами и свойством детерминированности алгоритма.

1. Назовите побочный эффект функции rand
2. Дайте свои определение недетерминированной функции и детерминированности алгоритма. И так же опишите различие между этими понятиями в вашем понимании. Мне кажется, что мы говорим на разных языках.

кто-то говорил про ООП?

Т.е. вы изначально были согласны, что Т++ будет ловить массу побочных эффектов?

При том, что кроме т-функции есть т-переменная, которая выполняет блокировку процессов.

И каким же боком она связана с побочными эффектами?

Лучше тем, что это сделали свойством языка, придав тем самым свойство параллельности

Тогда объясните принципиальную разницу между

Код: Выделить всё

tfun int fib (int n) {
  return n < 2 ? n : fib(n-1) + fib(n-2);
}

и

Код: Выделить всё

long fib_parallel(long n)
{
    long x, y;
    if (n < 2) return n;
    #pragma omp task default(none) shared(x,n)
    {
        x = fib_parallel(n-1);
    }
    y = fib_parallel(n-2);
    #pragma omp taskwait
    return (x+y);
}

Оба примера их манов.

По крайней мере компьютеры с Скиф/Скиф грид, спокойно работают и входят в TOP 500 мощных компьютеров.

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

[NickLion]

Не путай недетерминированные функции c побочными эффектами и свойством детерминированности алгоритма.

1. Назовите побочный эффект функции rand
2. Дайте свои определение недетерминированной функции и детерминированности алгоритма. И так же опишите различие между этими понятиями в вашем понимании. Мне кажется, что мы говорим на разных языках.

Функция rand меняет значение глобальной переменной. С одним и тем же аргументом (пусто) она возвращает разные значения. Вроде классическое определение функции с побочным эффектом.
А вот насчёт детерминированности - тут проблема терминологии. Я, как видимо и Crazy, исхожу из определения детерминированности алгоритма, детерминированности конечного автомата.
(А в этих терминах текущий компьютер является детерминированным конечным автоматом, а потому не может реализовать недетерминированность. Ну, эмулировать можно, но не более.)

[Crazy]

Дайте свои определение недетерминированной функции и детерминированности алгоритма.

Не учили в вузе, читайте хоть в вики

кто-то говорил про ООП?

Т.е. вы изначально были согласны, что Т++ будет ловить массу побочных эффектов?

Какие побочные эффекты?

Лучше тем, что это сделали свойством языка, придав тем самым свойство параллельности

Тогда объясните принципиальную разницу между

Код: Выделить всё

tfun int fib (int n) {
  return n < 2 ? n : fib(n-1) + fib(n-2);
}

и

Код: Выделить всё

long fib_parallel(long n)
{
    long x, y;
    if (n < 2) return n;
    #pragma omp task default(none) shared(x,n)
    {
        x = fib_parallel(n-1);
    }
    y = fib_parallel(n-2);
    #pragma omp taskwait
    return (x+y);
}

Оба примера их манов.

Как видишь, первый пример более простой и ясный, в отличие от использование прагм и макросов.

По крайней мере компьютеры с Скиф/Скиф грид, спокойно работают и входят в TOP 500 мощных компьютеров.

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

Чем качество меришь, линейкой?
Думаешь, что на такую штуку ерунду будут ставить? Думаю, что в таких проектах за качеством следят.

исхожу из определения детерминированности алгоритма, детерминированности конечного автомата.

А разве есть другие определения, как не последовательность шагов, приводящих к одному и тому же результату, на одних и тех же входных данных?

[/dev/random]

А разве есть другие определения, как не последовательность шагов, приводящих к одному и тому же результату, на одних и тех же входных данных?

Входными данными могут считаться разные вещи. Вы это прекрасно знаете, даже подчеркнули в другом своём посте.

Детерминированная функция - такая функция, значение которой зависит только от передаваемых параметров. Т.е. если она берёт данные от систем ввода-вывода, от операционки, даже из глобальных переменных - она недетерминированная. В то же время, детерминированный _алгоритм_ может брать данные откуда угодно, и недетерминированным от этого не станет.
Два фактора т.н. _чистоты_ функции: детерминированность (по определению выше) и отсутствие _побочных эффектов_ (ввода-вывода, изменения глобальных переменных и вообще каких-либо изменений состояния системы, кроме возврата значения).

[drBatty]

2. Дайте свои определение недетерминированной функции и детерминированности алгоритма.

по-русски - предопределённость. Я могу сказать ТОЧНО, что мне выдаст rand & time & sizeof. То, что я не могу точно сказать, что они напишут вам ничего не доказывают - вы утаиваете входные данные.

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

не совсем так - если не принять спец-мер, то почти любой алгоритм станет недетерминированным, даже простой инкремент.
если конечно кодер не озаботился отделить данные одного потока, от данных другого. К примеру, ++i может давать недетерминированный результат, если кто-то одновременно запускает другую ++i. Ну и что?

Как видишь, первый пример более простой и ясный, в отличие от использование прагм и макросов.

первый пример даёт непредсказуемый результат. Видимо о том и речь...

В то же время, детерминированный _алгоритм_ может брать данные откуда угодно, и недетерминированным от этого не станет.

станет. если он состоит из недетерминированных кусков. Вы написали ++i - всё, фтоппку. Вот только такое на любом ЯП, в некоторых просто есть заборчики, что-бы так не писать. В C++ нету, и кодеру надо самому...

[sciko]

Функция rand меняет значение глобальной переменной. С одним и тем же аргументом (пусто) она возвращает разные значения. Вроде классическое определение функции с побочным эффектом.

Классическая rand не меняет глобальных переменных и является примером недетерминированной функции без побочных эффектов.

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

Отсюда следует, что говорить о недетерминированности алгоритма нет смысла, т.к. он не реализуем. Поэтому логично говорить только о чистоте функции, а значит её детерминированости.

не совсем так - если не принять спец-мер, то почти любой алгоритм станет недетерминированным, даже простой инкремент.

Затрудняюсь оценить как связаны состояние гонки и недетерминированность алгоритма.

Как видишь, первый пример более простой и ясный, в отличие от использование прагм и макросов.

Вообще-то фундаментально они идентичны.
Распараллелить можно только чистые функции. Но вот ни один процедурный язык не проверяет чистоту функции (в отличии от Хаскеля состоит только из чистых функций и монад). Более того побочные эффекты или недетерминированость может скрываться где-то глубоко в стандартных библиотеках или написанных для непараллельного участка.
В этом смысле OpenMP более дружелюбен: учаски распараллеливания чётко отмечены и результат их работы более-менее понятен.

[NickLion]

Функция rand меняет значение глобальной переменной. С одним и тем же аргументом (пусто) она возвращает разные значения. Вроде классическое определение функции с побочным эффектом.

Классическая rand не меняет глобальных переменных и является примером недетерминированной функции без побочных эффектов.

Уж куда более классическая:

EXAMPLE
POSIX.1-2001 gives the following example of an implementation of rand() and srand(), possibly useful when one needs the same
sequence on two different machines.

Код: Выделить всё

           static unsigned long next = 1;

           /* RAND_MAX assumed to be 32767 */
           int myrand(void) {
               next = next * 1103515245 + 12345;
               return((unsigned)(next/65536) % 32768);
           }

           void mysrand(unsigned seed) {
               next = seed;
           }

[Crazy]

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

Отсюда следует, что говорить о недетерминированности алгоритма нет смысла, т.к. он не реализуем. Поэтому логично говорить только о чистоте функции, а значит её детерминированости.

Смотри недетерменированные конечный автоматы, легко реализуем, и на одном и том же наборе данных дает различный результат.

не совсем так - если не принять спец-мер, то почти любой алгоритм станет недетерминированным, даже простой инкремент.

Затрудняюсь оценить как связаны состояние гонки и недетерминированность алгоритма.

Прямое, неповторимость результатов на одно наборе данных.
Теорема Бернштейна-Рассела-Нариньяни, или отсутствие конкуренционной зависимости операторов, определяет ситуации когда операторы не только не могут выполнятся параллельно,
но и порядок выполнения так же важен.

Как видишь, первый пример более простой и ясный, в отличие от использование прагм и макросов.

Вообще-то фундаментально они идентичны.
Распараллелить можно только чистые функции. Но вот ни один процедурный язык не проверяет чистоту функции (в отличии от Хаскеля состоит только из чистых функций и монад). Более того побочные эффекты или недетерминированость может скрываться где-то глубоко в стандартных библиотеках или написанных для непараллельного участка.
В этом смысле OpenMP более дружелюбен: учаски распараллеливания чётко отмечены и результат их работы более-менее понятен.

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

[drBatty]

Классическая rand не меняет глобальных переменных и является примером недетерминированной функции без побочных эффектов.

ЩИТО?
мы значит о разных rand. Я об этой писал:

DESCRIPTION
The rand() function returns a pseudo-random integer in the range 0 to RAND_MAX inclusive (i.e., the mathe‐
matical range [0, RAND_MAX]).

The srand() function sets its argument as the seed for a new sequence of pseudo-random integers to be
returned by rand(). These sequences are repeatable by calling srand() with the same seed value.

If no seed value is provided, the rand() function is automatically seeded with a value of 1.

The function rand() is not reentrant or thread-safe, since it uses hidden state that is modified on each
call. This might just be the seed value to be used by the next call, or it might be something more elabo‐
rate. In order to get reproducible behavior in a threaded application, this state must be made explicit;
this can be done using the reentrant function rand_r().

Like rand(), rand_r() returns a pseudo-random integer in the range [0, RAND_MAX]. The seedp argument is a
pointer to an unsigned int that is used to store state between calls. If rand_r() is called with the same
initial value for the integer pointed to by seedp, and that value is not modified between calls, then the
same pseudo-random sequence will result.

The value pointed to by the seedp argument of rand_r() provides only a very small amount of state, so this
function will be a weak pseudo-random generator. Try drand48_r(3) instead.

Затрудняюсь оценить как связаны состояние гонки и недетерминированность алгоритма.

результат гонки детерминирован? да/нет?

кстати обратите внимание на not reentrant or thread-safe
в цитате...

[sciko]

мы значит о разных rand.

Ну, да. Я про тот который random, а не pseudo-random.

результат гонки детерминирован?

Затрудняюсь ответить. Скорее "да", чем "нет".

[drBatty]

мы значит о разных rand.

Ну, да. Я про тот который 1)random, а не pseudo-random.

результат гонки детерминирован?

Затрудняюсь 2)ответить. Скорее "да", чем "нет".

1) а... тут от реализации зависит... не знаю...
2) обычно таки "да". Т.е. результат гонки недетерминирован, а следовательно непредсказуем. Потому и весь алгоритм недетерминирован, если кодер хоть раз проворонил гонки. Ну а пользуясь стандартными функциями С/С++ проворонить очень легко - они практически все с побочными эффектами.

[Crazy]

обычно таки "да". Т.е. результат гонки недетерминирован, а следовательно непредсказуем. Потому и весь алгоритм недетерминирован, если кодер хоть раз проворонил гонки. Ну а пользуясь стандартными функциями С/С++ проворонить очень легко - они практически все с побочными эффектами.

Потоки и процессы теперь есть в стандарте C/C++?
Все зависит от выбора модели процессов.
Если брать модель Хоара, которая реализована в Erlang, Limbo, Go, то тут MPICH, Open MPI.

[NickLion]

мы значит о разных rand.

Ну, да. Я про тот который random, а не pseudo-random.

Круть, такой есть? Не поделитесь? Кроме отдельных физических плат и эмуляции на основе энтропийных данных, получаемых от пользователя я других не знаю. Да только первый вариант встречается редко, второй имеет низкую ширину канала (генерация порядка 200 байт за 6 секунд - это чрезвычайно низко) и непредсказуемую задержку к тому же. Поэтому во всех языках, которые знаю, когда говорят о rand - говорят о генераторе псевдо-случайных чисел.