Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 4 [5] 6   вперед  Ctrl      все
 Re: Тяпничная будущая мультипоточность  [new]
mirudom
Member

Откуда:
Сообщений: 1053
mayton
Давайте вы конкретизируете ваши вопросы в привязке к моим пунктам
Уважаемый mayton,
нет у меня вопросов, было интересно в оригинале осилить статью заслуженного чела на указанную тему.
26 янв 19, 21:40    [21794975]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная будущая мультипоточность  [new]
mayton
Member

Откуда: loopback
Сообщений: 42851
Nice job.
27 янв 19, 01:06    [21795048]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная будущая мультипоточность  [new]
mirudom
Member

Откуда:
Сообщений: 1053
mirudom
было интересно в оригинале осилить статью заслуженного чела на указанную тему.

Интересно было прочитать, много поучительного, но, эээ такое чувство, что дискуссия ведется об
использовании различных столовых приборов, ну, достоинство вилок или ножей в различной ситуации,
супчик - так лучше ложечкой, и тд, а вот вывод, вывод делается очень интересный,
надо есть руками.
9 фев 19, 22:13    [21805455]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная будущая мультипоточность  [new]
mayton
Member

Откуда: loopback
Сообщений: 42851
mayton
mayton
пропущено...

Был топик географии 17384728, где мне понадобилось реализовать Кривую Гилберта.
Она реализована как утилита но мне нужен был некий строительный шаблон набодобие
Iterator<Point> который по запросу next() выдает следующую координату кривой. Классический
алгоритм кривой - рекурсивен. Рекурсия внутри итератора - тот еще головняк. Разваливать его в FSM
со стеком мне не хотелось. Нудно да и ошибок можно наделать кучу. А реализация - вот она. Почти работает.
После этого у меня появился еще один мотиватор чтобы реализовать красивый строительный элемент.

Друзья. Топик - сложный и многогранный. Я форкну отдельное обсуждение по корутинам (сопрограммам).
Я возьму штук 3-5 ЯП и промоделирую итератор Гильберта. Особо меня интересует перформанс и как оно реализовано
с практической точки зрения. Прошу прощения что я беру такую специфичную задачу но у меня в наличии
пока ничего другого нет. Если у вас есть предложения - рад послушать.

Прошу прощения за внезапный UP.

Итератор Гилберта на двух потоках. Кривая и громозкая реализация. Ее надо упростить.
Опять-же разворачивание рекурсии в стек - не особо интересно.

public class GilbertPixelIterator implements IPixIterator {

    static Logger logger =  LoggerFactory.getLogger(GilbertPixelIterator.class);

    private BlockingQueue<Point> blockingQueue = new ArrayBlockingQueue<>(256, true);

    private Thread worker;

    private int u = 1;

    private Point poisonedPill = new Point(Integer.MIN_VALUE, Integer.MIN_VALUE);

    private int glx;
    private int gly;

    private Point current = null;

    private boolean finished = false;

    private void a(int i) {
        if (i > 0) {
            d(i - 1);
            linerel(+u, 0);
            a(i - 1);
            linerel(0, u);
            a(i - 1);
            linerel(-u, 0);
            c(i - 1);
        }
    }

    private void b(int i) {
        if (i > 0) {
            c(i - 1);
            linerel(-u, 0);
            b(i - 1);
            linerel(0, -u);
            b(i - 1);
            linerel(u, 0);
            d(i - 1);
        }
    }

    private void c(int i) {
        if (i > 0) {
            b(i - 1);
            linerel(0, -u);
            c(i - 1);
            linerel(-u, 0);
            c(i - 1);
            linerel(0, u);
            a(i - 1);
        }
    }

    private void d(int i) {
        if (i > 0) {
            a(i - 1);
            linerel(0, u);
            d(i - 1);
            linerel(u, 0);
            d(i - 1);
            linerel(0, -u);
            b(i - 1);
        }
    }

