Что нового я узнал о компьютере, когда решил написать Chrome Dino на C



Немного о проекте


Для знакомства с языком с я решил написать небольшое приложение chrome dino, которое является неудачным клоном всем знакомого динозаврика из хрома. Из-за отсутствия классов в си я решил изобрести свой велосипед: поля и методы класса поместил в структуру, конструктором стала функция, которая возвращает эту структуру. Внутренние поля и методы скрыты, указав перед ними static. (Про это есть несколько статей)

.

typedef struct Barrier {
    int width, height;
    int *picture;
    int x0, y0;
} Barrier;

Barrier* new_Barrier() {
  Barrier* barrier = NULL;
  barrier = malloc(sizeof(Barrier));

  return barrier;
}

Для удобства работы с графикой изображения хранятся в виде матрицы со
значениями [0, 1, 2, 3], это решение подтолкнуло на написание этой
статьи.
0 — прозрачный,
1 — синий,
2 — черный,
3 — серый.




Компьютер не знает что такое массивы, а двумерные — тем более


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


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


Для перебора ряда данных (одномерный массив) берется адрес первого элемента, а затем в цикле (с шагом = размер типа данных) осуществляется переход на следующий адрес.


int n = 10;
int step = sizeof(Barrier);
Barrier* barrier = malloc(step * n);

for (int i = 0; i < n; i += step) {
  *(barrier + i) = data;
}

Реализовать поиск элемента в двумерном массиве становится сложнее, по причине того, что весь массив записывается в последовательные ячейки и поиск приходится осуществлять по строке, а не матрице. Для поиска элемента матрицы в строке можно по формуле:


$$display$$A[ i ][ j ] = i * w + j$$display$$



где A — двумерный массив,
      i — индекс строки,
      j — индекс столбца,
      w — длинна вложенного массива A (ширина массива)

Еще сложнее найти элемент трехмерного массива, для его поиска необходимо воспользоваться формулой:


$$display$$B[ i ][ j ][ k ] = i * w * h + j * w + k$$display$$



где B — трехмерная матрица,
      k — индекс ряда двумерных матриц,
      h — длина вложенного массива B(высота матрицы).

Понятно, что для реализации работы с большей вложенностью массивов необходим единый алгоритм поиска его элемента:


$$display$$C[a_1][a_2]...[a_n] = \sum_{i = 1}^n a_i * L_{i - 1} * ... * L_1$$display$$


где C — n-мерный массив,
      n — вложенность,
      $inline$a_i$inline$ — индекс i-го массива,
      $inline$L_i$inline$ — длинна массива i.

Если за ось ординат принять количество операция компьютера, а за ось абсцисс — вложенность, то можно увидеть, как растет количество операций для вычисления элемента массива с увеличением вложенности. (Сумма и умножение приняты за одну операцию).




Помнить о памяти


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


Рассмотрим случай одномерного массива c элементами типа Barrier. Если количество элементов известно заранее, то для такого массива память выделяется один раз. В случае динамического массива, приходится каждый раз пересчитывать размер выделяемой для него памяти (если длина массива изменяется). Тогда для реализации стандартного метода push (добавление элемента в конец массива) необходимо выделить область памяти (равный сумме размера старого массива и величины типа элемента) и записать туда новый массив, а старый удалить. То же и с удалением элемента из массива.


int n = 10;
int step = sizeof(Barrier);
Barrier* barrier = malloc(step * n);

for (int i = 0; i < n; i += step) {
    *(barrier + i) = data;
}

n = 11;
free(barrier);
barrier = malloc(step * n);

for (int i = 0; i < n; i += step) {
    *(barrier + i) = data;
}

Можно сделать вывод: изменение размера массива довольно затруднительная операция, особенно если идет большой цикл добавления элементов в массив. Некоторые высокоуровневые языки выделяют чуть больше области памяти под массивы (например, ArrayList в java), видимо для повышения производительности.



Не примитивный примитив


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



Посмотреть проект можно туть.
Ads
AdBlock has stolen the banner, but banners are not teeth — they will be back

More

