Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Тупая оптимизация хуже преждевременной  (Прочитано 12940 раз)
0 Пользователей и 1 Гость смотрят эту тему.
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« : 24-02-2019 13:09 » 

https://habr.com/ru/post/441506/
До сих пор не обзавелся аккаунтом, да и не хочу. Потому пишу тут.

На работе дорос до воспитания джунов (пока тока один), потому стал больше обращать внимание на такие ошибки.
Ошибка автора статьи можно назвать это преждевременной оптимизацией, но назову ее тупой инстинктивной оптимизацией и вот почему. Первым инстинктивным способом сжатия будет выкинуть все "ненужное", но когда дошло до пакетирования, выяснилось, что мы не знаем границы данных в потоке байт. Тупая — потому, что надо было подумать хотя бы на один шаг вперед. Решение с маркером в 7-м бите тупейшее, возможно даже связано с особенностью схемы управления передатчиком. Но если взять более универсальный и, казалось бы, менее упакованный формат пакета, получим экономию. Маркировать начало пакета можно было бы двумя способами, в зависимости от способа пакетирования. Если нарезка на пакеты идет на стороне приемника, можно применить маркер из нескольких байт. Если пакетирование идет в передатчике, применить IO pin для сигнализации начала/окончания пакета.

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

Рассмотрим более универсальный вариант. Зафиксирован только тип устройств: АЦП. Одна выборка со всех каналов упаковывается как у автора, упаковкой по 10 бит на канал (точнее по bit_per_channel на канал). Выборки выравнены по байту.
В заголовке представлена дополнительная информация:
  • start_marker — маркер, который не встретится в пакете
  • packet_size — помощь в нарезке пакетов. В случае неполного пакета, например при внезапном отключении устройства, мы упремся в конец файла или входного потока.
  • device_id — номер устройства
  • timestamp — оставил как у автора, unix timestamp, хотя я бы добавил точности
  • channels — сколько каналов АЦП в одной выборке
  • bit_per_channel — бит на канал
  • record_per_sec — частота опроса, чтобы можно было рассчитать временные точки для записей
  • data — сами данные

Данные в любом порядке байт, как понравится. Я бы оставил принятый в телекоммуникациях "сетевой порядок".

Код:
struct packet_t {
    uint32_t start_marker; // =FFFFFFFF
    uint16_t packet_size;
    uint16_t device_id;
    uint32_t timestamp;
    uint8_t channels;
    uint8_t bit_per_channel;
    uint16_t record_per_sec;
    uint8_t data[]
}

Почему маркер FFFFFFFF? Потому, что появление максимального значения АЦП маловероятно и, в случае появления, можно уменьшить значение на 1, это будет не важно, т.к. АЦП и так уперся в свой потолок. Также в заголовке появление последовательности маркера практически исключено, только при: channels = 255 или device_id = 65535.
Посчитаем длину пакета для моего варианта и для автора статьи.

Мой вариант.
Сожрано под заголовок: 16 байт (расточительно!).
Размер выборки равен ceil(6 * 10 / 8) = 8 байт, потери 4 бита на выборку (волосы шевелятся!).
Размер data равен 8 * 100 = 800 байт.
Итого: 816 байт.

У автора.
Данные заняли ceil(6 * 10 * 100 / 8) = 750 (афтар молодец!).
Заголовок 4 байта.
Итого 754 байта исходных и ceil(754 * 8 / 7) = 862 в пакете (как так можно обосраться?).

Мораль: прежде чем кодить и паять, испачкайте пару листков бумаги, это дешевле и быстрее, чем переделывать.

P.S.: если говорить о реальном устройстве, необходимо еще возможность синхронизировать время на устройстве и сообщать этот факт в протоколе.
« Последнее редактирование: 24-02-2019 23:17 от RXL » Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #1 : 25-02-2019 04:47 » 

связки "однобайтовый_маркер,размер_пакета,тип_данных,данные,crc16" обычно достаточно, а то и вовсе json с z-терминатором

а оптимизировать объём вычислений сейчас нет необходимости, всё шустро считается, да и память растёт и дешевеет вроде
Записан

RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #2 : 25-02-2019 07:27 » 

В статье очень мало входных данных. Если предположить, что поток данных не имеет четкого начала (нет паузы между пакетами, либо передача пакета несколькими кусками), а приемник может начать работу в любой момент, найти начало пакета по одному байту сложнее. Мне не жалко 4 байта. А контроль, да, я упустил.

Сами юзаем JSON\0, но на PC. Опять же, канал и его пропускная способность в статье не раскрыты.

Насчет "растет и дешевеет" я бы поостерегся. Во-первых, ресурсов много бывает не долго, а во-вторых, пользователи могут пользоваться дешевым и слабым железом. Ноуты с 1-2 ГБ до сих пор продают.
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #3 : 25-02-2019 07:58 » 