    private void safePut(Point point) {
        try {
            blockingQueue.put(point);
        } catch (InterruptedException ex) {
            Thread.currentThread().interrupt();
            logger.warn("Thread interrupted during put!");
        }
    }

    private void linerel(int x, int y) {
        glx += x;
        gly += y;
        safePut(new Point(glx, gly));
    }

    private void moveto(int x, int y) {
        glx = x;
        gly = y;
        safePut(new Point(glx, gly));
    }

    public GilbertPixelIterator(int size) {
        checkArgument(size >= 4 , "Impossible to create gilbert gurve less than 4x4 plane!");
        int level = Utils.log2up(size);
        logger.trace(":: level = {}", level);
        worker = new Thread(() -> {
            moveto(0, 0);
            a(level);
            safePut(poisonedPill);
        });
        worker.start();
    }


    @Override
    public int getX() {
        if (finished) throw new IllegalStateException("Iterator is finished!");
        return current.x;
    }

    @Override
    public int getY() {
        if (finished) throw new IllegalStateException("Iterator is finished!");
        return current.y;
    }

    @Override
    public boolean next() {
        if (finished) {
            return false;
        } else {
            try {
                current = blockingQueue.take(); 
                finished = (current == poisonedPill);
            } catch (InterruptedException ex) {
                Thread.currentThread().interrupt();
                logger.warn("Thread interrupted during take!");
                finished = true;
            }
            return !finished;
        }
    }

    @Override
    public void reset() {
        throw new RuntimeException("Not implemented for mt-iterator");
    }
}


Меня интересуют языки с yield, ленивым конструированием списков.
Тоесть нужно не алгоритмическое а имено технологическое решение.
Предполагаю что будет масса рекурсивных алгоритмов которые обходят
деревья графы и прочие достаточно сложные для разворачивания структуры.

Под катом - каменты к алгоритму
+

На 90% это копия того кода на сях который мы делали в пятничной географии. Только там интеракция
этого сорца с другими модулями шла через STDOUT, тоесть проблемы передачи потока координат не было.
Тоесть эти функции a(), b(), c()... каноничны и собственно рисуют и вращают кривую на разных уровнях
раррешающей способности поверхности. Их изучать и анализировать не надо. А что надо?
Нужно выкинуть нахер блокирующую очередь и вспомогательный поток.
13 окт 19, 00:02    [21992944]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная будущая мультипоточность  [new]
hVostt
Member

Откуда:
Сообщений: 16164
mayton
Меня интересуют языки с yield, ленивым конструированием списков.


Конечный автомат же.
13 окт 19, 01:09    [21992958]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная будущая мультипоточность  [new]
mayton
Member

Откуда: loopback
Сообщений: 42851
Давай сюда свой конечный автомат. Или не-конечный?
13 окт 19, 01:21    [21992959]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная будущая мультипоточность  [new]
hVostt
Member

Откуда:
Сообщений: 16164
mayton,

Я к тому, что yield разворачивается в конечный автомат (потому что ленивый), который довольно громоздкий.
Хотя выглядеть это может и красиво )

Чёт я не увидел тут два потока...
13 окт 19, 02:28    [21992963]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная будущая мультипоточность  [new]
mayton
Member

Откуда: loopback
Сообщений: 42851
значит я хорошо их спрятал.
13 окт 19, 08:09    [21992971]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная будущая мультипоточность  [new]
mayton
Member

Откуда: loopback
Сообщений: 42851
На Kotlin можно попробовать переписать. Тогда явный Thread и очередь можно будет выкинуть.
13 окт 19, 12:36    [21993029]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная будущая мультипоточность  [new]
hVostt
Member

Откуда:
Сообщений: 16164
mayton
Картинка с другого сайта. значит я хорошо их спрятал.


