T omask = zmasks[D-1]<<i, imask = ~omask

Вынеси из цикла все эти омаски и имаски в предварительно просчитаные (16 штук всего). Внутри цикла оффсет и фикс только что-то значат.

А оффсетов тоже только 16?

Вынеси из цикла все эти омаски и имаски в предварительно просчитаные (16 штук всего).

Можно конечно, но думаю с этим и компилятор справится. Их не 16 а примерно 128 каждой уже получается.

оффсетов вплоть до 2^64.

128

Где?

i<D

zmasks[D-1]

Если их больше 16, то ты вышел за пределы zmasks

там для каждого D делается zmask[D-1]<<i где i=0..D-1

Этот Мортон

в аккурат испольется в MPI-AMRVAC для нумерации ячеек. Я как-то прям рядышком смотрел (и он там похожей абра-кадаброй высчитывается), но как именно у соседних ячеек находится не знаю. Времени сейчас нет особо туда лезть; но при случае подсобить могу.

Спасибо;-)

Как просто для соседней ячейки найти я знаю (см. исходный пост). Тут именно вопрос как найти соседнюю по диагонали, причем сделать это проще чем в общем случае.

соседа по диагонали

Зачем это может понадобиться, особенно для многомерных матриц?

Чем это отличается от вычисления N соседей, где N - размерность?

Хотя, скорее всего, твое решение и есть реализация этого.

Зачем это может понадобиться, особенно для многомерных матриц?

это долго обьснять, но многомерные матрицы (шо это вообще за зверь?) тут не очень причем.

Чем это отличается от вычисления N соседей, где N - размерность?

А как расположены эти соседи?

А как расположены эти соседи?

Встречный вопрос. Что имелось в виду под «соседом по диагонали»? Я думал, это диагональ N-мерного куба, как следствие «сосед по диагонали» - это «сосед по всем ординатам».

Почти правильно. Если у нас есть ячейка с координатами (i,j,k) то под соседом по диагонали понимается (i+1, j+1, k+1)

Но i, j, k не обязательно совпадают, т.е. это не обязательно именно диагональ куба. И такой сосед только один (да, вообще есть много диагоналей, но понимается именно эта диагональ и именно это направление).

(i+1, j+1, k+1)

что есть (i,j,k) + (1,0,0) + (0,1,0) + (0,0,1) - сумма соседей по ординатам. Если есть простой алгоритм нахождения соседа по любой ординате, то сосед по диагонали - (последовательная) сумма соседей по ординатам.

Ну именно так и делается, вопрос в том есть ли более простой алгоритм не требующий цикла по ординатам

Балда, у тебя zmasks размером 16!

Это маски для разных D (размерностей пространства).

Для каждой размерности пространства D для каждой оси номер i (0<=i<D) есть СВОЯ маска, она делается из zmask для этой размерности сдвигом на i бит.

Прежде чем называть кого то балдой научитесь читать код, а то совсем идиетом выглядите - в пяти строчках который комментарий разобраться не можете… ;-(

Я тупой, объясните на пальцах нахрена нужно это всё? Ну есть у меня трёхмерный массив, ну сделаю я эту кривую по нему получив линейный список «координат» получается. И чё? Не, ну я прочёл что оно применяется в херовой горе всяких штук. Но чёт я недопонимаю суть.

Я знаю как мин. два применения (на самом деле их наверное больше):

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

2. простой способ развернуть некоторые виды рекурсии в цикл, в частности обходы 2^D деревьев так сильно упрощаются.

простой алгоритм не требующий цикла по ординатам

патентуй, разрешаю.

Прежде чем

Ой б....

D = 100;

zmasks[ D - 1 ];

Если твоя поделка не падает, значит D не бывает больше 16. Иначе:

СВОЯ маска

Означает у тебя что есть не один, а куча zmasks'ов (наборов масок) разных размерностей, из которых ты достаёшь нужную маску zmasks_A[D - 1] zmasks_B[D - 1] по индексу, который, для конкретного zmasks_X может быть и больше 16.

Что до значения i — то ваще похер, ибо сначала ты получаешь значение маски по индексу, и только потом его сдвигаешь.

Давайте Вы просто модифицирует эти пять строчек что бы проиилюстрировать что именно Вы имеете ввиду?

Можно начать с D=3 и считать что других D не бывает.

И ещё вопрос (код на питоне)

n=0
for D in range(16):
  for i in range(D): n += 1

чему равняется n? А ведь это число РАЗНЫХ масок.

Ну есть у меня трёхмерный массив, ну сделаю я эту кривую по нему получив линейный список «координат» получается. И чё?

Спектр объекта более компактный, его проще фильтровать и паковать.

P.S. Пример: «Гильбертов кирпич» © — > кошмар водопроводчика :)

ну надо заметить, что Z-кривая не такая хорошая в смысле локальности и пр. как кривая Гильберта, но ее зато легко делать через всякие битовые операции. Вот Гильберта экономно сделать - это кошмар не только водопроводчика… ;-)

