VladislavS. (29.04.2022 15:12, просмотров: 279) ответил Costic на Обычно каждый узел списка хранит значение (value) и указатель на
следующий элемент (next). Последний элемент списка указывает на
начало списка. Указатель - это обычно 32-битное число. Для случая,
когда элементы списка размещены в массиве, т.е. последовательно, то
каждый next отличается от предыдущего на константу
sizeof(ListItem). В общем, меняем указатели next на индексы
массива. Последний индекс/указатель направит нас в начало списка.-
- Предположение, что обращение к флешу занимает константное время
вижу я. - LightElf(29.04.2022 18:25)
- При наличии предвыборки флэшь, работе в прерываниии и наличии DMA
на борту контроллера, не стоит на это рассчитывать, юный падаван. - VladislavS.(29.04.2022 18:42)
- Имана. При наличии всей этой тряхомудии утверждение: "список с
указателями быстрее массива с индексом" кажется мне несколько
голословным, о мудрейший. Думаю ещё через сотню сообщений мы узнаем
модель процессора, примененного ТС и сможем оценить всю глубину
глубин. - LightElf(29.04.2022 20:54)
- Архитектуру мы таки знаем. Это Cortex-MO+. А у него доступ по
указателю будет всяко быстрее вычисления смещения из индекса,
проверки и инкремента индекса. - VladislavS.(29.04.2022 21:38)
- Какое-то верование запрещает сразу инкрементировать указатель?
Инкремент на 8-битную константу занимает, емнип, одну инструкцию.
Загрузка же указателя из флеша требует двух обращений к флешу.
Имеется ли у обсуждаемого проца кэш чтения или там просто буфер
предвыборки - неизвестно. Так чта не все так однозначно, как
говорила дочь офицера. - LightElf(30.04.2022 16:49)
- Верование или нет, но я не видел, чтобы компиляторы так делали. Но
даже если допустить, с учётом развитости косвенной адресации, это
не много что меняет. Наверное, поэтому компиляторы и не делают
подобные оптимизации. Лишнии команды в случае с индексом тоже не из
воздуха, а из флэшь читаются, тут баш на баш. В кортексах шина к
флэшь обычно 64 бит и через буфер предвыборки. Контроллеру всё
равно за данными массива в флэшь обращаться, за одно и новый
указатель прочитается. VladislavS.(267 знак., 01.05.2022 00:33)
- Суть моего спича кагбэ в том, что даже на мелких кортексах выигрыш
в количестве команд не всегда приводит к выигрышу в реальной
производительности. И раз уж мы не знаем точную модель, то не знаем
и как там флеш устроен. Потому, считаю, утверждать "так быстрее чем
эдак" несколько преждевременно. - LightElf(01.05.2022 02:05)
- Ну это же всё легко проверяется. Берём Cortex-M0+, пишем в
прерывании как у ТС код и смотрим листинги: VladislavS.(4175 знак., 01.05.2022 08:05)
- Справедливости ради, код от начала прерывания до отправки данных по
назначению одинаков в случае связного списка и инкремента
указателя. Если общая загрузка процессора не зашкалит, то результат
будет одинаков. Но зачем делать плохо, если можно сделать хорошо. - VladislavS.(01.05.2022 08:37)
- блеать. если первое требование - равномерность подачи данных, то в
текущем прерывании готовим данные для отправки в следующем.
сохраняем их в заготовленную переменную и в самом начале следующего
прерывания отправляем куда там требуется. в этом случае можно
вообще нихрена не хранить, а считать на лету. - Mahagam(01.05.2022 10:25)
- Для полноты картины посмотрим листинг и этого варианта. За сдвиг
записи полезных данных на одну команду к началу прерывания платим
дополнительной переменной в SRAM и более длинным прерыванием: VladislavS.(811 знак., 02.05.2022 10:06)
- Для полноты картины надо мой вариант было рассмотреть, причём
желательно использовать для массива индекс типа uint16_t. Тогда в
моём варианте читать из флеша в 2 раза меньше, но использовать 1
РОН. И на частотах выше 25 МГц (предел флеша), думаю, будет профит. - Costic(02.05.2022 16:54)
- Во-первых, даже для чтения переменной из RAM надо сначала загрузить
её адрес из флэшь. Во-вторых, РОН экономить смысла нет, они при
входе в прерывание сохраняются в достаточгом количестве. В-третьих,
чтение 8/16/32 бит из флэшь занимает одинаково времени, ничего тут
не сэкономишь. Ну и самое главное, зачем в рантайме вычислять из
индекса адрес элемента массива, если его можно вычислить на этапе
компиляции? Так что, приводите листинг вашего варианта - будем
посмотреть. - VladislavS.(02.05.2022 17:31)
- По-вашему, наверное как-то так: Costic(209 знак., 02.05.2022 20:59, ссылка)
- Даже проверять не буду. Кода будет стопудово больше. Надо загрузить
адрес начала массива, загрузить адрес текущего индекса, загрузить
сам индекс и сложить их. Вместо того чтобы загрузить сразу
указатель. Желание на 32-битной системе сэкономить на разрядности
переменной улыбает - обычно эффект обратный получается. Кстати,
Cortex-M0 не умеет невыровненный доступ к памяти. Если вы сделаете
упакованную структуру с малоразрядным индексом, то получите вместо
экономии VladislavS.(146 знак., 02.05.2022 21:56)
- Чушь. Вы грузите свой 32-битный указатель, у которого старшие 16+
битов всегда одни и те же. Т.е. впустую гоняете данные из медленной
флеш. В моем варианте загружается только смещение (младшие 16 бит).
О выравнивании структуры пусть компилятор заботится. короче,
демагогия. - Costic(02.05.2022 23:18)
- Компилятор как раз таки позаботится о выравнивании и будет ваши 16 бит гонять в 32-битных словах. А если вы ему выкрутите руки и упакуете структуры, то будет побайтово их читать, ибо не умеет контроллер невыровненный доступ. Збсь такая "экономия". Адресация 32-битная, а значит к вашим 16 младшим битам нужно подгрузить и прибавить старшие вместо того чтобы одним чтением загрузить сразу указатель. И нет никакой проблемы с пропускной способностью флэша в современных VladislavS.(187 знак., 02.05.2022 23:57)
- Чушь. Вы грузите свой 32-битный указатель, у которого старшие 16+
битов всегда одни и те же. Т.е. впустую гоняете данные из медленной
флеш. В моем варианте загружается только смещение (младшие 16 бит).
О выравнивании структуры пусть компилятор заботится. короче,
демагогия. - Costic(02.05.2022 23:18)
- Даже проверять не буду. Кода будет стопудово больше. Надо загрузить
адрес начала массива, загрузить адрес текущего индекса, загрузить
сам индекс и сложить их. Вместо того чтобы загрузить сразу
указатель. Желание на 32-битной системе сэкономить на разрядности
переменной улыбает - обычно эффект обратный получается. Кстати,
Cortex-M0 не умеет невыровненный доступ к памяти. Если вы сделаете
упакованную структуру с малоразрядным индексом, то получите вместо
экономии VladislavS.(146 знак., 02.05.2022 21:56)
- По-вашему, наверное как-то так: Costic(209 знак., 02.05.2022 20:59, ссылка)
- Во-первых, даже для чтения переменной из RAM надо сначала загрузить
её адрес из флэшь. Во-вторых, РОН экономить смысла нет, они при
входе в прерывание сохраняются в достаточгом количестве. В-третьих,
чтение 8/16/32 бит из флэшь занимает одинаково времени, ничего тут
не сэкономишь. Ну и самое главное, зачем в рантайме вычислять из
индекса адрес элемента массива, если его можно вычислить на этапе
компиляции? Так что, приводите листинг вашего варианта - будем
посмотреть. - VladislavS.(02.05.2022 17:31)
- Для полноты картины надо мой вариант было рассмотреть, причём
желательно использовать для массива индекс типа uint16_t. Тогда в
моём варианте читать из флеша в 2 раза меньше, но использовать 1
РОН. И на частотах выше 25 МГц (предел флеша), думаю, будет профит. - Costic(02.05.2022 16:54)
- Ирония судьбы в том, что загрузить заготовленную заранее переменную в прерывании это то же самое что выбрать по заранее заготовленному указателю из массива. В смысле равномерности. Смотрим листинги, не ленимся. Шах и мат. - VladislavS.(01.05.2022 11:45)
- Для полноты картины посмотрим листинг и этого варианта. За сдвиг
записи полезных данных на одну команду к началу прерывания платим
дополнительной переменной в SRAM и более длинным прерыванием: VladislavS.(811 знак., 02.05.2022 10:06)
- блеать. если первое требование - равномерность подачи данных, то в
текущем прерывании готовим данные для отправки в следующем.
сохраняем их в заготовленную переменную и в самом начале следующего
прерывания отправляем куда там требуется. в этом случае можно
вообще нихрена не хранить, а считать на лету. - Mahagam(01.05.2022 10:25)
- Справедливости ради, код от начала прерывания до отправки данных по
назначению одинаков в случае связного списка и инкремента
указателя. Если общая загрузка процессора не зашкалит, то результат
будет одинаков. Но зачем делать плохо, если можно сделать хорошо. - VladislavS.(01.05.2022 08:37)
- Ну это же всё легко проверяется. Берём Cortex-M0+, пишем в
прерывании как у ТС код и смотрим листинги: VladislavS.(4175 знак., 01.05.2022 08:05)
- Суть моего спича кагбэ в том, что даже на мелких кортексах выигрыш
в количестве команд не всегда приводит к выигрышу в реальной
производительности. И раз уж мы не знаем точную модель, то не знаем
и как там флеш устроен. Потому, считаю, утверждать "так быстрее чем
эдак" несколько преждевременно. - LightElf(01.05.2022 02:05)
- Верование или нет, но я не видел, чтобы компиляторы так делали. Но
даже если допустить, с учётом развитости косвенной адресации, это
не много что меняет. Наверное, поэтому компиляторы и не делают
подобные оптимизации. Лишнии команды в случае с индексом тоже не из
воздуха, а из флэшь читаются, тут баш на баш. В кортексах шина к
флэшь обычно 64 бит и через буфер предвыборки. Контроллеру всё
равно за данными массива в флэшь обращаться, за одно и новый
указатель прочитается. VladislavS.(267 знак., 01.05.2022 00:33)
- Какое-то верование запрещает сразу инкрементировать указатель?
Инкремент на 8-битную константу занимает, емнип, одну инструкцию.
Загрузка же указателя из флеша требует двух обращений к флешу.
Имеется ли у обсуждаемого проца кэш чтения или там просто буфер
предвыборки - неизвестно. Так чта не все так однозначно, как
говорила дочь офицера. - LightElf(30.04.2022 16:49)
- Архитектуру мы таки знаем. Это Cortex-MO+. А у него доступ по
указателю будет всяко быстрее вычисления смещения из индекса,
проверки и инкремента индекса. - VladislavS.(29.04.2022 21:38)
- Имана. При наличии всей этой тряхомудии утверждение: "список с
указателями быстрее массива с индексом" кажется мне несколько
голословным, о мудрейший. Думаю ещё через сотню сообщений мы узнаем
модель процессора, примененного ТС и сможем оценить всю глубину
глубин. - LightElf(29.04.2022 20:54)
- При наличии предвыборки флэшь, работе в прерываниии и наличии DMA
на борту контроллера, не стоит на это рассчитывать, юный падаван. - VladislavS.(29.04.2022 18:42)
- Это не хуже, т.к. всё равно надо хранить или индекс, или указатель.
Вопрос в том, как автору удобнее заполнять этот список/массив.
Можно использовать макросы с __LINE__, но мне кажется, что это
будет не красиво. Дополнительный РОН... это от компилятора зависит.
Смещение (+1) к индексу известно на этапе компиляции, РОН не нужен.
Главное же - удобство пользования и размещение во флэш. - Costic(29.04.2022 15:49)
- В случае с указателем, доступ к полям структуры по фиксированному смещению. Компилятор все смещения знает и жёстко закодирует. В случае с индексом надо в одном регистре хранить адрес массива, во второй индекс загружать и для доступа к полям структуры их складывать и только потом смещение использовать. Посмотрите листинги, я чуть выше все ссылки на разные реализации собрал. - VladislavS.(29.04.2022 16:38)
- Предположение, что обращение к флешу занимает константное время
вижу я. - LightElf(29.04.2022 18:25)