я про потоки с вычислением, он у вас один. и зачем эти пляски с блокирующей коллекцией?
может громоздкость связана с неясно оформленой/понятой задачей? )
13 окт 19, 13:23    [21993042]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная будущая мультипоточность  [new]
mayton
Member

Откуда: loopback
Сообщений: 42851
hVostt
mayton
Картинка с другого сайта. значит я хорошо их спрятал.


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

Да нет никакой задачи. Это всё - мысли по теме будущей мультипоточности.
Вы сами можете задачу поставить? Чтоб всем была понятна мотивация.

Я одну задачу поставил. Итератор по сложной структуре данных.
13 окт 19, 14:15    [21993053]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная будущая мультипоточность  [new]
hVostt
Member

Откуда:
Сообщений: 16164
mayton,

ну вот yield-оператор ленивый, он будет возвращать данные по мере обращения. т.е. вычисления "вперёд", как вы сделали с коллекцией не будет, а если вам это нужно, то в любом случае мы придём либо к safe-блокирующей коллекции, либо к стеку с соответствующими ограничениями.

в C#, например, можно посмотреть в сторону DataFlow или Channels
13 окт 19, 16:31    [21993090]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная будущая мультипоточность  [new]
hVostt
Member

Откуда:
Сообщений: 16164
mayton
На Kotlin можно попробовать переписать. Тогда явный Thread и очередь можно будет выкинуть.


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

возможны более оптимальные конструкции типа Producer/Consumer, но от этого в любом случае никуда не деться.

какого волшебства там от котлина ожидается я не понял :)
13 окт 19, 16:33    [21993093]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная будущая мультипоточность  [new]
полудух
Member

Откуда: планета орков, г.Зверополис
Сообщений: 932
насколько я понял, там паттерн = много-много мелких задачек
а такие паттерны лучше всего паралеллить через GPU

mayton
Это всё - мысли по теме будущей мультипоточности

будущее многопоточности в полном, 100-процентном разделении потоков
чтобы один поток никак не пересекался с другим (ни в кэше, ни в памяти, ни где-то ещё)
А чтобы задача не проставивала, потоков должно быть больше, чем нужно
13 окт 19, 18:05    [21993149]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная будущая мультипоточность  [new]
mayton
Member

Откуда: loopback
Сообщений: 42851
полудух
будущее многопоточности в полном, 100-процентном разделении потоков
чтобы один поток никак не пересекался с другим (ни в кэше, ни в памяти, ни где-то ещё)

Это невозможно. Ну или по крайней мере подобная задача была-бы бесполезна и ненужна для бизнеса.
Задачи постоянно пересекаются по данным.
13 окт 19, 20:51    [21993235]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная будущая мультипоточность  [new]
полудух
Member

Откуда: планета орков, г.Зверополис
Сообщений: 932
там тоже самое всё, просто потоки не бегают туда-сюда по разным задачам
взял задачу - решаешь её
а ещё лучше, если каждый поток умеет делать только 1 тип задач
один из БД читает, другой в БД пишет, третий регекспит, четвёртый считает итд
как в клетке Картинка с другого сайта.
13 окт 19, 21:10    [21993246]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная будущая мультипоточность  [new]
mayton
Member

Откуда: loopback
Сообщений: 42851
полудух, ты моделируешь некий рай или Эдем для мультипоточности. И ему есть название.

Shared nothing. Это когда например ты задачи можешь разнести по разным хостам и запустить
их и тупо ждать результата. Интеракции между ними нет и не предвидится. Так например работает
блокчейн цепочка. У них интеракция - только цифровое подписывание текущего блока валютных
транзакций.

Это и позволяет гонять крипту на физически разных компах и ядрах и видеокартах и аппаратных
устройствах типа ASIC.
13 окт 19, 21:16    [21993250]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная будущая мультипоточность  [new]
mayton
Member

Откуда: loopback
Сообщений: 42851
hVostt
mayton
На Kotlin можно попробовать переписать. Тогда явный Thread и очередь можно будет выкинуть.


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

