Оптимизация ядерной графики

Kernel-side graphics support

POLL Ваше мнение об оптимизации GUI ядра

Total votes: 68
Оставить как было
24%
16
Убрать только CGA и VGA, оставить VESA1.2
7%
5
Оставить только VESA2-режимы (без изменения)
10%
7
Разделить 24 и 32bpp графику в условно-компилируемые блоки
26%
18
Оставить в ядре единственный 32bpp-режим
32%
22

  • Mario

    art_zh wrote: При этом сама 2мегабайтная таблица состоит из нескольких широченных полей, всю информацию из которых можно упаковать в 100-200 байт...
    Если это не идиотизм, то что?
    Я уже вообще запутался о какой таблице идет речь?

    У нас ведь область используется для проверки какому окну принадлежит видимая точка.
    Соответственно 1920*1200* 256 (глубина оконного стека) = 2,2 Мб. Как можно эту информацию упаковать в 100-200 байт? Даже если хранить только координаты окна и хитро высчитывать это получается уже 16 байт (4 dword координат, чтобы не терять время на всякие левые преобразования) на 256, итого 4 Кб. Однако у меня большие сомнения, что дополнительные вычисления для окон не съедят полученную прибыль от уменьшения размера области данных. Потому что придется также для каждой точки вычислять на лету все пересечения и наложения окон и придется это делать чаще, поскольку в текущем виде данные в области перерасчитываються лишь при изменении порядка окон в буфере.

    Есть правда идея хранить только по Х и Y две области данных, что кстати будет значительно меньше.
    1920 +1200 = 3120 байт. Однако это еще надо продумать.

    З.Ы. Вообще-то требуется больше памяти - на каждую точку нужно 256 битное число, чтобы каждый бит отвечал за свой слой. В этом случае:
    1920*32 + 1200*32 = 61440 + 38400 = 99840 байт или 97, 5 Кб. В общем около 100 Кб в противовес 2,2 Мб.
  • User avatar
    art_zh Kernel Developer
    Posts 1465
    Joined: Fri Aug 14, 2009 1:46 am

    Mario
    Я не говорю про 255 раскрытых окон (хотя даже и в этом случае на экране будут видны только 20-30 из них)

    Типичный случай: на экране висят 3-4 окна (иконки и панель задач не счет).
    Экранная карта в этом случае представляет собой массив из длинных цепочек одинаковых байтов, к тому же с очень высокой степенью повторяемости.

    Прогони такую структуру через 7z - упакуется байт в 200, не больше
  • Mario

    art_zh
    Можно и без упаковки - если вспомнишь как реализуется доступ к матрице в цветомузыкальной установке например (пример из электроники). Я дописал пост после З.Ы.
    Получается использование проецируемой трехмерной матрицы. Коду придется проверить установлены ли биты в текущем слое в обоих областях и есть ли до них биты в более верхних слоях.

    С упаковкой проблема в том, что место динамически приходится выделять и освобождать , плюс сама распаковка делается не мгновенно. Так что в худшем случае будет кушать те-же 2 Мб.
  • Serge Kernel Developer
    Posts 3952
    Joined: Wed Mar 08, 2006 6:25 pm

    art_zh
    на негоризонтальных линиях, свободных пикселях и тексте процент попадания в кэш очень невысок
    Вот этого мы точно не знаем. У современных процессоров очень эффективный кеш.
    Результат (время вычисления FHT по 1024 точкам) = 68533 плюс-минус 122 такта
    с включенным кэшированием экранной таблицы : 68976 плюс-минус 487 тактов
    То есть в данном тесте включение кеширования никак не снижает быстродействие кода не связанного с отрисовкой.

    Я согласен с тем, что отрисовка с таблицей забивает кеш и оказывает негативное влияние на быстродействие системы в целом. Но насколько велико это влияние сказать сложно. И я уверен что промахи кеша очень слабо влияют на быстродействие vline и putpixel, потому что там упор в видеопамять. Если есть способ "на лету" паковать и распаковывать байтовую карту то он сэкономит кеш и не скажется на скорости этих функций. Очень вероятно и на скорости hline. Она тоже упирается в видеопамять, только у неё предел выше.
  • User avatar
    art_zh Kernel Developer
    Posts 1465
    Joined: Fri Aug 14, 2009 1:46 am

    Serge wrote:То есть в данном тесте включение кеширования никак не снижает быстродействие кода не связанного с отрисовкой.
    Снижает, я специально обратил внимание на погрешность замеров (цифра после "плюс-минус" - это двойная дисперсия выборки):

    - время преобразования уменьшилось, и этот эффект достоверен на 90% (сдвиг между средними значениями - чуть меньше двух сигм).
    - без кэширования экранной таблицы дисперсия по времени снижается вчетверо.
    ______
    Моя интертрепация такова:
    1) выполнение некоего длинного алгоритма занимает строго определенное число тактов - если все данные уже загружены в кэш.
    2) в начале выполнения программы кэш забит посторонним мусором, который совсем недавно очень интенсивно использовался.
    3) остаточный рейтинг некоторых блоков этого мусора (например, рамки недавно открытого окна) чрезвычайно высок.
    4) при загрузке новых данных из кэша в первую очередь выкидываются блоки с минимальным рейтингом.
    5) некоторые из этих данных могут потребоваться в течение контрольного промежутка времени
    вывод - увеличение непроизводительных затрат времени при кэшировании экрана - хорошо согласуется с экспериментом.
    без кэширования таблицы эти затраты (и их статистический разброс) меньше - в этом случает основная часть системы и в самом деле резидентно сидит в кэше.

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

    Я выбрал FHT для чистоты эксперимента, - здесь на замер времени влияет только цифродробилка - системных вызовов нет.
    Интересно будет сравнить другие программы. - Вечерком отпишусь.
    Если есть способ "на лету" паковать и распаковывать байтовую карту то он сэкономит кеш и не скажется на скорости этих функций. Очень вероятно и на скорости hline. Она тоже упирается в видеопамять, только у неё предел выше.
    Будем работать.
    Last edited by art_zh on Thu Nov 25, 2010 5:52 pm, edited 1 time in total.
  • Serge Kernel Developer
    Posts 3952
    Joined: Wed Mar 08, 2006 6:25 pm

    art_zh

    По средним значениям разница 443 такта (+0.646%) , по минимальным 78 тактов. При том, что среднее число тактов меньше 70 тысяч. Кто это сможет заметить на трёхгигагерцевом процессоре ? Применение prefetch позволит ещё сэкономить в тактах.

    Сделал ещё тесты
    04.PNG
    04.PNG (8.46 KiB)
    Viewed 5439 times
    слева обычное ядро, справа ядро с форсированной отрисовкой линий (edi=1). Скорость vline практически не изменилась. И финт ушами
    03.PNG
    03.PNG (8.49 KiB)
    Viewed 5439 times
    прячем тестовое окно так что отрисовки не происходит. Обычное ядро, слева тестовое окно закрыто KFar
    vline 141288*350 = 49 450 800
    hline 183510*270 = 49 547 700
    вот и всё влияние промахов кеша на отрисовку.
  • User avatar
    art_zh Kernel Developer
    Posts 1465
    Joined: Fri Aug 14, 2009 1:46 am

    Serge
    Убедил, буферизация вывода действительно ускоряет рисование до 3.7 раз (похоже, запись во фреймбуйр идет блоками по 64 байта).
    Дык я в этом и не сомневался!

    Все остальные задержки - программные (очень остроумный второй пример, браво!) и непродуктивность кэша (особенно актуально для полноэкранной графики).
  • Mario

    Я несколько выше предложил модель экономящую память, работающую без сжатия. Несколько позже попытаюсь все изложить в графическом виде, чтобы объяснить суть. Все-же 100 Кб или 2,2 Мб - практически без потерь в скорости, поскольку как и предполагалось нас останавливает скорость обмена именно с видеопамятью. Обмен же с ОЗУ значительно более быстрый и даже удвоение времени затрачиваемого на вычисления не скажется на самом выводе, но даже этого можно избежать если правильно реализовать код.

    Единственный минус пока, который я знаю, в моей модели на текущий момент, это то что окна будут рассматриваться исключительно как прямоугольные области, без возможности сделать дырку в середине окна.
  • Serge Kernel Developer
    Posts 3952
    Joined: Wed Mar 08, 2006 6:25 pm

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

    Последние 10 лет видеокарты используют тайловую организацию видеопамяти. Пикселы располагаются не построчно, а блоками 4х2 или 2х2 пикселя, которые объединяются в бОльшие блоки по 2 или 4 кБ. В этом случае соседние пиксели на экране попадают в соседние линейки кеша gpu.
  • User avatar
    art_zh Kernel Developer
    Posts 1465
    Joined: Fri Aug 14, 2009 1:46 am

    Mario
    Надо бы что-то такое простенькое придумать, и желательно с дырками.

    Serge
    Угу, я тоже думал о тайлах (переводится как "кафельная плитка" или типа того)

    Народ,
    а что если мы системно разрешим только окна четного размера (в пикселях) для всех четырех углов?
    - пользователь этого даже не заметит,
    - железу это очень сильно понравится,
    - карта экрана (даже если ее не удастся заменить чем-то более разумным) усохнет в 4 раза,
    - и еще растровые шрифты можно будет сильно сжать и ускорить.
  • Mario

    art_zh wrote:Mario
    Надо бы что-то такое простенькое придумать, и желательно с дырками.
    С дырками не получиться экономии - либо дырки, либо экономия. Впрочем с 2003 года (насколько я знаком с системой начиная с Menuet) операционка замечательно обходиться без дырок. 99,99% приложений.
    art_zh wrote: Народ,
    а что если мы системно разрешим только окна четного размера (в пикселях) для всех четырех углов?
    - пользователь этого даже не заметит,
    - железу это очень сильно понравится,
    - карта экрана (даже если ее не удастся заменить чем-то более разумным) усохнет в 4 раза,
    - и еще растровые шрифты можно будет сильно сжать и ускорить.
    Не уверен, что такая оптимизация заранее имеющая известные и неизвестные (пока) ограничения полезна для дальнейшего развития.
  • Mario

    Вот собственно что я подразумевал:
    4.png
    4.png (13.66 KiB)
    Viewed 4633 times
    Весь фокус в том что для такой однобитовой матрицы не нужно хранить всю структуру. Достаточно хранить две проекции - на сторону X (горизонтали) и сторону Y (по вертикали). В результате на пресечении двух единиц есть точка, если хотя-бы по одной стороне отсутствует единица, то точки нет. Когда два нуля, то само собой ноль сразу.

    Для хранения 256 слоев каждой точки на каждой стороне нужно 256 битовое значение, т.е. 32 байт.
    Вся проверка сводиться к обработке этих 32-х байт по Х и 32-х байт по Y, разумеется это в крайнем случае если окно самое нижнее в оконном стеке. Самое верхнее окно вообще проверять не нужно.
    Т.е. Каждое 32-х байтное значение это набор слоев по сути.

    Если обрабатывать dword'ами, то для самого нижнего окна это будет 8 проверок на Х и 8 проверок на Y. Опять же это крайний случай. Проверка каждого для каждого dword это команда test - проверка на наличие установленных битов выше текущего рассчитываемого слоя. Причем если проверять с самого верхнего слоя то в общем случае это будет быстрее, чем проверять от нижнего к верхнему.

    Из плюсов, кроме существенной экономии памяти пересчет при изменении позиции окна в оконном стеке значительно ускорится.
  • User avatar
    art_zh Kernel Developer
    Posts 1465
    Joined: Fri Aug 14, 2009 1:46 am

    Mario
    Хорошо. Битовые поля просматриваются легко и просто.
    Хотя еще экономичнее в этом случае просматривать (на больше/меньше) для каждого окна его x1, y1, x2 и y2 - тут даже отдельная структура не нужна, координаты каждого окна известны. И работать будет явно быстрее, чем моя некэшируемая таблица :roll:

    Только надо как-то эффективно проверять перекрытие окон - перетряхивать весь оконный стек?

    И потом, надо ведь не просто определить видимость одной конкретной точки (для этого, кстати, нынешняя таблица лучше всего приспособлена).
    Как я понял Serge'a, надо уметь быстро (и просто) отрезАть от заданной линии невидимые куски, после чего забивать видимую часть линии во фреймбуфер на максимально достижимой скорости (например, rep movsd без дополнительных проверок)
  • Serge Kernel Developer
    Posts 3952
    Joined: Wed Mar 08, 2006 6:25 pm

    Сложноватой получится проверка. И ещё одна проблема. Карта окон используется для определения окна в точке (x,y) и установки соответствующего курсора.

    И не забываем про эмуляторы. Там просадка будет не слабой. Особенно в Боше.

    Нынешний вариант для Колибри самый оптимальный. Своеобразный z-буфер - размен памяти на быстродействие это обычное явление.
    • Post Reply

    Return to “Graphics subsystem”

    Who is online

    Users browsing this forum: No registered users and 6 guests