Schedulable lightweight virtual processes and concurrent loops P&L: -11.5 (≃ -12063 RUB)
Imagine a nested for loop, it is composed of multiple loops. We can simulate concurrency by executing parts of loops and rapidly switch between them.
This is what a kernel scheduler does and I think it's a very interesting part of an operating system. Unfortunately most programs are not written to be multithreaded so computers use very little of resources available to them.
19,190 1:09
Перепишите код Python на Java, чтобы можно было использовать настоящую многопоточность. Реализовать потоки запуска цикла, которые неоднократно пытаются выполнить N-й продукт, соответствующий этому номеру потока.
Rewrite Python code in Java so true multithreading can be used Implement loop runner threads that repeatedly try execute Nth product that matches that thread number
два часа Я вполне доволен тем, что создал. Я думаю, что API мог бы быть лучше. Или реализация ожидания результатов могла бы быть лучше. Расчет, чтобы увидеть, есть ли какие-либо новые результаты, является дорогостоящим из-за вложенных циклов. Я думаю, что это можно было бы сделать лучше. В идеале вложенные циклы должны содержать всего несколько инструкций и дополнений divmod. В противном случае они должны доминировать в используемых характеристиках.
2 hours I am fairly happy with what I created. I think the API could be better. Or the implementation of waiting for results could be better. The calculation to see if there are any new results is expensive due to nested loops. I think this could be done better. Ideally nested loops should only take a few divmod instructions and additions. Otherwise they shall dominate performance used.
2-4 часа Не могу вспомнить, когда начал
Я получаю повторяющиеся записи.
Родительский цикл выглядит так:
для письма буквами: для числа в цифрах:
для символа в символах:
Затем я пытаюсь расширить его с помощью нового параллельного цикла внутри внутреннего цикла.
Но каждая итерация будет выглядеть одинаково! Это не эквивалентно этому:
для письма буквами: для числа в цифрах:
для символа в символах:
для вложенных кодов: для эмодзи во вложенных: печать (вложенный эмодзи с буквенным номером)
Мне нужен какой-то способ расширить цикл через произвольное количество циклов, например, дерево циклов.
2-4 hours I cannot remember when I began
I get duplicate entries.
The parent loop looks this:
for letter in letters: for number in numbers: for symbol in symbols:
Then I try extend it with a new concurrent loop inside the innerloop.
But each iteration would look the same! It's not equivalent to this:
for letter in letters: for number in numbers: for symbol in symbols: for nested in codes: for emoji in nested: print(letter + number + symbol + nested + emoji)
I need some way of extending the loop through an arbitrary number of loops, like a tree of loops.
Я потратил на это 1 час. Я был не в настроении для развития, но протолкнулся.
I spent 1 hour on this. I wasn't really in the mood for development but pushed through.
Я понял свою ошибку в своей логике. Поток 0 отвечает за итерации цикла 0-8 Поток 1 отвечает за 8-16 Поток 2 отвечает за 16-24 И так далее В настоящее время я выполняю итерации цикла в неправильном потоке из-за математической логики отсутствия обработки циклов. Я использую оператор по модулю. В идеале каждый тикер вызывается в потоке только для своего диапазона.
I realised my bug in my logic. Thread 0 is responsible for loop iterations 0-8 Thread 1 is responsible for 8-16 Thread 2 is responsible for 16-24 And so on I'm currently executing loop iterations on the wrong thread due to a mathematical logic of not handling wraparound. I use the modulo operator. Ideally each ticker is only called on the thread for its range.
У меня есть проблема, которую мне нужно решить. Что не связано с параллелизмом.
Представьте, что у меня есть вложенный цикл, который выглядит так
``` Для письма В письмах:
Для числа в цифрах:
Распечатать(цифра буквы)
Для символа в символах:
Печать (буквенный символ) ```
Я хочу, чтобы эти три цикла выполнялись одновременно. Один из подходов — выбрать функцию для запуска на основе индексов! И объедините цифры и буквы вместе по кругу. Итак, мы получаем
А1
А÷
А2
А×
Проблема с этим подходом заключается в том, что циклы не являются отдельными. Это одна петля, которая была объединена.
Я думаю, что могу решить эту проблему, сделав коллекции мультиколлекциями. [Буквы, [цифры, символы] И выбирая из каждого подсписка циклический перебор и выставляя циклы как отдельные объекты.
I have a problem I need to solve. Which isn't related to the parallellism.
Imagine I have a nested loop that looks like this
``` For letter In letters:
For number in numbers:
Print(letter + number)
For symbol in symbols:
Print(letter + symbol) ```
I want these three loops to run concurrently. One approach is to pick the function to run based on the indexes! And merge the numbers and letters together round robin. So we get
A1
A÷
A2
A×
The problem with this approach is that the loops aren't separate. They're one loop that has been merged.
I think I can solve this by causing collections to be a multi collection. [Letters, [numbers, symbols] And picking from each sublist round robin and exposing the loops as separate objects.
Я создал многопоточную версию без циклов Joinable. Но в это время у меня перерыв. Мне нужно как-то связать многопоточность с присоединяемым циклом. Когда цикл Joinable получает 2 или более значений, он продолжает обработку. Это позволяет разделить и объединить конвейерную обработку. Я хочу, чтобы объединенные процессы происходили как можно быстрее и были многопоточными. В моем дизайне, который мне еще предстоит реализовать на Java, у каждого потока есть планировщик, который перепроверяет, что можно отметить, и отмечает это. Проблема заключается в разделении тиков по потокам, это легко, если есть только один уровень тикеров. Вы можете просто отмечать партии из 8 за раз. В отдельных темах. В моем примере есть вложенный цикл из 3 коллекций и разделение на две задачи, а затем эти две задачи объединяются в одну задачу для вывода результатов. Я хочу, чтобы вложенные циклы, отдельные задачи и объединенные задачи выполнялись партиями. Нужен способ отправки одновременных циклов в старые потоки. Может иметь общую коллекцию, называемую пулом тиков, которая проверяется всеми потоками. Текущий номер продукта связан с потоком. Я выбрал ÷ 8 из-за того, что 64 кратно 8. Чистое количество пакетов на поток.
```
Пока (правда) {
Для цикла в пуле тиков:
Если текущий[цикл] < thisThreadN[цикл]:
ток[контур] = ток[контур] 1
NewTickersOrResult = Loop.tick()
Если NewTickersOrResult.isTickers:
Еще:
}
```
I created a multithreading version of this without the Joinable loops. But at this time I am taking a break. I need to somehow tie the multithreading to the joinable loop. When Joinable loop received 2 or more values, it continues processing. This allows a split and merge in pipeline processing. I want joined processes to occur as soon as they can and to be multithreaded. In my design - that I am yet to implement in Java - each thread has a scheduler that rechecks what can be ticked and ticks it. The problem is splitting ticks over threads, it's easy if there is only one level of tickers. You can just tick batches of 8 at a time. In separate threads. My example has a nested loop of 3 collections and a split into two tasks and then those two tasks join into one task to print out the results. I want the nested loops, separate tasks and the joined tasks to be executed in batches. Kind of need a way to send concurrent loops to old threads. Could have a shared collection called the tick pool which is checked by all threads. The current product number is associated with a thread. I picked ÷ 8 due to the 64 being a multiple of 8. Clean number of batches per thread.
```
While (true) {
For loop in tick pool:
If current[loop] < thisThreadN[loop]:
current[loop] = current[loop] + 1
NewTickersOrResult = Loop.tick()
If NewTickersOrResult.isTickers:
Else:
}
```
Я думаю о том, как использовать производительность нескольких ядер процессора. Это требует радикального переосмысления того, как мы пишем код!
Мне пришло в голову, что циклы можно тривиально распараллелить с моим дизайном.
N = 0 .. N = 3×3×3
Если бы вы запустили метод tick во всех потоках с каждым N, вы могли бы запустить весь цикл за один раз.
I am thinking of how to use the performance of multiple CPU cores. It requires a drastic rethinking of how we write code!
It occurred to me that loops could be trivially parallelized with my design.
N = 0 .. N = 3×3×3
If you ran the tick method on all threads with every N, you could run the entire loop in one go.
Мне нужно написать присоединяемый тикер, который ожидает ввода от нескольких тикеров перед отправкой вывода. Это позволяет нам создавать конвейеры, которые разделяются и объединяются.
I need to write a Joinable Ticker that waits for inputs from multiple tickers before sending output along. This lets us create pipelines that split and merge.
Я добавлю, что вам нужен только один цикл while (true) на поток. Все остальное может быть запланировано одновременно в потоке.
I shall add that you only need one while (true) loop per thread. Everything else can be concurrently scheduled within a thread.
Вот почему я называю это виртуальным параллелизмом. Вам нужно будет использовать потоки для обеспечения параллелизма ввода-вывода. Все, что зацикливается навсегда или блокируется, не может быть составлено. Поэтому я буду писать весь свой код в будущем, чтобы попытаться никогда не блокировать и быть повторным. Это важный урок, который я усвоил при разработке своего многопоточного планировщика.
Блокировка невидима для программы. Программа не знает, что она блокируется. Вы должны знать, что метод может блокироваться, чтобы обойти его. Моя другая идея - это параллельный цикл while do, который изменяет блокировку на неблокирующую через синтаксический сахар. Это выглядит так
A1 = параллельно, в то время как { Буф = сокет.recv(1024) } Делать { Параллельно для (Socket socket : sockets) { Socket.send(buf) } } Кроссмердж А1
Этот синтаксис запускает несколько потоков для блокировки при получении данных. И для каждого из них он запускает поток в пуле потоков, чтобы обработать его и отправить в каждое соединение параллельно.
У меня есть еще одна идея - изменить приоритетный порядок выполнения. Этот планировщик в этом коде каждый раз перебирает тикеры в одном и том же порядке. Нет никаких причин, по которым мы не можем выполнять одни циклы чаще, чем другие.
That's why I call it virtual concurrency. You would need to use threads to provide IO concurrency Anything that loops forever or blocks cannot be composed. So I shall write all my code going forward to try never block and be reetrant. This is an important lesson I learned while developing my multithreaded scheduler.
Blocking is invisible to the program. The program isn't aware it is blocking. You need to know that a method can block to work around it. My other idea is a parallel while do loop which changes blocking to be non blocking through syntactic sugar. It looks like this
A1 = parallel while { Buf = socket.recv(1024) } Do { Parallel for (Socket socket : sockets) { Socket.send(buf) } } Crossmerge A1
This syntax spins up multiple threads to block on receiving data. And for each one it spins up a thread in a thread pool to handle it and send it to every connection in parallel.
Another idea I have is to change the priority execution order. That scheduler in that code round robins the tickers in the same order every time. There's no reason why we cannot execute the loops some more than others.
Интересно. Вы не использовали встроенную поддержку параллельности в Python, а использовали только базовое перечисление, индексирование и присваивание. Я думаю, это то, что нужно, чтобы понять. Это имеет воспитательное значение.
Interesting. You did not use any native support for concurrency in Python, and used only basic enumeration, indexing, assignment. I guess, that is what it takes to understand. This has educational value.