возможны более оптимальные конструкции типа Producer/Consumer, но от этого в любом случае никуда не деться.

какого волшебства там от котлина ожидается я не понял :)

Ленивый итератор на Scala я планирую переписать по аналогии с тем как я например генерил
кандидатов для простых чисел.

Решение очень изящное. И никаких тебе блокинг очередей.
/**
    * Prime candidates generator
    *
    * @return
    */
  def primeCandidates() : Stream[Int] = {
    def primeCandidates(n : Int, step : Int) : Stream[Int] = {
      n #:: primeCandidates(n + step, step^0x6)
    }

    2 #:: 3 #:: primeCandidates(5, 2)
  }


Но с Гилбертом так пока не вышло. Я что-то упускаю.
13 окт 19, 21:29    [21993253]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная будущая мультипоточность  [new]
fixxer
Member

Откуда:
Сообщений: 736
mayton
Но с Гилбертом так пока не вышло. Я что-то упускаю.


Вроде постил уже Четверговый корутин с Гилбертом
13 окт 19, 21:57    [21993263]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная будущая мультипоточность  [new]
mayton
Member

Откуда: loopback
Сообщений: 42851
fixxer
mayton
Но с Гилбертом так пока не вышло. Я что-то упускаю.


Вроде постил уже Четверговый корутин с Гилбертом

О. Шикарно. Почему я забыл. ХЗ.

Я только с вашего позволения заменю tuples, на case-class, так удобнее.
13 окт 19, 22:04    [21993268]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная будущая мультипоточность  [new]
mayton
Member

Откуда: loopback
Сообщений: 42851
А в чем разница между этими двумя операторами?

class ConsWrapper[A](tl : => scala.collection.immutable.Stream[A]) extends scala.AnyRef {
    def #::[B >: A](hd : B) : scala.collection.immutable.Stream[B] = { /* compiled code */ }
    def #:::[B >: A](prefix : scala.collection.immutable.Stream[B]) : scala.collection.immutable.Stream[B] = { /* compiled code */ }
  }
13 окт 19, 22:15    [21993273]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная будущая мультипоточность  [new]
fixxer
Member

Откуда:
Сообщений: 736
mayton
А в чем разница между этими двумя операторами?

class ConsWrapper[A](tl : => scala.collection.immutable.Stream[A]) extends scala.AnyRef {
    def #::[B >: A](hd : B) : scala.collection.immutable.Stream[B] = { /* compiled code */ }
    def #:::[B >: A](prefix : scala.collection.immutable.Stream[B]) : scala.collection.immutable.Stream[B] = { /* compiled code */ }
  }


Первый цепляет элемент, второй два стрима между собой.


def#::[B >: A](elem: B): Stream[B]
Construct a Stream consisting of a given first element followed by elements from another Stream.

def#:::[B >: A](prefix: Stream[B]): Stream[B]
Construct a Stream consisting of the concatenation of the given Stream and another Stream.
13 окт 19, 22:33    [21993278]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная будущая мультипоточность  [new]
полудух
Member

Откуда: планета орков, г.Зверополис
Сообщений: 932
mayton
полудух, ты моделируешь некий рай или Эдем для мультипоточности. И ему есть название.

Shared nothing. Это когда например ты задачи можешь разнести по разным хостам и запустить
их и тупо ждать результата. Интеракции между ними нет и не предвидится. Так например работает
блокчейн цепочка. У них интеракция - только цифровое подписывание текущего блока валютных
транзакций.

Это и позволяет гонять крипту на физически разных компах и ядрах и видеокартах и аппаратных
устройствах типа ASIC.

да не, я вроде не это описал Картинка с другого сайта.
разные хосты всё также будут мутить свою внутреннюю многопоточность
я скорее описывал другую архитектуру процессора
14 окт 19, 00:20    [21993313]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная будущая мультипоточность  [new]
mayton
Member