Давай-ка лучше ты покажешь как ты вызываешь эти Т.

И как у нас n влияета на значения D или i?

Судя по картинке это «Гильбертов Доширак».

Сигнатура функции неясна? T это различные варианты int.

Нет уж, Вы или проиллюстрируйте свою мысль кодом (может я Вас неправильно понял), или я буду считать что я Вас понял правильно и Вы предложили фигню.

неясна?

ясна.

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

напиши код, или я буду считать

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

и вот эти люди пишут софт...

Судя по Вашей речи, Вы перепутали ЛОР с родной Вам гопотой в подворотне.

Насколько я понял Вашу глубокую мысль

Вынеси из цикла все эти омаски и имаски в предварительно просчитаные (16 штук всего). Внутри цикла оффсет и фикс только что-то значат.

Вы предлагаете сделать что то вроде такого

const uint64_t zmasks[16]={
  0xffffffffffffffff, 0x5555555555555555, 0x9249249249249249, 0x1111111111111111,
  0x1084210842108421, 0x1041041041041041, 0x8102040810204081, 0x0101010101010101,
  0x8040201008040201, 0x1004010040100401, 0x0080100200400801, 0x1001001001001001,
  0x0010008004002001, 0x0100040010004001, 0x1000200040008001, 0x0001000100010001 
};

const uint64_t omasks[...], imask[...]; // заранее посчитанные таблицы

template <int D, typename T> T zoff_diag_shift(T offset){  
  for(int i=0; i<D; i++){
    T fix = offset&imask[D][i];
    offset = (((offset|imask[D][i])+1)&omask[D][i])|fix;
  }
  return offset;
}

Если это так, то Вы ошибаетесь - omask-ов и imask-ов вовсе не по 16 штук, их больше сотни каждой. Кроме того это не даст никакого выигрыша, поскольку компилятор и так развернет цикл и вычислит все эти omask и imask в компайл-тайм.

С каких пор она Мортона, а не Z-curve?

С тех пор как Мортон предложил ее юзать в геофизике ЕМНИП.

G. M. Morton. A computer Oriented Geodetic Data Base; and a New Technique in File Sequencing. — Ottawa, Canada: IBM Ltd., 1966. — (Technical Report).

что то вроде такого

Да, и это только первый шаг. После этого желательно подумать, а не получится ли прекалькулировать и оффсет с фиксом.

поскольку компилятор и так развернет цикл

Ну и пусть разворачивает то, что останется (оффсет и фикс).

omask и imask не по 16 штук, их больше сотни каждой

НЕ уникальных. А уникальных по 16.

как ты ловко переклал с больной головы на здоровую! условия ставишь?

Читая по вашим суждениям, решил стать перловщиком. Учу перл на досуге, времени в вагон пока карантин. Скоро буду поучать всех Перлу.

Владимир

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

Этому анону я бы поставил подпись «Нейроночка Владимир».

подумать, а не получится ли прекалькулировать и оффсет с фиксом.

У меня не получилось. А у Вас?

НЕ уникальных. А уникальных по 16.

Так код от Вас с иллюстрацией не-уникальности будет? Потому что если сдвиг масок по i не делать, то смысла в выносе нет, это все полумеры (допустим компилятор тупой). А если сдвиги масок делать, то их сразу становится за сотню.

если сдвиг масок по i не делать

Эти сдвиги (значения «omask») не уникальные, птмшт у тебя «i» тоже не бывает больше 16. И ты гоняешь «T» максимум 16 раз, где внутри каждого «T» ты гоняешь 16 раз «i».

то их сразу становится за сотню

НЕ уникальных. Чуешь?

код будет?

Ты опять?

У меня не получилось (прекалькулировать и оффсет с фиксом)

А вот этих тогда будет полный прекалькулированый набор в 16^2.

НЕ уникальных. Чуешь?

Все 100 с гаком будут разные.

Ты опять?

Это самый простой способ изложить свою мысль. Не волнуйтесь, я не собираюсь заставлять Вас делать свою работу;-)

А вот этих тогда будет полный прекалькулированый набор в 16^2.

этих будет столько же сколько значений аргумента на входе, много больше чем 16^2.

Все 100 с гаком будут разные

Проверял?

Не волнуйтесь

Вот и хорошо. Я бы может даже и расчехлился, но в данный момент мне проще писать текстом.

Проверял?

Это как бы и так очевидно по построению. Каждая zmask это в двоичном виде …00010001, единицы стоят на каждой D-той позиции, остальное нули.

так очевидно

Походу нет.

Каждая zmask

У тебя их всего 16!

на каждой D-той позиции

D то каким боком к значению змаски внутри итерации цикла?

Ты это значение змаски получаешь по индексу (D - 1) и D никак не участвует в формировании значения.

