Очень интересно. А вы не пробовали использовать несколько предсказателей? Например, по одному для каждой из битовых плоскостей или разложить изображение по масштабам в пирамиду и использовать свой предсказатель на каждом уровне.
Есть у этой книги небольшой недостаток, её желательно читать всю. Там последующий главы ссылаются на предыдущие. Седжвик приводит 2-3-4 деревья, как частный случай B-деревьев, лишь для того, чтобы показать как они отображаются на RB-деревья (что это одно и то же). Далее он говорит, что данный тип деревьев (2-3-4) не эффективен в виде «наивной» реализации для структур в ОЗУ, но т.к. любое дерево можно представить в виде бинарного, есть метод, как сделать это эффективно, используя лишь один дополнительный бит на узел, это и есть RB-деревья. Работа с бинарными же деревьями у него разбирается очень подробно. Также, в главе про 2-3-4 деревья упоминается, что в последующих главах будет представлена более общая реализация B-деревьев. Там узел может иметь любое заданное листьев (N), в том числе и 3, как в вашем случае. Но B-деревья более эффективны для работы с внешними источниками данных, таких как файловые системы и базы данных.
К сожалению, ни на хабре, ни на других ресурсах я не смог найти достаточно полную информацию на русском языке…
На всякий случай, может автору будет интересно. Все вопросы со структурами данных подробно и понятно описаны в книге Роберта Седжвика «Алгоритмы на С++. Анализ структур данных, сортировка, поиск алгоритмы на графах», в том числе и на русском языке. Вся теория подробна изложена с реализацией на С++. Там описаны, в том числе, 2-...-N деревья, как частный случай B-деревьев и сами B-деревья. Вообще книга, на мой взгляд, является лучшей книгой по структурам данных для программистов.
Да, похоже выравнивание есть. Просто сбил с толку термин — «плотная» упаковка. Всегда думал что плотно можно упаковать только по-байтово, наподобие сериализации.
А правильно ли я понимаю, что ваш контейнер будет работать только на x86 архитектуре, где пофигу на выравнивание. Иначе, я не вижу где выравнивается адрес начала объекта? Попробую пояснить:
Допустим data_size() = 0. sizeof(uint8_t) = 1. Кладем в кортеж байт. sizeof(uint32_t)=4. При попытке положить целое его начало уже не будет выравнено, т.к. адрес будет data_size() + 1.
Не, я немного не об этом. Веб-сокеты, как раз, работают на всех, более или менее, современных платформах. Не работает MSE (Media Source Extensions). В моем случае, к счастью, нет необходимости поддерживать старые браузеры (до принятия WebSockets, как стандарта).
Ну, к счастью, клиентов на IOS у нас пока нет. Мы используем Web клиент как дополнительный тонкий клиент к основному, без процедуры установки. Все работает только во внутри-корпоративных сетях, где очень мало мобильных клиентов. Не совсем понял про «старые» советы. Веб-сокеты, действительно, реализованы поверх обычных tcp, но сверху там еще есть: handshake, отдельные сообщения с заголовками и т.д. Что делать с IOS пока не понятно, так как MSE там выпилено, даже в Хроме.
Да, нет. Мы вот тоже реализовали свой велосипед на С++. Правда, даже не поняли что он сложный. Гоняем по нему видео для MSE. Отлично работает на всех клиентах, кроме IOS-based.
Тут все как сами пожелаете. Про конкретное решение решение и степень его применимости не шло никакой речи. Обсуждались лишь теоретические аспекты реализации работы с видео и их плюсы и минусы, а также от том, как должны, в идеале, быть устроены модули для работы с видео, для того чтобы их можно было бы применять во всех своих решения, а не писать велосипед каждый раз под каждый новый случай, а потом бороться с последствиями упрощений.
Для начала, достаточно будет с помощью, того же, ffmpeg декодировать какой-нибудь видео-клип размером 1280х1024 и убедиться что тайминги также стоят как вкопанные.
Я в этих цифрах не вижу ни «задержки больше чем 10 мс на кадр» ни того что бы «задержка при показе кадров плавала от 0мс до 40мс»..
Так, я все понял. Исходя из ваших ответов, вы не правильно представляете себе как работают современные операционные системы. Задержки берутся не из воздуха, задержки появляются тогда, когда планировщик распределяет общее время между несколькими работающими потоками. Если у вас нет загрузки системы, то и задержкам взяться не от куда. Все это я лишь привожу для того что бы показать что очередь сообщений являясь архаичным, но 100% переносимым по причине своей фундаментальности, механизмом в состоянии выполнять свои функции.
Вы этим тестом показали лишь то, что без нагрузки процессор занят только вашей «логикой» и выполняет ваш код без прерываний на параллельные задания. Все. Больше этот тест ничего не показывает. Как только вы напишите «боевой» код и нагрузите процессор, ваши тайминги сразу же поплывут.
Ну и зачем такие синтетические тесты?! Рендерер, в моем понимании, это компонент, который сглаживает неравномерную загрузку, в том числе. Как можно говорить о том, что он плавно работает, если нет загрузки?!.. И потом 4% и 4мс, при холостом выводе, это очень много. Нужно ориентироваться на 0%.и микро секунды. Ну сами подумайте, вы выводите 25 раз в секунду с паузами между этими выводами. Для современного процессора и для видео процессора это вечность, они просто стоят и курят в сторонке. Для ссылки: средненький аппаратный декодер спокойно декодирует H264 со скоростью 500 кадров в секунду, а уж выводить на экран битмапки 1280х1024 — это тысячи.
Да я сам читаю, что не нужно переусложнять там, где можно обойтись более простым решением. Так все-таки, вы можете подтвердить, что ваши одна HD камера и 9 SD которые работаю одновременно для кругового обзора, дают такой же результат, как вы привели. Если да, то замечательно и больше тут ничего не нужно, задача решена.
Теория здесь как-раз важнее, так как у вас нет возможности проверить ваш софт на огромном парке машин. Никто не спорит, что на отдельно взятой машине, в вакуме, в идеальных условиях, где кроме одного приложения с одним окном видео больше ничего не работает, вы увидите вышеописанную картину. Вы не приводите ни разрешение видео, ни разрешение с которым оно показывается, ни текущую загрузку CPU в вашем тесте. Загрузите машину хорошо, процентов на 50, выведите 2 HD видео одновременно и еще 8 SD дополнительно. Желательно проделать данный эксперимент на 10 машинах с разной конфигураций. Только, когда во всех этих условиях вы получите идеальный результат, можно будет о чем-то говорить. Количество машин, на которых мы отлаживали систему, порядка сотни, и поверьте, написать хороший рендерер, это не такая простая задача как вам кажется.
Как раз в занятости и проблема. Тема мультимедиа обширна и требуют некоторого начального багажа для понимания. Из-за этого всегда стоит дилемма, писать полностью с нуля, чтобы было интересно читать всем, или подразумевать что статья уже для продвинутых, сужая этим охват.
Приведу пример: вот хотим мы написать статью о том как правильно писать фильтры разных типов под DirectShow. Вроде бы все знаем, кода куча — короче, садись и пиши. И тут начинается. А там COM.
А о нем нужно рассказывать?! А там жуткая многопоточность, навязанная самой архитектурой. А про многопоточность нужно рассказывать, или предполагается, что человек знает что это такое и представляет какие есть примитивы в WinAPI ?! Для быстрой разработки у нас кругом свои обертки и врапперы. А наверное интереснее будет на голом С?! Значит нужно все переписывать и тестировать. В общем, я хочу сказать, нужно четкое понимания для кого писать и какая задача ставится. Для себя, я уже давно понял, что написание статей это отдельная большая и кропотливая работа, которая требует уйму времени.
Если коротко, то частое переключение потоков не приведет к быстрой обработке данных, скорее наоборот, за счет потери времени на переключение. Но, уменьшив квант, мы можем точнее реагировать на события. Для быстрой и эффективной передачи данных между потоками или устройствами лучше использовать очереди.
Нет ли случаем полезных ссылок под рукой по DXVA силами ffmpeg?
Нет, вся информация собиралась по крупицам. Советую посмотреть исходники утилиты ffmpeg, файл ffmpeg_dxva2.c, если не ошибаюсь. Благо он один и вся работа с DXVA там сконцентрирована. И, кстати, DirectShow вообще не используете?
У нас написана библиотека для проигрывания различных данных и используется в софте наподобие нелинейных редакторов. Библиотека написана на С++ и архитектура там своя, а вот компоненты библиотеки; источники, демуксеры, декодеры и т.д. используют как на ffmpeg, так и DirectShow фильтры. За счет единого интерфейса их можно комбинировать как угодно друг с другом. Т.е. сплиттер может быть ffmpeg, а декодер DirectShow, и наоборот. Рендереры все свои. В результате можно играть данные произвольных форматов, вперемешку, с произвольной скоростью, вперед и назад. Какие преимущества/недостатки в использовании ffmpeg + Angle перед DirectShow?
ffmpeg — более гибкий, всегда можно посмотреть что и где неправильно работает, поддержка кучи экзотических форматов используемых в камерах и оборудовании.
DirectShow — проще использовать, но: платные компоненты, медленный старт-стоп, жрет ресурсы системы (память, хендлы и т.д.). Пришлось изобретать wrapper для фильтров, наподобие струпцины, чтобы пихать и забирать данные.
Да. Microsoft продолжает продвигать свои продукты и разработки и их можно понять — конкуренция. По-этому, что бы делать interop DXVA (проприетарная технология которая, в свою очередь, требует Direct-X) и OpenGL (которая используется в QT) приходится компилировать QT с Angle. Так можно в рамках Angle конвертировать Direct3D поверхности в OpenGL поверхности, которые, в свою очередь, находятся в видео-памяти, без копирования.
На всякий случай, может автору будет интересно. Все вопросы со структурами данных подробно и понятно описаны в книге Роберта Седжвика «Алгоритмы на С++. Анализ структур данных, сортировка, поиск алгоритмы на графах», в том числе и на русском языке. Вся теория подробна изложена с реализацией на С++. Там описаны, в том числе, 2-...-N деревья, как частный случай B-деревьев и сами B-деревья. Вообще книга, на мой взгляд, является лучшей книгой по структурам данных для программистов.
Допустим data_size() = 0. sizeof(uint8_t) = 1. Кладем в кортеж байт. sizeof(uint32_t)=4. При попытке положить целое его начало уже не будет выравнено, т.к. адрес будет data_size() + 1.
Так, я все понял. Исходя из ваших ответов, вы не правильно представляете себе как работают современные операционные системы. Задержки берутся не из воздуха, задержки появляются тогда, когда планировщик распределяет общее время между несколькими работающими потоками. Если у вас нет загрузки системы, то и задержкам взяться не от куда.
Все это я лишь привожу для того что бы показать что очередь сообщений являясь архаичным, но 100% переносимым по причине своей фундаментальности, механизмом в состоянии выполнять свои функции.
Вы этим тестом показали лишь то, что без нагрузки процессор занят только вашей «логикой» и выполняет ваш код без прерываний на параллельные задания. Все. Больше этот тест ничего не показывает. Как только вы напишите «боевой» код и нагрузите процессор, ваши тайминги сразу же поплывут.
Приведу пример: вот хотим мы написать статью о том как правильно писать фильтры разных типов под DirectShow. Вроде бы все знаем, кода куча — короче, садись и пиши. И тут начинается. А там COM.
А о нем нужно рассказывать?! А там жуткая многопоточность, навязанная самой архитектурой. А про многопоточность нужно рассказывать, или предполагается, что человек знает что это такое и представляет какие есть примитивы в WinAPI ?! Для быстрой разработки у нас кругом свои обертки и врапперы. А наверное интереснее будет на голом С?! Значит нужно все переписывать и тестировать. В общем, я хочу сказать, нужно четкое понимания для кого писать и какая задача ставится. Для себя, я уже давно понял, что написание статей это отдельная большая и кропотливая работа, которая требует уйму времени.
Нет, вся информация собиралась по крупицам. Советую посмотреть исходники утилиты ffmpeg, файл ffmpeg_dxva2.c, если не ошибаюсь. Благо он один и вся работа с DXVA там сконцентрирована.
И, кстати, DirectShow вообще не используете?
У нас написана библиотека для проигрывания различных данных и используется в софте наподобие нелинейных редакторов. Библиотека написана на С++ и архитектура там своя, а вот компоненты библиотеки; источники, демуксеры, декодеры и т.д. используют как на ffmpeg, так и DirectShow фильтры. За счет единого интерфейса их можно комбинировать как угодно друг с другом. Т.е. сплиттер может быть ffmpeg, а декодер DirectShow, и наоборот. Рендереры все свои. В результате можно играть данные произвольных форматов, вперемешку, с произвольной скоростью, вперед и назад.
Какие преимущества/недостатки в использовании ffmpeg + Angle перед DirectShow?
ffmpeg — более гибкий, всегда можно посмотреть что и где неправильно работает, поддержка кучи экзотических форматов используемых в камерах и оборудовании.
DirectShow — проще использовать, но: платные компоненты, медленный старт-стоп, жрет ресурсы системы (память, хендлы и т.д.). Пришлось изобретать wrapper для фильтров, наподобие струпцины, чтобы пихать и забирать данные.