M
O(1/n) - that’s seems legit!
O(n * log log n) - no way! impossible!
O(n * log log n) - no way! impossible!
O(1/n) - that’s seems legit!
O(n * log log n) - no way! impossible!
Size: a a a
2020 May 18
PK
MaxGraey
В смысле? Второе как раз реалистично, а вот быстрее, чем за n -- нереалистично, как и 1/n
PS
Обе статьи не читал, но уверен, что в одной — про динамическое программирование, а во второй — про (битовый) параллелизм %)
M
Да, во второй про оно самое
PK
Что такое битовый параллелизм не понимаю: это будет атомик переменная, к которой дикий congestion с тонны тредов будет?
МБ
Что такое битовый параллелизм не понимаю: это будет атомик переменная, к которой дикий congestion с тонны тредов будет?
Не. Это когда биты определяют однозначно ту область памяти, с котрой надо работать.
PK
Наверное, я живу under a rock, но в идеальном мире, в котором можно адресоваться к индивидуальным битам, при том параллельно, это может и будет работать
PK
Не. Это когда биты определяют однозначно ту область памяти, с котрой надо работать.
И никто не будет эти битовые маски менять? SPMC?
AS
O(1/n) при безудержном параллелизме -- это как "любая зависимость выглядит линейной, если её нарисовать в логарифмических координатах достаточно толстым маркером!"
МБ
И никто не будет эти битовые маски менять? SPMC?
Какие маски?
PK
Не. Это когда биты определяют однозначно ту область памяти, с котрой надо работать.
Где эти биты живут?
PK
Это какое-то машинное слово, допустим, которое выполняет роль маски для хождения по регионам памяти
МБ
Не обязательно, от структуры данных существенно зависит. В качестве примера - кодировки кадров в видеопотоках. YUV2 какое-нибудь
PK
Наверное, я слишком с практической точки зрения пришел, унесу ее куда-нибудь подальше) бесполезно что-то дальше таким образом описывать
PS
Наверное, я слишком с практической точки зрения пришел, унесу ее куда-нибудь подальше) бесполезно что-то дальше таким образом описывать
С практической точки зрения — одна команда xor на 32-битном процессоре совершает 32 1-битных параллельных операции :)
МБ
А чего такого? Разнести величину по "плоскостям" памяти по битам, чтобы к битам был независимый доступ, - вполне себе практическое и широко используемое решение.
PK
А чего такого? Разнести величину по "плоскостям" памяти по битам, чтобы к битам был независимый доступ, - вполне себе практическое и широко используемое решение.
Независимый доступ к битам из нескольких потоков -- это как?) Точно эффективнее других, более приземлённых, решений будет?
МБ
Независимый доступ к битам из нескольких потоков -- это как?) Точно эффективнее других, более приземлённых, решений будет?
Используют же зачем-то в обработке мультимедии и сигналов. Наверное, есть выгоды.
PK
Как именно используют?)) Это точно решения без оверхеда?
PK
Вроде расстановки барьеров lfence/mfence по коду