Comments 26

    0
    Автор, возможно, хотел сказать, что в структуры он поместил указатели на будущие методы. Потому что структуры в Си НЕ МОГУТ содержать функции!
      +1

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

        0

        Но могут содержать ссылки на функции, так ведь?

        • UFO just landed and posted this here
            0

            Я по своей глупости слово "ссылка" использовал как синоним "адрес". Спасибо за комментарии)

        +25

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

          +1

          Все структуры объявлены по два раза, память под барьеры почему не переиспользуется, а выделяется всегда больше. Все структуры всегда аллцируются на куче — не надо так. Про поток сознания из последнего абзаца вообще сказать нечего

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

            Для перебора ряда данных (одномерный массив) берется адрес первого элемента, а затем в цикле (с шагом = размер типа данных) осуществляется переход на следующий адрес.

            int n = 10;
            int step = sizeof(Barrier);
            Barrier* barrier = malloc(step * n);
            for (int i = 0; i < n; i += step) {
                *(barrier + i) = data;
            }

            Простите, что?!


            Во-первых, в арифметике указателей уже учитывается размер типа данных, например, прибавление 1 к указателю типа int* прибавит sizeof(int).


            Во-вторых,


            for (int i = 0; i < n; i++) {
                barrier[i] = data;
            }
            
              0

              i[barrier] = data, тоже подойдет… Поэтому, в принципе, у автора там верно.

                0

                а может поэтому это ненормальное программирование?
                может это такой юмор?

                  +1

                  Потому что так по стандарту, адрес элемента массива ничто иное, как i + barrier, а потому без разницы как обращаться barrier + i, т. е. barrier[i] или i + barrier, т. е i[barrier]. Это не юмор, это Си.

                  0

                  Я не хотел говорить об арифметике указателей, мне хотелось рассказать про то, как это как это работает внутри.
                  Спасибо за комментарии)

                    0
                    Приведённый выше Ваш код просто некорректный странно, что приложение не падает (или падает?), так как происходит выход за пределы выделенной памяти.
                  +3

                  По-моему, вы мало что узнали, но запутались окончательно. Например, в Си вообще нет ссылок, только указатели. Лучше, все таки вначале, что то почитать.

                    +2
                    Компьютер не знает что такое массивы

                    Хабру точно нужны такие детсадовские статьи?

                      –2

                      image
                      Автор начните с учебника по С

                        0

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

                          0
                          В ассемблере любая переменная хранит как ссылку на ячейку памяти, так и значение, которое в ней хранится.

                          Переменная может и в регистре храниться.
                            +1
                            Эх, всё-таки нас правильно учили: сначала устройство компьютера, потом ассемблер, потом С, потом С++, и только потом всякие джавы. А нет, вру, сначала были алгоритмы и структуры данных. Т.е. знакомили с основ, постепенно повышая уровень абстракции.

                            А теперь не знают ничего ни про регистры, ни про устройство памяти, ни что такое реальный\защищенный режим. Начинают сразу с джаваскрипта, а С\С++ — это уже «сложно-непонятно» и позорятся незнанием.
                              +1
                              У меня на первом курсе с самого начала параллельно давали знания о булевой алгебре и физике логических элементов. На 3 курсе лаба была — на fpga свой процессор сделать. А там еще и сети были, и всякие цифро-аналоговые системы, системное программирование, схемотехника, теорверы и прочее.

                              Были ли полезны эти знания в работе непосредственно — нет. Помогло ли в обучении реально используемым вещам — очень даже.

                              Написать шейдер для unity 3d — без проблем. Навалять скриптик на python — легко. Распределенная приложуха на aws — дайте документацию, будет готово к вечеру. Написать прототип на embedded проект — вообще не напрягаясь.

                              Такая солянка в универе напрочь отбила любой страх обучению новому и дала гибкость. Даже банальная «чуйка» выработалась — базовые вещи уже на уровне инстинктов отложились, и часто пробелы в конкретных вещах компенсируются умением быстро докопаться к истине.

                              За 7 лет работы в на самых разнообразных проектах не возникало трудностей от слова совсем, и не потому что я знаю все на свете, а потому что научили учится.
                                +2
                                потом С, потом С++, и только потом всякие джавы.

                                Не троллинга ради, а интересных мыслей получения для: какой сакральный смысл в этой цепочки у С++? Да, на нем много всякого прикладного понаписано, но ведь при необходимости к нему вполне можно будет вернуться без потерь, нарушив озвученный порядок. Он ведь не даст каких-то сакральных знаний в сравлении с той же Java, это будет еще одна имплементация того же ООП.
                                  0
                                  логично же: сначала процедурное программирование, потом ООП, а потом на выбор что заинтересует
                                    0
                                    Не логично учить ООП через C++. Язык имеет достаточно отличий от C, чтобы не отдавать ему приоритет на фоне остальных С-подобных. Он объективно сложен, причем победа над этой сложностью не дает преимущества при освоении других языков и технологий впоследствии.
                                      0
                                      Да, почему-то нередко ООП в С++ представляют «каноничным», «таким, какой должен быть», при этом ругая джаву. А вот лично мне он видится там страшным костылём.
                                      Хотя, что ожидать от человека (меня), который начал с ZX бейсика и ассемблера, а в «настоящие компьютеры» вошел с изучением Perl, Java и PHP (да-да, все версии 4ые)…
                                0

                                А я узнал, что существительное "длина" может писаться как с одной, так и с двумя "н". По-видимому в зависимости от того, насколько длинна эта длина. Интересно, если ли версия с тремя "н"?

                                  0

                                  Да, а еще жираф — это длинношеее животное с тремя буквами "е", следующими подряд :)

                                Only users with full accounts can post comments. Log in, please.