В MIPS, например, страница может иметь размеры 4KB, 16KB,… 64MB.
В X86-64 тоже бывают 2-мегабайтные страницы.
Про пример, конечно он искусственный, но это не отменяет того факта, что прямой доступ к данным быстрее косвенного через указатель. И что дополнительные обращения к кучу — дополнительная сериализация.
Да я и не против ни Arm-а ни MIPS-а, «пусть расцветают сто цветов».
Мотивация же может быть отличной от «а то перестанут покупать».
Вот есть такая идея, она довольно изящно решает проблемы, штатные решения которых выглядят натянуто (всё IMHO, конечно). Я открыто описал, вдруг кому интересно.
Еще вопрос возник, а как Arm64 поступает с некогерентными данными при потере контекста?
Если для каждого мелкого кусочка вызывать mmap, виртуальных страниц будет очень много.
Поэтому нужна вторая куча под разделяемые данные.
Про совмещение когерентных и локальных данных.
Допустим, в варианте с тегами у меня есть структура
struct a { volatile char shared[64]; char local[64];};
компилятор в конструкторе проставит теги (в С это должен сделать программист).
При двух аллокаторах так сделать нельзя, требуется «char *shared», косвенные обращения и дополнительные вызовы alloc|free, что неудобно и неэффективно.
Конечно, вариант «здесь и сейчас прямо под рукой» имеет преимущества.
С другой стороны, зачем тогда Arm64 разрабатывали, чего он умеет такого, чего принципиально нельзя сделать, например, на MIPS64?
Имелось ввиду, что под каждый отдельный разделяемый кусочек придется выделять сегмент, что «загаживает» TLB.
Либо иметь специальный второй аллокатор. Что не очень удобно технологически. Например, делает невозможным совмещение в одном объекте когерентных и локальных данных.
Лично мне вариант с тегами представляется более простым и логичным.
Упс, mmap проецирует содержимое устройства/файла в виртуальное адресное пространство.
Конечно, программист волен сам создавать сегменты. Но это:
1) дорого, для того и нужен runtime, чтобы буферизировать память.
2) неудобно, целых 2 механизма аллокации, кабы путаницы не вышло
3) загаживается TLB
Первый раз слышу, что память под стек выделяется каким-то особым образом.
Не могли бы привести ссылку в подтверждение?
Всё, что выделяется через кучу, разделяется между потоками. Какими сегментами выделяется память, программисту неизвестно. Но скорее всего большими т.к. у кучи свой аллокатор и для неё выгодно у системы просить большими кусками. С другой стороны, очень большие страницы порождают сложности со свопом, вот и возникает баланс интересов.
Пусть программист вызывает malloc(100) и хочет чтобы эта память была когерентной.
Кому он что должен сказать? У Runtime нет информации о типе физических страниц, которыми ему нарезали память, может они по 4К, а может и по 1Мб. Значит на ровном месте появляется системный вызов, в котором на страницу, какой бы она ни была накладываются ограничения.
Тут вот какие возражения:
1) системный вызов там где он не нужен
2) наложение ограничений на потенциально большую страницу
3) разные ограничения могут противоречить друг другу
Механизм с тегами
1) всё делает в пользовательском режиме
2) ограничения с точностью до строки
3) когерентность всё равно идёт с точностью до строки
Есть всё же разница.
Строка кэша — 64 байта, если я хочу покрыть слово, я готов мириться с тем, что под раздачу попадёт вся строка.
Страница в 4К — это уже перебор, как мне кажется, бОльшие страницы — в мегабайт и больше — совершенно непригодны для этого.
Кроме того, память выделяет runtime, я как программист понятия не имею на каких страница какого размера расположены данные. И знать не хочу.
Если у программиста будет возможность просто сказать volatile или std::atomic и гарантировать когерентность именно этих данных, это благо.
Код и данные смешивают, например, в JIT.
Про сегменты есть тонкости, если не ошибаюсь. При загрузке кода нет возможности (слишком дорого) проверять настройки сегмента, а в TLB для страницы нет такой информации.
Ок, для столицы нашей необъятной Родины десятки, пусть N.
Через Казань M, Ё-бург — K,…
В результате надо поддерживать как минимум (N+M+K)**2 вариантов матриц расстояний как результат разных стыковок.
Если честно, меня немного пугает перспектива обращать пусть даже сильно разреженную матрицу размером 300млн Х 300млн, хотя бы и всего один раз :) Она ведь сильно вырожденная, за точностью чуть не уследил и бац!
С Дейкстрой и А* всё проще — простая идея, интуитивно понятное поведение, простая реализация.
Ну почему шторм, например паром по расписанию или разводные мосты.
На большой площади предрасчет будет будет зависеть от того, с какого направления куда мы едем.
Это уже накладно. Планом Б не отделаешься.
Ориентироваться на пользовательские привычки тоже опасно. Зимой одни привычки, летом другие. А в межсезонье? В одном городе выпал снег, а в другом нет, на какую модель ориентироваться?
Насколько я понял, метод заключается в наложении разности потенциалов на стартовую и финишные точки,
затем с помощью лапласиана находятся потенциалы в узлах и кратчайший путь прокладывается по максимальному потоку.
Боюсь, что для больших графов это будет весьма расточительно,
особенно, учитывая то, что даже когда старт и финиш рядом, считать придётся весь граф или значительную его часть.
В X86-64 тоже бывают 2-мегабайтные страницы.
Про пример, конечно он искусственный, но это не отменяет того факта, что прямой доступ к данным быстрее косвенного через указатель. И что дополнительные обращения к кучу — дополнительная сериализация.
Да я и не против ни Arm-а ни MIPS-а, «пусть расцветают сто цветов».
Мотивация же может быть отличной от «а то перестанут покупать».
Вот есть такая идея, она довольно изящно решает проблемы, штатные решения которых выглядят натянуто (всё IMHO, конечно). Я открыто описал, вдруг кому интересно.
Еще вопрос возник, а как Arm64 поступает с некогерентными данными при потере контекста?
Поэтому нужна вторая куча под разделяемые данные.
Про совмещение когерентных и локальных данных.
Допустим, в варианте с тегами у меня есть структура
struct a { volatile char shared[64]; char local[64];};
компилятор в конструкторе проставит теги (в С это должен сделать программист).
При двух аллокаторах так сделать нельзя, требуется «char *shared», косвенные обращения и дополнительные вызовы alloc|free, что неудобно и неэффективно.
Конечно, вариант «здесь и сейчас прямо под рукой» имеет преимущества.
С другой стороны, зачем тогда Arm64 разрабатывали, чего он умеет такого, чего принципиально нельзя сделать, например, на MIPS64?
Либо иметь специальный второй аллокатор. Что не очень удобно технологически. Например, делает невозможным совмещение в одном объекте когерентных и локальных данных.
Лично мне вариант с тегами представляется более простым и логичным.
Конечно, программист волен сам создавать сегменты. Но это:
1) дорого, для того и нужен runtime, чтобы буферизировать память.
2) неудобно, целых 2 механизма аллокации, кабы путаницы не вышло
3) загаживается TLB
Не могли бы привести ссылку в подтверждение?
Всё, что выделяется через кучу, разделяется между потоками. Какими сегментами выделяется память, программисту неизвестно. Но скорее всего большими т.к. у кучи свой аллокатор и для неё выгодно у системы просить большими кусками. С другой стороны, очень большие страницы порождают сложности со свопом, вот и возникает баланс интересов.
Пусть программист вызывает malloc(100) и хочет чтобы эта память была когерентной.
Кому он что должен сказать? У Runtime нет информации о типе физических страниц, которыми ему нарезали память, может они по 4К, а может и по 1Мб. Значит на ровном месте появляется системный вызов, в котором на страницу, какой бы она ни была накладываются ограничения.
Тут вот какие возражения:
1) системный вызов там где он не нужен
2) наложение ограничений на потенциально большую страницу
3) разные ограничения могут противоречить друг другу
Механизм с тегами
1) всё делает в пользовательском режиме
2) ограничения с точностью до строки
3) когерентность всё равно идёт с точностью до строки
Строка кэша — 64 байта, если я хочу покрыть слово, я готов мириться с тем, что под раздачу попадёт вся строка.
Страница в 4К — это уже перебор, как мне кажется, бОльшие страницы — в мегабайт и больше — совершенно непригодны для этого.
Кроме того, память выделяет runtime, я как программист понятия не имею на каких страница какого размера расположены данные. И знать не хочу.
Если у программиста будет возможность просто сказать volatile или std::atomic и гарантировать когерентность именно этих данных, это благо.
Про сегменты есть тонкости, если не ошибаюсь. При загрузке кода нет возможности (слишком дорого) проверять настройки сегмента, а в TLB для страницы нет такой информации.
Наложить только один потенциал и смотреть куда ток утечки идёт?
Через Казань M, Ё-бург — K,…
В результате надо поддерживать как минимум (N+M+K)**2 вариантов матриц расстояний как результат разных стыковок.
С Дейкстрой и А* всё проще — простая идея, интуитивно понятное поведение, простая реализация.
На большой площади предрасчет будет будет зависеть от того, с какого направления куда мы едем.
Это уже накладно. Планом Б не отделаешься.
Ориентироваться на пользовательские привычки тоже опасно. Зимой одни привычки, летом другие. А в межсезонье? В одном городе выпал снег, а в другом нет, на какую модель ориентироваться?
затем с помощью лапласиана находятся потенциалы в узлах и кратчайший путь прокладывается по максимальному потоку.
Боюсь, что для больших графов это будет весьма расточительно,
особенно, учитывая то, что даже когда старт и финиш рядом, считать придётся весь граф или значительную его часть.
Спасибо за ссылку, может кому пригодится.