Откуда: loopback
Сообщений: 42851
Придумай задачу под твой процессор.
14 окт 19, 00:49    [21993328]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная будущая мультипоточность  [new]
mayton
Member

Откуда: loopback
Сообщений: 42851
fixxer
mayton
А в чем разница между этими двумя операторами?

class ConsWrapper[A](tl : => scala.collection.immutable.Stream[A]) extends scala.AnyRef {
    def #::[B >: A](hd : B) : scala.collection.immutable.Stream[B] = { /* compiled code */ }
    def #:::[B >: A](prefix : scala.collection.immutable.Stream[B]) : scala.collection.immutable.Stream[B] = { /* compiled code */ }
  }


Первый цепляет элемент, второй два стрима между собой.


def#::[B >: A](elem: B): Stream[B]
Construct a Stream consisting of a given first element followed by elements from another Stream.

def#:::[B >: A](prefix: Stream[B]): Stream[B]
Construct a Stream consisting of the concatenation of the given Stream and another Stream.


Вот как-то так получилось. Итератор работает и тест прошел.

Только не нравятся мне вот эти две переменных. Они как-то не по феньшую в этой скале стоят.

package mayton.image.iterators.scala

class GilbertLazyStream {

  val u = 1

  var glx = 0
  var gly = 0

  private def linerel(x: Int, y: Int) : Point = {
    glx = glx + x
    gly = gly + y
    Point(glx, gly)
  }

  private def moveto(x: Int, y: Int) : Point = {
    glx = x
    gly = y
    Point(x, y)
  }

  private def a(i: Int): Stream[Point] = {
    if (i > 0) {
      d(i - 1) #::: linerel(+u, 0) #:: a(i - 1) #::: linerel(0, u) #:: a(i - 1) #::: linerel(-u, 0) #:: c(i - 1)
    } else {
      Stream.empty
    }
  }

  private def b(i: Int): Stream[Point] = {
    if (i > 0) {
      c(i - 1) #::: linerel(-u, 0) #:: b(i - 1) #::: linerel(0, -u) #:: b(i - 1) #::: linerel(u, 0) #:: d(i - 1)
    } else {
      Stream.empty
    }
  }

  private def c(i: Int): Stream[Point] = {
    if (i > 0) {
      b(i - 1) #::: linerel(0, -u) #:: c(i - 1) #::: linerel(-u, 0) #:: c(i - 1) #::: linerel(0, u) #:: a(i - 1)
    } else {
      Stream.empty
    }
  }

  private def d(i: Int): Stream[Point] = {
    if (i > 0) {
      a(i - 1) #::: linerel(0, u) #:: d(i - 1) #::: linerel(u, 0) #:: d(i - 1) #::: linerel(0, -u) #:: b(i - 1)
    } else {
      Stream.empty
    }
  }

  def nlz(xArg: Int): Int = {
    var x = xArg
    var n = 0
    if (x == 0) return 32
    n = 1
    if ((x >>> 16) == 0) {
      n += 16
      x <<= 16
    }
    if ((x >>> 24) == 0) {
      n += 8
      x <<= 8
    }
    if ((x >>> 28) == 0) {
      n += 4
      x <<= 4
    }
    if ((x >>> 30) == 0) {
      n += 2
      x <<= 2
    }
    n = n - (x >>> 31)
    n
  }

  def log2up(x: Int): Int = {
    if (x < 1) return 0
    32 - nlz(x - 1)
  }

  def gilbertPoinsStream(size : Int) : Stream[Point] = {
    val level = log2up(size)
    moveto(0, 0)
    Point(0,0) #:: a(level)
  }

}


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

Странно. Но почему я обошёлся без :: Nil хвостика? По идее его-бы надо добавить.
14 окт 19, 01:03    [21993332]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 4 [5] 6   вперед  Ctrl      все
Все форумы / Программирование Ответить