И только потом ты сдвигаешь значение на i. Где i тоже не может быть больше 16, т.к. «for ... i < D ...».

Таким образом, ты 16 раз крутишь одни и те же 16 значений для omask и imask.

Слушайте, ну если Вам не очевидно и Вы мне не верите, то давайте уже прекратим этот разговор. К ответу на вопрос топика это все равно не приближает.

И не увидел демиург, что его программа работает в 16 раз медленнее чем могла бы. И сказал демиург: «Это хорошо!».

Удачи!

Хм, а чего тут думать?

Значение Z-кривой получаются просто чередованием бит координат по каждому измерению. Соответственно, «просто» так добавить/отнять любое ненулевое значение по правилам обычной двоичной арифметики не получиться, ибо нужно чтобы перенос «прыгал» через биты соответствующие другим координатам.

Поэтому приведенный код можно улучшить только избавившись от лишних битовых операций и зависимостей по данным, чтобы CPU мог выполнить все действия (кроме слияние результатов) параллельно.

Пожалуй это неплохое задание для лабы по темам оптимизации и variadic templates.

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

Надо будет проверить как эта штука ложится на конвейер и можно ли прикрутить векторизацию.

Насчёт прыжков по битам все верно, но для перевода в обычные координаты и обратно есть загадочные операции с магическими числами, выходит сильно быстрее чем руками биты сдвигать/раздвигать.

https://en.wikipedia.org/wiki/Advanced_Bit_Manipulation#Parallel_bit_deposit_and_extract

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

В очень грубых тестах, это процентов на 5% получилось быстрее. Как-то мало. Я думал, что если показать компилятору отсутствие зависимостей по данным между итерациями, то он сделает больше. Если не понятен код zoff_diag_shift2*: он просто вычисляет инкрементированные координаты отдельно и потом собирает из них результат, а не модифицирует одну и ту же переменную. Пробовал убирать рекурсию, всё аналогично. Подозреваю, что быстрее могло стать из-за того, что |fix ушло.

#include <cstdint>

#include <functional>

const uint64_t zmasks[16]={
  0xffffffffffffffff, 0x5555555555555555, 0x9249249249249249, 0x1111111111111111,
  0x1084210842108421, 0x1041041041041041, 0x8102040810204081, 0x0101010101010101,
  0x8040201008040201, 0x1004010040100401, 0x0080100200400801, 0x1001001001001001,
  0x0010008004002001, 0x0100040010004001, 0x1000200040008001, 0x0001000100010001
};

template <int D, typename T>
T zoff_diag_shift(T offset)
{
    for(int i=0; i<D; i++){
        T omask = zmasks[D-1]<<i, imask = ~omask, fix = offset&imask;
        offset = (((offset|imask)+1)&omask)|fix;
    }
    return offset;
}

template <int D, int I, typename T>
T zoff_diag_shift2_step(T offset)
{
    T omask = zmasks[D - 1] << I;
    return ((offset|~omask) + 1)&omask;
}

template <int D, int I, typename T>
T zoff_diag_shift2(typename std::enable_if<I == 0, T>::type offset)
{
    return zoff_diag_shift2_step<D, I, T>(offset);
}

template <int D, int I, typename T>
T zoff_diag_shift2(typename std::enable_if<I != 0, T>::type offset)
{
    return zoff_diag_shift2_step<D, I, T>(offset)
         | zoff_diag_shift2<D, I - 1, T>(offset);
}

template <int D, typename T>
T zoff_diag_shift2(T offset)
{
    return zoff_diag_shift2<D, D - 1, T>(offset);
}

extern int n;
int bla = zoff_diag_shift<10, int>(n);
int bla2 = zoff_diag_shift2<10, int>(n);

это процентов на 5% получилось быстрее

Менее очень грубый тест показал, что мой вариант где-то на ~40% быстрее оригинала, что неплохо. (Изначально я мерял левые операции, которые сильно исказили результаты.)

Спасибо, интересно. Действительно fix в таком подходе ненужен оказывается.

Но я не очень понимаю так ли необходимо заморачиваться с шаблонной рекурсией, ведь D известен в компайл-тайм а короткие циклы компилятору разворачивать и оптимизировать вроде проще чем рекурсию на шаблонах?

Не факт, что цикл особо проще, хоть его структура и заранее известна компилятору. Я попробовал вот так:

template <int D, typename T>
T zoff_diag_shift7(T offset){
    T result = 0;
    for (int i=0; i<D; i++) {
        T omask = zmasks[D-1]<<i, imask = ~omask;
        result |= (((offset|imask)+1)&omask);
    }
    return result;
}

Он быстрее оригинала, но медленнее варианта выше (~430ms, против ~405ms и ~650ms).

Можно глянуть выхлоп -S, ИМНО должно быть примерно одинаково. Видимо для радикального ускорения надо юзать векторизацию.

На GCC5 первая версия быстрее, на GCC9 одинаково. Я использовал GCC5.