RXL, дело не в жалкости 4 байтов, один байт маркера найти не сложно - во входящем потоке ищется первый такой байт, а всё, что до - это мусор. Далее по размеру пакета и длине оставшегося потока определяем правильность пакета (или статус недокачанности). При любой ошибке выкидываем один байт из потока и повторяем поиск, а при удачном вытаскивании пакета можно поступить как при неудаче, либо сразу выкинуть пакет из потока и продолжить поиск. То есть, 4 байта маркера ничем не отличаются от одного байта маркера, по сути.

а память в ноут можно нужно добавить, сам так сделал  Краснею
Записан

Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #4 : 25-02-2019 12:05 » 

Цитата
Опять же, канал и его пропускная способность в статье не раскрыты.
UART

Такую задачу решал еще 95-96м

Когда сеанс связи был ограничен по времени,  поэтому не все данные могли быть уложены в пакет

Сам пакет имел маркер старта + упакованные данные + CRC16

Рассматривали несколько вариантов, но все же остановились именно на таком.. Не думал, что еще такие задачи актуальны.

Я тогда наставил на разделении передатчика, хранилища, измерителя, но ...
Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #5 : 25-02-2019 21:27 » 

Сбор данных будет всегда актуален.
UART то UART, да неведома скорость и физическая среда.
Я все же не об этом, а о том, что непременно надо придумать новый сжатый протокол с параметрами хуже, чем у избыточного, при этом совершенно не изменяемый.
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Ochkarik
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #6 : 25-02-2019 22:25 » 

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

RTFM уже хоть раз наконец!  RTFM :[ ну или хотя бы STFW...
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #7 : 26-02-2019 00:23 » 

Ochkarik, ты про непрерывность передачи? Это не совсем так, данные посылаются периодически, по мере появления. Если есть время послать таймстамп, есть время и на заголовок.
Если задача "здесь и сейчас на коленке", решение вполне адекватное. Только зачем тогда статью писать было? Я вот вчера смеситель на кухне поменял, теперь статью писать? Улыбаюсь
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Ochkarik
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #8 : 26-02-2019 06:46 » 

RXL, там в начале текста есть фраза на которую я тоже сразу внимания не обратил "от 100 раз в секунду" не Герц! еще и  "от 100". то есть никто не обещал периодичный процесс.
и уж точно автор не просто так прилепил метку времени к КАЖДОМУ набору семплов АЦП а не сразу к сотне отсчетов)  
а это существенно меняет задачу)
PS ИМХО, писать на эту тему статью на хабре... ну это как-то... и вообще)))
« Последнее редактирование: 26-02-2019 06:50 от Ochkarik » Записан

RTFM уже хоть раз наконец!  RTFM :[ ну или хотя бы STFW...
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #9 : 26-02-2019 07:52 » 

Сто отсчетов это всего лишь ceil(6 * 10 / 8 ) * 100 = 800 байт или 8 кбит/с для асинхронного формата 8N1. Даже за 9600 не вышли. Если у него непосредсвенное подключение к РС, на 115200 он может себе позволить 1900 точек. Есть RS232 и быстрее, наверняка у него порт в конвертере USB-COM.
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Ochkarik
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #10 : 26-02-2019 11:50 » new

RXL, ну ок.
1. в статье нет слова периодически. наоборот сказано: от 100 выборок в секунду. то есть каждой выборке - свое время. "от" означает что может быть и больше и меньше и вообще произвольно изменятся. верхнюю границу он кстати не оговорил.
так что у вас разные подходы и разное назначение протокола.
у автора пакет: 8 байт данных + 4 байта время, итого 12 байт на пакет, он сожрал 14 байт.
у тебя: заголовок 16 байт данных вместе с временем+8 байт данных.
у автора поток от 1.4КБ/с при 100 выборках
у тебя от 2.4КБ/с.
разница почти в два раза, в условиях автора. но возможно подойдет для какой то другой задачи - вопрос граничных условий.

2. кстати в комментах автор пишет, что приоритет был - объем, и флешка распаяна на плату. и там же пишет, что внемлет рекоменации использования байтстаффинга.
хотя если приоритет объем и флешка - можно было бы вообще по адресам флешки разложить с известным сдвигом и зациклить буфер записи на кратном адресе флешки.

3. и кстати искажение данных ради заголовка FFFFFFFF- вообще некрасиво как-то, даже если это АЦП. опять же, на этот случай используется байтстаффинг.

и оффтоп. была у нас чем то похожая задача управления. данных было 80бит , контроллер был 8 битный. выжать надо было максимум быстродействия, так RS422 на планируемой скорости стал работать с ошибками и было поздно менять интерфейс.  так-же сначала сделали битовый флаг, первое что пришло в голову и быстро. потом переделали на байстаффинг с цр-цой.
тоже как и автор про байтстаффинг до этого случая не знали и не додумались)
так что все это вопрос нюансов задачи...
« Последнее редактирование: 26-02-2019 11:52 от Ochkarik » Записан

RTFM уже хоть раз наконец!  RTFM :[ ну или хотя бы STFW...
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines