Кольцевой буфер FIFO

Normas
Offline
Зарегистрирован: 17.05.2017

При использовании кольцевого буфера  FIFO, если не хочу переполнять его (при переполнении буду  выставлять флаг) из физического размера буфера SIZE  два элемента всегда остаются неиспользуемыми? Те максимальная загрузка =(SIZE-2) или я чего-то не додумал?

Normas
Offline
Зарегистрирован: 17.05.2017

wdrakula
wdrakula аватар
Онлайн
Зарегистрирован: 15.03.2016

1.Для именно FIFO указатели делаются на первую занятую клетку и первую свободную, а нет так, как вы написали. Тогда никакой херни не происходит.

2. длину нужно делать только степенью двойки, тогда инкремент/декремент естественным образом максИруестя через AND.

3. если Ваш код требует учета каждого такта, то нужно взять камень побыстрее, сейчас не 80-е годы. Они даже по цене не будут особо различаться ;).

 

qwone
qwone аватар
Offline
Зарегистрирован: 03.07.2016

Я чего-то не понимаю или ТС запутался в своем незнании.

struct date {
  int D1;
  int D2;
};

struct date *start_buffer=NULL; //указатель на начало буфера


void setup() {
  start_buffer = new struct date[10];// создание буфера
  start_buffer[0].D1 = 5;
  start_buffer[0].D2 = 6;
  
  start_buffer[1].D1 = 5;
  start_buffer[1].D2 = 6;
}

void loop() {
  // put your main code here, to run repeatedly:

}

 

Normas
Offline
Зарегистрирован: 17.05.2017

qwone пишет:
Я чего-то не понимаю или ТС запутался в своем незнании.
Пока второе,  но я стремлюсь разобраться в решении вопроса. Спасибо, что помогаете понять.

wdrakula
wdrakula аватар
Онлайн
Зарегистрирован: 15.03.2016

Квон, дорогой! Вы - очень неплохой программист-самоучка. За  год, который я наблюдаю Вас на форуме, Ваш код стал сильно лучше.

Примите как совет, прошу Вас, пора приступить к системному профильному образованию. Нужно спокойно и планомерно освоить Кнута. Все три тома. И задачки порешать, хотя бы те, что не очевидны.

 

Normas
Offline
Зарегистрирован: 17.05.2017

wdrakula пишет:
3. если Ваш код требует учета каждого такта, то нужно взять камень побыстрее, сейчас не 80-е годы. Они даже по цене не будут особо различаться ;).
Крохоборничаю по тактам про запас, на 2560 занятость процессорного времени около 80%, основное время занимает loop, но буду выяснять тк  вполне возможно проблема  аналогичная "блокирующему Serial",  когда программа отправила данные через библиотечную функцию и функция ждет опустошения буфера или подтверждения завершения отправки от устройства. Тогда единственная цель ожидания не дать отправить следующую порцию данных пока устройство не освободится. 

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

Перейти на быстрый Due ARM пока не получается - ее драйверы творят гемор , после загрузки программы отваливается USB компорт, через который только что загружена программа. Причем, для разных версий IDE и драйвера платы ведет себя по разному. Итого - на некоторых версиях IDE удается скомпилировать и загрузить программу в Due, но она не работает - не могу даже помигать светодиодом. Проблема или с версией IDE или с операц. системой. Может быть есть ошибки в ARM - большой раздел Errata у производителя  огорчает. В общем, с Due , о/c и версиями IDE головная боль  и с ней буду разбираться отдельно, а пока использую 2560.

wdrakula пишет:
2. длину (буфера=SIZE) нужно делать только степенью двойки, тогда инкремент/декремент естественным образом максИруестя через AND.
Спасибо за хорошую идею, сделаю буфер SIZE=1024 (или 2048), тогда указатель станет фактически позиционным кодом и его инкрементация  сведется к перемещению единицы при помощи сдвига >>1  по 10-битному (или 11-битному для или 2048) полю. А если указатель станет=0 (единица ушла из младшего разряда), нужно дать ему значение b1 000 000 000 (для направления движения указателя вправо), я Вас правильно понял? Или для скорости выполнения программы не делать указатель длинее 8 бит? (тогда SIZE= 256) 

По п.1 осмыслю и спрошу позже, если согласитесь ответить.

Normas
Offline
Зарегистрирован: 17.05.2017

wdrakula пишет:
Нужно спокойно и планомерно освоить Кнута. Все три тома. И задачки порешать, хотя бы те, что не очевидны.
Тоже буду читать Кнута. Но очень много версий одних и тех же томов, какие рекомендуете?

http://mexalib.com/search/?q=%D0%98%D1%81%D0%BA%D1%83%D1%81%D1%81%D1%82%...

 

qwone
qwone аватар
Offline
Зарегистрирован: 03.07.2016

wdrakula. Спасибо. Кнут мне не поможет. Я просто уже приблизился к тому что бы понять свое НЕПОНИМАНИЕ ОПП , а так же языка Си , который повыше С++. Причем не вообще-то в теории ,а в практике.  Так что практика и практика, раз книжек по этой теме нет.

Normas пишет:
Но очень много версий одних и тех же томов, какие рекомендуете?

С этих 

Джефф Элджер - C++ Библиотека программиста

Дейтел Х., Дейтел П - Как программировать на C++

А так же закиньте в закладки это http://document.saraff.ru/   http://cpp.com.ru/kr_cbook/index.html#content  http://netlib.narod.ru/library/book0003/toc.htm

wdrakula
wdrakula аватар
Онлайн
Зарегистрирован: 15.03.2016

Обоим:  

1. Неважно, какие "версии" Кнута читать,

2. во времена Кнута еще не было ООП. Это просто алгоритмы и их теория.

3. Кстати сказать, я тоже не люблю ООП.  Я старый Сишник, реально не молодой :(. Но иногда ООП сильно нагляднее.

 

Normas
Offline
Зарегистрирован: 17.05.2017

wdrakula пишет:
1.Для именно FIFO указатели делаются на первую занятую клетку и первую свободную, а нет так, как вы написали. Тогда никакой керни не происходит.

Если поставить указатель для чтения (начало буфера) на первый занятый элемент, а конец  на первую свободную, по моим подсчетам максимальная заполненность без переполнения буфера все равно будет не SIZE, а (SIZE-1) ?

 

wdrakula
wdrakula аватар
Онлайн
Зарегистрирован: 15.03.2016

подумайте еще раз.. что мешает заполнить его до конца? 

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

Просто проверка на неравенство указателей делается ДО записи.

Перед записью байта делаем проверку, ферштейн зи? Вакаримас ка?

Normas
Offline
Зарегистрирован: 17.05.2017

wdrakula пишет:
подумайте еще раз.. что мешает заполнить его до конца? До состояния, когда оба указателя равны. В этом случае писать некуда.
Практически имеет смысл заполнять его до конца?

wdrakula
wdrakula аватар
Онлайн
Зарегистрирован: 15.03.2016

Normas пишет:

wdrakula пишет:
подумайте еще раз.. что мешает заполнить его до конца? До состояния, когда оба указателя равны. В этом случае писать некуда.
Практически имеет смысл заполнять его до конца?

1.Это Вам решать. Видит Б..г, странный вопрос! Как Вы программу пишите, так она и работает, в ней нет "маленьких зеленых человечков".

2. Вы там выше, какую-то ересь про указатель и степень 2 написали.

Я имел ввиду ТОЛЬКО то, приращение указателя кольцевого буфера записыватся математически так:

p = (p + 1) % <длина буфера>;

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

Например для <длина буфера> = 1024:

p = (p + 1) & 0x03ff; или    p = (p + 1) & 1023;

В откомпилированном коде добавится две инструкции по одному такту... не жалко.

Logik
Offline
Зарегистрирован: 05.08.2014

А если брать буфер 256, ни and ни указателей не нужно, адресация байтовым индексом, сравнения и инкримент самые быстрые. Если скорость так важна как Вы о ней думаете - байт лучший.

andriano
andriano аватар
Offline
Зарегистрирован: 20.06.2015

Normas пишет:

Практически имеет смысл заполнять его до конца?

В таком виде вопрос лишен смысла.

Для чего заполнять до конца (с какой целью)?

Logik
Offline
Зарегистрирован: 05.08.2014

Да уже в общем и не для чего. См. http://arduino.ru/forum/programmirovanie/inline-eto-prinuditelnyi-modifikator-ili-neobyazatelnaya-rekomendatsiya-kompi#comment-284443 Обычная история, попадает челу в руки ардуино - он начинает творит. Творит чего попало, в  основном херню. Не нужен ему буфер. Никакой, циклический - особенно не нужен.

andriano
andriano аватар
Offline
Зарегистрирован: 20.06.2015

Logik, вопрос не в том, для чего нужен кольцевой буфер, а в том, для чего его запонять до конца.

Logik
Offline
Зарегистрирован: 05.08.2014

Этот вопрос не имеет смысла без контекста задачи. А в контексте этой задачи буфер вобще не нужен.

Чисто абстрактно - да может требоватся полное заполнение. Например в протоколе первый блок данных 256 байт, и буфер 256. Если не заполнять полностю, то либо дробить блок либо увеличивать буфер, причем сразу в 2 раза. Оба пути - плохо. Проще обеспечить полное заполнение.

Arhat109-2
Offline
Зарегистрирован: 24.09.2015

qwone пишет:

wdrakula. Спасибо. Кнут мне не поможет. Я просто уже приблизился к тому что бы понять свое НЕПОНИМАНИЕ ОПП , а так же языка Си , который повыше С++. Причем не вообще-то в теории ,а в практике.  Так что практика и практика, раз книжек по этой теме нет.

В таком разе посоветую найти и почитать Пратт "языки программирования разработка и реализация" очень помогает понять "С" и многие иные языки, что называется "изнутри". Ещё можно почитать Ахо, Ульман "Алгоритмы и Структуры данных" или как-то наоборот, уж не помню.. Неплохо почитать книжки Гленфорда Майерса, Баррона, Касьянова и мн. др. Но, это все на сейчас "древности" и описываемые языки уже по большей части исчезли из жизни, разве что "С" остался.

Хотя, Касьянов (оптимизационные преобразования программ) хоть и несколько заумен, но вчитавшись сильно оцените прояснение простой истины: все подходы красивого кода используют те или иные способы оптимизации, что называется "в пальцах"... Очень хорошо у предпоследнего описаны рекурсивные алгоритмы .. ну, в общем по мне - это та классика, которая никогда не бывает бесполезной.

qwone
qwone аватар
Offline
Зарегистрирован: 03.07.2016

Arhat109-2, похоже вы меня не поняли. Что такое математика и ход ее развития. Обычно считается что математика это появление знаков 1-9,0. И все . Дальше идет опрерирование этими знаками. Но скорее всего чем больше развивается математика, чем больше проблем она решает, там больше математика обогащается знаками математической нотации (+,-,х ,/ =  > < ~   ну и так далее) . Разумеется многие знаки проникли в программирование.  Ведь Керниган и Ритчи не придумали язык программирования. Они банально предложили сбалансированую систему программой нотации, которая помогла компактно записать объемные коды на ассемблере. Эта же система оказалась расширяемой в разные стороны. Страуструп предложил сделать еще надстройку, которая еще компактнее записывать код и кусками заимствовать в других программах. Но появилось ООП. Все знают что это хорошо, но где нотация под эту систему. Нет ее. Похоже ООП , как феншуй- все надо делать по феньшую, но у каждого свое представление о феншуе.  А алгоритмы - так они больше как математические задачи. Нужны научить думать головой, но на практике малоприменимы, или применимы только как общее направление.

Logik
Offline
Зарегистрирован: 05.08.2014

Знаете, при попытках решения задач, одна из типовых ошибок - черезмерное ожидание сложности. Так у Вас и с ООП, оно всего только - наследование+инкапсуляция+полиморфиз. Но вмести они позволяют разрабу думать по другому. Вы ж когда на Си пишите не думаете о том как оно в машинном коде выйдет (ну мало кто о таком думает, есть конешно люди, но мало). И уж точно никто не думает как происходит пересылка данных между регистрами МК, все знают, происходит,  есть какие-то шины и стробы там внутри, чтото гдето переключается,,, ну и хрен с ним. А насамом жеж деле там меняются електромагнитные поля, электроны движутся вдали. Тоже нафиг. Этот мой бред к чему был - у того же процесса есть разные уровни описания и абстракции. И ООП  - только один из них, требующий еще меньше вдаватся в детали о потоках електронов чем Си. А на самом деле и электрони и машкод и синтаксис действительно тот же. 

Может так оно Вам понятней будет. Не ждите от ООП многого. В каком то смысле он - электроотвертка. Делает то же что и обычная, зачастую хуже, но быстрей и меньше усилий требует.

qwone
qwone аватар
Offline
Зарегистрирован: 03.07.2016

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

  Все же почему лучше второй метод . Для меня программа не то что запустилось и можно дальше забить на нее и заказчика, а так же кривая работа этой программы. Жизнь все же не сказка.  Программа после запуска должна "жить дальше", проходить различные мелкие средние и крупные изменения и наконец , если повится еще один заказчик, то после некоторого измения втюхать и ему эту программу.  Вот поэтому и надо пытаться программировать в режиме бога, так как менять программу приходится все же после взгляда на нее сверху. Вот по этой причине ООП и лучше. Но это если у вас очень конкретные представления об конкретной ООП и ее структуре, включая названия классов и методов входящих в нее.     

andriano
andriano аватар
Offline
Зарегистрирован: 20.06.2015

Logik пишет:

Чисто абстрактно - да может требоватся полное заполнение. Например в протоколе первый блок данных 256 байт, и буфер 256. Если не заполнять полностю, то либо дробить блок либо увеличивать буфер, причем сразу в 2 раза. Оба пути - плохо. Проще обеспечить полное заполнение.

Вы уверены, что написали сейчас именно про кольцевой буфер?

GarryC
Offline
Зарегистрирован: 08.08.2016

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

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

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

Logik
Offline
Зарегистрирован: 05.08.2014

GarryC пишет:

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

А если смогу? ;)

Но суть проблемы верно замечена. У полностью полного и у полностю пустого указатели (или индексы) указывают на один и тот же элемент. Потому отличит просто так не получится. Но достаточно завести флажок который устанавливается если после добавления данных указатель записи догнал указатель чтения и сравнялся с ним и сбрасывается после любой выборки данных. Все, проблема решена этот флажок позволит отличить пустой от полного. Очевидно его надо проверять при каждой попытке записи. Издержки мизерные. И даже наоборот, может даже ускорится работа т.к. перед добавлением данных будет только флажок проверятся, а не указатели сравниватся.

Прешибаллин
Offline
Зарегистрирован: 23.05.2017

Logik пишет:
Но суть проблемы верно замечена. У полностью полного и у полностю пустого указатели (или индексы) указывают на один и тот же элемент. Потому отличит просто так не получится. Но достаточно завести флажок который устанавливается если после добавления данных указатель записи догнал указатель чтения и сравнялся с ним и сбрасывается после любой выборки данных. Все, проблема решена этот флажок позволит отличить пустой от полного. Очевидно его надо проверять при каждой попытке записи. Издержки мизерные. И даже наоборот, может даже ускорится работа т.к. перед добавлением данных будет только флажок проверятся, а не указатели сравниватся.

Перед каждой записью все равно нужно проверять указатели не неравенство. Какой смысл выставлять флажок, если такая проверка и есть флажок, а больше он никому не нужен?

Arhat109-2
Offline
Зарегистрирован: 24.09.2015

qwone пишет:
Но появилось ООП. Все знают что это хорошо, ... Похоже ООП , как феншуй- все надо делать по феньшую, но у каждого свое представление о феншуе.  А алгоритмы - так они больше как математические задачи. Нужны научить думать головой, но на практике малоприменимы, или применимы только как общее направление.

Столько штампов в одном абзаце встречаю только у хохлосрачников .. как Вам это удалось?

1. Видиом я (и многие мои коллеги) - явно "не все", ибо знают насколько ООП - плохо во всех смыслах.

2.Алгоритмы не равно "метаематические задачи". Почто так - задачка на дом.

3. На практике Кнут - это сборище шикарных ПРАКТИЧЕСКИХ алгоритмов. Также как и алгоритмы разных "ахо-карасиков".. они потому и зовутся "классикой", что сделать иначе можно только через *опу. №все украдено до вас" (как правило программистами нашего и старше поколений)

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

Вот, к сожалению .. как раз непонимание почто вам рекомендуют то да это и приводит к тому, что у каждой программы остается только ДВА состояния:

первое - "Вау, как круто! Щас мы тут такую шикарную фигню забабахаем!"

и второе: -"Какой дебил это писал?!?"

Не в обиду, а так к слову.. :)

qwone
qwone аватар
Offline
Зарегистрирован: 03.07.2016

Arhat109-2. Я вас услышал. Забабахать программу аналогичную моим вам не удастся, код я не прячу, по многим причинам  1- зачем вам это надо, у вас и так есть много задач для решения, 2- зачем писать по другому если и так замечательно выходит, 3- вы не понимаете полностью причины почему я так пишу, а значит видите много "лишнего и ненужного", 4- как ни странно  код с моей точки не оптимален, ему есть куда развиваться. Как в ширину - надо еще много написать кирпичиков-классов. Как в глубину - написать полноценую ОС или программный движок. Вот их я пока не наблюдаю в среде Ардуино. В крайнем случае в открытом коде. Или у вас он завалялся??

Arhat109-2
Offline
Зарегистрирован: 24.09.2015

Как хотите. Вашего п.1 - действительно "за глаза" достаточно. Я лишь посоветовал "что почитать" из классики и для лучшего понимания, за которые Вы вроде сетовали.

Logik
Offline
Зарегистрирован: 05.08.2014

Прешибаллин пишет:

Logik пишет:
Но суть проблемы верно замечена. У полностью полного и у полностю пустого указатели (или индексы) указывают на один и тот же элемент. Потому отличит просто так не получится. Но достаточно завести флажок который устанавливается если после добавления данных указатель записи догнал указатель чтения и сравнялся с ним и сбрасывается после любой выборки данных. Все, проблема решена этот флажок позволит отличить пустой от полного. Очевидно его надо проверять при каждой попытке записи. Издержки мизерные. И даже наоборот, может даже ускорится работа т.к. перед добавлением данных будет только флажок проверятся, а не указатели сравниватся.

Перед каждой записью все равно нужно проверять указатели не неравенство. Какой смысл выставлять флажок, если такая проверка и есть флажок, а больше он никому не нужен?

Значит Вы ниче так и не поняли. Нет перед записю проверять указатели на неравенство не нужно. Только флаг проверять. А он установлен или сброшен при предыдущей операции. Там делался инкремент, указатели проверялись и в зависимости от результата флаг устанавливался или нет. Если бы Вы внимательно читали то наверно догадались бы что у флажка этого очевидное название - чтото типа "Буфер заполнен целиком, места нет". Зачем еще дополнительные проверки?